Transactional write の調査: SQLite rollback journal 編

プログラミングをしていると、電源断などの障害時でも不整合が起こらないようにデータを保存したいという要求がしばしばある。 通常こういう要求は DBMS やライブラリなどで担保することになるわけであるが、データ自体が DBMS に収まらない場合、 2 phase commit が必要になったり、システムプログラミングをしていると DBMS を使えなかったりする。 そんなときにデータを正しく書く方法が知りたくなったので、有名所の実装を調べていくことにする。

ここでは電源断などを考えることにする。 このときデータを守る方法としては、write ahead logging や rollback journal などの方法がある。 (論文などをサーベイしていないのでもっといろいろな方法があるかもしれない) これらの方法は、理屈としては難しいものではないが、ディスクデバイスにどのような仮定を持つかによって実装が難しいものになる。

例えば WAL の場合、1セクタ内に複数レコード r1, r2 を書いているとして、r1 を書き終えて、r2 を書いている際に電源断が起こったとする。 このとき、ディスクデバイスは、r1 を残してくれるのだろうか?

以降では、transactional write という用語を、電源断時に commit or rollback して整合性を保った状態に保つことができる write ということにする。 (この用語はもっと適したものがあるかもしれない)

今回は、ドキュメントが豊富な SQLite の rollback journal について調べてみる。

rollback journal については、Atomic Commit In SQLiteに詳しく記述されている。

SQLite は、先ず書き込み対象のページを rollback journal として書き出して、その後にデータベースファイルを書き換え、 最後に journal を削除する。

SQLite はこの書き込みに対してセクタへの書き込みはアトミックではないと思っている。

SQLite has traditionally assumed that a sector write is not atomic.

しかし、セクタ内への書き込みは linear だと仮定していて、必ず書き込みは先頭または末尾から書き始めて、途中で電源が起きた場合、その地点までは書き込まれ、それ以降は変更されないという仮定のようだ。

また新しいバージョンでは SQLiteファイルシステム抽象化レイヤの VFS から書き込みを atomic であると主張することもできる。

IO でどのような仮定が使えるかというのは sqlite3.h で定義されている。 ただし unix 向けの os_unix.c では、SQLITE_IOCAP_POWERSAFE_OVERWRITESQLITE_IOCAP_BATCH_ATOMIC が基本的に使われる。 (android 環境では ATOMIC 系もサポートされているようだ)

#define SQLITE_IOCAP_ATOMIC                 0x00000001
#define SQLITE_IOCAP_ATOMIC512              0x00000002
#define SQLITE_IOCAP_ATOMIC1K               0x00000004
#define SQLITE_IOCAP_ATOMIC2K               0x00000008
#define SQLITE_IOCAP_ATOMIC4K               0x00000010
#define SQLITE_IOCAP_ATOMIC8K               0x00000020
#define SQLITE_IOCAP_ATOMIC16K              0x00000040
#define SQLITE_IOCAP_ATOMIC32K              0x00000080
#define SQLITE_IOCAP_ATOMIC64K              0x00000100
#define SQLITE_IOCAP_SAFE_APPEND            0x00000200
#define SQLITE_IOCAP_SEQUENTIAL             0x00000400
#define SQLITE_IOCAP_UNDELETABLE_WHEN_OPEN  0x00000800
#define SQLITE_IOCAP_POWERSAFE_OVERWRITE    0x00001000
#define SQLITE_IOCAP_IMMUTABLE              0x00002000
#define SQLITE_IOCAP_BATCH_ATOMIC           0x00004000

SQLITE_IOCAP_POWERSAFE_OVERWRITE は先程の linear の仮定を示している。 SQLITE_IOCAP_BATCH_ATOMIC は f2fs の atomic write api を使う方法で、 なんとこれを使うと、journal なしで直接データベースファイルを更新する。 ファイルシステム側で transacional write を担保しているわけだ。

さて、先の journal の作り方だと、journal を作っている最中に電源断を起こすと不正な journal ができてしまう。 当然そのような journal を使ってしまうとデータベースが破損してしまう。 これを防ぐために、journal は最初にヘッダにレコード数を0と記録する。 次にレコードを書き終えた後、ヘッダを更新する。

レコード数を記録するフィールドはヘッダ先頭の magic の直後に位置していて、 linear の仮定からレコード数を書き換えている間に電源断が起きても、破損に気づくことができる。 (しかしレコード数は4バイトなので中途半端に書かれていた時に困らないか?)

この動作はファイルシステムが先ずファイルサイズを更新してからデータを書くということを仮定している。 昨今のジャーナリングファイルシステムだとデータを書いてからメタデータを更新するので、自前でヘッダにレコード数を書かなくても良い。 このために SQLITE_IOCAP_SAFE_APPEND を使うことができる。

以上が SQLite rollback journal の動作となる。