NuDB

NuDBという特殊なデータベースがある。削除や更新が一切出来ないが、メモリを使わないため、データベースが肥大した場合にも性能が一定という特性を持つ。 どういう場面にこのようなデータベースが必要なのか。

XRP Ledger（以下XRPL）では、マークルツリーを応用したSHAMapという構造を使って、毎世代の台帳が（論理的には）その世代の全状態を持っているという性質を実現している。 ここで、不変なコンテンツをそのハッシュ値で格納する（コンテンツアドレッシングのこと）データベースが必要になり、これをNodeStoreと呼んでいる。

This Module focuses on the backbone of XRPL’s state management: the SHAMap, which maintains cryptographically-verified ledger state in memory, and the NodeStore, which persists this state to disk. https://docs.xrpl-commons.org/core-dev-bootcamp/module03

このNodeStoreの実装として、当初はRocksDBなどの既存のDBを使っていたが、データが肥大してくると性能がでなくなる問題があった。そこで、「どうせコンテンツアドレッシングなら削除や更新なんか省いてもっと効率の良いものが作れるでしょ」という発想で作ったのがNuDBだ。

https://github.com/cppalliance/NuDB

仕組みは簡単である。KVのVの部分はログ書きする。そしてKからVの場所への索引をLinear Hashingによって実現する（チャッピーによると）。

だから、KからVを引くには、

1. KからVの番地を引く（索引アクセス）
2. その番地にあるデータを読む

ForeverDB

おれは無職で暇なので、XRPLの簡易版をRustで実装してやろうかと思ってちょっと動いてみたのだが、そのコアがSHAMapであることがわかり、とりあえずはSHAMapを作ることを目標にした。そしていざSHAMapの検討を始めると、NodeStore自体に興味を持ったので、まずはNuDB「的なもの」を作ってみることにした。Rustが強すぎるのでさくっと１日で出来た。その過程でbincodeが開発者がブチ切れて終了してたことを知った。

https://github.com/akiradeveloper/ForeverDB

一生データが消えないという意味でForeverDBと名付けた。Linear Hashingの部分は実装が重いのでありもので済ませようと思い、GDBMというのを使ってみることにした。これはLinear Hashingと似たようなExtendible Hashingというアルゴリズムを実装しており、比較的新しいバージョンでは障害耐性も上がったとかなんとか言ってるので、とりあえず使ってみるということになった。

実験内容

ベンチマークだが、N個のエントリを作ったあとクエリを繰り返し行うというもので計測した。Kは256bit、Vは1024バイト（ブランチの大きさ。256bitのハッシュ値を16個つなげると1024バイト）とした。CPUは7735HS、メモリは32GB

結果

N=10Mで猛烈に遅くなったので、クエリにおける2ステップのうち1ステップ目のメタデータアクセスしかしないモードを実装して追加測定を行った。

考察

1. 10Mで遅いのはログへのアクセスの方。ページキャッシュへのヒットミスが起こってディスクから読み出している。
2. メタデータも大きなデータセットでは劣化しているが、にしては速いのでなにかGDBMのアルゴリズムに関する話かな。

課題

• Linear Hashingの実装と比較