【読書メモ5-2】Transactional Information Systemsを読み終わった
前回
ノート
はじめに
集中して読む時間を取れたおかげでようやくTransactional Information Systemsをすべて読み終わった。
前回に引き続き、全体的な感想と各章の個別の所感を書き残していきたい。
全体的な感想
トランザクションのACID特性を達成するための理論的なベースと様々に試みられてきた工夫を概観し、全体的な地図を頭に入れることができたという感触がある。
読む前も「ACID特性とは何か」といった問いには答えられる程度ではあったが、読み終わった今ではそれに対する解像度が全く異なっている。トランザクションの分離性をどのような同時実行制御アルゴリズムで担保するのか、不可分性をどのような回復アルゴリズムによって実現するのか、I/Oコスト的に最適なバリアントは何か、といった深掘りした問いにも答えられるようになっている。ある程度咀嚼されて自分のものになっている感触がある。
2023年の今でもトランザクション制御に関する基礎理論の全体像を結ばせてくれるという価値は唯一無二である。興味を持った人にはぜひ読むのをおすすめしたい。
とはいえ非常に長かった。特に第三部は障害からの回復をメインに論じているため、実装的な観点からの解説が多く、それがあまり興味を惹かないのも効いた。非常に長い英文を追い続けた結果、読む速度はそれほど変わっていないが耐性は多少強化された気がする。
章別感想
第3部
第11章 トランザクションの復元
第2部までで考えてきた同時実行制御は、各トランザクションが成功することを前提としていた。第3部で初めて、トランザクションが失敗しても安全にロールバックできるかどうか、に関する正当性が複数導入される。
与えられたスケジュールに関する判定の基準として
- XCSR：ロールバックに関連する操作で拡張したスケジュールがCSRかどうか、という基準。
- PRED：スケジュールの任意のプレフィクスがreducibleかどうか（可換性に基づいて操作を並び替え、逆操作を相殺していったときに逐次的にできるか）、という基準。
次に、生成するスケジュールに課す条件として
- RC (Recoverability)：トランザクションAからデータを読んだトランザクションBは、Aがコミットされるまでコミットされない。
- ACA (Avoiding Cascading Aborts)：コミットされたデータしか読み込めない。
- ST (Strict)：トランザクションが終了するまで、それが書き込んだデータアイテムが読み書きされることがない。
- RG (Rigorous)：STに加え、トランザクションが終了するまで、それが読み込んだデータアイテムが書き込まれることがない。
- LRC (Log Recoverability)：RCかつ、write-write conflictの実行順に制限をかける。
これらの間の関係も導出される。例えば、とか、
とか。
3章の面白さが再燃してとても楽しい章だった。
第12章 障害回復に関する正当性
スケジュールがCSRかつLRCを満たすことを前提としたうえで、データベースが障害を起こしてメモリのデータが揮発したさい、安全に元の状態に復帰するための障害回復アルゴリズムを考えていく。本章はそのとっかかりとしてデータベースやログをフォーマルに定義し、障害回復アルゴリズムの全体像を概観する。
ログって、これまでは単なるデバッグ用の情報を記録するものという感覚だった。が、どうやらデータベース・トランザクションという分野ではそんなふわっとしたものではなく、障害回復を正しく行うための必須コンポーネントであるということを知り、ギャップが埋まった。
第13章 ページモデルにおける障害回復アルゴリズム
トランザクションの実行に関連する情報はログに記録していき、トランザクションのコミット時などのタイミングでログバッファをストレージに書き出す。
障害回復はこのログのスキャンを3回することで実現する。
- analysis pass：ログを読んで、コミットに失敗したトランザクションのリストを得る。
- redo pass：コミットされたトランザクションの内容をデータベースに反映しなおす。
- undo pass：失敗したトランザクションの内容をデータベースから取り除く。
さらに、I/Oコストやログサイズを最適化するために、チェックポイントやログ切り捨てといった手法が導入される。
データベースがキャッシュからストレージに書き出される際のI/Oコストが大きいせいで種々の工夫が必要になっているので、大容量安価なストレージがHDDからSSDに世代交代してI/Oが高速になったらもう少し違ったアルゴリズムが有用になるのかもしれない。
第14章 オブジェクトモデルにおける障害回復アルゴリズム
第13章の内容をオブジェクトモデルに拡張する。
第15章 障害回復における諸問題
12-14章で触りきれなかった雑多な話題。
第16章 メディアの回復
メモリの揮発だけでなく、ストレージそのものが故障や火災で吹っ飛んでしまった場合の対策を考える。
2つの手法を併用する。
- バックアップベースの手法。別ストレージに定期的なバックアップとログのコピーをとっておき、これをもとに復帰する。
- 誤り訂正符号ベースの手法。パリティを分散配置することで、1つのストレージが故障してもそのデータを符号から復元できる。RAIDで実用化されている。
章の冒頭でさすがに周辺のデータセンターをまとめて巻き込む大規模災害は無理、みたいなことを断ってて、あまりに厳密な誠実さに少し笑った。
第17章 アプリケーションの回復
クライアント―サーバ型アプリケーションのような、対話的なトランザクションの回復を取り扱う。主題になるのは、ストレージに保存することで耐障害性を持たせたメッセージキューを利用したメッセージのやり取りである。
著者曰く、近年のeコマースなどで広く用いられるクッキー/URLを用いたセッション管理は「対話的なトランザクションを再発明したものであるが、悲しいことにトランザクション的でない＝ACID特性を満たせないクッキー/URLに頼ってしまっているのが皮肉だ」とのこと。次世代のeコマースシステムはトランザクション的な高信頼手法を採用すると信じている、と書いているが、現在でもステートレスなHTTPとクッキー/URLを用いたアーキテクチャが一般的なことを見ると著者の予測は外れているだろうか。
第4部
第18章 分散トランザクションの同時実行制御
分散システムにはホモジニアスなものとヘテロジニアスなものが存在する。
ホモジニアスなものは、複数のサーバを論理的には単一のユニットとして取り扱うもので、2相ロックによって普通に制御できる。ただし、ロックの取得フェーズから解放フェーズに移行するタイミングをサーバ間で同期しなければならない。
ヘテロジニアスなものは、サーバ間をまたがるグローバルなトランザクションに加え、単一のサーバで実行されるローカルなトランザクションも許容したシステムであり、これによる難しさが追加で発生する。
分散システムってやたら難しそうと身構えていたが、意外とここまでの概念の拡張でいけるものである。
第19章 分散トランザクションの回復
分散システムの回復を行ううえで重要なのは、トランザクションがコミットされたのかアボートされたのかの判断をサーバ間で統一すること。これを2相コミットプロトコル(2PC)を用いて実現する。
具体的には、サーバの中からコーディネータを1つ定め、コミットの開始時に、関わる全サーバにコミット準備を要求する。全てのサーバが準備完了のメッセージを返信してきたらコーディネータはコミットを命令する。一つでも準備ができなかったならアボートを命令する。
2相コミット、聞いたことはあったがこの文脈にあったのかと目から鱗だった。
第5部
第20章 展望
本書の振り返りや将来的な課題について述べられているが、特に印象的なのはデータレプリケーションの話題。
ユーザが世界中に散らばっているインターネットアプリケーションのような状況では、各地域からのアクセスを高速にするため、同一のデータアイテムの複製を各所に配置するような必要が出てくる。それらデータの一貫性を維持するためのreplication control(複製制御)について触れられている。これは今になってさらに重要性を増している話題なので、より最新の文献をあたって見るのも面白そう。
おわりに
せっかく大著をここまで噛み砕きながら読み切ったので、演習問題にもしっかりと答えを出していきたいし、できればここに解答エントリを載せたい。
あとは、現代のSQL標準や、オープンソースRDBMSがどんな発展を遂げていて、どのアルゴリズムが採用されているのかをリサーチしていきたいところ。
