- 地理的な位置、移動、複製、並行、並列、時間
◆フォールト・トレランス
システムが部分的に壊れる- システムの一部が故障した時、サービスを続ける。
- 分散システムは、潜在的には、フォールト・トレランスを実現できる。
- 下手に作ると、１台でも止まると全部止る。
４台同時に故障する確率：0.054==0.00006
４台のどれかが１つでも故障する確率＝＝ １-（４台すべてが動いている確率） ：1-(1-0.05)4==0.18549375
◆スケーラビリティ
構成要素の数が増えた時にどうなるか。 10台で動くものが100台、1000台で動くか。
◆（集中）アルゴリズム
（集中）システムで問題を解くための指令の集まり。
- ｉｆ文
- ｗｈｉｌｅ文
- 手続き呼び出し
◆分散アルゴリズム
要素間のメッセージの伝達の方法の集まり- どのコンピュータもシステム状態に関して完全な情報を持たない
- コンピュータは、ローカルな情報だけで決定する。
- １台のコンピュータが故障しても、全体が破滅しない。 singlepoint of failure を回避したい。
- (グローバルな時計が存在しない)
◆分散アルゴリズムの例
- 電話で放送
- 電話で多数決
- 時計を合わせる
- 戸籍、住民登録
- 筑波大学安否確認アルゴリズム
◆キーワード
- キャッシュ、局所性、ヒント
- 木構造
- 冗長性
- 重複の除去
- 時間切れ
- 暗号、認証
- トレードオフ
実用になり、かつ、利益に見合うコストで実現できる範囲を探すことが大事に なる。
■分散システムにおける同期
◆集中システムの問題
マルチスレッド、共有メモリ- 臨界領域(critical region)
- セマフォ(semaphore)、モニタ(monitor)
- デットロック
- アトミック・トランザクション
◆分散システムの問題
- クロックの同期
- 相互排除
- 選出アルゴリズム
- アトミック・トランザクション
- デッドロック
- メッセージが紛失する
- 通信遅延がある
- 時計がたくさん
- システムが部分的に壊れる(partial failure)
◆なぜクロックを同期させないといけないか
- クロックを使うアルゴリズムのため
- 時間は、人間の思考の基本
■論理クロック
◆クロック
コンピュータは、時間を追跡する回路を持っている。 水晶発振とカウンタとラッチ。タイマ割込み。１秒間に５０回〜６０回割込みがかかる。 水晶発振か、電源の周波数を使う。 一回の割込みを、clock tick という。
単一のコンピュータでは、水晶でも問題がない。
複数のコンピュータでは、 クロックの進み方(clock skew)が違うので、だんだんずれてくる。
◆論理クロックと物理クロック
- 論理クロック
- 内部で一貫性がとれていればいい
- 物理クロック
- 実際の時計とおおきくずれていてはいけない
◆Lamportの論理クロック同期アルゴリズム
事前発生(happens-before)。「a→b」は、「aはbの前に発生する」
- もしaとbが同じプロセスの事象で、bより前にaが生じるなら、a→bは真であ る。
- もしaがあるプロセスがあるメッセージを送信したという事象で、 bが別のプロセスでそのメッセージを受信したという事象なら、a→bは真である。 (送信まえには受信できない。 メッセージの到着には、有限の時間がかかるので、送信と同時にも受信できな い。)
「a→bかつb→cならばa→cである」
並行性がある：「x→y」も、「y→x」も両方とも偽であることある。 xとyが別々のプロセスで発生して、それらの間でメッセージを交換しない時な ど。 どちらが先に起きたかということを言えない（言う必要がない）
◆時間値C(x)
イベント aについて、次のような性質を持つ時間値C(a) を割り当てる。- a→b ならば、C(a)＜C(b)
- 常に前進する。逆戻りしない。
◆Lamportのアルゴリズム
図(a) 独自のクロックを持つ３つのプロセス。進み方が異なる。
図(b) Lamportのアルゴリズムによるクロックの修正。
２つのイベントの間に必ず１ティック進める。小数点。 同時なら、プロセスＩＤで適当に。
１つの四角には、１つのメッセージだけ。 １つのホストが「同時」に複数のメッセージを送受信することはできない。
この方法でクロックを修正すると、次の性質が得られる。
- 同じプロセスにおいてaがbの前に発生すれば、C(a)＜C(b)となる。
- もしaおよびbが同じメッセージの送信と受信の事象ならば、C(a)＜C(b) となる。
- すべての事象a,bについて、a≠bならば、C(a)≠C(b)。 (total ordering)
■物理クロック
基準- 太陽
- 地球の公転、自転は一定ではない。ふらつきがある。 だんだん１日が長くなってきている。
- 原子時計
- セシウム１３３が 9,192,631,770 回振動。実際の日とずれる。
- UTC (Universal Coordinated Time)。
- 閏秒で調整。
◆物理クロックを合わせる
GPS の普及で、正確な時刻が簡単に取り出せるようになった。 NTP で合わせる。以前の方法。
- Sun rdate
- 時間が逆行することがある
- 時間が不連続に飛ぶ
◆adjtime(2)
進みすぎたクロックを逆行させて戻す変わりに、ペースを落とす。UNIX
int adjtime(const struct timeval *delta, struct timeval *olddelta)
◆Cristianの方法
UTCを持っている時刻サーバに問い合わせる。- m: P が要求を送る。
- t: サーバが応答を返す
- t + Ttrans に合わせる
- 最小値を調べる。
- Tround往復時間の半分で見積もる。
- サーバが落ちている／到達できない
- サーバが狂う
◆The Berkeley algorithm
マスターとスレーブがある。- マスターを１台選ぶ。
- スレーブから情報を定期的に集める。
- 時計の進み具合いの傾向を調べる。
- あまりに大きくずれているものを除外する
fault-tolerant average。 往復時間の誤差。
◆NTP(The Network Time Protocol)
- インターネット上のクライアントに UTC を提供
- 通信が切れても耐える。冗長性を持たせる。
- 高いスケーラビリティ。合わせる頻度を調整。
- 競合に強い。一種の認証技術を含む。
同期方法
- マルチキャストモード
- 手続き呼出しモード
- 対称モード
◆物理クロック同期の応用
- キャッシュの一貫性, HTTP if-modified-since
- メッセージ配信、ネットワーク・ニュース
■相互排除
共有データを他のプロセスが同時に利用しないようにすることを保証する。◆集中システムでの方法
- ロック
- セマフォ
- モニタ
- ランデブ
- Mutex
- Java synchronized
◆コーディネータを使うアルゴリズム
集中システムのエミュレーション。 １つのプロセスをコーディネータとして選ぶ。図。
普通のプロセス：
- 臨界領域に入る前に、コーディネータに要求メッセージを送る。
- コーディネータから許可の応答が得られれば、臨界領域に入る。
- 臨界領域から出る時には、解放メッセージをコーディネータに知らせる。
- 要求メッセージを受け付けた時に、他に利用しているプロセスがいなけ れば、許可の応答を送る。
- 他にプロセスがいれば、待ち行列に入れる。
- 解放メッセージを受け取った時に、待ち行列からプロセスを 取り出し、それに応答メッセージを送る。
- 公正(fair)
- 飢餓が起きない
- メッセージが３種類(要求、応答、解放)
- コーディネータの単一箇所性(single point of failure)
- コーディネータへの負荷の集中
◆分散相互排除
仮定- Lamportのアルゴリズムなどで、論理クロックが同期しており、事象の全 順序が保証されている。
- メッセージ伝送は、信頼性(reliable)がある。
プロセスが臨界領域に入ろうとする時、領域の名前、自分のプロセス番号、現 在時刻のメッセージを用意する。
このメッセージを他のプロセス（自分も含む）に送信する。
あるプロセスがメッセージを受け取った時、次の３つの場合がある。
- 自分が臨界領域にいないし、入ろうともしていないなら、 送信者にＯＫのメッセージを送信する。
- 自分が既に臨界領域にいる時には、応答せず、待ち行列に入れる。
- 自分が臨界領域に入ろうとしていたまだ入っていない時には、 到着したメッセージのタイムスタンプと 他のプロセスに送ったタイムスタンプを比較する。 一番タイムスタンプの低いもの（古いもの）が勝つ。 もし到着した方のメッセージが低いなら、ＯＫを返す。 自分のタイムスタンプが低いなら、待ち行列に入れてなにもしない。
すべてのプロセスからＯＫをもらったら、臨界領域に入る。
臨界領域から出る時には、待ち行列のすべてのプロセスにＯＫを送る。
アルゴリズムの性質：
- デッドロックも飢餓もない
- プロセス数がnの時、メッセージ数は、2(n-1)
- 故障の単一箇所性は、ない（コーディネータのような死ぬとやばいプロ セスがない。）
- しかし、単一箇所ではなくて、n箇所に増えている。涙。
- 遅いプロセスがいたら、そこがボトルネックになる。
- グループ通信プリミティブが必要。
結論：元の集中アルゴリズムよりも、遅く、複雑で、高価で、ロバスト性も小 さい。
分散アルゴリズムの可能性が示されたこと、将来への課題、 ほうれん草やラテン語。
◆トークンリング・アルゴリズム
たとえネットワークがバス型でも、ソフトウェア的にトークンリングを作る。
トークンは、point-to-point のメッセージで送られる。 （グループ通信は使われない。）
隣のプロセスからトークンを受け取ると、自分が臨界領域に入りたければ入る。
性質
- 簡単に正しいことがわかる
- トークンが失われると、再生しなければならない。実際には 失われたことと遅いだけを区別することが難しい。
- プロセスがクラッシュすると、トークンの送信に失敗するという形で 検出できることがある。その時には、クラッシュしたプロセスを リングから外す。
◆まとめ
| アルゴリズム | １回当たりのメッセージ数 | 入る前の遅れ | 問題 |
|---|---|---|---|
| 集中 | 3 | 2 | コーディネータのクラッシュ |
| 分散 | 2(n-1) | 2(n-1) | プロセスのクラッシュ |
| トークンリング | 1〜無限 | 0〜n-1 | トークンの紛失、プロセスのクラッシュ |
■選出アルゴリズム
分散アルゴリズムでは、しばしばコーディネータが必要になる。 どうやって、コーディネータを選ぶか。
- プロセスには、番号が振られている。
- すべてのプロセスは、他のプロセスの番号を知っている。
◆Bully algorithm
コーディネータが応答しないと気が付いたプロセスが起動する。- プロセス P は、ELECTION メッセージを高い番号を持つプロセスに送る。
- もし誰も応答しなければ、P が選ばれ、コーディネータとなる。
- 高い番号のプロセスから１つでも応答があれば、そのプロセスが 引き続き探す(1.にもどる)。
最後に残ったプロセスが、自分がコーディネータだと他のプロセスに知らせる。
ダウンから復帰したプロセスは、この選出アルゴリズムを起動する。
◆Ring algorithm
仮定- 各プロセスは、次のプロセス(successor)を知っている。
- トークンはつかわない。
- コーディネータがクラッシュしていることに気が付いたプロセス は、自分の番号を含む ELECTIOIN メッセージ作成し、次のプロセスに送る。
- 次のプロセスがダウンしていれば、スキップして次のプロセスに送る。 この時、自分の番号をメッセージに付加する。
- メッセージが最初のプロセスに戻ってくる。自分のプロセス番号を 含むメッセージを受け取ると、１週したことがわかる。 一番高い番号のものがねコーディネータとなる。
- コーディネータを知らせるメッセージを、次のプロセスに送る。
- 4. が一週すると終り。
■アトミック・トランザクション
相互排除、デットロックより高いレベルの抽象が欲しい。 特に分散では。集中でも、フォールト・トレランスの実現では必要。
◆トランザクションの意味
商談は、成立するか、しないか。 all or nothing。歴史：１９６０年代、テープの時代。 失敗したら、巻き戻す。
銀行口座間の預金の移動。
- 口座１から出金
- 口座２に入金
◆トランザクション・モデル
仮定- プロセスは、ランダムに故障する。
- メッセージの紛失は、タイムアウトと再送で回復されている。
- 安定記憶(stable storage)。ディスク２台で作る。
◆トランザクション・プリミティブ
- Begin Transaction
- Commit (End Transaction)
- Abort
- Read
- Write
◆特性(ACID)
- Atomic
- 外の世界からみると１つ。中間状態が見えない。不可分。
- Consistency
- 不変量(invariant)を保つ。例：口座間の預金の移動。預金の総額は不変。
- Isolated
- 並行するトランザクションは、孤立している。直列化可能(serializable)
- Durable
- Commit すると永続的。
◆直列化可能(serializable)
注意：Javaの serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で逐次的に実行した時と同じ結果 になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。
◆入れ子トランザクション(nested transactoin)
目的- 効率
- プログラミングの容易さ
◆トランザクションの実装(集中)
- プライベート作業空間。書き換える前にコピーを作り、コピーを更新。
- 先行書き込みログ。更新作業をログに記録して、後で戻せる(rollback) ようにする。
◆プライベート作業空間
全てのデータをコピーすると重たい。- 読み込みではコピーしない
- ファイル全体だけではなく、インデックス(inode)だけをコピーする。シャドー・ブロック。
◆先行書き込みログ(write-ahead log)
実行予定リスト(intentions list)シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶に書き込む。
- トランザクションの識別子
- 古い値
- 新しい値
クラッシュからの回復もできる。
◆トランザクションの実装(分散)
二相コミット(two-phase commit)（二相ロック(two-phase lock)ではない）。２種類のプロセス
- コーディネータ・プロセス、１つ
- サブオーディネート（残りの関連するプロセス）。従属。
- 第１相
- 全プロセスを Commit も Abort もできる状態にする。
- コーディネータは、ログに「準備」と書く。
- コーディネータは、サブオーディネートに「準備」メッセージを送る。
- サブオーディネートは、ログに「準備完了」と書く。
- サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
- コーディネータは、全てのサブオーディネートからの応答を待つ。
- 第２相
- 実際に Commit する。
- コーディネータは、ログに「コミット」と書く。
- コーディネータは、サブオーディネートに「コミット」メッセージを送る。
- サブオーディネートは、ログに「コミット完了」と書く。
- サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
- コーディネータは、全てのサブオーディネートからの応答を待つ。