algorithm - 使用 Redis 从有限范围内生成唯一 ID

Question

我有一些数据库项目，除了它们的主键之外，还需要一个对于项目所属的组唯一的索引。我们称该属性为nbr ，以及将项目组合在一起并定义唯一范围的属性 nbr :s 我们会调用 group .这nbr必须在 [1-N] 范围内，并且当从外部源导入项目时可以设置。因为所有项目都必须有 nbr ，然后任务变成了如何跟踪使用了哪些值，以启用免费的 nbr对于手动添加的新项目。

我正在使用 DynamoDB 和 Redis。我不能在 nbr 上建立 DynamoDB 索引.到目前为止，我的想法是使用 Redis 来跟踪哪些数字已用于特定组，以便对于 Redis key ，例如 <MYGROUP>-item-nbrs我可以存储所有用过的 nbr :s 并实现查找下一个空闲 nbr 的逻辑.使用范围内的孔nbr是可以接受的，但是在考虑用尽数字之前应该填补漏洞。

本质上，我想找到最大大小为 N 的稀疏数组中未使用的索引。

将此信息存储在 Redis 中以便快速找到免费 nbr 的良好结构是什么？ ？到目前为止，我的想法包括:

• 按排序顺序排列的所有已用 nbr 的单个逗号分隔字符串？要查找免费的 nbr，请输入 GET发出命令并解析字符串，直到找到一个空洞或列表的末尾，将选择的数字插入到字符串中，然后替换整个字符串。当 N 很大时，这似乎非常低效。

• 一个散列，其中每个都使用 nbr存储为自己的字段，并使用例如HSCAN遍历哈希字段以找到免费的 nbr .当N很大时，HSCAN必须扫描很多字段。

• 分区我的 nbr :s 进入名为 say p1-20、p21-40、p41-60 的字段，每个字段都包含一组已使用的 nbr :s 仅在该分区内，并且当分区耗尽时(不再有可用的 nbr :s)，将其完全删除以加速进一步的迭代。使用 HSCAN 进行迭代，使用 HSET 开始一个新的分区。

• 存储所有免费 nbr而不是全部使用，并使用排序集和 ZPOPMIN 或常规列表和 LPOP，可能划分为子集。使用所有免费的预填充 Redis nbr虽然 1-N 看起来很丑。

假设 N 的大小为 65536。

出于性能或其他原因，上述任何解决方案是否更好/更差？有没有更好/更聪明的方法，也许可以利用 Redis 的一些我不知道的聪明方面？

编辑:

Kevin 的回答导致了以下解决方案(伪代码):

function getFreeNbr() {
  while (true) {
    send "WATCH numbers"
    nbr = send "BITPOS numbers 0"

    if nbr < N
      send "MULTI"
      send "SETBIT numbers $nbr 1"
      if send "EXEC" != NULL
        return nbr
      end if
    else 
      send "UNWATCH numbers"
      return -1
    end if
  }
}

Answer 1

对于每个可能的 nbr，使用 Bitmaps 记录是否使用该值怎么样？

要记录一个值被使用，使用 SETBIT :

SETBIT key [nbr] 1

要找到免费的 nbr 使用 BITPOS :

BITPOS key 0

为避免竞争条件，您需要确保您的获取和设置是原子的。 [OP 在 follow-up question 中解决了这个问题。]

这将需要非常少的内存(8K 字节用于 65536 个可能的值)。 BITPOS 是 O(n)，但这不太可能成为真正的问题。