在不锁定的多线程应用程序中生成唯一的数字ids

Question

使用ExecutorService实现n个线程的多线程应用程序。

有x(数千万)任务提交给ExecutorService。

每个任务需要生成数百万项(项数不是常数)，其中每个项必须有一个数字唯一id (最大长度)。

我如何生成这样的ids？

在下列限制的情况下：

• 没有锁！没有阻塞！-性能是最高优先级(所以不能使用随机下一个、AtomicInteger或并发的ids哈希来从中提取)。
• 在所有线程中，Id必须是唯一的。
• 如果可能的话，最好是有顺序的ids，但不是必需的。
• 当然没有星展等等..。

话虽如此，

• 不可能给每个线程一个“it范围”供它使用，因为在理论1线程可以得到99%的任务-所以我们不知道给它什么范围(我们不能只是给它一个很大的范围)。
• 不可能为每个线程创建随机实例，因为唯一性得不到保证。

会感激你的想法。

Answer 1

目前还不清楚为什么标准答案GUID不适合您的情况。如果标准库生成器对您来说太慢了，则有一些可供选择的方法被吹嘘为更快。

如果GUID对您来说太慢了，那么您需要说明需要什么样的性能，以及为什么不能抛出更多CPU来解决问题。

其次，您声明没有锁定/阻塞。但是，对于同一台机器上的线程间通信，您只是获取大量的整数空间作为顺序it使用，几乎不需要任何锁，而且非常快。

“给我Xmil数字的下一个空闲块--每个处理的Xmil项目”必须在‘生成下一个数字的时间’中击败其他任何东西，并且锁定间隔完全在您的控制之下。

如果偶数太慢的话，你可以得到4组有奇数、偶数、负奇数和负偶数的唯一数集。除了您的executorId之外，一个简单的简短taskId可以任意地扩展集合的数量。

Answer 2

如果没有某种形式的同步，则无法跨多个线程获得顺序ID。但是，如果此要求是可选的，则可以在每个线程中有一个单独的计数器，并将其与全局计数器中的线程ID组合起来。例如，64位线程ID与64位线程特定计数器组合成128位整数，保证所有线程都是唯一的。这将是非常快的，因为您只需要增加特定于线程的计数器来生成一个新的ID。

当然，您不应该添加线程ID和计数器，因为这会导致重复。相反，您可以使用线程ID作为128位数字的上64位和计数器作为下64位。

不可能给每个线程一个“it范围”供它使用，因为在理论1线程可以得到99%的任务-所以我们不知道给它什么范围(我们不能只是给它一个很大的范围)。

这只是一个有足够大范围的问题。有了64位计数器，它将能够运行数百年而不会溢出。

或者，您可以使用当前时间戳而不是计数器。这将稍微慢一些，但可能无法测量，而且好处是您不会冒险丢失计数器状态，例如在重新启动的情况下。