豪鬼メモ

一瞬千撃

TkrzwのWindows対応 その弍

データベースライブラリTkrzwWindows対応の実装が一通り完了した。前回C++標準のstd::fstreamによるダミーのファイル入出力を使ってWindows対応した話をしたが、今回はそれを本番の真面目な実装に置き換える。メモリマップIOと位置指定IOの実装と性能評価についても論じる。
f:id:fridaynight:20210505165144p:plain


Tkrzwでは、データベースの論理構造の層とファイル入出力の層の実装を完全に分離している。いわゆるDI(dependency injection)の方法を採用してて、データベースオブジェクトを作る際に、で任意のファイル実装クラスを注入できるようにしている。そして、処理系依存部分はその実装クラスに全て隠蔽している。前回は、標準ライブラリのfstreamを使って、非効率ではあるが可搬性は最強であるファイル実装クラスを作り、TkrzwのデータベースがWindows上でも動くことを示した。

今回は、実用に値する効率のファイル実装クラスを作る。UNIX上のものと同じように、以下の5つのクラスから選択できるようにする。

  • StdFile : C++標準のstd::fstreamを使った実装
  • MemoryMapParallelFile : メモリマップIOを使ったロックなしの実装
  • MemoryMapAtomicFile : メモリマップIOを使った全体ロックの実装
  • PositionalParallelFile : ポジション指定IOを使ったロックなしの実装
  • PositionalAtomicFile : ポジション指定IOを使った全体ロックの実装

メモリマップIOとは、UNIXでいうところのmmapを使う方法である。現代的な全てのOSは、連続的で巨大な仮想メモリ空間をアプリケーションに提供してくれるが、その裏ではページ単位で断片化して管理される物理メモリのアドレスと連続的な仮想メモリのアドレスの相互変換をする機構が働いている。メモリマップIOはその延長とも言える技術で、仮想メモリファイルシステムのIOバッファにマッピングしてくれる。結果的に、仮想メモリの特定の領域の読み書きは常にファイルの内容への読み書きと同義となる。毎回のアクセスでシステムコールを呼ぶ必要がないため、CPUの利用効率がメッチャ良い。その代わり、仮想メモリの容量を超えるデータサイズは扱えない。スワップ領域を活用すれば実メモリより大きいデータを扱うことはできるが、そうするとシステム全体が遅くなるので、結局のところ実メモリよりも小さいサイズのデータベースに向いている。

ポジション指定IOは、UNIXでいうところのpreadとpwriteを使う方法である。ファイルの前から順に読み書きする前提のreadやwriteを使っても、位置を指定するseekシステムコールを使えばランダムアクセスはできるが、その方法だとseekとread/writeがスレッド間でアトミックになるようにクリティカルセクションで保護しなければならず、並列性がない。preadとpwriteは現在位置という概念がなく、特定の位置のデータの読み書きを一撃で行える利点がある。毎回の読み書きにシステムコールを呼ぶ必要があるためにCPUの利用効率は悪いが、仮想メモリのサイズに限定されずに巨大なデータサイズを扱うことができる。

それぞれのIOの方式に対して、読み書きの内容の原子性を保証しない実装と、読み書きの内容の原子性を保証する全体ロックを使う実装が用意してある。原子性とは、ファイルを更新している途中の状態が他のスレッドから見えないようにすることだ。これを保証するには、ファイル全体にreader-writeロックをかける必要がある。つまり、読み取りは並列にできるが、書き込みは並列にはできない。原子性を保証しない場合、更新したデータが壊れないという一貫性を確保するための排他制御だけをすれば良いので、書き込みも並列にできる。


それぞれの実装の性能を見てみよう。といっても、私はWindowsの実機を持っていない。私のノートPCでVMWareを動かして、そのゲストOSとしてWindows 10を動かして、その上でテストした。仮想OS上での性能テストなので、絶対的な数値は全く意味がない。とはいえ今はこれしか方法がないので、あくまで傾向を見るためと割り切って実施する。

まずは、ファイル実装クラスそのものの性能を見る。100バイトのデータを、位置をシーケンシャルにずらしながら、100万回書き込んでから、同じ方法で読み込みを行う。1スレッドと2スレッドでそれぞれ計測を行う。数値の単位はQPS(query per second = 1秒間に何回の操作ができたか)である。

class 1スレッドwrite 1スレッドread 2スレッドwrite 2スレッドread
StdFile 101954 121512 9807 102867
MemoryMapParallelFile 891634 950185 1011954 1161421
MemoryMapAtomicFile 1068594 1189989 778544 502644
PositionalParallelFile 163316 181725 9938 162703
PositionalAtomicFile 158954 177888 9823 148820

f:id:fridaynight:20210505231859p:plain

次に、それぞれのファイル実装クラスをハッシュデータベースに注入した場合の性能を見る。キーが8バイト、値が8バイトのレコードを100万個setし、それぞれをgetし、最後にremoveする。1スレッドと2スレッドでそれぞれ計測を行う。数値の単位は同じくQPSだ。

class 1スレッドset 1スレッドget 1スレッドremove 2スレッドset 2スレッドget 2スレッドremove
StdFile 30632 38441 29279 23003 26571 20225
MemoryMapParallelFile 44839 53553 37916 241746 376982 189223
MemoryMapAtomicFile 46344 54568 39628 197407 280086 151374
PositionalParallelFile 34970 42454 32875 16490 35076 20909
PositionalAtomicFile 34867 42308 32670 16366 31286 10953

f:id:fridaynight:20210505231923p:plain

予想通り、メモリマップIOの方が位置指定IOよりも圧倒的に早い。ファイルサイズが実メモリよりも小さいならば、メモリマップIOを使わない理由はない。位置指定IOは特にマルチスレッドでの書き込みが遅い。シングルスレッドよりマルチスレッドの方が遅いとは。理由はよくわからないが、排他制御でスレッドがブロックされた際のオーバーヘッドがかなり大きいのではないか。これはWindowsの特性なのか仮想マシンのせいなのか現状では判別できない。結局のところ、位置指定IOの実装は標準ライブラリの実装とほとんど同じ性能しか出ないみたいだ。

一方で、メモリマップIOでのマルチスレッドの性能が異常なほど高い。普通に考えると、2スレッドにすると理想的には性能が2倍になることが期待されるが、実際には各種のオーバーヘッドを伴うので1.5倍くらいになればラッキーくらいの感じだ。にもかかわらず、この検証では4倍くらいに早くなっている。マルチスレッドにすると本気出してプロセスの優先度が高まるみたいな感じなのだろうか。これはいかにも仮想マシンのスレッド機構の特性っぽい。

やはり、仮想マシン上で性能テストをするのはあまり意味がない。実マシンでやらねば。どなたかWindows機を持っている人、以下のコマンドを実行して結果を教えていただけないだろうか。ビルドするのがだるいだろうから、tkrzw_file_perf.exetkrzw_dbm_perf.exeのバイナリを置いておく。

  • tkrzw_file_perf.exe sequence casket.tkh --file std --iter 1000000 --threads 1
  • tkrzw_file_perf.exe sequence casket.tkh --file std --iter 500000 --threads 2
  • tkrzw_file_perf.exe sequence casket.tkh --file mmap-para--iter 1000000 --threads 1
  • tkrzw_file_perf.exe sequence casket.tkh --file mmap-para--iter 500000 --threads 2
  • tkrzw_file_perf.exe sequence casket.tkh --file mmap-atom--iter 1000000 --threads 1
  • tkrzw_file_perf.exe sequence casket.tkh --file mmap-atom--iter 500000 --threads 2
  • tkrzw_file_perf.exe sequence casket.tkh --file pos-para--iter 1000000 --threads 1
  • tkrzw_file_perf.exe sequence casket.tkh --file pos-para--iter 500000 --threads 2
  • tkrzw_file_perf.exe sequence casket.tkh --file pos-atom--iter 1000000 --threads 1
  • tkrzw_file_perf.exe sequence casket.tkh --file pos-atom--iter 500000 --threads 2
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file std --iter 1000000 --threads 1
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file std --iter 500000 --threads 2
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file mmap-para--iter 1000000 --threads 1
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file mmap-para--iter 500000 --threads 2
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file mmap-atom--iter 1000000 --threads 1
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file mmap-atom--iter 500000 --threads 2
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file pos-para--iter 1000000 --threads 1
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file pos-para--iter 500000 --threads 2
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file pos-atom--iter 1000000 --threads 1
  • tkrzw_dbm_perf.exe sequence --path casket.tkh --file pos-atom--iter 500000 --threads 2


実装上の留意点についてメモを残す。まず、UNIXシステムコールWindows上の対応するものに読み替える。

  • open -> CreateFile
  • close -> CloseHandle
  • ftruncate -> SetFilePointerEx, SetEndOfFile
  • pread -> ReadFile
  • pwrite -> WriteFile
  • sync -> FlushFileBuffers
  • mmap -> CreateFileMapping, MavViewOfFile
  • munmap -> UnmapViewOfFile, CloseHandle
  • msync -> FlushViewOfFile
  • errno -> GetLastError

ftruncate、mremap(mmap/munmap)、pread、pwrite、errnoに関しては、広範な箇所で使われるので、ユーティリティ関数群を書いておいた。ReadFileとWriteFileに関しては、公式の解説でも曖昧な点があったので、注意が必要である。UNIXのpread/pwriteと同等の機能をReadFile/WriteFileで実現するには、以下の実装を書くことになる。

inline int32_t PositionalReadFile(
    HANDLE file_handle, void* buf, size_t count, int64_t offset) {
  OVERLAPPED obuf;
  obuf.Internal = 0;
  obuf.InternalHigh = 0;
  obuf.Offset = offset;
  obuf.OffsetHigh = offset >> 32;
  obuf.hEvent = nullptr;
  DWORD read_size = 0;
  if (ReadFile(file_handle, buf, count, &read_size, &obuf)) {
    return read_size;
  }
  return -1;
}

inline int32_t PositionalWriteFile(
    HANDLE file_handle, const void* buf, size_t count, int64_t offset) {
  OVERLAPPED obuf;
  obuf.Internal = 0;
  obuf.InternalHigh = 0;
  obuf.Offset = offset;
  obuf.OffsetHigh = offset >> 32;
  obuf.hEvent = nullptr;
  DWORD wrote_size = 0;
  if (WriteFile(file_handle, buf, count, &wrote_size, &obuf)) {
    return wrote_size;
  }
  return -1;
}

マイクロソフトの解説によると、CreateFileでファイルを開く際にFILE_FLAG_OVERLAPPEDフラグを指定すると、そのハンドルに対するReadFileとWriteFileではOVERLAPPEDパラメータが使われ、そこに仕込んだコールバックを用いて非同期IO通知を行ってくれるとのことだ。しかし、ここでは、非同期IOを行いたいわけではなく、読み書きの位置指定をするためだけにOVERLAPPEDパラメータを指定したいのだ。じゃあ、FILE_FLAG_OVERLAPPEDを指定しないでファイルを開いておいて、ReadFileやWriteFileにOVERLAPPEDパラメータを渡すとどうなるのか。残念ながら公式の解説にはそれについての言及ない。しかし、おそらく位置指定だけが有効になると勝手に期待して、そう実装してみたところ、きちんと同期IOかつ位置指定で動作した。

ここで、ひとつ落とし穴がある。あるスレッドがWriteFileで更新した領域を、その後に別のスレッドがReadFileで読み込むと、書いたデータではなくヌルコードが読み出されてしまうことがある。ファイルシステムのバッファの原子性が保証されていないのかと疑って、CreateFileでハンドルを作る際にFILE_FLAG_WRITE_THROUGHを指定してバッファリングを切ってやると、その問題は発生しなくなる。しかし、バッファリングをしないとなるとシーケンシャルアクセスの速度すら遅くなってしまい、UNIX版との性能特性が変わりすぎるので、できればやりたくない。

調べたところ、WriteFileとReadFileはスレッドセーフであり、同じハンドルを介した操作をマルチスレッド間で同時に呼び出してもクラッシュはしない。しかし、WriteFileで更新した領域を直後にReadFile読んだ場合、更新後のデータが読み出されることは保証されるのだろうか。WriteFileが動作している間に同じ領域をReadFileした場合にどうなるかは未定義であってもよいが、ここで言っているのはそうではない。Mutex等のロックである領域を保護しつつ、WriteFileで書き込みを行ってから、ロックを解除した直後に、別のスレッドが同じ領域をReadFileで読み込んだ場合に、WriteFileの結果がきちんと反映されているのかという話だ。仕様を読む限りでは、そのようは保証をした文言は見つからなかった。しかし、Tkrzwのコードはその保証を前提として書かれているので、そうでないと困る。

検証コードを書いて実験してみたところ、WriteFileとReadFileの原子性には問題なさそうなことがわかった。しばらく悩んだが、結局、犯人はSetFilePointerExとSetEndOfFileであることがわかった。UNIXのftruncateがやるようにファイルのサイズを変更するためには、SetFilePointerExで位置を指定して、SetEndOfFileでその位置にファイルサイズを合わせるという手順を取る。2つの操作に分かれている時点で原子性が確保できないので、その2つはクリティカルセクションに入れていたのだが、実はWriteFile/ReadFileとSetFilePointerEx/SetEndOfFileの間でもレースコンディションがあるらしい。WriteFileしている間にファイルサイズが変わるとヌルコードが書き込まれるか、ReadFileしている間にファイルサイズが変わるとヌルコードが読み込まれるかのどちらかだ。よって、RWロックを用いて、WriteFileとReadFileの呼び出しは各々の共有ロックで保護しつつ、SetFilePointerExとSetEndOfFileの連続した呼び出しは排他ロックで保護することが必要になる。こうすると、WriteFileとReadFileは同時に実行されるが、それらを実行しているとファイル切り詰め処理は排他的になる。いやはや、この問題は厄介だった。SetEndOfFileの仕様はもうちょっとちゃんと書いといてほしいところだ。

メモリマップIOに関しては、UNIXではマップされたメモリのアドレス自体が識別子になっているのに対して、Windowsではメモリマップ用のハンドラと実際のメモリマップのポインタが別建てになっているところが少々面倒くさい。それ以外の挙動は全く同じなので、システムコールの読み替えさえ知っていれば簡単に書ける。


まとめ。TkrzwのWindows版をファイルIO層も含めて完全版として実装した。性能評価とチューニングをするには仮想マシンでは不十分なので、やはり実機が欲しくなる。Linuxの作業環境を一旦潰してWindowsを入れ直せばよいのだけれど、Linux側でも作業しなきゃいけないので、どうしたもんか。