在分布式和并发环境中生成唯一序列号时有哪些权衡？

Question

我很好奇在分布式和并发环境中生成唯一序列号的约束和权衡.

想象一下:我有一个系统,它所做的就是每次提出时都会返回一个唯一的序列号.这是这种系统的理想规范(约束):

保持高负荷.
允许尽可能多的并发连接.
分布式:跨多台机器分散负载.
性能:尽可能快地运行并具有尽可能多的吞吐量.
正确性:生成的数字必须:
1. 不要重复.
2. 每个请求都是唯一的(如果任何两个请求在同一时间发生,则必须有一种断开关系的方式).
3. (增加)顺序.
4. 请求之间没有差距:1,2,3,4 ......(实际上是一个总#请求的计数器)
容错:如果一台或多台机器或所有机器发生故障,它可以恢复到故障前的状态.

显然,这是一个理想化的规范,并非所有约束都可以完全满足.参见CAP定理.但是,我很想听听您对各种限制因素的分析.我们将留下什么类型的问题以及我们将使用什么算法来解决剩余的问题.例如,如果我们摆脱了计数器约束,那么问题就变得容易了:因为允许间隙,我们可以对数值范围进行分区并将它们映射到不同的机器上.

欢迎任何参考(论文,书籍,代码).我还想保留一份现有软件清单(开源与否).

软件:

Snowflake:一种网络服务,可以通过一些简单的保证在大规模生成唯一的ID号.
keyspace:一个可公开访问的唯一128位ID生成器,其ID可用于任何目的
RFC-4122实现存在于许多语言中.RFC规范可能是一个非常好的基础,因为它可以防止任何系统间协调,UUID是128位,并且当使用来自实现某些版本规范的软件的ID时,它们包含一个时间代码部分,可能的分类等

Answer 1

如果您使用 .NET 并且可以消除顺序和间隙/计数器要求，则只需使用System.Guid即可。它们实现了 RFC 4122 版本 4，并且在机器和请求之间已经是唯一的（冲突概率非常低）。这可以很容易地实现为网络服务或仅在本地使用。