# TrueTime ## 定義 TrueTime は Google が Spanner のために開発した時刻 API であり、時刻を単一値ではなく**不確実性区間 `[earliest, latest]`** として返すことを特徴とする。標準的な時刻インターフェースがクライアントに不確実性の概念を与えないのに対し、TrueTime はその区間を明示的に公開することで、分散システムが時刻の不確実性を正確に扱えるようにする。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) **TrueTime API**: | メソッド | 戻り値 | |---|---| | `TT.now()` | `TTinterval: [earliest, latest]` — 現在の絶対時刻を必ず含む区間 | | `TT.after(t)` | t が確実に過去なら true | | `TT.before(t)` | t が確実に未来なら true | ε = 区間幅の半分。`TT.now()` 呼び出し時の絶対時刻 `tabs(enow)` について `tt.earliest ≤ tabs(enow) ≤ tt.latest` が保証される。 ## 実装 - **タイムマスターマシン**: データセンターごとに配置。大半は GPS レシーバを持ち、残りは原子時計(「Armageddon マスター」)を持つ。GPS と原子時計を組み合わせることで、それぞれの障害モードが非相関となる。 - **タイムスレーブデーモン**: 各マシンに 1 つ。Marzullo のアルゴリズムで嘘つき(liars)を排除し、正確なマスターの時刻に同期する。 - ドリフトレートの上限: 200μs/秒 - ポーリング間隔: 30 秒 - ε の典型値: 1〜7ms を鋸歯状に推移。平均 4ms。 - TrueTime の信頼性: 機械統計上、故障 CPU は故障クロックの 6 倍多く、クロックの問題は相対的に極めて稀。 ## 横断的知見 - 現時点では wiki に Spanner が唯一の TrueTime 実装ソース。複数ソースが揃い次第知見を積み増す。 ## 未解決の問い - GPS と原子時計を持たない環境(パブリッククラウド、エッジ環境)で同等の不確実性保証を達成する手法は存在するか? - ε を 1ms 以下に安定させることは現実的か? 論文は「不可能な障害はない」と述べるが具体的な実験値は未公開。 - TrueTime の設計は Google が特許取得しているか? 他社の類似システム(Amazon Time Sync Service 等)との比較は? ## Spanner での用途 [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]では以下の用途に使われる: 1. **外部一貫性保証**: Commit wait(`TT.after(s)` が真になるまで待機)で `s < tabs(e^commit)` を確保。 2. **Paxos リーダーリースの不整合性証明**: リース区間の disjointness を TrueTime で証明し、余分なログ書き込みを不要にする。 3. **アトミックスキーマ変更**: 未来のタイムスタンプを `TT.now().latest` を超えた値で登録し、その時刻に達するまでの操作との整合性を確保する。 ## 関連 - ソース: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] - 概念: [[外部一貫性]] / [[分散トランザクション]] - エンティティ: [[Google]] / [[James C. Corbett]] / [[Jeffrey Dean]] ## 出典 - [[@2013__TOCS__Spanner - Google's Globally Distributed Database]](TOCS 2013 / OSDI 2012)