トランザクションの基本

本来はこの話はトランザクション技術アドベントカレンダー初日に書くべきだったかも知れない。

トランザクションとは「1つ以上の連続した操作の単位」であり、ACID特性を満たすとよく言われている。（というか先日も何度も何度も無意識にACIDという言葉を使っていた）

# ACIDとは

ACID(えいしっど、もしくはあしっどと読む人も居るしどっちでもいいと思う）は[Wikipedia](https://ja.wikipedia.org/wiki/ACID_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E7%A7%91%E5%AD%A6))にも説明があるが、そこの説明は僕にはイマイチだと感じたので僕の言葉で今一度説明する。
`Atomicity` `Consistency` `Isolation` `Durability`の4つがトランザクションの満たすべき性質であると提唱されており、その4つの頭文字を取ってACIDと呼ぶ。それぞれの性質の内容に付いて書くと

## Atomicityとは

トランザクションが残す**結果**が、すべてのトランザクション内操作が成功したか、もしくはすべて無かった事になったかのAll or Nothingになる特性の事をいう。不可分だとかは関係ない（というかトランザクションの個々の操作はインターリーブされることを前提として考えるので可分かどうかは主題ではない）。
複数のデータに読み書きをするにしても、全部のデータに対する更新が成功したか否かが**中途半端な結果にならずに**終わるという性質である。

## Consistencyとは

予めシステムに与えた制約条件（存在しない外部キーを参照してはならないとか）を破るようなトランザクションが**成功しない**という特性である。Atomicに操作が行われてるならConsistencyが破られる事はないんじゃない？という疑問を浮かべる人もいるが、トランザクション操作というのは容易に制約(Constraint)を破る。この用語が提唱された頃はシステムに与える制約条件として詳細なアプリケーションのドメイン知識を埋め込めばトランザクションに乗っかるだけで全部ハッピーというような構想があったようにも見えるが、イマドキの開発ではUNIQUEとかNOT NULLとか結構限定的な制約しかロクに使われていないように見える。
ActiveRecordなどはユーザレベルで制約条件に相当するような仕組みを作りこんでおり、どこまでがDBの責務であるべきかというのは結構難しい問題である。
Peter Bailisらによる[Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity](http://dl.acm.org/citation.cfm?id=2737784)の論文なんかでは「DB開発者がせっかくトランザクションの仕組みを作りこんだ割にアプリ開発者たち（とORマッパ作者たち）はほとんどトランザクションを使わず、データのValidationやらユーザレベルでの不変条件保護に労力を割いている。本当に必要なのは現状のリレーショナルモデル+トランザクションではないのでは？」と問題提起をしており大変興味深い。長くなってしまったので詳細はまた別の記事で。

## Isolation

トランザクションを実行する**過程**が外のトランザクションから独立して見えないという性質を言う。Atomicityは**結果**についてしか議論していない一方で、Isolationは**過程**の可視性に関する議論である点が多くの人にごちゃまぜに認識されやすい箇所である。
さて、トランザクションの実行過程が外のトランザクションから見えてはダメかというと厳密な事を言うと過程が外のトランザクションから見えてしまっても*問題はない*ケースは考えられうる。極端な話、**VSR**であれば自分以外のトランザクションによる未コミットな値を読んでしまってもそっちのトランザクションがコミットした後に自トランザクションをコミットに持っていくのは有りであるし、**Serializable**であればどうとでもなる。
また、世の中の一般的なDB(Oracle, MySQL, PostgreSQL, SQL Server, DB2などの有名ドコロ)のデフォルトのIsolation Levelは最弱より1〜2歩強いだけでありこれをもってして「ACIDのすべてが守られています」なんて言うと顰蹙を買うことになる。よってACIDのうち一番ないがしろにされがちな不憫な特性である。
Isolation Levelに関する詳細は明日まとめて書く。

## Durability

トランザクションがクライアントに完了をひとたび報告したなら、そのトランザクションの結果は上書きされない限り例え電源が消されようと残る、という性質である。どの永続デバイスにどのように保存されるかは規定しておらず、ディスク上のDBに変更が反映されているかも知れないし、Redoログの形で残っているだけかも知れない。
大学の時この話を聞いて「じゃあHDDが物理的に壊れても残るの？」と素朴な疑問を抱えたものだが、結論から言うとデータベースを格納しているHDDが突然吹き飛んでもメディアリカバリという仕組みで復旧できる所までセットでのDurabilityのようだ。メディアリカバリはログデータを必要なだけリプレイすることでメディアのデータを再生成するわけで、ログデータは常に安全な場所に（永久に）保管されて消失しない前提を暗黙に置くことが多い。とすると「ForceするタイプのDBはRedoログは要らない」と僕は過去に書いたが、ログからのメディアリカバリの為に結局Redoログをアーカイブに保存する必要がある事になる。
このDurabilityという特性はナイーブに実装するとパフォーマンスが全く出ない。それを改善するために人類が積み上げてきた最適化の歴史が面白いからいろんな人に知ってほしいというのがそもそもこの１人アドベントカレンダーを書いている主たるモチベーションであり、いろんな人に伝わったら嬉しいなと思っている。

## 既存DBのACID性

基本的な事をサラッと書くつもりがつい熱くなってしまって自分でも軽く引く長文になってしまったので今日はこのへんにしたいが最後に1つ論文を紹介する。
USENIX2014でのMai Zhengらの[Torturing Databases for Fun and Profit](https://www.usenix.org/node/186197)である。タイトルをそのまま[google翻訳にかける](https://translate.google.com/?hl=ja#en/ja/Torturing%20Databases%20for%20Fun%20and%20Profit)と「楽しいと利益のためのデータベースの拷問」と出て本当に頭おかしい（誉め言葉）。実験設定と結果しか流し読みしていない。ブロックデバイスのレイヤーで仮想デバイスを挟み込んで、そのレイヤーで発行されたブロックデバイスへのWrite命令の羅列を全て保存し、その羅列をわざと途中までしか実行していないブロックデバイスをリプレイによって作成し、その上でリカバリをさせる事で任意タイミングでの電源断を仮想的に再現する。そうしてリカバリを済ませたDBがACID違反をしていないかをチェックするというものである。ブロックデバイスのレイヤーでそれを実現することによってファイルシステムの実装に起因する問題をも見つける事ができる。なお羅列をどこで区切るかで長さn件に対してn通りの故障パターンが考えられうるため動作試験コストが膨大であるため実際はサンプリングしたとの事である。この技法はファイルシステムのデバッグやテストでは一般的なんだろうか？
結果から画像を引用すると
![acid-violation.png](https://qiita-image-store.s3.amazonaws.com/0/1716/2b307695-a742-c494-6676-53d7ad53d0c7.png)
一言で言うと商用含むほぼすべての(NTFS上でしか動かないSQL-Cはほぼ名指しに近いような…?)DBがDurability違反をしており、Consistency違反もちょいちょいあり、[Tokyo Cabinet](http://fallabs.com/tokyocabinet/index.ja.html)はAtomicityにも違反しているとしている。mmapを使っている箇所でWALの記事で説明したようにログの書き出しがmmapに対して先行しない場合があり、そこでUndoができなくなってしまうようである。そもそもTokyo Cabinetはちゃんとcloseしないと壊れる可能性があるという前提のストレージなので当然といえば当然である。

今日は長くなったがこのへんで。