Coursera

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

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

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

Week 2 : 期間

2016/09/05 - 2016/09/11

Week 2 : アジェンダ

Week 2: Gossip, Membership, and Grids
- Overview
- Lesson 1: Gossip
- Lesson 2: Membership
- Lesson 3: Grids
- Interview
- Homework

Lesson 1: Gossip

最初はマルチキャストの課題とは何か？から学んだ．マルチキャストとは，ユニキャストとブロードキャストの中間とも言える通信手法で，特定のノードグループに対してメッセージを送信する．前提としてノードはクラッシュするし，パケットはロストすると考える．またノード数が増えるとオーバーヘッドも増えるため，対障害性とスケーラビリティがマルチキャストの課題となる．

マルチキャストの実装には以下のアプローチがあり，それぞれにメリデメがある．最も優れているのは，ゴシッププロトコル（疫学的プロトコル : Epidemic Protocol と呼ぶこともある）とのこと．

Centralized（中央集約型）
- 最もシンプルな実装で，単純なループ処理で実現できる
- 対障害性に課題があり，送信の途中でエラーになると，再送ができなくなる
- 計算量としては O(N) になる
Tree-based（木構造型）
- IP マルチキャストのように，ルータやスイッチごとに木構造に分散させる
- 計算量としては O(log(N)) になり，中央集約型と比較すると早くメッセージを届けられる
- 木構造のセットアップとメンテナンスコストが課題になる
- もしノードがクラッシュした場合は，別のノード内のグループに移動させる必要がある
Gossip Protocol（ゴシッププロトコル）
- 特徴
  - 定期的（5秒間隔など）にランダムにターゲットノードを選択して UDP でゴシップメッセージを送信する
  - 受信側も同様に定期的にゴシップメッセージを送信する（当然，同じメッセージを別のノードから受けることもある）
  - 受信することを感染する (infected) と表現する
  - 全てのノードは独立している
  - 噂話があっという間に広まるのと同じように，一度送信したメッセージの広がりを把握することは難しくなる
- 種類
  - Push ゴシップ
    - O(log(N))
  - Pull ゴシップ
    - ターゲットノードに「最新のゴシップメッセージを持ってる？」と問い合わせる
    - O(log(log(N))) で拡散の速度は Push より Pull の方が圧倒的に高速
  - Push-Pull ゴシップ
    - Pull で問い合わせて，結果を Push で送信する

ゴシッププロトコルで実装されたサービス（ミドルウェア）も紹介されていた．

NNTP
Cassandra
EC2 and S3（ただし，公式には発表はされてなく噂として）

Lesson 2: Membership

データセンターでサーバは故障する．"Failures are the norm in datacenters." という表現だった．サーバが故障する頻度を認識する話で，MTTF の計算問題が出てきた．例えば，12ヶ月で故障するサーバが120台あった場合，MTTF は1ヶ月だし，12000台あった場合，MTTF は7.2時間となる．

次に，サーバの故障をどう検知するか？という話で，1000人の従業員を雇って常にモニタリングするよりも，自動で故障を検知するシステムを用意した方が正しく，メンバーシッププロトコルの解説があった．

メンバーシッププロトコルはメンバーシップリストを更新するが，更新手法として3種類ある．2個目の "Almost complete list" がゴシップスタイルで，今回のフォーカスとなる．

Complete list all the time (strongly consistent)
Almost complete list (weakly consistent)
Partial random list

メンバーシップには重要なプロトコルが2個ある．イメージとしては，プロセス(pi) がプロセス(pj) の故障を検知した場合，その情報をグループの他のプロセスに拡散することで，結果整合的にリストを更新する．

Failure Detector（故障検知）
Dissemination（拡散）

故障検知には以下の特徴がある．

Completeness（完全性） : 全ての故障を検知できること
Accuracy（精度） : 誤検知をしないこと
Speed（速度） : 故障を検知するまでの時間
Scale（スケール） : メンバー数に依存しないこと

Completeness と Accuracy を同時に満たすことは不可能で，通常は Completeness を保証し，Accuracy は100%でない場合がある．ただし，誤検知が起きても，確認してグループに戻すことで，大きなオーバーヘッドも無く，回避することができる．

そして故障検知のためのハートビートにも計4種類の手法がある．

Centralized Heartbeating（中央集約型ハートビート）
- 全ノードが中央にハートビートを送信する
Ring Heartbeating（リング型ハートビート）
- 両隣のノードにハートビート送信するパターン
- 反時計回りの方向にあるノードだけにハートビートを送信するパターンもある
- Centralized Heartbeating よりは良いが，2箇所が同時に故障すると，Completeness を失ってしまう可能性がある
All-To-All Heartbeating（全ノード型ハートビート）
- 全てのノードにハートビートを送信する
- Completeness は保証できるが，オーバーヘッドが大きくなりすぎてしまう
Gossip-Style Heartbeating（ゴシップ型ハートビート）
- 各ノードは { Address, Heartbeat Counter, Time (Local) } から構成されるテーブル情報を個々に保持する
- ゴシップメッセージを受けたときにテーブル同士をマージする
- マージの際にハートビートカウンターが新しい場合，その値で更新する（ただし，ローカルタイムは非同期のため，各ノードの時間にする）
- T(fail) 秒間ハートビートカウンターが更新されなかった場合，故障と判定し T(cleanup) 秒後にリストからメンバーを削除する
- T(fail) 秒後に即削除をしてしまうと，別のノードからまだ T(fail) 秒が経過していないリストが送られてしまい，新規ノードであると認識してしまう問題が起きる
- よって，一般的には T(fail) = T(cleanup) で同じ秒数を設定する

Lesson 3: Grids

例として，コロラド大学で実装された気象予報システム RAMS (Regional Atmospheric Modeling System) は，256個以上のプロセッサーを使って予測計算をしていた．簡単に言えば HPC (High Performance Computing) を使っていたことになる．スーパーコンピュータを使うことなく，分散して，並行して同様の処理をするのが，グリッドと言える．グリッドを実現するときに，ジョブを細分化した DAG (Directed Acyclic Graph) のスケジューリングを考える必要がある．どうやってジョブをアロケートするか？

イントラでグリッドを行う場合，HTCondor がよく使われる．例えば，学生が使うマシンは夜間は余剰リソースとなり，そこにアロケートしていく．例えば，ジョブが実行中のマシンが起動されて割り込まれた場合は，すぐに処理を停止する．再実行可能なタスクになっているため，すぐに別のマシンに投げることができる．大学間などグローバルに接続したグリッドを行う場合，Globus がよく使われる．サイトごとにジョブをアロケートして，サイト内（イントラ）のスケジュールはサイトに任せる．