$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

データ指向アプリケーションデザイン 第Ⅱ部 分散データを読んだ

データ指向アプリケーションデザイン 第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のようなツールは合意、障害検出などで重要な役割を果たす

データ指向アプリケーションデザイン 第I部 データシステムの基礎を読んだ

今更ながらデータ指向アプリケーションデザインを読んでいる。第I部 データシステムの基礎まで読んだ。とにかく面白くて良い。

自分は「3章 ストレージと抽出」がもっとも面白いと感じ、とくにSSTableとLSMツリーというシンプルなアルゴリズムで多くの問題を解決できていることに感動を覚えた。昔もマージソートに感動した覚えがあるけど、今回もマージソートはすごいという気持ちになる。また列指向データベースの基本的な考え方や圧縮効率を学べたのも良かった。

「4章 エンコーディングと進化」においては、変化しやすさを担保するための後方互換性(= 新しいコードが古いデータを読める)と前方互換性(=古いコードが新しいデータを読める)についてまとめた上で、いくつかのデータフローの中で何を満たすべきなのかがまとめられていた部分が良かった。たとえばデータベースとのやりとりだと何があれば前方・後方互換性が保たれるか、REST APIだとどうか、非同期のメッセージパッシングの送受信だとどうかなどが具体的に語られていた。

まだまだ先は長いけど地道に読んでいこうと思う。

読書ノート

### 1章 信頼性、スケーラビティ、メンテナンス性に優れたアプリケーション
- 本書はソフトウェアシステムにおける重要な3つの課題に焦点 315
    - 信頼性
        - フォールとがあっても正しく動き続ける
    - スケーラビリティ:負荷の増大に対してシステムが対応できる能力
    - メンテナンス性
        - 運用性:運用チームが扱いやすい
        - 単純性:新しいエンジニアが理解しやすい
        - 進化性:システムを変更しやすい
- レスポンスタイムはクライアント側で計測しなければ、ユーザーの視点に立てない 596

### 2章 データモデルとクエリ言語
- グラフストアは、頂点と辺の概念がある 1462
    - 任意の頂点を辺によって接続できる
    - 任意の頂点に対する入出力の辺を効率的に見つけ出せる。グラフを探索できる
    - 辺に異なるラベルを使うことで、単一グラフの中にさまざまな情報を保存する

まとめ 1761
- リレーショナルデータベース以外だと、以下の二つに分かれる
    - ドキュメントデータベース:データが自己完結しているドキュメント群で、リレーションがそれほど存在しないものをターゲット
    - グラフデータベース:あらゆるもの同士に関係が存在するようなユースケース
        - データのほとんどが多対多の場合リレーションモデルは不得意

### 3章 ストレージと抽出

ハッシュインデックスとlog-structuredなデータ保存
- log-structuredな仕組みでのデータファイルのコンパクションおよびマージ処理 2019
    - ログがあるサイズになったらファイルをクローズする
    - 凍結されたセグメントでは最新の値だけ残しマージする。複数のセグメントも最新のものは後のファイルに入っているはずなので、それを踏まえてマージ
- ハッシュインデックスでは各セグメントにインメモリのハッシュテーブルがある 2019
    - キーに対する値を見つけるには、最新セグメントのハッシュマップチェック -> なければ2番目の、...
- log-structuredな仕組みでは、レコードの削除を特別な削除レコード追加で代替できる 2041
- log-structuredな追記のみの仕組みのメリット 2041
    - セグメントの追記とマージはシーケンシャルな処理なためランダムな書き込みより高速
    - 並行処理やクラッシュリカバリがシンプル
    - データファイルのフラグメンテーションが少ない
- ハッシュテーブルのインデックスの制約 2068
    - メモリ内にキーが収まらなくなるとだめ
    - 範囲クエリの効率が悪い
    - -> SSTableとLSMツリーへ

SSTableとLSMツリー
- ソート済み文字列テーブル(Sorted String Table、SSTable) 2068
    - セグメントファイルのフォーマットに2条件を追加
    - キーでソートされていることという条件を追加
    - マージされたそれぞれのセグメントファイル中には、それぞれキーは一度だけしか現れないという条件を追加
- SSTableの利点 2095
    - マージソートできるためメモリ効率が良い
    - 全てのキーをインデックスに残さなくても、一部だけでどのあたりにそのキーがあるか分かる
- どうやってキーごとにソートしてデータを保存する? 2113
    - 書き込み時点ではメモリで管理、一定より大きくなったらディスクにセグメントとして書き込み
    - クラッシュからの復帰のためだけにディスク上に全ての書き込みを即座に追記するファイルを用意。セグメントをディスクに書き込むたびに削除
- このようなSSTableとコンパクション・マージを踏まえたインデックス構築のような構造をLSMツリー(Log-Structured Merge-Tree)と呼ぶ 2136
- 存在しないキーのルックアップの高速化のためにブルームフィルターが使われる 2164

- LSMツリーは通常書き込みを高速に処理でき、Bツリーは読み取りが高速に行えるものとみなされている 2243

オンライン分析処理(OLAP)と列指向データベース
- データウェアハウスではしばしば大量の列を持つことが多い。100〜数百。アクセスパターンは数列しかなく、それを効率化するために列指向データベースが使われる 2578
- 列指向ストレージの考え方:1つの行に含まれる全ての値をまとめて保存するのではなく、それぞれの列に含まれる全ての値をまとめて保存する 2605
- 列指向ストレージは圧縮に適している 2626
    - 行数よりも列の中身の種類数の方が少ないことが多いため
    - ランレングスエンコーディング
        - WHERE句でのOR条件はビットのORに、AND条件はビットのANDにマッピング可能
    - 列ストレージでSSTableのような順序強制の仕組みを使うと列の圧縮を助けられる 2670
- 列ごとに圧縮されていると、ソートされたテーブルの途中に行を挿入しづらい。これはLSMツリーのようにインメモリストアに書き込み -> 十分に貯まったらディスク上の列ファイルとマージ圧縮という方法を使う 2702
    - 読み込みは列データとメモリの両方から見る

まとめ
- ストレージエンジンは、トランザクション処理(OLTP)に最適化されたものと、分析(OLAP)に最適化されたものの2つに分類
    - OLTPでは莫大なリクエストと少数のレコード
    - OLAPでは少量のクエリと、多くのレコードスキャン
        - ディスクの帯域がボトルネックになるので列指向が使われる
    - 気づき: Web APIはOLTP、バッチ処理はOLAP
- OLTPには2つの考え方のストレージエンジン
    - log-structured:ファイルへの追記と古くなったファイルの削除だけ行える。SSTable、LSMツリー
    - インプレース更新:ディスクを更新可能な固定サイズのページの集合として扱う。Bツリー

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

- ごく一時的な目的の場合以外では、特定の言語の組み込みエンコーディングは使うべきでない 3013
    - 多言語とのポータビリティ
    - 前方および後方互換性の不足
    - 効率性
- Protocol Buffersなどのバイナリフォーマット 3114
    - 前方後方互換性を維持するためには 3155
        - フィールド名は変えられるが、フィールドのタグは変更できない
        - フィールドの追加
            - 新しいタグ番号なら、古いコードはそのフィールドを単純に無視するため問題ない。アノテーションからスキップするバイト数を把握できる。この特性で前方互換性が保たれる
            - タグ番号が変わらないので後方互換性は保たれる。しかし新しいフィールドは必須にできない(MySQLのスキーマと同じ)
        - フィールドの削除
            - 必須フィールドは削除できない、オプションフィールドは削除できる
- JSONなどのスキーマレスなテキスト形式と比較して、スキーマありのバイナリエンコーディングの優れた性質 3342
    - はるかにデータがコンパクト。フィールド名が必要ない
    - スキーマ自体がドキュメントになる
    - スキーマの変更をみるだけで前方後方互換性の維持チェックをデプロイ前にできる
    - コード生成しやすい

データフローと前方後方互換性
- データベースの場合、後方互換性は必須、前方互換性が求められることもしばしばある 3397
    - 新しいフィールドのことを解釈できなくても、古いコードが新しいフィールドに手を加えてはならない
- RPCやRESTの場合、すべてのサーバーがまずアップデートされ、クライアントはその後にアップデートされるという仮定をおいてシンプルにしてもいい 3569
    - 保つ必要があるのは古いクライアントからのリクエストを新しいサーバーが解釈できることと、新しいレスポンスを古いクライアントが壊れずに解釈できること
        - この特性はRPCが使うエンコーディング特性が引き継がれる
- 気づき: メッセージブローカーの場合は、RPCのレスポンスがない版として考えたらいい? 3597
    - 分散アクターフレームワークとかだと難しいとかもある

まとめ
- ローリングアップグレードをする場合、システム内を流れるすべてのデータは、後方互換性と前方互換性が保たれる方法でエンコードされなければならない
    - 後方互換性 = 新しいコードが古いデータを読める
    - 前方互換性 = 古いコードが新しいデータを読める
- データエンコーディングの互換性について
    - プログラミング言語固有のエンコーディングは、しばしば前方および後方互換性を欠いている
    - JSONなどのテキストフォーマットの互換性は利用の方法に依存する
    - Protocol Buffersなどのスキーマを持つバイナリフォーマットでは、前方および後方互換性の背マンティクスが明確に定義されている
- 互換性について、それぞれのデータフローで気をつける必要がある
    - データベースの書き込みと読み取り
    - RPCやREST APIのリクエストとレスポンス
    - 非同期のメッセージパッシングの送信と受信

MySQLのREPEATABLE READとREAD COMMITTEDのロック状況をdata_locksから観察する

前回MySQLのREPEATABLE READとREAD COMMITTEDの違いを知るために色々試した - $shibayu36->blog;という記事を書いたところ、yoku0825さんにMySQL 8.0以降だとperformance_schema.data_locksが使えると教えてもらったので試した。

テーブル定義

CREATE TABLE `posts` (
  `id` int NOT NULL,
  `title` varchar(255) NOT NULL,
  `body` text NOT NULL,
  UNIQUE KEY `id` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

両方ともREPEATABLE READ

> select * from posts;
+----+--------+-------+
| id | title  | body  |
+----+--------+-------+
|  1 | title1 | body1 |
|  2 | title2 | body2 |
+----+--------+-------+

# トランザクション1
begin;

# トランザクション2
begin;

# トランザクション1
UPDATE posts SET title = 'title2updated' WHERE id >= 2 and id < 5;

# トランザクション2
insert into posts (id, title, body) values (10, 'title10', 'body10'); # -> lockされる

この時にperformance_schema.data_locksを確認する。

> SELECT ENGINE_LOCK_ID, ENGINE_TRANSACTION_ID, OBJECT_NAME, INDEX_NAME, OBJECT_INSTANCE_BEGIN, LOCK_TYPE, LOCK_MODE, LOCK_STATUS, LOCK_DATA FROM performance_schema.data_locks where OBJECT_SCHEMA = 'repeatable_read_test';
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| ENGINE_LOCK_ID                    | ENGINE_TRANSACTION_ID | OBJECT_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE          | LOCK_STATUS | LOCK_DATA              |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| 275347546352:1579:275213534048    | 12672                 | posts       | <null>     | 275213534048          | TABLE     | IX                 | GRANTED     | <null>                 |
| 275347546352:516:4:1:275213531136 | 12672                 | posts       | id         | 275213531136          | RECORD    | X,INSERT_INTENTION | WAITING     | supremum pseudo-record |
| 275347545496:1579:275213527904    | 12670                 | posts       | <null>     | 275213527904          | TABLE     | IX                 | GRANTED     | <null>                 |
| 275347545496:516:4:4:275213524912 | 12670                 | posts       | id         | 275213524912          | RECORD    | X,REC_NOT_GAP      | GRANTED     | 2                      |
| 275347545496:516:4:1:275213525256 | 12670                 | posts       | id         | 275213525256          | RECORD    | X                  | GRANTED     | supremum pseudo-record |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+

これを観察すると

  • トランザクション1がテーブルのIXロック、id 2のレコードロック、ギャップロックを保持している
  • トランザクション2がテーブルのIXロック、INSERTでのギャップロックで待ち状態

という状況を観察できる。確かにREPEATABLE READ時にレコードロック+ギャップロックを取っていることがわかる。

UPDATE側がREAD COMMITTED

# トランザクション1
set session transaction isolation level read committed;
begin;

# トランザクション2
begin;

# トランザクション1
UPDATE posts SET title = 'title2updated' WHERE id >= 2 AND id < 5;

# トランザクション2
insert into posts (id, title, body) values (10, 'title10', 'body10'); # -> lockされない

この時にperformance_schema.data_locksを確認する。

SELECT ENGINE_LOCK_ID, ENGINE_TRANSACTION_ID, OBJECT_NAME, INDEX_NAME, OBJECT_INSTANCE_BEGIN, LOCK_TYPE, LOCK_MODE, LOCK_STATUS, LOCK_DATA FROM performance_schema.data_locks where OBJECT_SCHEMA = 'repeatable_read_test';
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
| ENGINE_LOCK_ID                    | ENGINE_TRANSACTION_ID | OBJECT_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE     | LOCK_STATUS | LOCK_DATA |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
| 275347546352:1579:275213534048    | 12675                 | posts       | <null>     | 275213534048          | TABLE     | IX            | GRANTED     | <null>    |
| 275347545496:1579:275213527904    | 12674                 | posts       | <null>     | 275213527904          | TABLE     | IX            | GRANTED     | <null>    |
| 275347545496:516:4:5:275213524912 | 12674                 | posts       | id         | 275213524912          | RECORD    | X,REC_NOT_GAP | GRANTED     | 2         |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
  • トランザクション1がテーブルのIXロック、id 2のレコードロックのみ。ギャップロックはなし
  • トランザクション2がテーブルのIXロック。INSERT時に待たされていないためdata_locksに内容が表示されない

確かにREAD COMMITTEDにするとギャップロックを取っていないことがわかる。

まとめ

performance_schema.data_locksを使うことでロック状況が可視化できた。以前PostgreSQLでこういうものを使ったことがあったが、MySQL 8.0からperformance_schema.data_locksというものが使えると知らなかったのでこれから便利に使えそうだ。