使用Redis在有限范围内生成唯一ID [英] Use Redis to generate unique ID from a limited range

问题描述

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

I have database items that, in addition to their primary key, need an index unique to the group in which the items belong. Let's call the property nbr, and the property that groups items together and defines the scope of unique nbr:s we'll call group. This nbr must be in the [1-N] range, and may be set when items are imported from an external source. Since all items must have a nbr, the task then becomes how to track which values are used, to enable picking a free nbr for new items that are added manually.

我正在使用DynamoDB和Redis.我在nbr上没有DynamoDB索引.到目前为止，我的想法是使用Redis跟踪用于特定组的数字，以便对于Redis键(例如<MYGROUP>-item-nbrs)，我可以存储所有使用的nbr:s并实现逻辑来查找下一个免费的nbr.可接受的nbr范围内的孔是可接受的，但是在考虑用完的数字之前，应先填充孔.

I'm using DynamoDB and Redis. I cannot have a DynamoDB index on nbr. The idea I have so far is to use Redis to track which numbers have been used for a particular group, so that for a Redis key such as <MYGROUP>-item-nbrs I could store all the used nbr:s and implement logic to find the next free nbr. Holes in the range of used nbr is acceptable, but holes should be filled before considering the numbers exhausted.

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

Essentially I want to find unused indices of a sparse array of max size N.

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

What would be a good structure for storing this information in Redis to quickly find a free nbr? My ideas so far include:

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

• A single comma-separated string of all used nbr's in sorted order? To find a free nbr, a GET command is issued and the string is parsed until a hole is found or the end of the list, the picked number is inserted into the string and then the entire string is replaced. When N is large, this seems very inefficient.

散列，每个使用的nbr都存储为自己的字段，并使用例如HSCAN遍历散列的字段以找到空闲的nbr.当N大时，HSCAN必须扫描很多字段.

A hash where each used nbr is stored as its own field, and using e.g. HSCAN to iterate through the fields of the hash to find a free nbr. When N is large, the HSCAN must scan a lot of fields.

将我的nbr:s划分为名为p1-20，p21-40，p41-60等的字段，每个字段仅包含该分区内已使用的nbr:s的排序集，并且当分区用尽时(不再有可用的nbr:s)，请将其完全删除以加快进一步的迭代速度.使用HSCAN进行迭代，然后使用HSET启动新分区.

Partitioning my nbr:s into fields called say p1-20, p21-40, p41-60, ..., each containing a sorted set of the used nbr:s within that partition only, and when a partition is exhausted (no more free nbr:s), remove it completely to speed up further iteration. Use HSCAN to iterate, and HSET to start a new partition.

存储所有可用的nbr而不是已使用的所有nbr，并使用排序的集和ZPOPMIN或常规列表和LPOP，并可能划分为子集.不过，使用所有免费的nbr 1-N预先填充Redis似乎很丑.

Storing all free nbr instead of all used, and using sorted sets and ZPOPMIN or regular lists and LPOP, possibly partitioned into sub-sets. Pre-populating Redis with all free nbr 1-N seems ugly though.

假设N的大小为65536.

Let's say N is in the magnitude of 65536.

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

Are any of the solutions above better/worse, for performance or other reasons? Is there a better/smarter way, maybe utilizing some clever aspect of Redis that I'm unaware of?

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

Kevin's answer resulted in the following solution (pseudo code):

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
  }
}

推荐答案

如何使用位图记录每个可能的nbr是否使用该值?

How about using Bitmaps to record, for every possible nbr, whether or not that value is used?

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

To record that a value is taken use SETBIT:

SETBIT key [nbr] 1

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

To find a free nbr use BITPOS:

BITPOS key 0

为避免出现竞争状况，您需要确保获取和设置是原子的. [OP在后续问题中解决了此问题.]

To avoid race conditions you'll want to make sure your get-and-set is atomic. [The OP addresses this in a follow-up question.]

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

This will require very little memory (8K bytes for 65536 possible values). BITPOS is O(n), but that's unlikely to be a real problem.

这篇关于使用Redis在有限范围内生成唯一ID的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！