这篇文章是关于 Go 语言标准库中math/rand
包的改进和math/rand/v2
包的引入。原文地址:https://go.dev/blog/randv2
随着math/rand/v2
的发展,Go标准库的演进
Russ Cox 2024年5月1日
自2012年3月Go 1发布[1]以来,对标准库的变更一直受到 Go 兼容性承诺[2]的限制。总体而言,兼容性一直是 Go 用户的福音,为生产系统、文档、教程、书籍等提供了稳定的基础。然而,随着时间的推移,我们意识到原始 API 中的错误无法通过兼容的方式修复;在其他情况下,最佳实践和惯例已经发生了变化。我们需要一个计划来执行重要的、破坏性变更。
这篇博客文章是关于Go 1.22的新 math/rand/v2[3]包,这是标准库中的第一个“v2”包。它带来了对 math/rand API[4]所需的改进,但更重要的是,它为其他标准库包的修订提供了一个示例。
(在Go中,math/rand
和math/rand/v2
是两个具有不同导入路径的不同包。Go 1及之后的每个版本都包含了math/rand
;Go 1.22增加了math/rand/v2
。Go程序可以导入任一包,或者两者都导入。)
本文讨论了math/rand/v2
中变更的具体理由,然后反思了将指导其他包新版本的一般原则[5]。
伪随机数生成器
在我们查看math/rand
(一个伪随机数生成器的API)之前,让我们花一点时间来理解这意味着什么。
伪随机数生成器是一个确定性程序,它从一个小的种子输入生成一个看似随机的长数列,尽管这些数字实际上并不是随机的。在math/rand
的情况下,种子是一个单一的int64
,算法使用线性反馈移位寄存器(LFSR)[6]的变体,从这个种子生成一系列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流密码作为生成器。后续的文章将专门讨论该生成器。
源接口
rand.Source
接口是错误的。该接口定义了一个低级随机数生成器的概念,它生成非负的int64
值:
// 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
种子:一些生成器是由更大的值进行种子初始化的,而接口没有提供处理这种情况的方法。
Seeding Responsibility
Seed
更大的问题是播种全局生成器的责任不明确。大多数用户不直接使用Source
和Rand
。相反,math/rand
包提供了一个通过顶层函数如Intn
访问的全局生成器。按照C标准库的做法,全局生成器默认行为是在启动时调用Seed(1)
。这对于可重复性是好的,但对于希望每次运行随机输出不同的程序来说是不好的。包文档建议在这种情况下使用rand.Seed(time.Now().UnixNano())
,以使生成器的输出依赖于时间,但应该由什么代码来做这件事呢?
可能主包应该负责如何播种math/rand
:让导入的库自己配置全局状态将是不幸的,因为他们的选择可能与其他库或主包冲突。但如果一个库需要一些随机数据并想使用math/rand
怎么办?如果主包甚至不知道正在使用math/rand
怎么办?我们发现在实践中,许多库添加了初始化函数,用当前时间来播种全局生成器,“只是为了确定”。
库包自己播种全局生成器会导致一个新问题。假设主包导入了两个都使用math/rand
的包:包A假设全局生成器将由主包播种,但包B在init func中播种了它。假设主包本身没有播种生成器。现在包A的正确操作取决于包B也被导入到程序中的巧合。如果主包停止导入包B,包A将停止获取随机值。我们在大型代码库中实际观察到了这种情况。
回想起来,显然,跟随C标准库在这里是一个错误:自动播种全局生成器将消除关于谁播种它的混乱,用户也不会因为不希望重复输出时而对重复输出感到惊讶。
可扩展性
全局生成器的可扩展性也不好。因为像rand.Intn
这样的顶层函数可以同时从多个goroutine调用,实现需要一个锁来保护共享的生成器状态。在并行使用中,获取和释放这个锁比实际生成更昂贵。相反,有一个每个线程的生成器状态会更有意义,但这样做会破坏没有并发使用math/rand
的程序的可重复性。
Rand
实现缺少重要的优化
rand.Rand类型[7]包装了一个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发现了一个几乎可以避免除法的算法[8](也参见他在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函数[9]。这在当时看起来是合理的,但回顾起来,我们没有足够关注这一变化的软件工程方面。现在如果你想读取随机数据,现在你有两个选择: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
以提供对核心源功能的直接访问,而且似乎不一致的是不加其他。
采纳了提案讨论中的另一个建议,我们添加了一个新的顶层通用函数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 中的bug修复和性能优化中受益。当然,鉴于 v2 正在引入破坏性更改,这并不总是可能的,但总是值得仔细考虑的。对于math/rand/v2
,我们安排了自动播种的v1函数调用v2生成器,但由于可重复性违规,我们无法共享其他代码。最终math/rand
没有太多代码,也不需要定期维护,所以重复是可管理的。在其他情况下,避免重复可能值得更多的工作。例如,在仍在进行中的encoding/json/v2
设计中,尽管默认语义和API已更改,但包提供了配置旋钮,使其能够实现v1 API。当我们最终发布encoding/json/v2
时,encoding/json
(v1)将成为它的薄包装,确保不从v1迁移的用户仍然能从v2的优化和安全修复中受益。
go1: https://go.dev/blog/go1
[2]go1compat: https://go.dev/doc/go1compat
[3]rand v2: https://go.dev/pkg/math/rand/v2/
[4]rand API: https://go.dev/pkg/math/rand/
[5]randv2 principles: https://go.dev/blog/randv2#principles
[6]LFSR: https://en.wikipedia.org/wiki/Linear-feedback_shift_register
[7]rand.Rand: https://go.dev/pkg/math/rand/#Rand
[8]Daniel algo: https://arxiv.org/abs/1805.10941
[9]read function: https://go.dev/pkg/math/rand/#Read