Yoshi Yamaguchi

math/rand/v2によるGo標準ライブラリの進化

Evolving the Go Standard Library with math/rand/v2 by Russ Cox

2012年3月にリリースされた Go 1以来、標準ライブラリへの変更はGoの互換性の約束によって制約されてきました。全体として見れば、互換性はGoユーザーにとって恩恵であり、本番システムやドキュメント、チュートリアル、書籍などに安定した基盤を提供してきました。しかし時間が経つにつれて、私たちは元のAPIに互換性を保ったままでは直せない誤りがあったことに気づきましたし、他のケースではベストプラクティスや慣習が変化してきました。互換性を破るような重要な変更を行うための計画も必要なのです。

この記事では、標準ライブラリで最初の「v2」となる、Go 1.22の新しいmath/rand/v2パッケージについて説明します。このパッケージはmath/rand APIに必要な改善をもたらしますが、それ以上に重要なのは、必要に応じて他の標準ライブラリパッケージをどのように改訂していくかの実例を示している点です。

(Goでは、math/randとmath/rand/v2はそれぞれ異なるインポートパスを持つ別々のパッケージです。Go 1およびそれ以降のすべてのリリースにはmath/randが含まれており、Go 1.22でmath/rand/v2が追加されました。Goのプログラムはどちらのパッケージをインポートしても構いませんし、両方インポートしても構いません。)

この記事ではmath/rand/v2での変更に関する具体的な根拠を議論し、そのあとで他のパッケージの新バージョンを導く一般的な原則について振り返ります。

疑似乱数生成器

疑似乱数生成器のためのAPIであるmath/randを見る前に、少し立ち止まってその意味を理解しておきましょう。

疑似乱数生成器とは、小さなシード入力から一見ランダムに見える数値の長い列を生成する決定的なプログラムのことです。とはいえ、その数値は実際にはまったくランダムではありません。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で書かれており、ガベージコレクタは保守的でシングルスレッドのstop-the-world方式のものであり、ライブラリ群も全体として基本的な実装にとどまっていました。Go 1からGo 1.5あたりにかけて、私たちはこれらそれぞれについて後戻りし、「本描き」の版を描き上げました。コンパイラとランタイムをGoに置き換え、マイクロ秒単位の一時停止時間で動く、精密で並列・並行なガベージコレクションを新たに書き上げ、標準ライブラリの実装も必要に応じてより洗練された最適化アルゴリズムに置き換えました。

残念ながら、math/randにおける再現可能性の要件のせいで、互換性を破らずにジェネレータを置き換えることはできませんでした。私たちはGo 1ジェネレータに縛られたままでした。これはそれなりに高速です(私のM3 Macでは1つの数値あたり約1.8ns)が、内部状態としてほぼ5キロバイトを保持します。対照的に、Melissa O’NeillによるPCGファミリーのジェネレータは、わずか16バイトの内部状態で、1つの数値あたり約2.1nsという、より良質な乱数を生成します。私たちはまた、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
%

(このdocコメントにおいて、「[0, N)」は半開区間を表し、範囲は0を含み2⁶³の直前で終わることを意味します。)

rand.Rand型はSourceをラップして、0からNの間の整数の生成や浮動小数点数の生成など、より豊富な操作群を実装します。

Sourceインターフェースをuint64ではなく63ビットに短縮した値を返すよう定義したのは、それがGo 1ジェネレータや他の広く使われているジェネレータが生成する値であり、C標準ライブラリが定めた慣習とも合致していたからです。しかしこれは誤りでした。より現代的なジェネレータはフル幅のuint64を生成するため、そちらの方がより使い勝手の良いインターフェースなのです。

もう一つの問題は、Seedメソッドがint64のシードをハードコードしていることです。ジェネレータの中にはより大きな値でシードされるものもありますが、このインターフェースにはそれを扱う方法が用意されていませんでした。

シードの責任

Seedに関するさらに大きな問題は、グローバルジェネレータをシードする責任がどこにあるのか曖昧だったことです。ほとんどのユーザーはSourceやRandを直接使いません。代わりに、math/randパッケージはIntnのようなトップレベルの関数からアクセスできるグローバルジェネレータを提供しています。C標準ライブラリに倣って、グローバルジェネレータは起動時にSeed(1)が呼ばれたのと同じように振る舞うのがデフォルトです。これは再現可能性という点では望ましいのですが、実行のたびに異なる乱数出力を求めるプログラムにとっては都合が悪いものです。パッケージのドキュメントでは、そのような場合にジェネレータの出力を時刻に依存させるためにrand.Seed(time.Now().UnixNano())を使うことを勧めていますが、では、どのコードがこれを行うべきなのでしょうか。

おそらくmath/randがどうシードされるかについてはmainパッケージが責任を持つべきでしょう。インポートされるライブラリが自らグローバルな状態を設定してしまうのは望ましくありません。その選択が他のライブラリやmainパッケージと衝突しかねないからです。しかし、あるライブラリがランダムなデータを必要とし、math/randを使いたい場合はどうなるでしょうか。mainパッケージがmath/randが使われていることすら知らない場合はどうでしょうか。実際のところ、多くのライブラリが「念のため」現在時刻でグローバルジェネレータをシードするinit関数を追加していることがわかりました。

ライブラリパッケージが自らグローバルジェネレータをシードすることは新たな問題を引き起こします。mainパッケージが、どちらもmath/randを使う2つのパッケージをインポートしているとしましょう。パッケージAはグローバルジェネレータがmainパッケージによってシードされると想定していますが、パッケージBは自身のinit関数の中でシードします。そしてmainパッケージ自体はジェネレータをシードしないとします。すると、パッケージAが正しく動作するかどうかは、パッケージBもたまたま同じプログラムにインポートされているという偶然に依存することになります。もしmainパッケージがパッケージBのインポートをやめたら、パッケージAはランダムな値を得られなくなってしまいます。私たちは実際に大規模なコードベースでこれが起きているのを観測しました。

振り返ってみると、ここでC標準ライブラリに倣ったのは明らかに誤りでした。グローバルジェネレータを自動的にシードしておけば、誰がシードするのかという混乱はなくなりますし、ユーザーは望んでもいないのに再現可能な出力に驚かされることもなくなります。

スケーラビリティ

グローバルジェネレータはスケーラビリティにも問題を抱えていました。rand.Intnのようなトップレベルの関数は複数のゴルーチンから同時に呼び出される可能性があるため、実装は共有されたジェネレータの状態を保護するロックを必要としていました。並列に使用する場合、このロックの取得と解放にかかるコストは実際の乱数生成そのものよりも高くつきました。代わりにスレッドごとのジェネレータの状態を持たせるのが理にかなっていますが、そうするとmath/randを並行に使わないプログラムでは再現可能性が失われてしまいます。

Rand実装に欠けていた最適化

rand.Rand型はSourceをラップしてより豊富な操作群を実装します。たとえば、[0, n)の範囲のランダムな整数を返すInt63nのGo 1における実装は次のようになっています。

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+1が2⁶³以下でnの最大の倍数になるようにmaxを計算し、そのループはmax+1以上のランダムな値を棄却します。この大きすぎる値を棄却することで、n個すべての出力が等確率であることが保証されます。nが小さい場合、そもそも値を棄却する必要が生じることはまれですが、nが大きくなるにつれて棄却はより頻繁に、そしてより重要になります。棄却ループがなかったとしても、2回の(遅い)剰余演算によって、この変換はそもそもランダムな値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という2つの選択肢があります。データが鍵素材として使われるのであればcrypto/randを使うことが非常に重要ですが、今では代わりにmath/randを使うこともでき、その結果として悲惨な事態を招きかねません。

goimportsやgoplsのようなツールには、math/randではなくcrypto/randのrand.Readを優先して使うようにする特別な処理が組み込まれていますが、それは完全な解決策ではありません。Readを完全に削除する方が望ましいのです。

math/randを直接修正する

新しい、互換性のないメジャーバージョンのパッケージを作ることは、私たちにとって決して第一の選択肢ではありません。新バージョンは、それに切り替えたプログラムにしか恩恵をもたらさず、旧メジャーバージョンの既存の利用はすべて置き去りにされてしまいます。対照的に、既存のパッケージの問題を修正すれば、既存の利用すべてに恩恵が及ぶため、はるかに大きなインパクトがあります。v1をできる限り修正することなしにv2を作るべきではありません。math/randの場合、上記で説明した問題のいくつかには部分的に対処できました。

  • Go 1.8では、Uint64メソッドを持つオプションのSource64インターフェースを導入しました。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 1ジェネレータを、Goランタイム内部ですでに使われている非常に軽量なスレッドごとのwyrandジェネレータに置き換えることで、グローバルジェネレータのスケーラビリティも改善できました。これによりグローバルなミューテックスが取り除かれ、トップレベルの関数のスケーラビリティは大きく向上しました。rand.Seedを呼び出すプログラムは、ミューテックスで保護されたGo 1ジェネレータにフォールバックします。

  • 私たちはGoランタイムの中でLemireの最適化を採用でき、Lemireの論文が発表された後に実装されたrand.Shuffleの内部でもそれを使いました。

  • rand.Readを完全に削除することはできませんでしたが、Go 1.20ではこれを非推奨とし、crypto/randを使うよう促しました。その後、エディタが非推奨関数の使用にフラグを立てたことで、暗号用途の文脈で誤ってmath/rand.Readを使っていたことに気づいた、という声を聞くようになりました。

これらの修正は完璧でも完全でもありませんが、既存のmath/randパッケージのすべてのユーザーに恩恵をもたらす、本物の改善です。より完全な修正のためには、math/rand/v2に目を向ける必要がありました。

math/rand/v2で残りを修正する

math/rand/v2の定義には入念な計画が必要でした。その後、GitHub Discussion、そしてプロポーザルの議論を経ています。このパッケージはmath/randと同じものですが、上で述べた問題に対処するために、以下のような互換性を破る変更が加えられています。

  • Go 1ジェネレータを完全に取り除き、PCGとChaCha8という2つの新しいジェネレータに置き換えました。新しい型は(汎用的な名前であるNewSourceを避けて)そのアルゴリズムにちなんで命名されており、将来重要な別のアルゴリズムを追加する必要が生じた場合にも、この命名方式にうまく収まるようになっています。

    プロポーザルの議論での提案を採用し、新しい型はencoding.BinaryMarshalerとencoding.BinaryUnmarshalerインターフェースを実装しています。

  • Sourceインターフェースを変更し、Int63メソッドをUint64メソッドに置き換え、Seedメソッドを削除しました。シードをサポートする実装は、PCG.SeedやChaCha8.Seedのように、それぞれ独自の具象メソッドを提供できます。この2つは異なるシード型を取り、どちらも単一のint64ではないことに注意してください。

  • トップレベルのSeed関数を削除しました。Intのようなグローバル関数は、今では自動シードされた形式でしか使えません。

  • トップレベルのSeedを削除したことで、トップレベルのメソッドがスケーラブルなスレッドごとのジェネレータを使うようハードコードできるようになり、利用のたびにGODEBUGを確認する必要もなくなりました。

  • Intnおよび関連する関数にLemireの最適化を実装しました。具象型であるrand.RandのAPIはこの値のストリームに固定されたため、今後発見されるかもしれない最適化を活用することはできなくなりますが、少なくとも今のところは最新の状態に追いつけました。また、Go 1.2の頃から使いたいと考えていたFloat32とFloat64の最適化も実装しました。

  • プロポーザルの議論の中で、あるコントリビューターがExpFloat64とNormFloat64の実装に検出可能な偏りがあることを指摘しました。私たちはその偏りを修正し、新しい値のストリームを固定しました。

  • PermとShuffleは異なるシャッフルアルゴリズムを使っており、異なる値のストリームを生成していました。これはShuffleがあとから実装され、より高速なアルゴリズムを使っていたためです。Permを完全に削除してしまうと、ユーザーにとって移行が難しくなってしまいます。そこで私たちはPermをShuffleを使って実装し直しました。これにより、実装を1つ削除することはできました。

  • Int31、Int63、Intn、Int31n、Int63nを、それぞれInt32、Int64、IntN、Int32N、Int64Nに改名しました。名前に含まれる31や63は無用に細かく紛らわしいものでしたし、名前の2番目の「単語」を大文字のNにする方がGoらしい書き方です。

  • Uint、Uint32、Uint64、UintN、Uint32N、Uint64Nというトップレベルの関数とメソッドを追加しました。中核となるSourceの機能に直接アクセスできるようにするためにUint64を追加する必要があり、それ以外を追加しないのは一貫性を欠くように思われたためです。

  • プロポーザルの議論からのもう一つの提案を採用し、Int64NやUint64Nに似ているものの任意の整数型に対して使える、新しいトップレベルのジェネリック関数Nを追加しました。旧APIでは、最大5秒のランダムなDurationを作るには次のように書く必要がありました。

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

    Nを使うと、同等のコードは次のようになります。

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

    Nはトップレベルの関数としてのみ存在します。Goにはジェネリックなメソッドが存在しないため、rand.RandにNメソッドはありません。(ジェネリックなメソッドは将来的にも実現しそうにありません。インターフェースとひどく相性が悪く、完全な実装には実行時のコード生成か、遅い実行のどちらかが必要になってしまうからです。)

  • 暗号用途でのmath/randの誤用を緩和するために、グローバル関数で使われるデフォルトのジェネレータをChaCha8にし、Goランタイムでも(wyrandを置き換えて)これを使うように変更しました。暗号学的な秘密情報の生成には引き続きcrypto/randを使うことが強く推奨されますが、誤ってmath/rand/v2を使ってしまっても、math/randを使ってしまう場合ほど破滅的な事態にはなりません。math/randにおいても、明示的にシードされていない場合、グローバル関数は今ではChaCha8ジェネレータを使うようになっています。

Go標準ライブラリを進化させるための原則

この記事の冒頭で触れたとおり、この作業の目標の一つは、標準ライブラリのあらゆるv2パッケージにどう取り組むかについての原則とパターンを確立することでした。今後数回のGoリリースでv2パッケージが大量に出てくることはありません。その代わりに、私たちは一度に1つのパッケージずつ取り組み、これから10年は通用する品質基準を確実に設定していきます。多くのパッケージはそもそもv2を必要としないでしょう。しかし必要になるパッケージについては、私たちのアプローチは3つの原則に集約されます。

第一に、パッケージの新しい、互換性のないバージョンは、標準ライブラリの外にあるv2モジュールと同様に、セマンティックインポートバージョニングにならってthat/package/v2という形式のインポートパスを使います。これにより、元のパッケージとv2パッケージを1つのプログラムの中で共存させられるようになり、これは新しい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ジェネレータについてより詳しく紹介します。

By Russ Cox