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

プロセスの一時停止

分散システムにおけるクロックの危険な使い方例
- パーティションごとに 1 つのリーダーをもつデータベース
  - 書き込みを受け付けられるのはリーダーのみ
  - 自分が書き込まれても安全であるとノードが知る方法
    - 例: 他のノードからリースを取得すること
      - リース: タイムアウト付きのロック。ある時点でリースを保持できるのは 1 つのノードのみ。つまり、リースを持っているのがリーダー
      - リーダーでありつづけるには、リースを更新し続けなければならない

while(true) {
    request = getIncomingRequest();

    // ロックの有効期限は別のマシンで設定されたもの
    // 比較されているのは、ローカルクロック
    // 問題1: ローカルクロックの同期がずれているとおかしな結果になる
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }


    if (lease.isValid()) {
        // 問題2: もし仮に isValid メソッドが実行されてから以下の行が実行されるまでに
        // アプリケーションが15秒停止したら、リースの有効期限は切れてしまっている
        // が、リースの有効期限が切れているかどうかの判定は次のループまでわからない
        process(request);
    }
}

アプリケーションスレッドが長い時間停止すると想定するのはおかしい？
- おかしくない
  - ランタイムに実装されている GC は時折実行中のスレッドをすべて停止する
  - 仮想マシンはサスペンド(すべてのプロセスが一時停止され、メモリがディスクに退避される) されうる
    - 仮想マシンを別マシンにライブマイグレーションするときに利用されるときがある
  - パーソナルコンピュータだったら、液晶パネルを閉じるだけでサスペンドされることがある
  - コンテキストスイッチやハイパーバイザーが他の仮想マシンへのスイッチを行うとき
    - スチール時間: ほかの仮想マシンで消費される CPU 時間
  - 同期的なディスクアクセスの場合、ディスク I/O の読み取り完了まで待機される
    - Java のクラスローダーはディスクからの読み取りを行う(ユーザーの指定なしに)
    - しかも、クラスが実際に利用されるまで遅延されるので、ディスク I/O と GC が同じタイミングで起きることさえある
    - ディスクがネットワークファイルシステムやネットワークブロックデバイスなら、ネットワーク遅延の変動にも影響をうける
  - ディスクへのスワッピング（ページング)が起きているなら、ディスクからメモリにページが読み込まれている間スレッドは一時停止される
    - スラッシング: ページングが頻発して、実際の作業を行う時間がほとんど取れない状態になること
  - SIGSTOP シグナル
- 上記の状況はすべて、実行中のスレッドを任意の時点でプリエンプション（一時的に中断）するが、すべてそのスレッド自身は気がつかない
- 単一マシン上のマルチスレッド制御のために使用可能な道具: ミューテックス、セマフォ、アトミックなカウンタ、ブロッキングキュー等
  - これは分散マシンでは使えない。共有メモリが存在しないため。ネットワークを通じてメッセージを送信するしかない。

レスポンスタイムの保証

ソフトウェアが反応する時間に期限が指定されているものがある。これがハードリアルタイムシステム
- Web の世界におけるリアルタイムは、厳密なレスポンスタイムの制約のないストリーム処理とう指す曖昧な言葉
- 組込システムにおけるリアルタイムは、あらゆる環境下で指定されたタイミングの保証が満たされるように注意深くシステムの設計とテストが行われるという意味
- RTOS: 指定された間隔で CPU 時間の割当保証を伴うプロセスのスケジューリングが必要

GC によるインパクトの制限

GC による一時停止を事前に計画された短時間のノードの停止のように扱い、一つのノードが GC を待っている間は、他のノードがクライアントからのリクエストを処理する、という方式もある
- これにはノードの GC による一時停止がもう直ぐ必要になることをランタイムがアプリケーションに通知できる必要がある
ヤング GC だけ行い、Old GC (Full GC) が必要になる前にプロセスを再起動するという方法もある
- 再起動するノードは一つだけにして、トラフィックはそのノード以外に流されるようにすればよい

知識、真実、虚偽

分散システムにおいて他のノードの状態を知るためには、ネットワークを通じたメッセージ交換を行うしか方法はない
分散システムでは、ある前提条件を仮定し、その前提の範囲内で正しく動作することを保証するシステムモデルがある

真実は多数決で決定される

ノードが自身の状況に対して下す判断は常に信じられるわけではない
- 分散システムは単一ノードに依存できない。そのノードはいつ障害を起こして、システムを停止して、回復不能にしてしまうかもしれない
- 多くの分散アルゴリズムは、クオラムに依存する
  - ノード群によって行われる投票。特定のノードへの依存を減らすために、判断を下す際に複数のノードの最小限度以上の投票がなければならない

リーダーとロック

あるものを一つだけにしなければならない状況
- データベースパーティションにおいて、リーダーになれるノードは一つに限られる
- あるリソース、オブジェクトのロックを保持できるトランザクション、クラインアントは一つに限られる
  - あるリソースやオブジェクトへの書き込みが並行に行われるようにするため
ノードの過半数から落ちているとみなされるにもかかわらず自分がリーダとして振る舞い続けようとすると、問題が生じる可能性がある

フェンシングトークン

ロックサーバーがロックやリースを渡すたびに、同時にフェンシングトークンも渡す
- ロックが渡されるたびに増加する数値
- クライアントはリクエストをストレージサービスに送信する際に、フェンシングトークンも含める
  - 増加するフェンシングトークンの順序でのみ書き込みを許すことによってストレージへのアクセスを安全にする
ロックサービスとして Zookeeper が使われている場合、トランザクション ID の zdix やノードバージョンの cversion をフェンシングトークンとして使用できる

ビザンチン障害

分散システムを難しくする問題は、ノードが嘘つくケース
- 例えば、ノードがメッセージを受信していないのにもかかわらず、受信したと主張する場合
- これをビザンチン障害という
- こうした信頼のおけない環境下で合意を形成する問題は、ビザンチン問題という
  - 二人の将軍問題を一般化したもの
ビザンチン耐性をもつとは、一部のノードに不具合があってプロトコルに従わなかったり、悪意を持った攻撃者がネットワークにおいて妨害をしたりしているような状況においても正しく動作し続けられることをいう
ビザンチン耐性を持たないといけないシステム
- 航空宇宙産業に関わるシステム
  - 放射線によって破損し、予測つかない反応を返す可能性がある
- 複数の組織が関わるシステム
  - 例えばブロックチェーンのようなピアツーピアのネットワークは相互に信頼し合っていない関係者が中央集中の認可機関なしにトランザクションが生じたかどうかについて合意する方法

弱い嘘

ハードウェアの問題やソフトウェアのバグのような弱い嘘に対応する仕組みを持たせることに価値はある
- ネットワークパケットに対するアプリケーションレベルのチェックサム
- 値の基本的なサニティーチェック
- NTP のサーバーアドレスのように複数のサーバーとやりとりして誤差を推定する

システムモデルと現実

システムモデル: 分散アルゴリズムが前提としているシステム中で生じると予想されるフォールトの種類の定式化
- タイミングの前提に関する 3 つのシステムモデル
  - 同期モデル
    - ネットワークの遅延やプロセスの一時停止機関、クロックの誤差に限度があることを前提とする
    - ほとんどの分散システムにおいて同期モデルは現実的ではない
  - 部分同期モデル
    - システムのほとんどの場合同期モデルのように振舞うものの、ネットワークの遅延、プロセスの一時停止、クロックの変動が上限をこえることが時々生じることを意味する
  - 非同期モデル
    - タイミングに関するいかなる前提を置くことも許されない
      - クロックを持っていないので、タイムアウトは利用できない
- ノードに関する一般的なモデル
  - クラッシュストップフォールト
    - ノードの障害はただ一つのみしかないという前提
  - クラッシュリカバリフォールト
    - ノードはいつクラッシュするかわからず、いつになるかもわからないもののレスポンスを再び返しはじめるかもしれないという前提をおく
    - ノードはクラッシュがあっても内容を保持する安定したストレージを持ち、メモリに保持されていたものは失われるとみなす
  - ビザンチン（任意）障害
    - ノードは他のノードを欺いたりすることも含めて何をするか全くわからない

アルゴリズムの正しさ

アルゴリズムの正しさは、その性質を記述することによって定義できる
例フェンシングトークンの性質
- ユニーク性: フェンシングトークンを求める二つのリクエストに同じ値が返されないこと
- 単調増加するシーケンス: リクエスト x に対するトークン t_x が返され、リクエスト y に対してトークン t_y が返される。この場合に、y の処理が始まる前に x の処理が終わっていれば、t_x < t_y となる
- 可用性
  - フェンシングトークンを要求し、クラッシュしないノードは最終的にいつかはレスポンスを受けること
あるアルゴリズムが何らかのシステムモデルにおいて正しいとは、そのシステムモデルにおいて生じうるあらゆる状況下においてその性質が満たされること

安全性とライブ性

ライブ性の性質: 最終的にはよいことが生じること。eventually という言葉その定義に含まれることが多い (eventual consistency)
安全性の性質: 何も悪いことが起こらないこと