DBMのダイレクトI/O対応

ファイルシステムのキャッシュ機構を介さずにストレージデバイスに対して直接入出力を行う機能をダイレクトI/Oなどと言ったりするが、それをデータベースライブラリTkrzwからも使えるようにした。LinuxとWindowsで使える。その前提として、アドレスとサイズがアラインメントされたメモリ空間とのストレージデバイスの間でのデータ転送に限定するブロックI/Oを実現する必要があった。その苦労話と性能評価を語ろう。

世にあるほぼ全てのストレージデバイスは、隣接するデータを一定のサイズでまとめて格納したブロック単位の入出力を実現するハードウェアである。上の図を見てほしい。ファイルシステムは、下層のストレージデバイスの差異を隠蔽して、任意のサイズのデータをファイルとして読み書きする機能を提供してくれる。しかし、あくまでOSとストレージデバイスの間のデータ転送はブロック単位で行われる。ブロックサイズはデバイスによって様々で、512バイト、1024バイト、4096バイト、65536バイトなどがあり得る。さらに、ストレージデバイス上では複数ブロックをセクター単位にまとめて管理されていたりもするらしい。物理的にどうなっているかは完全にハードウェアの製品依存だが、デバイスドライバはブロック単位の転送に専念することで詳細を隠蔽してくれる。

ファイルシステム上では、入出力の対象となるデータのまとまりは、ページとして管理される。各ページはメモリ上の隣接するバイトであり、多くの場合4096バイトである。ページはバッファとかキャッシュとかとも呼ばれる。readシステムコールが発行された際には、該当のブロック群をページに読み出すか、すでにメモリ上にあれば再利用し、そのデータの一部をユーザプロセスのバッファ上に複製する。writeシステムコールが発行された際には、該当のブロック群をページに読み出すか、すでにメモリ上にあれば再利用し、その一部にユーザープロセスのバッファからデータを複製する。writeによって更新されたページはダーティページと呼ばれるが、ダーティページは即座にデバイスに書き戻されるわけではない。一連の更新をまとめてデバイスに転送した方が性能上有利だからだ。典型的には、一定の時間が経過するか、キャッシュ用に割り当てられたメモリが枯渇してきた場合に、ダーティページはデバイスに書き戻される。書き戻されたページはまたクリーンなページに戻る。クリーンなページはいつ破棄されても構わないので、典型的にはLRU（＝最終利用が最も古いもの）なページから破棄されることで、キャッシュのメモリ使用量は一定に保たれる。

ダイレクトI/Oとは、ファイルシステムのキャッシュにアクセスせずに、ストレージデバイスのドライバとの間で直接データを読み出したり書き出したりする手法だ。ファイルシステムがやっていることをユーザプロセス側で一部肩代わりする手法とも言える。当然ブロックI/Oが前提となる。そんなことをして何が嬉しいのか。このIBMの解説がわかりやすい。要するに、キャッシュのヒット率が低すぎて性能上の利点がない場合には、キャッシュは単にメモリとCPUの無駄遣いになるので、デバイスと直接やりとりした方が得だということだ。では、キャッシュのヒット率が低くなるのはどんな場合かというと、巨大なファイル上のランダムアクセスを行う場合だ。例えば、256GBのファイルのランダムアクセスを行うとして、キャッシュに8GBのメモリを使うとしたら、ヒット率は3%ほどになる。つまり97%のアクセスでは、キャッシュ上の既存のページにヒットしないので、新しいページをキャッシュにロードするが、そのページはほとんど再利用されないで、短時間で書き戻されるか単に捨てられるのだ。実際のところ、ファイルシステムはシステム上の余剰メモリを全て使って高速化を図るので、そんな中で巨大ファイルのランダムアクセスを行うと、単に余剰メモリが枯渇してシステムが遅くなるだけだ。

ダイレクトI/Oを使えば、キャッシュ用のメモリを確保したり、キャッシュとの間のデータ転送にかかるCPU負荷を省いて、ストレージとの間の効率的な入出力を行うことができる。preadやpwriteといったシステムコールの応答はデバイスドライバの応答に律速されて遅くなる。ただし、キャッシュが効率的に効いているときの通用のI/Oよりは遥かに遅いが、キャッシュが効率的でないときの通常のI/Oよりは大分マシな性能になる。

現状では、LinuxとWindowsでのみダイレクトI/Oに対応している。Linux上では、openシステムコールにO_DIRECTというフラグをつけるとダイレクトI/Oを行うようになる。それをつけるだけで、カーネル内部でファイルシステムのキャッシュ機構を回避して、直接デバイスドライバとの間でデータ転送を行えるようになる。デバイスドライバをわざわざ書かなくても、preadやpwriteなどのPOSIX標準APIで利用できるというところが素晴らしい。ただし、以下の制限がある。

• ファイルディスクリプタはO_DIRECTをつけて開かれている。
• 転送サイズが512バイトの倍数である。
• ファイル上の転送開始位置が512の倍数にアラインメントされている。
• 転送先や転送元のバッファのアドレスが512の倍数にアラインメントされている。

つまり、以下のpreadとpwriteのシグネチャにおいては、この制限はこう言いかえられる。

ssize_t pread(int fd, void *buf, size_t count, off_t offset);
ssize_t pwrite(int fd, const void *buf, size_t count, off_t offset);

• fdはO_DIRECTをつけてopenされたもの
• buf % 512 == 0
• count % 512 == 0
• offset % 512 == 0

ブロックサイズは512が最低限に設定されているが、実際のデバイスのブロックサイズに合わせた方が高性能になるらしい。いずれにせよ、アプリケーション側でファイルシステムの真似事をしなければならない。これをブロックI/Oと呼ぼう。ダイレクトI/Oを指定するかしないかとは独立して、とりあえずブロックI/Oを実装しておけば、潰しが効きそうだ。ブロックI/Oでは、512バイト未満のデータを読み込むとしても、該当ブロックの512バイトを全て読み込んでから特定部分を取り出さねばならない。512バイト未満のデータを書き込む場合、該当ブロックの512バイトをバッファ上に読み込んでから、特定部分を書き換えて、全体を書き戻さねばならない。複数ブロックにまたがる場合も同様だ。バッファのアドレスも512バイトにアラインメントされていなければならないが、それは前回述べたalloc_alignedを使って行う。

Windows上では、CreateFileのフラグにFILE_FLAG_NO_BUFFERINGをつけると、O_DIRECTと同様の効果が得られる。オフセットとアドレスとサイズに512もしくはそれ以上のアラインメント制約がかかるのも同じである。

LinuxとWindowsの細かい差異として、ファイルサイズをアラインメントさせるかが挙げられる。Linuxの場合、ftruncateはO_DIRECTの影響を受けないので、ファイルサイズを任意に調整できる。WindowsのSetEndOfFileでは、アラインメントされたサイズにしか調整できない。よって、WindowsでダイレクトI/Oのファイルのサイズをアラインメント外に調整するには、一旦ファイルを閉じて通常モードで開き直してからSetEndOfFileを呼ぶ必要がある。

以上のような努力を全て内部で隠蔽して行い、あたかも普通のファイルのように使える機能をファイルクラスPositionalParallelFileに実装した。アプリケーション側は、ブロックを気にすることなく、任意のオフセットに任意の長さのデータを読み書きすることができる。DBMを使わないでこのファイルクラスを使うだけでもTkrzwを使う価値がある。こんな風に普通に使える。

PositionalParallelFile file;
file.SetAccessStrategy(512, PositionalParallelFile::ACCESS_DIRECT).OrDie();
file.Open("sample.txt").OrDie();
file.Write(0, "12345", 5).OrDie();
file.Write(5, "abcde", 5).OrDie();
char buf[6];
file.Read(2, buf, 6).OrDie();
std::cout << std::string(buf, 6) << std::endl;  // -> "345abc"
file.Close().OrDie();

SetAccessStrategyで、2以上のブロックサイズを指定すると、ブロックI/Oが有効になる。また、オプションで、ACCESS_DIRECTを指定すると、ダイレクトI/Oが有効になる。ブロックサイズを1とか512未満にして、ダイレクトI/Oを有効にすることも論理的には可能だが、後でエラーになるだけだ。ブロックサイズをデバイスの特性に応じて1024とか2048とかにする余地はある。オプションにはACCESS_SYNCというのも論理和で加えられるが、その場合にはO_SYNCフラグ（WindowsではFILE_FLAG_WRITE_THROUGHフラグ）によって、全ての書き込み操作がハードウェアの同期完了通知まで待たされる。

Tkrzwの全てのデータベースクラスは、つまり、HashDBM（ハッシュデータベース）もTreeDBM（B+木データベース）もSkipDBM（スキップリストデータベース）も、任意のファイル実装クラスを注入して利用できるようになっている。したがって、ダイレクトI/Oに基づくファイルの実装クラスさえ準備すれば、すべてのデータベースでダイレクトI/Oが利用できるようになる。オブジェクト指向万歳。

実際、ACCESS_DIRECTオプションを有効にしたファイルオブジェクトを組み込んだだけで、ほとんどのテストケースが通ってしまった。ただ、いくつかデータベース側で対応しなければならないこともあった。ファイルサイズが512バイトの倍数とは限らないことだ。その場合、ファイルの末尾の最後の512倍バイトの位置よりも後ろは、読めなくなってしまう。書き込みモードの場合には、次の512倍バイトまでftruncateでファイルを拡張すれば読めるようになるが、読み込みモードの場合にはそうはいかない。よって、ダイレクトI/Oモードで書き込みを行う場合には、データベースクラスの責任で、パディングデータを埋めて、ファイルサイズが512の倍数になるようにしなければならない。ファイルクラスの責任で勝手にパディングデータを埋めると、データベースクラスが知らない謎データでファイルが改竄されている扱いになってしまうので、あくまでデータベース側で対応する必要がある。どのデータベースクラスでも、検索用のブロックチェーンにつながらないダミーのデータを末尾に埋めることで対象できた。

性能上の工夫もした。HashDBMはレコードのインデックスを収めたハッシュテーブルをファイルの先頭に置いて使っている。B+木を扱うTreeDBMでもページデータの管理にHashDBMを使っている。ところで、4バイトの固定長数値表現の配列であるハッシュテーブルの読み書きをする場合、たった4バイトを操作するために512バイトの読み書きが必要となる。これは毎回のレコード操作で行われるため、非常に効率が悪い。よって、ファイルの先頭の指定したサイズに限定してバッファリングを行う機能をつけた。SetHaedBuffer(8192)とかやると、ファイルの先頭8192バイトに相当するブロックを読み出したバッファを作り、以後その領域に該当する読み書きはそのバッファを対象として行う。バッファされた領域は、SynchronizeメソッドかCloseメソッドが呼ばれた際にのみ、ファイルに書き戻される。

ブロックI/Oのおかげで、512バイトにアラインメントされない読み書きも透過的に行えるようになった。しかし、実際には512バイトにアラインメントされている方が効率的なわけで、データベース側にもアラインメント機能があると望ましい。そして、こんなこともあろうかと、Tkrzwの設計時からアラインメント機能は組み込まれている。align_powというチューニングパラメータはデフォルトで3になっており、これは全てのレコードのデータのオフセットが2^3=8バイトの倍数から始まることを意味している。これを9にすれば、2^9=512バイトにアラインメントされるというわけだ。ただし、その場合、キーと値とメタデータの合計サイズが512バイトより遙かに小さいケースでも常に512バイトの領域を専有することになる。なので、実際のアラインメントをいくつにするかは、どんなデータを格納するかによる。平均10KBとかのデータを入れるのであれば、2^10=1024バイトやそれ以上にアラインメントしてもよいだろう。平均1KB未満であれば、2^8=256バイトくらいがいいだろう。ただし、アラインメントがブロックサイズより低くかつマルチスレッドでアクセスする場合、PositionalParallelFileクラスでなくPositionalAtomicFileクラスを使う必要がある。なぜなら、DB層はアラインメントの単位でスレッド間の一貫性を保証するので、ファイル層のブロック管理の都合でアラインメント境界を跨いだ操作が暗黙的に行われるとスレッドセーフでなくなるからだ。

改めて留意すべきは、DB層のアラインメントとファイル層のブロックサイズは独立しているということだ。DB層のアラインメントがファイル層のブロックサイズと同じであるのは性能的に理想だが、必ずしも同じである必要はない。空間効率と時間効率のトレードオフを考えて設定すべきだ。さらに言えば、ファイル層のブロックサイズはデバイスのブロックサイズと同じであることが望ましいが、必ずしも同じである必要はない。LinuxとWindowsでは最低512バイトという制限があるだけだ。実際のブロックサイズと性能の関係はデバイス毎に異なるので、個々人の環境でベンチマークを取って最適な設定を探るしかない。

以上を踏まえて、データベースでダイレクトI/Oを活用するサンプルコードは以下のようになる。

# ダイレクトI/Oモードのファイルを取り込んだデータベースを作る
auto file = std::make_unique<PositionalParallelFile>()
file->SetAccessStrategy(
  512, PositionalFile::ACCESS_DIRECT | PositionalFile::ACCESS_PADDING).OrDie();
HashDBM dbm(std::move(file));

# アラインメントとバケットキャッシュを設定してDBを開く
HashDBM::TuningParameters params;
params.align_pow = 8;
params.cache_buckets = true;
dbm.OpenAdvanced("sample.tkh", true, params).OrDie();

# 普通に読み書きする
dbm.Set("japan", "tokyo").OrDie();
dbm.Set("china", "beijing").OrDie();
dbm.Set("korea", "seoul").OrDie();
std::cout << dbm.GetSimple("japan") << std::endl;

# データベースを閉じる
dbm.Close().OrDie();

めちゃ簡単だろう。ダイレクトI/Oなんて本来はめっちゃ面倒なのに、いけてるライブラリがあれば、こんなに簡単に利用できてしまうのだ。ファイルクラスが隠蔽してくれるおかげでオフセットやアドレスのアラインメントなんて考えなくていいし、そもそもデータベースクラスが隠蔽してくれるおかげで検索アルゴリズムやデータ管理アルゴリズムについて考える必要もない。ストレージデバイスを、単なる巨大な連想配列として、OSに余計な負荷をかけずに、直接扱うことができる。

C++のライブラリはもちろん、JavaとRubyとPythonからも使えるようにしてある。Pythonだとこんな感じになる。

dbm = tkrzw.DBM()
dbm.Open("sample.tkh", True,
  file="PositionalParallelFile", align_pow=8, cache_buckets=True,
  block_size=512, access_options="direct,padding").OrDie()

dbm.Set("japan", "tokyo").OrDie()
dbm.Set("china", "beijing").OrDie()
dbm.Set("korea", "seoul").OrDie()
print(dbm.GetStr("japan"))

dbm.Close().OrDie()

JavaとRubyとPythonからダイレクトI/Oを扱えるライブラリはそんなに多くないと思うので、それらの言語で巨大データを扱いたい場合にはそこそこ役立つだろう。下層のストレージがSSDなどの高速デバイスであれば、ちょっと遅い超巨大連想配列といった位置づけで利用できる。

性能評価をする。機材として、私のノートPCであるDell XPS13を使う。OSはUbuntu 20.04のLinux。CPUはIntel Core-i7 8550Uで、メモリは16GB載せている。ストレージはSSDだが、おそらく高性能なものではない。

以下の検証項目を考えた。双方とも、8GBくらいのデータベースファイルが作られる。いずれも、ファイルに対する読み込みはランダムアクセスになり、書き込みはほぼシーケンシャルになるはずだ。

• "Hash" : HashDBMで、値が8000バイトのデータを100万個、Set、Get、Removeする。
• "Tree" : TreeDBMで、値が80バイトのデータを1億個、Set、Get、Removeする。

Hashの動作の内訳を考えると、レコード本体の読み込みに平均1回ちょっとのファイルアクセスを必要となる。ハッシュテーブルのアクセスは完全にキャッシュされるのでファイルアクセスは発生しないので、レコード本体の読み出しのみをファイルから行う。ハッシュの衝突があるので1より増える。Treeの動作は、より複雑だ。複数のレコードがB+木のページにまとめられて読み書きされ、合計200万ページくらい読み書きとなる。その各々で平均1回ちょっとのファイルアクセスが発生する。Treeの方がスループットが高いのはレコード数とレコードサイズが違うことによる。

それぞれの検証項目に対し、以下のファイル実装で性能を測定する。

• "mmap" : mmapによるファイル実装
• "normal" : pread/pwriteによるファイル実装で、通常I/O
• "direct" : pread/pwriteによるファイル実装で、ダイレクトI/O

結果は以下のようになった。単位はQPS（クエリ毎秒）。

	mmap Set	mmap Get	mmap Remove	normal Set	normal Get	normal Remove	direct Set	direct Get	direct Remove
Hash	120435	464640	103931	124111	291351	124409	8225	3927	1973
Tree	1171394	1335418	1142689	1196678	1227268	1114940	309542	147918	55438

予想通り、ダイレクトI/Oは遅い。しかし、これがデバイスそのものの性能なのだ。この検証はハードウェアのブロックI/Oのスループットを測っているのとほ同義だ。意外なのが、HashのダイレクトI/Oで、SetよりGetが遅く、それよりさらにRemoveが遅かったということだ。普通に考えると、書き込みより読み込みの方が早そうなものだが、必ずしもそうでもないらしい。百歩譲って書き込みの方が早いとしても、それならなぜRemoveが遅いのかの説明がつかない。バックグラウンドで何かやるおかげで後の方の操作の方が遅くなったりするのかもしれないが、全く検討違いなことを言っているかもしれない。ダイレクトI/Oの性能特性やチューニングについては全く知見がないというのが正直なところだ。追って、実際のユースケースを想定した性能評価をしたいところだ。

mmapによるファイル実装を使うと、当然、プロセスの使用メモリはファイルサイズと同等の8GB以上になる。pread/pwriteによる通常のファイルI/Oでは、プロセスの使用メモリは増えないが、ファイルシステムのメモリ使用状況が悪化する。そもそもファイルシステムはほぼ全ての余剰メモリを使うので、メモリ使用量としては体感しづらい。しかし、8GB相当の既存のページを捨てさせているはずで、それはシステム全体の性能を低下させる。pread/pwriteによるダイレクトI/Oでは、そういった大量ページ粛清が起こらない。

とりあえず今言えるのは、数千QPSが許容できるスループットなのであれば、ノートPCの貧弱SSD上のダイレクトI/Oでもそこそこ使い物になるということだ。それでいてファイルシステムにかける負荷は少ないので、でかいデータを扱う際には便利だと思う。

Mac OSというかDarwinでもダイレクトI/Oはサポートされているらしく、fcntlにF_NOCACHEを渡すとできるとかできないとかいう話だ。気が向いたらそちらも検証する。

まとめ。データベースライブラリTkrzwにダイレクトI/O機能をつけた。DBMのシンプルなインターフェイスで、ストレージデバイスの読み書きを直接的に行うことができる。メモリ消費を抑えつつ比較的大きいサイズのレコードを大量に扱いたいという場合には役立つだろう。