『データ指向アプリケーションデザイン』8章「分散システムの問題」要約

[データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF%E6%8C%87%E5%90%91%E3%82%A2%E3%83%97%E3%83%AA%E3%82%B1%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%83%87%E3%82%B6%E3%82%A4%E3%83%B3-%E2%80%95%E4%BF%A1%E9%A0%BC%E6%80%A7%E3%80%81%E6%8B%A1%E5%BC%B5%E6%80%A7%E3%80%81%E4%BF%9D%E5%AE%88%E6%80%A7%E3%81%AE%E9%AB%98%E3%81%84%E5%88%86%E6%95%A3%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E8%A8%AD%E8%A8%88%E3%81%AE%E5%8E%9F%E7%90%86-Martin-Kleppmann/dp/4873118700) を読む。

# 注意
これは私のための要約であり、情報が欠落しています。この記事を情報源として使うには不適切です。


# 8章 分散システムの問題
> 結局のところ、エンジニアとしての私たちのタスクは何もかもおかしくなったとしても仕事をこなしてくれる（たとえばユーザーの期待に添った保証を提供する）システムを構築することです。

8章は、前章までの楽観的な戦略から離れて信頼性の低いネットワーク、信頼性の低いクロックなどがどの程度回避できるのか、悲観的な視点で語られる。

## 8.1 フォールトと部分障害
単一のコンピュータで動くソフトウェアは結果が予測しやすい。うまく動いているか、動かないかのどちらか。ハードウェアが正しく動作していれば、同じ処理は常に同じ結果をもたらす（**決定的**）。

しかし、ネットワークで接続された複数のコンピューターで動くソフトウェアの動作は予測しづらい。システムの一部が破損していることがある（**部分障害**）。加えて、複数のノードやネットワークが関わる処理を行うとき、うまく動く場合も予想外の失敗をする場合もある（**非決定的**）。何が成功したかどうか伝えるメッセージもネットワークを介するため、 **知ることができない** こともある。

### 8.1.1 クラウドコンピューティングとスーパーコンピューティング
大規模なコンピューティングシステムの構築方法は次の2つの間に存在する。

- スーパーコンピューターのような、ハイパフォーマンス・コンピューティング（HPC）
- 複数テナントのDCを接続したクラウドコンピューティング

HPCの分野では、演算の途中結果をチェックポイント処理しストレージに保存しておく。もし演算途中でシステムの一部が障害になれば一度クラッシュさせて途中からやり直す。単一ノードのコンピューターに近いフォールト処理になる。

クラウドコンピューティングはそうではない。

- オンラインでなければならない。クラッシュさせてサービスが止めることは受け入れられない
- 安く済むコモディティマシンを使うため障害の発生率は高くなる。スーパーコンピューターなどと違ってハードウェアの信頼性が高くない
- ネットワークトポロジーは高い2分割帯域幅を提供するためにClosトポロジーで構成されることが多い。スーパーコンピューターは、多次元メッシュやトーラスなどの特化したトポロジーを採用
- 規模が大きれば大きいほど、常に何かが故障している前提に立つ必要がある
- 障害を起こしたノードがあっても全体としては処理を継続できるなら運用やメンテナンスについて有益な機能。クラウド環境では、あるマシンのパフォーマンスが悪ければ、単純にそのマシンを破棄して新しいマシンを要求できる
- 地理的に分散している動作環境では、ローカルネットワークよりも信頼性の低いインターネットを経由することになる。スーパーコンピューターの場合、ノードはすぐ近くにある

フォールトはまれだと考えることは、分散システムにおいて賢明ではない。ほとんどあり得ないようなことも含め、生じうるフォールトを考えておくことは重要。テスト環境でそういった状況を人為的に発生させ、何が起こるか見てましょう。

## 8.2 信頼性の低いネットワーク
大量のマシンがネットワーク接続されたシステムをシェアドナッシングシステムと呼び、マシン固有のメモリやハードウェアにはアクセスするにはネットワークを介さなければならない。

DCの内部ネットワークは非同期パケットネットワークになっている。ノードから他ノードへパケットを送信できるが、ネットワークはいつ到達するか、そもそも到達するのか保証しない。

- ネットワークケーブルが抜かれたかも
- ネットワークが輻輳していたり、リモートが過負荷になっていたりして、あとから配信されるかも
- リモートがクラッシュしているかも
- リモートが応答なし状態になっているかも（例：リモートがガベージコレクションによる高負荷）
- リモートのレスポンスがネットワーク上で消失したかも
- レスポンスが遅延配送されるかも

送信側は、パケットが配送されたかどうかもわからない。そしてレスポンスが受信できない理由を知ることは不可能です。通常これらはタイムアウトで対処する。

### 8.2.1 ネットワークのフォールトの実際

中規模データセンターに関するある研究では、一ヶ月あたりおよそ12回のネットワークのフォールトが生じている。その半分では単一のマシンが切り離され、ほか半分ではラックがまるごと切り離されていたことがわかっている。その研究では、冗長なネットワーク機器を追加しても障害発生の主因である人間のミスに対する保護にはならず、フォールトは期待するほど減らなかった。

EC2のようなパブリッククラウドは、一時的なネットワークの不調が頻繁に生じることが知られている。よく管理されたプライベートなデータセンターネットワークのほうが安定した環境になり得る。

たとえネットワーク障害が自分の環境で珍しいとしても、フォールトが生じるということは対処しなければならない。想定外の状況に陥ったソフトウェアはどのような予想外の動きをするか分からない。クラスタがデッドロックに陥り、ネットワーク回復後、リクエスト処理できなくなったり、すべてのデーアを削除してしまったりすることもありえる。

ソフトウェアがネットワーク障害に対してどのように動くのか知っておく必要がある。そのためには、ネットワークの問題をわざと発生させ、システムの反応をテストすることも一つの手段（Chaos Monkey)。

### 8.2.2 フォールトの検出

- ロードバランサーは停止してしまったノードへのリクエスト送信を停止する（ローテから外す）
- シングルリーダーレプリケーションのシステムでは、リーダーに障害が発生したとき、フォロワーがリーダー昇格する

ネットワークは不確実なため、ノードが動作しているのかどうかを知ることは難しい。

- ノードが動作しているはずのマシンに到達できるが、プロセスがない場合OSがTCP接続を拒否する。しかし、受信したリクエストを処理したあとにクラッシュしたら、ノードがどれだけのデータを処理したか知ることはできない
- ノードのプロセスがクラッシュしたものの、OSが動作しているなら、別ノードにクラッシュ通知を送り役割交代できる。HBaseはそういうことをやっている
- データセンターのネットワークスイッチの管理インタフェースにアクセスできるなら、ハードウェアレベルのリンク障害かどうか調べられる。スイッチにアクセスできない環境なら、これはできない
- 接続しようとしているIPアドレスが到達不能だとルーターが判断できるとき、ICMP Destination Unreachableパケットを返してくる場合がある

リクエストが成功したことを確認したいのなら、アプリケーションそのものから適切なレスポンスを受信する以外に選択肢がない。

### 8.2.3 タイムアウトと限度のない遅延
フォールトを検出する唯一確実な方法はタイムアウト。しかし、タイムアウトの長さに単純な答えはない。

- タイムアウトが長ければ、ノードが落ちているとみなされる時間が伸びる。
- タイムアウトが短ければ、落ちていないノードを落ちているとみなすことが増える。

落ちていないノードを、落ちているとみなしたとき、2回動作が実行されてしまうことがある。

パケットの遅延上限が保証されているネットワークを持つシステムを想像してみる。すると、一定時間d以内に配送されるか、ロストするかの2種類になる。また、リクエストの処理時間が必ず一定時間r以内に終わるという制約があったとする。この2つの仮定があれば、タイムアウト時間は、 2d + r が適切であると定まる。
しかし、現実にはこの2つの仮定を満たすシステムはないため、単純に考えられない。

#### 8.2.3.1 ネットワークの輻輳とキューイング
車で移動するとき、移動に要する時間は主に混雑度の割合で変化します。コンピュータネットワークのパケット遅延も同様で、キューイングによって生じることがほとんど。

- 複数のノードが同時に同じ宛先にパケットを送るとき、スイッチはキューイングし、送信先のネットワークリンクに1つずつ送ります。ネットワークリンクが混雑しているとき、パケットはスロットを得るまで待ち時間があります（これはネットワークの輻輳と呼ばれます）。スイッチのキューを埋めてしまうような大量のデータがやってくると、パケットはドロップされ、パケットの再送が必要になります。
- パケットが宛先のマシンに到達しても、すべてのCPUがビジーなら、OSによってキューイングされます。キューが処理されるのは、マシンの負荷次第でどれくらいの時間がかかるか分からない。
- 仮想化された環境では、OSの動作は他の仮想マシンがCPUコアを使うときに、数十ミリ秒、一時的に停止する。この間VMはネットワークから来たデータを処理できないので、やってきたデータは仮想マシンのモニターによってキューイングされる。ネットワークの遅延の変動幅はさらに大きくなります。
- TCPはフロー制御（輻輳回避あるいはバックプレッシャーと呼ばれることもあります）を行います。その際に、ノードはネットワークリンクや受信側のノードを過負荷に陥らせることがないように、自身の送信レートを制限します。そのためデータはネットワークに入る前に送信側でもキューイングされます。
- TCPではラウンドトリップ時間から計算したタイムアウト時間でパケットがロスしたものと見なし、自動的に再送されます。アプリーケーションからは、パケットのロストと再送は区別できず、遅延という事実だけがわかります。

パブリッククラウドや、マルチテナントデータセンターのばあい、リソースは多くの顧客間で共有されており、 MapReduceのようなバッチ型のワークロードは容易にネットワークリンクを溢れさせる。近くの誰かが大量のリソースを利用していれば、ネットワークのち円は大きく変動するかもしれない。そういった場合、タイムアウトは経験則で決めるしかない。

ラウンドトリップ時間の分布を長期間かつ多くのマシンにわたって計測し、遅延の変動の期待値を決定する。そしてアプリケーションの性格を考慮にいれれば、障害検出にかかる時間と短すぎるタイムアウトのリスクとの間で、トレードオフを判断できる。

一定のタイムアウト設定を使うのではなく、継続的にレスポンスタイムとその変動を計測し、観測されたレスポンスタイムの分布に応じて自動的にタイムアウトを調整することも良い。これは、AkkaやCassandraで利用されている、 Phi Accrual failure detector で行える。TCPの再送のタイムアウトも同様に動作している。

### 8.2.4 同期ネットワークと非同期ネットワーク
ネットワーク遅延が一定の最大値以内に収まり、パケットドロップがないと見なせるなら、分散ネットワークははるかにシンプルになる。

旧来の固定回線の電話ネットワークは極めて信頼性が高く、音声のフレーム遅延や通話の断線が生じることはきわめてまれです。電話は、通話者のレイテンシーが常に小さいこと、人間の音声サンプリングを転送するのに必要な帯域です。電話をかけると回路が確立され、通話者間の経路全体に対して固定量の帯域が保証されます。この回路は通話が終わるまで保持される。ネットワークの次のホップ先には、16ビットの領域が予め割り当てられているためキューイングの影響を受けることがない。

エンドツーエンドのネットワーク最大レイテンシーも一定になります。

#### 8.2.4.1 単純にネットワーク遅延を予測できるようにはできないのか？
電話の回路は、それが確立されている間は他者が利用できない。TCP接続のパケットは機会があれば利用可能な帯域を利用する。

データセンターのネットワークや、インターネットはバースト性を持つトラフィックに最適化されている。一定の転送速度で十分なら回路が向いているが、必要な転送速度が大きく変動するならパケット交換方式のほうが向いている。
回路で転送速度を変動させるなら、過不足なく割り当てる必要がある。

## 8.3 信頼性の低いクロック
クロックと時間は重要です。通信は瞬時に行われるものではないため、メッセージが届く頃には時間が進んでいます。各コンピューターは、自身の中にクロックを持っています。このクロックをある程度同期する一般的な仕組みがNTP（Network Time Protocol）です。

### 8.3.1 単調増加のクロックと時刻のクロック
現代のコンピューターは、2つの異なるクロックを持っている。1つは、時刻のクロック。もうひとつは、単調増加のクロック。

#### 8.3.1.1 時刻のクロック
時刻のクロックが行うのは、現在の日付と時刻を返すこと。実時間やwall-clock timeと呼ばれる。Linuxのclock_gettime(CLOCK_REALTIME)は、エポックからの経過秒数を返す。時刻のクロックはNTPと同期されます。したがって、同期のタイミングで以前の時刻にジャンプしたりすることがあるため、消費時間の計測に向かない。

#### 8.3.1.2 単調増加のクロック
タイムアウトやサービスのレスポンスタイムなど、期間を計測するのに向いている。Linuxにおけるclock_gettime(CLOCK_MONOTONIC)がそれ。常にクロックが進んでいくことが保証されている。複数CPUソケットをもつサーバーでは、CPUごとに個別にタイマーを持つことがあるので、CPUをまたいだ比較をしてはいけない。

### 8.3.2 クロックの同期と正確性
時刻のクロックの同期は、NTPサーバーやそのほかの外部時刻のソースを設定する必要があります。しかし、同期の限界があります。

- クロックは温度によって変動します。1日1回の同期で17秒ずれます。
- クロックとNTPサーバーがずれすぎていると、同期が拒否されたり、時刻がリセットされます。アプリケーションから見ると時間がジャンプしているように見えます
- ファイアウォールの設定によってNTPサーバーと同期できない
- NTPとの同期で、ネットワークが輻輳していると、1秒近い誤差がでることがある
- NTPサーバーの時間が間違っている（数時間ずれている）ことがある
- NTPサーバーによってはうるう秒の調整を少しずつ行うサーバーがあるが、動作はそれぞれ
- クロックが仮想化されている仮想マシンの場合、ほかのVMが動作している間数十ミリ秒一時停止する。アプリケーションからみると時間をジャンプしているように見える
- 制御できないデバイス（携帯電話や組み込みデバイス）では、クロックは信頼できない。ハードウェアに手を入れてクロックをずらすユーザーもいる

ヨーロッパの金融商品市場には、UTCに対して100ミリ秒以内に同期を要求しているものもあるが、多大な労力と専門性が求められる（PTPなど）。

### 8.3.3 同期クロックへの依存
頑健なソフトウェアは、不正確なクロックに対する備えが必要。同期されたクロックが必要なソフトウェアを使うのなら、各マシンのクロックのずれを注意深くモニタリングするべき。クロックのずれは、劇的なクラッシュではなく気づかないほどわずかにデータが損失していく。ずれが大きければ、クラスタから外すなどの対応が必要。

#### 8.3.3.1 順序関係をもつタイムスタンプ
複数のノードにわたるイベントの順序付けも気をつける必要がある。ノードそれぞれでクロックがずれていると、予期しない動作をする

![IMG_6211 (1).jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/38967/a0c482c6-6f1b-fced-bc1f-486aac66e7d7.jpeg)


ノード2は、x=1を最新の書き込みだと誤って認識してx=2をドロップすることになる。

この衝突回避戦略は、LWW(last write wins)と呼ばれ、CassandraやRiakのようなリーダーレスレプリケーションで使われている。

「最近」の値を残してほかの値を捨てることで衝突を解決するアプローチは、「最近」の定義がローカルの時刻クロックに依存しているので不正確な場合がある。

イベントの順序付けについては、論理クロックを使うと安全性が高い選択肢になる（p.197 「5.4.4 並行書き込みの検出」参照）。

#### 8.3.3.2 クロックの値には信頼区間がある
マシンの時刻クロックはマイクロ秒やナノ秒の分解のを持っているが、さまざまな要因で10ミリ秒はずれる（NTPサーバーとの同期通信など）。読みだした時刻のクロックを点としてみるのではなく、信頼区間内に時刻があるとみたほうがいい。

ほとんどのシステムには、誤差がどの範囲に収まるか公開されていない。GPS受信機と原子時計は別だが、サーバーから時刻を得た場合、誤差の期待値は分からない。

Google の Spanner の TrueTime API は例外。明示的にローカルクロックの信頼区間を報告する。あり得るもっとも早い時刻と、あり得るもっとも遅い時刻の2値を返す。その間に実際の時刻がある。

#### 8.3.3.3 グローバルなスナップショットのための同期クロック
スナップショット分離レベル（7.2.2 スナップショット分離とリピータブルリード）の最も一般的な実装には単調増加するトランザクションIDが必要。分散したノードで単調増加するIDを発行することはボトルネックを生む。

Spanner は、時刻クロックからのタイムスタンプをトランザクションIDとして使用している。クロックの信頼区間だけ待てば、因果関係が明確になる。各データセンターに原子時計を配備しておよそ7ミリ秒以内の誤差でクロックを同期している。

### 8.3.4 プロセスの一時停止
パーティションごとに1つのリーダーを持つデータベースにおいて、とあるノードが自分が引き続きリーダーであるかどうか知る手法のひとつに、リースがある。リースはタイムアウト付きのロックで、リーダーがタイムアウトまでに更新しなければロックは解除されて、別のノードがリーダーになる。もし、あるノードが自分がリーダーだと勘違いしてしまうと、書き込みを複数許してしまうためデータ一貫性に問題が起こる。

```java
while (true) {
    request = getIncomingRequest();
    // リースが最低でも10秒残っていることを保証する
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew()
    }
    
    if (lease.isValid()) { // この時点でプログラムが停止したら？
        process(request); // ここの処理が長時間かかったら？
    }
}
```

自分がリーダーであるかどうかのロジックでは、予想外の一時中断に注意。一時中断は、GC、ディスクアクセス、ページング、ライブマイグレーション、ディスクへのスワッピング、SIGSTOPなどが考えられるため。

#### 8.3.4.1 レスポンスタイムの保証
多くのシステムは、スレッドやプロセスがどの時間一時停止するか分からない。航空機、ロケット、ロボット、車のようなハードリアルタイムシステムでは、ソフトウェアが反応する時間に期限が指定されている。

リアルタイムシステムの開発は、プロセスのスケジューリングから、最悪ケースの実行時間が保証された関数など厳しい制約がある。加えて、スループットは低くなる可能性がある（p.311 のコラム「レイテンシーとリソースの活用」）。

#### 8.3.4.2 ガベージコレクションによるインパクトの制限
プロセスの一時停止の悪い影響は、ガベージコレクションを調整することで緩和できる。「GCがもうすぐ必要そうです」とノードが別のノードに連絡すると、新しいリクエストを振らないようにしてGCに集中させる工夫ができる。