イントロダクション
これは@kumagiが一人でトランザクション技術に関する話をまとめていくアドベントカレンダーである。
トランザクション技術は多岐にわたり、複雑に絡み合い、DBの中で巨大な密結合コンポーネントを生み出している。そのためその中身を語るアドベントカレンダーも完全に順序付けて章立てしていくのは難しい。そのため様々な側面から一日に読めそうな文量の記事毎にまとめてアドベントカレンダーとするので、25日も話題が持つのかはさておき必ずしも記事の区切りは技術としての区切りの良さとは関係がない。
しかも初めの数日はトランザクションが実現する並行制御の理論的側面についての整理を淡々と述べるので退屈になること請け合いだけれど、可能な限り図解しながら説明を尽くすのでわからない所は容赦なくはてブやTwitterなどで書いて貰えたら適宜加筆修正をするつもり。
アドベントカレンダーを書くにあたって参考にする教科書は
Jim Gray著のTransaction Processing: concepts and techniques
Gerhard Weikum著の
の2冊を教科書とする。どちらも鈍器のように分厚い本である。それと適宜論文などを参照していく。
教科書を読み下して噛み砕いて説明している部分はこの2冊を読んで理解している人には不要と思われる。
データベースの文脈においてトランザクションとは「1つ以上の手続きを1つの単位としてまとめた操作」を言う。
複数のユーザーが同一のデータに対して同時に操作を行った場合、何の対策もしなかった場合容易に値への更新が衝突し、狙い通りの値にならない事態に見舞われる。
この図では2人のユーザーが同時にxに1を足す操作をしに来たのだから、最終的にxの値は0から2へと増加していて然るべきだが1になってしまった。更新が1つ消えてしまった事になる。もっと複雑なケースを考えていけばさらに複雑な状況は容易に起こりうる。そういった状況にならないようにするためには個々のユーザが全員一人ずつ順番に操作しに来てくれれば良いのだが、性能上の理由からそうも言っていられない。特にこれからはマルチコア・メニーコアの時代である。
トランザクションのインタフェース
トランザクション操作を投入したら個々のトランザクションをうまく並列に実行してくれる装置を考える。その装置からはそれぞれのトランザクション操作は Read(x) Write(x, value) Abort() Commit() の操作の列でありその裏でどういう意図が有ってそれらの操作を行うかは見えていない。 例えばRead(x) -> 10 をした後に Write(y, 100) が実行されたからといってそのxとyの値にどういう関係があるかはトランザクション装置からは見えない。関係があるかも知れないし無いかも知れない。それらのルールを短くまとめると以下になる。
- ルール1:
Readが読む値もしくは最終状態の値は「初期状態」もしくは「その値に対して一番最近Writeされた」一つの値である - ルール2:
Writeが書き込むのは、それまでに自トランザクションが行ったすべてのReadから算出されたと仮定した何らかの値である。
文章では直感的ではないが、図に書くと先ほどの絵はこのようになる。
左端の緑色が値の初期状態。右端の紫色が値の最終状態を表す。この様な図を便宜的にスケジュール図と呼ぶ事にする（正しい名称は僕が知らないだけで別にあるかも知れない）二つのトランザクションがReadとWriteをそれぞれ実行しているが、Writeが衝突しておりルール1の「一番最近Writeされた」という部分に違反するので許されない。
Serializable
複数のトランザクションが入り乱れて複数の値を操作する場合、得られた結果が正しいものであるかという基準が必要となる。そこで スケジュールの等価性という考え方を導入する。例えば
Tx1: Read(x) Read(y) Write(z)
Tx2: Read(x) Write(y)
Tx3: Read(z) Write(z)
Tx4: Read(z) Write(x)
という4つのトランザクションが並行に実行され、以下のようなスケジュール図を描いたとする。
このように複数のトランザクションの操作が複雑に入り乱れた場合、これが望ましい実行状態であるのかについて議論する事は自明ではないが。結果として「あたかも個々のトランザクションを1つずつ順番に行ったかのように実行」（以後逐次実行と呼ぶ）できれば良いので、逐次実行と比較して何らかの基準で一致していればそのスケジュールは正しいと言えるという基準があると良さそう、というのが並行制御の出発点である。
4つのトランザクションが何らかの順番で1つずつ(Serialに)実行されていった場合、トランザクションは4つなので4!=24通りの実行パターンがある。仮に適当な順で並行に4トランザクションを実行したとして、そのどれかと同じ結果を残すことができるならそれはSerialな実行と見做しても実際差し支えない。このように並行なトランザクションの実行がSerialな実行と同じ結果を残せる場合Serializableであると言う。
明日はトランザクションの正しさとして基本となるFSRについて説明する。