# ハイブリッド論理クロック ## 定義 ハイブリッド論理クロック(Hybrid Logical Clock, HLC)とは、物理時刻と Lamport 論理時刻を組み合わせた分散クロック方式である。Demirbas ら(2014)が提案し、CockroachDB([[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]])が本番採用したことで広く知られる。 - **物理時刻成分**: NTP などで粗く同期されたノードの壁時計 - **論理時刻成分**: Lamport クロックに基づく因果関係カウンタ ノードはメッセージ送受信のたびに HLC タイムスタンプを交換し、自身の HLC を更新する。クラスタ全体に設定した**最大許容オフセット**(CRDB デフォルト 500 ms)の範囲内でクロックが同期している前提で動作する。 ## 主要特性 CockroachDB §4.1 が挙げる 3 特性: 1. **因果関係追跡**: ノード間メッセージに HLC を添付・受信で更新することで Lamport クロックと同様の因果追跡を実現。これにより Range リースの不整合(2 ノードが同時にリースを持つ状況)を検出・防止できる 2. **厳密単調増加**: 単一ノード内はプロセス再起動後も保証。起動時に最大クロックオフセット分待機することで実現 3. **自己安定**: ノード間通信が十分あれば一時的なクロックスキューがあっても HLC が収束する傾向がある(強保証ではなく軟弱的緩和) ## 不確実性区間との関係 CRDB では各トランザクションが HLC に基づく不確実性区間 `[commit_ts, commit_ts + max_offset]` を持つ。区間内のキー値を "過去の書き込み" とみなす uncertainty restart により、**単一キー線形化可能性**を保証する。これは [[TrueTime]] の commit wait とは異なるアプローチで、コミット遅延なしに不確実性を処理する。 ## TrueTime との比較 | 観点 | HLC(CockroachDB) | TrueTime(Spanner) | |---|---|---| | 仕組み | 物理+論理の組み合わせ | GPS + 原子時計の実時間不確実性区間 | | ハードウェア要件 | 汎用サーバー(NTP 等) | 専用(GPS/原子時計) | | 不確実性上限 | 設定値 max_offset(デフォルト 500ms) | ε ≈ 4ms | | 一貫性保証 | 単一キー線形化可能性 | 厳密直列化可能性(外部一貫性) | | コミット遅延 | なし(Read Refresh でリトライ) | commit wait(≥ 2ε) | ## 横断的知見 - 現時点での wiki ソースは CockroachDB のみ。他の分散システムでの HLC 採用事例(MongoDB, YugabyteDB 等)が揃い次第積み増す。 ## 未解決の問い - HLC の max_offset を小さく設定するほど uncertainty restart が減る一方、クロックドリフトへの耐性が下がる。実運用での推奨設定値の根拠は何か? - TrueTime のような atomic clock ベースのクロックが汎用クラウドでも利用可能になりつつある(AWS Time Sync Service 等)。これにより HLC と TrueTime のギャップは縮まるか? - CRDB の自己終了機構(80% 超過でノード終了)は過剰な保護か、それとも必要か? ## 関連 - ソース: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] - 概念: [[外部一貫性]] / [[分散トランザクション]] / [[TrueTime]] / [[地理分散SQLデータベース]] - エンティティ: [[CockroachDB]] ## 出典 - [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]](SIGMOD 2020 §4.1〜4.3)