最近データ分析をしていて複雑なSQLを書き始めた結果、SQLの概念が理解できてなくて上手くクエリを書けないことに気づいた。そこで概念を理解するために「達人に学ぶSQL徹底指南書」を読んだ。
今まさに欲しい情報が詰め込まれていて良かった。本を読む前はCASE式やウィンドウ関数の概念、SQLの前提となる集合論の考え方、NULLが条件に含まれた時にどのような動きをするかを理解できていなかった。しかしこの本にはその辺りが全て含まれていたため概念を理解でき、その結果SQLを書くスピードが上がった。 それ以外にもいろんな集計をする事例も書かれていたため、SQLのチートシートとしても使えそう。
特に10章までの情報は非常に参考になった。SQLをちゃんと理解したい人はそこまで読むと良さそう。
最近仕事では機能開発ではなくデータ分析の仕事をしばらくやっているのだが、同僚から「本物のデータ分析力が身に付く本」というムックが良かったと聞いたので読んでみた。
この本は「データを集計し計算する」といった、いわゆる一般的にはデータ分析のメインと考えられていていろんな書籍で語られているような部分には焦点を当てず、その前後で何をすべきかを語ってくれている。たとえば
自分もいきなりデータを見るのではなくてちゃんと仮説を立ててから調査すべきという心構え自体は持っていたが、この本を読んでデータ分析実行の前にここまで時間をかけて事前に設計と事前チェックをするのかと勉強になった。
ちなみにこの本を参考にして仕事中に調査したいことのデータ分析設計書を作っていたが、確かに設計書は良い。何が良いかというと
まさにdesign docと同じようなメリットが得られている。この調子で分析をやっていきたい。
こんな感じでデータ分析をするエンジニアはぜひ読んでおきたい一冊だと思った。演習もついていて知識も深めやすいので是非。
## プロローグ
- どんな計算をしたかの技術論を聞かされても意思決定者は苦痛。本当に共有すべきはデータ分析の一連のストーリー 7
- 1. 何のために、何を知ろうとしたか
- 2. そのためにどんな仮定を置き、どの範囲を考えに入れたか
- 3. どんなデータを使って、どんな意味合いの数字を出したか
- データ分析の心構え 9
- 必ず課題アプローチをする 10
- 「課題」を決める
- 課題を解決するための「問い」を決める
- 問いに答えるための「データと分析方法」を決める
- データ分析の正しさは「プロセス」で評価 11
- ![[Pasted image 20240328115652.png]]
- すぐに平均値を出す、集計表を作るといった「計算」を始めてはならない
- 計算の前にやること 11
- 1つ目: 前述の一連のストーリーを設計する
- 1. 何のために、何を知ろうとしたか
- 2. そのためにどんな仮定を置き、どの範囲を考えに入れたか
- 3. どんなデータを使って、どんな意味合いの数字を出したか
- 2つ目: データの信頼性と傾向をチェック
- 3つ目: すでに明らかにした「知りたいこと」と「データの傾向」とを照らし合わせて適切な分析方法を選ぶ
- 計算の後にやること 12
- 分析の結果を正しく評価し解釈する
- 計算結果誤差、AとBは本当に差があるのか、認知バイアスの思い込みに囚われていないか
- 分析の結果を正しく使ってもらえるように表現する
- 要するに何が言えるのか、だから何をすべきなのかを、ビジネスの文脈に落とし込んで端的に語れなければならない
## データ分析を設計する
- 分析の概念図 20
- ![[Pasted image 20240328144334.png]]
- 問題領域 = 課題解決のための問い
- 評価軸 = 何を良い施策とするかの判断軸
- 要因 = それぞれの評価軸に左右するもの
- ![[Pasted image 20240328144522.png]]
- 利点：重大な見落としを防ぐ、無駄なデータ収集を防ぐ、作業の途中で迷子になるのを防ぐ、結果を相手に納得してもらい使ってもらえる、データアプローチになるのを防ぐ
- 概念図を書くステップ 23
- ![[Pasted image 20240328144752.png]]
- 問題領域の決定では、 26
- 1. 問題領域を出す。もっと広い可能性ともっと狭い可能性を書き出し、その中でどの問いが最適か見比べる 26
- 2. 問題領域を選ぶ。この問題領域を選んだ理由を説明できるようにし、関係者と合意をとる
- 評価軸決定のプロセス 30
- 1. 評価軸を挙げる
- コツは
- ボトムアップ式：問題領域に関わりそうな言葉をたくさん出してグルーピングしてみる
- 芋蔓式：1つの評価軸から、その評価軸が良ければどんなものでもいいか？と問う。「安くて機能が足りていれば、どんな機種でもいいのか？」
- 2. 評価軸を選ぶ
- 一般には2~4個程度の方が良い
- 選んだ時に関係者と議論して合意すべき
- 問題の具体的記述のプロセス 33
- 主語、問題領域、評価軸をつなげて、1つの文で表す
- 言語化することでブレない分析が可能
- 分析の方向を修正するラストチャンス
- 要因の列挙のプロセス 34
- 評価軸に対してブレストを行う
- 要因の選択プロセス 38
- 1. 重要度で仕分けする
- 重要度の3視点
- 問題や評価軸を大きく左右する
- その業界の常識として、考慮しないと説得力がなくなる
- 上のいずれかの視点で、重要と判断した理由を関係者に説明できる
- ![[Pasted image 20240328160848.png]]
- 必要あれば判断理由の補足も書く
- 注意点
- 重要度と入手しやすさは別で考える
- 重要度の仕分けは、すべての評価軸の全ての要因を同じ1枚の紙の上で行う
- 判断基準のブレをなくす
- 重要度中に集中したら、さらに仕分けする
- 2. データの入手しやすさで仕分けする
- 入手しやすさ判断の2視点
- 入手方法が想像できる
- 入手できなくても、類似のデータなどから推測できそうと考えられる
- アンケートなどで自分で調査できると考えられるなら入手可能で良い
- 3. 分析する要因を決定する
- 右上を分析する
- ![[Pasted image 20240328161813.png]]
- 右下で不可欠な例：ウイルス耐性
- 部品の配置・連結プロセス
- 1. 問題領域と評価軸を書く
- 2. 評価軸に要因をつなげる
- ![[Pasted image 20240328162109.png]]
- 3. 要因をグルーピングする
- ![[Pasted image 20240328162140.png]]
- 4. 要因同士の関係を推測してつなげる
- ![[Pasted image 20240328162205.png]]
- 5. 分析の流れを説明できるか確認する
- 一連のストーリー3ステップを、概念図も使いながら報告できるかを確認する
- ![[Pasted image 20240328162716.png]]
## データを事前にチェックする
- ヒストグラムを書かずに集計すると、データに外れ値があることにすら気づけない 53
- データを「可視化」した方が平均値などを「集計」するよりもデータの実態がよく分かる
- データの事前チェックの必要性 53
- 怪しいデータを使って分析をしないように
- データの傾向を知り、どの分析方法が適切かを決定する
- データを事前にチェックする4つのポイント 54
- データの出所チェック 55
- 5W1Hチェック: 誰が、いつ、どこで、何を、なんのために、どのようにして作ったデータなのか？を確認することで、信頼度・偏りのなさ・正確性をチェックする
- 一次情報を使う
- データ全体概要のチェック。データ全体を、馴染み深く感じるまで視る 57
- 1. データのサイズ確認
- 2. データがどのように並んでいるか
- 3. それぞれのデータの意味合いを理解する
- 4. 値の大体の規模（桁）と、単位を確認する
- 5. 欠損値、外れ値の「有無・多少」を見る
- 6. その他、目立つ特徴を頭に叩き込む
- 注意: データのサイズ確認、データの並び、データの意味合いは、生データを自分で確認しながら調査する 57
- 何列・何行か、どのようなデータの塊があるか、各列の見出しと意味を解釈、各列ごとの気づき、一見して欠損値や外れ値が目立つか
- 個別の値のチェックを行うときは、欠損値、外れ値、データの方向の3つをチェックする
- 欠損値の特定の便利手法 62
- 欠損値の中身がNULLだけでない場合や、空白が入っている場合などにも対応できる
- 外れ値特定の3ステップ 65
- 有無：ヒストグラムや散布図などでデータを可視化し、外れ値の有無を判断
- ヒストグラム：1変数の分布の形がわかる。2変数以上には不便
- 散布図：2変数の関係がわかる。分布の形はわかりにくい
- 値：最大値・最小値を算出して、外れ値の値を知る
- 場所：データが大きい場合、フィルタ機能を使って最大値や最小値に等しいデータが「どこにあるか」を特定する
- 外れ値のサインをつけておくと、たとえ取り除かなかったとしても取り除かなかった理由が説明できる
- データの方向をチェックする 70
- 実はサービス評価が1の方が「良い」だったみたいな
- クレンジングのステップ 71
- 欠損値の除外
- 他の値で埋める時は、なぜ埋めた、どのように埋めたのかのメモを残す。これがないとデータの恣意的な改竄を疑われる
- 外れ値の除外
- 外れ値自体には学びが多いと心構える
- データの方向の逆転
- 直感と数字の大小が異なる場合に、データ方向を逆転する
- 注意
- 欠損値や外れ値だからといって無条件に除いて良いとは限らない。新しい発見が潜んでいることもある
- クレンジング後にも最初に戻れるように生データを必ず残す
- クレンジング後にデータの傾向をチェックする 76
- 1. データを再び可視化
- 2. 値がどの辺に分布しているかをチェック
- 3. どんな形に分布しているかをチェック
## 分析方法を選ぶ
- 代表値 = 平均値、中央値、最頻値
- 平均値が有効な4条件 83
- 中央値が有効な条件 85
- 最頻値が有効な条件 87
- 3つの代表値のメリットデメリット 87
- 万能な代表値はなく、どんなに適切な代表値を選んでも生データに比べれば多くの情報が失われることに注意 88
- クロス集計
- 効果 91
- 注意点 95
- 先入観を捨てるため、あらかじめ想定した要因だけ分析して終わらず、多くの組み合わせを試す。色々な組み合わせでクロス集計表や散布図を作る
- 密接に関連する項目は全て出す
- 例) 正規雇用数と非正規率だけ出すのはだめ。同時に雇用合計数を出すと別の観点が見えてくる
- データ数や構成比も一緒に出す
- データ数や構成比のクロス集計表を用いないと、そのクロス集計が妥当かの判断ができない
## 標準偏差
- 標準偏差の使い道 120
- 多様性や格差を定量化する、比較する
- サービスレベルを均質化する施策の導入前後で、効果を比較可能になる
- 不確実性を定量化する、比較する
- 為替レートの変動の激しさを定量化し、今後も同じ変動幅と仮定したときの不確実性を算出可能
- リスクを定量化する、比較する
- 投資のリスクの可視化など
- 平均値の信頼性の判断と比較
- 品質を管理する
- +-3標準偏差の場合0.27%となるので、これを使うと外れ値認定できる 131
## グループ間の差の確からしさを検証する
- 平均値の代償関係の確からしさは、以下の三つで決まる 149
- 平均値の差が大きいほど信頼できる
- ばらつきが小さいほど信頼できる
- データ数が多いほど信頼できる
- 他人の分析結果を聞いた時は、この三つを必ず確認すること
- 検証ツールのp値=全体では差が無い確率（危険率）を何%まで許容するかは状況による 153
- 店の陳列棚をちょっと変えるだけなら30%くらいの失敗は許容できるかもしれないが、人命がかかる話なら0.01%の失敗も許容できないかもしれない
- 差の検証を行うときは、比較集団が対応ありか対応なしかに注意すること 155
## 分析結果の受け止め方と伝え方
### 分析結果の解釈の思い込みを避ける
- 分析をするときは、認知バイアスや印象操作に注意して解釈の誤りを防ぐ必要がある 161
- データ分析中は、思いついた仮説にいつの間にか囚われて信じてしまう、仮説確証バイアスになりやすい。エラーを防ぐためには 164
- 無意識にとらわれている仮説はないか、自省する
- 考えたこともない（関係なさそうな）要因でも、もしかして関係していないか、あえて分析する
- 極端な数字によるエラーであるアンカリング：数字を提示されると、その数字に意味がなくても、判断がその数字に影響される 166
- この誤りを起こさないように
- 意図的に余分な情報が提示されていないか、チェックする習慣をつける
- 値の大きさで、差がある・ないような印象が提示されていないか、いつも冷静に検証する習慣を付ける
- 言葉の表現によるエラーであるフレーミング：同じ意味でも表現で判断が変わってしまう 167
- 防ぐために
- ポジティブ（ネガティブ）な結論に誘導していないか、疑う習慣を付ける
- 同じ事象を、ポジ<->ネガと逆の言い方に置き換えてみて、自分の判断が変わらないかを確認する習慣をつける
- 情報の順序によるエラーであるプライミング：先にポジティブな事象を提示することで、ネガティブな事象を目立たなくしている 169
- 防ぐために情報の提示順序を逆にしてみて、自分の判断が変わらないかを確認する習慣を
- 偽の関係によるエラーである擬似相関：2つの現象が、共に観測されるだけで、一方が他方の原因だと思い込みやすい 172
- 防ぐために、複数の因果モデルを比較し、どれが論理的にもっともらしいか、どれが常識的に理解しやすいか、考える習慣を
- 分析結果の解釈におけるバイアスのまとめ 173
- 思い込み（仮説確証バイアス）
- 無意識にとらわれている仮説はないか、他に仮説はないか？
- 極端な数字（アンカリング）
- 余分な情報や極端な数字が、意図的に提示されていないか？
- 言葉の表現（フレーミング）
- 逆の言い方をした時に判断が変わらないか？
- 情報の順序（プライミング）
- 情報の提示の順序に引きずられていないか？
- 偽の関係（擬似相関）
- 他の因果モデルを考えたか？単なる偶然ではないか？
### 分析結果の表現で誤解を招かない
- 数字自体を使ってもらうには、数字の実質的な意味合いを、相手の判断に刺さる視点で伝えることが大切 181
- 誤魔化されないためのチェックポイント 182
- 報告者の立場・思想信条・利害などから、どのような結論に誘導したがっているかを読むことで、鵜呑みを防ぐ
- 調査方法、集計方法、強引な解釈に注目する習慣を
- サンプル数は十分？
- 偏りなく公平にサンプリングされている？
- どんな質問文、どんな選択肢で聞いたか？
- グラフや言葉の表現が操作されていないか？
- 不都合な数字が意図的に隠されていないか？
- 集計方法が適切か？
- 解釈が客観中立か？
データ指向アプリケーションデザイン 第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のようなツールは合意、障害検出などで重要な役割を果たす
