分散ID生成の進化は、マイクロサービスアーキテクチャのボトルネックとなった集中型データベースシーケンスから、TwitterのSnowflakeやUUIDのバリアントへと遡ります。初期のアプローチは、NTP同期時計に大きく依存していましたが、これはリープセコンド、クロックドリフト、ネットワークパーティションの際に脆弱であることが判明しました。イベントソーシングおよびグローバルに一貫したログ記録の必要性から、調整オーバーヘッドなしで因果関係を尊重する厳密に単調なシーケンスが求められています。
従来のアプローチは、可用性と順序付けの間の時計ずれのジレンマに直面しています。物理的なタイムスタンプは厳密な同期を必要とし、CAP定理に従ってパーティション耐性を侵害しますが、ラプラスタイムスタンプやベクトル時計のような純粋な論理時計は、時間的ローカリティとデータベースの圧縮効率を犠牲にします。データベースのインデックス効率のためにkソート可能性が必要な場合、課題はさらに重要性を増します。この粗い時間順序は、厳密な単調性と共存しなければならず、フェイルオーバーシナリオでは後方移動が発生しないことを保証します。さらに、海底ケーブルの切断時に地域的な孤立がIDの衝突や可用性の喪失を引き起こさないようにしなければなりません。
物理時間（ミリ秒コンポーネント）と論理カウンタを組み合わせたハイブリッド論理クロック（HLC）アーキテクチャを実装し、ノードIDのパーティショニングを強化します。各地域クラスターは、スタートアップ時またはメンバーシップ変更時に、etcdやZooKeeperなどのコンセンサスサービスからノードID（10-16ビット）を受け取ります。各ノード内で、物理時間が進んでいない場合にHLCが論理コンポーネントを増加させ、クロック調整にもかかわらず単調性を保証します。
ID構造は次のように組み合わされます：エポックミリ秒（41ビット）+ 論理カウンタ（12ビット）+ ノードID（10ビット）。パーティション中、ノードはローカル論理カウンタ空間からIDを引き続き割り当てます。パーティションが回復した際には、HLCの最大プラスワンマージルールにより、中央集権的な調整なしに因果関係の保存が保証されます。
あるグローバルな暗号通貨取引所は、AWS us-east-1、eu-west-1、およびap-southeast-1全体での取引IDの生成が必要でした。このシステムは、市場の変動中に1秒あたり800万件の注文を処理しながら、規制監査トレイルのために厳密な時間秩序を維持する必要がありました。海底ケーブルメンテナンス中のネットワークパーティションは、以前のレガシーシステムでのUUIDv4衝突のリスクを引き起こし、データベースの一意制約違反と取引停止をもたらしました。
解決策1：キャッシングを伴う中央集権的PostgreSQLシーケンス
PostgreSQLシーケンスを展開し、アプリケーションレベルのバッチ割り当て（10,000 IDsを一度に取得）を使用することで、データベースのラウンドトリップを削減しました。しかし、アジア太平洋ネットワークパーティション中に、キャッシングノードは90秒以内に割り当てられた範囲を使い果たし、UUID生成にフォールバックせざるを得なくなりました。これは監査トレイルの順序を破ることになりました。単一のRDSインスタンスも、クロスリージョンの書き込みに140msのレイテンシペナルティを生み出し、50ms未満の生成要件に違反しました。
解決策2：SnowflakeインスパイアのTwitterアルゴリズム
ZooKeeper管理のノードIDを用いたSnowflakeの実装は、各ノードで22,000 IDs/secを達成し、優れたソート可能性とコンパクトな64ビットIDを提供しました。しかし、NTPデーモンが欧州ノードでリープセカンドのスミア状態に陥り、米国ノードが早急なステッピングを使用したため、システムはミリ秒タイムスタンプの重複を生成し、高コストのデータベース制約チェックを必要とし、スループットが40％低下しました。
解決策3：CRDT収束を伴うハイブリッド論理クロック
CockroachDBのHLCパターンを採用し、各地域のリーダーはローカル論理カウンタを维护，通过ノードIDの空間を地域ごとに分割し、各ノードで1ミリ秒あたり4096 IDsを管理しました。シンガポールケーブル切断中、孤立したノードは論理カウンタを使用してIDを引き続き生成し、再接続後、HLC比較関数が重複を防ぎつつ因果関係を保持しました。このアプローチは、正しさの保証のために128ビットのID幅を犠牲にし、パーティション中の可用性を維持しました。
選ばれた解決策と結果
解決策3が選ばれたのは、そのパーティション耐性と単調性保証のためでした。このシステムは、南シナ海のケーブルメンテナンス中の4時間のパーティションにも耐え、重複なしで、孤立した東京地域で1秒あたり1200万件のIDを処理しました。再調整後、HLCの先行-before追跡により、IDの再書き込みはゼロで済み、ストレージコストはUUIDに比べて15％減少しました。
ほとんどの候補者は、NTPが常に時間を前方に進めると仮定します。実際には、積極的な時計ずれ補正により、数百ミリ秒後方に時間が設定されることがあります。この解決策には、永続的な単調クロック（CockroachDBの「合成」時間に類似）を維持する必要があります：OSが、最後に割り当てられたIDの物理コンポーネントよりも小さいタイムスタンプを報告した場合、システムは物理的後退を無視し、実時間が追いつくまで論理カウンタのみを増加させ続けます。
さらに、ノードが最大のドリフト信頼区間をゴシップし、ローカルの不確実性が10msを超える場合、生成要求を拒否するクロックバウンド伝播を実装します。このメカニズムにより、IDを発行する前に非同期のノードを検出できます。これにより、外部の整合性を侵害する「巻き戻し」異常を防ぎます。
候補者は、10ビットのノードIDが1,024のユニークな生成器しか提供できないことをよく見逃します。頻繁にポッドの再起動があるKubernetes環境では、単純なID割り当てが数週間内にネームスペースを使い果たしてしまいます。解決策は、エポックベースの再利用の実装です：ノードIDはetcd内でTTL（生存時間）でリースされ、再利用されるIDは最大の時計ずれを超える「墓碑」隔離期間に入ります（通常は24時間）。
再デプロイメント中、システムはそのノードIDから発行された最後のIDのHLCをチェックします。現在のグローバル時刻からそのタイムスタンプを引いた値が隔離時間を超えた場合、そのIDは再割り当てが安全と見なされます。これには、退役ノードのメタデータを追跡する墓地サービスが必要です。
kソート可能なID（Snowflakeのような）は、LSMツリーまたはBツリー構造の「ホットエンド」での書き込みを集中させ、最新のSSTableまたは最右の葉ページを圧迫します。候補者は、kソート可能性が読み取りローカリティを改善する一方で、CassandraやTiKVにおいて書き込み増幅を引き起こすことをしばしば見逃します。軽減策として、シャードプレフィックスを介じたエントロピーコーディングを導入します：ノードIDまたはクライアントセッションの4ビットハッシュをIDの前に追加し、粗い時間順序を維持しながら16のRocksDBメンテーブル間で書き込みを分散させます。
CockroachDBの場合、ID列の上にハッシュシャーディングインデックスを使用します。別のアプローチとして、最近のIDをRedis Streamsにバッファリングし、コールドストレージへのバッチ挿入を行う書き込みデッキングを採用します。これにより、取り込みが圧縮サイクルから分離されます。