システムデザイン面接：ハイブリッド論理クロック（HLC）を使用してノード間のイベントを順序付ける方法

プロンプトとスコープ

3リージョンのKey-Valueストア向けにノード間バージョンスタンプを設計します。各ノードにはローカルの物理時計（ウォールクロック）のみが存在し、最大スキューは50ミリ秒と想定されています。ネットワークではメッセージの遅延、再試行、並べ替えが発生する可能性があり、ノードの時計が逆行することもあります。書き込みには、MVCC、監査の順序付け、競合診断のための比較可能なバージョンが必要です。

これは、分散ストレージ、データベース、インフラストラクチャ、およびシステムデザインの面接に適したテーマです。HLCはペア (physical, logical) で構成されます。物理部分はウォールタイムの近くにとどまり、論理部分は物理時間が進まない場合や、より新しいリモートスタンプが観測された場合に進みます。この問題では、並行イベントの実世界での順序を推論することは求められておらず、TrueTimeスタイルのハードウェア時間境界も提供されていません。

面接官がテストしていること

面接官はコンポーネントの前に保証を求めています：

優れた回答では、HLCが因果関係の順序、ローカルの単調性、物理時間への近接性を保持することを説明します。グローバルな実時間順序や競合のない全順序を主張することはありません。
優れた回答では、「物理時間プラスカウンター」と繰り返すだけでなく、ローカルイベントおよび受信イベントに対する更新の不変条件（Invariants）を提示します。
優れた回答では、書き込み時のみにスタンプを生成するのではなく、最大クロックスキュー ε を読み取り処理に持ち込み、MVCCで再試行が発生する理由を説明します。
優れた回答では、ベクトルクロックやTrueTimeと比較し、HLCがコンセンサス、一意性制約、またはアプリケーションの競合解決を置き換えるものではないことを述べます。

不十分な回答では、単に2つのマシンクロックの最大値を取るだけにとどまります。それでは、メッセージの因果関係、時計の巻き戻り、論理カウンターのオーバーフロー、不確実性区間が見落とされてしまいます。

回答前の確認事項

スタンプは何を保証する必要がありますか？ HLCはキーごとのMVCCバージョンの順序付けには十分ですが、リージョン間での外部整合性（External Consistency）コミット順序にはコンセンサスまたは時間境界サービスが必要です。
50 ミリ秒は厳密な上限ですか、それとも観測されたメトリクスですか？厳密な上限のみが ε を安全に定義できます。推定値はアラートや保守的な再試行に役立ちます。
読み取りはレプリカをまたぐことができますか、また再試行は許可されますか？レプリカ間の読み取りには読み取りタイムスタンプと不確実性境界を含める必要があります。再試行が禁止されている場合は、保証または調整ラウンドを変更する必要があります。
並行する書き込みはどのようにマージされますか？ HLCはタイムスタンプを比較可能にしますが、アプリケーション側で条件付き書き込み、ベクトルコンテキスト、または明示的なマージルールが依然として必要です。

30秒の回答フレームワーク

「各ノードで (p,l) を保持します。p は観測された最大の物理時間であり、l はその物理時間内でのタイブレークを行います。ローカルイベントの場合、max(now,p) を使用し、物理時間が進んだら論理部分をリセットし、そうでなければインクリメントします。リモートスタンプを受信した場合は、ローカル、リモート、現在の物理コンポーネントの最大値を取り、複数のソースがその最大値を共有する場合は論理部分をインクリメントします。これにより、因果関係を持つメッセージによってHLCは進みつつ、値はウォールタイムの近くに維持されます。MVCCの場合、スキュー上限 ε を不確実性ウィンドウに変換します。そのウィンドウ内のバージョンには再試行またはより高い読み取りタイムスタンプが必要です。HLCは並行イベントの実際の順序を証明するものではなく、コンセンサスや競合のマージを置き換えるものでもありません。」

ステップごとの詳細な回答

1. まず不変条件を述べる

各ノードは T=(p,l) を維持し、まず p で比較し、次に l で比較します。設計には3つの不変条件が必要です：

p は、ノードが観測したウォールタイムおよびリモートの物理コンポーネント以上であること。
1つのノードによって発行された連続するイベントは、厳密に増加するスタンプを持つこと。
イベントAのスタンプがイベントBに伝達された場合、Bのスタンプは厳密に大きくなること。

HLCの論文では、これを物理時間の近くにとどまりながら因果関係情報を保持することと説明しています。Martin Fowlerのパターンでも、ハイブリッドタイムスタンプを物理時間プラス論理カウンターとしてモデル化しています。

2. ローカルイベントの更新

now を現在の物理時間、(p,l) を古いスタンプとします：

text

if now > p:
    p = now
    l = 0
else:
    l = l + 1

ウォールクロックが逆行した場合でも、p は逆行せず、論理部分は増加し続けます。実装では、カウンターが制限値に近づいたことを検知する必要があります。サイレントなラップアラウンドが発生すると、比較の順序が逆転してしまいます。論文ではHLCが固定幅ストレージを使用できることが示されていますが、その幅は時計の分解能、許容されるドリフト、イベントレートに対して検証する必要があります。

3. リモートスタンプ受信後の更新

リモートの R=(rp,rl) に対して、q=max(now,p,rp) を計算し、どのソースがその最大値に達したかに基づいて論理コンポーネントを選択します：

text

if q == now and q > p and q > rp:
    (p, l) = (q, 0)
else if q == p and q == rp:
    (p, l) = (q, max(l, rl) + 1)
else if q == p:
    (p, l) = (q, l + 1)
else:
    (p, l) = (q, rl + 1)

重要な不変条件は構文ではなく次の点です。最大物理コンポーネントは決して後退せず、ローカルとリモートの値が最大値で一致した場合、論理コンポーネントは両方を超えます。送信メッセージやトランザクションコンテキストに現在のHLCを添付します。受信側は自身のイベントをスタンプする前にクロックを更新します。これにより、順序が入れ替わった古いメッセージが、既に観測された因果タイムスタンプを下げることはありません。

4. MVCCバージョンへのHLCの利用

MVCCの書き込みでは、そのHLCをバージョンとして使用できます。読み取りトランザクションは t で開始され、不確実性境界として t+ε を保持します。ここで ε はクラスタで許可されている最大物理クロックスキューです。t より後で t+ε 以前のバージョン v を確認した場合、そのバージョンが読み取り前にコミットされたのか、それとも進んだクロックによって生成されたのかを判別できません。安全な実装では、待機するか、読み取りタイムスタンプを進めるか、再起動します。CockroachDBのトランザクション層のドキュメントでは、HLCの物理・論理コンポーネントと、この不確実性による再試行動作について説明されています。

これにより、同期エラーが観測可能な再試行コストに変換されます。平均レイテンシを見るだけでなく、ε、不確実性再試行率、論理カウンターの増加を監視します。

5. 代替案の比較

ベクトルクロックは並行性を識別しますが、参加者のセットに伴ってメタデータが増加します。少数のレプリカセットで明示的な競合検出が必要なシステムに適しています。
HLCは、MVCC、監査、順序付けに固定幅の物理＋論理スタンプを使用します。2つの並行イベントが無関係であることを証明することはできず、それ単体でグローバルコミットプロトコルを完結させることはできません。
TrueTimeのような時間境界サービスは、エラー境界を持つ時間間隔を公開し、より強力な外部整合性をサポートできます。特殊な時計インフラストラクチャまたはコミット待機（Commit Wait）が必要です。

判断基準は次のとおりです。低メタデータ、実時間に近いタイムスタンプ、比較可能なバージョンが必要な場合はHLCを選択します。並行性を正確に検出する必要がある場合はベクトルコンテキストを保持します。外部整合性が必要な場合はコンセンサスまたは時間境界サービスを追加します。

6. 障害ケースと検証

物理時間のロールバック：後方へのジャンプを注入し、p が決して減少しないこと、およびスタンプが増加し続けることを確認します。
リモートの並べ替え：大きいスタンプを配信した後に小さいスタンプを配信します。後者によってローカル状態が低下してはなりません。
論理カウンターの増加：物理時間をフリーズさせ、イベントを急速に生成します。オーバーフロー前の保護パスを検証します。
ε を超えるスキュー：クロックドリフトを注入し、暗黙的な整合性の主張ではなく、起動拒否、読み取り専用への縮退、または可視化された再試行を確認します。
MVCC再試行ストーム：ウィンドウヒット率、再試行回数、ノード分散を記録し、真の競合とクロックスキューを切り分けます。

高品質な回答例

「クロックの保証とストレージの保証を分離して考えます。クロックは (p,l) を保持します。ここで p は観測された最大の物理時間であり、l は物理時間が進まない場合やリモートスタンプが同じ最大物理コンポーネントを持つ場合に進みます。すべての送信メッセージはHLCを保持します。受信側はローカル、リモート、現在の時間の最大物理コンポーネントを取得し、論理コンポーネントをその最大値にあるすべてのソースより大きくします。これにより、ウォールクロックが逆行した場合でも、因果関係のチェーンは厳密に増加するスタンプを取得します。

MVCCの場合、読み取りトランザクションには開始タイムスタンプ t とスキュー境界 ε があります。t と t+ε の間のバージョンを確認することは曖昧であるため、再試行するか読み取りタイムスタンプを前進させます。これにより、クロックエラーが明示的な再試行コストに変換されます。スキュー、論理カウンター、ウィンドウヒットを監視します。HLCは低メタデータのバージョン順序付けに役立ちますが、並行イベントは依然として任意の比較可能な順序を受け取る可能性があります。ベクトルクロックによる並行性検出や、コンセンサスまたはTrueTimeの外部整合性保証を提供するものではありません。」

よくある間違い

間違い → ローカルスタンプを now で上書きする → クロックの巻き戻しによりバージョンが後退する → 最大物理コンポーネントを保持し、論理的にインクリメントする。
間違い → リモートの最大物理時間のみを保持する → 同じ物理時間での因果関係の順序が失われる → 一致した場合はローカルとリモートの両方の論理値を超えてインクリメントする。
間違い → HLCがすべての並行関係を識別すると主張する → 単一のスカラー比較では『並行』を証明できない → 競合検出のためにベクトルまたは明示的な因果コンテキストを保持する。
間違い → 未来のように見えるバージョンを無視する → クロックスキューの下で読み取り前に存在していた可能性がある → ε ウィンドウを使用して再試行するか読み取りタイムスタンプを進める。
間違い → スキュー監視を省略する → 再試行ストームがデータベースの競合のように見える → ノードごとのスキュー、ウィンドウヒット、論理カウンターの増加を記録する。

フォローアップ質問と回答

2つの並行する書き込みが同等のHLC値を持つ場合、どちらが優先されますか？

HLCは順序付けキーを提供するものであり、実世界の順序を提供するものではありません。Last-Write-Wins（最終書き込み勝利）が許容される場合は、決定論的な (HLC, node-id) タイブレーカーを定義します。並行編集を失ってはならない場合は、複数のバージョンを保持するか、アプリケーションマージ用のベクトルコンテキストを保持します。これが競合ポリシーであり、HLCの因果証明ではないことを明確に述べてください。

最大スキューが50ミリ秒から2秒に増加した場合はどうなりますか？

古い ε を安全として扱うのをやめ、ドリフトしているノードを分離し、時刻同期を修復します。ε を大きくするとMVCCの不確実性再試行が増加し、小さくすると誤ったバージョンを読み取るリスクが生じます。境界を復元できない場合は、書き込みを一時停止するか、読み取り専用に縮退するか、より強力な調整を追加します。しきい値、アラート、リカバリアクションは運用ポリシーに属します。

高スループット下で論理カウンターが無制限に増加するのを防ぐにはどうすればよいですか？

物理ティックあたりのイベント数を制限し、十分な幅の整数を使用し、制限値の近くでアラートを発します。物理時間が進むのを待つか、時間分解能を上げるか、書き込みを拒否することができます。カウンターを切り捨てると単調性が損なわれます。ストレステストでは now をフリーズさせ、オーバーフロー前の保護パスをテストする必要があります。

データベースの自動インクリメントシーケンスを直接使用しないのはなぜですか？

単一のシーケンスは全順序を提供しますが、リージョン間の書き込みは同期的にコーディネーターに到達する必要があり、レイテンシが増加し可用性が低下します。HLCを使用すると、ノードはバージョンの順序付けや因果関係のヒントのために、実時間に近いスタンプをローカルで生成できます。厳格なグローバルコミット順序が必要な場合は、コンセンサスシーケンス、TrueTime、または同等の調整メカニズムを使用します。