python - 从很大范围的数字中分配一个数字的最佳解决方案是什么？

Question

需求说明

有一个数字 1 - 160 000 000 的池。

创建obj时，需要给obj分配一个编号。有一些规则

1. 池中的数字
2. 没有被其他obj占用的数

此外，用户有时会指定一个数字用于对象创建。

下面是一些解决方案，每个都有自己的问题，所以我希望有更好的解决方案

请注意，我们在这里使用 mongo DB。我不想因为这个问题而更改数据库。

解决方案1

生成一个包含 160,000,000 个项目的大表(集合)。 集合的结构是

number,allocated

分配号码时，使用find_one_and_update方法更新一条记录，将分配的false改为true

问题

这个解决方案的问题是生成一个 160,000,000 的集合太重了

解决方案2

与解决方案 1 类似，只是我们不会一次生成 160,000,000。相反，我们每次生成 1000。当这 1000 条记录用完时，我们生成另外 1000 条

问题

问题是用户有时可以指定数字。例如，我们在集合中生成了 1000 条记录，但使用时想使用编号 5000 代替。所以这是现在的问题，因为我们没有生成它

解决方案 3

我们每次创建一个obj，都会给这个obj生成一个1-160,000,000之间的随机数，并保存在db中。

问题

很难避免你生成的随机数以前没有被使用过

Answer 1

执行此操作的通常方法是使用(分片)原子计数器。计数器最初的值为零。当需要索引时，应调用 API 以原子方式递增此计数器并给出其旧值。

虽然这可能比您提到的方法快得多，但根据您的需要，这可能仍然不够快。上述情况的瓶颈是在使增量原子化时通常使用的单个锁。这在某些分布式情况下并不理想。

使用分片计数器:

在这种分布式场景中提高性能的常用方法是使用分片计数器:

1. 切分计数器(将值范围 1..160,000,000 分成 N 不相交的范围)。
2. 在具有 N 个不同锁的 N 个线程/进程/实体/机器中运行相同的原子增量服务。
3. 基于某些属性(可能是对象的地址或对象的散列)，选择范围之一(在分布式系统中，您可以使用分布式散列)
4. 请向 (2) 中提到的相应服务索取下一个索引。

以上将提高性能 N 倍，并且可能会根据您的应用程序需求进行扩展。

关于分片计数器的一些有趣的阅读是在这个 link .

请注意，如果您想使用随机数生成(解决方案 3)，您可以使用 Bloom Filters 优化查找是否存在 key 。 .根据您的性能需求，这可能就足够了。