Coursera で "Cloud Computing Concepts, Part 1" Week 5 を受講した

Coursera

Coursera でイリノイ大学の講義 "Cloud Computing Concepts, Part 1" を受講してる！

Week 5 に関して個人的な勉強メモをまとめた．

• https://www.coursera.org/learn/cloud-computing

Week 5 : 期間

• 2016/09/26 - 2016/10/02

• Week 5: Classical Distributed Algorithms

  • Overview
  • Lesson 1: Snapshots
    • What is Global Snapshot?
    • Global Snapshot Algorithm
    • Consistent Cuts
    • Safety and Liveness
  • Lesson 2: Multicast
    • Multicast Ordering
    • Implementing Multicast Ordering 1
    • Implementing Multicast Ordering 2
    • Reliable Multicast
    • Virtual Synchrony
  • Lesson 3: Paxos
    • The Consensus Problem
    • Consensus In Synchronous Systems
    • Paxos, Simply
    • The FLP Proof [OPTIONAL]
  • Interview
  • Homework

Lesson 1: Snapshots

• グローバルスナップショット
  • プロセスごとに取得する
  • プロセスに一部でも変更があった場合はグローバルスナップショットを再作成する

Global Snapshot Algorithm

• グローバルスナップショットとは，各プロセスの状態と各チャネルの状態を記録すること
• システム上に N 個のプロセスがあり，各プロセス間に行き帰りのチャネルがある
• ようするに Pi と Pj がある場合
  • Pj → Pj
  • Pj → Pi
• Chandy-Lamport Global Snapshop Algorithm
  • Initiator プロセス
    • 自身の状態を表す
    • Marker メッセージを作る
    • Marker メッセージは他のプロセス (N-1 個) に対して送信される
  • Marker を最初に受信する場合
    • 自身の状態を記録する
    • 別のプロセスから戻ってくる Marker を受信した場合は別のプロセスの状態を記録する
• 実際にサンプル図を使って考える
  • P1 : Initiator は 自身の状態を S1 として保存する
  • P2 と P3 に対して C12 と C13 上で Marker を送信する
  • P1 からの Marker を受信した P3 は初回なので自身の状態を S3 として保存する
  • そして C31 で Marker を P1 に返す
  • Marker を P3 から受信した P1 は2回目の Marker なので，C31 の状態を空にする
  • もしまだ C12 が届いてないとした場合
  • C32 が P2 から見ると初回の Marker 受信となる
  • よって P2 で自身の状態を S2 に保存する
  • C12 を受信したら2回目の Marker なので，レコーディングを中止する

Consistent Cuts

• Cut とは
  • 「各プロセスと各チャネルの境界となる時間」を意味する
  • 境界の内側にいる場合 : in the cut
  • 境界の外側にいる場合 : out of the cut
• コンシステントカットとは順序が整っている場合にそう呼ぶことができる
  • メッセージの送信中でカットした場合も順番が合っていれば大丈夫

Safety and Liveness

• Liveness
  • 結果的に良いことが起きることを保証する
    • オリンピックで100mをはしったら，誰かが金メダルを取る
• Safet
  • 結果的に悪いことが起きないことを保証する

Lesson 2: Multicast

Multicast Ordering

• Multicast ... プロセスのグループにメッセージを送信する
• Broadcast ... プロセス全てにメッセージを送信する
• Unicast ... 1プロセスから1プロセスにメッセージを送信する
• マルチキャストをするときの順番に関して
  • FIFO
    • プロセスP1から発生する M1:1 と M1:2 の順番は確実に保証される
    • ただし M3:1 と M1:2 はわからない
  • Causal
    • FIFO の拡張モデル
    • こっちの方が前後関係を考慮できて良い
  • Total
    • 完全にロックをして整合性を取る

Implementing Multicast Ordering 1

• FIFO ordering
  • 各プロセスの状態（整数）を持ったベクター
  • 自身を +1 する
  • 受信した側は送信元の状態が +1 であることを確認する
    • +1 なら受信側の状態を +1 する
    • 違っていたらバッファに置く（そのプロセスのベクターを）
    • また既に知っている値よりも小さかった場合は捨てる

Implementing Multicast Ordering 2

• Causal ordering
  • FIFO ordering に似ている
  • ただし，シーケンス番号の扱いとベクターの更新方法が異なる
  • シーケンス番号ではなくベクター全体をマルチキャストで送信する
  • 2個の条件が満たされるまで受信側はバッファに置く
    • 受信した側は送信元の状態が +1 であること
    • 前後関係が満たされていること

Reliable Multicast

• 信頼性を高める
• Pi->Pj
• Pjが全体に送ることで担保される

Virtual Synchrony

• 仮想同期
• View 各プロセスがメンテナンスをしているメンバーシップリスト
• View を更新することを View Change と呼ぶ（プロセスが増えたり減ったり，落ちたりすること）

Paxos

The Consensus Problem

• 分散システムで重要
• 制約
  • Validity
  • Integrity
  • Non-triviality
• コンセンサス
• 同期システムモデルと非同期システムモデル
• 同期の場合は全てのプロセスが同期される
• 非同期システムは実行時間のboundsはない

Consensus In Synchronous Systems

• f ... クラッシュするプロセス数
• f が知り得ない場合にも合意プロセスが成り立つ

Paxos, Simply

• Paxos Algorithm
• safety と eventual liveness を提供する
• 多くのシステムが採用している
  • Zookeeper (Yahoo!)
  • Chubby (Google)
• コンセンサスにおける安全条件とは？
• 複数のプロセスが異なる値を決定することがないこと
• Paxos はラウンドを持つ
  • ラウンドは非同期
  • タイムアウトもする
• Phase1 : Election リーダーを選出して（これもackが必要）
• Phanse2 : Bill リーダーが値を提案して確認する
• Phanse3 : Law 決定した最終的な値をマルチキャストで送信する
• Phase.1 と Phase.2 で既に過半数の同意が取れているため，Phanse.3 は過半数の同意なく送信できる
• 過半数からの ack があればok