10

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

想象一下：我有一个系统，它所做的只是在你每次询问时返回一个唯一的序列号。这是此类系统的理想规范（约束）：

  • 在高负荷下保持站立。
  • 允许尽可能多的并发连接。
  • 分布式：将负载分散到多台机器上。
  • 性能：尽可能快地运行并具有尽可能多的吞吐量。
  • 正确性：生成的数字必须：
    1. 不重复。
    2. 每个请求都是唯一的（如果任何两个请求同时发生，则必须有办法打破关系）。
    3. 以（增加）顺序。
    4. 请求之间没有间隙：1,2,3,4...（实际上是总数 # 个请求的计数器）
  • 容错：如果一台或多台或所有机器宕机，它可以恢复到失败前的状态。

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

欢迎任何参考资料（论文、书籍、代码）。我还想保留一份现有软件（开源与否）的列表。

软件：

  • Snowflake：一种用于大规模生成唯一 ID 号的网络服务，并提供一些简单的保证。
  • keyspace：一个可公开访问的唯一 128 位 ID 生成器，其 ID 可用于任何目的
  • RFC-4122 实现存在于多种语言中。RFC 规范可能是一个非常好的基础，因为它避免了任何系统间协调的需要，UUID 是 128 位的，并且当使用来自实现特定版本规范的软件的 ID 时，它们包含一个时间码部分，排序可能等。
4

2 回答 2

1

如果您必须按顺序（每台机器）但可以放弃间隙/计数器要求，请查找RFC 4122中指定的版本 1 UUID 的实现。

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

于 2011-10-28T19:38:24.077 回答
0

这是一种可以满足所有要求的方法的高级想法，尽管有一个可能与许多用例不匹配的重要警告。

如果您可以容忍有两个序列号 - 立即返回一个逻辑序列号；保证唯一且有序但有间隙 - 并且一个单独的物理物理保证按顺序排列，没有间隙并且稍后可用 - 那么解决方案似乎很简单：

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

一旦第二个系统完成处理，就可以按需进行从逻辑到物理的映射。

于 2014-10-31T17:56:14.780 回答