ROLLBACK TO (SAVEPOINT)をどう実装するか
これまで書いてきた記事は実装のほぼ固まったものについて解説する形のものが多かったですが、それらとは区別し、現在検討中のことについて検討事項のカテゴリーで書きたいと思います。今回は、ROLLBACK TO（およびSAVEPOINT）の実装について書きます。
なお、僕は追記型MVCCについては聞きかじった程度ですし、PostgreSQLのソースを読んだこともないので、大部分を想像（妄想？）で補って実装しようとしています。ここに書かれている手法が実際役に立つかどうかは怪しいので、何かに利用したり誰かに話したりする際にはご注意下さい。
ROLLBACKの実装
PostgreSQLに倣って、トランザクションIDをxid、あるタプルが見えるトランザクションの範囲をxminおよびxmaxで表します（xmin <= xid < xmaxのときそのタプルは可視となります）。
| xmin | xmax | firld1 | field2 | ... |
|---|---|---|---|---|
| 500 | 505 | aa | bbb | ... |
| 505 | 508 | aa | ccc | ... |
| 508 | bb | ddd | ... |
上記のようなデータがあり、3行目のタプルがコミットされていないとします（つまり、xid = 508のトランザクションを実行中です）。ここでこのトランザクションをロールバックした場合、各タプルの状態はこのままでコミットログにxid = 508がABORTEDと記録されます。
次に、xid = 509でデータを参照する場合を考えます。2行目のタプルはxmin <= xidですがxmax = 508なのでxid < xmaxが成り立たず、本来xid = 509のトランザクションからは見えません。しかしコミットログを調べるとxid = 508はABORTEDと記録されているのでxmaxを無視して可視とします(xid = 505に関してはコミットログがCOMMITEDなのでxminは有効です*1）。3行目のタプルはxmin = 508なので本来可視ですが、2行目と同様xid = 508はABORTEDなのでxminを無効とし、このタプルを無視します。
このデータをさらに更新する場合を考えてみます。xid = 510で更新するとすると、本来であれば3行目のxmaxを510に設定するところですが、xid = 508はABORTEDなのでこれを無視し、もう一つ前の2行目のタプルのxmaxを更新します。この結果、下記のようになります。これをxid = 510以降で参照すると、4行目だけが可視となります。
| xmin | xmax | firld1 | field2 | ... |
|---|---|---|---|---|
| 500 | 505 | aa | bbb | ... |
| 505 | 510 | aa | ccc | ... |
| 508 | bb | ddd | ... | |
| 510 | cc | ddd | ... |
以上のようにして、ROLLBACKを実現できます。
ROLLBACK TOの実装
トランザクション内ではxidの代わりにcid（コマンドID）が用います。例えば、次のようなデータを考えます（cidにとってのcmin、cmaxはxidにとってのxmin、xmaxに対応します）。
| xmin | xmax | cmin | cmax | firld1 | field2 | ... |
|---|---|---|---|---|---|---|
| 500 | 500 | 1 | 3 | aa | bbb | ... |
| 500 | 500 | 3 | 7 | aa | ccc | ... |
| 500 | 7 | bb | ddd | ... |
2行目の状態（cid = 3）に対してSAVEPOINTを作成しているとします。このとき、ROLLBACK TOでその状態まで戻すにはどうすればよいでしょうか。コマンドID版のコミットログがあれば同じように動作するように思えます（以下、便宜的にコマンドID版のコミットログをコマンドコミットログ、従来のトランザクションのコミットログをトランザクションコミットログと呼びます）。ROLLBACK TOでSAVEPOINTまで戻すためには、cid = 4, 5, 6, 7のコマンドコミットログをABORTEDにします。このトランザクションがコミットされた後に他トランザクションからこのデータを参照する場合を考えてみましょう。2行目のタプルを参照する際にはxid = 500, cid = 7のコマンドコミットログがABORTEDになっているため、cmaxを無視してこのタプルを可視とします。同様に、3行目のタプルは無視されます。
このようにして、コマンドコミットログというものを導入することによって、ROLLBACk TOも実現できそうです。
コミットログの実装
トランザクションコミットログは、一つのファイルに記録することができます。IN_PROGRESS、COMMITED、ABORTEDの3状態は2ビットで表現することができるため、あるxidに対応したログを、ファイルのxid * 2ビット目から2ビットに記録することでランダムアクセスが可能となります。しかし、コマンドコミットログはトランザクションごとに複数存在します。トランザクションコミットログのように単純にはいきません。
最初に思いつくのはトランザクションの数だけコマンドコミットログのファイルを作成することです。しかし、一つのトランザクションのコマンドコミットログがディスクブロックの大部分を埋めるほど長くなることはまれだと思うので、この方法ではディスクの使用効率が悪すぎます。また、キャッシュの観点からも非効率です。
とはいえ、コマンドコミットログの長さは固定長ではないため、すべてのコマンドコミットログを一つのファイルにべた書きしたのではランダムアクセスすることができません。これを解決するために、ログファイルとは別にインデックスファイルを作成する方法が考えられます。
インデックスファイルには、あるトランザクションのコマンドコミットログがログファイルの何バイト目から始まるかを記録します。例えば、xid = 500, cid = 7のコマンドコミットログを参照する場合を考えます。まず、インデックスファイルから、xid = 500の位置を引きます。位置が8バイトで記録されているとする*2と、8 * 500バイト目から8バイトを読み出します。この読み出した8バイトの値がログファイル上での位置を表します。コマンドコミットログではIN_PROGRESSとCOMMITEDを区別する必要がないので（トランザクションコミットログを見ればわかるため）、1ビットで状態を表すことができます。今、仮に読み出した値が（10進数で）54321だったとすると、cid = 7のコマンドコミットログを読み出すには、ログファイルの54321 * 8 + 7ビット目を見れば良いことになります。
考察
インデックスファイルとログファイルに分離することでランダムアクセス可能なコマンドコミットログを実現し、ROLLBACK TOとSAVEPOINTが実装可能になるのではないかと思います。しかし、コマンドコミットログのようなものの存在は聞いたことがありませんし、そんなものがなくてもROLLBACK TOやSAVEPOINTを実現できるのかもしれません。他の良い方法や、PostgreSQLでの実装方法をご存知の方がいらっしゃれば教えていただければ幸いです。
また、そもそもROLLBACK TOとSAVEPOINTを実現する必要があるのか、ということも悩んでいます。ROLLBACKだけであればコマンドコミットログは不要になるため実装は簡単になります。
まとめ
トランザクションIDごとのコミットログだけでなく、コマンドIDごとのコミットログ（というよりアボートログ？）を用いることで、ROLLBACK TOを実現することができそうです。しかし、僕が知らないだけで、より機知のより良い方法が存在する可能性は多分にあります。また、そもそもROLLBACK TOを実現する必要があるかについても検討中です。
