データ指向アプリケーションデザイン 第I部 データシステムの基礎を読んだ - $shibayu36->blog; の続き。今回は第Ⅱ部を読んだ。長いし難しいが勉強になる。
今回はクオラム、並行操作の検知、パーティショニングとセカンダリインデックス、スナップショット分離、さまざまな課題が合意の問題に帰結する話あたりが面白かった。
読書ノート
### 5章 レプリケーション
- 同期型と非同期型レプリケーション 4001
- 同期型レプリケーションの利点は、フォロワーが持っているデータが最新であることの保証。欠点はフォロワーが反応を返さなかったら書き込みが処理できなくなってしまうこと。全てのフォロワーを同期型にするのは現実的でない
- 準同期型：フォロワーの一つだけ同期型、それ以外は非同期型。2ノードに最新データのコピーがあることが保証
- 非同期型：フォロワー遅延でもリーダーは書き込みを継続できる利点。リーダー障害時にレプリ完了していない書き込みが損失する欠点。
- 論理ログレプリケーション 4166
- ストレージエンジンの内部から分離させた論理ログを利用したレプリ
- 例: MySQLのbinlog
- 内部から分離されたので後方互換性を保ちやすく、リーダーとフォロワーで異なるバージョンやストレージエンジンを動作させられる
- 外部システムに送信したい場合も役立つ。データウェアハウスへ送るなど
- レプリケーションによって時間の巻き戻りに見えることがある 4298
- モノトニックな読み取りを実現する方法の一つは、各ユーザーが常に読み取りを同じレプリカから行うこと 4298
- レプリケーションによって因果関係が逆転するように見えることがある 4338
- マルチリーダーレプリケーションは異なる2つのデータセンターで並行して同じデータが変更されることがある大きな欠点がある。それらの書き込みの衝突を解決しなければならない 4408
- かなり難しいのでできればマルチリーダーレプリケーションは避けたい
- マルチリーダーレプリケーションが適切なのは、
- インターネットに接続されていないときもアプリケーションが動作し続けなければならない時 4408
- スマホ側がローカルデータベース、サーバー側がリモートデータベースとして、マルチリーダーレプリケーションの考え方を反応できる
- リアルタイムコラボレーティブ編集
- 収束的に衝突を解決する様々な方法 4492
- 最後の書き込みを勝たせる
- ユニークIDを与え、値が大きいものを優先
- 値のマージ
- 衝突記録をしてユーザーに解決してもらう
- マルチリーダーレプリケーションのトポロジー 4540
- リーダーレスレプリケーションではクライアントは複数ノードに読み書きする 4622
- 書き込み・読み込みはどれだけの数成功していれば良いか？ => クオラムという考え方 ⭐️
- n個のレプリカ、最低w個の書き込み成功、最低r個に読み込み発行として、w + r > nであるなら読み取りで必ず最新の値が得られることを保証できる
- リーダーレスレプリケーションは並行して書き込みがあるため、結果整合性を実現するために同じ値に収束させる必要がある 4820
- 操作Aと操作Bがある時、3つの可能性。AがBより先、BがAより先、AとBが並行。AとBが並行なら解決しなければならない衝突が生じている
- バージョン番号を用いることで、並行操作を検知できる 4901 ⭐️
- アルゴリズム
- サーバーは全てのキーのバージョン番号を管理し、書き込みのたびにバージョン番号をインクリメント。書き込まれた値と合わせて新しいバージョン番号を保存
- クライアントがキーを読み取る時、サーバーは上書きされていない全ての値を最新のバージョン番号と合わせて返す。クライアントは書き込みを行う前に、そのキーを読み取らなければならない
- クライアントはキーを書き込む場合、以前の読み取りで得たバージョン番号を含め、その読み取りで得た全ての値をマージしなければならない
- ショッピングカートの例だと和集合を取るなど。ただし削除に対応するために削除マーカーを追加するというやり方を取る必要もあり
- バージョン番号を含む書き込みを受信すると、サーバーはそのバージョン以下のバージョン番号を持つ全ての値を上書きできる
- 気づき：複数バージョンを考慮した書き込みによって、以前のバージョンをobsoleteしていくイメージ
まとめ
- レプリケーションの目的
- 高可用性：いくつかのマシンダウンでも動かせる
- 切断されている状態での操作：ネットワーク障害でもアプリケーションが動作し続ける
- レイテンシ：地理的にユーザーの近くに配置し、ユーザーとのインタラクションを高速化
- スケーラビリティ：複数のレプリカで処理して、多くの読み取りを処理する
- レプリケーションアプローチ3つ
- シングルリーダーレプリケーション
- クライアントは全ての書き込みを1つのリーダーノードに送り、リーダーが他のレプリカに変更イベントを送る
- フォロワーからの読み取りデータはレプリ遅延があり得る
- マルチリーダーレプリケーション
- クライアントは複数のリーダーのいずれかに書き込む。リーダー群は変更イベントをリーダーそれぞれに送り、かつ全てのフォロワーへ送信
- リーダーレスレプリケーション
- クライアントは書き込みを複数のノードに送信し、古いデータを持つノードを修正するために読み取りを複数のノードから並列に行う
- レプリケーションは同期でも非同期でも行える
- 非同期は基本は高速に動作するが、レプリケーションラグが大きくなったり、サーバー障害が起こったりするときに何が起こるか理解が必要。リーダー障害によるフェイルオーバー時にデータ損失も生まれる
- レプリケーションラグが生じている状況での振る舞いを理解するための一貫性モデル
- read-after-write一貫性：ユーザーは自分が投入したデータを常に見ることができる
- モノトニックな読み取り：ある時点のデータをユーザーが一度見たら、それ以前の時点のデータを見ることがない
- 一貫性のあるプレフィックス読み取り：適切な因果関係を保持した状態でデータを見ることができる
- 複数書き込み時の衝突問題。ある操作が他の操作より先に行われたのか、並行して行われたかを判断する必要がある
### 6章 パーティショニング
- リバランシングの最低限の要求 5451
- 完了後は負荷（=データストレージや読み書きのリクエスト）はノード間で公平に分配されている
- リバランシング実行ちゅうも、読み書きを受け付け続けなければならない
- 移動データは必要最小限に行い、リバランシングが高速かつネットワークやディスクI/0の負荷が最小になるようにする
- キーの範囲でパーティションしている中で特定のデータベースはどう的にパーティショニングする 5503
- パーティション数をデータの総量に適合させられる
- パーティション数がノード数以下になると遊んでいるノードができる -> 最小パーティション数で対応
- 自動リバランスは自動的な障害検出と組み合わさると、一時的にノードが低速になった時にリバランスが走り、他のノードの負荷が高まり状況を悪化させることがある 5564
- どこかに人を介在させた方が良いケースが多い
- リクエストのルーティングの3手法 5564
- ある範囲がどこにあるかを返す時、全ての場所で一致している必要がある -> 合意形成のプロトコルの出番
- ZooKeeperに依存させる例
まとめ 5637
- パーティショニングの目標は、データやクエリの負荷を均等分配し、不均衡に高い負荷が生じるノード（ホットスポット）を生じないようにすること
- パーティショニングをどういうキーで行うか、ノード追加や削除でどうリバランスするか
- 2つのパーティショニングアプローチ
- キー範囲によるパーティショニング
- 1パーティションに最小値と最大値を設定し、その中のものをノードに入れる
- 範囲クエリが効率的に処理できるが、ホットスポットが生じるリスクが大きい
- パーティションが大きくなりすぎた時はその範囲を2つに分割するリバランスを行う
- ハッシュパーティショニング
- キーにハッシュ関数をかけて、ハッシュの一定の範囲をノードに入れる
- 負荷分散は均等になりやすいが、範囲クエリは非効率になる
- 事前に固定数のパーティションを作成、各ノードに複数のパーティションを割り当て、リバランスでは各1つのパーティションを移動という方式を使う
- ハイブリッドなアプローチ
- 複合キーを使い、パーティションを1つの値できめ、他の部分でソート順を決める
- 一対多の関係を作るときに使い勝手が良い。user_idでまず絞り込み、範囲を使ってその投稿の一部を取得するみたいなやつ 5313
- 気づき：DynamoDBとかこういう感じになっていそう
- パーティショニングとセカンダリインデックス。セカンダリインデックスもパーティションする必要がある。方法は2つ
- セカンダリインデックスをプライマリキーおよび値と同じパーティションに保存
- ドキュメントによるパーティショニング、ローカルインデックスとも呼ばれる
- 書き込みの際に更新するパーティションが1つで済むが、読み取りには全てのパーティションにクエリする必要あり
- 値が入っている場所とは別でグローバルにセカンダリインデックスを保存
- 語によるパーティショニング、グローバルインデックスとも呼ばれる
- 読み取りはパーティションを1つで済むが、書き込みは複数のパーティションを更新する必要がある
- 複数パーティションを更新するため、アトミックにするには分散トランザクションが必要。しかし実際にはセカンダリインデックスの更新は非同期で行われる 5426
### 7章 トランザクション
- トランザクションの安全性の保証はしばしばACIDで示される 5806
- ACIDにおける一貫性(consistency)はそもそもアプリケーションの特性であり、データベースだけの責任ではない
- 原子性：書き込みがオールオアナッシング 5923
- 分離性：他のトランザクションの書き込みの一部だけが見えることはない
- スナップショット分離は、バックアップや分析的なクエリのように長時間実行される読み取りだけを行うクエリに有益 6213
- マルチバージョンオブジェクトを使ったスナップショット分離の実装 6244
- 削除されたデータにアクセスするトランザクションが存在しないことが確実になったら、GCされる
- トランザクションを提供していないデータベースには、しばしばアトミックなcompare-and-set操作がある 6372
- 最後の読み取り時から値が変化していない場合に限定して更新のロストを防ぐ
- 気づき: DynamoDBのConditional Updateっぽい
- 逆にスナップショット分離されていると困る
- ロックやcompare-and-setはデータの最新のコピーが1つしかないことを前提としている 6400
- レプリケーションがあると手法が適用できない
- 衝突する複数バージョンの生成を許し、アプリケーションコードや特別なデータ構造を使って事後にそれらのバージョンの衝突解決やマージをするのが一般的
- インデックス範囲ロック(next-keyロック)によってファントムや書き込みスキューに対する保護となる 6776
まとめ 6937
- トランザクションに関連する様々なレース条件
- ダーティリード：あるクライアントが他のクライアントのまだコミットされていない書き込みを読む
- read committed分離レベル以上なら起こらない
- ダーティライト：あるクライアントが他のクライアントによるまだコミットされていない書き込みの内容を上書きしてしまう
- ほぼ全てのトランザクション実装で起こらない
- 読み取りスキュー、nonrepeatable read：あるトランザクション内で読み取る内容が変わる
- スナップショット分離(repeatable read)によって防げる
- 更新のロスト：2クライアントが並行してread-modify-writeサイクルを実行するとき、片方がもう一方の書き込みを変更内容を考慮せずに上書きしてロストすること
- スナップショット分離レベルの実装によっては自動回避することもある。明示的なロック = SELECT FOR UPDATEしなければならないこともある
- 書き込みスキュー：トランザクションが何かを読み取り、その値に基づいて判断を下し、結果をデータベースに書き込むケースで、書き込みが行われた時点で判断の根拠となった前提が崩れていること
- 例: 当直が当該時間帯にいるので自分は抜けても良いを2並列で行うケース 6431
- 直列化可能分離レベルのみがこの異常を回避できる <- これあんまり分かってないかも
- 普通にSELECT FOR UPDATEでロック範囲を広く取れば大丈夫みたいな話は出てきた 6452
- ファントムリード：INSERT/DELETEを実行したときにおけるnonrepeatable readみたいな現象
- スナップショット分離で単純なファントムリードを回避できるが、書き込みスキューを伴うファントムに対してはインデックス範囲ロックのような特別な対応が必要
- 直列化可能分離レベルのみ上記全てを防げる
- 直列化可能なトランザクションの実装方法3種類
- 文字通りにトランザクションを順次実行する
- ツーフェーズロック
- パフォーマンス上の特性からあまり使われていない
- 直列化可能スナップショット分離（SSI）
- 非常に新しいアルゴリズム。楽観的アプローチを取り、コミット時点でチェックした時に直列化可能になっていなければ中断
### 8章 分散システムの問題
- タイムアウト設定として、一定のタイムアウト時間を使うのではなく、継続的にレスポンスタイムとその変動（ジッター）を計測し、観測されたレスポンスタイムの分布に応じて自動的にタイムアウト調整する方法もある 7460
- クロックは、時刻のクロックと単調増加のクロックの2つがある 7549
- 単調増加のクロックは、タイムアウトやレスポンスタイムなど期間を計測するのに適す
- クロックズレの監視と、一定以上のズレをクラスタから除外する 7635
- 気づき：ヘルスチェックで除外と同じようにクロックズレも観察するのは面白い
- クロックズレがあると衝突回避のlast write wins戦略も難しくなる 7664
- 「最近」とは何か問題
- Google Spannerでは現在時刻に関する信頼区間を問い合わせることができる。`[earliest, latest]`みたいな形 7715
- これを使えば、確実に重なっていないものを分離できる
- 単一ノードで信用できるものはないので、真実は多数決で決定される 7917
- ノード群によって行われる投票で最小限度以上の投票がないと判断を下せない
- システムはあるものを1つだけにしなければならないことがよくある 7947
- リーダーノードが1つ、ロックを保持できるトランザクションが1つ
- フェンシングトークンを使ったシンプルな解決
- システム中に生じるフォールトの種類の定式化 8114
- タイミングの前提
- 同期モデル：ネットワーク遅延やプロセスの一時停止期間、クロックの誤差に限度があると前提する。ほとんどのモデルでは現実的なモデルではない
- 部分同期モデル：ほとんどの場合同期モデルのように振る舞うが、ネットワーク遅延、プロセスの一時停止、くろっdbmsHelperの変動が上限を超えることが時々生じる。多くのシステムにおいて現実的なモデル
- 非同期モデル：タイミングに関していかなる前提を置くことも許されない。クロックすら持たない
- ノード障害に対するモデル
- クラッシュストップフォールト：ノードの障害はクラッシュしかないという前提を置く
- クラッシュリカバリフォールト：ノードはいつクラッシュするか分からず、いつかレスポンスを再び返し始めるかもしれないという前提を置く。クラッシュしてもストレージには内容を保持するが、メモリは失われる
- ビザンチン障害：ノードは他のノードを欺いたり惑わしたりすることがある
- 現実のシステムでは部分同期モデルとクラッシュリカバリフォールトモデルが最も有益なモデル
- アルゴリズムの性質における安全性とライブ性 8141
- 安全性の性質は、あるシステムモデルにおいて考えられるあらゆる状況下で常に守られなければならない
- ライブ性の性質は特定状況に限りという注意書きが許され、最終的にその状態に回復できれば良い
- フェンシングトークンの例
- ユニーク性：2つのリクエストに同じ値を返さない。安全性
- 単調増加するシーケンス：安全性
- 可用性：要求し、クラッシュしていなければ、最終的にレスポンスを受け取る。ライブ性
まとめ
- 分散システムにおいて生じうる幅広い部分障害 8219
- ネットワーク経由のパケットはロストしたり長く遅延したりする。リクエストとレスポンスのどちらでロストしたかも分からない
- ノードのクロックが他のノードと大きくズレる可能性がある。急に進んだり戻ったりする
- プロセスが処理中にどれほどの長さ一時停止するか分からない。他のノードから落ちているとみなされた後に地震に一時停止があったことを理解しないまま復活しうる
- 障害につながるフォールトの検出さえも難しい。多くはタイムアウトに頼る
- タイムアウトはネットワーク障害とノード障害の区別ができない
- フォールトが検出されたとして、システムが耐えられるようにすることは、共有された状態がないため難しい
- 単一ノードが重要な判断を安全に下すことはできないため、他のノードの助けを得てクオラムが合意に至るようにするためのプロトコルが必要
### 9章 一貫性と合意
- 線形化可能性の詳細な説明 8654
- 線形化可能性による最新性の保証が役立つ環境 8733
- ロックとリーダー選出
- 制約およびユニーク性の保証
- 合意アルゴリズムは線形化可能なストレージを安全に実装できる 8825
- シーケンス番号は因果律との一貫性を持つ全順序を持たせながら生成できる 9107
- 例: ランポートタイムスタンプ。全てのノードとクライアントが、過去に見た最大のカウンタ値を追跡し、その値を全てのリクエストに含めるという発想
- シーケンス番号の仕組みはユーザー名のユニーク性などを解決できない。全順序の確定時期を知る必要がある => 全順序ブロードキャスト 9191
- ユーザー名を作成する操作が行われた場合、同じユーザー名を全順序中でその操作より先に要求していたノードが他にはないことが確実になって初めて、その操作が成功したと安全に言える
- 全順序ブロードキャストは、線形化可能なストレージを使って特定レジスタにincrement-and-set操作を行い番号を作ることで実装できる 9312
- 2相コミットは複数ノードにまたがるアトミックなトランザクションを実現するためのアルゴリズム 9434
- すべてのノードがコミットするか、すべてのコミットが中断するかのどちらかになる
- 2相ロックとは別物なので注意
- 2つの重要な「帰還不能点」がある。参加者が「yes」を返すと参加者は街がなくコミットできると約束する。コーディネーターが決断したら決定を覆せなくなる
- 詳細 9486
- 合意の定式化：1つ以上のノードが値を提案(propose)し、合意アルゴリズムはそれらの値の中から1つを決定(decide)する。この形式かで、以下の性質を満たさなければならない 9698
- 一様同意：2つのノードが異なる決定をしていない
- 整合性：2回決定しているノードがない
- 妥当性：ノードが値vを決定したら、vを提案しているノードがある
- 修了生：クラッシュしていない全てのノードは、最終的に何らかの値を決定する
まとめ 9949
- 一貫性モデルである線形化可能性
- すべての操作を単一の全順序の時間軸に収める
- その目標は、レプリデータが、あたかもデータのコピーが1つしかないように見え、そのデータに対する全ての操作がアトミックに働くようにすること
- 1つのクライアントの書き込み成功すれば、即座に全てのクライアントからの読み込みはその値を見れなければならない 8596
- 言い換えれば最新性の保証
- データベースがシングルスレッドの変数のように振る舞ってくれるが、速度が落ちる（特にネットワーク遅延時）欠点がある
- 因果律
- 線形化可能性より弱い一貫性
- システム中のイベントに順序（原因と結果に基づく出来事の前後関係）を持ち込むもの
- バージョン履歴は分岐と合流を持つ時系列になる
- 線形化可能性よりオーバーヘッドが少ない
- 2つの操作に因果関係がある場合に必ず順序が一貫する 9045
- スナップショット分離は因果律における一貫性を提供する 9017
- 因果律における一貫性はネットワークの遅延によって速度が低下することのない一貫性の中で最もつよ 9076
- 因果律でも、ユーザー名ユニークを保証するような実装をするなら、順序保証だけでは対応できない。何らかの方法で並行して他ノードが同じ名前の登録をしていないか知る必要がある => 合意の問題へ
- 合意を達成する = すべてのノードが決定に同意するような方法で何かを決め、その決定を覆せなくなるようにすること
- 分散システムにおいての幅広い問題が合意の問題に落とし込める
- 線形化可能なcompare-and-setレジスタ
- アトミックなトランザクションのコミット：分散トランザクションのcommit or rollback
- 全順序ブロードキャスト：メッセージの配信順序の決定
- ロックとリース：ロックはどのクライアントが取得に成功するかを決定する
- ノードの生死
- ユニーク制約
- シングルリーダーデータベースなら決定権はリーダーのみなので、上記問題は簡単。しかしリーダーに障害があった時、対処方法は3つ
- リーダーが回復するまで待つ
- 手動でフェイルオーバー
- 自動的に新しいリーダーを選出 => 結局合意の問題になる
- ZooKeeperのようなツールは合意、障害検出などで重要な役割を果たす
