使用 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，可能划分为子集。用所有免费 nbr 1-N 预填充 Redis 看起来很难看。

假设 N 的大小为 65536。

以上任何解决方案 better/worse 是否出于性能或其他原因？有没有 better/smarter 方法，也许可以利用 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

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

记录一个值被使用 SETBIT:

SETBIT key [nbr] 1

要找到免费的 nbr 使用 BITPOS:

BITPOS key 0

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

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

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

Use Redis to generate unique ID from a limited range

algorithm

sparse-matrix

redis