23章 クリティカルな状態の管理:信頼性のための分散処理_1/2
背景
- プロセスのクラッシュや自然災害など何かしらの影響でシステムを一時止める必要がある。
- それらの影響により、ネットワークの分断は避けることができない。
- 分散合意を理解する事は、アプリケーションの一貫性、可用性の影響を理解するべきです。
分散型システムの基本的な概念
- プロセスのグループのリーダーはどれ?
- グループ内の一連のプロセスは何ですか?
- メッセージが分散キューに正常にコミットされましたか?
- プロセスがリースを保持しているかどうか
- 特定のキーのデータストア内の値は何ですか?
23.1 合意を利用する目的: 分散システムの協調障害
実際の障害を回避するためのアルゴリズムを見ていきましょう
23.1.1 Case1:スプリッドブレイン問題
手法
* レプリケーションされた2つのファイルサーバを一つのセットとする
* 2つのファイルサーバは同じ物理サーバであってはいけない
* それぞれのファイルサーバのペアは1つがリーダでもう1つがフォロワ
* どちらかと更新が取れなくなった場合もう片方を殺すコマンドを発行する
問題
* ネットワークの遅延やパケットの破棄がされた時
* 両方が双方に対してシャットダウンコマンドを打ち合う事になる
23.1.2 Case2:人間の介入が必要なフェイルオーバ
手法
* 高度に断片化されたデータベースシステムには各シャードプライマリが存在
* 別のデータセンタのセカンダリに同期しレプリケートする
* 外部システムが健康状態をチェックし、プライマリにセカンダリを昇格させる
* 逆にセカンダリの健全性を判断できない場合人間にエスカレートする
問題
- データの損失はないが、可用性に悪影響
- エンジニアの操作不可が増加
23.1.2 Case3: グループメンバシップアルゴリズムの障害
手法
* システムには索引、検索を実行するコンポーネントがある
* 開始時にノードは互いのノードを見つけクラスタに追加
* クラスタはリーダを選出し、調整を実行
問題
* クラスタを分割するネットワークパーティションの作りになっていた場合
* 各々がマスタを選出し、書き込み、削除を受け入れ、殺しあう
23.2 分散合意の動作
- 非同期分散合意の問題
メッセージパッシングにおける遅延に上限がない
殺しあう
分散アルゴリズムの考え
- crash-fail: クラッシュしたノードがシステムに戻ることがない考え
- crash-recover: 逆に戻るという考え (クラッシュではなく、遅延、再起動が確率が高いため)
ビザンチン将軍問題: 悪意のある不正メッセージやバグを少数のサーバが送り混乱させる問題
非同期分散合意問題を有限時間内で解決することが不可能
FLP不可能生: ネットワークが信頼できないのであれば処理が進むことを保証できるアルゴリズムはない
分散合意問題に対する最初の解決策は
* LamportのPaxosプロトコルが有名これについて説明していこう
23.2.1 Paxosの概要:サンプルのプロトコル
- それぞれのシステムが各提案をする
- 厳密に順序づけされる(シーケンス番号)
- プロポーザ(提案を行うプロセス)はシーケンス番号をアクセプタに送信する
- 各アクセプたは自分がそれ以上に大きいシーケンス番号を持つ提案を見ていない場合承認する
- プロポーザは必要であればより大きいシーケンス番号でリトライできる
- 過半数のアクセプ宝合意を得たら、プロポーザは値をつけてコミットメッセージを送信し、コミットできる
- ここでポイントなのは、ノード一つ一つは完全は全体のビューを持っていない
- 断片しかない
23.3 分散合意のためのシステムアーキテクチャパターン
- 今までは分散合意という低レイヤの話をした
- これからは、それを踏まえた高レイヤの話をする
23.3.1 信頼性を持つ複製ステートマシン
- 複製ステートマシン: 同一の処理の集合を同一順序で複数のプロセスで実行するシステム
- 合意アルゴリズム上の論理レイヤとして実装されたシステム
- 処理順序は、合意アルゴリズムによってグローバルに順序づけにしたがって実行する
23.3.2 信頼性を持つ複製データストアおよび設定ストア
- 複製データストアは複製ステートマシンの応用例の一つ
- 合意アルゴリズムによって順序づけされた状態で動作するデータストア
問題
* 不整合があってはいけないにも関わらず
* タイムスタンプが意味をなさない→処理速度を落とす事で対処
23.3.3 リーダ選出を利用する高可能性をもつ処理
- 分散システムにおけるリーダ選出問題 = 分散合意の問題
- リーダがいるシステムだと、高可用性を持つサービスでもシンプルなものとして扱える
- リーダだけに命令すれば良いから
23.3.4 分散協調およびロックサービス
- 分散演算処理におけるバリアとは、何かの女権が満たされるまで、
- あるプロセスグループが処理を進めないようにブロックする仕組み
- 分散演算処理に使われる
- バリアは複製ステータマシンとして実装することもできる
- プロセスが死んでも良いように、無制限のロックをしないことが重要
23.3.5 信頼性を持つ分散キュー及びメッセージング
キュー
* 共通のデータ構造、多くのワーカープロセス間でタスク分散する方法として利用
* タスクが正常処理されることを保証する必要があるが、比較的容易にワーカの障害や消失を許容できる
問題
* キューが失われるとシステム全体が動作しなくなること
アトミックブロードキャスト
- 全ての参加者が確実に同じ順序でメッセージを受診する分散システム
- 極めて強力
- これを負荷分散装置として利用する。
queueing-as-work-distribution(分散キューイング)
- キューをロードバランシングの道具として使う
p311
図23-5を見てください
- キューイング、メッセージングシステムは優れたスループットが必要
- しかし、非常に少ない待ち時間はいらない