两天前，Mike Malone 在 Medium 上发表了一篇很有意思的文章，讲的是 V8 中 Math.random() 的实现，以及所使用的 PRNG 质量有多弱：http://bit.ly/1SPDraN。

这篇文章今天登上了 Hacker News 的热门榜单。它把 Math.random() 是如何出问题的、又该如何修复讲得非常清晰透彻，所以就问题本身我没什么要补充的。不过，作者是在生成大概率不冲突的大尺寸 ID 的场景下发现 PRNG 的弱点的，我想分享一种自己过去多次使用过的替代方案，它既快速又极其可靠。

唯一 ID 的难题

理论上，如果你想生成唯一 ID，就需要保存某种状态来确保 ID 永不重复。最简单的情况就是用一个计数器。但必须以一致的方式保存上一次生成的 ID。系统重启时，绝不能因为存储的计数器没有正确持久化到磁盘，就再次生成相同的 ID。

如果要让多个进程来生成唯一 ID，每个进程都必须确保给自己的 ID 加上一个进程专属的前缀，这个前缀永远不会与其他进程的前缀冲突。这同样管理起来很复杂。仅仅为了可靠地保存上一个 ID，就会在我们需要每秒生成大量 ID 时耗费大量时间。

好在有一个简单的解决方法。在 0 到 N 之间生成一个随机数，让 N 足够大，使得碰撞概率在任何实际应用中都可以忽略不计。这个方法的前提是我们生成的数字在 0 到 N 之间是均匀分布的。如果这个前提成立，我们就可以利用生日悖论来计算碰撞概率。

只要位数足够多，就能轻易让碰撞概率比小行星撞击地球的概率还要低数十亿倍，即使我们以每秒数百万个 ID 的速度持续生成数百年。如果你觉得这个余量还不够，只需再增加位数，就能轻松让 ID 空间比宇宙中的原子总数还要大。

这种生成方式有一个巨大的优势：它是完全无状态的。多个节点可以同时生成 ID 而无需交换消息。而且不需要在磁盘上存储任何东西，所以速度完全取决于 CPU 有多快。计算量很小，完全可以放进 CPU 缓存。因此它非常快速、方便。

Mike Malone 用的正是这个思路，他利用 PRNG 来创建一个由一组字符组成的 ID，每个字符都是 64 种可能字符之一。为了生成每个字符，他使用了 V8 中那个较弱的 PRNG，结果导致了碰撞。别忘了，我们最初的假设是每个新 ID 都必须在 0 到 N 的空间中均匀选取。

你可以通过使用更强的 PRNG 来修复这个问题，但这需要对 PRNG 进行分析。另一个问题是种子——重启后如何再次启动进程，以确保不会再次使用 PRNG 的初始状态？否则，你真正的 ID 空间受限于 PRNG 的种子空间，而不是其输出空间本身。

出于以上所有原因，我想向大家展示一个能避免大多数这些问题的简单技巧。

使用加密哈希函数生成唯一 ID

加密哈希函数是一种不可逆的函数，它将一串比特转换为固定长度的比特串。它们被设计用来抵御各种攻击，不过在这一应用中，我们只依赖它们的一个特性：输出的均匀性。输入中改变一位，输出的每一位都有 50% 的概率发生变化。

为了获得可靠的种子，我们借助操作系统的帮助，通过读取 /dev/urandom 来获取。给生成器设置种子是一个我们确实需要外部熵的时刻，否则就很可能犯下大错，再次生成相同的序列。

作为加密哈希函数的例子，我们将使用著名的 SHA1，它的输出是 160 位。注意，在这个场景下你甚至可以使用 MD5：它的那些安全漏洞对我们的用法没有任何影响。

我们先创建一个种子，从 /dev/urandom 读取 160 位。用伪代码表示大致如下：

seed = devurandom.read(160/8)

我们还会初始化一个计数器：

counter = 0

接下来是每次生成新 ID 的函数：

function get_new_id()
    myid = SHA1(string(counter) + seed)
    counter = counter + 1
    return myid
end

基本上，我们有一个固定的字符串作为种子，然后用递增的计数器与它一起做哈希，所以如果种子是“foo”，我们输出的新 ID 就是：

SHA1(“0foo”)
SHA1(“1foo”)
SHA1(“2foo”)

这对于我们的用例来说已经足够好了。不过我们可能还需要让 ID 难以被预测。为了让 ID 变得极难预测，只需在 get_new_id() 函数中不用 SHA1，而改用 SHA1_HMAC()，其中种子作为密钥，计数器作为 HMAC 的消息。

这种方法速度很快，能保证良好的分布，因此碰撞难度就和生日悖论预测的一样，无需对 PRNG 进行分析，而且是完全无状态的。

我在自己的 Disque 项目中就用它在分布式系统的多个节点之间生成消息 ID。

Hacker News 讨论帖见：https://news.ycombinator.com/item?id=10606910