ikemonn's blog

技術ネタをちょこちょこと

分散システム 原理とパラダイム の同期について読んだ

Time, Clocks, and the Ordering of Events in a Distributed System を読んでいたが、ぼんやりとしか分からなかったので、まず下記の同期の章を読んだ。

分散システム―原理とパラダイム

分散システム―原理とパラダイム

  • 作者: アンドリュー・S.タネンバウム,マールテン・ファンスティーン,Andrew S. Tanenbaum,Maarten van Steen,水野忠則,東野輝夫,宮西洋太郎,鈴木健二,西山智,佐藤文明
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2003/10
  • メディア: 単行本
  • クリック: 25回
  • この商品を含むブログ (20件) を見る

物理的クロック

  • クロック
    • 時間追跡管理回路(circuit for keeping track of time)
    • 時計ではなく、タイマの方が適切
    • 水晶で出来ている
      • 水晶は種類、切削方法、圧力の大きさに依存して明確に定義された周波数で発振する
    • 各水晶には2つのレジスタがある
    • 水晶は一回の発振ごとにカウンタを1減らす
      • カウンタが0になると割り込みが発生され、カウンタは保持レジスタから再設定される
      • 各割り込みはclock tickと呼ばれる
    • クロックの同期のズレをclock skewと言う
    • 原子時計
      • 原子の遷移をみる

クロック同期アルゴリズム

  • 全てのアルゴリズムは下記のモデルに基づいている
    • 各マシンは1秒にH回の割り込みを発生するタイマをもっていると仮定する
    • このタイマが動いた時、割り込み処理ハンドラは1をソフトウェアクロックに加える
    • ソフトウェアクロックは同意がなされている過去のある時点以来のtickの数を追跡管理している(C)
    • UTC時間がtのとき、マシンpのクロック地はCp(t)である
    • 完全な世界では全てのpとtに対して、Cp(t) = tである
    • だが実際はずれる

Cristioanのアルゴリズム

  • 正確な時間を持つtime serverがいるとする
  • 短い周期で各マシンが現在の時間を問い合わせるために時間サーバにメッセージを送る
  • 各マシンが時間を受け取ると、調整した後に自己のクロックをその時間にあわせる
  • 各マシンが返ってきた時間をそのまま自己クロックに適用させると問題が起こる
    • 時間サーバへの要求送信と、返答の到着との時間間隔を正確に記録する

Berckeleyのアルゴリズム

  • Cristioanのアルゴリズムにおいて、time serverは受動的
  • Berckeleyのアルゴリズムでは時間デーモンが、各マシンにそれぞれが保持している時間について時々問い合わせる
  • その返答に基づいてサーバは平均の時間を計算し、全ての他のマシンにその時間を進める/戻すように通知する

論理クロック

  • クロックの同期は可能であるが、絶対的である必要はない
  • 通常問題になるのは、全てプロセスが現在の時間について正確に同意しているということではなく、イベントの発生順序について同意しているということ

Lamportのタイムスタンプ

  • 事前発生
    • a -> b は「aはb以前に発生する」
      • aがまず発生し、次にイベントbが発生していることに全てプロセスが同意していることを示す
    • 事前発生関係は次の2つの状況において直接的に観察できる
      • もしaおよびbが同じプロセスにおけるイベントで、aがb以前に発生するならa->b
      • もしaが1つのプロセスによって送信されたメッセージのイベントであり、bが別のプロセスによって受信されたそのメッセージのイベントなら、a->bは真
  • それぞれのイベントaに対して、全てのプロセスが合意する時間時C(a)を割り当てられることが重要
    • a->bならばC(a) > C(b)
  • クロック時間Cは常に増加しなければならない
    • 減算してはいけない

f:id:ikemonn:20170704214130p:plain

    • 各プロセスが異なる速度で動作しているとする
    • 避けるべき例
      • A: プロセス0(以降p0)がp1にメッセージを送ると、p1は10かかったと判断する
      • B: p1がp2にメッセージを送ると16かかったと判断する
      • C: p2がp1にメッセージを送ると-4となり明らかに不正である
    • 対応方法
      • C: p2では60に出発しているので60以降でないといけない、60未満であれば出発時の時間+1になるように自己クロックを進める
  • 必ずイベント間には1のtickがある
  • この方法を利用すると次の条件にしたがって、分散システムにおけるすべてのイベントに時間を割り当てられる
    • 同じプロセスに置いて、aがb以前に発生するなら C(a) < C(b)
    • もしaおよびbがそれぞれメッセージ送信および受信を表すなら C(a) < C(b)
    • すべての区別できるイベントaおよびbに対してC(a) ≠ C(b)

ベクトルタイムスタンプ

  • Lamportタイムスタンプでは、2つのイベントの順序については言及できるが関係については言及できない
  • C(a) < C(b)でも、必ずしも本当にaがbより以前に発生したことを意味しない
  • たとえば掲示版を考える
    • 投稿と反応の2種類があると仮定する
    • もしメッセージBがメッセージAのあとで配信されたとしても、Bは投稿Aへの反応とは限らない
      • 因果関係を把握していない
  • 因果関係はベクトルタイムスタンプで把握できる
    • イベントaに割り当てられたベクトルタイムスタンプVT(a)はイベントbにたいして、VT(a) < VT(b)なら、aはbに因果的に先行する
  • 各プロセスPiに次の2つの特性をもつ、1つのベクトルViを維持させることによって構成される
    • Vi[i]はPiにおいて今まで発生したイベントの数である
    • もしVi[j] = kならPjにおいて、k個のイベントが発生したとPiは判断する