Go 博客

使用 math/rand/v2 演进 Go 标准库

Russ Cox
2024 年 5 月 1 日

自 Go 1 于 2012 年 3 月发布 以来，对标准库的更改一直受到 Go 的 兼容性承诺 的限制。总的来说，兼容性对于 Go 用户来说是一个福音，它为生产系统、文档、教程、书籍等提供了稳定的基础。然而，随着时间的推移，我们意识到最初的 API 中存在无法通过兼容方式修复的错误；在其他情况下，最佳实践和约定也发生了变化。我们需要制定一个计划来进行重要的、破坏性的更改。

这篇博文介绍了 Go 1.22 中新的 math/rand/v2 包，这是标准库中的第一个“v2”。它为 math/rand API 带来了必要的改进，但更重要的是，它为我们如何根据需要修改其他标准库包树立了榜样。

（在 Go 中，math/rand 和 math/rand/v2 是两个不同的包，具有不同的导入路径。Go 1 及其后的所有版本都包含 math/rand；Go 1.22 添加了 math/rand/v2。Go 程序可以导入这两个包中的任何一个或两个。）

这篇文章讨论了对 math/rand/v2 中更改的具体理由，然后 反思将指导其他包的新版本的通用原则。

伪随机数生成器

在我们研究 math/rand 之前，它是一个用于伪随机数生成器的 API，让我们花点时间了解一下它的含义。

伪随机数生成器是一个确定性程序，它从一个小的种子输入生成一个看似随机的数字序列，尽管这些数字实际上并不随机。在 math/rand 的情况下，种子是一个 int64，并且算法使用 线性反馈移位寄存器 (LFSR) 的变体生成 int64 序列。该算法基于 George Marsaglia 的一个想法，由 Don Mitchell 和 Jim Reeds 进行了调整，并由 Ken Thompson 为 Plan 9 和 Go 进行了进一步的定制。它没有正式名称，因此这篇文章将其称为 Go 1 生成器。

目标是使这些生成器快速、可重复并且足够随机以支持模拟、洗牌和其他非加密用例。可重复性对于数值模拟或随机化测试等用途尤其重要。例如，一个随机化测试器可能会选择一个种子（可能基于当前时间），生成一个大的随机测试输入，然后重复。当测试器发现错误时，它只需要打印种子以允许使用该特定大型输入重复测试。

可重复性在时间上也很重要：对于特定的种子，Go 的新版本需要生成与旧版本相同的序列值。我们在发布 Go 1 时没有意识到这一点；相反，我们以困难的方式发现了它，当我们尝试在 Go 1.2 中进行更改时，我们收到了有关我们破坏了某些测试和其他用例的报告。在这一点上，我们决定 Go 1 兼容性包括给定种子的特定随机输出，并 添加了一个测试。

这些类型的生成器的目标不是生成适合于推导出加密密钥或其他重要秘密的随机数。由于种子只有 63 位，因此从生成器中提取的任何输出，无论其长度如何，都将仅包含 63 位的熵。例如，使用 math/rand 生成 128 位或 256 位 AES 密钥将是一个严重的错误，因为密钥更容易被暴力破解。对于这种类型的使用，您需要一个加密强度高的随机数生成器，如 crypto/rand 所提供。

有了足够的背景知识，我们可以继续讨论 math/rand 包中需要修复的内容。

math/rand 的问题

随着时间的推移，我们注意到 math/rand 存在越来越多的问题。最严重的是以下内容。

生成器算法

生成器本身需要替换。

Go 的初始实现虽然是生产就绪的，但在许多方面都是整个系统的“铅笔素描”，工作得足以作为未来开发的基础：编译器和运行时是用 C 编写的；垃圾收集器是一个保守的、单线程的、停止世界的收集器；库在整个过程中使用了基本实现。从 Go 1 到大约 Go 1.5，我们回到了每个的“完全着墨”版本：我们将编译器和运行时转换为 Go；我们编写了一个新的、精确的、并行的、并发式垃圾收集器，其暂停时间为微秒级；并且我们用更复杂、更优化的算法替换了标准库实现，根据需要。

不幸的是，math/rand 中的可重复性要求意味着我们无法在不破坏兼容性的情况下替换生成器。我们被困在 Go 1 生成器中，该生成器速度相当快（在我的 M3 Mac 上约为每数字 1.8ns），但保持着近 5 千字节的内部状态。相比之下，Melissa O’Neill 的 PCG 生成器系列 以每数字 2.1ns 的速度生成更好的随机数，并且只有 16 字节的内部状态。我们还希望探索使用 Daniel J. Bernstein 的 ChaCha 流密码 作为生成器。一篇 后续文章 特别讨论了该生成器。

源接口

rand.Source 接口 是错误的。该接口定义了一个低级随机数生成器的概念，该生成器生成非负 int64 值

% go doc -src math/rand.Source
package rand // import "math/rand"

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
//
// A Source is not safe for concurrent use by multiple goroutines.
type Source interface {
    Int63() int64
    Seed(seed int64)
}

func NewSource(seed int64) Source
%

（在文档注释中，“[0, N)” 表示一个 半开区间，意味着该范围包括 0 但结束在 2⁶³ 之前。）

rand.Rand 类型 包装一个 Source 以实现更丰富的操作集，例如生成 0 到 N 之间的整数，生成 浮点数 等等。

我们定义 Source 接口以返回一个缩短的 63 位值而不是一个 uint64，因为这是 Go 1 生成器和其他广泛使用的生成器生成的，并且它与 C 标准库设定的约定相匹配。但这是一个错误：更现代的生成器会生成完整的 uint64，这是一种更方便的接口。

另一个问题是 Seed 方法硬编码了一个 int64 种子：一些生成器是由更大的值播种的，并且接口没有提供任何方法来处理这种情况。

播种责任

Seed 的一个更大的问题是播种全局生成器的责任不明确。大多数用户不直接使用 Source 和 Rand。相反，math/rand 包提供了一个全局生成器，可以通过顶级函数（如 Intn）访问。按照 C 标准库，全局生成器默认情况下表现得好像在启动时调用了 Seed(1)。这对于可重复性来说是件好事，但对于希望其随机输出在每次运行时都不同的程序来说却是不好的。包文档建议在这种情况下使用 rand.Seed(time.Now().UnixNano())，以使生成器的输出依赖于时间，但什么代码应该这样做？

也许主包应该负责如何播种 math/rand：如果导入的库自己配置全局状态，那将是件不幸的事，因为他们的选择可能会与其他库或主包发生冲突。但是，如果库需要一些随机数据并希望使用 math/rand 会怎么样？如果主包甚至不知道正在使用 math/rand 会怎么样？我们发现，在实践中，许多库都会添加 init 函数，这些函数会使用当前时间播种全局生成器，“以确保安全”。

库包自己播种全局生成器会导致一个新问题。假设包 main 导入两个都使用 math/rand 的包：包 A 假设全局生成器将由包 main 播种，但包 B 在一个 init 函数中播种了它。假设包 main 本身并没有播种生成器。现在，包 A 的正确操作取决于包 B 也在程序中导入的巧合。如果包 main 停止导入包 B，包 A 将停止获取随机值。我们在实践中观察到这种情况发生在大型代码库中。

回想起来，显然按照 C 标准库的做法是一个错误：自动播种全局生成器将消除关于谁播种它的困惑，用户将不再对他们在不希望的情况下获得的可重复输出感到惊讶。

可扩展性

全局生成器也不能很好地扩展。由于顶级函数（如 rand.Intn）可以从多个 goroutine 同时调用，因此实现需要一个锁来保护共享的生成器状态。在并行使用中，获取和释放此锁的成本高于实际生成。相反，拥有一个每个线程的生成器状态更有意义，但这样做会在没有并发使用 math/rand 的程序中破坏可重复性。

Rand 实现缺少重要的优化

rand.Rand 类型 包装一个 Source 以实现更丰富的操作集。例如，以下是 Go 1 实现的 Int63n，它返回 [0, n) 范围内的随机整数。

func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    max := int64((1<<63 - 1)  - (1<<63)%uint64(n))
    v := r.src.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}

实际转换很简单：v % n。但是，没有算法可以将 2⁶³ 个等可能的值转换为 n 个等可能的值，除非 2⁶³ 是 n 的倍数：否则，某些输出必然会比其他输出更频繁地发生。（作为更简单的示例，尝试将 4 个等可能的值转换为 3 个。）代码计算 max，使得 max+1 是小于或等于 2⁶³ 的最大 n 倍数，然后循环拒绝大于或等于 max+1 的随机值。拒绝这些过大的值可以确保所有 n 个输出都是等可能的。对于小的 n 来说，需要拒绝任何值的可能性很小；对于更大的值，拒绝变得更加普遍和更加重要。即使没有拒绝循环，两个（慢速）模运算也会使转换比生成随机值 v 的成本更高。

在 2018 年，Daniel Lemire 发现了一种算法，它几乎可以一直避免除法（另请参阅他 2019 年的博文）。在 math/rand 中，采用 Lemire 的算法将使 Intn(1000) 速度提高 20-30%，但我们无法做到：更快的算法会生成与标准转换不同的值，从而破坏可重复性。

其他方法也比它们可能的速度慢，受到可重复性的限制。例如，如果我们可以更改生成的数值流，Float64 方法可以轻松地提高大约 10% 的速度。（这是我们在 Go 1.2 中尝试进行并回滚的更改，前面提到过。）

Read 错误

如前所述，math/rand 不适合也不适合用于生成加密密钥。crypto/rand 包执行此操作，其基本原语是其 Read 函数 和 Reader 变量。

在 2015 年，我们接受了一项提议，让 rand.Rand 也实现 io.Reader，以及 添加顶级 Read 函数。这在当时似乎很合理，但事后看来，我们没有足够重视此更改的软件工程方面。现在，如果您想读取随机数据，您有两个选择：math/rand.Read 和 crypto/rand.Read。如果数据将用于密钥材料，使用 crypto/rand 至关重要，但现在可以使用 math/rand 代替，这可能会产生灾难性的后果。

像 goimports 和 gopls 这样的工具有一个特殊情况，确保它们更喜欢使用 crypto/rand 中的 rand.Read 而不是 math/rand，但这并不是完整的解决方案。最好完全删除 Read。

直接修复 math/rand

创建新的不兼容的主要版本包永远不是我们的首选：该新版本只对切换到它的程序有利，而所有现有版本的旧主要版本的使用则留在了后面。相反，修复现有包中的问题会产生更大的影响，因为它修复了所有现有的使用。我们不应该在不尽一切努力修复 v1 的情况下创建 v2。在 math/rand 的情况下，我们能够部分解决上面描述的一些问题。

• Go 1.8 引入了可选的 Source64 接口，其中包含一个 Uint64 方法。如果 Source 还实现了 Source64，那么 Rand 会在适当的时候使用该方法。这种“扩展接口”模式提供了一种兼容（虽然略显笨拙）的方式来事后修改接口。

• Go 1.20 自动播种了顶级生成器并弃用了 rand.Seed。尽管这在我们的输出流可重复性重点方面看起来像是不可兼容的更改，但 我们认为，在 init 时或在任何计算中调用 rand.Int 的任何导入包也会明显更改输出流，并且当然添加或删除这样的调用不能被视为重大更改。如果这是真的，那么自动播种不会更糟，并且它将消除未来程序的这种脆弱性来源。我们还添加了一个 GODEBUG 设置 来选择回到旧的行为。然后，我们将顶级 rand.Seed 标记为 弃用。（需要播种可重复性的程序仍然可以使用 rand.New(rand.NewSource(seed)) 来获取本地生成器，而不是使用全局生成器。）

• 在消除了全局输出流的可重复性之后，Go 1.20 还能够在不调用 rand.Seed 的程序中让全局生成器更好地扩展，用一个非常便宜的每线程 wyrand 生成器 代替 Go 1 生成器，该生成器已在 Go 运行时内部使用。这消除了全局互斥锁，并使顶级函数更好地扩展。调用 rand.Seed 的程序将回退到受互斥锁保护的 Go 1 生成器。

• 我们能够在 Go 运行时采用 Lemire 的优化，并且还在 rand.Shuffle 内部使用它，它是在 Lemire 的论文发表后实现的。

• 虽然我们不能完全删除 rand.Read，但 Go 1.20 标记了它 弃用，以支持 crypto/rand。从那以后，我们听说了一些人发现他们在加密上下文中意外地使用了 math/rand.Read，因为他们的编辑标记了对已弃用函数的使用。

这些修复不完美且不完整，但也确实是帮助了所有现有 math/rand 包用户的重要改进。为了更完整地修复，我们需要将注意力转向 math/rand/v2。

修复 math/rand/v2 中的其余部分

定义 math/rand/v2 需要大量的计划，然后是 GitHub 讨论，然后是 提议讨论。它与 math/rand 相同，但以下重大更改解决了上面概述的问题

• 我们完全删除了 Go 1 生成器，用两个新的生成器代替，PCG 和 ChaCha8。新类型以其算法命名（避免使用通用名称 NewSource），这样如果需要添加另一个重要算法，它将很好地融入命名方案。

  根据提议讨论中的建议，新类型实现了 encoding.BinaryMarshaler 和 encoding.BinaryUnmarshaler 接口。

• 我们更改了 Source 接口，用 Uint64 方法替换了 Int63 方法，并删除了 Seed 方法。支持播种的实现可以提供它们自己的具体方法，例如 PCG.Seed 和 ChaCha8.Seed。请注意，两者采用不同的种子类型，两者都不是单个 int64。

• 我们删除了顶级 Seed 函数：现在只能以自动播种的形式使用像 Int 这样的全局函数。

• 删除顶级 Seed 也让我们能够通过顶级方法硬编码可扩展的每线程生成器的使用，避免在每次使用时进行 GODEBUG 检查。

• 我们为 Intn 和相关函数实现了 Lemire 的优化。具体的 rand.Rand API 现在锁定到该数值流，因此我们将无法利用任何待发现的优化，但至少我们再次更新了。我们还实现了我们想在 Go 1.2 中使用的 Float32 和 Float64 优化。

• 在提议讨论期间，一位贡献者指出了 ExpFloat64 和 NormFloat64 实现中的可检测偏差。我们修复了该偏差并锁定了新的数值流。

• Perm 和 Shuffle 使用了不同的洗牌算法并产生了不同的数值流，因为 Shuffle 发生在第二位并使用了一种更快的算法。完全删除 Perm 会使迁移对用户更加困难。相反，我们使用 Shuffle 实现了 Perm，这仍然让我们可以删除实现。

• 我们将 Int31、Int63、Intn、Int31n 和 Int63n 重命名为 Int32、Int64、IntN、Int32N 和 Int64N。名称中的 31 和 63 过于刻板和令人困惑，而大写的 N 在 Go 中更符合第二个“单词”的习惯命名方式。

• 我们添加了 Uint、Uint32、Uint64、UintN、Uint32N 和 Uint64N 顶级函数和方法。我们需要添加 Uint64 来提供对核心 Source 功能的直接访问，并且如果不对其他函数进行添加，这似乎不一致。

• 根据提议讨论中的另一条建议，我们添加了一个新的顶级通用函数 N，它类似于 Int64N 或 Uint64N，但适用于任何整数类型。在旧的 API 中，要创建最多 5 秒的随机持续时间，有必要编写

  d := time.Duration(rand.Int63n(int64(5*time.Second)))
  

  使用 N，等效代码是

  d := rand.N(5 * time.Second)
  

  N 只是一个顶级函数；rand.Rand 上没有 N 方法，因为 Go 中没有通用方法。（通用方法将来也不太可能出现；它们与接口严重冲突，并且完整的实现将需要运行时代码生成或慢速执行。）

• 为了缓解在加密上下文中滥用 math/rand，我们让 ChaCha8 成为全局函数中使用的默认生成器，并且我们还更改了 Go 运行时以使用它（替换 wyrand）。程序仍然强烈建议使用 crypto/rand 生成加密密钥，但意外使用 math/rand/v2 并不像使用 math/rand 那样灾难性。即使在 math/rand 中，全局函数现在在没有显式播种的情况下也会使用 ChaCha8 生成器。

演进 Go 标准库的原则

如本文开头所述，这项工作的目标之一是为我们如何处理标准库中的所有 v2 包建立原则和模式。在接下来的几个 Go 版本中不会出现大量的 v2 包。相反，我们将一次处理一个包，确保我们设置了可以持续十年的质量标准。许多包根本不需要 v2。但对于那些需要的包，我们的方法归结为三个原则。

首先，新版本的不兼容版本包将使用 that/package/v2 作为其导入路径，遵循 语义导入版本控制，就像标准库外部的 v2 模块一样。这允许在单个程序中同时使用原始包和 v2 包，这对于 逐步转换为 新的 API 至关重要。

其次，所有更改都必须以尊重现有使用和用户为基础：我们不能引入不必要的混乱，无论是以对现有包进行不必要的更改的形式，还是必须学习的全新包的形式。在实践中，这意味着我们以现有包为起点，只进行有充分动机并提供价值的更改，这些价值足以抵消用户更新的成本。

第三，v2 包不能抛弃 v1 用户。理想情况下，v2 包应该能够完成 v1 包可以完成的所有操作，并且在发布 v2 后，v1 包应该被重写为 v2 的薄包装器。这将确保 v1 的现有使用继续受益于 v2 中的错误修复和性能优化。当然，鉴于 v2 引入了重大更改，这并不总是可能的，但它始终是需要仔细考虑的事情。对于math/rand/v2，我们安排了自动种子 v1 函数来调用 v2 生成器，但由于可重复性违规，我们无法共享其他代码。最终math/rand 代码量并不多，也不需要定期维护，因此重复是可以管理的。在其他情况下，避免重复的更多工作可能值得。例如，在encoding/json/v2 设计（仍在进行中）中，虽然默认语义和 API 已更改，但该包提供了配置旋钮，使它能够实现 v1 API。当我们最终发布encoding/json/v2时，encoding/json（v1）将成为它的薄包装器，确保没有从 v1 迁移的用户仍然可以从 v2 中的优化和安全修复中受益。

一篇后续博文更详细地介绍了ChaCha8 生成器。