两天前，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 之间均匀分布。如果这一前提成立，我们就可以利用 birthday paradox（生日悖论）来计算发生碰撞的概率。

只要使用足够多的比特，就很容易让发生碰撞的概率比小行星撞中地球的概率低数十亿倍；即使我们每秒生成数百万个 ID，持续数百年，也是如此。如果这个余量对你来说还不够，那就再增加一些比特；你甚至可以轻松得到比宇宙中原子数量还大的 ID 空间。

这种生成方法有一个很大的优点：它完全 stateless（无状态）。多个节点可以同时生成 ID，而无需相互交换消息。此外，磁盘上没有任何东西需要保存，因此速度可以达到 CPU 所能达到的极限。计算过程也很容易放入 CPU 缓存中。所以它非常快，也非常方便。

迈克使用的正是这个思路：利用 PRNG 创建一个由一组字符组成的 ID，其中每个字符都来自 64 个可能字符中的一个。为了创建每个字符，他使用了有缺陷的 V8 PRNG，结果导致了碰撞。请记住，我们最初的假设是：每个新 ID 都必须在 0 到 N 的空间中均匀选取。

你可以使用更强的 PRNG 来解决这个问题，但这要求对 PRNG 进行分析。另一个问题是播种：进程重启后，你要如何重新启动它，才能确保不会再次选中 PRNG 的初始状态？否则，你实际的 ID 空间就会受 PRNG 的播种方式限制，而不是受其输出空间本身限制。

基于上述所有原因，我想向你介绍一种简单的技术，它可以避开其中的大多数问题。

使用 crypto hash function（密码学哈希函数）生成唯一 ID

密码学哈希函数是不可逆函数，能够将一串比特转换为固定长度的一串比特。它们的设计目标是抵抗各种攻击，不过在这个应用中，我们只依赖它们所具备的一个特性：输出的均匀性。改变哈希函数输入中的一个比特，会导致输出中的每个比特以 50% 的概率发生变化。

为了获得可靠的种子，我们借助操作系统，查询 /dev/urandom。播种时我们确实需要一些外部熵，否则就真的有可能犯下严重错误，再次生成相同的序列。

作为 crypto hash function 的示例，我们将使用广为人知的 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_HMAC() 替代 SHA1，其中种子是密钥，而计数器是 HMAC 的消息。

这种方法速度快，能够保证良好的分布，因此碰撞会像 birthday paradox 所预测的那样难以发生；无需对 PRNG 进行分析，而且它完全无状态。

我在自己的 Disque 项目中使用了这种方法，以便在分布式系统的多个节点之间生成消息 ID。

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