データ志向アプリケーションデザイン読書メモ

RDSMSにおいてはBツリーが伝統的に強い

最初に発明されて以降ほぼずっと使われ続けている

やはりアルゴリズムとデータ構造こそが正義というのは100回繰り返しても足りない

データはコードよりずっと長い期間生きる

コードは変えることは難しくないがアルゴリズムとデータ構造は一度決定すると大きく変えることは難しい

エンコーディング

言語特有のシリアライゼーションなどは言語に強く依存し前方互換性や後方互換性が考慮されていないので基本的には使うべきではない

JSONやCSV, XMLなど広範な需要をサポートするフォーマットは完璧ではないにしろ（型や効率性の面）、落とし所として広い利害関係内で合意を得られる最小公倍数的なフォーマットであるためその非効率さや足りない機能面などを無視しても使われており、それは合意を得るということが実質的に最も難しいことであるためその目的を最も果たしているとも言える。また合意を得ている上では結局のところフォーマットというのは何でも問題ない

特にCSVなどは改行や列中のカンマ、数値と文字列の区別のなさなどの不完全な点はある

JSONはすべてのレコードにフィールド名が含まれるなど効率性の面では非効率、コメントを入れることができない

前方互換性、後方互換性を考慮してエンコードすること

具体的には古いアプリケーションから新しいアプリケーションで書き込まれたデータが読めること、また新しいアプリケーションから古いコードで書き込まれたデータが読めること

Thrift、Protocol Buffer、Avroといったスキーマを持つバイナリフォーマットはコンパクトで効率的なエンコードが可能かつ前方互換性、後方互換性を考慮したセマンティクスが定義されていることなどから自社の同じデータセンター内での通信のような合意を得るコストが比較的少ない通信などにおいて使用することが可能

非同期のメッセージングパッシング（メッセージブローカーやアクター）

第二部 分散データ

データベースを分散したい理由

スケーラビリティ：WriteやReadを複数のマシンに分散する

耐障害性：１台に障害が起きても他のマシンが代理を努めてくれる

レイテンシ：ユーザに最も近いロケーションからレスポンスを返すことができる

最もシンプルなスケールの方法は垂直スケールすなわちスケールアップ

ただコストの上昇が性能の向上に対して比例以上になっていくことで、コスト効率はあまりよくない

水平スケールアーキテクチャ（シェアードナッシングアーキテクチャ）は独立したマシンにおいて実行される。ただ水平スケールには制約とトレードオフももちろんある。利用できるデータモデルの表現力に制約が生じてしまうこともある。場合によってはシングルスレッドの単純なプログラムの方が１００以上のコアのクラスターより高い性能を発揮することもある。

大まかにシェアードナッシングアーキテクチャでデータを分散させる方法は２つある

レプリケーション

同じデータを複数のマシンで保持する方法

パーティショニング

データセットをパーティションと呼ばれる小さなサブセットに分割する方法（シャーディングとも呼ばれる）

２つを組み合わせてパーティショニングしたそれぞれのパーティションを更にレプリケーションしたレプリカを増やすことも可能

レプリケーションは現在ではROWベースでのレプリケーションがよく使われる。ステートメントベースでのレプリケーション（INSERT文やUPDATE文などそのままレプリカでも実行する方法）は非決定的な結果（NOW()）を返す可能性や自動インクリメントのIDなどで問題になるケースがある

VoltDBではトランザクションを決定的なものにするという制約を課すことでステートメントベースのレプリケーションを使用している

WAL（Write Ahead Log）の転送によるレプリケーションはMySQL、PostgreSQL、Oracleで行われる。常に追記される変更内容のバイナリ形式のログを転送することによってフォロワーにおいても完璧にリーダーの変更内容を再現出来る。

WALに含まれるのはどのディスクブロック中のどのバイトが変更されたかといった詳細のため、ストレージエンジンと密接なつながりを持つ

バイナリ形式であるためレプリケーションプロトコルのバージョンやソフトウェアのバージョンが異なると同じログを使えない場合がある

WALの転送によるレプリケーションの場合バージョンのミスマッチは許されていないことが多く、バージョンのアップグレードにはダウンタイムが伴う

ストレージエンジン（Innodb等）のログはストレージエンジンの物理的なデータ表現に依存するため、行ベースでの論理ログレプリケーションが存在する。ストレージエンジンの物理的な表現から独立しているという意味で論理ログ

RDBMSの論理ログはテーブルへの書き込みを記述するレコードの並びで行単位

MySQLのbinlogはこの形式

論理ログの利点としてはストレージエンジンの違いやバージョンの違いを抽象化出来ること

複数のレプリカが存在するかつクエリが完全にランダムにバランシングされる場合、ラグの存在するフォロワーレプリカのラグの差により、追従済みのレプリカと追従していないレプリカにバランシングされ、追従済みに存在するデータが存在しないかのような挙動になる場合がある。

そのため同じクライアントは同じフォロワーにリクエストが行くようにクエリをルーティングすると一貫性のある結果を参照出来る可能性が高い

そのためクライアントの何らかのIDをもとに一意にリクエスト先のフォロワーを決定するアルゴリズム（名前忘れたけどリングに対象のレプリカを追加していく方法）を使うとよい

パーティショニングする場合書き込みが別個に行われるため、書き込みの順序と読み取りの順序が前後しレプリカから読み取りした時にあたかも先の書き込みが後から書き込まれたかのようにレプリカをReadしたクライアントから見える場合がある

これを防ぐためには一貫性のあるプレフィックス読み取りが必要になる

防ぐ方法としては互いに因果関係のある書き込みを必ず同じパーティションに書き込むことでレプリケーションも同じ順番であることを保証すること

マルチリーダーレプリケーション

得られるメリットより加わる複雑さの方が大きいので一つのデータセンター内でマルチリーダー構成を使う意味はほとんどない

複数のデータセンターに分散される場合、それぞれのリーダーが自分の書き込みを他方のリーダーノードに送信しつつそれぞれフォロワーノードを持つ

ただ大きなデメリットとして同じデータが別々のDCで編集された場合変更がコンフリクトしてしまうこと

他にもマルチリーダーレプリケーションは後付けで追加された機能のため、整合性制約やトリガー、インクリメントのキーなどで問題になりがちなので通常は可能であれば避けるべきものである

マルチリーダー構成が妥当な場合はオフラインアプリケーション（カレンダーアプリやノートアプリなど）でオフラインでも操作が発生するようなアプリケーションの場合

オフライン時はローカルで読み取りと書き込みを行いインターネットが復帰した時にローカルでの変更を送信する必要があるため、それぞれのクライアントがリーダーのように振る舞う

概念的にはマルチDCでのマルチリーダーレプリケーションと全く同じである

CouchDBなどはマルチリーダーでの構成を念頭に置いて設計されているためこの種のアプリケーションに向いているとのこと

並行性

並行性を定義する上で厳密な時刻は問題にならない

単純にそれぞれがお互いのことを認識していないのであれば、それらが生じた物理的な時間がどうであれ、２つの操作は並行しているとされる

結果的には離れた場所で起きた２つの出来事は生じた時間間隔がその距離を光が移動する時間よりも短いならお互いに影響を及ぼすことはできないという物理学上の原理から物理学的に現象の並行性が生じているといっていい

微分していけば微細な時間レベルでどちらかが先ということは定義出来るかもしれないが、光が移動する時間より小さい差であればお互いがどちらが先に操作を行ったのかは認識出来ない

基本的にレプリケーションは本質的な難しさを抱える

というのはレプリケーションを使った時点で分散システムとなりネットワークの遅延やネットワークの障害、ノードの障害や復帰といったことに対応出来る必要があるため

なのでシングルノードで対応出来るのであれば避けるべきだと思う

どうしてもRead性能が足りなくなった時の最終手段的に使うものでスケールアップで対応出来るならコスト効率は悪くてもスケールアップで対処するべき問題は多い

分散システムを運用するコストに比べればスケールアップするコストの方が低い場合は多々ある

Riakのようなマルチマスターでのクラスタリングを前提としてsiblingやバージョンベクトルによる衝突の解決など衝突を自動的に解決するデータ構造を組み込んだシステムで解決出来るならそうするべきだと思う

リーダーレスレプリケーション

複数のノードに同じ内容の書き込みを同時に送信し、古いデータを持つノードを修正するための読み取りを複数のノードから並列に行う方法

w + r > n となるように設計する

w = 書き込みノード

r = reader node

n = sum of nodes

MySQLによるシングルリーダーでのレプリケーションをスケールさせるのはそのアプリケーションのシンプルさや保守性と引き換えに運用難易度が高い

まとめ

シングルリーダーレプリケーションはシンプルだがレプリケーションの遅延によりデータが巻き戻るように見えるような現象が発生する場合がある

それぞれ以下のような一貫性モデルがある

read-after-write

ユーザは自分自身が投入したデータを常に読み取ることが出来る

モノトニックな読み取り

ある時点のデータを見たらそれ以前のデータを読み取ることは出来ない

一貫性のあるプレフィックス読み取り

ユーザは例えば質問とその質問への回答を適切な順序でいったように、適切な因果関係を保持した状態でデータを読み取ることが出来る

マルチリーダー、リーダーレスについても同様に並行性に本質的な難しさを抱えており、一見して理解が難しいアルゴリズムなどで解決などしている

トランザクションの欠如に対して常にアプリケーションコードをプログラマが書かなければならなくなるより、トランザクションの過剰な利用がボトルネックとなってくる場合に対処するようにしたほうが良いと信じています - Spanner: Google's Globally-Distributed Database 2012 James Corbett他

実際にトランザクションを使わないで陥るエラーに対処するよりはトランザクションを過剰に利用するくらいで何かがボトルネックになった時に対処するほうがマシなことがよくある

トランザクションファースト

分離レベル

read commited

スナップショット分離（snapshot isolation)

直列化可能性（serializability)

NoSQLのような分散データベースで過剰に語られるトランザクションがパフォーマンスを犠牲にしているという主張とデータベースベンダーからトランザクションによる保証は価値あるデータを持つ重要なアプリケーションに欠かせない要求であるという主張もどちらも誇張が含まれる

serializability 分離はパフォーマンス上の問題があり実際に利用されることは少ない。データベースによっては実装していないものすらある。Oracleにも直列化可能性分離レベルはあるが実際にはスナップショット分離として実装されている

ACID特性について

原子性（Atomicity）

一連の書き込みの中でエラーが起こった場合Rollbackして書き込むか何も起こらなかったかのように振る舞う性質。オール・オア・ナッシングの保証。

分離性

並行に実行されているトランザクションがお互いに影響しあわないことを保証する性質

例えばあるトランザクションの複数の書き込みのうち一つが行われたに他のトランザクションがReadしたとしても途中の状態が読み取られないことを保証する。他ユーザから見ても複数の書き込みが書き込まれたか全く書き込まれていないかとしか見えないことを保証する

read-modify-writeやcompare-and-set型の操作は軽量トランザクションなどとも呼ばれるが厳密には通常呼ばれる意味でのトランザクションではない

compare-and-setの例：

code:sql

UPDATE wiki_pages set content = 'new_content'

WHERE id = 1234 AND content = 'old content';

分散データストアではそもそも複数オブジェクトのトランザクションを実装していないものも多い

パーティションをまたいで実装することが難しいなどの理由

serializability分離はパフォーマンス上負荷がかかるので実際には問題があるものの弱い分離レベルが利用されることが多い

そのため財務データを扱うならACID特性のあるデータベースを使わないというわけではなく、そういったデータベースでさえバグの発生を防げるとは限らないので並行性の問題にはどういったものがあるか、それを回避するためにはどうすればよいのかを理解しなければならない

最も基本的なRead Commitedレベル分離

以下の２つの性質を保証する

データベースから読み取りを行った際に見えるデータはコミットされたもののみであること（ダーティリードが生じない）

トランザクション途中の書き込みが他のクライアントから見える場合「ダーティリードが存在する」と呼ばれる

データベースへの書き込みを行う場合、上書きするのはコミットされたデータのみであること（ダーティライトが生じない）

read commited分離はECサイトのようなよくある同じ商品を購入しようとするような書き込みの競合のようなケースに対して有益

ただread commitedは同じカウンタのインクリメントのようなレース条件は防いでくれない。コミットされた後に行われたデータの更新自体はダーティライトではないため

ダーティライトを避けるためには行レベルロックを使う方法が一般的

行またはドキュメントのロックを取得してから更新する対象のオブジェクトを更新する方法。他のトランザクションがロックを取得したい場合ロックが解放されるまで待つ必要がある

Snapshot分離

あるトランザクションが読み取るデータはそのトランザクションが開始した時点でのデータベースのスナップショットというもの

例えばDBのバックアップなどはバックアップ開始時点から終了までの間に書き込みがある場合リストア時点で整合性がなくなってしまう可能性があるためスナップショット分離が必要

他にも分析的なクエリでDBのスキャンをする場合その時点でのスナップショットでなければ実行時刻によって整合性のない結果が返るかもしれない

バックアップや分析用クエリなど長時間実行される読み取りだけを行うクエリで有益な分離レベル

ElasticsearchのPoint In time APIなどはこういったスナップショット分離を提供してくれる

MySQL InnoDB, PostgreSQL, Oracle, SQL Server等で広くサポートされている

スナップショット分離では通常書き込みロックが使われる

読み取りはロックを必要としない

読み取りが書き込みをブロックすることはなく書き込みが読み取りをブロックすることもない

そのためスナップショット分離中も通常通り書き込みを処理しながら同時に長期間に渡って実行される読み取りクエリをロックの競合を発生させることなく処理出来る

あるオブジェクトについて複数のバージョンを並べて管理する手法をMVCC（マルチバージョン並行性制御）と呼ぶ

read commited分離だけでよければ１つのオブジェクトにつきコミットされたバージョンとコミットされていないバージョンの２つだけを保持していれば問題ないがスナップショット分離においては長期間のクエリになる場合があるため複数。read commited分離のバージョン管理を複数個に拡張したような形

read commitedはクエリごとに個別のスナップショットを使い、スナップショット分離ではトランザクション全体に渡って同じスナップショットを使うという違い

データベース的には削除クエリを実行したとしても即時物理的に削除されるわけではなく削除マーカーが設定され、参照するトランザクションがなくなった時点でガベージコレクタが適切なタイミングで削除マーカーがつけられたレコードを削除して領域を解放する

Update処理は内部的には削除と作成に変換される。つまり削除マーカーがつけられた行と新しい値で新規に作成される行となる

トランザクションがデータベースから読み取りを行う場合、そのトランザクションから見えるオブジェクトと見えないオブジェクトを決定するためにそのトランザクションのIDが使われる。

つまりトランザクションID 10が書き込みを行っているトランザクションではID 11はIDが異なるためID 10がコミットするまではコミット後のオブジェクトを見ることは出来ない

スナップショット分離はスナップショット分離トランザクションが開始した時点で他に発生しているすべてのトランザクションのリストを作成し、そのトランザクションの書き込みは後にコミットされるものでもすべて無視する

スナップショット分離トランザクション開始後に発生したトランザクションの書き込みもコミットされているか否かに関わらずすべて無視する

Copy-on-Writeで更新が発生した時に新規にInsertを行い参照する親ページのポインタを変えるだけというのはappend only型のアプローチで非常にシンプルになる

古いものは削除マーカーが付けられGCされる

スナップショット分離はMySQLやPostgreSQLにおいてはリピータブルリード、Oracleではserializableと呼ばれる

これはSQL標準にスナップショット分離という概念が無いため

read-commitedとスナップショット分離は主に読み取りのみのトランザクションとそれに並行して書き込みが行われる場合にその該当トランザクションから一貫してデータが見えるかということを保証するもので、並行した書き込みにおける更新のロストなどには関知しない

カウンタや残高を並行して更新するような場合がよくありがちなケース

またJSONドキュメント中の一部を更新するなどReadの後にWriteが必要なケースなど

アトミックな書き込み操作

並行した書き込みに対する対処方法

MongoDBはJSONドキュメントの一部をアトミックに更新するような操作を提供している

ORMでは自動的に生成されるクエリではこの手のアトミックなクエリにならなかったりするので都度生成されるクエリがアトミックになっているかは確認は必要

明示的なロック

DBの組み込みのアトミックな操作で不十分な場合アプリケーション側で明示的にロックするという方法がある

読み取りロックすればそのトランザクションが終了するまでは並行に読み取りを行うことは出来ない

第８章　分散システムの問題

おかしくなるかもしれないことは必ずいつかおかしくなる

「結局の所、私達エンジニアとしてのタスクは何もかもがおかしくなったとしても仕事をこなしてくれる（例えばユーザの期待に沿った保証を提供する）システムを構築することです」

内部的なフォールトが生じた場合、コンピュータは間違った答えを返すよりは完全にクラッシュするほうが望ましい

ErlangのLet it crash的な思想にも通じる

下手に状態を保持するくらいなら壊れるがままにする方が良い

単一のコンピュータであれば振る舞いは単純でおかしくなるかおかしくならないかの２つ

常に正しく演算処理を行うというのは最初のデジタルコンピュータの設計上の目標でもあった

分散システムのある部分において何らかの形で破損している状態を部分障害と呼ぶ。問題は部分障害が非決定的なことで、ネットワークが関わる処理を行おうとする場合、うまく動作することもあれば、予想外の失敗が生じることもありやってみるまで分からないということ。またネットワークがレスポンスを完全にロストすれば成功したかどうかさえ知ることが出来ない

というのはネットワークは結果を完全にロストするかもしれないし、そもそも到達したかどうかさえレスポンスが返ってくるまで分からない

回線が同期ネットワークではなく非同期ネットワークとして設計されてる故

スイッチのキューがパンクしたかもしれないし、マシンのCPU時間を他プロセスによって専有されておりパケットが処理出来ないかもしれないし、スイッチのキューが専有されているかもしれない

エンドツーエンドで回線が確保される同期ネットワーク（ISDN等電話ネットワークなど）では予め決められた容量が確保され帯域保証される

ISDNで4000フレーム/秒

帯域が確保出来た時点で通話が開始される

非同期ネットワークでは事前に帯域を確保せずそれぞれのクライアントが送信したパケットを都度帯域に割り当てる

ある意味ネットワークも量子論的な不確定性を抱えているといえるかもしれない

レスポンス（観測結果）はレスポンスを観測するまで非決定的で観測した時に状態が確定する

GCがなぜ好まれないか

Stop-the-world形式でのGCはすべてのスレッドを一時的にしろ長いときには数分にも及ぶ場合がある停止を行うことがありその間に現在時刻などクロックに依存する処理（リースの取得など）をしていた場合期待しないリーダーに書き込みが行われるなど整合性を失う原因となる処理を実行してしまう思わぬフォールトを生むから

スレッドが停止することを想定していないコードが存在する場合GCが思わぬエラーを生む

仮想マシンがサスペンドやライブマイグレーションなどで別ホストへ移行するなどですべてのスレッドがそれとは知らずに停止する場合がある

クロックに依存するコードがある場合こういった場合に思わぬフォールトになる

Javaのクラスローダーはクラスファイルのロードを最初にそのクラスが利用された時点まで遅延させるので、ディスクIOが発生する場合どの程度遅延が発生するか予想が難しい

実際にはファイルシステムがEBSなどネットワーク越しのファイルシステムだったりするとネットワークの遅延に影響を受ける場合もある

ディスクへのスワッピングが可能な場合ほとんどの時間をディスクからメモリにプログラムを読み出す時間に費やされる場合もある（スラッシング）

分散システムには共有メモリはなく、信頼できないネットワークを通じてメッセージを送信するしかないためマルチスレッドプログラミングにおけるスレッドセーフを保証するための道具（セマフォや、アトミックなカウンタ、ブロッキングキュー等）が存在しない

自身が停止していたことさえ該当スレッドは知らないうちに外界のノードは時間が進んでいるということさえ想定しなければいけない

感想：前に読んだSFで、デジタル化された精神が自身で時が停止していたことさえ気づかないけど主観的な時間では連続的になっているというような話があった（イーガンだったか）。それを思い出した

航空機やロボット、車等スレッドの停止が許されないようなシステムもある

WebにおけるリアルタイムとはサーバがクライアントにPush形式でデータを送信したり、サーバが厳密なレスポンスタイムの制約なしにストリーム処理するという程度でソフトリアルタイムになる

GCを緩和する方法の一手段としてGCを予めスケジュールに組み込み、GCが近くなったらそのノードへのリクエストをルーティングしないようにランタイムがアプリケーションに通知、上位のリクエストルーターで調節し別のノードへリクエストが行われるようにし、その間にGCを行うというものがある

金融取引システムなどGCが大きな影響を与えるかもしれないシステムにおいてこの手法を使っているものがある

デプロイにおけるローリングアップグレードのような考え方

分散システムが本質的に難しいのはシェアードナッシングにより共有メモリバスやディスクが存在しないため信頼性のないネットワーク上でメッセージを送信しないといけないこと

「システムに関するこういった議論は哲学に近いものです。すなわち、システム内で真、あるいは偽であると分かっているのはどういうことなのでしょうか？認識と計測に信頼が置けないのであれば、その知識に対してどれだけの確信が持てるのでしょうか？ソフトウェアシステムは、原因と結果のように物理的な世界において期待されるような法則に従うべきなのでしょうか？」

それに対する方法としてシステムをモデル化出来、システムモデルにしたがって実装することによりアルゴリズムによってわずかな保証を提供するだけでも、その上に信頼性のある動作を実現できる

具体的にはロックサービスに対してロックを要求する時にロック取得と同時に単調増加するフェンシングトークンを返してもらい、書き込み時にフェンシングトークンをリクエストに含めることで同一オブジェクトのロックに対してリース期間後にロックを取得した別のスレッドが存在し、スレッドが停止していたとしてもトークンの増加の整合性が確認出来るのでデータの破損を防げるというもの

航空機システムのような非常に高い信頼性が求められるシステムではビザンチン耐性が備わっている必要がある

Webシステムのような任意のユーザがネットワークにメッセージを送信することが出来るようなシステムにおいても悪意のある攻撃者を想定しなければいけない

8.4.3 システムモデルと現実

タイミングの前提に関してシステムは3つに分かれる

同期モデル

ネットワークの遅延や一時停止、クロックの変動が一定の範囲内に収まることを意味する。リアルタイムシステムで求められる性質であるがとてもコストが高くソフトウェアの性能に大きな制約がつく

部分同期モデル

システムがほとんどの場合同期モデルのように振る舞うものの、ネットワークの遅延やプロセスの一時停止、クロックの変動が上限を超えることが時々生じるという意味。わずかでも超えることがあるということはそれに依存したバグが発生する可能性があることを意味するので非同期モデルとあまり変わらないといえば変わらない

非同期モデル

タイミングに関していかなる前提も許されないモデル

クロックさえ持っていないためタイムアウトを利用することも出来ない

ノードに関するモデル

クラッシュストップフォールト

ノードの障害はクラッシュしかないという前提を置く

クラッシュリカバリフォールト

ノードはクラッシュするがいつかは分からないもののレスポンスを返すまでリカバリするかもしれないという前提を置くモデル

ビザンチン障害

ノードは他のノードに対して虚偽のメッセージを意図的に送る可能性もあるモデル

現実的には部分動機モデルとクラッシュリカバリフォールトの組み合わせでモデリングされる組み合わせが最も有益なモデル

8.4.3.1 アルゴリズムの正しさ

アルゴリズムの正しさ（correctness）はその性質（properties）によって定義出来る

あるソートアルゴリズムは出力リスト中の異なる任意の2つの要素について左側の要素は右側にある要素よりも小さい、というような定性的性質

同様に分散アルゴリズムも求める性質を書き出すことによってその正しさを定義出来る

8.4.3.2 安全性とライブ性

単調増加するトークンのような安全性に関わる性質がある一方、トークンを要求するノードいつかはトークンを含むレスポンスを受け取ること、といった可用性に関わる性質はライブ性といえる

安全性は何も悪いことが起こらないこと、ライブ性は最終的にはなにか良いことが生じることと定義することも出来る

抽象的なシステムモデルは現実のシステムの複雑さを理論的に管理可能なフォールトの集合へと純化し、システマティックにそれらの問題を理解して解決するのに役立つ

アルゴリズムが正しいことはそれらの性質が何らかのシステムモデルにおいて常に保たれることを示すことによって証明出来る

9 章 一貫性と合意

フォールトトレランス（耐障害性）を持つ分散システムを構築するためのアルゴリズムとプロトコルの例についての章

耐障害性を持つシステムを構築する最善の方法は有益な保証を持つ汎用的な抽象概念を見出し、それらを実装し、アプリケーションをその保証に依存させること

トランザクションと同じであるシンプルな保証をするアルゴリズムを実装しそれにアプリケーションを依存させる

トランザクションという抽象概念、つまり失敗するか失敗しないかという二択の一連の処理が存在するかのようにアプリケーションも振る舞うように依存することで、ACID特性（原子性、永続性、分離性）を獲得出来る

重要なのはそういった抽象概念を見出すこと

9.2 線形化可能性

線形化可能性（linearizability) は原子的一貫性（atomic consistency), 強い一貫性（strong consistency), 即時一貫性（immediate consistency), 外部一貫性（external consistenc) と呼ばれることもある

基本的な発想はクライアントから見るとデータのコピーが1つしかなくそのデータに対するすべての操作がアトミックであるようにシステムに見せるということ

これが保証されれば、実際には複数のレプリカが存在しているとしてもアプリケーションはそのことを考慮しなくてもすむようになる

Writeしたデータが常に最新であるように振る舞うことから最新性の保証（recency guarantee) とも言える

9.2.2.2 制約及びユニーク性の保証

銀行口座の残高がマイナスにならないことや在庫数以上の商品を販売しないこと、同じ映画館の席を予約しないことを保証したい時に線形可能性のあるアトミックなcompare-and-set操作が必要になる

9.2.3.1 線形化可能性とクオラム

Dynamoスタイルのレプリケーションを行うリーダーレスなシステムは線形可能性を提供しないと考えるほうが安全

パフォーマンスの低下を許容するならDynamoスタイルのクオラムを線形化可能にすることは可能だがパフォーマンスの低下やCompare-And-Set操作に関しては実装出来ないため

具体的には読み取りの際にアプリケーションに結果を返す前に読み取り修復を同期的に行い、書き込みの際に書き込みの送信前にノードのクオラムの最新状態を読み取る

9.2.4 線形化可能にすることによるコスト

9.2.4.1 CAP定理

線形化可能なあらゆるデータベースにはCAP定理の制限がある

アプリケーションに線形化可能性が必須で、レプリカがネットワークにより切り離されている場合、切り離されているレプリカはリクエストを処理出来ない

アプリケーションに線形化可能性が必須ではない場合、ネットワークで他のレプリカから切り離されていてもそれぞれのレプリカが独立でリクエストを処理出来るような方法で書き込みを受け付けることが出来る（マルチリーダー）

ネットワークの問題が生じていても利用出来るが線形化可能ではない

したがって線形化可能性を必要としないアプリケーションは、ネットワークの問題に対する耐性を高く出来る

Eric Brewerが2000年にCAP定理として名付けた

このトレードオフ自体は分散データベースの設計者により1970年代から知られていた

CAPは2000年代移行のNoSQLが普及するきっかけとなった定理とも言える

CAPはしばしばC（Consistency）、A（Availability）、P（Partition tolerance）の3つの中から2つを選択することとされるがこれは誤解を招く

ネットワークの分断はフォールトの1種なので、選択に関係するようなものではなく、好むと好まざるに関わらず生じる

もし完全なネットワーク（フォールトが一切生じない、遅延しない）があるとしたらシステムは一貫性（線形化可能性）と完全な可用性をどちらも提供出来る

ネットワークが不完全であるからこそ線形化可能性か可用性のどちらかを選択しなければならない

厳密な形式的な定義でのCAP定理自体は1つの一貫性モデル（線形化可能性）と1種類のフォールト（ネットワーク分断）だけ

ネットワークの遅延やノードが落ちる等については形式的なCAP定理は言及しない

それゆえにCAP定理は歴史的には大きな影響力はあるが、システム設計における実際的な価値はほとんどない

9.3.1.1 因果律に基づく順序と全順序の違い

全順序（totally ordered）である場合はすべての操作が一つの直列な流れの上で行われているかのように振る舞う。線形化可能なシステムは全順序である

因果律があるようなシステム、つまりあるBという操作の前にAが行われるというようなhappens-before関係が存在するそれらの間に順序関係があるということになるが、並行に行われていれば比較不可能。つまり半順序になるため因果律は全順序ではなく半順序を定義する。操作によっては順序が決まることもあるが、並行操作のように比較不可能な場合があるため全順序ではなく半順序

Gitのバージョン履歴のように依存関係のグラフは並行に作成されある時点でマージされて一つの流れに解決される。

意図しない解決をしてしまう

そのためtrunkベースでの開発のようにタイムラインを1つにことで、多数のブランチが並行に歴史を持ってしまい解決の際に多大なコストを払うことより頻繁なpullやfetchにより解決するソリューションを取る場合もある

9.3.1.2 因果律の一貫性よりも強い線形可能性

多くの場合線形化可能性を必要としているように見えるシステムに本当に必要なのは、因果律における一貫性だけでありこれは線形化可能性よりも効率の良い実装が可能

近年結果整合性に近いパフォーマンスや可用性を持ちつつ因果律を保持するタイプのデータベースの研究が進んでいる

プロダクションまで到達したものは多くはなく、克服すべき課題はまだまだある

9.3.1.3 因果律における依存関係の補足

データベースの全体にわたる因果律の依存関係の追跡のためバージョンベクトルなどが使える

9.3.2 シーケンス番号の順序

シーケンス番号やタイムスタンプを使ってイベントの順序付けが出来る

こういった論理クロックは全順序を提供する

複数のノードがシーケンス番号を独立して生成する場合因果律との一貫性を持たないシーケンス番号を生成してしまう場合がある

9.3.2.2 ランポートタイムスタンプ

因果律に対して一貫性を持つシーケンス番号を生成する方法としてランポートライムスタンプがある

ノードが複数ある場合でも全順序を提供する

それぞれのノードはカウンタを持ち、操作ごとにシーケンシャルにインクリメントしていき、それとは別にノードIDを持つ

カウンタ値とノードIDの組をタイムスタンプとする

（counter, node ID)

カウンタ値は大きい方が大きいタイムスタンプとなり、カウンタ値が同じであればノードIDを比較しノード値が大きい方が大きいタイムスタンプとなる

具体的にはすべてのノードとクライアントが、過去に見た最大のカウンタ値を追跡し、その値をすべてのリクエストに含めるというもの

あるノードが受信したリクエストもしくはレスポンスに含まれるこの値が、そのノード自身のカウンタ値よりも大きかった場合そのノードは自身のカウンタ値をその最大値に置き換える

最大のカウンタ値がすべての操作においてやりとりされている限り、全順序と因果律における一貫性を保証する

つまり因果律の依存関係をタイムスタンプに含めることで全ての操作の順序を一貫したものにすることが可能になっている

順序関係をアルゴリズムで強制的に各操作に含めているとも言えるかもしれない

ランポートタイムスタンプの全順序からは2つの操作が並行して行われたのか、それとも因果律における依存関係があるのかを知ることは出来ない

ランポートタイムスタンプは全順序を決めることは出来るがそれは結果的な話で、全ノードの操作を収集して初めてこういった順序があったと分かる

そのためあるユーザ名で並行して別々のユーザがその名前のユーザを作成しようとした場合、リクエストが届いた時点で即時に判定するというようなことは出来ない

同じユーザ名を全順序中でその操作より先に要求していたノードが他にはないことが確実になってはじめて、その操作が成功したと安全に言える

全順序の確定時期という概念

9.3.3 全順序のブロードキャスト

全順序ブロードキャストはメッセージが配信された時点で順序が確定するということ

既に配信されたメッセージの前に後からメッセージを挿入することは出来ない。そのため、全順序ブロードキャストはタイムスタンプによる順序付けよりも強力といえる

もし全順序ブロードキャストを行えるのであれば、その上に線形化可能なストレージを構築出来る

あるユーザ名をユニークに取得したいという実装をしたければ、自身でログに追記しユーザ名取得に関する最初のメッセージが自分だった場合取得出来ることになる

書き込みにおける線形化可能性は保証出来るが読み取りにおける線形化可能性は保証しない

すなわちこれらのどれかが解決できれば他の問題も解決出来るということ

9.4 分散トランザクションと合意

合意が必要な状況

leader election （リーダーの選出）

シングルリーダーレプリケーションを行うシステムではどのノードがリーダーかを書くノードが合意していないとフェイルオーバーした際にスプリットブレイン状態になってしまう

複数のノードでトランザクションを実現させる分散トランザクションを実現させようとすると複数のノードでトランザクションの結果について合意していなければならない

つまり全てのノードが中断もしくはロールバックするか、すべてのノードがコミットするかしなければならない。これをアトミックコミット問題とも呼ぶ

合意の不可能性

あるノードがクラッシュするリスクがあるなら常に合意に達することが出来るアルゴリズムは存在しないということを証明した

クロックやタイムアウトも全く使えないというようなモデル

クロックやタイムアウトを使うことが出来るのなら合意は解決可能になる

9.4.1 アトミックなコミットと2相コミット（２PC )

2相コミットは複数ノードにまたがるアトミックなトランザクションを実現するためのアルゴリズムで分散データベースにおける古典的なアルゴリズム

1. アプリケーションがまずコーディネータに対しトランザクションIDを要求する

2. アプリケーションは各参加者で単一ノードのトランザクションを開始し、それぞれのトランザクションに対してグローバルでユニークなトランザクションIDを添付する

3. すべてのRead/Writeはいずれかの単一ノードトランザクション中で行われる

この段階でなにか問題が生じたらコーディネータもしくは参加者のいずれかが中断出来る

4. アプリケーションのコミットの準備が整ったらコーディネータが複数のノードにまずフェーズ1として準備リクエストを送信する

この段階でリクエストのいずれかが失敗もしくはタイムアウトしたらコーディネータはトランザクションIDに対する中断のリクエストを全参加者に送信する

リクエストを受信した参加者はyesとレスポンスを送信した時点でそのトランザクションを中止する権利を放棄することになる

5. コミット出来るというレスポンスが全ノードから返ってきてコミットの準備が整っていることを示した場合に実際にフェーズ2でコミットリクエストを送る

まずコーディネータは自身のトランザクションログにそのトランザクションを書き込みそれ以降にクラッシュした場合にも判断が分かるようにする（これをコミットポイントと呼ぶ）

トランザクションログを書いた後に実際にコミットリクエストを各参加者に送る

コミットすると判断しディスクに書き込んだ時点で後戻りは出来ない

この間に参加者がクラッシュしたらトランザクションはその参加者がリカバリした時点でコミットされる

2PCが分散データベースにおいて原子性を保証できるのはこういった帰還不能点を設定していることによる

コーディネータがクラッシュした場合参加者が出来ることはコーディネータがリカバリしてコミットを完了することを待つことのみ

このようにコーディネータを単一の責任のポイント＝単一ノードのアトミックな処理とみなすことで分散DBにおける原子性を保証する

ただこのためコーディネータが単一障害点となるためAvailabilityはどうしても低くなる

9.4.2 分散トランザクションの実際

分散トランザクションは他の方法で提供することが難しい安全性を保証している一方、パフォーマンス上の問題から多くのクラウドサービスでは分散トランザクションが引き起こす運用の問題上分散トランザクションを実装しないという選択をしている

MySQLの分散トランザクションは単一ノードのトランザクションに比べて10倍以上遅いという報告もある

パフォーマンスコストの大部分はクラッシュ時のリカバリに必要なディスクへの強制的なWrite（fsync）の増加とネットワークのラウンドトリップの増加

データベース内部の分散トランザクションであれば特定のプロトコルに従うプロトコルを実装するだけでよいのでバージョンさえ合えば問題ないが、ヘテロジニアスな分散トランザクション、つまり実行しているソフトウェアが複数ある中での分散トランザクションは多くの課題がある

9.4.2.1 exactly-onceなメッセージ処理

あるメッセージを承認するという処理とそのメッセージの実際の処理内容をデータベース上でトランザクションとして処理することでその後何回同一のメッセージが配信されたりリトライされたとしてもexactly-onceな処理として安全に処理出来る

メールの配信などに利用出来るかもしれない

メッセージは任意の回数再配信出来るが、送信回数自体は1回のみとしたいような場合そのメッセージを承認するという書き込みと送信したという書き込み（副作用）をトランザクションにする

ただメール送信という副作用はメールサーバに2PCが大抵無いので難しいかもしれない

分散トランザクションは障害を増幅する傾向がある

9.4.3 耐障害性を持つ合意

合意とは「複数のノードが何かについて同意すること」

映画館の同じ席を予約しようとした場合や同じユーザ名を取得しようとする場合、相互排他的にどのクライアントが勝者となるかを決めるために合意アルゴリズムを利用できる

合意は通常以下のように形式化される

1つ以上のノードが値を提案（propose）し、合意アルゴリズムはそれらの値の中から1つを決定（decide）する

合意アルゴリズムは以下の性質を満たす必要がある

一様同意（uniform agreement)

2つのノードが異なる決定をしない、つまりすべてのノードが決定に同意していること

整合性（integrity)

2回決定しているノードがいないこと

妥当性（validity)

ノードが値ｖを決定したら、ｖを提案しているノードが存在すること

終了性（termination）

クラッシュしていないノードは最終的に何らかの値を決定すること

合意のシステムモデルはクラッシュしたノードは突然消えたり、決して戻ってこなことを前提としている

2PC（2 Phase commit)は終了性を保証できない

クラッシュしたノードがリカバリすることを前提としているため

どんな合意アルゴリズムでも過半数のノードが動作していなければ合意に達することが出来ないとういことが数学的に証明されている

そのため終了性要件を満たすためにはクラッシュしているノードは半数以下でなければならない

耐障害性を持つ合意アルゴリズムとしてViewstamped Replication, Paxos, Raft, Zabがある

これらのアルゴリズムは実際には上記の同意、整合性、妥当性等の個別の要件は利用していない。その代わり値の並びを保証する全順序ブロードキャストアルゴリズムとなっている

各ノードが次に送信したいメッセージを提案（propose）し、全順序の下で配信する次のメッセージを決定する

よって、全順序ブロードキャストは複数回にわたって合意が行われることと等価

9.4.3.2 シングルリーダーレプリケーションと同意

シングルリーダーレプリケーションはすべての書き込みをフォロワーに適用するという点では全順序ブロードキャストと同じようなもの

シングルリーダーレプリケーションは運用者がリーダーを決定するという独裁的な合意アルゴリズムのバリエーション

処理をすすめるために人間による介入が必要になるため合意の終了性要件を満たしていない

9.4.3.4 合意の限界

合意アルゴリズムは分散システムにおけるブレークスルー

安全性の性質を持ち込み不確実性のあるシステムにおいて耐障害性を保てる（少なくともノードの過半数が動いている限り）

また全順序ブロードキャストを提供し、線形化可能でアトミックな操作を実装できる

ただデメリットもある

ノードが決定を下す前に提案に対して投票するプロセスは同期レプリケーションの一種

パフォーマンスが犠牲になる

ノード数は障害を起こしても問題ないノード数nに対して、2n + 1となり1個のノードが障害を起こすことを許容するなら3ノード、2ノードまでの障害を許容するなら5ノード必要となる

ネットワークの局所的な障害などでリーダーの移動が発生し続けるなどのエッジケースがある

ZookeeperはGoogleのChubbyを参考にしている

線形化可能なアトミックな操作を提供しているためZookeeperのAPIを利用すれば耐障害性のある分散システムを一から作る必要がなくなる

データベースのパーティショニングなどにも利用される

ノードを追加した際のリバランシングなどをアトミックに操作するため

また分散システムを一から構築し数千ノード間で合意を得るために大量に投票を集めたりしなければいけない場合と比べてZookeeperのノード自体の数を5ノード程度に抑えてその中で合意を得ることが可能になるので効率のいい合意操作が行える

ただ上でも述べた通り合意を耐障害性のある方法で得ることは基本的な仕組みとしては同期レプリケーションとなり、非同期ではないため秒間数百件といったようなパフォーマンスは得られづらい

数分や数時間に1件などで変化する値のようなものを想定したアルゴリズムではある

Apache CuratorのようなZookeeperの生のAPIを抽象化したツールもある

またZookeeperやetcd、Consulはサービスディスカバリとしても使える

9.4.4.3 メンバーシップサービス

Zookeeperはメンバーシップサービスの研究の長い歴史の一部とみなせるかもしれない

1980年代までさかのぼり、航空管制システムなど信頼性の高いシステムを構築する上で重要なものだった

OLTPとバッチ処理、ストリーム処理の違い

一言で言うと入力データが有限か有限でないか

OLTPやストリーム処理は有限ではなく、バッチ処理は有限のため適用出来るシステムモデルに大きな差が生じる

11章 ストリーム処理

12章 データシステムの将来

まとめ

実は2018年に翻訳された当時に話題になっていたので買っていたけど最初の導入部分が少し冗長で積んでいて今更読んで内容の濃さに驚いた。もっと早く読んでればよかった

データを扱うアプリケーションに関してこれほど広範囲に網羅している本もなかなかない

個別のテーマについては薄く紹介する程度に書かれてる箇所も多いので理解を深めるために参照文献を見ていくといいかもしれない

参照文献のリストだけでも膨大なので余裕で2、3年ぐらいかかりそうなボリューム

2回3回と読み直したい