lkv - Point Lookup特化の超高速組み込みKVS
lkv、という新しい組み込みDBを作りました。Rust製です。
nuskey8 / lkvA lightweight and fast embedded key-value store for Rust.Rust製の組み込みDB、というと他にもsledやredbなどの選択肢が思い浮かびますが、lkvの最大の特徴はPoint Lookupの速度です。
他のDBと比較しても桁違いの速度を誇り、std::HashMapとほぼ同等のパフォーマンスを発揮しています。一応これはlkvにとって有利な条件でのベンチマークではありますが、とはいえこれだけのパフォーマンスを汎用DBで叩き出すことは難しいでしょう。
当然これだけの性能を出すためのトレードオフはあり、対応するキーで辞書引き・順不同で全ペアをスキャン、以上の機能が存在しないほか、設計上頻繁な書き込みには全く向いていません。あくまでちょっとした設定の永続化や、マスタデータのような変更がほとんどないデータを置くことを想定しています。まあ汎用的なDBを目指すなら最初からRocksDBやLMDBでいいので、こういう尖ったDBが1つくらいあってもいいでしょう。
使い方
内部の設計について語る前に、まず簡単な使い方を見ていきましょう。
use lkv::{Database, Result};
fn main() -> Result<()> {
// DBを作成 (作成済みのDBにはDatabase::open()を利用)
let mut db = Database::create("./example.lkv")?;
// 書き込み
let mut write = db.begin_write()?;
write.put("name", "lkv")?;
write.commit()?;
// 読み取り
let read = db.begin_read()?;
assert_eq!(read.get("name")?, Some(b"lkv".as_slice()));
// iterは順序未定義
for item in read.iter()? {
let (key, value) = item?;
println!("{} = {}",
String::from_utf8_lossy(key),
String::from_utf8_lossy(value));
}
drop(read);
Ok(())
}
DBは単一のバイナリファイルとして作成され、Key/Valueともに&[u8]のシンプルなAPIです。具体的な型を放り込みたい場合は適当なシリアライザを使ってもらえれば良いでしょう。
書き込みに関しては普通ですが、読み取りはget()/iter()ともにゼロコピーになっています。また、読み取りに関しては複数スレッド・プロセスからアクセスしても安全ですが、書き込みは同時に1つのwriterのみとなっています。
また、詳細は後述しますが、基本的にはかなり省メモリで動作しますが、書き込みを続けていくとメモリ使用量が悪化します。これを防ぐには定期的なcompact()が必要になります。RocksDBのような自動compactionはありません。
db.compact();
内部設計
それでは設計の話に入りましょう。
多くのDBはB+treeやLSM-treeといったデータ構造を採用しています。これらは読み書きも十分効率的で、かつ柔軟な検索が可能である点で優れており、ちゃんとした(？)DBを作るなら基本はこの手のデータ構造を利用することになります。
一方、lkvはこのどちらにも属していません。lkvは概ね以下のような構成になっています。
+-----------------------------------------+
| Superblock 0 |
+-----------------------------------------+
| Superblock 1 |
+-----------------------------------------+
| Base (generation N) |
| - Header |
| - Slot table |
| - Packed records |
| - Checksum blocks |
+-----------------------------------------+
| Overlay |
| - Batch record #1 |
| - Batch record #2 |
| - ... |
+-----------------------------------------+
Superblockはメタ情報を保持する専用のページで、世代ごとに2つのブロックが交互に利用されます。これはファイル破損に対する耐性を高めるためで、RocksDBなども同様の設計になっています。
DBの本体となるのはBase/Overlayの2層構造です。
Baseはファイル上に構築されたimmutableなハッシュテーブルです。これは実行時に書き変わることはなく、mmapで参照されます。
OverlayはBaseの構築後に行われた書き込みを記録する追記ログです。こう聞くとWALに近い印象を受けますが、WALがあくまで障害回復のための用途であるのに対し、こちらはBaseより優先度の高い実データを保持する役割を持っています。また、キーと値への参照は常にオンメモリにキャッシュされ、compact()を明示的に呼ばない限り肥大化していきます。
この2層構造により、get()が呼ばれたときの処理は
- メモリ上のキャッシュをチェックし、ヒットしたら参照からOverlayの値を取得
- 存在しなければBaseのハッシュテーブルを引く
の2つのみで完了します。計算量のオーダーはO(1)で済むため、巨大なB-treeを二分探索するよりも遥かに高速です。また、書き込み時はOverlayに追記するだけなので、それ自体は軽量になっています。
一方、この設計には問題もあります。
まずハッシュテーブルである都合上、B-Treeのような範囲検索は不可能です。ここはトレードオフとして完全に切り捨てています。仕方ない。
また、Overlayが全てメモリに乗る都合上、書き込みが増えるほどメモリ使用量が悪化します。これを避けるにはcompact()を明示的に呼ぶ必要がありますが、compact()はかなり重い処理である上、追加でBaseを再構築してから縮小を行うため、一時的にファイルサイズが増加します。頻繁な書き込みに適さないのはこのためです。
というわけでDBとしての汎用性は低いものの、Point Lookupが中心であれば圧倒的な性能を発揮してくれます。また、そこまで件数が多くなければOverlayが多少増えても問題はないため、小さめのデータを保持する用途にも悪くはないでしょう。
なお、これらの設計はPalDBとBitcaskという2つのDBから影響を受けたものです。PalDBはwrite-onceな読み取り専用DBで、不変のハッシュテーブルを構築することで読み取り性能に特化させています。一方のBitcaskはちょうどOverlayで説明したようなログ構造をベースとした設計になっています。lkvはちょうどこの2つを足し合わせたような設計になっているわけですね。
C API
READMEに書き忘れてたのでそのうち書くんですが、一応C APIも用意されています。
#include <stdio.h>
#include "lkv.h"
int main(void) {
// DBを作成
lkv_database *db;
lkv_database_create("./example.lkv", NULL, &db);
// 書き込み
lkv_database_put(db, (const uint8_t *)"name", 4, (const uint8_t *)"lkv", 3);
// 読み取り
const uint8_t *value;
size_t value_len;
lkv_database_get_ref(db, (const uint8_t *)"name", 4, &value, &value_len);
printf("%.*s\n", (int)value_len, (const char *)value);
lkv_database_close(db);
return 0;
}
feature flagをつけるだけで簡単にビルドできるようにしてあるので、Rust以外からも使おうと思えば使えるようになってます。使い道があるかはわかりませんが...
まとめ
というわけでlkvの紹介でした。元はといえば@hadashiAさんのDryDB(旧VKV)を眺めていて、読み取り専用で、かつ範囲検索などの機能を捨てていいならハッシュテーブルの方が高速になるんじゃないか？というアイデアが発端だったりします。なんやかんやで書き込み機能までつけてしまいましたが、ちゃんと実証できたので良かったですね。とはいえちゃんと計測したわけではないので、今度C#バインディングを作って比較してみたいところです。
一応プレビュー版としてリリースしましたが、既に使えるものにはなっているはずなので、是非是非使ってみてください！