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

Question

我有一些数据库项目，除了主键之外，还需要项目所属组的唯一索引。我们将该属性称为 nbr ，以及将项目分组在一起并定义唯一 nbr 范围的属性:我们会打电话group 。这个nbr必须在 [1-N] 范围内，并且可以在从外部源导入项目时进行设置。由于所有项目都必须有 nbr ，任务就变成了如何跟踪使用了哪些值，以便能够选择一个免费的 nbr对于手动添加的新项目。

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

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

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

• 所有使用过的 nbr 的单个逗号分隔字符串(按排序顺序)？要查找免费的 NBR，请输入 GET发出命令并解析字符串，直到找到一个洞或列表末尾，将选取的数字插入到字符串中，然后替换整个字符串。当 N 很大时，这看起来效率很低。

• 每个都使用 nbr 的哈希值存储为自己的字段，并使用例如HSCAN迭代哈希的字段以查找空闲的 nbr 。当N很大时，HSCAN必须扫描很多字段。

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

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

假设 N 的大小为 65536。

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

编辑:

凯文的回答产生了以下解决方案(伪代码):

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

如何使用 Bitmaps 来记录每个可能的 nbr，无论该值是否被使用？

要记录某个值被采用，请使用 SETBIT :

SETBIT key [nbr] 1

要查找免费的nbr，请使用BITPOS:

BITPOS key 0

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

这将需要很少的内存(8K 字节可容纳 65536 个可能的值)。 BITPOS 的复杂度为 O(n)，但这不太可能成为真正的问题。