組み込みDBの速さを体感する

ここ数日、VKV という readonly & 組み込み用途の KVS を動かして遊んでいる。

VKV については作者の hadashiA さんがハイパー省メモリかつ高速な readonly 組み込み DB を Unity にぶちこもうという記事を書いていて、どんな思想で作っているかが紹介されており、とても面白い。

自分が何をして遊んでいるかというと、主に色々なベンチマークを取っている。

現時点でリポジトリに上がっているベンチマークは、以下のようにかなりシンプルなものだ。

ただ、DB のパフォーマンスはワークロード次第なわけで（DB に限った話ではないが）、もう少し実世界のユースケースに寄せたものも見てみようと思い、以下のような条件を試してみた。

固定キーではなく Zipf 分布でキーを選択
- skew は 0.5 / 0.99 をそれぞれ試す
キーを可変長文字列にする
キー空間を拡張
- 〜1,000,000 個
バリューサイズを拡大
- 〜512 バイト
アクセス順をランダムにしつつ、全データに最低 1 回はアクセス
Warmup を行わない Cold start
- 少量データでは Warmup によってメモリに載り切ってしまうが、実運用ではキャッシュされていないケースも多いはず

正直なところ、ちゃんとベンチマークが取れているかにはあまり自信がない。また VKV 自体もまだプレビュー状態なので、具体的な数値はここでは載せない。

それでも、自分が普段触っているサーバー型の RDB では見たことのない lookup 速度が出ている、という印象は強く残った。

例えば、

といった条件でも、B-Tree に優しいキー昇順で全件スキャンすると、1 lookup あたり 1 μs は軽々と下回る。

さらに、データ量を減らしてメモリに載せ切り、Warmup した状態では、ランダムアクセスでも 100 ns 前後になるケースもあった。

ということで、こんな印象を持った。

色々ベンチマークとって遊んでいて理解深まってきたこととして、データサイズがそこまで大きくないケースで Warmup した VKV に対抗できるのはインメモリ & 排他制御なしのデータ構造(Java でいうと TreeMapなど)だろうなと

ちなみに、ChatGPT にインメモリ前提のデータ構造の速度感を聞いてみた結果は以下の通り。

さて、ns オーダーとなると、たとえ readOnly に最適化されていたとしても、サーバー型の RDB で達成するのはかなり厳しい。

プロセス間通信やクエリエンジンを通す時点で、物理的に無理がある、というのが自分の理解。

一方で、組み込み DB を理想的な条件で動かした場合、単純な lookup であれば ns オーダーに到達できる、ということが見えてきた。

例えば、手元で動かした LMDB は、Warmup 後に数百 ns 程度で lookup できた。

また SQLite でも、

SELECT * FROM users LIMIT 1

のように WHERE 句すら無い SQL を、プリペアドステートメント経由で実行すると、200 ns 以下で lookup できる、という報告もある。

数百 ns という数値は、DRAM に数回アクセスしただけで簡単に超えてしまう。つまり、このあたりでは CPU キャッシュラインが効いているはず。

ただ、自分は CPU キャッシュの速度感をあまり掴めていない。そこで、体感するための学習プロジェクトを作ってみた。

以前、自力で試したときは意図せず最適化されてしまい、あまり理解が進まなかったが、今回は AI の助けもあり、分かりやすい結果とその解説まで得られた。良い時代になったな、と思う。

このプロジェクト自体の結果も面白かったので、別記事にまとめようと思っている。