Go标准库`math/rand/v2`

• 伪随机数发生器
• math/rand的问题
  • 生成算法
  • Source 接口
  • 种子的职责
  • 可扩展性
  • Rand实现缺少重要的优化措施
  • 读取错误
• 直接修复math/rand
• 剩余的在math/rand/v2中修复
• 发展Go标准库的原则

原文在这里。

由 Russ Cox发布于2024年5月1日

自2012年3月Go 1发布以来，标准库的更改一直受到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序列。该算法基于乔治·马萨格里亚的想法，经过唐·米切尔和吉姆·里德斯的调整，并由肯·汤普森为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的初始实现虽然已经准备好投入生产，但在许多方面是整个系统的”panic sketch”，足以作为未来开发的基础：编译器和运行时用C语言编写；垃圾收集器是一个保守的、单线程的、STW(stop-the-workd)的收集器；这些库使用了基本的实现。从Go 1到大约Go 1.5，我们回过头来绘制了每一个的”fully inked”版本：我们将编译器和运行时转换为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^{63}$次方之前结束。）

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

我们定义了Source接口，返回一个截断的63位值而不是一个uint64，因为这是Go 1生成器和其他广泛使用的生成器所产生的，并且符合C标准库所设定的约定。但这是一个错误：更现代的生成器产生完整宽度的uint64s，这是一个更方便的接口。

另一个问题是Seed方法硬编码了一个int64种子：一些生成器使用更大的值进行种子化，而接口没有提供处理这种情况的方法。

种子的职责

Seed 的一个更大问题是，对全局生成器进行种子化的责任并不明确。大多数用户不会直接使用Source和Rand，而是通过像Intn这样的顶层函数来访问math/rand包提供的全局生成器。按照 C 标准库的做法，全局生成器默认表现得像是在启动时调用了Seed(1)。这对于可重复性是好的，但对于希望每次运行都得到不同随机输出的程序来说却不是。在这种情况下，包文档建议使用rand.Seed(time.Now().UnixNano())，使生成器的输出依赖于当前时间，但是应该由哪段代码来做这个操作呢？

主包可能应该负责如何对math/rand进行种子化：如果导入的库自己配置全局状态，这可能会与其他库或主包的选择发生冲突，这是不太理想的。但是，如果一个库需要一些随机数据并想要使用math/rand怎么办？如果主包甚至不知道math/rand正在被使用怎么办？我们发现，在实践中，许多库添加了初始化函数，用当前时间来种子全局生成器，“以防万一”。

库包自己种子化全局生成器导致了一个新问题。假设main包导入了两个都使用math/rand的包：包 A 假设全局生成器将由 main 包进行种子化，但包 B 在初始化函数中进行种子化。如果 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^{63}$ 是 n 的倍数，否则没有算法能够将 $2^{63}$ 个可能性等概率地转换为 n 个等概率的值：在其它情况下，某些输出必然会比其他输出更频繁（作为一个更简单的例子，尝试将4个等可能的值转换为3个。）。代码计算出最大值 max，使得 max+1 是小于或等于 $2^{63}$ 的最大 n 的倍数，然后循环会拒绝大于或等于 max+1 的随机值。拒绝这些过大的值确保所有 n 个输出都是等可能的。对于小的 n，需要拒绝任何值本身是罕见的；随着 n 的增大，拒绝变得更加常见并且更加重要。即使没有拒绝循环，两个（慢）取模操作也可能使转换的成本比首先生成随机值 v 更高。

在 2018 年，Daniel Lemire 发现了一个几乎总是避免除法的算法（也请参阅他 2019 年的博客文章）。在math/rand中，采用 Lemire 的算法将使Intn(1000)的速度提高 20-30%，但我们不能这么做：更快的算法生成的值与标准转换不同，破坏了重复性。

其他方法也受到重复性的约束，无法达到它们可能的最佳速度。例如，如果我们能改变生成的值流，Float64方法很容易加快大约 10%。（这是我们在 Go 1.2 中尝试并回滚的更改，前面提到过。）

读取错误

如前所述，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

制作一个新的、不兼容的主要版本的包绝不是我们的首选：这个新版本只对切换到它的程序有益，而所有现有的旧主要版本的使用都被遗留在了后面。相反，在现有包中修复一个问题会有更大的影响，因为它修复了所有现有的使用情况。在 v2 的情况下，我们永远不应该在没有尽可能修复 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函数中使用了它，这个函数是在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检查。
• 我们实现了 Lemire 优化的Intn和相关函数。现在具体的rand.RandAPI 锁定在了该值流中，因此我们无法利用尚未发现的任何优化，但至少我们再次与时俱进。我们还实现了我们在 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。但是，对于那些需要的包，我们的方法归结为三个原则。

首先，包的新版本，如果与现有版本不兼容，将使用该/包/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生成器。

声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。

Author: mengbin

blog: mengbin

Github: mengbin92

cnblogs: 恋水无意

腾讯云开发者社区：孟斯特