データ指向アプリケーションデザイン | 第08章分散システムの問題

Tags:

発表者: ファン・ユンホ、キム・ウンテク

分散システムを扱うことは、1台のコンピュータで動くソフトウェアを書くこととは根本的に異なる。
エンジニアは、あらゆることがうまくいかなくても役割を果たし続けるシステムを構築しなければならない。

障害と部分障害

単一コンピュータ環境では、2つの状態を予測できる。
分散コンピューティング環境では、予測できない方法で故障する。これを部分障害という。

単一コンピュータ環境

正常に動作する。
動かない。 -> 「たまたま運が悪い日」のように見えることもあるが、多くは誤って書かれたソフトウェアの結果である。

分散コンピュータ環境

ネットワークで接続された複数のコンピュータでソフトウェアが実行される。
分散システムでは、システムのある部分は正常に動作する一方で、別の部分が予測できない形で故障することも珍しくない。これを部分障害という。
部分障害は非決定的なので扱いにくい。
何かが成功したかどうか分からない場合もある。

クラウドコンピューティングとスーパーコンピューティング

高性能コンピューティング:

数千個のCPUを持つスーパーコンピュータ。
通常、天気予報や分子動力学のように計算コストが非常に高い科学計算作業に使われる。

クラウドコンピューティング:

マルチテナントのデータセンター。
IPネットワーク（Ethernet）で接続された汎用コンピュータなど。

従来の企業向けデータセンターは、この2つの極端な形の中間にある。

スーパーコンピュータで実行されるジョブは、通常、計算状態を耐久性のあるストレージにチェックポイントとして定期的に保存する。
障害が発生すると、最後のチェックポイントから計算を再開する。単一ノードのコンピュータに近い。

分散システムを動作させるには、部分障害の可能性を受け入れ、ソフトウェアに耐障害性メカニズムを組み込まなければならない。
信頼できない構成要素を使って信頼できるシステムを構築する必要がある。完全な信頼性は存在しない。
障害処理はソフトウェア設計の一部でなければならず、障害が発生したときにソフトウェアがどう動作するかを理解していなければならない。

信頼できないネットワーク

本で主に扱う分散システムはシェアードナッシングシステム、つまりネットワークで接続された多数のマシンである。
シェアードナッシングがシステム構築の唯一の方法ではないが、いくつかの理由からインターネットサービスを構築する主な方法になっている。

特別なハードウェアが不要で比較的安価であり、汎用的なクラウドサービスを活用でき、地理的に分散した複数のデータセンターに冗長配置することで高い信頼性を確保できる。
各ノードは他のマシンのメモリやディスクにアクセスできない。ネットワークが唯一の通信手段である。
この種のネットワークでは、ノードは別のノードへメッセージ（パケット）を送れるが、ネットワークはメッセージが到着することを保証しない。

保証されない原因はさまざまである。

リクエストが失われる。
リクエストがキューで待機し、後で送信される。
リモートノードに障害が発生する。
リモートノードが一時的に応答を止めるが、後で再び応答を始める。
レスポンスがネットワーク上で失われる。
レスポンスが遅延し、後で送信される。

送信側は、パケットが送信されたかどうかさえ区別できない。
そのため受信側が応答メッセージを送るが、その応答メッセージも失われたり遅延したりする。
この問題を扱う一般的な方法がタイムアウトである。

現実のネットワーク障害

信頼できるネットワークを作る完全な方法はまだない。
ある会社の管理された環境でも、ネットワーク問題は驚くほど頻繁に発生する。
公開クラウドサービスでもネットワーク障害はよく発生する。
ネットワーク障害がまれであっても、障害が起こり得ることを認識し、ソフトウェアがそれを処理できるよう設計しなければならない。

エラー処理が定義されテストされていなければ、悪いことが勝手に起こり得る。
必ずしもネットワーク障害に耐えられるよう処理する必要はない。
ネットワークが十分に信頼できるなら、問題が起きたときに単にユーザーへエラーメッセージを表示するのも妥当な方法である。

しかし、ソフトウェアがネットワーク問題にどう反応するかを理解し、システムがそこから復旧できることを保証しなければならない。

障害検出

多くのシステムでは、障害のあるノードを自動で検出できなければならない。

ロードバランサは死んだノードへリクエストを送るのをやめなければならない。
単一リーダーレプリケーションを使う分散データベースでは、リーダーに障害が発生するとフォロワーの1つがリーダーへ昇格しなければならない。

タイムアウトと上限のない遅延

タイムアウトだけが障害検出の確実な手段だとすると、タイムアウトはどのくらい長くすべきだろうか。残念ながら簡単な答えはない。

タイムアウトが長いと、ノードが死んだと宣言されるまで待つ時間が長くなる。
タイムアウトが短いと、障害を早く発見できるが、応答が一時的に遅いだけでも死んだと宣言する危険が高まる。

ノードが死んだと宣言されると、そのノードの責務は別のノードへ渡されるため、他のノードとネットワークに追加負荷がかかる。
特に、そのノードは実際には死んでおらず、過負荷のため応答が遅いだけかもしれない。その負荷を他のノードへ移すと、連鎖障害を引き起こす可能性がある。

ネットワーク輻輳とキュー待ち
ネットワークでのパケット遅延の変動は、キュー待ちが原因である場合が多い。

複数のノードが同じ宛先へ同時にパケットを送ろうとすると、ネットワークスイッチはパケットをキューに入れ、ネットワークリンクへ1つずつ渡す。
ネットワークリンクが混雑していると、パケットはスロットを得るまでしばらく待つことがある。これをネットワーク輻輳という。
TCPはフロー制御を行い、輻輳回避やバックプレッシャーによって送信を制限し、過負荷にならないようにする。
TCPはタイムアウト内に確認応答を受け取らないと、パケットが失われたとみなして再送する。

遅延時間に敏感なアプリケーションはTCPの代わりにUDPを使う。

UDPはフロー制御を行わず、失われたパケットを再送しないため、ネットワーク遅延を大きく変動させる原因の一部を取り除く。

UDPは、遅延したデータに価値がない状況で選ぶとよい。

このように、信頼性と遅延変動性の間にはトレードオフがある。

同期ネットワークと非同期ネットワーク
電話ネットワークは極端に高い信頼性を持つ。エンドツーエンドの遅延時間は低くなければならず、声の音声サンプルを送るのに十分な帯域幅が必要である。通話時には回線が作られる。
2人の間の経路全体に沿って、その通話に対して固定され保証された量の帯域幅が割り当てられる。ISDNネットワークは秒間4,000フレームの固定比率で実行される。
この種のネットワークは同期式である。データが複数のルーターを経由しても、キュー待ち問題に悩まされない。

単にネットワーク遅延を予測可能にできないのか。
データセンターネットワークとインターネットが回線交換ネットワークなら、往復時間の最大値を保証できる。EthernetとIPはキュー待ちの影響を受けるパケット交換プロトコルであり、したがってネットワークには上限のない遅延がある。これらのプロトコルには回線という概念がない。

なぜデータセンターネットワークとインターネットはパケット交換を使うのか。瞬間的に集中するトラフィックに最適化されているからである。瞬間的に集中するデータ転送に回線を使うと、ネットワーク容量を浪費し、転送が不必要に遅くなる。TCPは利用可能なネットワーク容量に合わせてデータ転送率を動的に調整する。

タイムアウトに正しい値はない。実験を通じて決める必要がある。

信頼できない時計

このリクエストはタイムアウトしたか。
このサービスの99パーセンタイル応答時間はどのくらいか。
このサービスは過去5分間で平均して毎秒何件のクエリを処理したか。
ユーザーはサイトでどのくらいの時間を過ごしたか。
この記事はいつ公開されたか。
何日何時にリマインドメールを送るべきか。
このキャッシュ項目はいつ期限切れになるか。
ログファイルに残ったこのエラーメッセージのタイムスタンプは何か。

単調時計と時刻時計

時刻時計: 日付と時刻を返す。

NTP（Network Time Protocol）で同期するが、信頼性は高くない。

ファイアウォール。ネットワーク遅延時間、最大1秒程度。うるう秒が発生し、1分の長さが59秒または61秒になる。NTPサーバーでは1日にわたって徐々に処理することがある。モバイル/組み込みデバイスは信頼性が低い。

単調時計: 継続時間の測定に適している。

別の単調時計との比較には意味がない。

同期された時計に依存する問題: 問題の原因は、時計が間違っていることに気づけない点である。

明白なエラーよりも、微妙なデータ損失が起こる。時計がずれているノードは死んだものとして宣言され、取り除かれる必要がある。最後の書き込み勝ち（Last write wins, LWW）。

リーダーなしデータベース: マルチリーダーレプリケーション、Cassandra、Riak。

データベースの書き込みが不可解に消える。この事実を知っておくことが重要である。グローバルスナップショット用の同期時計: Googleの事例。 SpannerとGoogle TrueTime API。

信頼区間を明示的に報告する。最も早いタイムスタンプと最も遅いタイムスタンプを含む区間が重ならなければ、Bは明らかにAより後に実行された。 Spannerは因果性を反映するため、Bを信頼区間の分だけ遅延実行する。 Googleは各データセンターにGPS/原子時計を配置し、約7ミリ秒以内で同期する。

プロセス停止: パーティションごとにリーダーが1つあるデータベースを仮定する。書き込みを受け付けるのはリーダーだけである。

質問: リーダーノードは、自分がまだリーダーであることをどう知るのか。

1つの方法は、リーダーが他のノードからリースを得ることである。特定時点でリーダーは1つだけ存在する。

シナリオ: リーダーであり続けるには、定期的にリースを更新しなければならない。障害が発生した場合、リース更新を止めるため、期限切れ時に別のノードがリーダー役を引き継ぐ。

while (true) {
	request = getIncomingRequest();

	// 常にリースが少なくとも10秒は残るよう保証する。
  if (lease.expiryTimeMillis - System.currentTimeMillis() < 10_000) {
    lease = lease.renew();
  }

  if (lease.isValid()) {
    process(request);
  }
}

問題は何か。

同期された時計に依存している。時刻を確認する時点とリクエストを処理する時点の間に、非常に短い時間しか流れないと仮定している。もし途中でプログラムが停止したらどうなるか。別のノードがリーダーを引き継ぐ。このスレッドが停止していたことを誰も知らせないため、処理を続けてしまう。これは安全ではない。

システムが停止する場合: stop-the-world: GC停止。仮想環境でのsuspend: メモリ内容を保存し、その後再開する。ノートPCでは休止中にも発生する。スレッドのコンテキストスイッチ。遅いディスクI/O操作。 UnixではSIGSTOP（^Z）コマンド。

単一マシンで有用な道具:

ミューテックス（mutex）。セマフォ（semaphore）。アトミックカウンタ（atomic counter）。ロックフリー（lock-free）データ構造。ブロッキングキュー（blocking queue）。

応答時間保証: リアルタイムOS（RTOS）: 航空機、ロケット、ロボット、自動車産業など。

最悪実行時間を明示する。動的メモリ割り当てが禁止されることがある。膨大な量のテストが必要である。そのため、プログラミング言語、ライブラリ、ツールの範囲が厳しく制限される。

知識、真実、そして嘘

ネットワークは信頼できない区間である。結局、部分障害、信頼できない時計、プロセス停止に悩まされる可能性がある。
信頼できるソフトウェアを作る方法に役立つ概念を紹介する。

真実は多数決で決まる

1つのノードだけを見て正常稼働中か判断するのは難しい。

例: full GCで停止したサービスを死んだと判断したが、再び生き返って、それまでの作業を続ける。

代わりに、クォーラム、つまりノード間の投票に依存する。特定ノード1つへの依存を減らすため、決定には複数ノードから最小数の投票を受け取る必要がある。

ノードの過半数をクォーラムとするのが最も一般的である。3台中1台の障害、5台中2台の障害でも正常に動作できる。

リーダーとロック システムが単独で動かなければならないとき:

スプリットブレインを避けるため、データベースパーティションのリーダーになれるノードは1つだけである。
特定のリソースやオブジェクトへ同時に書き込んだり汚染したりすることを防ぐため、そのリソースやオブジェクトのロックを取得できるトランザクションまたはクライアントは1つだけである。
ユーザー名でユーザーを一意に識別できなければならないため、特定のユーザー名で登録できるユーザーは1人だけである。

… 画像 …

フェンシングトークン

… 画像 …

ロックサービスとしてZooKeeperを使う場合、トランザクションIDのzxidやノードバージョンのcversionをフェンシングトークンとして使える。これらは単調増加が保証されるため、必要な性質を持つ。

ビザンチン障害

分散システムの問題は、ノードが「嘘をつく」（任意の障害を持つ、または汚染された応答を送る）危険があると、はるかに難しくなる。このような動作をビザンチン障害（Byzantine fault）と呼び、このように信頼できない環境で合意に達する問題をビザンチン将軍問題（Byzantine Generals Problem）という。一部のノードが誤動作してプロトコルに従わなかったり、悪意ある攻撃者がネットワークを妨害したりしても、システムが正しく動作し続けるなら、そのシステムはビザンチン耐障害性を持つという。これは概して現実的ではないため、認証、アクセス制御、暗号化、ファイアウォールなどの従来の仕組みが、今も攻撃者から保護する主な手段として使われている。

弱い形の嘘

ハードウェア問題、OS、ドライバ、ルーターバグによるネットワークパケットの汚染。
通常はTCP/UDPチェックサムで検出される。
アプリケーションでチェックサムを使って問題を解決する。
公開アプリケーションはユーザー入力を慎重にサニタイズしなければならない。
値の範囲確認、適切なメモリ割り当てのための入力サイズ制限、基本的な正常性チェックを行う。
NTPクライアントでは複数のサーバーアドレスを設定すると役立つ。

システムモデルと現実

システムモデル: システムで発生すると予想される障害の種類を何らかの形で定式化したもの。

タイミング仮定

同期モデル: ネットワーク遅延、プロセス停止、時計誤差のすべてに上限があると仮定する。
部分同期モデル: システムはほとんどの時間は同期システムのように動作するが、ときどきネットワーク遅延、プロセス停止、時計ドリフトの上限を超えるという意味である。
非同期モデル: このモデルでは、アルゴリズムはタイミングについていかなる仮定もできない。

ノード障害

crash-stop障害: ノードがある瞬間に突然応答を停止すると、その後そのノードは永久に使えず、決して戻ってこないという意味である。
crash-recovery障害: ノードはある瞬間に死ぬことがあるが、未知の時間が経った後にはおそらく再び応答し始めると仮定する。
crash-recoveryモデルでは、ノードはメモリ上の状態を失うが、死んでもデータが残る安定したストレージ、つまり不揮発性ディスクストレージがあると仮定する。
ビザンチン（任意）障害: ノードは前節で説明したように、他のノードをだましたり欺いたりすることを含め、まったく何でもできる。

アルゴリズムの正しさ
性質を記述し、常に満たされるか確認する。

例: フェンシングトークン

一意性: フェンシングトークン要求が同じ値を返さない。
単調なシーケンス番号: 要求xがトークンtxを、要求yがトークンtyを返し、yが開始する前にxが完了していたなら、tx < tyを満たす。
可用性: フェンシングトークンを要求し、死ななかったノードは最終的に応答を受け取る。

安全性（safety）と活性（liveness）

安全性
- 安全性性質が破られると、その性質が壊れた特定の時点を指し示せる。たとえば一意性が破られれば、重複したフェンシングトークンを返した特定の操作を識別できる。
- 安全性性質が破られた後は、その違反を取り消せない。すでに壊れた状態である。
活性
- 活性性質は逆に働く。ある時点を特定できないこともある。たとえばノードが要求を送ったがまだ応答を受け取っていないかもしれない。しかし、将来その性質を満たせるという希望は常にある。

安全性: 常に満たされることを要求する。すべてのノードやネットワーク全体が故障しても、誤った結果を返してはならない。

活性: 警告は許容される。ネットワーク分断があるなら、分断期間に上限を置く。

現実への対応
分散システムの正しさを考えるうえで非常に有用だが、限界は明確である。

crash-recoveryモデル: ノードが死んでもデータは残ると仮定する。
- ディスク汚染。
- ハードウェア障害。
- 誤った設定によるデータ消失。

コンピュータサイエンスとコンピュータ工学の違い:

実際の実装では、不可能だと仮定していたことが起こる場合を処理しなければならないことがある。
- printf(“너라서 짜증나”)
- exit(666)

それでも抽象システムモデルは重要である。

現実システムの複雑さ -> 推論できる管理可能な障害集合を抽出する -> 問題を理解し体系的に解決する。

まとめ

ネットワークパケットはいつでも破損したり遅延したりする可能性がある。
ノードの時計は時刻を信頼できない。
プロセスは実行中にstop-the-worldに遭遇する可能性がある。

部分障害は分散システムの明確な特徴である。

検出からして難しさが始まる。タイムアウトは使うが、これはネットワーク障害とノード障害を区別できない。
厳密なリアルタイム応答保証とネットワーク遅延制限を置くことは可能だが、コストが非常に高く、リソース使用率は低くなる。

次章は、すべての分散システムの問題に対処する解決策である。

データ指向アプリケーションデザイン | 第08章 分散システムの問題