分散ユニークID生成の設計

要件と規模の見積もり

分散ユニークID生成器（ticket server）の機能要件は単純で、「重複しない64bit整数を、複数のサーバーから同時に、低遅延で払い出す」ことに尽きます。だが非機能要件がこの問題を面接に値するものにします。第一にグローバル一意性（全ノード・全時刻で衝突ゼロ）、第二に単調増加とソート可能性（新しいIDほど数値が大きい＝生成時刻でおおよそ整列する）、第三に高スループットと低遅延（採番のたびに中央DBへ往復しない）、第四に可用性（一部ノードが落ちても採番が止まらない）です。

規模を具体的な桁で見積もります。大規模SNSのタイムライン投稿・いいね・DMなどにIDを振ると仮定し、ピーク書き込みを100,000 QPSと置きます。IDは1件8バイト。ID列そのもののストレージ増加は 100,000 × 8 byte/s = 800 KB/s、1日あたり約69GB、1年で約25TBに達します（本体データではなくID列だけでこの桁）。ここから「採番の速さ」より「IDをインデックスに詰めたときの挙動」が支配的コストだと分かります。ランダムなIDはB木の挿入位置を毎回散らし、ページ分割とキャッシュミスを誘発するからです。ゆえに時刻先頭で単調増加するIDが設計の中心命題になります。

大枠の設計

まずAPIとデータモデルを定めます。採番APIは next_id() -> int64 の一つだけ。中央集権DBを唯一の採番元にする素朴案は、UPDATE counter SET val = val + 1 RETURNING val を全採番で実行するもので、強い単調性は得るものの、そのDBが単一障害点かつスループット上限になります。そこで各ノードが自律的に採番する方式（Twitter Snowflake）を大枠に採用します。ビット配分は次のとおりです。

この配分から採番能力が逆算できます。1ノードは毎ミリ秒4096個、すなわち毎秒約409万個。マシンIDが1024通りなので理論上限は 4096 × 1000 × 1024 ≒ 4.19 × 10^9（毎秒約42億個）で、先の100,000 QPS要件を4桁上回ります。採番ロジックの擬似コードは次のとおりです。

def next_id():
    ts = current_millis()
    if ts < last_ts:              # 時計が逆行した
        wait_until(last_ts)       # 逆行が解消するまで待つ（後述）
        ts = current_millis()
    if ts == last_ts:
        seq = (seq + 1) & 4095    # 12bitマスクで巡回
        if seq == 0:              # 同一msで4096個を使い切った
            ts = wait_next_millis(last_ts)  # 次のミリ秒までスピン
    else:
        seq = 0                   # ミリ秒が進んだので連番リセット
    last_ts = ts
    return ((ts - EPOCH) << 22) | (machine_id << 12) | seq

上位ビットほど時刻という配置が肝心です。IDを数値として比較すると、まず時刻、次にマシンID、最後に連番の順で効くため、生成の前後関係がほぼそのまま数値順序になり、DBのB木では常に右端付近へ追記されます。ページ分割がほぼ起きず、ホットな末尾ページだけがキャッシュに乗るため、書き込みが軽くなります。この局所性の効きは、LSMツリーのように追記を前提とする構造とも相性が良い点で、ストレージ実装の議論（LSMツリー、ライトアヘッドログ）にも接続します。

主要コンポーネントの深掘り

マシンIDの割り当てが最初の要所です。同じマシンIDを2ノードが持てば連番空間が衝突し一意性が崩れます。静的な設定ファイルは単純ですが運用でずれます。実務ではZooKeeperやetcdのような合意ストアに一時ノードを作り、IDを排他的にリースするのが定石です（合意アルゴリズムの中身はPaxosとRaftを参照）。10bitで1024ノードという上限は、コンテナが頻繁に入れ替わる環境では意外に窮屈で、後述のトレードオフの対象になります。

UUIDとの比較も面接で必ず問われます。UUIDは調整なしでローカル生成できる128bit識別子ですが、版によって性質が大きく異なります。

要点は「単調性はビット配置がすべて」という事実です。UUIDv4がインデックスに不向きなのは乱数だからではなく、時刻情報を上位に持たないからです。UUIDv7はまさにこの点を修正し、先頭48bitにミリ秒を置くことでSnowflakeに近い局所性を、マシンID調整なしで得ます。64bitに収める必要がなくグローバルな協調も避けたいならUUIDv7、8バイト厳守で時刻精度と連番の細かな制御が要るならSnowflake、という住み分けになります。

ボトルネックとトレードオフ

横にスクロール

最大の敵は時計の逆行（clock skew / NTPの巻き戻し）です。Snowflakeの一意性はローカル時計の単調前進を前提にするため、NTP同期で時刻が過去へ飛ぶと、同じ (時刻, マシンID, 連番) を再発行して衝突します。対策は擬似コードのとおり、逆行を検知したら逆行幅を過ぎるまで採番を待機する（短い逆行なら数ミリ秒のブロックで吸収）ことです。逆行が大きい場合は採番を止めてアラートを上げる方が、静かに重複IDを撒くより安全です。実運用では、時刻を1ミリ秒でも巻き戻さないよう単調増加を保証するOSクロック（monotonic clock）を併用します。

次のボトルネックは中央集権DB採番のスループットです。1行のカウンタ更新は強い単調性を与える反面、全採番がその1行のロック争奪に直列化し、可用性もその1台に依存します。これを緩和するのが事前割当（segment / ticket）方式です。各アプリノードがDBから「10001〜20000」のようにID範囲を一括で借り、ローカルではメモリ上のカウンタで配り、使い切る前に次の範囲を非同期で先読みします。DBへの往復はステップ幅分の1に減り、範囲を配る UPDATE segment SET max_id = max_id + step は原子的な1操作で済みます。

トレードオフは厳密な単調性と分散性の綱引きに集約されます。全世界で1件たりとも逆転しない厳密単調が要るなら中央採番しかありませんが、可用性とスループットを犠牲にします。Snowflakeやsegmentは「同一ミリ秒内の順序」や「範囲間の順序」を緩め、代わりにローカル採番の速度と耐障害性を得ます。多くのシステムでこの緩和は許容範囲です。ID自体に厳密な全順序を求めず、必要なら別途タイムスタンプ列で並べればよいからです。

さらにスケール時の論点として、採番の負荷分散とマシンID枯渇があります。10bitの1024ノード上限は、オートスケールでコンテナが分単位で生成・破棄される環境では足りなくなりがちで、ビット配分をタイムスタンプ41→39bit・マシン10→12bitのように振り直す（＝寿命を縮めて並列度を上げる）判断が要ります。採番ノード群自体を負荷に応じて増減させる設計は、リクエストを均すL4ロードバランサや、範囲リースの整合を保つ一貫性ハッシュといった周辺技術と組み合わせて初めて実運用に耐えます。結局のところ「64bitという固定予算を、時刻の寿命・並列ノード数・毎ミリ秒の採番数へどう三分割するか」が、この設計の本質的な意思決定です。