# ID生成器と論理クロック ## 定義 ID生成器(ID generator)とは、データベースレコードに一意な識別子を割り当てる仕組みである。単一ノードのオートインクリメントカウンタは実装が単純で、ID の大小関係がレコード作成順序を表す(順序保証)という利点を持つが、単一障害点になる・地理分散環境で往復通信が必要になる・高スループット下でボトルネックになる、という3つの問題を抱える。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "ID Generators and Logical Clocks") 論理クロック(logical clock)は、物理時計に依存せずイベントの因果順序を近似的に表現する仕組みである。Lamport クロックは「あるノードが観測したどのタイムスタンプよりも大きい値を生成する」ことしか保証できず、そのノードが観測していないイベントとの順序は保証されない。 ## 分散 ID 生成の設計空間 | 方式 | 一意性 | 順序保証 | 単一障害点 | |---|---|---|---| | 単一ノードのオートインクリメント | 保証 | 保証 | あり | | シャーディング(偶数/奇数ノード等) | 保証 | 失われる(ノード間の順序不明) | 個々のシャードには残る | | 事前割り当てブロック | 保証 | 失われる(ブロック間の順序不明) | 個々のノードには残る | | ランダム UUID(v4等) | 高確率で保証 | なし(ランダム) | なし | | 時刻ベース一意化(UUIDv7・Snowflake・ULID・MongoDB ObjectID等) | 保証 | 近似的(クロックスキューで乱れうる) | なし | | Lamport クロック / ハイブリッド論理クロック | 保証 | 因果順序のみ保証(線形化可能ではない) | なし | | 線形化可能な ID 生成器(単一ノードの fetch-and-add) | 保証 | 完全に保証(線形化可能) | あり(フォールトトレラントにするにはコンセンサスが必要) | (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "ID Generators and Logical Clocks", "Linearizable ID Generators") ## 論理クロックの限界と線形化可能な ID 生成 Lamport クロックやハイブリッド論理クロック(HLC)は、メッセージを介して因果関係のあるイベント間の順序を保証するが、通信していないイベント間の順序は保証しない。DDIA が示す例では、あるユーザーがラップトップでアカウントを非公開に設定した直後にスマートフォンで写真を共有した場合、2つの操作が別々のデータベース(アカウント DB・写真 DB)にそれぞれ HLC タイムスタンプで記録される。両者は通信していないため、写真 DB のローカルカウンタがわずかに遅れていると、写真のタイムスタンプがアカウント変更より小さくなり、MVCC のスナップショット読み取りで「非公開設定前」の状態として写真が閲覧されてしまう。 これを解決する最も単純な方法は、真に線形化可能な ID 生成器(単一ノードで atomic fetch-and-add を行い、永続化・複製する)を使うことである。地理分散環境で単一ノードへの往復通信を避けたい場合は、Spanner の TrueTime のように、不確実性区間の長さだけ待機する(commit wait)ことで、通信なしに線形化可能な順序を保証する方式もある。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizable ID Generators") さらに、論理クロックやコンセンサスを使わない線形化可能な ID だけでは、ロックやユニーク制約の実装には不十分である。「自分のタイムスタンプが最小かどうか」を判定するには、原理的に全ノードからの応答を待つ必要があり、1ノードでも到達不能になるとシステムが停止してしまう。フォールトトレラントに実装するには、単なる論理クロックではなくコンセンサスが必要になる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Enforcing constraints using logical clocks") ## 横断的知見 - **HLC の「因果順序のみ保証」という性質は、CockroachDB の単一キー線形化可能性の限界と表裏一体である**: [[ハイブリッド論理クロック]] ページは CockroachDB の HLC が「不確実性区間 + Read Refresh」で単一キー線形化可能性のみを保証し、真の外部一貫性には至らないと記録するが、本章が示す「アカウント DB と写真 DB のような通信していない別データベース間では HLC の因果順序保証が効かない」という一般的な限界(図10-10)は、CRDB の単一キー限定という設計上の妥協が、HLC というプリミティブそのものの理論的限界から直接導かれることを示す。すなわち CRDB が単一キーに留めているのは実装上の選択ではなく、HLC を使う以上避けられない制約である。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizable ID Generators", [[ハイブリッド論理クロック]] の Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §4.1〜4.3) - **TrueTime の commit wait は「線形化可能な ID 生成器」と「外部一貫性のあるコミットタイムスタンプ」という2つの異なる目的に同じ機構が使い回されている**: [[TrueTime]] ページは commit wait を Spanner の外部一貫性保証の手段として記録するが、本章は同じ commit wait を「通信を伴わずに線形化可能な ID を生成する」一般的な手法として位置づける(TiDB/TiKV のタイムスタンプオラクルは同じ問題を単一ノードの fetch-and-add で解く対照例)。これは、不確実性区間つき物理クロックという1つのプリミティブが、コミット順序保証と ID 生成という表面上は別の2つの問題を同時に解いていることを示す。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Implementing a linearizable ID generator", [[TrueTime]] の Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) ## 未解決の問い - UUIDv7・Snowflake・ULID のような時刻ベース ID は本番で広く使われているが、クロックスキューによる順序逆転が実際にどの程度の頻度で発生し、どのようなアプリケーション不具合につながっているかの定量データは本章にはない。 - 論理クロックにコンセンサスを組み合わせて「フォールトトレラントな線形化可能 ID 生成器」を構築する具体的なアーキテクチャ(単一ノードのフォールトトレラント化以外)は、どの程度実用化されているか。 ## 関連 - ソース: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] - 概念: [[線形化可能性]] / [[ハイブリッド論理クロック]] / [[TrueTime]] / [[分散コンセンサス]] ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]]