在分布式和并发环境中生成唯一的序列号时，需要进行哪些权衡？

Question

我对在分布式并发环境中生成唯一序列号的禁忌和权衡感到好奇。

想象一下:我有一个系统，它所做的就是在每次询问时返回一个唯一序列号。下面是这样一个系统(约束)的理想规范：

• 在高负荷下熬夜。
• 允许尽可能多的并发连接。
• 分布式:将负载分散在多台机器上。
• 性能:尽可能快地运行，并且有尽可能多的吞吐量。
• 正确性:生成的数字必须：
  1. 不重复了。
  2. 每个请求都是唯一的(如果任何两个请求同时发生，则必须有断开联系的方法)。
  3. 按(增加)顺序排列。
  4. 请求之间没有漏洞:1，2，3，4.(实际上是一个总计#请求的计数器)

​

• 容错:如果一台或多台机器故障，它可以在故障前恢复到状态。

显然，这是一个理想化的规范，并不是所有的约束都能完全满足。见帽定理。不过，我很想听听你对各种限制因素的分析。我们将留下什么样的问题，我们将使用什么算法来解决剩下的问题。例如，如果我们去掉了计数器约束，那么问题就会变得容易得多:因为允许出现空白，所以我们只需对数字范围进行分区，并将它们映射到不同的机器上。

欢迎任何参考资料(论文、书籍、代码)。我还想保存一个现有软件的列表(不管开源与否)。

软件

• 雪花：一种网络服务，用于在高比例尺上生成唯一的ID号，并提供一些简单的保证。
• 键空间：一个可公开访问的、唯一的128位ID生成器，其ID可用于任何目的。
• RFC-4122实现以多种语言存在。。RFC规范可能是一个非常好的基础，因为它不需要任何系统间的协调，UUID是128位，当使用来自实现特定规范版本的软件的ID时，它们包括一个时间代码部分，使排序成为可能，等等。

Answer 1

如果您必须是顺序的(每台机器)，但可以删除gap/计数器请求，请按照RFC 4122中指定的那样查找版本1的UUID的实现。

如果您在.NET中工作，并且可以消除顺序和间隙/计数器的要求，只需使用System.Guid。它们实现RFC 4122版本4，并且在机器和请求之间已经是唯一的(非常低的碰撞概率)。这可以很容易地作为web服务实现，或者只在本地使用。

Answer 2

这里有一个高层次的方法，可以满足所有的需求，尽管有一个重要的警告，可能与许多用例不匹配。

如果您可以容忍有两个序列号--一个逻辑序列号立即返回；保证唯一和有序，但有间隙--以及一个单独的物理序列号保证顺序顺序，没有间隙，并在一段时间后可用--那么解决方案看起来很简单：

• 一种能提供高分辨率时钟+机器id作为逻辑序列号的分布式系统。
• 将所有逻辑序列号流到一个单独的分布式系统中，该系统对逻辑序列号进行排序，并将它们映射到物理序列号。

从逻辑到物理的映射可以在第二个系统完成处理后立即按需进行。