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.8 纳秒），但维护着近 5 千字节的内部状态。相比之下，Melissa O’Neill 的PCG 生成器家族以约 2.1 纳秒每数的速度生成更好的随机数，并且内部状态只有 16 字节。我们还想探索使用 Daniel J. Bernstein 的ChaCha 流密码作为生成器。一篇后续博文专门讨论该生成器。

Source 接口

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 函数，用当前时间来播种全局生成器，“只是为了确保”。

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

回想起来，在这里遵循 C 标准库显然是一个错误：自动播种全局生成器将消除谁来播种的困惑，并且用户在不希望重复输出时不会再感到惊讶。

可伸缩性

全局生成器的可伸缩性也不好。由于像rand.Intn这样的顶层函数可以同时从多个 goroutines 调用，因此实现需要一个锁来保护共享的生成器状态。在并行使用中，获取和释放这个锁比实际生成要昂贵。更好的做法是拥有一个每线程的生成器状态，但这会破坏在没有并发使用 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.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 的程序中提高全局生成器的可伸缩性，用 Go 运行时内部已经使用的非常廉价的每线程wyrand 生成器替换了 Go 1 生成器。这移除了全局互斥锁，使顶层函数的伸缩性大大提高。调用 rand.Seed 的程序则回退到受互斥锁保护的 Go 1 生成器。

• 我们能够在 Go 运行时中采用 Lemire 的优化，并且还在 rand.Shuffle 中使用了它，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 接口，将 Int63 方法替换为 Uint64 方法，并删除了 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 生成器。