designing-data-intensive-application.md

p.vi

コンピューティングはポップカルチャーです。(...)ポップカルチャーは、歴史を重んじ ません。ポップカルチャーは、アイデンティティと当事者意識に他なりません。それは他者との協力や過去、未来とは関係なく、今を生きることです。

めっちゃいい

---

p.xii

• なぜこの本を書いた？
  • 分散システムの設計についての定番の書籍が無かった
• この本を読むとどうなる？
  • データを扱う上での基本的な概念を効率的に学習できる
    • 既存の OSS プロジェクトの位置づけ
    • バッチ処理とストリーム処理の違い
    • データの分割方法
    • 更新ログの活用方法
  • (p.8)100% 稼働するシステム構築の難しさが分かり、99.99% の稼働率ながら期待どおりに動くシステムを作るための考え方が養われる

---

p.xiii

• CAP定理は実用上有益でない
  • 対象となるシステムが狭い
• CAP定理とは？
  • 分散システムにおける情報複製に関する定理。以下の3つを同時に満たすことはできない、というもの
  • 1. Consistency => データの読み書きにおいて受け取るものは最新の書き込みデータもしくはエラーのみである
  • 2. Availability => ノードに障害が発生しても他のノードが応答する。単一障害点が無い
  • 3. Partition-tolerance
• 対象読者 *

---

p.ix

• 分散システムについての社会背景
  • ムーア則の崩壊
    • 一方で CPU はメニーコア化、ネットワークは高速化している
  • データ量・トラフィック量の増加（Twitter とか）
  • 機敏なプロダクト開発に対応できる柔軟なデータモデリングへの要求
  • OSS を利用する人間たちが増えた
  • AWS などの IaaS により多くの現場が容易に複数地域に跨る分散システムを構築できるようになった
  • ユーザーが期待する可用性の水準が高まっている
• 演算指向アプリケーションとデータ指向アプリケーション
  • 演算指向 => CPU サイクルがボトルネックになるアプリケーション
  • データ指向 => データ量やその複雑さ、変化速度が主な課題となるアプリケーション

---

p.3

• 今日、多くのアプリは演算指向でなくデータ指向
  • CPU matter ではなくデータの複雑度・量・変化速度 matter
• データ指向アプリケーションにおいて求められる機能
  • データを保存し、自身・他からそのデータを見つけられるようにする（DB）
  • 処理量の多い結果を記憶し、読み取り速度を高める（キャッシュ）
  • データ検索時にキーワード検索などフィルタリングできるようにする（検索インデックス）
  • 他のプロセスにメッセージを送り処理を非同期化する（ストリーム処理）
  • 蓄積された大量のデータを定期的に処理する（バッチ処理）
• これらを当たり前に感じる環境 = データシステムという抽象化が上手くいってる

---

p.4

• "本書は、データシステムの原理と実用性の双方、そしてデータ指向アプリケーションを構築するためにそれらを使う方法を巡る旅です"
  • (ravelll) データシステムとデータ指向アプリケーションを独立して捉える必要がありそうだ
• 1章では reliability と scalability を持ちつつメンテナンス性も高いデータシステムの基礎を調べる
  • (ravelll) 可用性 => availability
• パフォーマンス特性（アクセスパターン）や実装が異なるツールたちをなぜ データシステム という用語でまとめて考えるべきか
  • 例えば DB、キュー、キャッシュ
  • どんどんユースケースに特化したツールが生まれている
    • 分類しづらい
  • アプリケーション側がデータ処理やストレージに要求することが幅広くなり単一ツールではカバーできなくなってる
    • 複数を組み合わせて効率化する
    • (ravelll) 個々に語るというよりはまとめて捉えて立ち位置を把握するほうが良いということ？

---

p.5

---

読書会 2019/09/02

• nginx の 99 percentile の値取ろうと思ったけど DataDog の取得が弱くて 95 か MAX かくらいしか上手く取れない
• 今は MongoDB はシャーディングしてない？ => してない
  • Primary, Replica, Hot Stanby
  • i3en 12 (Primary, Secondary)
• Performance Service によってどこが軽くなる？
  • MongoDB に入ってる *Usage データを外部にサービスごと切り出す
• 全体のスループットが R/W 合わせて 20,000 超えるのはピークレベル
  • api への書き込みが 40,000 reqs/min あってすごい、新記録
    • ということは Mongo へのアクセスはもっとある

---

3章 ストレージと抽出

• 運用するアプリケーションの特性に合わせてストレージエンジンを効果的に動かすためにはストレージエンジンの挙動を大まかに知っておく必要がある
  • トランザクションに最適化されたストレージエンジンもあれば分析に最適化されたストレージエンジンもある
• ここで見ていくエンジン: log-structured ストレージエンジン、B-tree などのページ指向なストレージエンジン

3.1 データベースを駆動するデータ構造

• ログ：追記のみが行われるデータファイル
  • ログ = アプリケーションログではない
  • この本ではログ = 追記だけが行われるレコードの並び
    • 人間が可読か否かは問わない。例えば他のプログラムが読むことを目的とするならばバイナリで良い
• 追記はかなりパフォーマンスが良い操作
  • 一方で愚直な探索はかなりパフォーマンス悪い(O(n))
• データにメタデータを付与してデータ探索の効率を上げる => インデックス

3.1.1 ハッシュインデックス

• key とそれに対応する value が格納されているファイル上の位置をセットにしたものを持っておく（ハッシュマップ）
  • データ挿入時にはハッシュマップも更新する
• 各キーに対応する値が頻繁に更新されるようなワークロードに向いてる
  • 例：動画に対するその視聴回数
• ログが肥大化したらファイルをクローズし各キーの最新行だけを残して別セグメントに移す(コンパクション)
• (ravelll)ここで言う "セグメント" とは何を指している…？
  • メモリのセグメント？
  • ストレージセグメントという言葉が出てきたので違う…？
• (ravelll)ログを人間が読まないならCSVとかじゃなくて良いのだなー
• key/value を削除するときは削除を示すデータを挿入してそれ以前の値を捨てられるようにマークする
• (ravelll)ハッシュマップはインメモリである必要があるのはなぜ？
  • ディスクを2回見る（1回目はハッシュマップの参照、2回目は値の参照）のはパフォーマンス的に許容できないレベルということ？
  • ログが大きいのであればディスクに保管しているハッシュマップを1回取ってくるくらいならパフォーマンス的にも問題ではないのでは
    • ディスクにハッシュマップを記録し続けることによるパフォーマンス劣化が問題？
    • Bitcask だとスナップショットをディスクに保存して再起動後にメモリに読み込めるようにしている
  • ちゃんと書いてあった、パフォーマンス的に無理という話だった
• (ravelll)各セグメントにハッシュマップを置く理由がよく分かってない
  • イメージがわかない。コンピュータサイエンス〜
• SSD でもある程度シーケンシャルな書き込みのほうが望ましい、そうなんだ
• 追記だけにせず過去の値を上書きする仕様にすると、更新中にクラッシュすると辛い感じになる
  • 追記だけだと気にする必要なくて楽
• 長時間あるセグメントにデータ置いとくとフラグメンテーションが起きる可能性が高まる？
• ハッシュマップでは範囲で取得するクエリは効率悪い
  • 各キーを素朴にルックアップする感じにになってしまう

3.1.2 SSTableとLSMツリー

• セグメントファイルへの書き込みをキーでソートされるように行う
  • ソート済み文字列テーブル（Sorted String Table）
• マージ時には各セグメントファイルのキーを頭から見ていき最小のものから新しいセグメントファイルに書き込むことで新しい SSTable が簡単にできる
• ハッシュマップは持たない
• ハッシュマップと違い、全てのキーについてのオフセットをメモリに持たなくてもよい
  • 間引いた形でキーとオフセットのリストを保持しておいて探したいキーに近いものを探せば比較的近くのオフセットを見つけられるのでそこからスキャンする
• (ravelll)圧縮 = キーの重複しているレコードを消すということ？
• ソートをキープしてデータを記録するには赤黒木、AVLツリーとかのツリー構造が使える
  • ソートされたデータを管理するのはディスク上よりもメモリ上のほうが遥かに容易とのこと
• データ追加の順序
  • balaced tree に対してデータを追加する
  • 一定以上木が大きくなったらファイルに書き出す
  • マージ・コンパクションはバックグラウンドでたまにやる
• このままではデータベースがクラッシュしたときに直近の balanced tree にしかなかったデータが消失してしまう
  • ログを別途ディスクに持っておく（これはソート済みではない）ことで balanced tree を復旧できるようにしておくと回避できる

3.1.2.2 SSTableからのLSMツリーの作成

• LSM: Log-Structured Merge-Tree
• ソート済みのファイルのマージとコンパクションを基盤とするストレージエンジン: LSMストレージエンジン
  • Lucene の "語の辞書" の保存方法はこういう感じ

3.1.2.3 パフォーマンスの最適化

• パフォーマンスが損なわれるエッジケースを考える
  • 例えば LSM ツリーのアルゴリズムは存在しないキーの探索に時間がかかる場合がある
    • 種々のストレージエンジンはブルームフィルタを使って存在しないキーを検知している

3.1.3 B ツリー

• 最も一般的なインデックス構造
• SSTable と同様にキーと値のペアをソートされた状態で保持する
  • キーと値のルックアップが得意
  • 範囲に対するクエリが得意
• log-structured index と違うのは、データベースを固定サイズのブロックもしくはページに分割すること
  • log-structured index: 可変のセグメントに分割
• 1ページにある小ページへの参照の数 => 分岐係数(Branching Factor)
  • 通常数百程度
• 新たな値を追加するときは対応するページにキーを入れる。空きがないときは新たなページを作り既存のページにある参照の半分を持ってくる
• 木が常に balanced なので n 個のキーを持つ B ツリーの深さは常に O(log n) になる
  • ほとんどのデータベースでは深さ3~4で収まる
  • ページサイズ4KB, 深さ4レベル、分岐係数500 だと 256TB のデータを格納できる

3.1.3.1 B ツリーの信頼性を高める

• ページ更新はすなわちデータの更新なので危ない
  • 複数のページの更新中にクラッシュするとインデックスもぶっ壊れる
  • 対応として、ツリーへの変更内容を追記していく redo ログを残しておくことで B ツリーを復旧可能にしておく方法がある
• log-structured インデックスの場合よりも並行処理への対応が複雑になる
  • あるスレッドから見たときにインデックスツリーの整合性が保たれていなく見えるかもしれない

3.1.3.2 B ツリーの最適化

---

4章 エンコーディングと進化

• 進化性(1章で紹介)
• RDB => 全体が一貫したスキーマに従う
• NoSQL => 部分ごとにスキーマが異なりうる
• スキーマの変更があるときはアプリケーションもコードを変更する必要がある場合が多い
  • けど大規模なアプリじゃ対応するコード変更をシュッとやりづらい。どうする？
    • ローリングアップデート
  • クライアントアプリはアップデートするかどうかユーザー次第になってしまう
• 変更前後のアプリが同時に動きうるとはどういうことか
  • 新旧のデータフォーマットがシステムに共存しうるので互換性が問題になる

4.1 データエンコードのフォーマット

• プログラムが持つデータ表現
  • メモリ上では CPU によるアクセスや操作が効率的になるよう最適化されて保持される
    • ポインタを含むインメモリな表現
  • IO に出力するときには自己完結な形で表現される
    • JSON などのバイト列としての表現
• 表現の変換 => エンコーディング（シリアライズ、マーシャリングとも）
  • ちなみに文字表現に関するエンコーディングは Character Encoding = 文字列符号化方式
    • 例えば UTF-8 は Unicode Code Point をバイト列に変換するルールの1つ

4.1.1 言語固有のフォーマット

• Ruby だと Marshal 使うとマーシャリングできる
  • data = Marshal.dump("asdffdsa")
• エンコーディングに関する問題
  • それぞれの言語ごとのフォーマットを持つので他の言語から読むのが難しく相互運用しづらい
    • 用途を考えたときに、JSON ベースでの会話をバイト列で置き換えて効率化、とかはありそう
      • 人間が読まないなら JSON とかにする必要無さそう
  • セキュリティ
    • ユーザー入力を絶対アンマーシャリングしてはいけない
  • マーシャリングを提供するライブラリは後方互換性を無視しがち
  • マーシャリングの実装がパフォーマンスを無視しがち
    • そうなの…

4.1.2 JSON, XML, 様々なバイナリフォーマット

• JSON, XML, CSV => テキストフォーマット
• XML, CSV は数値と文字列の数値を区別できない
• JSON は整数と浮動小数点数を区別できないし精度の指定もできない
  • 2^53 は IEEE754 の倍精度浮動小数点数では表現できない
  • ツイートの ID は 64bit の数値 = IEEE754倍精度では表現できない
    • ツイートを表す JSON には表現のパースミスを防ぐために ID が2つ含まれている。(1) JSON の数値型 (2) 10進数の文字列
• JSON/XML はバイナリ文字列はサポートされていない
  • base64 エンコードして文字列として格納して回避
    • データサイズが33%増加してしまう…
• JSON Schema 誰も使ってない
  • OpenAPI…
• CSV はまずスキーマがない
• とは言え、そのデータがやり取りされる間で合意されているならそんなに問題じゃない

4.1.2.1 バイナリエンコーディング

• 大きなデータ（テラバイト級とか）を扱うときには効率的なデータフォーマットが効いてくる
  • そこでバイナリエンコーディング
• 既存のテキストフォーマットに対応するバイナリエンコーディングが存在する
  • JSON なら MessagePack, BSON, BJSON とかがある
  • JSON と MessagePack はあんまり容量に差がない

4.1.3 Thrift と Protocol BuffersBuffers

• MessagePack ではフィールド名もバイナリとして表現していたが、これらではフィールド番号しか持たないことで大きく容量を削減している
  • フィールド番号とフィールド名の対応付けは通信する人がやる
• required/optional はバイナリには反映されない

4.1.3.1 フィールドタグとスキーマの進化

• schema evolution
  • 重要そうにかかれている = 1ジャンルとして確立しているということ？
• エンコードされたデータがフィールド名を持たない => フィールド番号を変えない限りは名前を変えても大丈夫
• 古いコードは認識できないタグ番号を持つ新しいフィールドを無視する
  • 本当に？実装によりそうな気がする
• 新しく追加するフィールドをデフォルト値無しの required にできない
• フィールドを削除するときに番号を付け替えないよう注意

4.1.3.2 データ型とスキーマの進化

• Protobuf にはリストや配列のデータは持たずに repeated マーカーがあるだけ
  • optional => repeated への変更をシュッとできる
  • optional から repeated にデータ型を変更したとき、optional のつもりで取得しているコードは配列の末尾を参照することになる
• Thrift にはリストデータ型がある
  • ネストしたリストデータを表現できる

4.1.4 Avro (Apache Avro)

• Thrift が Hadoop のユースケースにハマらなかったから作った
• フィールドタグ（フィールド番号）が無い
• スキーマとデータとのズレを全く許容しない設計にすることでフィールド番号やデータ型の一部をデータから省略している
  • 互換性保つの難しくね？

4.1.4.1 ライターのスキーマとリーダーのスキーマ

• ライターとしてのスキーマとリーダーとしてのスキーマが存在し、それらは一致していなくてもよい、という設計
  • ライターのスキーマとリーダーのスキーマそれぞれを満たすようにデータを変換する層がある

4.1.4.2 スキーマの進化の規則

• Avro における前方互換性 = 新スキーマをライターとして持つ + 旧スキーマをリーダーとして持つ
• 追加・削除できるフィールドはデフォルト値を持っているフィールドだけ

4.1.4.3 そもそもライターのスキーマとはなんなのか

• 通信する側はリーダーとしてのスキーマだけを持ち、データの先頭にライターのスキーマが入ってるのでそこと比較し差分を吸収するよう変換ができる
• スキーマそのものを含めずとも、スキーマのバージョンと対応するスキーマ構造を DB に保存し、データにはスキーマのバージョンだけを入れる、ということもできる
• あんまりバージョンあるとデバッグやばそう

4.1.4.4 動的に生成されたスキーマ

• Avro はフィールド番号がない = データが含まれる JSON から動的にスキーマが生成できる

4.1.4.5 コード生成と動的型付き言語

• コード生成の恩恵は静的型付き言語のほうがより強く受けられる
  • 型チェックがある

4.1.5 スキーマのメリット

• Thrift や Protobuf が種々の言語でサポートされるまでになった理由: JSON Schema みたく複雑な規約・使い方でなかったから
• 古くは ASN.1 というスキーマ定義言語があり、それと昨今の言語は共通点がある
  • ネットワークプロトコルの定義に利用されてる
  • バイナリエンコーディングは X.509 のエンコードに利用されてる
• スキーマに基づくバイナリエンコーディング、便利ですよ
  • データがコンパクト
  • スキーマがドキュメントになるし、最新状態が必ず保たれる（デコードに利用されるから）
  • 静的型付き言語ならスキーマからコードを生成して型チェックや入力補完に使える
• スキーマが進化すると IO するデータの保証・柔軟性が高まる

4.2 データフローの形態

4.2.1 データベース経由でのフロー

• DB においてライターとリーダーは同一プロセスな場合がある
  • 後方互換性が無いと自分自身がデータをデコードできなくなってしまう
• ローリングアップデートの過程で新旧のコードが同時に DB にアクセスしうる
  • 新コードで加えた変更を旧コードが読む可能性がある
    • 前方互換性が必要
• コードは突然スキーマにフィールドが増えてもそれを無視して更新できる機構にすべき
  • 新コードが新フィールドの値を更新 => 旧コードが新フィールドを無視して更新、で消えたら困る
  • あんまりピンとこないけど、誰かが防いでくれるから気にしない、というのは良くないという感じ？
• DB によっては新しい業を追加するときに既存レコードの該当行を null で更新しなくてよい
  • PG はしない？MySQL はするっぽい
  • 更新しない DB の場合はデコード時に null を補完する

4.2.1.2 アーカイブストレージ

4.2.2 サービス経由でのデータフロー：REST と RPC

• サービス：サーバーが公開するAPI
• DB は SQL によってクライアントに任意の操作を可能にするが、サービスは API によってクライアントができることを制限する
• SOA, Microservices いずれにしてもその目的は分割した小さなサービスにそれぞれのリリースサイクルをもたせ進化を加速すること
  • 新旧のサーバーが混在しうるのでデータのエンコーディングの互換性が重要になる

4.2.2.1 Web サービス

• REST は HTTP 上に構築される設計哲学でありプロトコルではない
  • リソース識別に URL を使う
  • キャッシュの制御
  • 認証
  • HTTP を用いたコンテントタイプのネゴシエーション
• SOAP はネットワーク API リクエストのための XML ベースのプロトコル
  • HTTP の機能をほぼ使わないことを目標としている
  • SOAP の関連標準 = WS-*
  • SOAP を利用した Web API の仕様は WSDL で記述される
    • WSDL は人間には読めない => 各種ツール群や IDE への強い依存

4.2.2.2 RPC の問題

• ローカルの関数呼び出しと同じように透過的にリモートサーバーのメソッドを呼び出す
  • それぞれ性質が全く違うのに透過的に呼び出すと色々問題がある
    • 成功・失敗がパラメータのみによって決まらなくなる
    • 遷移する状態が違う（タイムアウトがある）
    • 冪等性のない関数をリトライで複数実行することによる問題
    • 不安定な処理時間
    • メモリ内のオブジェクトへの参照を渡して効率化することができない
    • 連携するシステムが別々の言語で実装されている場合、変換する機構が必要で、質が悪いと死ぬ

4.2.2.3 現在の RPC の方向性

• 最近の RPC フレームワーク群（i.e. gRPC）はリモートリクエストとローカル関数の呼び出しを明確に区別している
• サービスディスカバリの機構を持っているフレームワークもある
• gRPC リクエストのキャッシュってどうなってるんだろう？
• パブリックな API は RESTful API、インターナルな API なら RPC も、というのが現状

4.2.2.4 RPC のデータエンコーディングと進化

• サーバー・クライアントが独立してデプロイできない => 進化性の阻害
• クライアントが利用したい API のバージョンをサーバー側とどう合意するか
  • URL にバージョンを含める
  • ACCEPT ヘッダーにバージョンを入れる
• [48][49] 興味ある

4.2.3 メッセージパッシングによるデータフロー

• メッセージブローカーがいることで送信者は受信者のIPを知る必要がなくなる
  • IPが変わりやすい環境下で便利とあるけどブローカーは知っている必要があるわけでそんなに便利…？
• メッセージブローカーによって送信側と受信側は論理的に分離される

4.2.3.1 メッセージブローカー

• Kafka ってメッセージブローカーなのか

4.2.3.2 分散アクターフレームワーク

まとめ

• "素早いアプリケーションの進化と、頻繁なデプロイを目指しましょう。"

---

第II部 分散データ

• スケールアップの問題はコストの上昇が性能の向上に対して比例以上になっていくこと
  • また種々のボトルネックによりサイズを2倍にしてもスループットが2倍になるとは限らない
• シェアードナッシングアーキテクチャ = スケールアウト
• パーティショニング = シャーディング

---

5章 レプリケーション

• 3つのレプリケーションアルゴリズム
  • シングルリーダー
  • マルチリーダー
  • リーダーレス

5.1 リーダーとフォロワー

• 問：すべてのレプリカが最新のデータを持っていることをどのように保証するか？
  • 解決策としてリーダーベースレプリケーションがある
    • = マスター・スレーブレプリケーション
• Apache Kafka などの分散メッセージブローカーにもこの仕組がある

5.1.1 同期と非同期のレプリケーション

• DB ごとに設定できたりハードコードされていたりする
  • PostgreSQL では？
  • MySQL では？
• "通常レプリケーションはきわめて高速です。多くのデータベースシステムは、変更をフォロワーに対して1秒以内に適用します。"
• 同期型のレプリケーションを利用することでフォロワーが持っているデータが最新であることを保証できる
• 同期型レプリケーションを使うときは通常1つのフォロワーに対して同期型、他のフォロワーに対して非同期型のレプリケーションを使う
• 非同期型レプリケーションはフォロワーが多い場合やフォロワーが地理的に分散している場合に利用されている

5.1.2 新しいフォロワーのセットアップ

• 問：新たに追加したフォロワーがリーダーのデータの正確なコピーを持っていることをどのように保証できるか？
  • データコピーではその間に起きた変更が反映されない
  • テーブルロックすればダウンタイムが発生する
• 解決策
  • リーダーが取った自身のスナップショットをコピー
    • スナップショットはダウンタイムなしで取れる
  • その後スナップショットを取った時点以降の変更をリーダーに要求する

5.1.3 ノード障害への対応

• 問：ノードはどこかのタイミングで必ず死ぬが、リーダーベースのレプリケーションの高可用性を達成するにはどうしたらよいか？
• フォロワーが死ぬ場合
  • フォロワーが復帰したあとにトランザクションログから最後に処理したトランザクションを探し、以降の変更をリーダーに要求する
  • キャッチアップリカバリ
• リーダーが死ぬ場合
  • フォロワーをリーダーに昇格する（フェイルオーバー）
  • クライアントの書き込み先を新しいリーダーに向ける
  • 古いリーダーが復帰後に自身をフォロワーと理解できるようにする
• フェイルオーバーにおける問題
  • 非同期レプリケーションを使っているときに、昇格したリーダーが古いリーダーの障害した時点までのすべてのメッセージを受信していない可能性がある
    • 受信されなかったデータを破棄する選択肢があるが、Redis など外部のストレージと同期的にデータが扱われるシステムの場合、それらとのデータの整合性が失われる危険がある
  • スプリットブレイン
  • リーダーが落ちていると判断するタイムアウト時間を設定するのが難しい問題
    • リーダー昇格のコストを下げられればタイムアウト時間短くしてガンガン昇格させる運用ができそう

5.1.4 レプリケーションログの実装

5.1.4.1 ステートメントベースのレプリケーション

• リーダーがすべての更新系クエリをログに残し、フォロワーに流す
  • 違うやり方が今日では好まれている
  • NOW() とか RAND() が崩壊する
  • 既存のデータに依存するクエリの場合、実行順序が壊れると結果がノード間で変わってしまう
• MySQL 5.1 以前で採用されていた
  • 今はステートメント中に非決定性があるか否かによって挙動を変えている

5.1.4.2 write-ahead ログ（WAL）の転送

• データベースへの書き込みをすべてログとして持っておくのはステートメントベースのレプリケーションと同じでは？
  • ステートメントではなくもっと低レベルなログであることがポイントっぽい
• PostgreSQL で採用されている
• ログがかなり低レベルな命令になっているのでバージョンアップに注意する必要がある
  • リーダーをフォロワーを別々のバージョンにすることが許されない

5.1.4.3 論理（行ベース）ログレプリケーション

• レプリケーションやストレージエンジン用に独立したログのフォーマットを使う手法
  • レプリケーションログのストレージエンジンに対する依存がなくなる
  • ストレージエンジンを物理的とみなすとこのログは論理的 => 論理ログと呼ばれる
• ログは行を単位としてテーブルへの書き込みを記述するレコードの並び
• 複数の更新を含むクエリの場合、更新される各行に対するレコードとそのトランザクションのコミットに対応するログが記録される
• MySQL の binlog はこの方式
• ストレージエンジンと切り離されているのでリーダーとフォロワーで別々のバージョンやストレージエンジンを使うことができる

5.1.4.4 トリガーベースレプリケーション

• トリガを使ってデータの変更をアプリケーションプロセスから読み取り必要な変更を加えた上でレプリケーションを行う
• 黒魔術っぽい

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

• 非同期レプリケーションが遅延することで見えるデータに差が生じるものの、反映を待てばちゃんと結果が見える => 結果整合性(eventual consistensy)
• read-after-write (read-your-write) 一貫性
  • 自身の更新がページ更新時に反映されていることを保証する一貫性
• リクエストの都度に別々のフォロワーを参照すると時をさかのぼって古いデータが見えてしまう危険がある
  • モノトニックな読み取りによってこの異常が起きないことを保証する必要がある
    • 連続した読み取りにおいて時間が巻き戻らないことを保証する
• 一貫性のあるプレフィックス読み取り
  • ある順番で行われた一連の書き込みについて、それが正しい順序でそれらが見えることを保証する
  • シャーディングした DB で問題になる
• トランザクションの存在意義
  • アプリケーション開発者がレプリケーションの微妙な問題を気にする必要なく、単純にデータベースが適切に処理を行うものと信じられるようにすること

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

• ユースケースは限定的
  • マルチDCの例
• クライアントの更新を一時的に受け付けるローカルDBをリーダーとみなすパターン
  • オフラインでも更新を受け付けるカレンダー
  • Google Docs みたいなやつ
• 書き込みの衝突をどうするか、が最大の問題
  • あるレコードへの書き込みをハンドルするリーダーを固定することで衝突を回避する
  • 書き込みのタイムスタンプを比較して大きい方を勝者として扱い適用する
    • 最後の書き込みを勝たせる = Last Write Wins (LWW)
  • など
• マルチリーダーレプリケーションツールでは衝突を解決するロジックをアプリケーションのコードでかけるようになってる
  • が、バグの温床になりやすい
  • Amazon はこの部分のバグでカートからの削除が反映されないケースが起きた
• Google Docs の衝突解決アルゴリズム：操作変換(Operational transformation)
• 最も一般的なレプリケーショントポロジーは All-to-All
  • MySQL はデフォルトでは循環型トポロジーのみをサポート
• スパニングツリーっぽい話が出てきた（無限ループ回避）
• 衝突検出に関しては多くのツールが貧弱なので頑張る必要がある

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

• 全レプリカに書き込み、全レプリカから取得する
  • 失敗は無視し、古いデータを取得したときは新しいバージョン番号を持つものを真とする
• Dynamo とかがやってるスタイル
• 最新データを全レプリカに反映させる2つの手法
  • データ欠損の補修はアプリケーション側が取得に気づいた際に更新を行う手法 (読み取り修復)
  • DB 側で補修するためのバックグラウンドプロセスを動かしておく手法もある (反エントロピー処理)
• (読み取り修復と読み出し修復とで表記ゆれがある)
• 全レプリカ数 n, 読み込み・書き込みそれぞれについて成功とみなすノード数を r, w と置き、これらの値に基づいて読み書きを設定するやり方: クオラム読み取り・書き込み
  • Dynamo ではこれらの値を設定できる
  • 一般的な選択肢として n を奇数個（特に 3 か 5)にし、w = r = (n+1)/2 にする方法がある
• 結局 Dynamo スタイルでも衝突は起きるのでいい感じに解決する必要がある
  • 例：同じキーに対して複数のクライアントから並行にリクエストが行われたとき
• 複数クライアントから並行にリクエストされる環境において、LWW における Last がリクエストの順序における Last であることを保証できない
  • 単純にタイムスタンプを見て Last を勝たせる、という妥協点
• データを絶対失いたくない => LWW は厳しい

--

6章 パーティショニング

• partitioning -> for scalability
• 分析用途でもパーティショニングすることはある
• 大規模なデータセットをどうパーティショニングするんだっけ、どうインデックス付するんだっけ

6.1 パーティショニングとレプリケーション

• 普通パーティショニングした各パーティションは別々のノードに配置される
• 図6-1 はパリティブロックのない RAID 5 っぽい
• レプリケーションについて述べたこと（5章）はすべてパーティショニングにも等しく当てはまる

6.2 キーバリューデータのパーティショニング

• 大量のデータをパーティショニングするとき、各レコードはどのノードで保管すべき？
• パーティショニングの目標： データとクエリの負荷をノード間で均一に分散させること
  • 偏りがある状態： Skew
  • 偏って忙しくなっているノード： Hot Spot
• ランダムにレコードをノードに入れていくことで均等に分散できるが、クエリするときにどのデータがどのノードにあるかわからないため全部に投げる必要があり厳しい。どうやる？
  • インデックスを作る方法（手動・自動）
    • Bigtable, HBase, RethinkDB, MongoDB
    • ノードの境界を日付にすると書き込みが1つのノードに集中することになる
      • 上手いことやって分散させると良い
    • 連続したデータが連続して配置されるので範囲選択に強い
  • インデックスを作った上でキーのハッシュによって利用するノードと記録する位置を決定する方法
    • パーティション間で均等にキーを分散させられる
    • コンシステントハッシュ
      • 境界を均等に設けず、例えばノードのIDをデータのキーと同様にハッシュ化して境界とするとか
    • 連続したデータが連続して配置されない
      • 範囲選択のクエリはすべてのパーティションに対して実行される
  • 複合インデックスを使い、先頭列のハッシュ値でパーティションを決定、以降の列の値は SSTable として格納する方法
    • 各パーティションにあるデータについては範囲選択が容易にできる
    • 各パーティションがユーザーを表し、パーティション中のデータは日付順になっている、みたいな感じ
• データを適切に分散できてもホットスポットはできる
  • i.e. あるキーに対する変更がものすごい量発生する
  • こういうワークロードについてはデータ側で自動的に対処することができないのでアプリケーション側で何とかする手がある
    • 例えばアプリケーション側でキーに乱数を付与して特定キーへの処理を分散させることができるけど読み込みが大変になる
  • 将来的にデータベースがいい感じにやってくれるでしょう…

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

• レコードがプライマリキーによってのみ取得されるなら楽だけどセカンダリインデックスが使われる場合はもっと複雑になる
• セカンダリインデックスは Solr や Elasticsearch などの存在意義、とはどういうこと？
  • セカンダリインデックスとして使われているということ？
• セカンダリインデックスを持つシステムのパーティショニング方法は大きく分けて2つ
  • 1. ドキュメントベースのパーティショニング
    • 各パーティションが自身だけを対象範囲とするセカンダリインデックス（ローカルインデックス）を持つ
    • MongoDB, Cassandra, Elasticsearch などで使われている
    • セカンダリインデックスの部分だけを検索条件にすると結局全部のパーティションにクエリを流す必要があり大変
  • 2. 語ベースのパーティショニング
    • セカンダリインデックスの各キーについて、各パーティションが決まった境界を受け持つ用にインデックスを持つ
    • インデックスが他のパーティションのレコードを含めうる（グローバルインデックス）
    • 書き込みが複数のパーティションに影響を及ぼすため低速になる

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

• どこかパーティションが死んだら誰かがその役割を引き継いだりホットスポットにならないよう再分配したりしないといけない。どうデータを配置する？
• 1. ハッシュ値の剰余で決める
  • リバランシング時に動かす必要のあるデータ多くて死ぬ
• 2. 1ノードが多くのパーティションを持つようにし、レコードではなくパーティションを必要に応じて動かす
  • パーティション数は固定で、1ノードが持つパーティション数が変わる
  • Elasticsearch がこれ
  • パーティションごとに運用コストはかかるのであんまりたくさんパーティション作ると死ぬ
  • パーティションはダウンタイムなしに増やせるのかな :thinking_face:
  • データサイズの変動が大きい状況では適切なパーティション数の変化も激しいので難しい
• 3. 動的なパーティショニング
  • Bツリーのバランシングみたいなことをパーティショニングでやる
  • データの量に応じて適当なパーティションのサイズにすることができる
  • MongoDB, HBase, RethinkDB
  • データサイズだけでリバランシングするとキーごとの処理量の偏りに対応できなそう
• 4. 各ノードが持つパーティション数を固定にし、ノードを増減させる
  • ノードを追加したら既存のノードにあるパーティションを分割し、片方をもらう感じでやる
  • Cassandra の各ノードのパーティション数は256がデフォルト！そういうサイズ感なのか
• リバランシングは負荷が高く影響範囲も大きいので自動化するとカスケード障害が怖い、手動が良いのでは

6.5 リクエストのルーティング

• このリクエストは誰(どのIP)に送るべき？ -> サービスディスカバリの問題
  • パーティションの割当に関する情報を誰が持つか
    • クライアント、各ノード、proxy
  • どうやってパーティションの割当が変わったことを知るか
• パーティションとノードのマッピングを管理するサービスを使う
  • i.e. ZooKeeper
  • ZooKeeper にマッピング情報を保存し、ルーティング層（Proxy）に変化を通知する
  • MongoDB は独自に似た仕組みを実装している（config server, mongos）
• どこかのノードにとりあえず問い合わせて、間違ってたら正しいリクエスト先を教えてもらう
  • Cassandra はこれ
• 自動でリバランシングを行わないならルーティング層が決まったマッピング情報を持つだけで良くシンプル
• Envoy はどういう感じでサービスディスカバリをやってるんだろう？

まとめ

• パーティショニングが必要になるのは単一のマシンで保存・処理をするのが現実的でないほどのデータがある場合
  • 具体的にはどれくらいなんだろう
• 2つのパーティショニングアプローチ
  • キーの範囲によるパーティショニングでは動的にパーティションを割っていくのが一般的
  • ハッシュパーティショニングではパーティション数を固定してノードを増減させるのが一般的
• セカンダリインデックスの2つのパターン
  • ドキュメントベース（ローカルインデックス）
  • 語ベース（グローバルインデックス）
• クエリのルーティング

--

7章 トランザクション

• "トランザクションは、アプリケーションが複数の読み書きを論理的な単位としてまとめる方法"
  • 1単位は成功（コミット）か失敗（ロールバック）しか取らない
  • 結果、アプリケーションは部分的な失敗を考慮することなくシンプルに再試行できる
• アプリケーションのプログラミングモデルをシンプルにすることを目的として生まれた
  • (ravelll) 確かにデータが正しく保存できることはアプリケーションの本質ではなさそうで、DB 側で担保されているのが自然そう
• トランザクションも一長一短あり、場合によってはトランザクションを提供しないほうが良い場合もある

7.1 トランザクションというとらえどころのない概念

• ACID = トランザクションが保証する安全性
  • Atomicity - 原子性
  • Consistency - 一貫性
  • Isolation - 分離性
  • Durability - 永続性
• ACID の実装は DB ごとに違う
• ACID <=> BASE
  • Basically Available
  • Soft state
  • Eventual consistency
• Atomicity
  • DB があるトランザクションの処理以前か完了後の状態しか持たない性質
    • 何らかの要因でコミットが失敗した際にトランザクションを中断し途中まで行われた変更を全て破棄できるのが大事
  • Abortability のほうが良かったんでは、という説も
• Consistency
  • アプリケーションがデータに対して持つ一貫しているべきルールに従うようにデータが保持されること
  • ACID の中でこれだけはアプリケーション側で担保すべき特性
  • 語呂合わせのために入ってるだけでは、という説も
• Isolation
  • 並行して実行されるトランザクション間の分離 => 他のトランザクションの途中の状態が見えない
  • 同じデータを並行に参照する場合に、それらのトランザクションを直列化したときと処理結果が同じになるよう振る舞うことを保証する性質
  • Serializability とも
  • 実際には Serializable になるほどの保証はパフォーマンスの問題からされないことが多い
    • MySQL で最も厳格なトランザクション分離レベルは Serializable
• Durability
  • データがちゃんとディスクに書き込まれることを保証する性質
    • ディスク上のデータ構造破損をカバーする write-ahead ログの用意もこれに含まれる
    • 特定数以上のレプリカへのレプリケーションが完了するまでを指す場合もある
  • 完全な durability は存在しない
• トランザクションの分離性はインデックスも包括する
• リーダーレスレプリケーションは Atomicity が無いものも多い
  • アプリケーションがカバーする
  • 複数のレプリカから値を読んで最新のものを取る Dynamo Style とか
• ActiveRecord などの ORM は中断したトランザクションをリトライしてくれなくて残念
  • とは言え自動リトライは必ずしもすべきものではない
    • コミットが承認されたことを DB 側が返すことに失敗したらリトライが2重更新になる
    • エラーの原因が過負荷なら自動リトライは問題を加速させてしまう
  • Exponential Backoff => リトライを指数関数的に交代させていくアルゴリズム

7.2 弱い分離レベル

• トランザクションを完全に直列化可能にすることを諦めること = トランザクションの並行性における問題全ての解決を放棄することではない
  • 並行の問題の一部から保護する
• Read Committed
  • Read (Only) Committed と考えると理解しやすい
  • 最も基本的なレベルのトランザクション分離
  • レコードロックの提供
  • dirty read/write の防止
  • Atomicity
• スナップショット分離
  • pg, MySQL では "Repeatable Read" だけど Oracle では "Serializable"
  • (ravelll) 図7-6の問題、これを防ぐのはアプリケーション側の責務な気がするけど違う？
  • Consistency を保証するための仕組み
  • 例：バックアップの最中にトランザクションがコミットされ、バックアップ済みのデータとこれからバックアップするデータとで一貫性が損なわれてしまう
    • スナップショット分離（データ全体で一貫性のある最後のスナップショットを利用する）で対応する
      • 実際にスナップショットを作るわけではなく、各トランザクションIDから自身のトランザクションから見えるべきデータを導く
  • オブジェクト = トランザクション内で行われるクエリ1つの内容
  • (ravelll) ここで言う "ページ" は何を指している？ページングのページ？
• Skew ホットスポットを伴うワークロードのことを指すだけでなくタイミングの異常も指す
  • skew: 歪んだ、傾ける など
• SQL 標準のトランザクション分離レベルについては論文中で定義がなされているが、それに従っていない実装も多い
• "取得したデータに手を加えて更新" は並行性の問題に会う
  • Atomic な更新（冪等な Update とか）を使えば回避できる
  • (ravelll) [38] の文章気になる
    • ORM で read-modify-write サイクルとなるクエリを書きやすくなってしまう問題について
  • 明示的なロックを取って read-modify-write する方法もある
    • ロックを取るコードを書き漏れないようにするの難しそう
  • DB 側で更新のロストを自動検出できる
    • pg のリピータブルリードは検出できる（MySQL はできない）
  • UPDATE 時の Where 句に更新対象のフィールドを更新前の値で指定することで回避する方法
    • compare-and-set
    • スナップショットからの読み取りが可能だと where 句が常に true になってしまうのでダメ
• 書き込みスキュー
  • pg のリピータブルリードも検出できない
    • トリガーで解決できるかも
  • (ravelll) 現実的にはでかくロックを取るなのかなあ
  • (ravelll) 会議室の例の "上のクエリが0を返した場合の処理" の分岐を実現する何かを端折られている？
  • (ravelll) 書き込み -> 読み込みの順にして後からトランザクションを中断/コミットの判断をする方法でもスナップショット分離の場合はダメそう
• ファントム
  • あるトランザクションの書き込みが他のトランザクション中の別のクエリの結果を変える効果
  • ロックを掛けるべきレコードが無いのが問題ならロックが取れるだけのデータを作っておけばよいのでは？という発想
    • 会議室の例だと、予約のレコードを作っておくんでなく、選択肢のレコードを作っておきそれを select for update させることでロックを取れるようになる
    • 並行性制御の仕組みがアプリケーションのデータモデルに漏れることを意味するのでダサい
    • Serizlizable にするほうがマシ

7.3 直列化可能性

• 決定的 => 入力に対して出力が一意に定まるもの
• 並行して実行されるトランザクションそれぞれの結果が、1つずつそれらを実行したときと同じになることを保証する
  • 書き込みスキューを含め、全てのレース条件を回避できる
• 実現方法
  • 本当に1つずつやる
  • 2 Phase Lock (2相ロック)
  • 直列化可能なスナップショット分離を行う
• (1.) 本当に1つずつやる
  • 現実的になった背景
    • "RAM 安くなって実はトランザクションの実行に必要なデータセットを全部メモリに載せられるんでは？"
    • "なら高速にトランザクション実行できるし1個1個やってっても処理時間的になんとかなるんでは"
    • "OLTPは少数の読み書きしかしないし"
    • "ストアドプロシージャ使えばネットワークレイテンシーも抑えられるし今は PL/SQL とかじゃなくリッチな言語で書ける"
  • Redis はこれ
  • ロックに関するオーバーヘッドがない分、並行実行よりも高速に動作する場合がある
  • ストアドプロシージャの活用
    • (航空券予約を想像しつつ)沢山のユーザー入力を1トランザクションにしようとすると入力待ちが長く非効率
    • トランザクションを細かくしていくとネットワークレイテンシーが馬鹿にならない
    • そこで処理をストアドプロシージャとしてまとめて1リクエストでガッとやる
  • ストアドプロシージャの欠点
    • コードが DB 上にある
      • デバッグむずい
      • テストむずい
      • 監視しづらい
    • 効率悪いコードを書いたときの影響がでかい
    • 最近は多少いい感じに書ける
      • Redis だったら Lua で書ける
      • Lua ファイルを Sha1 で登録して eval できるっぽい https://rest-term.com/archives/3038/
  • 書き込みのスループットが高いアプリケーションの場合はパーティショニングでカバーできる可能性も
    • パーティショニングした上で読み書きを単一のパーティショニングに制限できるなら並行に処理できる
  • 書き込みの比重が高いアプリケーションでは使えなさそうだけど、書き込みの比重が高いアプリケーションほど Serializeable を求める場合が多いような気もする
    • 仮想通貨とか
    • その背景があってのブロックチェーン…？
• (2.) 2 Phase Lock
  • 変種が色々あるので区別して Strong Strict Two-Phase Lock と呼ばれる場合も
  • 2 Phase Commit とは違うので注意!
  • あるオブジェクトについて、書き込み・読み取り関係なくトランザクション完了まで排他処理となるようオブジェクトをロックする
    • A transaction の write 中に B transaction が対象オブジェクトの古い状態を read することもできない
    • スナップショット分離だと W/R は互いにブロックしない
  • MySQL や SQL Server の Serializable は 2PL する
  • 2 Phase => Start と Finish におけるロックの操作（取得と解放）
  • 共有ロックと排他ロック
    • Read => Shared, Write => Exclusive
  • デッドロックが容易に起きるので DB には検出と解消のための機構がある
  • Predicate Lock （述語ロック）
    • 条件に当てはまるオブジェクト全てに対してロックを取る
      • 将来的に当てはまるオブジェクトに対してもロックを取れる
      • (ravelll)あるトランザクション内で Select where => insert としたときに追加されたオブジェクトも where に含まれるなら勝手に共有ロックが取られるということ？
    • 全部ロックするしどれか1オブジェクトでもロックを取られていたら待つ
  • Range Lock（インデックス範囲ロック）
    • 述語ロックが特定の条件に対するロックなのに対して、条件を含む単純な絞り込み対象に対してロックを取るのがインデックス範囲ロック
• (3.) 直列化可能なスナップショット分離（SSI）
  • 2PL が悲観的な制御であることに対して SSI は楽観的な制御
    • とりあえずトランザクションを並行実行させて、Serializable でない結果となるときに中断する
  • 同一のオブジェクトに対する更新が多く起きる場合、中断させられるトランザクションの割合が高くなりパフォーマンスが悪い
    • リトライが起きると負荷が高まる
    • 2PL の場合は待つ
  • いうて競合することが少ない場合はパフォーマンスが高くなる
  • プレミス: ある時点では真だった事実
  • serializable でなくなったことをどう検出する？
    • 古くなった MVCC 読み取りを検出する
      • コミットの直前で MVCC データベースを確認し、古くなった操作があったら中断する
    • 更新時に他のトランザクションの共有ロックに対して影響があれば通知する
      • が、あくまでも中断が起きるのはコミット時

まとめ

• トランザクション関係の用語の簡単な説明がここに書かれてるので忘れたときは見ると便利
  • p.288, 289

---

8章 分散システムの問題

• これまでの数章で出てきたテーマ: 「おかしくなったことをシステムがどう扱うのか」
• "おかしくなるかもしれないことは必ずいつかおかしくなるものと考えましょう"
• "私たちのタスクは何もかもがおかしくなったとしても仕事をこなしてくれるシステムを構築すること"
• 優れたソフトウェアが搭載された個々のコンピュータが通常取りうる状態は、完全に動作するか完全に壊れているか
  • 決定的な処理
  • 間違った答えを返すよりクラッシュするほうが望ましい
  • 分散システムの場合はここが根本から違うのじゃ…
• 分散システムで部分障害が起きると処理が非決定的になるのでムズい
  • 何がどこで失敗したのか謎、そもそも失敗・成功が分からない、とか
• ハイパフォーマンスコンピュータからクラウドコンピューティングへのスペクトラム
  • 間のどこかにエンタプライズデータセンターが入る
  • スペクトラム中の位置によってフォールトを扱うためのアプローチが変わる
  • ダウンタイムの許容、ハードウェアの信頼性、ネットワークの形状、故障を前提とするか、部分障害があってもシステムを継続できるか、ハードウェアの地理的な分散、などの面で違いがある
• "信頼性のないコンポーネントから信頼性のあるシステムを構築する"

8.2 信頼性の低いネットワーク

• 人間が設定する機器で問題が起きているなら単純にその危機を冗長化するだけではフォールトは減らない
• 「サメが海底ケーブルかじってて…」というギャグ
• ネットワークリンクは送信が成功しているからといって受信が成功するとは限らんぞ！
• 普通はネットワークの問題に対してはエラーページを出すだけで良いかもだけど、ソフトウェアがネットワーク障害に対してどういう動きをするのかは知っておいたほうがいいぞ -- p.305

9章 一貫性と合意

• fault-tolerance: 耐障害性
• 耐障害性を持つ分散システムが備えるべきアルゴリズムとプロトコルの話
• 分散システムが耐障害性を持つためには然るべき抽象的なアルゴリズムに分散システムを依存させる
  • 例えば合意などについて、アプリケーションが意識しなくて済むようにする（この辺は DB と同じ）
• 分散システムが提供できる保証には限度がある。何ができて何ができないかを知ると良い

9.1 一貫性の保証

• "結果整合性(Eventual Consistency)"は、最終的に同じ状態に収束するという意味で"収束性(Convergement)"のほうが良いんでは
• トランザクション分離と分散一貫性モデルの共通点・違い
  • トランザクション分離：並行したトランザクションにおけるレース条件を回避する
  • 分散一貫性モデル：遅延・フォールトに際してレプリカの条件を調整する

9.2 線形化可能性 (Linearizability)

• 別名：atomic consistency, strong consistency, immediate consistency, external consistency
• "基本的な発想は、データのコピーが1つしかなく、そのデータに対する全ての操作がアトミックであるかのようにシステムを見せるということです"
  • Atomicity: DB があるトランザクションの処理以前か完了後の状態しか持たない性質
• "線形化可能性を持つシステムでは、1つのクライアントの書き込みが成功すれば、即座にそのデータベースから読み取りを行うすべてのクライアントが書き込まれたばかりの値を見ることができなければなりません"
  • 誰かの書き込みが即座に見える => レプリカが1つしかないかのような振る舞い
• 線形化可能性 = 最新性の保証
• 線形化可能性を持たないシステムの例
  • Alice と Bob は別々のレプリカからデータを見ておりレプリケーション遅延の影響を受けてる
  • 1つのレプリカしかないようには見えず最新性が保証されていない => 線形化可能性を持っていないシステム
• 分散システムの文献において レジスタ は KVS で言うキー
  • 1つだけデータを保持できるある領域を指す一意性のある値？
• "したがって、あるクライアントの読み取りで新しい値の1が返されたら、 たとえまだ書き込み操作が完了していなくても、それ以降の読み取りでも全て新しい値が返されなければなりません"
  • そのシステムは Atomicity を持っていないのでは？？Atomicity は Linearizable System において必須ではない？
• Serializable との違い
  • Serializable の関心事はトランザクション、Linearizable の関心事は各レジスタ
  • 例えば書き込みのスキューは各レジスタで見ると特にそれ自体問題ではない(= Linearizable & !Serializable)
  • 2PLを取って書き込みを行ってもレプリケーション遅延が起きているレプリカからデータを取得することはあるのでは…？(= !Linearizable & Serializable)
    • なかった。2PLによる Serializable System は Linearizable でもあるそうな（by コラム）
  • SSI のときはあるトランザクションが他のトランザクションによる書き込みが反映されないスナップショットを使うので最新性が保証されない(= !Linearizable & Serializable) (まだ読みきれてない)

9.3 順序の保証

• "線形化可能なレジスタはデータのコピーが1つしかなく、すべての操作はある時点でアトミックに有効になるかのように振る舞う" => "操作が実行される順序は明確に定まる"
  • 操作が有効になるとはどういうこと…？操作が行われ結果に反映されるということなのかな
  • 順序が明確に定まる => 各操作のリクエスト・レスポンスのタイミングがわかればその順番を少なくとも1つ定めることができるということ？
    • 一意に定まる訳ではない気がする。同じ値を返している連続する読み込みは順不同になるのでは。　
• 順序付けは大事な基本的概念なので再三触れてきた
  • そうだっけ…
  • シングルリーダーレプリケーション => リーダーがレプリケーションログに書き込む順序
  • Serializability => トランザクションがあたかも何らかの順序に従って実行されたかのように振る舞うことを保証
  • 分散システムにおけるタイムスタンプ・クロック => 順序付けされていない世界に順序を持ち込む
    • 分散システムにおける各システムで起きる物事は本質的には違う時間軸で動いている（クロックしか頼れるものがない）
• 順序付けは因果関係を保つのに役立つ
  • サッカーの結果が出る -> Alice が結果を取得する -> Alice が叫ぶ -> それを聞いた Bob が結果を取得
  • この因果関係に違反するようなデータの取得や更新が行われてはいけない（それは線形化可能ではない）
  • 因果に対して一貫している振る舞いをする -> causally consistent (因果律において一貫している)
• 並行して行われた => 因果関係はない
• 全順序と半順序
  • 数値のような異なる2つの要素について必ず大小関係を判定できるもの => 全順序
  • 集合のように、判定できる場合もそうでない場合もあるもの => 半順序
    • { 1 } ＜ { 1, 2 } だけど { 1 } と { 2 } は大小を判定できない
  • 例えば並行した処理を許容するシステムにおいて各操作は半順序、と言えそう
  • 因果律は全順序を定義しない（因果関係のあるものを並行に実行しようとするシステムもある）
• Linearizable にするのがパフォーマンスの面でコストが高い場合、causally consistent にする選択肢を取れる
  • causally consistency だとネットワーク遅延があってもパフォーマンスが劣化しない、というのは並行実行を許容するから？待ってたら因果律違反になるようなネットワーク遅延はない？
• システムを流れるすべての処理のシンプルさとパフォーマンス・可用性のトレードオフになるっぽい
  • 可用性 => Linearizable にすると違反が増えるから？
• "多くの場合、線形化可能性を必要としている用に見えるシステムに本当に必要なのは、因果律における一貫性だけ"
  • どういう場合で線形化可能性が必要？