小编典典

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

redis

我有一些数据库项目,除了它们的主键外,还需要一个索引,这些索引对于项目所属的组是唯一的。让我们称之为属性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
  }
}

阅读 308

收藏
2020-06-20

共1个答案

小编典典

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

要记录使用的值,请使用SETBIT

SETBIT key [nbr] 1

要免费nbr使用BITPOS

BITPOS key 0

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

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

2020-06-20