各種データベース実装と各種ファイル実装の性能比較

dependency injectionで任意のファイル実装を利用できるTkrzwだが、ダイレクトI/Oのファイル実装を各種のデータベースに組み込んだのが前回までの物語である。Tkrzw 0.9.18をリリースしたので、お試しいただきたい。今回は、完成した実装の性能を測定する。ダイレクトI/Oがどのくらい実用になるのか知りたいだろう。キャッシュの活用が重要概念になってくる。

先に、全体の説明を通じた用語の整理をしておきたい。4層の異なるキャッシュが関係してくるので、何について語っているのかを区別するのが重要だ。

• デバイス内キャッシュ : デバイスの内部で最近使われたブロックの内容をメモリ空間に保持する機構
• システム内キャッシュ : OSの一部であるファイルシステムの中で、ファイル内の連続した領域（4096バイト）を「ページ」としてメモリ空間に保持する機構
• ファイル内キャッシュ : 私が実装したファイルクラスの中で、ファイル内の連続した領域（任意だが512バイトとか1024バイトとか）を「ページ」としてメモリ空間に保持する機構
• データベース内キャッシュ : 私が実装したデータベースクラス（B+木）の中で、論理的に関連するレコードを「ページ」としてメモリ空間に保持する機構

今回の実験で扱うデータベースとアクセスパターンを想定する。

• HashDBM（ハッシュテーブル）の更新
• HashDBM（ハッシュテーブル）の検索
• TreeDBM（B+木）の更新
• TreeDBM（B+木）の検索
• SkipDBM（スキップリスト）の更新
• SkipDBM（スキップリスト）の検索

各操作を100万回ずつやることにしよう。毎回の操作で1から100万の数値からランダムにキーを決めると、63万件がユニークになり、27万件は重複する。既存のキーと重複した場合には上書きする。よって、最終的には63万件のデータベースが構築される。キーがランダムな8バイトの文字列で、値は100バイトの適当な文字列にする。合わせて108バイトが正味のデータになるが、データベースの種類によるフットプリント（管理用データ）が付くので、各レコードのサイズは120バイト弱になる。

ファイルの実装は以下のものを想定する。

• mmap : MemoryMapParallelFile（メモリマップI/O）
• pos : PositionalParallelFile（通常I/O）
• pos-block : PositionalParallelFile+Cache（ブロックI/O）
• pos-block-cache : PositionalParallelFile+Cache（ブロックI/Oとキャッシュ）
• pos-direct : PositionalParallelFile+DirectIO（ダイレクトI/O）
• pos-direct-cache : PositionalParallelFile+DirectIO+Cache（ダイレクトI/Oとキャッシュ）

またいくつか用語が出てきたので、整理する。

• メモリマップI/O : mmapで確保仮想メモリ上の領域を直接読み書きする。その仮想メモリ上の領域はファイルシステムの責任でファイルの内容に同期される。
• 通常I/O : preadおよびpwriteを使った通常のファイル入出力。ファイル内の絶対的な位置を指定してランダムアクセスできて便利。読み書きの内容はファイルシステムの責任でファイルの内容に同期される。
• ブロックI/O : preadおよびpwriteを使ったファイル入出力だが、読み書きの位置もデータサイズもブロックサイズの倍数になる制約をファイルオブジェクトの責任で設けたもの。読み書きの内容はファイルシステムの責任でファイルの内容に同期される。
• ダイレクトI/O : ブロックI/Oを前提として、ファイルにO_SYNCフラグをつけて開くことで、ファイルシステムを介さずにデバイスドライバとの間で直接的に入出力を行う。

今回の実験の目的はダイレクトI/Oの性能を知ることである。他の3つは比較対象として実験に含める。ダイレクトI/Oを使わないただのブロックI/Oは実際のユースケースでは無意味な設定だが、ユーザプロセス内の挙動がダイレクトI/Oと全く一緒になるので、下層のダイレクトI/O機構のオーバーヘッドを知るための比較対象として最適なのだ。

レコード数が63万個だとメモリに乗り切るので、mmapが最も高速になる。通常I/Oも同じ理由で高速になる。システムコールのオーバーヘッドを伴うが、システム内キャッシュが活用されるからだ。ブロックI/Oは通常I/Oに無駄な制約をつけただけなので、ファイル内キャッシュを使わない場合、単にシステムコールを呼ぶ回数が増えて転送するデータ量も増えるだけなので、遅くなる。ダイレクトI/OはブロックI/Oと同じ挙動だが、ファイルシステムのメモリを使わないで毎回デバイスドライバの応答を待つため、桁外れに遅くなる。ブロックI/OとダイレクトI/Oにそれぞれファイル内キャッシュをつけると、システムコールを呼び出して入出力を行う回数が減り、またシステム側での処理が効率化するので、キャッシュがヒットするならば、性能が改善する。ファイル内キャッシュの導入によってどの程度性能が改善するのかというのが、今回の見どころだ。

ファイル内キャッシュの構造は前回述べた線形リストから変更して、双方向連結リストとハッシュ表を組み合わせたLRU削除機能付きのものに変えた。これによってキャッシュするページの数に関わらず一定のオーバーヘッドで動作するようになった。とはいえ256ページしかキャッシュしないので、63万レコードの規模から考えると、ほんの一部のデータしかファイル内キャッシュには乗らない。設定で増やすのは簡単だが、敢えて容量を抑えて、局所性が非常に高い場合のみにしか有効に働かないようにしている。

検証は自分のノートPCのLinux上で行う。筐体はDellのXPS 13で、/proc/cpuinfoによると、CPUはIntel Core i7の1.8Ghzで、8コアらしい。RAMは16GB搭載。ストレージはNVMe接続のSSDで、hdparmによると、ハードウェアのキャッシュありで16274MB/secで、キャッシュなしで637MB/secの性能らしい。転送のスループットでなくランダムアクセスの能力の方が大事なのでこの数値はあまり当てにならないけども。

HashDBMの実験を行う。上述の通り、レコードサイズは120バイトくらいになるので、128バイトでレコードをアラインメントする。バケット数はレコード数の2倍にするので、ハッシュ値の衝突率は30%とかに抑えられるだろう。このシナリオを実現するには、こんなコマンドを実行すればよい。

$ ./tkrzw_dbm_perf sequence --path casket.tkh --file mmap-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000
$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000 --cache_buckets
$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000 --cache_buckets --block_size 512 --padding
$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000 --cache_buckets --block_size 512 --padding --pagecache
$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000 --cache_buckets --block_size 512 --direct_io --padding
$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_seed -1 --random_key --size 100 --buckets 2000000 --align_pow 7 --iter 1000000 --cache_buckets --block_size 512 --direct_io --padding --pagecache

メモリマップI/Oでは、基本的にデータが事前読み込みと遅延書き込みで処理されるので、ストレージデバイスにアクセスする回数は非常に少ない。メモリに乗る限りの規模においては最速のモードである。通常I/Oでは、前回の述べたバケットキャシュを有効にするので、ハッシュ値が衝突しない限り、各レコードの操作で実際のファイル入出力は1回で済む。ただし、読み書きしたレコードが属する4096バイトの領域はページとしてシステム内キャッシュに乗せられるので、デバイスとのやり取りの回数は、この規模では、メモリマップI/Oと大差ないはずだ。ブロックI/OやダイレクトI/Oでも、ファイル内キャッシュの一種であるバケットキャッシュを有効にするので、実際のファイル入出力は、ハッシュ値が衝突しない限り、各レコードの操作で1回で済む。ただし、各レコードの読み書き必要なファイルアクセスについてはより詳細に検討する必要がある。ファイル内キャッシュを使わない場合、操作の回数の分だけデバイスを叩くことになる。この規模だとデバイス内キャッシュがそれなりに効くはずだが、どの程度役に立つかは実験してみないとわからない。

結果は以下の通りだ。単位はQPS（クエリ毎秒）。

	set	get
mmap	1,118,605	1,261,031
pos	490,103	793,348
pos-block	324,885	728,326
pos-block-cache	445,521	610,674
pos-direct	5,323	12,769
pos-direct-cache	15,543	12,500

メモリマップI/Oのスループットが100万QPSを超えるのは、メモリの読み書きをしているだけなので、当然とも言える。これを基準として、他の設定の結果は全てファイルクラスの層とそれより下層のオーバーヘッドを反映しているとみなしてよい。通常I/Oにすると、それだけでスループットが半減する。システムコールを呼ぶコストだろう。ブロックI/Oにすると、さらに性能が落ちる。それにファイル内キャッシュをつけると、Setの性能だけが少し改善する。これはSetの際にだけファイル内キャッシュがそれなりに効くことを示唆している。ではなぜGetの性能が下がるのかというと、ファイル内キャッシュの検索と更新にかかるコストが原因である。

予想通り、ダイレクトI/Oは遅い。桁違いどころか、3桁違いに遅い。そして、ファイル内キャッシュをつけるとSetの性能がかなりマシになることがわかった。わざわざ自前のキャッシュ機能を実装した甲斐があるというものだが、それでも遅いもんは遅い。しかし、この、Set = 15543 QPS、Get = 12500 QPS という結果こそが、普通の安いSSDを使って、局所性を利用したファイルシステムのキャッシュによる性能向上が一切無駄になる規模での、データベースの真のスループットである。これより早いアルゴリズムもソフトウェアも存在しないのだ。ハードウェアの性能だけがスループットを決める世界である。

ところで、局所性が低いはずのハッシュデータベースの操作でなぜ更新処理だけプロセス内のキャッシュが効くのだろうか。アラインメントが128で、ブロックサイズが512バイトであれば、1ブロックに4レコードが格納される。 よって、63万レコードは16万ブロックに格納される。今回の実装では直前256ページしかキャッシュしないので、ランダムなブロックにアクセスすれば、キャッシュのヒット率はほぼゼロになるはずだ。しかし、実際には多少の局所性がある。

更新処理で何が起きるのかを考える。まず、キーから算出したハッシュ値に対応するバケットを調べて該当のレコードの有無を知る。全てのバケットはオンメモリなので、この時点ではファイルアクセスはない。キーが重複するレコードが存在する27万回は既存レコードの領域の読み出しを行い、読み出した領域はすぐに新しいレコードのデータで書き換えられる。この操作にはキャッシュが効く。レコードサイズは128バイトなので、そのレコードのデータを書き換える際には、先に同じブロックの既存データを読み込んで、該当のレコードの128バイトを書き換えてから、512バイトを書き戻す。よって、既存レコードの上書きには、キャッシュが効かない場合、読み込み2回と書き込み1回が発生する。キャッシュを効く場合には、先に読み込んだデータをそのまま使うので、読み込み1回と書き込み1回になる。既存レコードがない63万レコードでは、ファイルの末尾にレコードを書き足す。ここで末尾への局所性が起こる。キャッシュが効かない場合、各レコードで読み込み2回と書き込み1回が発生する。キャッシュが有効な場合、4レコード毎にまとめて書き込み1回が発生するだけである。ファイル内キャッシュ付きダイレクトI/Oのケースで実際にログを取ったところ、ページの読み込み要求が152万回で、そのうち84万回は既存ページの再利用に成功していた。ダイレクトI/Oの読み込み要求数は66万回、書き込み要求数は54万回であった。結論として、更新処理においてはファイル層のキャッシュはそこそこ役立つということが確かめられた。

検索処理で何が起きるのかを考える。まず、キーから算出したハッシュ値に対応するバケットを調べて該当のレコードの有無を知る。全てのバケットはオンメモリなので、この時点ではファイルアクセスはない。該当のレコードが存在する確率は63%であり、つまり63万回くらいはバケットに書き込まれたオフセットのブロックの読み込みを行う。ハッシュ値が衝突する場合には読み込みの回数が増える。ファイル内キャッシュ付きダイレクトI/Oのケースで実際にログを取ったところ、ページの読み込み要求が84万回で、そのうち512回だけしか既存ページの再利用には成功していなかった。当然ながら、ダイレクトI/Oの読み込み要求数は84万回、書き込み要求数は0回であった。結論として、検索処理においてはファイル層のキャッシュは全く役に立たないということが確かめられた。

TreeDBMの実験を行う。B+木の実装は、それ自体がデータベース内キャッシュとして機能する。レコードを詰め込んだページのサイズが4060バイトを超える場合にページの分割が行われるようにチューニングしよう。期待値として2015バイトから4060バイトまでの間のサイズのページを単位としてページの読み書きが行われる。アラインメントはデフォルトの1024バイトなので、ブロックI/Oに由来する無駄は発生し得ないが、アラインメントのためのパディングによる空間効率と時間効率の無駄はある。この設定だと1ページの最大レコード数は31件なので、63万レコードは少なくとも2万ページに分割されて保存される。実際にはその2倍くらいになるだろう。これらを全部キャッシュに乗せてしまうと大規模運用時の挙動を再現できないので、キャッシュするページ数を1000ページに抑える。このシナリオは、こんなコマンドになる。

$ ./tkrzw_dbm_perf sequence --path casket.tkt --file mmap-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000
$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000
$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000 --cache_buckets --block_size 1024 --padding
$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000 --cache_buckets --block_size 1024 --padding --pagecache
$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000 --cache_buckets --block_size 1024 --direct_io --padding
$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000 --cache_buckets --block_size 1024 --direct_io --padding --pagecache

メモリマップI/Oが高速なのは当然だが、毎回のファイル入出力で使われるデータが大きい分、性能の差が小さくなるはずだ。ダイレクトI/Oとその他の方式の差も相対的には小さくなるだろう。そして、いずれの方式でも、ファイル内キャッシュは意味がないだろう。有限のリソースであるメモリはファイル内キャッシュでなくデータベース内キャッシュに割り当てた方がよい。

今回のシナリオでは、データベース内キャッシュに乗せるノード数を抑えているので、結果的に内部ノードしかキャッシュされない。よって、毎回のアクセスで末端ノードのデータのためのファイルアクセスが発生する。その際に期待値として3KB程度の入出力が発生する。広い範囲に渡って既存領域を何度も書き換えるので、ファイル内キャッシュは効かないはずだ。100万回のsetをして63万レコードが保存された状態では、ログによると、内部ノードの数は258個、末端ノードの数は50354個になるようだ。つまり、末端ノードの各ページには平均12.5個くらいのレコードが格納され、シリアライズすると1600バイトを少し超えるくらいのデータになる。これを1024にアラインメントするので、ほとんどの末端ノードは2048バイトのデータとしてファイルに格納される。

結果は以下の通りだ。単位はQPS（クエリ毎秒）。

	set	get
mmap	123,094	178,123
pos	73805	126,449
pos-block	77,207	132,956
pos-block-cache	47,112	97,567
pos-direct	1,895	4,140
pos-direct-cache	1,326	2,657

メモリマップI/Oが最速だが、通常I/OやブロックI/Oもそこそこ頑張っている。データベース内キャッシュのページのアラインメントとファイルのブロックサイズが同じなので、通常I/OとブロックI/Oの動作はほぼ同じになる。よって、その二つの性能がほぼ同じなのは当然だ。そして、予想した通り、ファイル内キャッシュは全く性能向上に寄与しない。むしろ性能が劣化するので、使う意味が全く無い。

ここでも、ダイレクトI/Oは遅い。それはともかく、ハッシュ表とB+の結果が数倍しか変わらないのが面白いところだ。計算量で考えるとハッシュ表のO(1)に対してB+木のO(log N)は大きく劣るはずだが、実運用上の性能はオーダー上は変わらない。なぜなら、大規模なデータベースでもB+木の末端ノード以外のノードはデータベース内キャッシュに乗るので、毎回の検索や更新の操作におけるファイルアクセスは1箇所で済むからだ。つまりファイル層へのアクセスパターンは実はハッシュ表とほぼ同じで、ページ単位で入出力を行う分だけ転送量が増えるところが異なるだけだ。B+木を考えた人は偉大だ。

更新処理で何が起きるのかを考える。既に述べたように、中間ノードのデータはメモリ上にあるので、その木構造を辿って末端のノードを特定する。そしてそれをファイルから読み出す。読み出しはファイル操作1回で済み、アラインメントされたページデータを読み出すだけだ。更新された末端ノードは遅延書き込みで処理されるが、データベース内キャッシュのヒット率が低いことから、かなり短期間でファイルに書き戻される。一定数のレコードが追加されて末端ノードが分割された場合、新たに作られたノードとその上位の中間ノードにもフラグが立てられ、遅延書き込みの対象となる。とはいえページ分割の頻度はレコード単位の更新回数よりもかなり少ない。ハッシュデータベースの場合と同じように、新規のノードをファイルに書き込む際には、ファイルの末尾のブロックに操作が集中する。ファイル内キャッシュ付きダイレクトI/Oのケースで実際にログを取ったところ、ページの読み込み要求が1164万回で、そのうち492万回が既存ページの再利用に成功していた。ダイレクトI/Oの読み込み要求数は377万回、書き込み要求数は95万回であった。キャッシュのヒット率が42%もあるのは意外だが、これは単にデータベース層の実装の都合に起因するものである。あるノードのデータを読み込むとして、そのデータのサイズが事前にはわからないので、ノードのヘッダ部分だけを先に読み込んでサイズを調べてから、そのノード全体を読み込むという実装になっている。つまり同じ領域を二度読みすることがある。キャッシュが有効の場合、二度目の読み込みの際にはキャッシュが効くので、見かけ上局所性があるように見えてしまう。この挙動に関してはいずれ改善したい。

検索処理で何が起きるのかを考える。更新処理と全く同じように操作対象の末端ノードを特定して読み込み、該当のレコードがそこにあればそれを処理する。ランダムアクセスの場合、局所性の欠如により、ほぼ毎回の操作で末端ノードのデータの読み込みが発生する。上述した重複読み取りの分が加算されるので、200万回の読み取りが発生する。DB層の各ページはファイル層の2から3ページで構成されるので、その回数だけファイル内キャッシュの読み込みを行う。ファイル内キャッシュ付きダイレクトI/Oのケースで実際にログを取ったところ、ページの読み込み要求が431万回で、そのうち96万回が既存ページの再利用に成功していた。ダイレクトI/Oの読み込み要求数は335万回、書き込み要求数は0回であった。だいたい予想通りだ。

設計通りの実験結果には満足しているが、改めて考えてみると、最適な設計とは言い難い部分がある。とりあえず、ノードのヘッダだけ読み込むのがダサい。また、ページ内キャッシュの構造に合わせて、連続したブロックの読み書きをブロック単位で複数回に分けて読み込んでいるのもダサい。さらに、ダーティページを書き出す際に、隣接するブロックをまとめてクリーンアップする処理を実装すべきだ。

SkipDBMの実験を行う。スキップリストの構築はメモリ上のバッファと中間ファイルを用いたマージソートで行われ、ファイルアクセスはシーケンシャルにしか行われない。なので、SkipDBMの更新処理で使われる中間ファイルではブロックI/OやダイレクトI/Oの実装はせず、メモリマップI/Oか通常I/Oで処理する。検索に関してはスキップしながら二分探索を行うので、ランダムアクセスになる。よって、構築後のデータベースファイルはダイレクトI/Oで利用できるように実装している。なお、SkipDBMはキーの重複を許すので、レコード数は63万ではなく100万になる。

スキップリストのチューニングで最も重要なのは、ステップ単位の設定である。デフォルトは4で、これは各レコードを平衡木のノードとみなした場合に4つの枝が生えていることを意味する。つまり階層を一つ辿る毎に探索範囲が4分の1になる。逆に言えば、全体の階層は4を底にしたレコード数の対数になるということだ。検索処理の最後には、4つの隣接したレコードを1つずつ辿ることになる。ここで局所性が最大になる。つまり、ファイル内キャッシュの性能を活かすには、ステップ単位を大きくした方がよい。少なくとも、単一のブロック内に収まるレコードの数以上にはした方がよい。今回は、ブロックサイズを1024にしよう。そうすると1ブロックに8個くらいのレコードが入る。末端で2ブロックのシーケンシャルアクセスを行わせるとすれば、ステップ単位は16くらいが良さげだ。そうすると、16を底にした100万レコードの対数は4.81なので、5階層の平衡木が作られることになる。このシナリオは、こんなコマンドになる。

$ ./tkrzw_dbm_perf sequence --path casket.tks --file mmap-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000
$ ./tkrzw_dbm_perf sequence --path casket.tks --file pos-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000
$ ./tkrzw_dbm_perf sequence --path casket.tks --file pos-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000 --block_size 1024 --padding
$ ./tkrzw_dbm_perf sequence --path casket.tks --file pos-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000 --block_size 1024 --padding --pagecache
$ ./tkrzw_dbm_perf sequence --path casket.tks --file pos-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000 --block_size 1024 --direct_io --padding
$ ./tkrzw_dbm_perf sequence --path casket.tks --file pos-para --random_seed -1 --random_key --size 100 --step_unit 16 --max_level 5 --iter 1000000 --block_size 1024 --direct_io --padding --pagecache

SkipDBMでもスキップリストのデータベース内キャッシュが実装されている。これは根に近い上位ノードのみをキャッシュする実装になっている。逆に言えば、末端に近いノードはキャッシュされない。しかし、スキップリストを使った二分探索というアルゴリズムの特性上、検索処理の終盤は位置が近いレコードに連続的にアクセスするので、単一操作内でのアクセスパターンの局所性はそれなりにある。つまり、上位ノードは複数の操作にまたがって局所性があるのでデータベース内キャッシュが有効活用され、下位ノードは単一操作内での局所性が高いのでファイル内キャッシュが有効活用されるというわけである。実のところ、ファイル内キャッシュの実装を決断したのはSkipDBMをダイレクトI/Oモードでも実用的な速度で利用できるようにするためである。

結果は以下の通りだ。単位はQPS（クエリ毎秒）。

	set	get
mmap	399,456	210,161
pos	264,601	103,596
pos-block	211,099	93,662
pos-block-cache	313,009	142,370
pos-direct	4,935	1,169
pos-direct-cache	115,116	5,194

毎度のことながらメモリマップI/Oが最速だ。通常I/OやブロックI/Oでの性能劣化はHashDBMと同程度である。SkipDBMのデータベース層ではアラインメントはなく、レコードのサイズである120バイトくらいを単位としたランダムアクセスが行われる。よって、アラインメントはあるが128バイト単位に設定したHashDBMの実験結果と似た感じになるのは納得がいく。通常I/OとブロックI/Oの結果を比較すると、ブロックI/Oを使っても利点はないが、それほどオーバーヘッドは大きくないことがわかる。ブロックI/Oにファイル内キャッシュを使うと構築も検索も高速化する。上述したように、構築時にも中間ファイルの読み書きはシーケンシャルアクセスで行われるし、検索時にも末端ノードはシーケンシャルアクセスで読み取られるので、この結果は納得のいくものだ。

そして、やはりダイレクトI/Oは遅い。しかし、ファイル内キャッシュを有効にすると、構築が115116 QPS、検索が 5194 QPSという実用的な性能で利用できるようになる。理論的には、テラバイト級の規模のデータベースでもそんなに変わらない検索性能になるはずなので、スキップリストはやはり大規模なデータベースに向いていると言えそうだ。バッチ更新しかできないというのが玉に瑕だが、それを分かって使う分には、めちゃ便利だ。ダイレクトI/Oならシステム内キャッシュが汚れないので、超大規模なデータベースをそこそこ高性能なストレージ上で運用するには最適な形態とも言える。データマイニングとかにもうってつけだ。

なお、構築時のファイル内キャッシュのログを見ると、ページの読み込み要求は117万回で、そのうち106万回は再利用に成功していた。シーケンシャルアクセスは同じブロックに連続してアクセスするので、局所性が極めて高くなる。検索時には、ページ読み込みの要求は948万回で、そのうち754万回は再利用に成功していた。こちらも予想通りで、検索操作の終盤で起きるシーケンシャルアクセスの効率化に成功している。

まとめ。ダイレクトI/Oを使ってシステム内キャッシュを回避した場合でも、ファイル内キャッシュを管理するファイル実装を使うと、スループットが向上する場合がある。特に、HashDBMの構築と、SkipDBMの構築および検索で大きな効果がある。ダイレクトI/Oは積極的に使うものではないが、大規模なデータベースではダイレクトI/Oを使わざるを得ないこともある。データベースファイルのサイズが明らかに実メモリに乗り切る規模ならメモリマップI/Oを使うべきで、それが怪しい場合には通常I/Oを使うべきだ。そして、データベースファイルのサイズが実メモリのサイズの何倍もあって、システム内キャッシュのヒット率も期待できないことが明らかな場合には、ダイレクトI/Oを使わざるを得ない。HashDBMとSkipDBMをダイレクトI/Oで運用する場合、ファイル内キャッシュを有効にして損はない。TreeDBMではデータベース内キャッシュが存分に働くのでファイル内キャッシュを使う利点はない。

それにしても、ダイレクトI/Oを使った実験からは学ぶことが多い。システム内キャッシュがお世話をしてくれるおかげで普段はファイル入出力の遅さに気を使うことはあまりないが、ダイレクトI/Oを使うと嫌でも気付かされる。不要な入出力を行っていたら、それは如実な性能劣化として現れるようになる。常に計算量を意識して設計と実装を進めるのがまともなプログラマであるが、局所性という概念も忘れちゃいけないなと改めて思う次第だ。