豪鬼メモ

一瞬千撃

DBMの設計と実装 その8 ファイルクラス毎の性能

前回設計した4つのファイル具象クラスを実装し、その性能を測ってみた。


mmapありファイルロックなしであるMemoryMapParallelFileというクラスと、mmapありファイルロックありであるMemoryMapAtomicFileというクラスと、mmapなしファイルロックなしであるPositionalParallelFileというクラスと、mmapなしファイルロックありであるPositionalAtomicFileというクラスを実装してみた。それらの性能を図りたい。

まずは、1スレッドで、100バイトの文字列を1000万回書き込むテスト。ファイルサイズは1000000000バイト(954MB)になる。オフセットを0、100、200とずらして書き込むシーケンシャルアクセスと、オフセットをランダムに決めるランダムアクセスの両方を測定した。シングルスレッドだとそれぞれのクラスでスループットはどれくらい出るのか。

クラス Seq Write Seq Read Rnd Write Rnd Read
MemoryMapParallelFile 7,581,742 QPS 12,014,696 QPS 4,563,364 QPS 4,838,227 QPS
MemoryMapAtomicFile 7,858,269 QPS 12,794,807 QPS 4,480,116 QPS 4,905,746 QPS
PositionalParallelFile 950,962 QPS 1,351,362 QPS 739,976 QPS 1,018,328 QPS
PositionalAtomicFile 950,187 QPS 1,331,649 QPS 735,836 QPS 993,415 QPS

まずわかるのは、メモリマップI/Oが圧倒的に効率的だということだ。シーケンシャル書き込みで8倍くらい、シーケンシャル読み込みで10倍くらい、ランダム書き込みで6倍くらい、ランダム読み込みで5倍くらいメモリマップI/Oが高速だ。そして、当然ながら、シングルスレッドの場合はロック機構による差はあまり出ない。

次に、10スレッドで100バイトの文字列を100万回ずつ書き込む。全体の操作回数は上と同じになる。そして上と同じくシーケンシャルアクセスとランダムアクセスの両方を測定する。マルチスレッドだとそれぞれのクラスでスループットはどれくらい出るのか。

クラス Seq Write Seq Read Rnd Write Rnd Read
MemoryMapParallelFile 7,698,532 QPS 10,020,994 QPS 7,643,432 QPS 9,144,095 QPS
MemoryMapAtomicFile 2,378,891 QPS 10,230,659 QPS 1,427,267 QPS 9,538,727 QPS
PositionalParallelFile 1,084,185 QPS 5,610,970 QPS 770,063 QPS 5,360,002 QPS
PositionalAtomicFile 182,761 QPS 5,434,638 QPS 136,015 QPS 5,011,813 QPS

まず、mmapありのロックなしであるMemoryMapParallelFileの結果に着目しよう。シングルスレッドの時と比べて、シーケンシャルアクセスのスループットが変わっていないかむしろ悪化している。つまり並列化の恩恵がない。これはファイル末尾に対する操作はメタデータの保護のためにロックがかかるからなのか。しかし、atomic整数を先にチェックすることで占有ロックがかかる確率を限界まで下げているはずで、メモリにmemcpyする操作は共有ロック内でしか行っていないわけで、なんか腑に落ちない結果でもある。一方でランダムアクセスのスループットは並列化によって1.7倍程度に向上しているので、実装にミスがあるというわけでもなさげだ。

次に、mmapありのロックありであるMemoryMapAtomicFileの結果に着目しよう。ファイル全体のreader-writerロックを使っている。占有ロックがかかる書き込み操作のスループットはシングルスレッドの時に比べて激減しているので、ロックでブロックされた場合のコストがいかに高いかというのがよくわかる。逆に考えると、スループットがほとんど悪化していないMemoryMapParallelFileの実装はシーケンシャルアクセスにおいてもうまく行っているとも言える。共有ロックは読み込み操作同士をブロックしないので、シーケンシャル読み込みとランダム読み込みの性能はロックありでも高い。

次に、mmapなしのロックなしであるPositionalParallelFileの結果に着目しよう。mmapの結果とは異なり、シーケンシャル読み込みのスループットが顕著に向上している。シーケンシャル書き込みのスループットはほとんど変わっていない。また、ランダム読み込みのスループットは向上するが、ランダム書き込みのスループットは変わらない。つまり、pwriteはあまり並列化の恩恵がないが、preadの並列化はかなり利くらしい。pwriteとpreadの性能はシーケンシャルアクセスでもランダムアクセスでもそんなに変わらない。もちろんこれは全ページがファイルシステムのキャッシュに乗っている規模だからだけども。

最後にmmapなしのロックありであるPositionalAtomicFileの結果に着目しよう。やはり、占有ロックのスレッドがブロックしまくるせいだろう、書き込みがシーケンシャルでもランダムでも遅い。読み込みはきちんと並列化しているので、読み込みが多いユースケースならこれでも十分に使えるシーンがあると思うけども。

総評として、やはりmmapありのロックなしであるMemoryMapParallelFileの性能が良い。シングルスレッドでもマルチスレッドでもそこそこ早く、読み込みも書き込みも弱点がない。ただ、正直なところ、マルチスレッドの書き込みのスループットがもう少し高くなることを期待していたので、期待外れ感はある。でも、実装を見直してもミスは見つけられなかった。そんなもんなのかなぁ。ソースを公開したら識者の意見を仰ぎたいところだ。それはそうとして、MemoryMapParallelFileの上にハッシュテーブルのDBMを実装すると、1GB程度のデータベースだったら、Getで300万QPS以上は出る見込みだ。ハッシュテーブルならバケットとレコード本体の2回の読み込みで検索が完了するのだから。