コード → https://github.com/wuxb45/lsm-trie-release

USENIX ATC15の論文。これはタイトルだけで読みたくなる論文ですね。LSMで、trieですよ。

LSMは普通はtreeですよね。Log Structured Merged Treeという古くからある有名なデータ構造。私も何度か実装しました。追加がシーケンシャルwriteになるので高速になり、けっこう便利なのですよね。一方でtrieというのはインデックスがエッジに含まれるtreeで、これも非常に古くからあるデータ構造。組み合わせたらどんな素敵なんだろう、という話。

この人が作ったのはsmall data用のKVS。実際、KVSの用途はsmall dataが圧倒的に多い。1エントリあたり数十バイトくらいのものが大量にあったりする。そういうのに普通にシステムを作ると、データが小さいとインデックスやパディングが相対的に大きくなってダメになる。工夫を凝らさないと良いものはできない。事実、ビッグデータというのは一つ一つのデータが大きいわけではなくて、小さいデータが大量にあるという状態を示す言葉なのだよね。そこに技術的な困難さがあるわけだ。

振り返ってみると現代のKVSには、write amplification、large index set、readが遅いという欠点がある。LSM trieはこれらの欠点を解決する。

この論文ではLevelDBが比較対象。LevelDBベースで改良したという話なのかもしれない、と思ったがgithubに上がっているソースを見ると全部自分で書いたっぽいですね。

LevelDB自体はwriteに最適化したKVSで、けっこう速いしGoogleが作っただけあっていろんなところで使われている著名なもの。LevelDB自体の解説もなかなか詳しい。

これもLevelDBもBloom Filterを多用している。Bloom Filterを深く使った人にしか分からないこともちゃんと書いてあるという印象。そうだったそうだった。私も使ってたからそうだよねと納得感がある。そっから先の肝心のところを詳しく読んでないけど、普通に考えればtrieを使ってインデックスサイズを減らして頑張ったんだろうな。LSMで書き込みが速くてパディングもなく、GCして。Bloom Filterは削除ができないからGCのときに作り直してんでしょどうせ。

で、実際にsmall dataを入れたり出したりして、readもwriteも性能が良い。

しかしこのタイトルはキャッチーでいいですね。