我很好奇在分布式和并发环境中生成唯一序列号的约束和权衡。
想象一下:我有一个系统,它所做的只是在你每次询问时返回一个唯一的序列号。这是此类系统的理想规范(约束):
- 在高负荷下保持站立。
- 允许尽可能多的并发连接。
- 分布式:将负载分散到多台机器上。
- 性能:尽可能快地运行并具有尽可能多的吞吐量。
- 正确性:生成的数字必须:
- 不重复。
- 每个请求都是唯一的(如果任何两个请求同时发生,则必须有办法打破关系)。
- 以(增加)顺序。
- 请求之间没有间隙:1,2,3,4...(实际上是总数 # 个请求的计数器)
- 容错:如果一台或多台或所有机器宕机,它可以恢复到失败前的状态。
显然,这是一个理想化的规范,并非所有约束都可以完全满足。见CAP 定理。但是,我很想听听您对各种放宽约束的分析。我们将留下什么类型的问题以及我们将使用什么算法来解决剩余的问题。例如,如果我们摆脱了计数器约束,那么问题就变得容易多了:由于允许有间隙,我们可以对数值范围进行分区并将它们映射到不同的机器上。
欢迎任何参考资料(论文、书籍、代码)。我还想保留一份现有软件(开源与否)的列表。
软件:
- Snowflake:一种用于大规模生成唯一 ID 号的网络服务,并提供一些简单的保证。
- keyspace:一个可公开访问的唯一 128 位 ID 生成器,其 ID 可用于任何目的
- RFC-4122 实现存在于多种语言中。RFC 规范可能是一个非常好的基础,因为它避免了任何系统间协调的需要,UUID 是 128 位的,并且当使用来自实现特定版本规范的软件的 ID 时,它们包含一个时间码部分,排序可能等。