データベースと呼ばれるシステムは大抵、ファイルにデータを記録する。DBMも例外ではない。でも、ファイルって何だろう。ここでちゃんと考えてみたい。
ファイルには二つの側面がある。外的側面と内的側面だ。外的側面は、ファイルシステム上でのリソース管理における位置づけだ。リソースIDがあって、それに紐づけた名前があって、その名前がディレクトリに記載されているというものだ。結果として、ディレクトリ名のリストとファイル名を区切り文字で繋げたファイルパスで個々のファイルは識別されることになる。UNIXの場合、リソースIDはinode、ファイル名はリンク、ディレクトリはそのままディレクトリと呼ばれ、パスの区切り文字は「/」だ。今回、外的側面にはあまり興味がない。「パスを指定するとファイルを開くことができる」という条件が満たされていれば何でも良い。C++20からは外的側面も標準化されていて、ディレクトリを作ったりファイル名を変更したりといった操作も標準ライブラリでできるようになる。良い時代だ。
内的側面とは、主にファイルを開いた後のAPIについての言及だ。UNIXの場合、いくつものシステムコールでAPIが構成されている。openにパスを渡してファイルを開くと、ファイルディスクリプタの整数を返してくれる。そのファイルディスクリプタと任意のバッファのポインタを渡してreadを呼ぶと、データを読み込んでバッファに書き込んでくれる。データを書き込んだバッファのポインタとファイルディスクリプタを渡してwriteを呼ぶと、バッファ上のデータをファイルに書き写してくれる。ファイルが使い終わったらファイルディスクリプタを渡してcloseを呼ぶとファイルを閉じてくれる。この4つのシステムコールが代表的なものだが、実際にはファイルに関わるだけで何十個もシステムコールがあり、それらの使い方をいちいち覚えるのがUNIXプログラマの最低条件となる。もちろんWindowsプログラマはWin32で同じ苦労をせねばならない。ただ、内的側面の標準化は昔からなされていて、C言語ならFILEという構造体があり、C++ならfstreamというのがある。C/C++に限らないならもっとお気楽に生きられる。
残念ながら、標準ライブラリのファイルAPIは今回は使えない。スレッドセーフではないからだ。単一のファイルオブジェクトを複数のスレッドで同時に使った場合の動作は未定義だ。同一ファイルを開いた複数のファイルオブジェクトを個々のスレッドが使うことは許されるが、ファイル内のデータを保護するための排他制御機構を何ら持たないので、その方法も今回は使えない。さらに、バッファリングの挙動を細かく制御するのも難しい。十分な性能を引き出し、また並列化を確保するには、UNIXのシステムコールを使って最適化された実装を自分で書いた方が良さげだ。一方で、OS独自のAPIを使うと移植性がなくなってしまう。それに、50年も経とうとしているUNIXのAPIは古臭い部分も多いのであまり直接使いたくない。
そういうわけで、ファイル入出力を抽象化したクラスを設計する必要がある。まずは純粋仮想関数だけを備えたインターフェイスクラスを設計する。それを継承した具象クラスをいくつか作り、OS依存の実装は個々のクラスの中に隠蔽する。データベースを実装するためのコードの中にはOS依存の処理は一切入れないのが条件だ。将来的にWindows版を作る場合にも、ファイルの具象クラスの一部をWin32のAPIを使って書き換えればよい。
ファイルインターフェイスの具体的なAPIは以下のようになる。スレッドセーフであることが仕様として明言される。
class File {
public:
virtual Status Open(const std::string& path, bool writable, int32_t options = OPEN_DEFAULT) = 0;
virtual Status Close() = 0;
virtual Status Read(int64_t off, void* buf, size_t size) = 0;
virtual Status Write(int64_t off, const void* buf, size_t size) = 0;
virtual Status Append(const void* buf, size_t size, int64_t* off = nullptr) = 0;
virtual Status Truncate(int64_t size) = 0;
virtual Status Size(int64_t* size) = 0;
};パスを渡してファイルを開くOpen、ファイルを閉じるClose、任意の位置のデータを読み込むRead、任意の位置にデータを書き込むWrite、末尾にデータを書き込むAppend、ファイルサイズを変えるTruncate、現在のファイルサイズを知るSize、という7個のメソッドが提供される。これだけ。このAPIは、ランダムアクセスを念頭に置いて設計されている。読み書きの位置は必ず利用者側で指定する。シーケンシャルアクセスがしたければ、そうなるように利用者がオフセットを計算すればよい。ただし、Appendは例外だ。ファイルの末尾に、指定された領域をアトミックに確保した上で、そこに書き込みを行い、その領域のオフセットを返す。Appendが並列に呼ばれた場合、領域の確保、すなわちファイルサイズの拡張と書き込み位置の計算という処理をアトミックに行った上で、確保された領域に書き込みを行う。クリティカルセクションはファイルサイズを変更するその瞬間だけで、書き込み操作を行っている間はクリティカルセクションではない。しかし、全てのスレッドが重複しない位置に書き込みを行うことは保証されるので、競合は発生しない。ここが並列性の肝だ。
「具象クラスをいくつか作り」と上で述べたのは、移植性のためだけではない。ユースケースに合わせたて最適な性能の実装を使い分けるべく、具象クラスを複数提供するのだ。実装において選択すべき要素が二つあり、それを組み合わせた4つの具象クラスが考えられる。一つ目の要素はメモリマップを使うかどうかだ。UNIXだとmmapシステムコールで実現される機能だが、これはファイルの中身をメモリ上に直接マッピングするもので、いったんmmapを読んでメモリ領域を確保しておけば、メモリ領域にデータを書き込むだけで、適当なタイミングもしくはmunmapを読んだ時にその更新内容がファイルに反映されるというものだ。仮想メモリのサイズより大きいファイルは扱えないという短所はあるが、システムコールを呼ばずにファイルの読み書きができるので、効率が高いという利点がある。メモリマップを使わない場合には、preadおよびpwriteというシステムコールを毎回読んで、任意の位置のデータを読み書きすることになる。
二つ目の要素はWriteのアトミック性をファイル層で保証するかどうかだ。保証する場合、ある領域をWriteしているスレッドがいる際に、その書き込み途中の状態がReadで読み込まれてはならないという制約を守ることになる。それには、必然的にファイル全体にreader-writerロックをかけなければいけない。なぜなら、いつだってファイル全体を対象としたReadやWriteが呼ばれるかもしれないからだ。どの領域を読む場合も全体を共有ロックせねばならず、どの領域に書き込む場合にも全体に占有ロックをかけなければならない。一方で、その保証をしない場合、全く排他制御をせずに読み書きを行うことができる。例外は既に述べたようにファイルサイズが拡張される状況だけだ。ということで、以下の4つの具象クラスを提供することとなる。
| クラス名 | メモリマップ | アトミック性 |
| MemoryMapAtomicFile | ○ | ○ |
| MemoryMapParallelFile | ○ | × |
| PositionalAtomicFile | × | ○ |
| PositionalPrallelFile | × | × |
DBMの下敷きとなる実装の本命は、MemoryMapParallelFileである。仮想メモリのサイズは32GBとか普通に取れる時代なので、取れるならそうしない理由がない。毎回の読み書きでシステムコールを呼ぶオーバーヘッドはかなりでかいのだ。1バイト読むのと100バイト読むのが大して変わらないというくらいでかい。それ以上の大きさのデータベースを作るなら、仕方ないのでPositionalPrallelFileを使うべきだ。アトミック性はDBMの層で確保されるので、ファイル層のアトミック性は不要だ。そのためのハッシュロックである。
てことで、MemoryFileParallelFileを設計する。Openした時にファイルディスクリプタを取得して、それを使ってmmapでメモリマップを作る。メモリマップは始点とサイズを指定して作らねばならない。また、メモリマップした領域に実際にアクセスする前に、ftruncateでファイルのサイズをそれ以上に大きくしておかねらばらない。そうしないとsegmentation faultを食らう。ということは、書き込みを行う前にファイルサイズを決めておかなければならない。なので、ここで一つ決断をする。クラス内での「論理的」なファイルサイズと、ファイルシステム上での「物理的」なファイルサイズは別々に管理すると。物理的なサイズはファイルを開いた時に適当に大きめに確保して、論理的なサイズが物理的なサイズを超えそうになったら、その前に物理的なサイズを倍にするという、リソース割当ではよくある技法を使う。ファイルを閉じる際に物理的サイズを論理的サイズに合わせるようにftruncateすれば、外部的な整合性は回復する。さて、mmapした領域を拡大するにはmremapというシステムコールを発行するのだが、これが厄介だ。メモリマップ全体を別領域に確保する可能性があるからだ。てことは、あるスレッドがそのメモリの読み書きをしている最中に別のスレッドがmremapを呼ぶと、無効な領域へのアクセスとしてsegmentation faultを食らう。しかし、個々の読み書きに占有ロックをかけたら並列性が全くなくなってしまう。どうする？
マップされたメモリにアクセスする際には、つまりReadとWriteの際には、以下の手順を踏めば良い。ReadもWriteもほとんどの場合に共有ロックしかかけずに処理を行う。
- アクセスする領域の終点を算出する
- もし終点が既に確保した領域（atomic整数）以前であれば、共有ロック内で、アクセスを行う。（ほとんどの場合はここで終了）
- そうでなければ、占有ロックを確保して、もう一度、終点が既に確保した領域より大きいか調べ、大きければmremapとftruncateを呼ぶ。
- 占有ロックを開放して、共有ロック内で、アクセスを行う。
この手順は、ファイルが縮小しないという前提で成り立っている。確保した領域のサイズをチェックした後にそれが小さくなると困るからだ。しかし、その制約さえ受け入れれば、多くの場合では、共有ロックのみでマップされたメモリにアクセスできる。この決定により、ファイルを小さくする可能性があるTruncateメソッドだけはスレッドセーフではなくなった。ただし、DBMでは初期化以外でTruncateは使わないので、Truncateが並列に呼ばれることはない。Truncateもスレッドセーフにするには、終点の検査を占有ロック内で行った上でそのままmremapを呼ばねばならないのだが、そのオーバーヘッドを避けたいので、こんな落とし所になっている。
上記は物理サイズの管理についてだが、論理サイズの管理でも注意点がある。論理サイズもatomic整数として管理されるのだが、複数スレッドが同時に論理サイズの加算を行うのが厄介だ。単純な加算命令同士の競合であれば、fetch_addメソッドを発行するだけで整合性が取れる。しかし、ファイルサイズを増やすのは単純な加算を伴うAppendだけではない、ファイル末尾を超える終点を持つWriteもそうだ。その場合、終点位置が新しいファイルサイズになるので、それは加算でなく代入である。複数の代入命令が同時に起こった場合、結果の値が大きい方を残さねばならない。それはCompare-and-Swapを使ったこんなようなコードになるだろう。C++17標準だとcompare_exchange_weak（偽陰性あり）とcompare_exchange_strong（偽陰性なし）が使えるのだが、今回は前者でOK。
// atomic_int64_t file_size_;
const int64_t end_position = off + size;
while (true) {
int64_t old_file_size = file->file_size_.load();
if (end_position <= old_file_size ||
file_size_.compare_exchange_weak(old_file_size, end_position)) {
break;
}
}ということで、一番面倒なMemoryMapParallelFileが効率的に実装できそうなことはわかった。mmap周りのコードを削ってpread/pwrited読み書きするようにすればPositionalParallelFileも実装できるだろう。そしてそれぞれをファイルロックで保護して細かい排他制御を無くせばMemoryMapAtomicFileとPositionalAtomicFileも実装できる。後者2つはDBMでは使わないが。
