Infino设计无协调ID生成方案，每秒生成数十亿ID

在设计 Infino 时——截至本文写作时，它是 Search Benchmark Game 上搜索查询最快的引擎，也是 ClickBench 上最快的搜索引擎——我们不得不从零开始重新思考引擎的许多部分，以便为规模化和 agent 查询所需的性能做设计。标识符（id）的生成与使用就是其中之一，本文介绍我们的 id 是如何工作的。写入方以每秒数十亿的速度生成这些 id，彼此之间无需协调，id 在实践中不会冲突，并且经过压缩后，每个 id 副本的存储占用略高于一个字节。

Infino 表中的每一行都有一个系统管理的 _id 列，由引擎分配，用户无法设置。它会随每个搜索结果一起返回，因为用户之后可能想对搜索中看到的文档发起更新或删除请求，需要一个方式来标识文档。此外，表中的每一行都需要存储它，以便能够被返回；在万亿行规模下，id 的每一个字节都要付出 1TB 的存储成本和同等量级的缓存成本。

我们之前关于 Infino 对象存储架构的文章可能会有帮助，但在继续阅读之前并非必需。

考虑到 Infino 写入和查询数据的方式，我们在 id 方案中寻求以下特性。

写入方之间无需协调：Infino 的写入方可以作为多个进程、在多台机器上运行，全部追加到对象存储上的同一张表，而且没有中央服务器来分发标识符。写入方应该从启动那一刻起就能自行生成 id，无需向任何人注册。

按时间有序：许多用例需要根据创建时间检索行，例如获取最新数据或调试。如果 id 本身记录了行的创建时间，那就很好，这样就不需要单独的 timestamp 字段来存储创建时间。由于 Infino 跟踪每个 superfile（Infino 的 Parquet 文件，存放数据和索引）的最小和最大 id，按时间有序的 id 还能让更新和删除跳过那些 id 范围不可能包含目标 id 的 superfile。

存储时紧凑：每一行都存储自己的 id，因此写入时间相近的 id 应该共享大部分比特位并且压缩效果好（随机比特位无法压缩）。

任何 Parquet 读取器都可读：由于 superfile 是普通 Parquet 文件，DuckDB、PyArrow 或任何其他 Parquet 读取器都能打开，_id 应该是一种这些读取器能够理解、并能按时间顺序排序的列类型。

增长空间充足：繁忙的写入方在每毫秒能生成多少 id 上永远不应触及上限，并且 id 的时间戳不应在数据仍在使用期间耗尽——有些方案的时间戳在几十年内就会耗尽。

有几种常见的 id 生成方式。自增是一个计数器，就像数据库序列那样。id 小且有序，但每个写入方都必须经过同一个计数器，因此不同机器上的写入方需要协调器。

UUIDv4 是 122 个随机比特位，因此无需协调，但 id 无序且无法压缩。UUIDv7 和 ULID 都以 48 位毫秒时间戳开头，后跟随机比特位，因此它们按时间有序，不过在同一个毫秒内，只有生成器在随机比特位中维护计数器时它们才保持有序 [1]。

最后，Twitter 的 Snowflake 将 41 位毫秒时间戳、10 位机器 id 和 12 位序列号打包进 64 位。这些 id 小且按时间有序，但必须有人为每台机器分配唯一的机器 id，而且一台机器每毫秒最多只能生成 4,096 个 id。

下表将这些方案与我们所需的特性进行对比，同时列出了 Infino 的 id，我们将在下一节描述它。

这些常见方案没有一个具备全部特性。自增和 Snowflake 需要协调，UUIDv4 没有顺序。UUIDv7 和 ULID 接近了，但它们的随机比特位会带来存储成本，除非生成器恰好是单调的；而且在同一个毫秒内，只有生成器维护计数器时它们才有序。我们设计了自己的 Snowflake 风格 id 来解决这些不足。

Infino 的 id 是一个 128 位的 Snowflake 风格 id [2]，由 64 位毫秒时间戳、40 位写入方 id 和 24 位序列号按此顺序组成。

它与 Snowflake id 有三处不同。第一，写入方 id 是随机的，而非分配的。每个写入方在启动时抽取 40 个随机比特位；在 40 位的情况下，对于最多约 148,000 个并发写入方，同一张表的任意两个写入方抽到相同比特位的概率保持在 1% 以下。因此，无需任何服务来分发写入方 id。Snowflake 用其 10 位机器 id 无法做到这一点，因为仅 32 个写入方时，其中两个抽到相同 id 的概率就有 38%。

第二，序列号是 24 位而非 12 位，因此一个写入方每毫秒可以生成约 1670 万个 id，之后才需要等待时钟跳动，这远远超过一个写入方在一毫秒内追加的数量。

第三，时间戳是 64 位而非 41 位。它不需要自定义纪元，并且作为有符号 128 位整数，id 在数百万年内都保持为正。这让我们可以将 id 存储为普通的 Decimal128(38, 0) Parquet 列，任何 Parquet 读取器都能将其作为数字读取，而对 id 排序就是按它们生成的毫秒排序。

生成器本身维护的状态极少，即只有它最后发出的那个 id。它从一个由后台线程更新的共享毫秒时钟读取当前时间 [3]，因此读取时间是从内存加载而非系统调用，并且时钟永远不会倒退。如果自上一个 id 以来时钟已经跳动，下一个 id 就在新的毫秒从序列号 0 开始；否则，它就是上一个 id 加一。请注意，一个写入方从不写入另一个写入方读取的内存，因此写入方之间不会互相拖慢，即使在同一进程内也是如此。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）