mrasu’s blog

読んだ物の内容など

Distributed Computing: Principles, Algorithms, and Systems (3章)

「Distributed Computing: Principles, Algorithms, and Systems」の3章
コンピュータ内の時計に誤差が発生するせいで、発生順と発生時間が同じにならないので、どのように時刻を取るかという話
時間すら定義が必要とか、分散怖い・・・

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

Chapter3 Logical time

3.1 Introduction

イベントの因果関係を把握することで

  1. イベントの生存と失敗を把握したり、デッドロック検知のアルゴリズム
  2. 復旧時にファイルの不整合を見つけて、復旧ポイントを作成できる
  3. 進捗を把握でき、古い情報の削除やGCに役立つ
  4. 並列性の度合を把握できる。

普段の生活では、腕時計や近くの時計などが「ある程度」同期していれば、遠隔のことでも因果関係が把握できるが、
分散システムでは各プロセスの数十ミリ秒の時刻差でも長すぎる。
論理時刻を使って時刻を見れるようにする

3.2 A framework for a system of logical clocks

論理時計には、2種類の時間データがある

  1. ローカルプロセスの進捗を計測するための、ローカルな時計
  2. 他プロセスとの一貫性を持った時間を持つための、グローバルに統一された時計

全ての論理時計には、時計を管理するために2つのルールがある

  1. イベントがあったときに、ローカルな時計を更新する方法
  2. 受信したメッセージに付加された論理時計の情報を見極め、グローバルな時計を更新する方法

3.3 Scalar time

Lamportが提案したScalar timeは、ローカルとグローバルの時計を分けない。
ルールは、

  1. 送信や内部イベントなどを実行する前にd時間進める(dの値はシステムによるが1が典型)
  2. メッセージには自分の時間を付加し、受信側は自分の持つ時間と比較して大きいほう+1の時間に変更する

すると、送信イベントと受信イベントの時間は、常に 送信 < 受信

順序を決める場合に、同時刻に起きたイベント(並列性がある)にも、順序をつけるときは、プロセスに序列をつけて、後の時刻で起きたとする。
時間は、イベントが起きたときに更新されるので、時間の前後に因果関係がない。つまり、強い一貫性があるわけではない。

3.4 Vector time

Fidge,Mattern,Achmuckそれぞれが、提案したVector time はn個の各プロセスにn次元行列(vt)の時間を持たせる
ルールは、

  1. イベント実行前に、vt[i]をd進める
  2. 各メッセージは送信者が持つベクトルを付加し、受信側は各値を自身の持つ時間と比較して大きいほうの時間に変更する(+1はしない)

すると、

二つのプロセスの行列vh, vkについて、

  1. vh = vk なら、全ての時間が一致している
  2. vh <= vk なら、全ての時間がvh[i]以上
  3. vh < vk なら、vh <= vk かつ、いずれかがvh[i]より大きい
  4. vh || vk なら、 ^(vh < vk)⋀vk < vh

イベントxとyが持つvh,vkについて、

vh < vk なら、 xとyは因果関係にあり、vh||vkなら、x||y
強い一貫性を持つので、時間を見れば因果関係があるかどうかわかる
各プロセスにある自分の時間は(dが1なら)自身に起きたイベントの数なので、その時にあるベクトルの合計は事前に起きた各プロセスのイベントの総量
因果関係がわかるので、いろいろなところで使いやすい

ベクトルの長さは全てのプロセスの進捗を知りたければ、全プロセス数が必要だが、nプロセス間のイベントが対象であればnでいい。

3.5 Efficient implementations of vector clocks

vector clockは規模の大きい分散だと、オーバーヘッドが大きい

3.5.1 Singhal-Keshemkalani&s differential technique

変更された時間だけを送るようにすれば、メッセージ量が減らせる。特に通信範囲を限定している場合には通信コストを削減できる
つまり、

{(i1, v1), (i2, v2)}

のように、変更部分を指定する。
この方法を実現するためには、各プロセスが他のプロセスに送った時間を覚えておく必要があり、O(n2)の空間が必要になってしまう。
これを避けるために、

  1. 最後に送った時間(LS: Last Sent)
  2. 時間を更新した時間(LU: Last Update)

を記録すれば、LS < LU になっている部分が変更があった場所だとわかるので十分

3.5.2 Fowler-Zwaenepoel's direct-dependency technique

自プロセスの時間だけを付加して送信する。
各プロセスが時間を保持すれば、他プロセスとの推移的依存関係を再帰で求めることができる。
これは、負荷情報が少ない代わりに、推移的な依存を求めるための時間と、過去データを保持する空間が必要になる。
そのため、情報がリアルタイムで必要になるアプリケーションには適さない
また、時間の更新はメッセージを受信してから送信するまでの間に行う必要がある

3.6 Jard-Jourdan's adaptive technique

前のイベントが発生した後に発生した受信イベントの時間を付加して送信すると、送信イベントに必要な直接の依存関係にあるイベントを把握できる。
プロセスに内部イベントが発生したら、受信イベントでためてきたイベント(pseudo-direct)をプロセスの依存関係に追加する

3.7 Matrix time

Matrix timeは、

  1. 自プロセスのローカル時間
  2. 自プロセスが確認した他プロセスのローカル時間 (Vector time)
  3. 他プロセスのローカル時間
  4. 他プロセスが確認した他プロセス(第3者のプロセス)のローカル時間

を持つ(つまり、各プロセスが保持する全プロセスのローカル時間を持つ)
更新方法は、

  1. 送信や内部イベントなどを実行する前にd時間進める
  2. 各メッセージは送信者が持つ行列を付加し、受信側は
    1. 自プロセスが確認した他プロセスのローカル時間は、自身の持つ時間と送信プロセスが確認した他プロセスのローカル時間を比較して大きいほうの時間に変更する
    2. 第3者のプロセスの時間は、受信データと自身のデータを比較して大きいほうの時間に変更する

全てのプロセスが確認した第3者プロセスlがtより大きい場合、自プロセスは「プロセスlは全プロセスに対してt以降の情報を送っている」と理解できる
つまり、プロセスlに関するt以前の情報は全プロセスにわたっているので、削除しても問題ないとわかる

3.8 Virtual Time

3.8,1 Virtual time definition

Virtual timeは以下を満たす必要がある。

  1. 送信時間 < 受信時間
  2. 何かのイベントの実行時間 < 次のイベントの実行時間

これで、因果関係があるイベントA, Bでは、Aが終わった時間 < Bの開始時間 を維持する

特徴は

  1. 各Virtual timeは同一のものではない
  2. 部分的に順序だっているが、全てのプロセス間の時間と実行順序が等しいわけではない
  3. 現実の時間とリンクしていたり、別物だったりする
  4. プログラマが操作できるものであったり、何らかの定義によって暗黙的に決まっているものだったりする
  5. 計測可能だったり、特定のルールに従って代入される

3.8.2 Comparison with Lamports losical clocks

Lamport のロジックとの違い

Lamportのものは時間を正確にしているので、時間の前後関係から依存関係を正確に出すことができる
Virtual time では不正確になることがあり、不正確だとわかった時に時間を修正するので、依存関係はでない

3.8.3 Time worp mechanism

メッセージの前後関係と、メッセージに付随するタイムスタンプの前後関係は必ずしも一致しない。
それを解決するために、time warpが存在する
time warp はローカルと、グローバルの2つの機能にわけられる

3.8.4 The local control mechanism

ローカルの時間はイベント間で変化し、イベント途中では変化しない。
受信したメッセージは受信時刻順に並べられ、順に処理される。
もし、処理済みのメッセージ以前のタムスタンプがついたメッセージが来た場合、ロールバックして対象のメッセージから順に処理する。
(ロールバックが発生する必要が少ないことが前提)

ロールバック対象の処理の中にメッセージの送信イベントがあった場合、送信先をロールバックする必要があり、
送信先のロールバック対象に送信イベントがあった場合には、送信先の送信先をロールバックする必要がある。

ロールバックのために、Antimessageを用意する。
Antimessageのために、各受信(送信)時間の逆数を記録する。また、イベントの実行後の状態も記憶しておく必要がある。
ロールバックが必要になったら、

  1. ロールバック直前のイベントまで状態を戻す
  2. 戻した時間以降に発生した送信イベントに対してantimessageを対象プロセスに送信する
  3. 戻した時間から処理を実行する

また、antimessageを受け取ったプロセスは

  1. 処理実行前にantimessageを受け取ったら、対象の処理キューから削除する
  2. 処理実行中または、処理後だった場合は、ロールバックを実行してantimessageを送信する
  3. antimessageに対応したメッセージが見つからない場合は、何もせず、対応メッセージが来たら何もせず削除する

Global control mechanism

Global Virtual Time(GVT) は実時間rの時のシステム状態のプロパティの1つで

  1. 全てのvirtual timeが実時間r
  2. r時点で送信はされているが処理されていないメッセージの送信時間

の小さいほう
GVTは減少しないし、システムのvirtual clockとみなすことができる。
GVTが正確に何時であるかを知ることはできないが、GVTの取得アルゴリズムでは、アルゴリズムの開始と終了の間の時間を求めることができる
ただし、O(d) (dは遅延)かかる

GVTの利用例としては、

  1. メモリ管理
    古い情報の削除、受信されていないことを送信先に伝えて送信キューからの削除
  2. 停止検知
    プロセスはメッセージがなくなってローカルのvirtual timeが無限大になったら停止し、GVTが無限大になったらメッセージを送信を停止する。
    time warpではGVTが無限大になったら停止を教えてくれる
  3. エラーハンドリング
    たいていのエラーはロールバックで直るが、直らなければ通知する
  4. IO
    ロールバックが存在するので、外部機器への出力はすぐに実行するのではなくGVTがreceive timeを超えたときに実行する
  5. スナップショット管理
    ローカルのvirtual timeがtの時にスナップショットを取り、ロールバックがtを跨いだらスナップショットを破棄する。
    GVTがtを超えたら、スナップショットは完成し、有効であると考えられる

3.9 Pysical clock syncronization: NTP

分散システムの時間が必要な理由は以下など、

  1. イベントが発生した時間
  2. 別マシンで起きたイベント間の時間差
  3. イベントが発生した順序

定義は、

  1. 時刻 (Time)
    あるマシンのもつ時刻。実時間と同じ
  2. 頻度 (Frequency)
    時計の進んだ割合
  3. 差(Offset)
    実時間との差
  4. ねじれ(Skew)
    実時間との頻度の差
  5. ドリフト(Drift)
    クロックの値の二階微分

ネットワークを挟むので、時刻差を推測する必要がある。
そこで登場するのがNTP。