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

Question

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

我正在使用DynamoDB和Redis。我无法在上创建DynamoDB索引nbr。到目前为止，我的想法是使用Redis跟踪用于特定组的数字，以便为Redis密钥（例如，<MYGROUP>-item- nbrs我可以存储所有used
nbr：s并实现逻辑以查找下一个free）nbr。在使用范围内的nbr孔是可以接受的，但是在考虑用完的数量之前，应先填充孔。

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

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

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

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

• 将我的nbr：s划分为称为p1-20，p21-40，p41-60等的字段，每个字段仅包含该分区内的一组使用过的nbr：s，并且在分区耗尽时不再使用（不再可用nbr： s），将其完全删除以加快进一步的迭代速度。使用HSCAN进行迭代，然后使用HSET启动新分区。

• 存储所有可用空间nbr而不是所有可用空间，并使用排序后的集合和ZPOPMIN或常规列表和LPOP（可能会划分为子集）。不过，使用所有免费的nbr1-N 预先填充Redis 似乎很丑。

假设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

如何使用位图来尽可能记录nbr是否使用该值？

要记录使用的值，请使用SETBIT：

SETBIT key [nbr] 1

要免费nbr使用BITPOS：

BITPOS key 0

为了避免比赛条件，您需要确保获取和设置是原子的。OP在后续问题中解决了这个问题

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