論文翻訳: Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases

Sandeep Kulkarni^*, Murat Demirbas^**, Deepak Madeppa^**, Bharadwaj Avva^**, and Marcelo Leone^*
*Michigan State University
^**University at Buffalo, SUNY

Abstract

分散システムにおける時間の扱いに関して、理論と実践の間には根本的な乖離が存在する。従来の分散システム理論は時間概念を意図的に排除し、並行性を論理的に扱うための抽象概念として "因果関係追跡" (causality tracking) を導入した。一方、実際のシステムでは厳密なクロック同期の実現が困難であることから、物理的な時刻情報 (NTP) を採用しつつも、ベストエフォート的な実装に留まっていた。この理論と実践の間のギャップを埋め、分散システムにおける時間管理の理論的基盤と実用的実装を整合させるため、本研究では論理クロックと物理クロックの双方の利点を統合したハイブリッド論理クロック (HLC) を提案する。HLC は論理クロックと同様に因果関係関係を捕捉可能であり、分散システムにおける整合性のあるスナップショットの識別を容易にする。同時に、HLC は論理クロックを常に NTP クロックに近似した状態に保つため、物理クロック/NTP クロックの代替としても利用可能である。さらに HLC は 64 ビット NTP タイムスタンプ形式に適合しており、NTP の不連続点や不確実性に対しても耐性を有する。本研究では、HLC が wait-free トランザクションの順序制御や、多版型グローバル分散データベースにおけるスナップショット読み取り操作において、多くの利点をもたらすことを実証する。

Table of Contents

1. Abstract
2. 1 導入
   1. 1.1 時間の簡潔な歴史
   2. 1.2 本研究の貢献
3. 2 予備知識
4. 3 HLC: ハイブリッド論理クロック
   1. 3.1 問題定義
   2. 3.2 ナイーブアルゴリズムの説明
   3. 3.3 HLC アルゴリズム
   4. 3.4 Properties of HLC
5. 4 Resilience of HLC
   1. 4.1 Self-stabilization
   2. 4.2 Masking of synchronization errors
6. 5 Experiments
   1. 5.1 AWS deployment results
   2. 5.2 Stress testing and resilience evaluation in simulation
7. 6 Discussion
   1. 6.1 Snapshots
   2. 6.2 Compact Timestamping using l and c
   3. 6.3 Other related work
8. 7 Conclusion
9. References
10. 翻訳抄

1 導入

1.1 時間の簡潔な歴史

時間は幻想である。(Time is an illusion.)
- Albert Einstein

論理クロック (LC): LC [12] は 1978 年に Lamport によって分散システムにおけるイベントのタイムスタンプ付与と順序付けの手法として提案された。LC は物理的な時間 (例えば NTP クロック) とは独立した概念であり、ノードはクロックにアクセスできず、メッセージ遅延やノードの処理速度・処理能力に上限が存在しない。捕捉される因果関係は "happened-before" (hb) と呼ばれ、これは時間の経過ではなく情報の伝達に基づいて定義される¹。LC は分散システム理論においては有用であるが、1) LC を使用するとイベントを物理的な時間軸と関連付けてクエリーを行うことが不可能である点、2) hb を捉えるために、LC は全ての通信が現在のシステム内で行われ、バックチャネル通信が存在しないことを前提としている点、といった現代の分散システム環境では実用的ではない点がいくつかある。これは現代の統合型で疎結合なシステム環境 (system of systems) においては時代遅れの前提条件である。

1988 年にはベクトルクロック (VC) [7, 19] が LC のベクトル化版として提案された。VC では各ノードでベクトルを保持し、そのノードが他のノードの論理クロックについて持っている知識を追跡する。LC 1 つの一貫性スナップショット (すべての関連するノードで同じ LC 値を持つもの) を見つけるのに対し、VC は全ての可能な一貫性スナップショットを特定でき、これはアプリケーションのデバッグにおいて有用である。Figure 1 に示すように、LC では (a, w) が一貫性カット (consistent cut) として検出されるが、VC は (b, w) や (c, w) も一貫性カットとして識別する。しかし残念ながら、VC の空間要件はシステム内のノード数に比例するため、実用的には許容できないレベルとなる。

物理時間 (PT): PT はネットワークタイムプロトコル (NTP) [20] によって同期されたノードの物理時計を利用する。分散システムにおいて完全なクロック同期を実現することは不可能であるため、PT には不確実性の範囲が付随する。PT は物理時刻を使用してタイムスタンプを付与することで LC の欠点を回避できるが、1) 不確実性の範囲が重複する場合、PT ではイベントの順序付けが不可能となる。NTP は通常、公開インターネット環境において数十ミリ秒単位の精度で時刻を維持でき、理想的な条件下のローカルエリアネットワーク内では 1 ミリ秒単位の精度を達成できる。しかし、非対称的な経路やネットワーク輻輳によって時折 100 ミリ秒以上の誤差が生じることがある。2) PTには、閏秒 [13, 14] や POSIX 時間への非単調更新 [8] といったいくつかの不連続点 (kink) が存在し、これらによってタイムスタンプが逆行する現象が発生する可能性がある、という新たな欠点も生じる。

TrueTime (TT): TT は Google が分散型マルチバージョンデータベース Spanner [2] の開発のために最近提案した時刻同期方式である。TT は、各クラスタに配備された GPS 時計や原子時計によって実現される高精度なクロック同期機構に依存している。TT は LC/VC/PT の一部の欠点を回避できるが、新たな欠点も生じる: 1) TT の実装には専用ハードウェアと独自開発の高精度クロック同期プロトコルが必要であり、これは多くのシステム (例えばパブリッククラウドプロバイダーからリースしたノードを使用する場合など) にとっては実現が困難である。2) TT を因果関係を尊重するイベント順序付けに用いる場合、\(e \ {\sf hb} \ f\) ならば \(tt.e \lt tt.f\) という制約が必須となる。TT は純粋に物理クロックの同期のみに基づいているため、この制約を満たすために Spanner は必要に応じてイベント \(f\) の実行を遅延させる。このような遅延と並行処理能力の低下は、特にクロック同期精度の低い環境下では重大な制約要因となる。

ハイブリッド時間 (HT): HT とは、安定化因果決定論的マージ問題 [10] を解決するために、VC と PT クロックの両方の特性を統合した時間概念として提案された手法である。HT では各ノードが自身の PT クロックに関する他ノードの知識を保持する VC を維持する。HT は PT クロックのクロック同期性という前提条件を利用して VC から不要なエントリを削除することで、因果関係追跡に伴うオーバーヘッドを削減する。実際のシステムにおいては、ノードの HT のサイズは、直近の \(\epsilon\) 時間枠内に通信を行ったノード数のみに依存する。ここで \(\epsilon\) は、クロック同期の不確実性を表すパラメータである。近年、Demirbas と Kulkarni [3] は HT を Spanner [2] の一貫性スナップショット問題の解決に適用する方法について検討を行っている。

1.2 本研究の貢献

本論文では、分散システムにおける時刻同期とタイムスタンピングの理論 (LC) と実践 (PT) の間に存在するギャップを埋めることを目的とする。さらに、TT の保証を一般化・強化する新たな手法を提案する。

• 我々はハイブリット論理クロック (Hybrid Logical Clock; HLC) と呼ばれる論理クロック版の HT アルゴリズムを提案する。HLC は、物理時計 (PT および TT と同様の概念) と論理時計 (LC と同様の概念) の両方を改良したものである。HLC は常に自身の論理時計を NTP 時計に近似させるように設計されており、これにより分散 Key-Value ストアやデータベースにおけるスナップショット読み取りなど、様々なアプリケーションにおいて物理時計/NTP 時計の代替として使用することが可能となる。最も重要な点として、HLC は論理時計の特性 (\(e \ {\sf hb} \ f \Rightarrow hlc.e \lt hlc.f\)) を保持するため、HLC はクロック同期の不確実性を待つ必要なく、事前の調整も必要とせず、事後的な方法で一貫性のあるグローバルスナップショットを取得し返却することができる。

• HLC は NTP と後方互換性があり、64 ビットの NTP タイムスタンプ形式に適合する。さらに HLC は NTP プロトコルに対して重ね合わせ的に動作する (つまり、HLC は物理クロックを読み取るだけで更新は行わない) ため、HLC は NTP を使用するアプリケーションと干渉することなく並行して動作させることができる。加えて、HLC は特定のサーバ-クライアントアーキテクチャを必要としない汎用的な設計となっている。HLC は WAN 環境におけるピアツーピアノード構成でも動作し、各ノードが異なる NTP サーバを使用することを許容する²。セクション 3 では、HLC アルゴリズムを提示するとともに HLC の空間要件に関する厳密な上限値を証明し、この上限値が因果推論のための LC 特性を HLC が満たすのに十分であることを示す。

• HLC は一般的な NTP の問題 (非単調な時刻更新を含む) に対してマスキング耐性を提供し、さらに時刻同期が劣化した状態においても処理の進行と因果関係情報を捉えることができる。HLC は自己安定化機能を備えた耐障害性システムであり、セクション 4 で詳述するように、クロック変数の任意の破損に対しても耐性がある。

• 我々は HLC を実装し、様々な展開シナリオ下における HLC の運用実験結果を提供する。セクション 5 では、ストレステスト環境下においても HLC が適切に制御可能であり、クロック値のサイズが一定の範囲内に収まることを実証する。これらの実用的な境界は我々の分析で証明された理論的境界よりもはるかに小さい値である。我々の HLC 実装は、匿名化された形で https://github.com/AugmentedTimeProject で利用可能である。

• HLC は分散データベース [2, 11, 15, 16, 22, 24] における一貫性のあるスナップショットの識別に直接的な応用がある。また、分散システムにおける因果メッセージロギング [1]、ビザンチン障害耐性プロトコル [9]、分散デバッグ [21]、分散ファイルシステム [18]、分散トランザクション [25] など、多くの分散システムプロトコルにおいても有用である。セクション 6 では、分散データベースにおけるスナップショット読み取りにおける HLC の利点を具体的に示す。

1. ¹イベント \(e\) がイベント \(f\) よりも時間的に先行する (\(e\) happened-before \(f\)) とは、\(e\) と \(f\) が同じノード上で発生し、\(e\) が \(f\) よりも時間的に先行している場合、または \(e\) が送信イベントであり、\(f\) がそれに対応する受信イベントである場合、または前二者に基づいて推移的に定義される。
2. ²実際には、HLC はアドホックなクロック同期プロトコル [17] でも動作可能であり、NTP に限定されるものではない。

2 予備知識

分散システムは時間の経過とともにその構成ノード数が変動し得るノードの集合によって構成されるシステムである。各ノードは、送信動作、受信動作、およびローカル動作という 3 種類の動作を実行可能である。タイムスタンピングアルゴリズムの目的は、システム内の各イベントに対してタイムスタンプを割り当てることにある。タイムスタンピングアルゴリズムは大文字で表記し、このアルゴリズムによって割り当てられたタイムスタンプは対応する小文字で表記する。例えば、Lamport [12] の論理クロックアルゴリズムを LC と表記し、このアルゴリズムがイベント \(e\) に割り当てたタイムスタンプを \(lc.e\) と表記する。

発生前順序関係 \({\sf hb}\) はシステム内のイベント間の因果関係を捉える概念である。これは [12] で定義されているように、イベント \(e\) がイベント \(f\) よりも前に発生している (\(e\ {\sf hb}\ f\) と表記) とは、\(e\) と \(f\) が同じノード上で発生するイベントであり、\(e\) が \(f\) よりも先に発生している、あるいは \(e\) が送信イベントで \(f\) が対応する受信イベントである場合を指す推移的関係である。我々は \(\lnot(e\ {\sf hb}\ f) \land \lnot(f\ {\sf hb}\ e)\) の場合、イベント \(e\) と \(f\) が同時発生 (concurrent) している (\(e\,||\,f\) と表記) と言う。

既存の文献における研究成果に基づき、以下の命題が成り立つ: \[ e \ {\sf hb} \ f \Rightarrow lc.c \lt ec.f \\ lc.d = lc.f \Rightarrow e\,||\,f \\ e \ {\sf hb} \ f \Leftrightarrow vc.e \lt vc.f \] しかしながら、以下の主張は成り立たない: \[ e \ {\sf hb} \ f \Leftarrow lc.c \lt lc.f \\ lc.e = lc.f \Leftarrow e\,||\,f \\ e \ {\sf hb} \ f \Rightarrow pt.e \lt pt.f \]

3 HLC: ハイブリッド論理クロック

本セクションでは、我々の HLC アルゴリズムを紹介するためにまず単純な実装方法から始める。続いて HLC の正しさを証明し、その性能に関する厳密な上限値を示す。さらに、分散システムにおける HLC の有用な特徴についても詳細に解説する。

3.1 問題定義

HLC の目的は、LC が提供するものと同様の一方向因果関係検出 (one-wey causality detection) を実現しつつ、クロック値が常に物理クロック (NTP クロック) に近い値を維持することにある。HLC に関する正式な問題定義は以下の通りである。

分散システムにおいて、各イベント \(e\) に対してタイムスタンプ \(l.e\) を割り当てる。このとき、以下の条件を満たす必要がある:

1. \(e \ {\sf hb} \ f \Rightarrow l.e \lt l.f\)

2. \(l.e\) の空間要件は \(O(1)\) 個の整数で表現可能である。

3. \(l.e\) は有限の空間で表現される。

4. \(l.e\) は \(pt.e\) に近い値となる。すなわち \(|l.e-pt.e|\) は有界である。

第一の要件は HLC が提供する一方向因果関係情報を捉えるものである。第二の要件は、\(l.e\) の記憶領域要件が \(O(1)\) 個の整数で表現可能であることを意味する。複数の整数を単一の大きな整数にエンコードすることを防ぐため、\(l.e\) の更新処理は \(O(1)\) 回の操作で完了することを要求する。第三の要件は、\(l.e\) を表現するために必要な空間が有限であることを示しており、つまり無制限に増大しないことを意味する。実際には \(l.e\) のサイズは \(pt.e\) と同じであることが望ましく、NTP プロトコルではこれは 64 ビットに相当する。

最後に、第四の要件は \(l.e\) が \(pt.e\) に近い値であるべきであることを規定している。これにより、我々は HLC を PT の代わりに使用できる。この利点を説明するため、設計者が (物理) 時刻 \(t\) でスナップショットを取得したい場合を考える。物理クロックは完全に同期していないため、Figure 2 に示すように異なるノードで時刻 \(t\) 時点での状態を読み取るだけでは一貫性のあるスナップショットを得ることはできない。一方、HLC を使用すれば、論理時刻 \(t\) 時点で全てのノードのスナップショットを取得することで、このような一貫性のあるスナップショットを得ることができる。このようなスナップショットが一貫性を持つことは保証されている。なぜなら、HLC の第一要件から \(le=lf\Rightarrow e\,||\,f\) が成立するためである。セクション 6 では、協調を必要としない事後的な分散システム状態の一貫性のあるスナップショットをユーザが HLC で取得できるようにする仕組みについて、より詳細に解説する。

3.2 ナイーブアルゴリズムの説明

\(l.e\) が \(pt.e\) に近い値となることを目標とする場合、ナイーブアルゴリズムではまず任意のイベント \(e\) において \(l.e \ge pt.e\) とする規則を採用する。我々は本アルゴリズムの設計を Figure 3 に示す。このアルゴリズムは LC アルゴリズムと同様の動作原理を持つ。初期状態では \(l\) の値は全ノードにおいて \(0\) に設定される。ノード \(j\) で送信イベント \(f\) が発生した場合、\(l.f\) には \(\max(l.e+1, pt.j)\) の値を代入する。ここで \(e\) はノード \(j\) における直前のイベントである。これにより、\(l.e \lt l.f\) と \(l.f \ge pt.f\) が保証される。同様に、ノード \(j\) で受信イベント \(f\) が発生した場合、我々は \(l.f\) に \(\max(l.e+1,pt.j)\) を設定する。ここで \(l.e\) はノード \(j\) における直前のイベントのタイムスタンプであり、\(l.m\) はメッセージ (すなわち送信イベント) のタイムスタンプである。これにより \(l.e \lt l.f\) および \(l.m \lt l.f\) が保証される。

Figure 3 に示すアルゴリズムが問題定義で示された最初の 2 つの要件を満たしていることは容易に確認できる。しかしながら、このナイーブなアルゴリズムは 4 つ目の要件を満たしておらず、これが空間制約下での表現における 3 つ目の要件の違反にもつながる。この 4 つ目の要件違反を示すため、Figure 4 に示す反例を参照されたい。この図は \(|l.e-pt.e|\) が無制限に増大していく様子を示している。ノード 1, 2, 3 間のメッセージングループは無限に繰り返すことができ、ループの各反復ごとに論理クロックと物理クロックのずれ (\(l-pt\) の差) は増大し続ける。

この無制限なクロックドリフト問題の根本原因は、ナイーブアルゴリズムが \(l\) を用いて、これまでに観測された \(pt\) 値の最大値と、新規イベント (ローカルイベント、送信イベント、受信イベント) による論理クロックの増分の両方の情報を保持しようとする点にある。この設計によりクロックは情報を失う。すなわち、新たに設定された \(l\) 値が \(pt\) 値に由来するものか (例えばノード 0 からノード 1 へのメッセージ送信の場合)、あるいは因果関係に由来するものか (その他のメッセージの場合) が不明確になる。このため、\({\sf hb}\) 関係を失うことなく \(l\) 値をリセットして \(l-pt\) の差を制限する適切な方法が存在せず、これは要件 1 の違反につながる可能性がある。

この反例は、ノードの物理クロックが当該ノード上の任意の 2 つのイベント間で少なくとも 1 回はインクリメントされるという要件を満たしている場合でも成立することに注意。Figure 4 はこの制約を \(pt\) と \(l\) の間に満たしているにもかかわらず、それでも \(|l-pt|\) の値は依然として無制限に増大し続ける。ただし、この反例が成立しない条件も存在し、単純なアルゴリズムで HLC 問題を十分に解決できる場合がある。具体的には、送信イベントと受信イベントに十分な時間が確保され、システム内のすべてのノードの物理クロックが少なくとも 1 回はインクリメントされる状況を仮定すれば Figure 4 の反例は成立せず、単純なアルゴリズムによって \(|l-pt|\) の値を有界に保つことができる。

システム内の全ノードにまたがって物理クロックの更新速度やイベント発生速度に関する仮定に依存して HLC の正しさと有界性を証明する代わりに、次セクションでは HLC を適切に実装する方法を示す。

1.	\( Initially \ lc.j := 0 \)
2.	\( {\bf Send \ or \ local \ event} \)
3.	\( \hspace{12pt}l.j := \max(l.j + 1, pt.j) \)
4.	\( \hspace{12pt}{\rm Timestamp \ with} \ l.c \)
5.	\( {\bf Receive \ event \ of \ message} \ m \)
6.	\( \hspace{12pt}l.j := \max(l.j + 1, l.m + 1, pt.j) \)
7.	\( \hspace{12pt}{\rm Timestamp \ with} \ l.j \)

3.3 HLC アルゴリズム

コンピュータサイエンスにおけるあらゆる問題は
さらなるレベルの間接参照によって解決可能である。
― David Wheeler ー

我々は反例から得られた知見を使用して正しい HLC アルゴリズムを開発した。このアルゴリズムでは、ナイーブアルゴリズムにおける \(l.j\) という表記を、\(l.j\) と \(c.j\) の 2 つの部分に拡張している。最初の部分 \(l.j\) は、これまでに学習した \(pt\) 情報の最大値を保持するための間接参照として機能し、\(c\) は \(l\) の値が等しい場合にのみ因果関係の更新を捉えるために使用される。

\({\sf hb}\) に違反することなく \(l\) をリセットする適切な場所が存在しなかったナイーブアルゴリズムとは対照的に、HLC アルゴリズムでは情報が最大 \(pt\) 値について到達またはそれを超えた時点で \(c\) をリセットすることが可能である。\(l\) はノード間で受信した最大 \(pt\) 値を示すものであり、イベントが発生するたびに連続的に増加するものではないため、一定の時間枠内では、以下のいずれかが必ず発生する: 1) ノードがより大きい \(l\) 値を含むメッセージを受信し、その \(l\) 値が更新されるとともに \(c\) もこれに対応してリセットされる、あるいは 2) 他のノードから情報を受信しない場合、ノードの \(l^) 値は変化せず、そのpt値が追いついてl値が更新され、同時に \(c\) もリセットされる。

HLC アルゴリズムの構造を Figure 5 に示す。初期状態では \(l\) と \(c\) の値はともに \(0\) に設定される。新たな送信イベント \(f\) が生成されると \(l.j\) は \(\max(l.e,pt.j)\) に設定される。ここで \(e\) は \(j\) ノードにおける直前のイベントを指す。ナイーブアルゴリズムと同様にこれにより \(l.j \ge pt.j\) が保証される。ただし "\(+1\)" の加算を削除したため \(l.e\) が \(l.f\) と等しくなる可能性がある。この問題に対処するため我々は \(c.j\) の値を利用する。\(c.j\) をインクリメントすることで辞書順比較³において \(\langle l.c, c.e\rangle \lt \langle l.f, c.f\rangle\) が成立することを保証する。\(l.e\) が \(l.f\) と異なる場合、\(c.j\) はリセットされ、これにより \(c\) の値が一定範囲内に収まることが保証される。新たな受信イベントが生成されると \(l.j\) は \(\max(l.e,l.m.pt.j)\) に設定される。ここで \(l.j\) が \(l.e\) と等しいか、\(l.m\) と等しいか、あるいはその両方であるかに応じて、\(c.j\) の値が設定される。

ナイーブアルゴリズムに対する反例について再考する。HLC アルゴリズムを適用した場合のこの例を Figure 6 に示す。ノード 1, 2, 3 の間でループを継続すると、ノード 1, 2, 3 の \(pt\) 値が \(l=10\) に追いつき、これを超えた後、\(c\) を \(0\) にリセットすることがわかる。これにより各ノードの \(c\) 変数が適切に制限される。

HLC アルゴリズムの正しさを証明するために、まずこのアルゴリズムが要件 1 を満たし、LC アルゴリズムとして使用できることを示す。これはアルゴリズム内で \(l\) 値と \(c\) 値がどのように更新されるかを見れば容易に理解できる。

定理 1. 任意の 2 つのイベント \(e\) と \(f\) に対して、\(e \ {\sf hb} \ f \Rightarrow (l.e,c.e) \lt (l.f,c.f)\) である。∎

次に HLC が要件 4 を満たすことを示す。この要件は HLC 値が PT 値に近いことを要求するものである。アルゴリズムにおける \(l\) の更新方法を考慮すると、定理 2 の証明は容易に理解できる。

定理 2. 任意のイベント \(f\) に対して、\(l.f \ge pt.f\) である。∎

定理 3. \(l.f\) は \(f\) が認識している最大クロック値を表す。言い換えると、\( l.f \gt pt.f \Rightarrow (\exists g: g \ {\sf hb} \ f \land pt.g = l.f) \) である。

Proof. 我々は新しいイベントが生成されるときに帰納法でこれを証明する。初期状態では、この命題は自明に満たされる。新しいイベント \(f\) が生成される場合を考える。

• \(f\) が送信イベントで \(e\) が直前のイベントである場合、帰納法によって次が成り立つ。\[ l.e \gt pt.e \Rightarrow (\exists g: g\ {\sf hb} \ e \land pt.g = l.e) \] さらに、HLC アルゴリズムより、\(l.f \gt pt.f\) ならば \(l.f = l.e\) である。また \(e \ {\sf hb} \ f\) は真である。したがって次が成り立つ。\[ l.f \gt pt.f \Rightarrow (\exists g: g \ {\sf hb} \ f \land pt.g = l.f) \]

• \(f\) が受信イベントで \(e\) が同じノード上の直前のイベント、\(m\) を受信したメッセージとする。

  再び、\(l.f \gt pt.f\) が真ならば \(l.f\) は \(l.e\) または \(l.m\) に等しい。これらの各ケースの分析は前のケースと同様である。したがって次が成り立つ。\[ l.f \gt pt.f \Rightarrow (\exists g: g \ {\sf hb} \ f \land pt.g = l.f) \] ∎

定理 3 を使用して \(|l-pt|\) が有界であることを示すことができる。

系 1. 任意のイベント \(f\) に対して、\(|l.f - pt.f| \le \epsilon\) である。

Proof. クロック同期制約により \(e \ {\sf hb} \ f\) かつ \(pt.e \gt pt.f + \epsilon\) を満たす 2 つのイベント \(e\) と \(f\) が存在することはない。したがって、定理 3 からこの定理が導かれる。∎

最後に、要件 3 を証明するために HLC の \(c\) 値も有界であることを示す。これを実現するために定理 3 を拡張し、特定の時刻に生成されたイベントと \(c\) 値の関係を明らかにする。定理 4 で示すように \(c.f\) は時刻 \(l.f\) において生成されたイベントに関する情報を包含している。

定理 4. 任意のイベント \(f\) に対して、\[ \begin{align*} c.f = k \land k \gt 0 \Rightarrow & (\exists g_1, g_2, \ldots, g_k : \\ & (\forall j: i \le j \lt k: g_i \ {\sf hb} \ g_{i+1}) \\ & \land (\forall j : 1 \le j \le k : l.(g_i) = l.f) \\ & \land g_k \ {\sf hb} \ f) \end{align*} \]

Proof. ...

3.4 Properties of HLC

4 Resilience of HLC

4.1 Self-stabilization

4.2 Masking of synchronization errors

5 Experiments

5.1 AWS deployment results

5.2 Stress testing and resilience evaluation in simulation

6 Discussion

6.1 Snapshots

6.2 Compact Timestamping using l and c

6.3 Other related work

7 Conclusion

References

1. K. Bhatia, K. Marzullo, and L. Alvisi. Scalable causal message logging for wide-area environments. Concurrency and Computation: Practice and Experience, 15(10):873–889, 2003.
2. J. Corbett, J. Dean, et al. Spanner: Google's globally-distributed database. Proceedings of OSDI, 2012.
3. M. Demirbas and S. Kulkarni. Beyond truetime: Using augmentedtime for improving google spanner. LADIS '13: 7th Workshop on Large-Scale Distributed Systems and Middleware, 2013.
4. E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11), 1974.
5. R. Escriva, A. Dubey, B. Wong, and E.G. Sirer. Kronos: The design and implementation of an event ordering service. EuroSys, 2014.
6. R. Fan and N. Lynch. Gradient clock synchronization. In PODC, pages 320–327, 2004.
7. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference, 10(1):56–66, Feb 1988.
8. K. Kingsbury. The trouble with timestamps. http://aphyr.com/posts/299-the-trouble-with-timestamps.
9. R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative byzantine fault tolerance. SIGOPS Oper. Syst. Rev., 41(6):45–58, October 2007.
10. S. Kulkarni and Ravikant. Stabilizing causal deterministic merge. J. High Speed Networks, 14(2):155–183, 2005.
11. Avinash Lakshman and Prashant Malik. Cassandra: Structured storage system on a p2p network. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC '09, pages 5–5, 2009.
12. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
13. The future of leap seconds. http://www.ucolick.org/~sla/leapsecs/onlinebib.html.
14. Another round of leapocalypse. http://www.itworld.com/security/288302/another-round-leapocalypse.
15. C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguica, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. OSDI, 2012.
16. W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. Don't settle for eventual: Scalable causal consistency for wide-area storage with cops. In SOSP, pages 401–416, 2011.
17. M. Maroti, B. Kusy, G. Simon, and A. Ledeczi. The flooding time synchronization protocol. SenSys, 2004.
18. A. Mashtizadeh, A. Bittau, Y. Huang, and D. Mazieres. Replication, history, and grafting in the ori file system. In SOSP, pages 151–166, 2013.
19. F. Mattern. Virtual time and global states of distributed systems. Parallel and Distributed Algorithms, pages 215–226, 1989.
20. D. Mills. A brief history of ntp time: Memoirs of an internet timekeeper. ACM SIGCOMM Computer Communication Review, 33(2):9–21, 2003.
21. B. Sigelman, L. Barroso, M. Burrows, P. Stephenson, M. Plakal, D. Beaver, S. Jaspan, and C. Shanbhag. Dapper, a large-scale distributed systems tracing infrastructure. Technical report, Google, Inc., 2010.
22. Y. Sovran, R. Power, M. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In SOSP, pages 385–400, 2011.
23. W. Vogels. Eventually consistent. Communications of the ACM, 52(1):40–44, 2009.
24. Z. Wu, M. Butkiewicz, D. Perkins, E. Katz-Bassett, and H. Madhyastha. Spanstore: Cost-effective geo-replicated storage spanning multiple cloud services. In SOSP, pages 292–308, 2013.
25. Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. Aguilera, and J. Li. Transaction chains: Achieving serializability with low latency in geo-distributed storage systems. In SOSP, pages 276–291, 2013.

翻訳抄

分散システムにおける論理クロックと物理時刻の長所を統合したハイブリッド論理クロック (HLC) を提案し、因果関係追跡と物理時刻への近似を両立させながら、64 ビット NTP 形式での実装と一貫スナップショット取得を可能にした 2014 年の論文。

1. KULKARNI, Sandeep S., DEMIRBAS, Murat, MADEPPA, Deepak, AVVA, Bharadwaj and LEONE, Marcelo. Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases. In: AGUILERA, Marcos K., QUERZONI, Leonardo and SHAPIRO, Marc (eds.). Principles of Distributed Systems: 18th International Conference, OPODIS 2014, Cortina d'Ampezzo, Italy, December 16-19, 2014. Proceedings. Cham: Springer International Publishing, 2014, pp. 17-32. Lecture Notes in Computer Science, vol. 8878. ISBN 978-3-319-14472-6. Available from: https://doi.org/10.1007/978-3-319-14472-6_2