🔥虚無との戦い

☁分散システム

14 min read

分散システムまとめ

Distributed System.

分散システムとは,そのユーザに対して単一で首尾一貫 (coherent) したシステムとして見える独立したコンピュータの集合.

重要な側面は,

  • 分散システムは自律コンポーネントからなる
  • ユーザはそれらを単一のシステムとしてあつかう

重要な特性は,

  • 多様なコンピュータの差異
  • それらが通信する方法

に関して, ユーザから隠蔽されていること.

☁ミドルウェア

Middleware. 分散システムは,

  • ユーザとアプリケーションからなる高位レベル層
  • OS や基本通信機能

の間に存在するソフトウェアの層として構成されることがおおい. そのため, 分散システムをミドルウェアと呼ぶ.

ref. ミドルウェア - Wikipedia

☁クライアントサーバ方式

🌉プロキシ/Proxy

プロキシはクライアントとサーバの間に存在し、情報元のサーバに対してはクライアントの情報を受け取る、クライアントに対してはサーバの働きをする（HTTPプロキシの場合）。

🎨Proxy Pattern

☁ピアツーピア方式(P2P)

対等の者 (Peer, ピア) 同士が通信をすることを特徴とする通信方式.

クライアント - サーバ方式と対比される.

  • Napster … はじめて登場した p2p システム
  • Gnuterra … servants (サーバがいない.クライアントのみ)

Bittorrent

巨大なファイルを高速にダウンロードすることを目的に開発された P2P.

DHT (Distributed Hash Table)

ネットワーク状のマシンの集まりに Data を保存&取得するための分散アルゴリズムの総称.

100 万ノード超のネットワーク上に 1 つの巨大 Hash table を構築する技術. Key と value からなるデータを保存したり取得したりする.

100 万ノードのどのマシンに保存すればいいか.

  • ランダムに ID を設定.
  • key のハッシュ値をデータの ID とする.
  • 担当領域が決まる.
  • データ ID を担当しているマシンが保存先.

経路表を見て, データ ID に一番近いマシン ID をもつマシンを選んで, そいつに転送する. これをひたすら繰り替えしてたどりつく.

ref Hiroya Nagao, Graduate student at Tokyo institution of technology

Chord

DHT を実現する代表的なアルゴリズム.

特徴

  • マシン ID は Hash (マシンの IP アドレス)
  • ID 空間はリング状.
  • 担当決めは時計回り.
  • 各ノードは経路表 (finger table) を参考にクリエを転送して検索.
  • O (logN) でノード探索.

Grid computing

WAN 上にある計算資源 (CPU などの計算能力や, ハードディスクなどの情報格納領域) を結びつけ, ひとつの複合したコンピュータシステムとしてサービスを提供する仕組み.

複数のコンピュータをネットワークを介してつないで構成した, 高性能な仮想コンピュータ (Workstation)

Globus

グリッドソフトウェアの開発を進める団体.

Globus Toolkit

Grid Computing を構成するためのデファクトスタンダードな OSS.

クラウドコンピューティングとの比較

グリッド・コンピューティングクラウド・コンピューティング
管理形態別々の組織による管理形態単一組織による管理形態
標準化団体ありなし
用途科学技術計算などの大規模な演算処理と大規模演算に加え
並列性の高いアプリケーションWeb アプリなどの用途で利用可能

OpenStack との比較

  • OpenStack は Cloud Computing
  • Globos は Grid Computing

KVS: Key-Value Store

-> DataBase へ

CAP 定理

ノード間のデータ複製において, 同時に次の 3 つの保証を提供することはできない.

  • 一貫性 (Consistency) 全てのノードにおいて同時に同じデータが見えなければならない.
  • 可用性 (Availability) ノード障害により生存ノードの機能性は損なわれない. つまり, ダウンしていないノードが常に応答を返す. 単一障害点が存在しないことが必要.
  • 分断耐性 (Partition-tolerance) システムは任意の通信障害などによるメッセージ損失に対し, 継続して動作を行う. 通信可能なサーバーが複数のグループに分断されるケース (ネットワーク分断) を指し, 1 つのハブに全てのサーバーがつながっている場合は, これは発生しない. ただし, そのような単一障害点のあるネットワーク設計は可用性が成立しない.

wikipedia:

example

  • consistency & Partition-tolerance: HBase
  • Availiability & Partition-tolerance: Casandra
  • Availiability & Consistency: RDBMS

Eventual Consistency

厳密な一貫性を要求する考え方ではなく, 結果的に一貫性が保たれればよいという考え方.

Casandra で利用されている.

Quorum (consistency level)

分散トランザクションが処理を実行するために必要な最低限の票の数である. quorum ベースの技術は分散システムにおいて, 処理の整合性をとるために実装される.

多数決の原理. 最低 2 ノードからの応答によって通信が成功/ 失敗したかどうかを判断する.

Mutual Exceptions

相互排他

MapReduce

クラスター上での巨大なデータセットに対する分散コンピューティングを支援する目的で, Google によって 2004 年に導入されたプログラミングモデル.

関数型プログラミングの map/reduce を参考にしている.

(map square '(1 2 3 4))
 
(reduce + '(1 2 3 4))

MapReduce の後継として, Spark, Tez が注目を集めている.

Hadoop

もっとも有名な MapReduce のオープンソース実装 (Java)

Apache Hadoop - Wikipedia

HDFS

Hadoop 独自のファイルシステムである. HDFS は各 OS が提供するファイルシステム上で動作し, 数ペタバイトの容量まで拡張するよう設計している.

YARN

Yet Another Resource Negociator.

Hadoop のスケジューラ. Node に仕事を割り当てる順番を制御する.

Distributed File Systems (DFS)

複数のサーバに点在するフォルダを一つのフォルダツリーのように扱う技術.

ファイルシステムの仮想化技術.

  • GFS
  • HDFS

Clock Syncronization

クロック同期.

分散システムにおいて, プロセスが協調して互いに同期しあうことが重要.

物理的クロック

コンピュータのもつクロックを時間の基準とする考え方.

Cristian’s algorithm

一般的なアルゴリズム. request,response の平均時間を足す.

Cristian’s algorithm - Wikipedia, the free encyclopedia

集中アルゴリズム.

NTP

デファクトスタンダードな 時間同期プロトコル. 通信時間による時刻値の誤差を小さくする工夫がなされたプロトコル.

Network Time Protocol - Wikipedia

論理クロック

プロセスの同期は必要だけれども, それが絶対的な時間でなくてもいいという考え方. さらに, 時間を同期している必要もなく, イベントの発生順序について合意していればいいという考え方.

Lamport timestamps

ほとんどすべての 分散システムで利用されている, 論理クロックアルゴリズム. lamport が唱えた.

Vector Clock

ベクトルクロック (Distribute Systems p248)

Lamport timestamps に 因果性 を導入.

  • happens-before”(事後) 関係

    イベントの順番を知るための方法.

    同一プロセス内で発生したイベント A, B において.

    • A が B より以前に発生した場合, A->B.
    • A がメッセージを送るイベント, B がそれを受け取るイベントなら, A->B.

    異なるプロセスで発生したイベント X, Y において.

    • X->Y も Y->X も成り立たない. X, Y は「同時」である.

    イベント A に対して, 全てのプロセスが同意する時刻 C (A)

    • A->B の場合, C (A)->C (B) でなくてはならない.
    • A がメッセージを送るイベント, B がそれを受け取るイベントなら, C (A)->C (B) である.
    • 時計の値 C は常に進み続ける. (イベント間では必ず 1 つ進む)

Global Snapshot

分散システムにおけるそのときの状態.

liveness & Safety

Collectness (正確性) は 2 つの性質からとらえられる

  • liveness (生存性) guarantee that something good will happen, eventually.

  • Safety (安全性) guarantee that something bad will never happen.

Snapshot Algorithm

Chandy-lamport global snapshot alogrithm ともいう.

📝Remote Procedure Call(RPC)

Remote Procedure Call/RPC, 遠隔手続き呼び出し.

  • 異なるアドレス空間(クライアントからサーバなど)のプロセス間で関数を呼び出すためプロトコルまたは技術.
  • リモートで実行される関数をローカル関数と同様に扱えるように設計されている.
  • コードは自動生成されることもおおい(ex.Spring).

🔖JSON-RPC

RPCのデータやり取り形式で🔖JSONをもちいる.

以下はv2.0の仕様.

  • method: 呼び出すメソッド名の名前.
  • params: JSON.
  • id: requestとresponseを一致させる番号.
{"jsonrpc": "2.0", "method": "subtract", "params": {"minuend": 42, "subtrahend": 23}, "id": 3}
{"jsonrpc": "2.0", "result": 19, "id": 3}

📝gRPC

Google Remote Procedure call/gRPC. 🔖Googleの開発したRPC派生技術.

  • 📝HTTP/2を利用.
  • バイナリデータの扱いに秀でる(http2のProtocol Buffers技術).
    • 既存技術のRPCはバイナリを扱いづらかった.

📝Protocol Buffers

Googleによって開発されたデータシリアライズのための言語/プラットフォームに依存しないバイナリフォーマット. 構造化されたデータ（構成設定や通信プロトコルのメッセージなど）を効率的に保存・交換するために使われます.

LPC

Local Procedure Call. 同一プロセス内で関数が呼ばれる.

📝トランザクション処理

RPCにおけるトランザクションとは, クライアントからサーバへの一連の処理.

  • commits サーバに変更を残す.
  • aborts サーバになにも影響を与えない.

Concurrency

Pessimistic Concurrency

もっとも悪い場合を想定して, オブジェクトにアクセスさせない.

排他的ロック. lock/unlock, ロックを獲得したものだけアクセスさせる.

  • write mode
  • read mode

Optimistic Concurrency

もっともよい場合を想定して, オブジェクトにアクセスさせる.

pessimistic concurrency よりも並列性を向上させる.

📝コンセンサスアルゴリズム

参加者のグループにおいて単一の結果について合意を得るプロセス

たとえば以下のようなものに関わりがある.

Reliable Multicast

Make sure that all of them receive the same updates in the same order as each other

Membership/Failure Detection

To keep their own local lists where they know about each other, and when anyone leaves or fails, everyone is updated simultaneously

Leader Election

Elect a leader among them, and let everyone in the Exclusigroup know about it.

Mutual Execution

To ensure mutually exclusive (one process at a time only) access to a critical resource like a file.

Synchronize

メッセージが一定時間内にやりとりされるシステム.

  • 合意をとるアルゴリズムは存在する.

Asynchronize

メッセージが不定な時間にやりとりされるシステム.

  • 合意をとるアルゴリズムは存在しない.(LFP proof)

PAXOS

もっとも有名な 合意アルゴリズム.

🔗References

グラフビュー

バックリンク

Recents