分散システムにおけるユニークIDジェネレータの設計
概要
この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。
本記事では、分散システムにおけるユニークIDジェネレータの設計について解説します。
単一のデータベースであれば auto_increment で一意なIDを採番できますが、複数のサーバーにまたがる分散環境ではこの方法は通用しません。本記事では、分散環境で一意なIDを生成するための代表的なアプローチを比較し、Twitterのスノーフレーク（Snowflake）方式を掘り下げていきます。
設計の要件
本記事では、Alex Xu の設計演習にならい、次の要件を満たすユニークIDジェネレータを設計する。
- 一意性: IDは一意である（重複しない）
- 数値のみ: IDは数値のみで構成される
- 64ビット以内: IDは64ビットに収まるサイズである
- 日付順: IDは日付順に並ぶ（後に生成されたIDほど値が大きい）
- 高スループット: 1秒間に10,000以上のユニークIDを生成できる
設計の選択肢
分散環境でユニークIDを生成するアプローチは複数あり、それぞれに長所と短所がある。本記事では、以下の4つを順に比較していく。
いずれも「一意なIDを生成する」という目的は同じだが、前述の要件（数値のみ・64ビット以内・日付順・高スループット）をどこまで満たせるかが異なる。これを意識しながら見ていく。
マルチマスターレプリケーション
マルチマスターレプリケーション（multi-master replication）は、データベースの auto_increment 機能をそのまま活かすアプローチである。
単一のデータベースであればIDを1ずつ増やせばよいが、複数のデータベースサーバーで同じことをすると、各サーバーが 1, 2, 3, ... と同じIDを採番してしまい重複する。そこで、IDを1ずつではなく、サーバー台数 k ずつ増やすことで重複を避ける。各サーバーには異なる初期値（オフセット）を与えておく。
例えばサーバーが2台（k=2）の場合、次のように採番される。
| サーバー | 初期値 | 増分 | 生成されるID |
|---|---|---|---|
| サーバー1 | 1 | 2 | 1, 3, 5, 7, ... |
| サーバー2 | 2 | 2 | 2, 4, 6, 8, ... |
サーバー1は奇数、サーバー2は偶数を担当するため、両者のIDが衝突することはない。
各要件の充足状況を整理すると次のようになる。
| 要件 | マルチマスターレプリケーションでの充足状況 |
|---|---|
| 一意性 | ✅ 初期値と増分をずらすことで重複を回避 |
| 数値のみ | ✅ auto_increment の数値がそのまま得られる |
| 64ビット以内 | ✅ 通常の整数IDで収まる |
| 日付順 | ❌ サーバーをまたぐと生成時刻順に大小が並ばない |
| 高スループット | ✅ データベースの台数に応じてスケールできる |
※ ただし、増分をサーバー台数 k に固定するため、複数データセンターへの拡張やサーバーの追加・削除に弱いという運用上の弱点もある（k が変わると増分の設計をやり直す必要がある）。
マルチマスターレプリケーションは日付順の要件を満たせず、構成変更にも弱い。次のUUIDでは別のアプローチを見ていく。
UUID
UUID（Universally Unique Identifier）は、情報を一意に識別するために使われる128ビットの値である。サーバー間で調整（coordination）しなくても、それぞれが独立して生成でき、しかも衝突する確率が極めて低いのが特徴である。
UUIDは一般に、次のような16進数とハイフンの文字列で表現される。
09c93e62-50b4-468d-bf8a-c07e1040bfb2
128ビットもの広大な値空間を持つため、各サーバーが勝手にUUIDを生成しても、実用上ぶつかることはまずない。この「サーバー同士が連携しなくてよい」という性質が最大の強みである。
各要件の充足状況を整理すると次のようになる。
| 要件 | UUIDでの充足状況 |
|---|---|
| 一意性 | ✅ 衝突確率が極めて低く、実用上一意 |
| 数値のみ | ❌ 16進数・ハイフンを含み、数値のみではない |
| 64ビット以内 | ❌ 128ビットあり、64ビットに収まらない |
| 日付順 | ❌ 生成時刻順に大小が並ばない |
| 高スループット | ✅ 各サーバーが独立生成でき、十分に高速 |
※ 一方で、サーバー間の調整が不要なため、実装が単純で水平にスケールしやすいという強みがある。
とはいえ、UUIDは**「数値のみ」「64ビット以内」「日付順」の3要件を満たせない**。次のチケットサーバーでは、これらの弱点を補う別のアプローチを見ていく。
チケットサーバー
チケットサーバー（ticket server）は、Flickrが分散環境での主キー採番のために開発したアプローチである。アイデアはシンプルで、ID採番専用のデータベースサーバーを1台用意し、その auto_increment にIDの発行を一手に引き受けさせるというものである。
マルチマスターレプリケーションでは各サーバーが個別に auto_increment を持つことで順序や構成変更の問題が生じたが、チケットサーバーでは採番するデータベースを1か所に集約することでこれを回避する。各アプリケーションサーバーは、IDが必要になるたびにチケットサーバーへ問い合わせ、auto_increment の次の値を受け取る。
各要件の充足状況を整理すると次のようになる。
| 要件 | チケットサーバーでの充足状況 |
|---|---|
| 一意性 | ✅ 集約した auto_increment が重複なく採番する |
| 数値のみ | ✅ auto_increment の数値がそのまま得られる |
| 64ビット以内 | ✅ 通常の整数IDで収まる |
| 日付順 | ✅ 1台で単調増加するため、後のIDほど値が大きい |
| 高スループット | △ 単一サーバーがボトルネックになりうる |
※ さらに、5要件の外だが**単一障害点（SPOF）**という可用性の弱点がある。チケットサーバーが停止するとID採番に依存する全システムが止まる。SPOFを避けて複数台に増やすと、今度はサーバー間の同期という課題が生まれ、マルチマスターレプリケーションと同様の順序・重複の問題に逆戻りしうる。
チケットサーバーは数値ID・実装の単純さから中小規模では有力だが、単一障害点という可用性の問題を抱えるため、大規模かつ高可用な環境には向かない。次のTwitterスノーフレーク方式では、サーバー間の調整なしに、数値・64ビット・日付順のすべてを満たすIDを生成する仕組みを見ていく。
Twitterスノーフレーク方式
スノーフレーク（Snowflake）は、Twitterが分散環境でのID採番のために開発した方式である。これまでの3案はいずれかの要件を満たせなかったが、Snowflakeはこれらをすべて満たす。
発想の転換は、IDを1つの連番として直接採番するのをやめ、64ビットを複数の区画（section）に分割し、各区画に別々の意味を持たせる点にある（分割統治のアプローチ）。区画の構成は次の通りで、合計はちょうど64ビットになる。
各区画の役割は次の通りである。
| 区画 | ビット数 | 説明 |
|---|---|---|
| 符号ビット | 1 | 常に 0 に固定する。これによりIDは正の値になり、多くの言語・データベースが扱う符号付き64ビット整数（BIGINT 等）に安全に収まる。将来の利用のための予約でもある |
| タイムスタンプ | 41 | 基準時刻（独自のエポック）からの経過ミリ秒。最上位（符号ビットの直後）に置くことで、後に生成されたIDほど値が大きくなり、IDが自然に時刻順にソート可能になる（Snowflakeの肝）。41ビットで約 2^41 / (1000 × 60 × 60 × 24 × 365) ≈ 69年 分を表現できる |
| データセンターID | 5 | データセンターを識別する（2^5 = 32 個） |
| マシンID | 5 | マシンを識別する（データセンターあたり 2^5 = 32 台）。データセンターIDと合わせて最大 2^10 = 1024 台を一意に特定でき、異なるマシンが同じミリ秒に採番しても衝突しない |
| シーケンス番号 | 12 | 同じマシンが同じミリ秒内にIDを生成するたびに1ずつ増やし、ミリ秒が変わると 0 に戻す連番。2^12 = 4096 個まで区別できる |
この構成により、5要件はすべて満たされる。
| 要件 | Snowflake方式での充足状況 |
|---|---|
| 一意性 | ✅ タイムスタンプ・マシン・シーケンスの組み合わせで一意 |
| 数値のみ | ✅ 64ビット整数であり数値のみ |
| 64ビット以内 | ✅ ちょうど64ビットに収まる |
| 日付順 | ✅ タイムスタンプが最上位にあるため時刻順にソートできる |
| 高スループット | ✅ 1台あたり毎秒約409万個（4096 × 1000）生成可能で、要件の毎秒10,000個を大きく上回る |
※ データセンターIDとマシンIDは起動時に固定され、稼働中に生成されるのはタイムスタンプとシーケンス番号だけである。マシンIDを誤って重複させるとID衝突の原因になるため、割り当ての管理には注意が必要である。
Snowflakeは、サーバー間の調整なしに各マシンが独立して採番できるにもかかわらず、数値・64ビット・日付順・高スループットのすべてを満たす。これが本設計で採用するアプローチである。
まとめ
分散環境でユニークIDを生成する4つのアプローチを、5つの要件に照らして整理すると次のようになる。
| 要件 | マルチマスター | UUID | チケットサーバー | Snowflake |
|---|---|---|---|---|
| 一意性 | ✅ | ✅ | ✅ | ✅ |
| 数値のみ | ✅ | ❌ | ✅ | ✅ |
| 64ビット以内 | ✅ | ❌ | ✅ | ✅ |
| 日付順 | ❌ | ❌ | ✅ | ✅ |
| 高スループット | ✅ | ✅ | △ | ✅ |
-
マルチマスターレプリケーション:
auto_incrementの増分をずらして重複を防ぐが、サーバーをまたぐと日付順を満たせず、構成変更にも弱い - UUID: サーバー間の調整なしに独立生成でき高スケーラブルだが、128ビット・非数値・非時系列で今回の要件に合わない
- チケットサーバー: 採番を1か所に集約して数値・64ビット・日付順を満たすが、**単一障害点（SPOF）**という可用性の弱点を抱える
- Twitterスノーフレーク方式: 64ビットを区画分割し、タイムスタンプを最上位に置くことで、サーバー間の調整なしに5要件すべてを満たす。これが本設計の採用案である
比較表のとおり、他の3案はいずれかの要件で欠けるのに対し、Snowflakeだけがすべてを満たす。分散システムでユニークIDが必要になったときは、Snowflake方式（およびその派生）が有力な選択肢になる。
参考文献
この記事は以下の情報を参考にして執筆しました。