読者です 読者をやめる 読者になる 読者になる

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

Coursera

Coursera

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

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

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 がよく使われる.サイトごとにジョブをアロケートして,サイト内(イントラ)のスケジュールはサイトに任せる.

Interview

全部見れてなくて TODO にしてある.