2日前、Mike MaloneがMediumに、V8におけるMath.random()の実装と、そこで使われているPRNGの品質がいかに低いかについて、興味深い記事を公開しました。http://bit.ly/1SPDraN

この記事は今日、Hacker Newsでトップニュースの一つになっていました。Math.random()がどのように壊れていて、どう修正すべきかという点では、非常に明快で有益な内容です。その問題自体について付け加えることはありません。ただ、著者がPRNGの弱点を、大規模でおそらく衝突しないIDの生成という文脈で発見していたので、私が過去に何度も使ってきた、別の方法を紹介したいと思います。高速で、極めて信頼性の高い方法です。

一意なIDの問題

理論上、一意なIDを生成したいなら、同じIDが二度と生成されないことを保証するために、何らかの状態を保存する必要があります。単純なケースなら、ただのカウンターを使えばよいでしょう。しかし、直前に生成したIDは、一貫性のある方法で保存しなければなりません。システムを再起動したとき、保存していたカウンターがディスクに正しく永続化されていなかったために、同じIDが再び生成されるようなことは決して起きてはいけません。

複数のプロセスで一意なIDを生成したい場合は、各プロセスが、自分のIDに、ほかのプロセスのプレフィックスと衝突しないプロセス固有のプレフィックスを付ける必要があります。これを管理するのも複雑になり得ます。古いIDを信頼できる方法で保存しなければならないというだけで、1秒あたりに大量のIDを生成したい場合には、とても多くの時間がかかります。

幸い、簡単な解決策があります。0からNまでの範囲で乱数を生成するのです。Nを十分に大きくすれば、衝突する確率は、実用上どのような用途でも無視できるほど小さくなります。生成する数が0からNまで一様に分布していれば、この方法は機能します。この前提が成り立つなら、誕生日のパラドックスを使って衝突の確率を計算できます。

十分なビット数を使えば、1秒あたり数百万個のIDを、何百年にもわたって生成し続けたとしても、衝突する確率を小惑星が地球に衝突する確率より何十億倍も低くすることは簡単です。それでも余裕が足りないというなら、ビットをさらに追加すればよいでしょう。IDの取り得る範囲を、宇宙に存在する原子の数より大きくすることさえ簡単にできます。

この生成方法には大きな利点があります。完全にステートレスなのです。複数のノードがメッセージをやり取りせず、同時にIDを生成できます。さらに、ディスクに保存するものが何もないため、CPUの性能を最大限に活かして動かせます。計算は簡単にCPUキャッシュに収まります。そのため、非常に高速で便利です。

Mike Maloneはこの考え方を使い、PRNGによって、64種類の文字のいずれかで構成されたIDを作っていました。各文字を生成する際に、弱いV8のPRNGを使っていたため、衝突が発生していました。ここで、最初の前提を思い出してください。新しいIDはそれぞれ、0からNまでの範囲から一様に選ばれなければなりません。

この問題は、より強力なPRNGを使えば解決できますが、そのためにはPRNGの分析が必要です。もう一つの問題はシードです。再起動後に、PRNGの初期状態を再び選んでしまわないようにするには、プロセスをどのように再開すればよいのでしょうか。そうしなければ、実際のID空間を制限するのは出力空間そのものではなく、PRNGのシードになってしまいます。

以上の理由から、こうした問題の大半を避けられる、ごく単純な手法を紹介したいと思います。

暗号学的ハッシュ関数を使って一意なIDを生成する

暗号学的ハッシュ関数は、ビット列を固定長のビット列に変換する、逆算できない関数です。さまざまな攻撃に耐えられるよう設計されていますが、この用途では、その性質の一つである出力の一様性だけを利用します。ハッシュ関数への入力の1ビットを変えると、出力の各ビットは50%の確率で変化します。

信頼できるシードを得るために、OSの力を借りて、/dev/urandomを読み出します。ジェネレーターにシードを設定する段階では、外部からのエントロピーが本当に必要です。そうしなければ、同じ系列を再び生成するという大きな間違いを犯す危険があります。

暗号学的ハッシュ関数の例として、よく知られているSHA1を使います。出力は160ビットです。なお、この用途ならMD5のハッシュ値を使うこともできます。MD5の脆弱性は、ここでの使い方には影響しません。

まず、/dev/urandomから160ビットを読み出してシードを作ります。擬似コードでは次のようになります。

seed = devurandom.read(160/8)

カウンターも初期化します。

counter = 0

これが、新しいIDを生成する関数です。

function get_new_id()
    myid = SHA1(string(counter) + seed)
    counter = counter + 1
    return myid
end

基本的には、固定された文字列であるシードに、増加していくカウンターを連結してハッシュ化します。たとえばシードが「foo」なら、次のようなIDが生成されます。

SHA1(“0foo”)
SHA1(“1foo”)
SHA1(“2foo”)

これで今回の用途には十分です。ただし、IDを簡単に予測できないようにしたい場合もあるでしょう。IDを非常に予測しにくくするには、get_new_id()関数でSHA1を使う代わりに、SHA1_HMAC()を使います。この場合、シードが秘密鍵で、カウンターがHMACのメッセージになります。

この方法は高速で、分布の良さが保証されているため、衝突の起こりにくさは誕生日のパラドックスから予測されるものになります。PRNGの分析も必要なく、完全にステートレスです。

私は、分散システム内の複数のノード間でメッセージIDを生成するために、自分のDisqueプロジェクトでこの方法を使っています。

Hacker Newsのスレッドはこちらです。https://news.ycombinator.com/item?id=10606910