読んだので個人的なメモを残す。
exhaustiveなメモではない。

第5章レプリケーション

データのレプリケーションのメリット

(データをユーザーの近くに保持でき)レイテンシーが下げられる
可用性(= ノード障害への耐性)を上げられる
(読み取りクエリを処理するマシンをスケールアウトさせられ)スループットを高められる

ほぼ全てのデータベースは、変更をノード間でレプリケーションするアルゴリズムとして以下のいずれかを使っている。

シングルリーダー
マルチリーダー
リーダーレス

5.1 シングルリーダー

postgreSql, mysql mongoDB, kafka, rabitMQなどで使われている。

レプリカのうち

１つはleader (= master = primary)
- writeを受け付ける。新しいデータをローカルストレージに書いたあと、フォロワーに送信する(=レプリケーション)
- readを受け付ける。
残りはfollower (= read replica = slave = secondary = hot standby)
- readを受け付ける。

レプリケーションは

同期的
- フォロワーでデータ更新がコミットされるのを確認してからマスターで更新がコミットされる。
- 👍️(書き込みしたクライアントから見て？)フォロワーが持っているデータは常に最新でありリーダーとの一貫性が保障される
非同期的
- 👎️クライアントに成功が返された場合でも書き込みの永続性は保障されない。
  - 例えば、書き込んだ直後のリーダーに障害が発生し、その更新が反映された他のレプリカがfail overによってリーダーになった場合。
- フォロワーが多い場合やフォロワーが地理的に分散している場合に広く利用される。

📝同一DB内でも、フォロワーによって同期型と非同期型を選択することができる。
一般的なのは、複数のフォロワーのうち１つに対して同期型レプリケーションを行い、その速度が低下したら別のフォロワーのいずれかを同期型にする。
💡ロックを取ることなくDB全体のスナップショットを取ることは可能。MySQLだとサードパーティーツールのinnobackupexが必要。
💡DBの状態にはバージョンにIDがふられている。PostgreSQLであればログシーケンス番号。MySQLではbinlog coordinate。

ノード障害への対応

フォロワーの障害
- (障害 = クラッシュして再起動や、リーダーとのネットワークが一時的に切れる)
- 👉️ フォロワーは自力でキャッチアップリカバリーによって復活する。(保持しているデータ変更のログを使う + リーダーにキャッチアップ)
リーダーの障害
- 👉️フェイルオーバーを行う。
  - (リーダーはリーダーとして復活することはない)
  - フォローのいずれかをリーダーに昇格させる
  - フォロワーたちはデータ変更を新しいリーダーから受信しはじめる
- 自動的なフェイルオーバーと、管理者による手動のフェイルオーバーがある。
  - 自動だとフェイルオーバーの検知でフォースポジティブが発生しうる。(システムの高負荷やネットワークの問題でタイムアウトが発生した場合に、これがリーダーレプリカの障害と見なされる可能性がある)

自動的フェイルオーバーについて

プロセス
1. リーダーに障害が起きたことの確認。タイムアウトを利用して検知することが多い。
2. 新しいリーダーの選出。
  - 最もふさわしい候補は、それまでのリーダーのデータ変更に一番最近まで従事していたレプリカ
  - 選出方法は
    - 残っていレプリカによる選出で行われる
    - コントローラーノードが指定することもある。
3. システムの再設定
  - クライアントの書き込みを新しいリーダーに送信するように設定
  - フォロワーは新しいリーダーを新しいリーダーから受信する(ように設定？)

フェイルオーバーで発生しうる問題

非同期のレプリケーションを使用しており、元のリーダーが障害後に復活した際、新しいリーダーとの間でレースコンディションが発生しうる。
スプリットブレイン(複数のレプリカが自分をリーダーと信じている状態)が発生しうる。

リーダーベースのレプリケーションの手法

ステートメントベースのレプリケーション
- リーダーは書き込みリクエストをログに記録し、そのステートメントログをフォロワーへ転送する。
- 👎️ NOW() や乱数などの非決定的な関数を呼ぶステートメントは破綻を呼ぶ。
- 👎️インクリメントするidがテーブル内に振られている場合、実行順序が影響する。→ レプリカ上でも実行順序を合わせる必要がある→複数のトランザクションをserializableに実行する必要が生じる
write-aheadログの転送
- リーダーがログファイルへの書き込みのかたわら、ネットワーク経由でそれをフォロワーにも送信する
- 👎️リーダーとフォロワーのストレージフォーマットを統一する必要がある → 場合によりデータベースのアップデート時にダウンタイムが発生する。
論理ログ(rowベース)を使用したレプリケーション
- レプリケーション用の独立したログフォーマットのログ(論理ログ)を使用する
- 👍️論理ログのフォーマットは後方互換性を保ちやすい
- 👍️論理ログのフォーマットは外部のアプリケーションがパースしやすいので、外部に送信してそこで使用(= 変更データのキャプチャ)できる
トリガーベースのレプリケーション
- アプリケーション側のコードを使用する。
- 例えば、
  - データベースのログを読み取るツールを使う
  - RDBのstored procedureを使い、別のテーブルにデータの変更を書き込む。これをフォロワーが読む。
- 👍️柔軟性が高い。
- 👎️オーバーヘッドが大きい。バグが発生しやすい。制約が生じやすい。

レプリケーションラグにまつわる問題

分散している以上完全に同じタイミングで複数のノードの更新を行うことはできない。結果として、問題が発生する。

以下、非同期レプリケーションのレプリケーションラグが起因で発生する問題を３つ紹介する。それぞれに関してリーダーベースで非同期レプリケーションの場合の保障方法を紹介する (いずれもアプリケーション層で実現方法。これらの煩わしい保障方法からアプリケーションを解放するのが、トランザクションの存在意義である。)

問題① あるクライアントがwriteしたあとにreadをした際、自分がwriteしたはずのデータが見れない。
- 原因: read時にまだ、followerレプリカに変更が反映されていたい。
- 保障:これが発生しないように保障されている状態を「read-after-write consistencyが保たれる」と呼ぶ。リーダーベースで非同レプリケーションの場合の実現方法は、
  - 自分が更新したデータのreadは leaderレプリカから読み取る
  - データの更新時刻を記録するようにする。最後の更新時刻から例えば一分以内に行うreadはleaderレプリカから行う
  - followerレプリカのレプリケーションラグをモニタリングし、一分以上leaderから遅延しているレプリカからはreadを行わない。
  - clientは最後の書き込みのタイムスタンプを保持する。そのタイムスタンプまでの更新が反映済みのレプリカからしかreadを行わない。
問題② あるクライアントによってあるレコードがwriteされたとする。この時、他のあるクライアントにとって1回目のreadではAが見えるが、2回目のreadではAが見えない。
- 原因: 1回目と2回目で異なるfollowerレプリカを見ており、前者には変更が反映されているが後者には変更が反映されていない。
- これが発生しないように保障されている状態を「monotonic readが保障される」と呼ぶ。リーダーベースで非同レプリケーションの場合の実現方法は、
  - あるユーザーのリクエストによるread先のレプリカを常に同じものにする。例えば、user id のハッシュ値によって決める。
問題③ 他のクライアント(たち)によってA→Bの順にレコードが書かれたとする。あるクライアントのread時にAは含まずBだけがreadできてしまう。
- 原因: leaderレプリカが複数ある、例えばシャーディングされたDBで問題になる。最初にreadしたfollowerレプリカにはAの変更が反映されていなかったが、後者にはBの変更が反映されていた。
- これが発生しないように保障されている状態を「consistent prefix が保たれる」と呼ぶ。リーダーベースで非同期レプリケーションの場合の実現方法は、
  - 因果関係のある書き込みは同一のleadレプリカに対して行う。

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

📝 単一データセンター内ではメリットが少ないので使用されない。

leaderレプリカの増加により、scalabilityは改善
(複数ロケーションによる)latencyの改善はなし
(複数ロケーションによる)availabilityの改善はなし

📝マルチリーダーレプリケーションでも、同期レプリケーションだとメリットは少ない

👉️ 同期的に衝突を検出したいのが目的なら、シングルリーダーレプリケーションを使うべし。

マルチデータセンターでは

各データセンター内で、leader１つとfollower複数
各leaderへのwriteは以下へレプリケーションされる
- 同一データセンター内のfollowers
- 他のデータセンターのleader (ここで別の変更が行われていた場合、書き込みの衝突⭐の解決が必要)
👎️ 以下と合わせて問題になりうる。よって可能であれば避けるべきと見られることも、
- 自動インクリメントのキー
- DBのトリガー
- DBのconstraint
使用例として、オフラインでも使用できるカレンダーアプリ。デバイス内、リモートサーバー内のそれぞれにリードレプリカを持っていると解釈できる。

衝突に関して(自分の考え)それぞれのリードレプリカが更新のヒストリーを持っていて、他のリーダーから届いたレプリケーションが、以下の全てを満たすときに、衝突、といえそう？？(これを実現するのがバージョンベクトルか？)

自分の持っていない更新コミットを含んでいる
自分は受け取ったレプリケーションが持っていない更新コミットが詰まれている
それらのコミットが同じレコードに関するものだったり、アプリケーションロジック上片方しか許容できない

更新にタイムスタンプだけを持たせるだけだと衝突を検知できない気がする。

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

使用例
- dynamo db を含むdynamo スタイルのDBは使用している。
- cassandra (dynamo dbに影響を受けた)
適する状況
- 高可用性と低レイテンシーが求められ、時折古いレコードが読まれることが強要される場合。
- マルチリーダーレプリケーションと同様、マルチデータセンターでの使用に適している。
実装方式は色々
- 🟢クライアントが書き込みを自分で複数のレプリカに送信する
- coordinator nodeが各レプリカに送信する

本書では🟢の形式のリーダーレスレプリケーションのアルゴリズムである「クオラム書き取り/読み取り」を説明していた。
これは、 N個のレプリケーションがある際に、wとrを w + r > N を満たすように設定する、というもの。

書き込み時には、最低w個のレプリカへの更新が反映されることを必須とする
読み込み時には、最低r個のレプリカからの読み取りを必須とする

なお、一部のレプリカのみに反映された更新は以下のように全レプリカへ反映される

読み取り修復
- = クライアントが複数のプロセスから読み出した際、最新の書き込みバージョンを持つレコードの値をそうでないレコードの値に上書きする
半エントロピー処理
- = バックグラウンドプロセスによるレプリケーション。

wとrの設定に関して、

例えば読み込みヘビーなら、w=N, r=1にすると良い。
N < w+r の時、レイテンシーが低くなる。かつ可用性が高まる。
N <<< w + rの時、古い値を読み取ってしまう可能性が高まる。-> 衝突の解決が複雑になる？

並行な書き込みについて

定義 (⚠️これは自分で考えた)
- 「あるレコードXに対して二つの書き込み操作があり、X->AとX->B である時、(AのヒストリーにBが含まれていない) && (BのヒストリーにAが含まれていない) の時にこれらは並行な書き込みと言える(?)
- 並行な書き込みの解決方法
- レプリカが一つの場合
  - サーバー側とクライアント側のそれぞれで、「あるレコードのバージョンヒストリー」を保持しておく。クライアント側で書き込み時にはまずサーバー側のバージョンヒストリーを読み出す。もしもそこに自分にないバージョンが含まれていることを検知したら、次の書き込みバージョンは所謂マージコミット的な変更になる。
    - マージのアルゴリズムは、色々。アプリケーション層での実装例としては、
      - タイムスタンプを見て新しいバージョンを採用。
      - 変更を比較して和集合を取る。(appendの変更しかない場合に有効)
- レプリカが複数の場合
  - バージョンベクトルを使用するなどする。

📝cassandraはdynamo dbに着想を得ているリーダーレス

第６章パーティショニング

パーティションする目的はスケーラビリティである。(それぞれのノードは独立に自分の持つパーティションに対してクエリを実行できる)

この章で説明することは以下。

データに対するインデックス付け
ノードの追加とその際のリバランシング
DBのリクエストを適切なパーティションにリクエストするルーティング

📝一部のパーティションにレコードが偏っている状態をSkewと呼び、そのパーティションをhot spotと呼ぶ。

インデックス付けの方法

キーの範囲に基づく
- 👍️ そのキーによるrangeに対するスキャンが容易になる
- 👎️アクセスパターンによってはホットスポットが発生する
- ダイナミックパーティショニングを行う(❌パーティション数固定はだめ。それぞれのパーティションの範囲を事前に決めると、偏りが発生することがある)
キーのハッシュ値の範囲に基づく
- ⚠️ハッシュ値のmodで切るのはNG (リバランシングの負担が極めて大きくなる)
- 👍️ホットスポットを避けれる
- 👎️rangeによるqueryはすべてのパーティションに送られ、結果をマージする必要がある
複合キーを作成する
- 以下。

パーティションとセカンダリーインデックス

複合プライマリーキーは
- プライマリーキーのハッシュ値によりパーティションを決定。
- 各パーティション内で、セカンダリーキーによるインデックスを貼る(ローカルインデックス)
  - 通常セカンダリインデックスは特定の値を検索する方法

この結果、

同じプライマリキーのレコードは同一パーティション内にある
パーティション内でセカンダリーキーによるrangeのqueryのパフォーマンスが良い。

しかしながら、セカンダリーインデックスによる検索の読み取りは、全てのパーティションに対するscatter & merge になる。
この対策方法は、

セカンダリーキーでパーティショニングされたインデックスを保持する。
- 👍️ セカンダリーキーによる検索時に、どのパーティションを見に行く必要があるか分かる。
- 👎️ 書き込み時にこのインデックス更新するために低速で複雑になる
  - なお、Dynamo DBではこのインデックス更新は非同期で行われる。

パーティションのリバランシング

負荷をクラスタ内のあるノードから別のノードへ移行するプロセスを説明する。

🟢リバランシングの戦略

パーティション数を固定する。
- ノード数よりはるかに多くのパーティションを作成しておき、１つのノードに複数のパーティションを割り当てる。あるノードの負担が大きくなったら新たにノードを増やし、既存の全てのノードからパーティションを盗む。
  - リバランシングの最中は古いパーティションに対する読み書きが行われる
  - 👎️ パーティションを増やせないため、データ量増加によりパーティションのサイズが巨大になりうる。すると、リバランシングやノード障害からのリカバリの負担が大きくなる。
dynamic partitioning
- パーティションのサイズが閾値より大きくなれば分割。小さくなれば他とマージする。
- 👍️ パーティション分割、マージしたあとも、キーの範囲は
ノード数に比例するパーティショニング
- ノードごとのパーティションの数を固定する。データが増えたら新しいノードを加え、既存の全てのノード内のパーティション(それぞれ１つ？)のレコードを盗んでくる？？？

🟢リバランシングの運用

自動のリバランシング
- 👎️ 例えば、あるノードが過負荷でリクエストのレスポンス処理速度が落ちたとする。結果、他のノードがこのノードが落ちたと見なしてリバランシングを開始した場合、さらなる負荷がかかる。
手動のリバランシング
- (処理のどこかに人を介在させるのがおすすめ)

🟢リクエストのルーティングはサービスディスカバリを利用する。
あるキーのレコードが含まれるパーティションがどのノードに含まれるかの解決)を行う。
このためのマッピングの置き場は

クライアント側
ルーティング層
各ノードそれぞれ

いずれにせよ、これらは、Zookeeperなどのクラスタ管理サービスが保持するマッピングを参照する。各ノードはリバランシング時に、これに対して更新を送信する。

第７章トランザクション

長々まとめたが、P288のまとめがよくまとまっている。

トランザクションが提供する安全性の保証は

Atomicity
- commit all .or. abort al
- DBの特性
Consistency (一貫性)
- アプリケーションが満たさなければならない不変性。
- アプリケーションによって異なる。例えば会計システムの場合、全てのアカウントでまとめると常に貸方と借方は等しい、など。
- DBの性質ではなくアプリケーションの特性
Isolation
- 並行して実行されたトランザクションがお互いから分離されていること
- 複数のレベルがある
  - serializable level
  - snapshot isolation level
  - read committed level
- DBの特性
Durability (永続性)
- トランザクションが成功したらそこで書き込まれた全てのデータが失われないこと
- DBの特性

なお、以下同じ単語が複数の意味で使われて混乱を産んでいる。

📝Atomicity, Consistencyの意味の整理

Atomicity
- In ACID, commit all or abort all
- In multithreaded programming,ある処理の途中に他のスレッドから途中の状態が見えないこと (ACIDでこれはisolation)
Consistency
- In asynchronous replication, 結果整合性
- In CAP, 線形化可能性 (9.2章に詳しい)
- IN ACID, データベースが「良い状態」にあることを表すアプリケーション固有の概念

(DB内部ではなく)アプリケーション層で失敗したトランザクションをリトライすることの問題点

トランザクションが成功したがコミットの成功をクライアントに送信中にネットワークに障害が起こった場合、クライアントはそのトランザクションが失敗したとみなす
- 👉 アプリケーションレベルでの重複排除仕組みが必要
失敗がDBの過負荷によるものだった場合、リトライは状況を悪化させる
- 👉 リトライの回数を制限する。exponential backoff を行う。過負荷に関するエラーは他のエラーと異なる対応をする。
トランザクションがDB外に副作用を持つ場合がある。
- 👉 複数のシステムをまとめてコミットするにはtwo phase commitが使えるかも
クライアントのプロセスがリトライ中に落ちたらそのプロセスがDBに書こうとしたデータは失われる。

以降は Isolation の話。

Read committed level

定義
- ダーティーリードが発生しない = 他のトランザクションの未コミットの変更は見えない
- ダーティーライトが発生しない = 他のトランザクションの未コミットの変更を含むオブジェクトへの上書きができない
実装方法
- ダーティーリードが発生しない
  - 👈 オブジェクトごとに、書き込みトランザクションに関して、コミット前の古い値と、コミット予定の新しい値の両方を保持する。トランザクション進行中のオブジェクトの読み取り時には、古い値を返す
  - ❎ 読み込みをするトランザクションはそのオブジェクトの行ロック⚠️を取得する、だとパフォーマンスが悪い
- ダーティーライトが発生しない
  - 👈 書き込みをするトランザクションはそのオブジェクトの行ロックを取得する。

⚠️デッドロックが発生する可能性がある。

Snapshot isolation level

(これはread committedの保障も満たしている)

定義
- non repeatable read が発生しない = トランザクションが読み取るデータは、全てそのトランザクション開始時にDBにコミット済みのもののみ。
  - ⚠️ これは各オブジェクトのバージョンではなく、読み取り時のテーブルのバージョン、と捉えるべき。別のトランザクションが走っているとして、「レコードAの読み取り後にそのトランザクションが完了して、次のBの読み取り時にそのトランザクション反映後の新しい値が返される」のは、non repeatable read である。
  - non repeatable readは、DBのバックアップ時や、実行時間の長い分析クエリ時に問題になる
それぞれのDBにおける呼び名
- Oracleでは、Serializable level (がこれを満たす中で最も制約が弱いレベル)
- PostgreSQLでは、repeatable read
- MySQLでも、repeatable read
実装方法
- 書き込みロック + MVCC(multi version concurrency control 🟥)を用いる。
- 読み込み時には、トランザクション中ずっと同じスナップショットから読み取りを行う。
  - 👉読み取りが書き込みをブロックすることはなく、書き込みが読み取りをブロックすることもない
- インデックスは、単純にオブジェクトの全バージョンを指しておき、見えないバージョンは無視する。(実際は色々 P.261)

🟥一貫したスナップショットを読み取るための実装は、以下の通り。(一つ一つのスナップショットを保存するとパフォーマンスが悪すぎる)

実装例
- それぞれのトランザクションの開始時点で、DBは実行中のトランザクションのリストを作成する。
- 新しくオブジェクトを作成する場合には、オブジェクトが内部的に保持するcreated_byにそのトランザクションのIDが保持される。
- オブジェクトの更新時は、既存のオブジェクトはそのままで、新しいオブジェクトを作成し、それが内部的に保持するcreated_byにそのトランザクションのIDが保持される。
- オブジェクトの削除時は、読み出したスナップショットに含まれるバージョンのオブジェクト(後述)が内部的に保持するdeleted_byにそのトランザクションのIDが保持される
- トランザクション中に読み込み時に、それまでにコミット済みのtransaction_idの集合をidsとすると、(created_by in ids && created_by) && (deleted_by == null || deleted_by not in ids) の中でcreated_byが最大のバージョンのオブジェクトを読み取る

書き込みスキュー問題

前章で挙げられなかったレースコンディションとして、書き込みスキューが挙げられる。書き込みキューとは、２つのトランザクションが同じオブジェクト(群)からの読み込み結果を元に書き込みを行う場合に発生するレースコンディション。

この中で「更新のロスト」と「ファントム」を取り上げる。(DBによっては先述のバージョンを使えば発生しないものもある)

更新のロスト問題

定義
- 「アプリケーションがDBからなんらかの値を読み取り、その値を元に新たな値をDBに書き込む」read-modify-write 操作を二つのトランザクションで同時に行った時に発生しうる。
- (1つ目のトランザクションの読み取り) -> (2つ目の読み取り) -> (1つ目の書き込み🟥) -> (2つ目の書き込み🟢) の順に行われた場合、🟢が🟥を上書きし、🟥の更新が失われる。
例
- 二人のユーザーがドキュメントを更新する場合に、片方の更新が失われる。
解決方法
- ① DBの提供するアトミックな更新処理を利用する。多くのRDBでは
  - SELECT users SET col = col + 1 WHERE key = 'foo' で、read-modify-write 操作をアトミック(transactionより粒度は小さいはず)に実行してくれる。
  - 可能な内部実装は、
    - ①カーソル固定 = トランザクションは読み取り〜書き込み完了までオブジェクトのロックを取得する。
    - ②全ての操作を単一スレッド上で実行する
  - ORmapperを使うとこれを使わず、意図せず安全なread-modify-writeサイクルを実行するコードを書きがち。
- ② DBの提供する更新のロストの自動検出を利用する
  - read-modify-writeサイクルの並列実行を許可し、トランザクションマネージャーが更新のロストを検出したら、トランザクションを中断かつリトライする。
  - 👀対応しているDB/分離レベルは、PostgreSQLのrepeatable read、 Oracleのserializable、 SQL serverのスナップショット分離レベル。
    
    MySQL/InnoDBのrepeatable readではこれを提供していない。
- ③ 書き込み時に明示的に行ロックを取得する。
  - SELECT * FROM users WHERE id=5 **FOR UPDATE **
  - 👎 アプリケーションコードのどこかで必要なロックを追加し忘れる可能性がある
- ④ 分離レベルとしてSerializable levelを採用する。

⚠️マルチリーダー、リーダーレスのレプリケーションがされたDBでは①②③は利用できない。

ファントムリードによる書き込みスキュー

定義
- 奇襲するパターンは、「①SELECT文🟢である条件を満たすか確認 -> ②アプリケーションで処理を続行するか判断 -> ③DBへ書き込み」で、最後の書き込みより前に🟢の条件が満たされなくなっている。
- 例
  - ❶ 病院の当直システムにおいて、ある時間帯に他の医者の当直当番が入っていたらキャンセルができる。
  - ❷ ユーザーがユーザー名を登録する際に、もしそれがユニークな名前でなければ作成失敗にする
解決方法
- ①のロック取得クエリでロック取得。つまり、SELECT ~ FOR UPDATE により関連するオブジェクト全てのロックを取る
  - 👍 ❷のユニークなvalidationでは使用できない。なぜなら、条件を満たす行が存在しないことをチェックしているから。
- ②衝突の実体化 = 条件を満たす行が存在しないことをチェックのために、存在する全ての組み合わせを含むテーブルを用意する。
  - = ファントムをDB中の行の集合におけるロックの衝突に置き換える
  - 👎 並行性の制御の仕組みをアプリケーションのデータモデルに漏れ出してしまうのは望ましくない
- ③条件を満たす行が存在しないことをチェック
- 👀 PostgreSQLのrepeatable read、 Oracleのserializable、 SQL serverのスナップショット分離レベルでは自動検知できない。

Serializable level

最も強い分離レベル。DBの考えられる全てのレースコンディションを回避してくれる。

定義
- 複数のトランザクションがそれぞれ１つずつ順番に、並行でなく実行でされた場合と同じになることを保証する。
実装方法
- ①完全な逐次実行 = 単一スレッドで順次トランザクションを実行する
  - ただし、パフォーマンスが問題になるので、
    - OLTPトランザクションのように、小さくて高速(短く少数の読み書きしかしない)場合のみ使用する。
    - トランザクションのコード全体をストアドプロシージャとしてDBに登録しこれを実行する。これによって、アプリケーションのクエリ発行の待ち時間やネットワーク通信の待ち時間が不要になる。(ストアドプロシージャの言語は、VoltDbはJava、RedisはLua)
    - DBをパーティショニングする。ただし、アプリケーションが使用するデータ構造的にトランザクションが単一パーティションで実行できる場合のみ有効。
- ② two phase lock
  - ❶sharedとexclusiveのモードを持つlock + ❷predicate lockかrange lockで実現する。
    - ❶各オブジェクトは、shared/exclusiveの二つのモードを持つlockを持つ。
      - 読み込み時には、shared modeのロックを取得する必要がある。shared modeのロックは複数のトランザクションが、同時に取ることができる。
      - 書き込み時には、exclusive modeのロックを取得する必要がある。もし(いずれのモードだとしても)ロックが他のトランザクションによって取得されていたら、待つ。
      - ロックを取得したトランザクションはトランザクション終了までそのロックを保持し続ける。(つまり、shared mode lockを取得したまま待ち状態に入るトランザクションもありそう)
      - 👉 書き込みは他の書き込みも読み取りもブロックする。読み取りは他の書き込みのみブロックする。
      - デッドロックはDBによって自動検出され、いずれかのトランザクションが中断される。リトライはアプリケーションが明示的に行う。
      - ⚠️ これだけだとファントムは発生しうる -> predicate/range lockで対応。
    - ❷predicate lockかrange lockによってファントムの発生を防ぐ。
      - predicate lock(述語ロック)
        
        トランザクションA内で読み込みのためにSELECT文によって検索をした場合、その検索条件にマッチする集合に対する共有ロック(=述語ロック)を取る。この集合が不変になることを保障したい。
        
        そもそも、その集合内のオブジェクトの排他ロックがトランザクションBによって取られていたら、AはBの終了を待つ。
        
        Cが挿入or更新or削除しようとしているオブジェクトがAの述語ロックにマッチしている場合、CはAの終了を待つ。
        
        👎パフォーマンスがよくない -> 多くのDBではrange lockを使用している
      - range lock(範囲ロック)
        
        パフォーマンス向上のためにpredicate lockのマッチするオブジェクトの集合を大きくする。マッチを包含するインデックスエントリの共有ロックを取る。
        
        (例) 読み込みのクエリが SELECT * FROM reservations WHERE room_id = 123 AND 22/08/15 < start_timeであり、room_idカラムにインデックスが貼られているとする。この時、rood_id=123のインデックスエントリのロックを取得する。
        
        別のトランザクションの書き込みは、インデックスを辿って書き込み対象のエントリに辿り着き、それが共有ロックを取られていたら、解放されるまで待つ。
        
        範囲ロックを与えるのに適したインデックスがない場合には、テーブルロックにfallbackする。
- ③Serializable Snapshot Isolation (2008~)
  - スナップショット分離に基づいている。トランザクション内の読み取りは一貫したDBのスナップショットから行われる。
  - 楽観的ロックを取る= 潜在的に危険なことが生じても、トランザクションの実行をブロックせずにそのまま継続し、結局問題がなったことを期待する。問題があればabortされ、retryが必要になる。
    - c.f. two phase lockは悲観的ロック
    - 潜在的に危険なことが生じる = premiseが覆る可能性がある状況 = あるトランザクションにおける読み取り後にDBのスナップショットが書き換えられる。(スナップショットは実際にバージョン数だけあるわけではないため)
      - 潜在的な危険①あるオブジェクトの読み取り時に、そのオブジェクトの他のトランザクションによる未コミットのバージョンが存在する
        
        「現在のトランザクションの読み取り後に書き込みをした」 && 「その未コミットの書き込みがコミットされたことをDBが検知された」場合には、実際にpremiseが覆っている。
        
        読み取りだけの場合や、その未コミットの書き込みがコミットされなかった場合には、premiseは覆っていない。
      - 潜在的な危険②あるオブジェクトの読み取り後に、その後の書き込みに影響する可能性のある他のトランザクションによる書き込みが検出された
        
        略
  - 👍️ ライターはリーダーをブロックせず、リーダーもライターをブロックしない

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

(以下結構端折ってる)

分散システムを利用する目的は

scalability
fault tolerant
low latency (データを地理的にユーザーの近くにおける)

分散システムには部分障害が生じうる。その原因は、

ネットワーク経由でのパケット送信時にパケットがロストしたり遅延したりする。
ノードのクロック同士がずれうる。
プロセス(スレッド)が処理中に一時停止することがある。かつ自分はそれに気が付いていない。
- stop-the-world GCによるもの
- VMのsuspend and resumeによるもの
- OSによるpreemptiveなスレッド切り替えによるもの
- ディスクI/O待ちによるもの
- OSのディスクへのスワッピング(ページング)処理によるもの

TODO🔥:

ビザンチン障害についてメモる
プロセスの一時停止とリースとフェンシングサービスについてメモる

第9章一貫性と合意

合意とは

合意(Concensus)を達成するとは、

全てのノードが決定に同意するような方法で何かを定め、その決定を覆せなくすること
以下の性質を保つ
- 一様同意 uniform agreement (安全性)
- 整合性 integrity (安全性)
- 妥当性 validity (安全性)
- 終了性 termination (ライブ性)
  - 半数未満のノードに障害があっても他のノードは決定に達する = 耐障害性を形式化したもの。
合意とは、様々なアプリケーションで再利用可能な概念分散システムで提供される以下の保障や抽象概念(詳細は後述🟩)は実際には合意と等価である。
- 線形化可能なcompare-and-setレジスタ
- 全順序ブロードキャスト
- 分散トランザクションにおけるアトミックなコミット
- ロックとリース
- レプリケーションされたDBにおけるリーダー選出
- 協調サービス(ZooKeeper等)における線形可可能でアトミックな処理
- ユニーク制約
- 📝シングルリーダーデータベースは書き込み時に合意アルゴリズムが不要！しかし、リーダーシップの管理や変更の対応のために必要である😞
- 📝リーダーレスやマルチリーダーレプリケーションのシステムは通常グローバルな同意を用いない -> 衝突が発生する。が問題ない。
📝内部的なアルゴリズムはそれぞれの用途で見ていく。
👎️合意には以下の限界がある
- 処理を行う上で厳密な過半数を必要とする。半数以下のノードからなるネットワークが分離されると、それらはブロックされる。
- ノードの追加や削除は簡単に行えない。
- ネットワークの問題により障害中のノードの検出を誤判定する可能性がある。この場合、リーダーの選出を繰り返し行うため、パフォーマンスが悪化する。

分散システムで提供される保障や抽象概念は合意アルゴリズムを使用している

線形化可能性(linearizability)は、強い一貫性モデル
- レプリケーションされたデータ(オブジェクト)が、あたかもデータのコピーが一つしかないかのように見え、そのデータに対する操作がアトミックに働く。つまり、最新性の保証。
- 定義
  - ある読み込み/書き込み処理A -> Bの実行時間帯が被っていない場合、Bの操作はAが反映された状態のDBに対して行われる。
  - AとBの実行時間帯が被っている(並行している)場合には、それらの操作の順番は問われない。
- 具体的な用途は
  - リーダー選出のための分散ロック
  - DBのユニーク制約
  - クロスチャンネルタイミング依存関係
- 実装方法
  - 📝「レプリケーションを持たない」のは耐障害性が失われるのでなし。
  - 略
- 線形化可能にすることのコスト
  - 可用性(Availability)が失われる
    - CAP定理は「ネットワーク分断が発生したときにC(＝線形可能性)とAのいずれかしか担保できない」ことを表している。
  - パフォーマンスが落ちる
    - 多くのDBでCを犠牲にする理由はAの担保ではなく、パフォーマンスの悪化防止
因果律は、弱い一貫性モデル
- イベントに順序を持ち込む
  - バージョン履歴は分岐と合流をもつ時系列(並列に行われる処理もある)
- 「システムに必要なのは実は線形可能性ではなく、因果律における一貫性」だという場合も多い。
- 線形化可能性ほどの調整のためのオーバーヘッドを持たず、ネットワークの問題も線形化可能性ほど敏感ではない。
- 実装
  - バージョン管理のために、ランポートタイムスタンプ (counter, node id) を用いる
- 👎️操作の全順序が決まるのは全ての操作が収集できた後である＝あるイベント発生時に他のノードでそこまでに発生したイベントの全てを得られる訳ではない → あるリクエストの受信時に即座に成功かの判断はできない。
❎結果整合性(eventual consistency)は弱い保証であり、これは合意アルゴリズムを必要としない(?)
全順序ブロードキャスト
- ノード間のメッセージ交換プロトコル
- 以下の安全性が常に満たされる。
  - (信頼性)メッセージは厳密に一度だけ全てのノードへ配信される
  - (順序付け)全てのノードは、同じ順序でメッセージを受信する
- メッセージが配信された時点で順序が確定される
- 使用される例
  - データベースのレプリケーション
  - ZooKeeperやetcd
  - serializableなトランザクション
  - フェンシングトークンを提供するロックサービスの実装
  - linearizableな、アトミックなcompare-and-set操作
    - 全順序ブロードキャストをappendのみが行われるログとして使用⭐
- 実装方法
  - linearizableなシークエンス番号生成器で、各ノードは処理のシークエンス番号を発行してもらい、その順番に各ノードはメッセージ送信を行う。ただしその生成器の冗長化のためにはまた合意が必要である。
分散トランザクション
- 📝多くのNoSQL分散DBではサポートされていないが、様々なクラスタ化されたRDBではサポートされている
- アトミックなコミットを実現するために同意アルゴリズムが用いられている。
- アトミックなコミットが有用なケースは
  - マルチオブジェクトトランザクション
  - セカンダリインデックスの作成時
- アトミックなコミットの実装
  - クライアントのリクエストはコーディネータに渡る。コーディネータは各ノードへ以下のリクエストを行う。
  - ①データの書き込み依頼
    - これを受け取った時点で各ノードはトランザクションを開始する。
  - ②(P1)コミット可能か質問(いかなる場合でも可能ならノードはyesが返す)
    - ここでyesを返したノードはその後絶対にコミットを行う義務を追う。
  - ｰｰｰコミットポイントｰｰｰ
    - ここを越えた時点でコーディネータは絶対に全てのノードへコミット依頼を送り届ける(リトライ含める)義務を追う。
    - コーディネータは中断するかの判断をディスク上のトランザクションログに書き込む🟦
  - ③(P2)コミット依頼
- X/Open XAに準拠するDB, メッセージブローカーetcを用いることで、2つ以上の異なる技術を利用して分散トランザクションの2 phase commitを実現できる。
- 👎️パフォーマンスが良くない。
  - 🟦のディスク書き込み
  - ネットワークのラウンドトリップの増加
- 👎️コーディネータがクラッシュした場合、各ノードは関係するレコードのロックを取り続けることになる。この場合、コーディネータのリカバリーを待つ必要がある。
- 👎️コーディネータがレプリケーションをもたない場合、これが単一障害点になる。
ZooKeeperやetcd
- インメモリデータベースの分散キーバリューストア。(ただし永続化のためにディスク書き込みは行われる)
- データのレプリケーションは耐障害性を持つ全順序ブロードキャストアルゴリズムによって行われる。
提供する機能は以下。これらは分散協調に使用される。
- ロック。👈️linearizableでアトミックな操作を利用して実装される。 ⭐同意アルゴリズムを使用している。
- ロック/リース×プロセスの一時停止に起因するレースコンディションを防ぐために使用されるフェンシングトークンの発行。👈️操作の全順序付けを行うことで実現される。
  - zookeeperサーバーに接続中のクライアントの障害検出。👈️クライアントから定期的に送信するハートビートのタイムアウトによって検知される。
  - 他のクライアントの新たな参加や、他のクライアントでの障害発生等が、クライアントへ通知される。(クライアント自らポーリングする必要はない)
- 用途
  - 協調及び設定サービスとしての使用。利用例は以下。(合意アルゴリズムを自分で実装しなくて良い)
    - リーダーの選出
    - パーティショニングされたリソースにおいて、どのノードにどのパーティションを割り当てるかの判断
  - サービスディスカバリのために利用
    - ＝特定のサービスにアクセスするのに接続しないといけないIPアドレスを知るために使用。
    - これは合意を必要としない。
  - メンバーシップサービスとしての利用
    - ＝アクティブでクラスタのメンバーとなっているノードを判断する。
    - 合意と障害検出を組み合わせ、他のノードに障害が発生してきるかをノード間で同意する。

📝トランザクション分離の目的は並行してトランザクションを行うことに起因するレースコンディションを避けること。分散の一貫性の目的は、遅延やフォールトに再してレプリカの状態を調整すること。

「データ指向アプリケーションデザイン」第 II 部 (分散データ) を読んだ

第5章 レプリケーション