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

mrasu’s blog

読んだ物の内容など

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

「Distributed Computing: Principles, Algorithms, and Systems」という分散システムについての教科書を読み始めました。
Hadoopが「『超人しか使えない』分散システムを凡人が使えるようにしたライブラリ」という評価を受けていて、
どれほど難しい世界なのか見たくなりました。

1章は「分散システムとは何か」というイントロです。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems


Chapter1. Introduction

1.1 Definition

「分散システム」を表すと、

  1. コンピュータが壊れても、仕事(work)を止めない
  2. メモリやクロックを共有せず、ネットワーク越しにメッセージで通信し、半自立的で疎結合に問題を解決する
  3. ユーザーには1台のコンピュータに見える独立したコンピュータ群
  4. WANのように疎結合だったり、LANのように密結合だっり、マルチプロセッサーのように超疎結合だったりする幅広い意味でつかわれる単語

と、いろいろ言われるが、特徴は

  1. 物理クロックを共有しない
    重要。これによって「分散」が可能で、プロセッサ間で各々固有に各自実行できる
  2. メモリ共有しない
    メッセージパッシングを使用する。ただ、抽象的なメモリ空間を使用することはあるし、マルチプロセッサ間の共有に関する研究は分散コンピューティングの研究にもある
  3. 地理的に疎
    よくある特徴だが、必須ではない。GoogleはLAN内にクラスタを作っている
  4. 独立・不均一
    速度やOSは統一されていないし、特定のプログラムのためだけに動いているわけでもない。リソースを貸し出すことで協調している

1.2 Relation to computer system components

コンピュータ達はWANやLANでつながっており、各コンピュータ内に設置した分散ライブラリを通じてつながっている。
そのミドルウェアは非同時性などを隠している。CORBAとかRPCとかある。

1.3 Motivation

分散システムを使う動機は以下がある

  1. もともと分散している
    銀行間の金銭移動や離れた地域を通した合議制
  2. リソース共有
    周辺機器やDB,データで完全コピーを作れない場合。地理上の関係で一ヵ所におけない場合。
  3. 遠隔からデータやリソースを使用する
    大きすぎたり、重要だったりして、複製を作れない場合。中央に巨大なシステムを作り、遠隔からはクエリを投げるようになる
  4. 高信頼性
    分散すれば、データや実行を複製でき、地理的に単一障害点にもならない
  5. コストパフォーマンスが悪くなっている
    リソースを共有したり、リモートからアクセスするのはコストが高くなっている。
  6. スケーラビリティ
    リソースを追加することがボトルネックになっていない
  7. 拡張性
    疎なプログラムを追加する場合、システムのパフォーマンスに影響しない導入をしやすい

1.4 Relation to parallel multiprocessor/multicomputer systems

並列システムと分散システムの差を考える。

並列システムの特徴は

  1. マルチプロセッサーはプロセスがメモリを共有して、メモリへのアクセスするための配置方法にはomega/butterfly
  2. マルチコンピュータはメモリを共有せず、2D-meshとHypercube
  3. アレイプロセッサーはクロックは共有するが、メモリは共有せずにメッセージパッシング

分散についての研究は80年,90年代にあったが、消えてしまった。理由は

  1. 高速計算の需要がなかった
  2. 規模の経済が働いて、高速処理をするのが高くなかった(分散するより、高速に計算するほうがコスパがよかった)

Flynnによるアーキテクチャの分類

  1. SISD
    単一のCPUで単一のメモリを対象に処理する
  2. SIMD
    異なるデータに対して同一の命令を実行する(行列演算などで行われる)
  3. MISD
    同一データに対して異なる命令を実行する(可視化とか)
  4. MIMD
    異なるデータに対して異なる命令を実行する(並列システムではよくある形)

結合度による分類

  1. UMAのように、メモリを共有しているマルチプロセッサ
  2. NUMAやメッセージパッシングを使用しているマルチプロセッサ
  3. 同一箇所に置かれるマルチコンピュータ。異なるプロセッサを使用していて分散システムと呼べるが、物理的距離が近く並列システムのように速度問題がない
  4. 地理的に分散されたマルチコンピュータ。伝統的な分散システムの形

指標群

  1. 特定システムの速度を上げるための並列化による速度比。T(n)の関数であらわされる
  2. CPUがコミュニケーションのために発生する待ち時間の時間
  3. プログラムにおける分散化(並列化)されたプログラムの割合
  4. プロセス間通信の量の比率を粒度(granularity)という。コミュニケーションコストが低いと通信が多い並列化が良いが、遠隔に分散しているなら通信回数を減らすことでオーバーヘッドが減る

1.5 Message-passing systems versus shared memory systems

共有メモリの方がメッセージパッシングより簡単だが、分散システムは共有メモリを持つことができないので、仮想の共有メモリ「分散共有メモリ(distributred shared memory)」を作成する。
逆に共有メモリ上でメッセージパッシングをすることも可能である

共有メモリ上でメッセージパッシングを再現するなら、「送信」と「受信」という操作を模倣し「送信」時に送信相手のものと割り当てられたメモリ空間に書き込めばいい
メッセージパッシングで共有メモリを再現するなら、「書込」と「読込」という操作に対応して、マスタープロセスに「送信」し、マスタープロセスから「受信」することで再現する。
ただし、共有メモリを再現したところで、当然、ネットワーク通信による遅延は避けられるわけではない

1.6 Primitives for distributed communication

いろいろな選択肢

  1. バッファリング
    メッセージを送信するときには、送信時に同時にネットワーク上のリソースに書き込むか、一度バッファしてからネットワークに書き込むかを選択できる(普通はバッファする)
  2. 同期(synchronous)
    送信時にデータが受信されるのを待って完了とみなすなら「同期」している。書き込み対象(マスタプロセスとか)に書き込まれた時点で完了とするなら「非同期」
  3. ブロッキング
    送受信処理が完了するのを待ってから次の処理に移るなら「ブロッキング」。完了前に次の処理に行くなら「ノンブロッキング」。受信でノンブロッキングだと、最新データが読まれていないないかもしれない
    ノンブロッキング時の完了処理は、ループなどでステータスを見続けるか、Wait()を呼んでそこで完了を待つか。(Wait()はノンブロッキングと違い、完了を気にしない処理が実行できるというメリットがあるのだと思う)

通信だけでなく、プロセッサでも同期の選択肢があるが、分散では無理。コード上の1点で全処理揃うまで待つということはできる。

1.7 Syncronous versus asyncronous executions

同期については、プロセッサや通信だけでなく、実行においても注目に値する

  • 非同期
    1. プロセッサの同期性が不要で、ドリフト率に制限がない
    2. メッセージの遅延に上限がない
    3. ステップ実行時間に上限がない
  • 同期
    1. プロセッサは同期され、2プロセッサ間のドリフト率には限界がある
    2. 1論理ステップに行われる必要があるので、メッセージの遅延には上限がある
    3. 1ステップ実行時間に上限がある

同期を前提としたほうがアルゴリズムの設計や検証が簡単だが、実際には完全な同期システムを作るのはかなり難しく、遅延も発生するので難しい。
そこで、「仮想同期」ができた。一定時間内では非同期にして、枠を超えたら同期するようにする。

同期システムで非同期を再現するのは簡単(同期システムは同期するようにした非同期システムとみなせる)
非同期システムで同期システムを表すにはsyncrhronizerをつかう(5章で扱う)

失敗がないシステム(落ちないシステム?)では非同期システムと同期システムでできることは変わらないが、
失敗(落ちる?)することが前提のシステムでは同期システムのほうができることが多い

1.8 Design issues and challenges

インターネット出現当初から分散システムは存在していて、現在も分散システムは重要であり、課題もある。
現存する課題は以下のように分類できる

  1. システム構成やOS
  2. アルゴリズム
  3. テクノロジーの発展や新しいアプリケーションの出現

分類に重複部分はあるが、それぞれに特徴が存在する

  1. システム面についての課題
    1. 通信
      適切な通信方法は何か(RPCか、ROIか?メッセージ型かストリームか)
    2. プロセス
      クライアントやサーバーのプロセス管理やコードマイグレーション(デプロイ?)、モバイルやソフトのデザインについて
    3. ネーミング
      透過的でスケーラブルなリソースやプロセスにするには名前が重要。モバイルは動くのでさらに難しい
    4. 同期
      同期やプロセス間協調の仕組みは重要。
    5. データ蓄積とアクセス
      高速でスケーラブルなデータ蓄積法やデータアクセスの透明性は重要
    6. 一貫性とレプリケーション
      ボトルネック回避、高速アクセス、スケーラビリティの確保のためにレプリケーションが必要だが、一貫性の問題と衝突する
    7. フォールトトレランス
      リンクやノード、プロセスが落ちてもシステムが動いている必要がある。
    8. セキュリティ
      暗号化、通信、アクセスコントロール、鍵の生成と配布、認可、グループ管理など
    9. APIと透過性
      APIは差異吸収に重要である
      透過性には、アクセス、場所、マイグレーション、再配置、レプリケーション、平行実行、障害に対して吸収することが期待される
    10. スケーラビリティとモジュラリティ
  2. アルゴリズムの課題
    1. 実行モデルとフレームワーク
      interleaving model と partial order modelがあるらしい(詳細は別章?)。input/output automata modelとかTLAとか
    2. 動的な分散グラフアルゴリズムと分散ルーティング
      分散システムは動的にグラフの負荷が変わったりするので、普通とは違う。最短経路は、ユーザーのためだけでなく、ネットワーク負荷などにも影響する
    3. 時間などのグローバルな状態
      正確な物理時間を維持することと、相対的な論理時間を維持するという課題がある。
      論理時間は物理時間を共有するオーバーヘッドを削減し、分散環境下のロジックやプロセスの依存関係を把握し、進み具合を確認できる
      他のグローバル状態を見るためにも、特別なアクセス法が必要
    4. 同期・協調のメカニズム
      分散システムは並列で動くべきだが、システム状態などの情報共有やリソース管理のために同期・協調が必要。時間合わせとかリーダー決定、排他制御デッドロック解決などで
    5. グループ内のコミュニケーションやマルチキャスト、メッセージ送信順序
      コンテクストを共有し、アプリケーション単位の共通タスクを行うプロセスのグループが必要なものがあり、グループ内ではプロセスの参加・脱退・失敗を考慮する必要がある
    6. イベントや述語(?)のモニタリング
      各環境で定義され別の環境からは見えない述語は、システム全体の状況を把握したり、デバッグなどに役に立つ。
    7. 分散プログラムに適した設計と、検証ツール
      系統だった設計がされ、正しいことを検証されたプログラムはデバッグや設計など多くの時間の節約になる
    8. デバッガ
      分散下では実行可能であろう選択肢があまりにも多いため、デバッグが必要
    9. レプリケーション、一貫性、キャッシュ
      高速にアクセスのために、レプリケーションやキャッシュに対する一貫性は重要で、どこに置くかも重要
    10. World Wide Webデザイン
      wwwは分散で、キャッシュや先読みなどがある。これらの性能を向上させることも課題
    11. 分散共有メモリ
      実現はできるが、まだ高価。他のプロセスで待たされないとか、排他制御、非同期アクセスを完全に許容するメモリ管理、(完全な一貫性は遅すぎるので)現実に即した一貫性の定義などが必要
    12. 信頼性とフォールトトレランスの備わったシステム
      不正なメッセージに対処する合意(consensus)アルゴリズムレプリケーション、冗長性と選挙、分散DBとトランザクション、自動修正、チェックポイントの作成と復元、異常検知
    13. 負荷分散
      データ分散、プロセス分散、スケジューリングによって、より高スループット
    14. リアルタイムスケジューリング
      決められた時間に終わらなければならないミッションクリティカルなアプリケーションではリアルタイムスケジューリングが重要だが、遅延や断絶の可能性があるネットワークでは全体の状態を見ることすらできない
    15. パフォーマンス
      分散において、高スループットが主目的であるわけではないが、ユーザーが感じる速さは重要。パフォーマンス測定や測定法作成のためにもメトリクスは必要だし、測定ツールも必要
  3. アプリケーションに関する課題
    1. モバイル
    2. センサーネットワーク
    3. ユビキタスコンピューティング
    4. P2P
    5. pub-subの仕組み
    6. 分散エージェント
    7. データマイニングのための分散
    8. グリッドコンピューティング
    9. セキュリティ