分散システムにおけるユニークIDジェネレータの設計

分散システムにおいてユニークなIDを生成するのって意外と難しいんです。auto incrementを単純に使うと容易に衝突してしまいます。

なので、今回はいろいろなIDの生成方法を紹介していきたいと思います。

設計に必要な情報をあつめる

まずは、IDの設計を考えるうえで、次のいくつかの要件を考慮する必要があります。

一意性: システム全体でユニークであるIDを生成することが必須です
ソート可能性: IDがソート可能な形式であれば、データベースやアプリケーションでの検索や管理が効率的になります
IDに含まれる文字: 数字のみなのか文字列も含んで良いのか
IDの長さ: IDの長さはシステムのパフォーマンスに直結する重要な要素です。特に、データベースや分散システムにおいては、IDの長さがクエリの速度やストレージの効率性に大きく影響します
システムの規模: 高スループット環境では、ID生成アルゴリズムのパフォーマンスが極めて重要になります
推測困難性: IDを改ざんされても機密情報が見れないようにできている必要があります

これらはシステムがなにを要求するのかにどこまで対応していくのかが変わっていくかと思います。

では具体的な生成方法についてみていきましょう。

ユニークIDの生成

今回紹介するのは、「システム設計の面接試験」で紹介されているものを紹介したいと思います。

マルチマスターレプリケーション
汎用一意識別子(UUID)
チケットサーバ
X(旧Twitter)によるsnowflakeアプローチ

マルチマスターレプリケーション

マルチマスターレプリケーション方式では、複数のデータベースノードが同時に書き込み操作を実行できるようになります。この方式でIDを生成する場合、通常は各ノードが固有のID範囲を管理します。例えば、使用中のデータベースの数が k 個の場合、IDは k 個ずつ増えていきます。もし3つのデータベースノードが存在する場合、IDの生成順序は以下のようになります。


ノード1: 1, 4, 7, 10, ...

ノード2: 2, 5, 8, 11, ...

ノード3: 3, 6, 9, 12, ...

設計方法は非常に単純ですが、下記のような問題があります。

データセンターでの拡張が大変: 新しいデータベースノードを追加する場合、既存のID範囲や増加パターンを再設定しなければならず、手間がかかります。
スケーリングが難しい: ノードの追加や削除が伴うため、システムのスケーラビリティに制約が生じることがあります。

汎用一意識別子 (UUID)

(UUID)は、128ビットの識別子であり、システム内の各エンティティを一意に識別するために使用されます。UUIDの生成は非常に簡単で、ほとんどの場合、各サーバーが独自にUUIDを生成するため、中央管理の必要がありません。

生成が簡単: UUIDはアルゴリズムによって簡単に生成することができます。特別な設定や管理が不要です。ライブラリで用意されているものが多いのでサクッと生成が可能です。
スケーリングが容易: 各サーバが独自にUUIDを生成するため、追加のサーバを導入する際に特別な調整が不要です。これにより、システムのスケーラビリティが向上します。

これだけ見るとuuid素敵！ってなるんですが、、、

サイズが大きい: 128ビットのUUIDは、従来の整数ベースのIDに比べてサイズが大きくなります。これがデータベースのパフォーマンスやメモリ使用量に影響を与える可能性があります。
ソート性能が低い: ものによってはソートができるものもありますが、一般にuuidと言ったらソートできないものを指しますね。

UUIDv6,7,8がRFC 9562で定義されました！ (2024-05-10)

わかりやすい記事があったのでそちらも紹介いたします

チケットサーバ

分散システムや大規模システムにおいて、ユニークなID（チケット）を生成し、各ノードやクライアントに提供するためのサーバです。中央集権的なID生成システムとして機能するため全てのID生成リクエストを一元管理し、連続的かつ一意なIDをクライアントに提供する役割を担います。

Flickerが分散型の主キーを生成するためのチケットサーバを開発しました。
- Ticket Servers: Distributed Unique Primary Keys on the Cheap
実装が簡単: ID生成ロジックを集中管理することで、コードの複雑さを削減できます
障害点が単一: 単一のチケットサーバが障害点になる可能性があり、このサーバがダウンするとシステム全体がIDを生成できない状況に陥ります
データの同期: 複数のチケットサーバを運用する場合、各サーバ間でデータが同期されていなければ、IDの一意性保証が難しくなります

twitterによるsnowflakeアプローチ

調べると結構細かいことがたくさんでてきたので、詳しい話はほかの解説記事にお任せします。。。下記に良さそげなリンクを張っておきました。
ここでは、IDの構成について簡単に説明して終わります。

IDを異なるセクションに分割
- タイムスタンプが41bitある→69年はもつ（2^41-1 bit）

[1]

そのほか考慮事項

一意識別子の生成は、その設計と実装においていくつかの課題を伴います。具体的には、クロック同期、セクション長のチューニング、高可用性の観点から問題があります。それぞれの問題について詳しく説明します。

クロック同期

クロックの同期：IDジェネレータが同じクロック（時間）を持つと仮定しても、各サーバやノードのクロックが完全に同期することは難しいです。これは「クロックドリフト」という現象により、時間の微妙な誤差が累積してしまうためです
複数コア問題：異なるコア上で異なるスレッドが並行して動作する場合、一貫性を保つために厳密なクロック同期が必要になります。また、クラスタ内で各ノードが独立して動作している場合、それぞれのノードがまったく同じタイミングでIDを生成することはほぼ不可能です

対策

NTP Network Time Protocol の利用：各サーバのクロックをNTPサーバで定期的に同期することで、時間の誤差を最小限に抑えます。
ローカルタイムに依存しない構造：生成時にシーケンス番号やランダム部分を活用し、タイムスタンプの依存度を減少させることで、クロック同期の問題を軽減します。
- トークンバケット

セクション長のチューニング

セクション長のバランス：UUIDの構造を設計する際、タイムスタンプ部分とランダム部分のバランスをどう取るかは重要な課題です。タイムスタンプを長くすると、より多くの情報を時間に含めることができますが、その分ランダム性が減少し、一意性に問題が出る可能性があります。

おわりに

IDの生成と一口にいってもシステム要件によって考慮することがたくさんあるなと改めて感じました。RFCについて、UUIDの件で初めてちゃんと読みましたが、意外と面白かったのでまたほかのものも読んでみようかと思います。

参考文献