衝突しないランダムな12桁のIDを払い出す方法

このたび誠に遺憾ながら次の要件を満たすIDの生成を命じられました。

• 12桁の整数値 000,000,000,000 ～ 999,999,999,999 の中からランダムなIDを払い出すこと
• すでに払い出したIDと同じIDを払い出さないこと
• 払い出しが高速であること
• ランダムに払い出すこと

連携システムや現実的な都合上、なんとかこれを実現しなければなりません。

🙄「そんな理想的なものあるかよ」

と思いつつプログラマである私はいろいろ考えるのでした。

連番で割り当てる

今回はランダムに払い出すことが要件なので利用できませんが、それを許す環境であれば真っ先に検討したい方法です。0から始めて最後の999,999,999,999まで IDの最大値 + 1 を順番に割り当てていくだけの単純な方法で、実装の簡潔さと管理のしやすさがあります。データベースを使う際もAUTOINCREMENT機能による後押しがあります。

一方でこの方法で払い出したIDがシステム側でのみ利用されていれば問題はありませんが、ユーザーがなんらかの方法でIDを確認できる状況にあるときは連番で割り当てていることがバレると不都合なこともあります。

• 利点: 高速・単純・衝突しない・列挙が簡単
• 欠点: セキュリティ的に不安

以前使っていたとあるサービスでは会員IDが連番で払い出されていたためにユーザー総数の検討をつけることができましたし、会員IDがログインIDにもなっていたため、ログインすることができる有効なユーザーIDの一覧を簡単に推測できてしまいました。

🙄「きっと賢いひとが作ったんやろなあ」

ランダムな値を生成して衝突したらやり直す

乱数を使って払い出すIDを決定する方法です。払い出したIDが少ないうちは高速かつ良好に動作しますが、払い出す数が増えるにつれ徐々に衝突確率も増えていきます。そこまでたくさんのオブジェクトにIDを割り振ることは通常ありえませんが、もし仮に95%のIDを払い出しているとしたら、次のIDの払い出しに成功する確率は約60回の試行を経てやっと95%という計算になります。99%のIDを払い出していれば約300回の試行で95%です。

最近のコンピュータは非常に高速なのでこのくらいの試行回数なら簡単に突破するでしょう。しかし最悪計算時間は $\Omega(\infty)$ です。

このコストをどのように見るかは時と場合に寄りますが、新しいIDを払い出すために処理がブロックすることは好ましくないとわかります。しかもブロック時間は乱数に依存するので不定です。最終的にはまともにIDを払い出せなくなるので、この問題を解消する方策をなにか考えなければなりません。

🙄「でも1億のIDを払い出したとしてもまだ全体の0.01%なので問題ないのでは？(ガバ)」

また、IDの払い出しに即時性が求められるのであれば、あらかじめ生成しておけばいいという小手先の方法を思い立つはずです。これも途中までは良好に動作すると思われますが、結果的にやっていることは変わらないので、ゆくゆくは衝突による性能低下の対策が必要になります。

• 利点: 人間の感覚でランダムっぽいIDを生成できる
• 欠点: リトライが発生することがある

某有名サービスはこの方法でブン回してIDの払い出しをしたと噂で聞いたことがあります。

シャッフルした値を生成する

ランダムな値を生成すると衝突するので、12桁のすべてのIDをシャッフルして順番に取り出せばランダムに取り出せば衝突せずIDの払い出しができるはずです。それではやってみましょう！

import random

a = list(range(1000000000000))
random.shuffle(a)
print(a[:10])    # 試しに最初の10個でも取得してみるか

🙄「死ーん」

結果がでませんね？12桁というのはIDとして扱うには不安ですが、列挙するには大きすぎるというふたつの問題を抱えています。UUIDのようにデカすぎれば衝突しないことを前提に楽観的な方法もとれるのですが、今回はそういうわけにはいきません。

12桁の数値は通常64bit整数型で管理することになるので、すべてを列挙するとなると単純計算で7.5TBのデータ量になります。当然メモリには乗り切らないので、ディスクに一度書き出してからランダムに並べ替えることも考えられますが、IDの払い出しという作業だけにこんな資源の無駄遣いはしたくありません。

• 利点: データ量に目を瞑れば理想的
• 欠点: 解決策として愚かすぎる

誰かうまくいくか試してみてください。

シャッフルした値を生成するジェネレータを使う

これまでの議論で先行評価が実行時間・メモリ空間の面で不利に働くことは明確です。それなら遅延評価を利用すべきなのです。今我々に必要とされているのはシャッフルした値を生成するジェネレータであり、ジェネレータの評価ごとに値をひとつずつ返してくれればやりたいことは賢く実現できます。乱数を固定するためにシード値を決めておけば再現性もあるはずです。

🙄「シャッフルされた…値？」

そんな便利なものがあれば使いたいものです。結局シャッフルするためにはすべての値が列挙されてなければならず、7.5TBという非現実的なデータ量と向き合うことになります。

• 利点: 実現できればわりといい手法
• 欠点: 実現できない

先行評価が理由で遅延評価が必要だが、遅延評価のために先行評価が必要。
これすなわち 🐓 AND 🥚

提案手法: シーケンスIDを分割し乱数テーブルで置換する

ここまでいろいろと足りない頭で考えてきて、根本的にやり方を変える必要があると感じてきました。

まずは問題の大きさです。12桁という数値を甘く見積もっていました。この数値の絶妙な大きさが私を苦しめているのです。分割統治法にならい、大きな問題を小さな問題に分割してそれをまとめあげて解決することができないか考えてみたいと思います。12桁が大きいなら4桁ずつ分割して AAAA, BBBB, CCCC の3セグメントにすれば、それぞれのセグメントでは 0～9,999 といった小さな値を考えればいいことになります。249,873,205,369 の場合 AAAA = 2498, BBBB = 7320, CCCC = 5369 です。

次に要件で妥協できるところを探り当てます。現実的には要件をすべて完全に満たす必要がないことが多いです。さすがにIDが重複してしまうのはマズいので、今回はランダム性に目をつぶってもらいました。システム設計者にとってはなんちゃってランダムIDであってもユーザーにとってある程度ランダムっぽく見えればいいというケースは結構ありえます。そこで各セグメント内でランダムになるように0～9,999の値に対してあらかじめ計算された乱数テーブルを用意します。今回は AAAA, BBBB, CCCC の3セグメント用のカラムを用意します。

 segment | seg_a | seg_b | seg_c |
---------+-------+-------+-------+
    0000 |  6276 |  6232 |  9304 |
    0001 |   899 |  3153 |   203 |
    0002 |  1039 |  7562 |  6055 |
      :       :       :       :
    9999 |  5961 |  9925 |  6575 |
---------+-------+-------+-------+

seg_a, seg_b, seg_c はそれぞれのカラムの中に 0～9,999 の値がちょうど1回現れるようにシャッフルされています。このテーブルを使って、AAAA-BBBB-CCCC といった値を seg_a(AAAA)-seg_b(BBBB)-seg_c(CCCC) に置換すればおよそランダムっぽい値が得られると思いませんか？

最後に、よりよい手法というのは複数の手法のハイブリッドであることが常です。はじめの方で話したようにIDを払い出す理想的な方法は連番で割り当てることでした。連番ID(seq_id)割り当てと同時に乱数テーブルに照らし合わせて実際に割り当てるID(id)を決定すれば、内部的には連番で扱うことができますし、割り当てられたID(id)がユーザーにバレても、IDからなんらかの推測は立てにくくなります。

     seq_id     |       id       |
----------------+----------------+
 0000 0000 0000 | 6276 6232 9304 |
 0000 0000 0001 | 6276 6232 0203 |
 0000 0000 0002 | 6276 6232 6055 |
    　　  :      |        :　     |
 9999 9999 9999 | 5961 9925 6575 | 
----------------+----------------+

さて、一見良さそうな方法ですが、セグメントに分割したおかげで上位セグメントほど変化に乏しいといった弱点があります。完璧には解決できませんが、簡単な緩和策としてセグメント数を増やした上で例えば DD-BB-FF-CC-EE-AA の順に入れ替えるなどが考えられます。ほかになにかいい発想はありますかね？

• 利点: 高速・単純・衝突しない
• 欠点: 上位セグメントが変化しにくい

🙄「でもな、やることいっぱいで正直こんなことに時間をかけてられへんのや」

最後に

もちろん許すならUUIDのようなほぼ衝突しないものを使うべきですし、私もそうします。ここでは開発環境・連携システム・現実世界との兼ね合いによるいくつかの制約条件がある中で、なるべく理想的な解を探ってきました。もし私と同じ境遇の人がいて、なにかの参考になれば幸いです。

おわり🌱