atomic-write.re

= Atomic な永続化方法


ファイルに対する @<tt>{write()} システムコールで書いたデータの永続化は @<tt>{fsync()} か @<tt>{fdatasync()} を、
Mmap されたファイルの変更データの永続化は @<tt>{msync()} を使えば良いのでした。
基本的な永続化の操作はこれだけしかないのですが、もう少し高い抽象度から見た操作として、
Atomic に書き込みを永続化するにはどうすれば良いかについて考えていきましょう。
具体的には、以下のそれぞれの場合について説明します。


 * Atomic にファイルに追記したい場合
 * Atomic にファイルまるごと上書きしたい場合
 * Atomic にファイルの一部を上書きしたい場合
 * Copy-on-Write (CoW)
 * その他


== Atomic にファイルに追記したい場合

この方法は追記ファイルである WAL ファイルの Atomic 書き込みに使えます。
前提として、データを書きたい場所、すなわちファイル内のオフセットは分かっているものとします。
それまでも同様に Atomic に追記しているのであれば、ファイルの終端オフセットは分かるはずなので、
それがこれから追記するデータの先頭オフセットとなります。

まずは、書きたいデータの Checksum を計算します。アルゴリズムは @<tt>{crc32} など好きなものを選んでください。
ただし、アルゴリズムの特性を良く理解してから選びましょう。
今回必要になる Checksum の性質で一番重視すべきものは、Hash 関数として捉えたときの衝突耐性です。
不完全なデータなのに完全だと誤判定されてしまう事象が発生する確率が無視できない状況では、
データを正しく Atomic に書ける、という性質を担保するのが難しくなります。

データを実際に書くときは、Checksum、データサイズ、データの中身を書き、永続化保証が必要なら直後に永続化命令を発行します。
Checksum は典型的には固定サイズですが、そうでない場合は Checksum データの終端が分かるようにします。
データサイズも同様です。例えば 64bit little endian unsigned integer を使うのであれば、8 bytes 固定です。
このフォーマットは一例ですが、それぞれのデータの位置が後で分かるようになっていることが必要です。
データサイズが固定長である場合は、あえて毎回データサイズを記録しなくても良いでしょう。
可変長のデータについては、別途固定長のサイズ情報を記録することで、区切りが分かるというわけです。
C 言語の文字列のように、区切り文字を使うケースもありますが、
データに区切り文字そのものを格納できないという制約があったり、
頑張って格納しようとするとエスケープ処理が必要だったり、
前から順番に読まないと区切りが分からないというデメリットがありますので、
データを永続ストレージに格納するという文脈では多くの場合
サイズ情報を別途記録する方が良いと考えられます。
特にエスケープ処理はセキュリティの穴が空きやすいので原則使わないようにしましょう。

Crash recovery するときには、まず Checksum とデータサイズをメモリに読み込みます。
これで、データサイズが分かる(データサイズそのものが正しいかどうかはこの時点でまだ分からないので、
値が大きすぎるなど、仕様に反するときは何らかのエラー処理を行う必要があるかも知れません)。
次に、データの中身をメモリに読み込み、Checksum を再計算し、記録されているものと一致すれば、
それは正しく完全に書かれたデータだと信じられます。
Checksum が不一致ならば、データは不完全と判断します。

「完全なデータが書かれているならば Checksum が一致する」という命題は真です。
しかしその逆である、「Checksum が一致するならば完全なデータが書かれている」という命題は
必ずしも真ではありません。だから、信じると書きました。
完全なデータではないのに Checksum が偶然一致してしまった、
という稀な事象が起きていないと信じているということです。
このリスクを少しでも減らすためには、Checksum アルゴリズムの選定に気をつかうだけでなく、
Checksum が一致したとされるデータが
(DBMS レベルで、さらにはアプリケーションレベルで)正しいかどうかを確認するのが
良いでしょう。



== Atomic にファイルをまるごと上書きしたい場合

設定ファイルなどを更新するときに、ファイルをまるごと Atomic に変更したいときがあります。
ファイルを読む人は、Open したときのファイル内容を一貫して読めます。
これは大きなファイルでも使えるテクニックですが、
ファイル内容の変更量が少ない場合は無駄が多いデメリットとなりますので注意が必要です。

まず対象と同一ディレクトリ内に Temporary な名前で新規ファイルを作成し、新しい中身を書き込み、永続化します。
同一ディレクトリでなくても構いませんが同じファイルシステムに属する場所でないと
次の Rename 操作が失敗するので注意してください。
次に、@<tt>{rename()} システムコールを使って名前を対象のものに変えます(上書きします)。
@<tt>{rename()} は Atomic 動作が保証されており、@<tt>{rename()} の前後で対象ファイルを Open した人は、
古いファイル内容か、新しいファイル内容のどちらかを必ず見ることになります。
古いファイル内容は、それを Open している人がいなくなった後に削除されます。
Rename 前の永続化は必須なので、注意してください。この永続化をサボる人が多すぎるらしく、
サボっててもちゃんと動くようお節介をしてくれるファイルシステムもあるようです
(ext4 の @<tt>{auto_da_alloc} オプション参照)。

Rename の結果を永続化するには、新しいファイルに対してさらなる @<tt>{fsync} の実行が必要です。
以前は @<tt>{rename()} によるファイルメタデータの変更を永続化するために
対応するディレクトリエントリを永続化する必要があるという話がありましたが、
@<tt>{ext4} など最近のファイルシステムでは対象ファイルの @<tt>{fsync} で良さそうです@<fn>{footnote_rename}。

 * 参考(1): @<href>{http://d.hatena.ne.jp/kazuhooku/20100202/1265106190}
 * 参考(2): @<href>{http://blog.gachapin-sensei.com/archives/618823.html}

//footnote[footnote_rename][Linux 5.17 ext4 (ordered) で私が動作を確認した限りでは、Rename 後の永続化操作は、親ディレクトリに対する @<tt>{fdatasync} をするのでも新しいファイルに対する @<tt>{fsync} をするのでもどちらでも構わないようです。ただ、異なるファイルシステムや異なる OS では挙動が異なるかも知れませんので十分注意してください。]


== Atomic にファイルの一部を上書きしたい場合

MySQL などでは Double write という手段が使われています。
Double write buffer という専用のファイルを用意し、そこにまず書いて永続化してから、
本体ファイルを上書きし、最後に Double write buffer から消します。
Double write buffer に書くときは Atomic に追記するテクニックを使います。
Crash recovery 時に Double write buffer に残っているデータは
本体ファイルにおいて中途半端に書かれている可能性があるので、
本体ファイルの上書き操作を再実行することで Atomic 性を担保します。

Double write buffer は WAL における Redo log と似た働きをすると思って良いでしょう。
WAL を使っているシステムの場合、WAL ファイルにログとして上書きしたいイメージを追記することで、
Crash recovery 時に上書き操作を Redo することで Atomic 性を担保できます。
毎回 WAL などに書くとログファイルが膨れあがってしまうので、
Checkpoint 後に初めて上書きする場合などに限るなどの最適化が行われます。
この方式は PostgreSQL で採用されています。

典型的なブロックストレージでは Block ひとつの書き込みについては Atomic 性を持っています。
ファイルシステムが何か特別なことをしていない限り、昨今の Linux では 4KiB sector HDD が存在するので、
実体としての Atomic write 単位が 512B だったり 4KiB だったりしますが、小さい方に合わせて、
512B Alignment された領域に 512B の @<tt>{write()} システムコールを 1 回のみ用いた書き込みであれば、
Atomic に書かれるとみなして良いです。
HDD に限らず Flash memory で作られたブロックストレージも、この性質を満たすように作られているはずです。
Linux のファイルシステムのスーパーブロックの書き込みはこの性質を仮定しています。
これはシステム依存の挙動であることに十分注意してください。
あなたがシステム全てをコントロールできる立場にあり、特定の書き込みが Atomic に書かれることが確信できるなら
ご自分の責任でそれに依存した設計をしても構いません。
それを信じることができない環境では、Atomic 追記のテクニックを使う必要があります。



== Copy-on-Write (CoW)

上書きするときにコピーする、という名前通りの手法です。
CoW という言葉を使うときは、メモリ断片とそれを指すポインタ(ポインタは Atomic に書き換えられることが前提)の話と、
ディスク上で Tree 構造を扱うときの話があるように思います。今回は後者の話です。
Tree ノードの一部を上書きしたいとき(通常は Leaf ノード)、新しいノードを確保し、
ノードの中身をまるごとコピーして、必要な変更を新しいノードに加えます。
新しい変更は Atomic に実行する必要はありません。新しいノードはまだ Root ノードから辿れない状態なので。
ノードの位置情報を参照しているノード上で書き換える必要がありますが、
その書き換えが Atomic に出来るならそうして終わりです。
Atomic に書き換えできない場合は、同様に位置情報を書き換えたノードのコピーを作って……という操作を
再帰的に繰り返します。
すると、いずれ一番上の Root ノードに到達します。
Root ノードが Atomic に書けるならそれを Atomic に書き換えて終わりですが、
そうでないなら、Root ノードの変更されたコピーを用意して、
新しい Root ノードの位置情報を、
何らかの方法でその Tree 全体を管理するデータ(Root の位置情報が記録されている場所) を Atomic に書き換えます。
CoW のメリットは、WAL が不要な点と、(Root ノードまで CoW する場合に)自動的に過去の Snapshot が作られる点です。
(Root ノードまで CoW する場合の)デメリットは、Tree の深さと同じ数のノードの CoW を実行する必要がある点です。


== その他

データの Atomic な永続化方法は他にもあるかも知れません。
興味があれば是非探求してみてください。
Atomic な操作はそのシステムで用意されている何らかの Atomic なプリミティブ操作に依存して
構築されますので、プリミティブが何かについて意識することが大切です。
例えば、NVRAM はブロックデバイスと異なり、もっと細かい単位で永続化ができるようなので、
よりきめこまかな方法で目的を達成できる可能性があります。
例えば、分散システムではたとえディスクに永続化しなくても、
複数ノードにコピーが存在する事実をもって永続化相当とみなせるかも知れません。
何を前提とできるかは環境によって異なり、またそれが未来永劫不変の性質であるとみなせるわけでもありません。
DBMS も含め、ソフトウェアは環境に合わせて変化する必要があります。
Atomic な永続化手法についても、例外ではありません。