Free Online Developer Tools - ULID, UUID, NanoID, CUID, Snowflake ID, JWT Decoder, Base64, JSON Formatter & More

工具菜单

碰撞计算器

根据生成速率、节点数和时长估算 ULID 碰撞概率。计算在每个毫秒内使用 80 位生日界,再把这个概率累积到整个时间窗口。

ULID 碰撞概率计算器

根据您的生成量、机器数量和运行时间评估分布式系统中的 ID 碰撞风险。

ULID 碰撞指的是什么

ULID 是 128 位,写成 26 个 Crockford Base32 字符。前 48 位是以毫秒计的 Unix 时间戳,其余 80 位是随机数。两个 ULID 只有在两部分都相同的时候才相等,所以碰撞只可能发生在同一个毫秒里。

因此,好几个月的总量通常并不吓人。生日问题不是对着整个生命周期的总数算的。它先看落在同一毫秒里的 ID,再把这个很小的概率对窗口中的每一个毫秒重复一次。

本页使用的公式

在一个毫秒内,从 d = 2^80 种取值里抽取 n 个 80 位随机后缀。至少出现一次重复的概率就是生日界。n 不大时,大约是 n(n-1) / 2^81,因为 2 x 2^80 = 2^81。2^80 等于 1,208,925,819,614,629,174,706,176。

这个计算器使用相近的形式:每个毫秒 n^2 / 2^81,比 n(n-1) / 2^81 略高。n 是整个集群在一毫秒内的数量:把每个节点的速率换成每毫秒的 ID 数,再乘以节点数。M 是时长里的毫秒数。一年按 365.25 天、一个月按 30.4375 天,与表单一致。整个窗口内至少发生一次碰撞的概率约为 1 - exp(-M x n^2 / 2^81)。当指数小于 10^-6 时,页面直接显示这个指数,因为此时 1 - exp(-x) 和 x 已经无法区分。

模型假设速率是均匀摊开的,并且每个节点独立抽取随机后缀。把很多 ID 挤进少数几个毫秒,会比同样的平均速率更危险,因为概率随 n 的平方增长。

演算例子

一个毫秒内 1,000 个 ID。用更紧的配对数:1,000 x 999 / 2^81 = 4.13 x 10^-19。要在同一个毫秒里生成大约一万亿个 ID,这个概率才会变得平常。2^40 大约是 1.1 x 10^12。

表单的默认值:每个节点每秒 100 个 ID,10 个节点,持续 5 年。整个集群平均每毫秒 1 个 ID(100 / 1,000 x 10)。M 为 157,788,000,000 毫秒。ID 总数也是 157,788,000,000。累积概率约为 6.53 x 10^-14,大约是 15 万亿分之一。平均值只有每毫秒 1 个时,大多数毫秒里根本没有一对,所以这里的 n^2 形式略微偏高。

计算器上才比较容易读出数字的速率:每一毫秒都有 50,000 个 ID,持续一天。M 为 86,400,000。指数约为 8.93 x 10^-8,大约是 1,120 万分之一。这是每秒 5,000 万个 ID,属于集群规模,不是单个进程。

什么时候用它

  • 你准备把 ULID 当作主键,想要一个对应真实流量的数字,而不是一句关于 80 位的口号。
  • 你想看清真正要填的是每毫秒多少个 ID,而不是表里有多少行。
  • 你在把它和 Snowflake(碰撞是协调错误)或 UUID v4(生日问题把全部历史放进一个桶)比较。

常见误区

  • 不要把生命周期总量塞进一次生日公式。那等于假设所有 ID 都产生于同一毫秒,会把风险放大很多个数量级。
  • 单调 ULID 是另一种模型。在单个进程里把随机段当作计数器递增的库,在 80 位计数回绕之前不会和自己碰撞,而回绕不会发生。剩下的风险只存在于互不协调的进程之间。
  • 时钟回拨会复用一个毫秒。如果随机段也被重置,每次都是一次新抽取的假设就不成立。
  • 页面不会查询数据库。同样的输入永远得到同样的估算。
  • 节点数只有在这些节点于同一毫秒、从同一个 80 位空间抽取时才有意义。每个进程自己的单调计数器不属于这个模型。

碰撞模型有何不同

格式重复可能出现在哪里应该度量什么
ULID(随机后缀)同一毫秒且 80 个随机位相同每毫秒的 ID 数,再在整个窗口上重复
UUID v4整个历史中的任意时刻总量对照 122 个随机位(约 n^2 / 2^123)
Snowflake同一毫秒、同一数据中心、同一 worker、同一序列worker 冲突和序列溢出,不是随机生日界
CUID2(官方实现,长度 24)任意时刻,不按时间分桶长度。一个字母加 23 个 base36 字符大约是 124 位

问题

为什么 ULID 只能在同一个毫秒里碰撞?

前 48 位是时间戳。毫秒不同,前缀就不同,80 位后缀不会跨时间比较。两个 ID 相等必须前缀和后缀都相同。

公式里的 2^81 是什么?

随机后缀有 d = 2^80 种取值。生日界的首项是 n(n-1) / (2d)。2d 就是 2^81。计算器使用 n^2 / 2^81,含义相同,并且略偏保守。

10^-14 的概率算安全吗?

作为标识符是安全的。它远低于数据库主键需要担心的量级。要看的是有多少 ID 共享同一毫秒。平均值接近 1 时还不是碰撞区间。每毫秒持续数万个,指数才会变得可见,而且仍然很小。

单调 ULID 会改变这个结果吗?

会。单调生成器在单个进程内把随机位当作计数器来用,因此该进程不会在同一毫秒重复取值。本页模型是相互独立的随机抽取。它适用于那种设计,不适用于每进程计数器。

它能告诉我表里是否已经有重复吗?

不能。它只根据你输入的速率、节点数和时长计算概率。页面不连接数据库,你输入的内容也不会上传。

请作者喝杯咖啡,支持开发更多好用的工具