巷で話題のデータ指向アプリケーションデザインが、たしかに良い本だったので、個人的メモ。

1章

信頼性: 障害があっても正しく動作し続ける
- フォールト: ハードウェア、ソフトウェア、ヒューマンのエラー
スケーラビリティ: データやトラフィックが増加しても対応できる
メンテナンス: 開発や運用など様々な人が生産的に関われる
- 運用性、単純性、進化性
head-of-line blocking: 少数の低速なリクエストのために、以降のリクエストの処理が遅れること

2章

リレーショナルモデル: リレーションとタプル、クエリオプティマイザ
Not Only SQL: 書き込みスループット、柔軟なスキーマ
ネットワークモデル: グラフモデルとは別
グラフ型のデータモデル: ノード、エッジ
- プロパティグラフ: 探索しやすい, e.g. Cypher
  - ノード
    - ユニークな識別子
    - 外向きの辺
    - 内向きの辺
    - プロパティのコレクション
  - エッジ
    - ユニークな識別子
    - 始点
    - 終点
    - 頂点間の関係を示すラベル
    - プロパティのコレクション
- トリプルストア: e.g. SPARQL
  - 主語: ノード
  - 述語: プロパティかエッジ
  - 目的語: プロパティかノード

3章

ログ: 追記だけが行われるレコード
インデックス
- ハッシュインデックス: キーのバイトオフセット(場所)を保存する
- コンパクション: セグメント中の重複を削除して最新のものを残す、セグメントはマージできる
- 削除フラグ
- ハッシュマップスナップショットによるリカバリ
- チェックサムによる破壊チェック
Sorted String Table
- ソートされたキー
- 隣接するセグメントを比較してマージソートする
log-structuredストレージ: Log-Structured Merge-Tree、書き込みが速い
ページ指向ストレージ
- Bツリー
  - ソートされたキー
  - 固定サイズのページ
  - 子のページへのポインタ
  - 書き込みがログより難しい
  - write-aheadログ: 追記型のツリーの変更ログ
  - 読み込みが速い
  - ページをロックすればトランザクションを実現しやすい
列指向ストレージ
- 列の圧縮
  - ビットマップエンコーディング: ある値であるかを0/1で表現し、その位置を保存

4章

後方互換性: 古いコードによって書かれたデータを新しいコードが読める
前方互換性: 新しいコードによって書かれたデータを古いコードが読める
Thrift, Protocol Buffers: バイナリエンコーディングライブラリ
- フィールドタグが実用上変更できない、追記のみ
- 前方互換性はある
- 後方互換性は条件付き
Avro
- ライターとリーダーのスキーマが同一でなくてよい、差分を解決する
スキーマのメリット
- コンパクト
- ドキュメント
- 互換性の確認
- 型チェック
RPCの問題
- ネットワークのリクエストは予測不能
- タイムアウト
- 冪等でない可能性
- ネットワークのレイテンシによる遅延
- 渡されるデータのサイズ
- 言語の差異
非同期のメッセージパッシングシステム: メッセージを一時保存して中継する
- 信頼性を高められる
- 受信側のアドレスやポートを知る必要がなくなる
分散アクターフレームワーク
- ロジックをアクターにカプセル化
- ネットワーク経由で送信

5章

レプリケーション: 同じデータのコピー
- シングルリーダー
- マルチリーダー
- リーダーレス
同期のタイミングと可用性のトレードオフ
フォロワーの障害: キャッチアップリカバリ
リーダーの障害: フェイルオーバー
- 新しいリーダーの選出
- 書き込みはすべて反映されているか?
- 古いリーダーが復活したら?
- スプリットブレイン
レプリケーションログ: 変更のキャッチアップ
- ステートメントベース: 乱数などに弱い
- write-aheadログ: 変更がストレージと結びついている
- 論理ログ
- トリガーベース: カスタムコードなど、バグりやすい
read-after-write: 書き込んだものを読み込めるか
monotonic read: レプリカが複数ある時などで、同じものを読み取れるか
一貫性のあるプレフィックス読み取り: ある順で書き込まれたものが、同じ順で読み取れるか
マルチリーダー
- 書き込みに強くなる
- 衝突の解決が必要
  - Last Write Win: 時刻が一致しない場合不正確
  - マージする
- オフラインでクライアントが動くとき便利
- レプリケーションのトポロジーをどうするか
リーダーレス
- 複数のレプリカに書き込む
- 複数のレプリカから読み取る
- クオラム: nノード、w個に書き込む、r個から読み取る、w + r > n
  - sloppy quorum: n以外のノードへ書き込みや読み取りを受け付けること
- 並列で行われる書き込みをどう処理するか?
  - イミュータブルなキーを利用する
  - バージョン番号を使う
  - 集合な値を使う

6章

パーティショニング: シャーディング
キーによるパーティション
- ホットスポットに注意する
- ハッシュによるパーティション
- 範囲検索
パーティションしすぎると場合によっては読み取りが遅くなる
セカンダリインデックス
- ドキュメントベースのパーティション
  - ローカルインデックス: 同じパーティションに存在する値のインデックス
    - 検索のために全てのパーティションを読み取る可能性がある、スキャッタ・ギャザー
- 語ベースのパーティション
  - 語によってパーティションが決まる
  - グローバルインデックス
  - 書き込みが複雑になる
パーティションのリバランシング
- パーティション数をノード数より大きい値に固定する
  - リバランシングしやすい
  - データ量が変動する場合は無駄が多い
- 動的なパーティション
  - データサイズが均一になるようにする
  - ノード数に比例するようにする
- 自動か手動か
リクエストのルーティング: サービスディスカバリ
- ルーティングをするコンポーネントはどうやってパーティションの割り当て変化を検知するのか
- Zookeeperを使ったメタデータ管理

7章

トランザクション: コミット、アボート、ロールバック
- Atomicity: All-or-Nothing, Abortability
- Isolation: 並行して実行されたトランザクションがお互いから分離されている、Serializability
複数のオブジェクトの操作のトランザクション
- 1行1列だけでなく、複数を対象とする操作が一般的
- 分散トランザクション: パーティションに対して
Isolation: パフォーマンスとのトレードオフ
- read commited
  - コミットされたもののみを、読み書きする
  - 行レベルロック
  - nonrepeatable read, 読み取りスキューが起こる
- スナップショット分離
  - トランザクション時点のDBの (対象オブジェクトの) スナップショットを使う
  - Multi-Version Concurrency Control
  - repeatable readとも呼ばれる
  - compare-and-set: 読み取り時から値が変わっていない場合に限り値を更新する、更新ロストの回避
  - 書き込みスキューやファントムを防げない
直列化可能な Isolation
- 2PL
  - リーダーやライターが互いをブロックする
  - 共有ロックと排他ロック
  - デッドロックが起こる
  - 長いトランザクションにより処理が遅くなる可能性がある
  - ファントムを避けるために
    - 述語ロック: 条件にマッチするオブジェクトのロック
    - インデックス範囲ロック: 述語ロックの近似的なもの
- 直列化可能なスナップショット分離
  - 楽観的な並行性制御
  - リーダー・ライター間でブロックしない
  - コミット時点で直列化可能かチェックする

8章

分散システムと部分障害
ネットワーク
- フォールト
- タイムアウト、遅延
- 同期/非同期
クロック: 時刻、単調増加
- 同期、正確性
- 信頼区間: 水晶発振器の変動の期待値、NTPサーバーの不確実性、ネットワークのラウンドトリップ
- Google Spanner TrueTime API
- 分離のためのトランザクションの順序関係に対するオプション
- リーダーであることのリースがクロックの同期を前提とする
他のノードの状態はメッセージの交換で把握する
フェンシングトークン
- リースのたびにフェンシングトークンを渡す
- クライアントは書き込みリクエスト時にトークンを付与する
- 古いトークンは拒絶される
- Zookeeper
ビザンチン障害
- ノードは嘘をつくか
- 嘘をつかれても耐性を持つ
  - e.g. ブロックチェーン
- 分散データシステムでは、基本ないと想定できる
- 弱い嘘に対する防衛: 設定ミス、バグ

9章

合意: Consensus
一貫性: 整合性
線形化可能性: Linearizability
- ある順で行われた処理の結果が順番通りに観測できる
- 直列化と異なり、オブジェクトについて
- 使う場面
  - ロックとリーダーの選出
  - 制約やユニーク性の保証
  - 異なる通信チャネルの間での整合性
因果律
- シーケンス番号: 論理クロック
- ランポートタイムスタンプ
  - カウンタ、ノードID、過去に見た最大のカウンタ
- 全順序のブロードキャスト
  - Zookeeper, etcd
  - ステートマシンレプリケーション
  - compare-and-setの利用
  - 合意と等価
アトミックなコミット
- 2PC
  - 1. 準備 => 2. コミット
  - コーディネータ: トランザクションマネージャ
  - コーディネータに障害がおこるとブロッキングがおこる
- ヘテロジニアスな技術間のトランザクション
  - X/Open XA: コーディネータのAPI
  - XAがSPFになる危険性
耐障害性を持つ合意
- 一様同意
- 整合性: integrity、2回決定しているノードがない
- 妥当性: vを決定していたら、vを提案しているノードがある
- 修了生: クラッシュしていないノードは何らかの値を決定する
メンバーシップと協調サービス: ノードの死活監視

10章

Systems of record: source of truth
導出データシステム
バッチ処理
UNIXの哲学
- 一つのことだけをうまくこなす
- プログラムの出力は他の未知のプログラムの入力となると想定する
MapReduce
- ストレージが多様
- 処理モデルが多様
- 障害に備えた設計
データフローエンジン

11章

ストリーム処理
パブリッシュ/サブスクライブモデル
メッセージブローカー
- データの有限期間での保持
- データ変更の通知
- クライアントからの承認 (acknowledgement)
- ログとしての利用
  - オフセット=シーケンス番号
異なるシステムでの同期のための利用
- ログとしてのブローカーを読み出せば同じように導出できる
- 変更データキャプチャ: change data capture、DBをミュータブルな方法として利用
- イベントソーシング: イミュータブルなイベント、追記のみ
- 並行性の制御: 書き込みと読み取りビューの同期実行
- イミュータビリティの限界: パフォーマンス、プライバシー
時刻
- イベントの時刻 or 処理の時刻
- ウィンドウ
excactly-once: effectively-once?
- 冪等
- マイクロバッチ処理: ストリームを分割する
- アトミックなコミット

12章

データシステムの将来
信頼性、スケーラビリティ、メンテナンス性
ラムダアーキテクチャ: イミュータブルイベントの追記、バッチ処理とストリーム処理の併用
フェデレーションと解体: 読み取りと書き込み
- ログ
導出された状態の監視
- ステートフルでオフライン動作できるクライアント、それへのプッシュ
- クライアント/サーバーに対するエンドーツーエンド
エンドツーエンド
- 冪等のため
- 重複の抑制のため
- 操作識別子のため
機械学習、バイアス、説明責任、プライバシー