はじめに

これはデータベース・システム系 Advent Calendar 2023 の12/23の記事である
そして Nostr (2) Advent Calendar 2023 の12/2の記事である
LMDBというDBMSについて調べてみた内容をつらつらと書く

Discraimer

筆者はデータベースシステムの専門家ではないため、頓珍漢な記述をしている可能性あり。その点ご留意頂きたく。誤っている点があれば指摘頂ければ幸甚
一部、推測に基づいた内容あり。それらの箇所は推測に基づいている旨分かるように記述する
- （実装を確認するといったところまでは行えなかったため）

LMDBについて調べようと思ったきっかけ

nostrなる分散アプリケーションのための通信プロトコル・アーキテクチャがある
比較的自由度の高いものであるが、現状の主なアプリケーションが分散SNS（マイクロブログ）であるため、その分散SNSを指す意図でnostrというキーワードが使われている場合も多い
詳細は以下のリンク先を参照されたい
- 分散型SNS nostr 仕組み解説 - Speaker Deck
筆者はnostrのリレーサーバのいくつかの実装で採用されていたことからLMDBの存在を知った
- 具体例を挙げるとstrfryという実装で利用されている
  - 後述だが、LMDBはKVSで、そこで言う所のKでしかレンジスキャンができない
  - それでは不便なので strfry では、RasgueaDBというライブラリでLMDBをラップし、Vの中の特定のデータをインデックスとしたレンジスキャンなど、より高機能なI/Fを用意した上で利用していたりするそうで、興味深いところである
- LMDBはプリミティブな機能しか提供しないが、逆に言えば高機能にするための実装を含まないコンパクトなソフトウェアいうことでもある。また組み込みDBの形をとっている。そういったところから、他のDBMSのストレージエンジンとして用いられることもあるようである
  - 例えば、分散DBであるTiDB は過去にはLMDBをストレージエンジンに使えた時期があったように見える
  - 時系列DBであるInfluxDBでもストレージエンジン刷新の際の候補の中には入っていたようである
少しウェブを検索するとパフォーマンスが高いとの情報があったのと、メモリマップドであること（≒mmap使っていること)を前面に押し出していたことから興味を持った
- "パフォーマンスが高い" という表現は曖昧性にあふれているが、ご容赦願いたい
なぜ、メモリマップドであることが気になったかについては続くセクションにて分かるかと

補足:簡単なリレーサーバの説明

nostrというアーキテクチャにおける唯一のサーバで、クライアント間のデータの仲介役。やっていることだけ見ると、ストリームインタフェース（Websocket）を持った一風変わったデータベースシステムと言えないこともない
リレーサーバのワークロードの特徴（筆者の認識）
- 扱うデータの構造
  - リレーショナルな部分も多少ある
- readが大半
- writeは大半が新規エントリの追加で、既存エントリの更新は少ない
- アクセスパターンには時間的局所性がある
  - 現在時刻基準で数時間以内に記録されたエントリ、というような形のリクエストが多い

LMDB概要

名称: Lightning Memory-Mapped Database（LMDB）
- 最初はMemory-Mapped Database（MDB）という名称であったようだが、2012年に現在の名称に変わったそうである
KVS（Key-Value Store）
- キーでのイテレーションが可能
- トランザクションをサポート
元々OpenLDAPがバックエンドにBerklay DBを使用していたが、様々な課題があったため、それらを解消できるものとして開発が始められた
- 筆者は知らなかったが、データベースシステム界隈での知名度はそれなりに高いシステムであった模様
組み込みDB
Read Optimized
公式のHPによれば "fully transactional with full ACID semantics" とのこと

LMDBのパフォーマンスってイケてる？

ベンチマーク
- https://web.archive.org/web/20210420131134/http://www.lmdb.tech/bench/inmem/
- https://www.influxdata.com/blog/benchmarking-leveldb-vs-rocksdb-vs-hyperleveldb-vs-lmdb-performance-for-influxdb/
参考になりそうな記事
- Embeddableなkey value storeについてのメモ - hnakamura's blog
評価方法によって見え方が大分変わるようではあるが、ハイパフォーマンスな方であるのは確かのようである
どのような設計になっているのだろうか？

LMDBの設計について

結局のところなぜ高速なのか？

他のシステムに対するアドバンテージとしては以下あたりぐらいしかないはず
- （だが、それだけでそんなに速くなるものなのか。有識者の意見求む）
- ゼロコピー
- Read Optimized
  - readはwriteにもブロックされず、複数トランザクションが走れる
  - （一方で、writeは複数トランザクションの同時実行ができないので、性能は並かそれ以下かもしれない）
- データへのアクセスで生ポインタが使える
  - バッファプールを用いている多くのDBMSでは論理アドレス（ページID等）でバッファプールからページをFetchすること（さほど大きくはないだろうがオーバヘッドは生じるはず）を繰り返す必要があるはずだが、LMDBはメモリマップドなので、Pointer Swizzling的なことをしているか、そもそも毎回同じアドレスにマップしているか、いずれかは不明だが、生ポインタを使って他のページやその中のデータにアクセスできている（はず）

適するユースケースと適さないユースケース

(他のKVSなDBMSを意識した記述となっている点は注意されたい)
適するケース
- readバウンドなワークロードなケース
適さないケース
- 一回のwriteトランザクションで扱うデータサイズが小さすぎるケース
- 仮に4byteのkeyと4byteのvalueの合わせて8byteのkey-valueペアを新規追加もしくは更新する場合を考える
- LMDBはページ単位で処理を行い、そのページは一度作成した後はイミュータブルにするので各々の操作では以下のような非効率な処理を行うことになってしまう
  - リーフページだけでなく、B+-treeのrootまでの間に位置するページ（rootページ含）をメモリコピーし、更新をかけた上でディスクに書き込む
  - たった4byteもしくは8byteのためだけの操作が、4kB x 処理するページ数のメモリコピーとディスクI/Oを生じさせてしまう
    - (上では(LMDBの)ページサイズを4kBとしているが、settingによってはもっと大きなサイズである可能性もある)
- このあたりは以下のリンク先記事の筆者間（2つ目はLMDBの開発者が書いたもの）のレスバにて Write Amplification といった言葉で言及されている
  - https://web.archive.org/web/20210526123038/http://banksco.de/p/lmdb-the-leveldb-killer.html
  - https://web.archive.org/web/20201111195059/https://symas.com/is-lmdb-a-leveldb-killer/

では、Nostrのリレーサーバなるものには適しているのか?

扱うデータにリレーショナルな部分も多少ある
- => KVSを工夫して使えばどうにかなる範囲ではありそう
  - 可もなく不可もなく
readが大半を占める
- => Read Optimized である
  - ◎
writeは大半が新規エントリの追加で、既存のエントリの更新は少ない
- 特にLMDBだからどうこうということはない
  - 可も不可もなく
アクセスパターンには時間的局所性がある（現在時刻基準で数時間以内に記録されたエントリ、というような形のリクエストが多い）
- => DBMS一般として扱いやすい特性であり、LMDBが特別そのような特性のワークロードでハイパフォーマンスかといえばそうではない認識。どころか、KVSで言うところのKの順序でのイテレーション（インデックススキャン）はできても、それ以外のデータ（※）によるイテレーションには対応していないので、RDBなどと比べると劣ると見ることもできる
  - △
  - ※: ここでは時刻情報をインデックスのキーに用いることなどを想定
見解: LMDBの元々の高速さも踏まえて考えると、一般的な？RDB（※）やNoSQL（KVS含）なシステムを使うよりは良い選択なのではないかと考える
- ※: RDBを使うのはやりたいことに対してオーバースペック過ぎるように思う
- 注: 以下を前提した場合での話である
  - 一次記憶より大きなサイズのデータを扱う必要がある。もしくは、そのようなシチュエーションになりうる
    - この前提がないのであれば、Redisなどを使った方が良さそうな気がする
  - ステートレスなサーバを水平スケールさせて、データは共通のDBサーバから得るといったことをしない
  - Andrew Crotty他のMMAP利用に関する論文の検証で用いられたようなコア数が大きい計算機を利用しない
    - 論文では64コアの計算機を検証に利用している
    - 筆者が調べたところでは（I/Oに限らず）TLB shootdownのパフォーマンスへの悪影響はコア数が多いほど大きなものとなるようである
    - 従って、化け物のようなコア数の計算機を使っていないのであれば、（論文の主張するところが無視できるようになるわるわけではないと思うが、）評価結果として示されたほどのI/Oパフォーマンスの差は生じない可能性がある
    - つまり、MMAPを利用して（しまって）いるLMDBの、バッファプールを用いたDBMSに対するディスアドバンテージがさほど顕在化しない可能性がある
    - なお、MMAPを利用した場合のTLB shootdownによるread I/O性能の低下以外のディスアドバンテージについては、LMDBではある程度回避できていてる可能性がある
      - MMAPを利用する場合に一番NGなマップ領域を介したwriteを行っていない
        
        DMBSにおけるストレージへのwriteは、データの確実な永続化のため、二次記憶まで物理的に？書き出された状態とする必要がある。つまり、OSのオンメモリのディスクキャッシュに書き出したら終了！とはならない
        
        にもかかわらず、メモリ上のマップ領域を介したストレージへのwriteはOSのディスクキャッシュへのメモリコピーを行ってしまい、不要なオーバヘッドを負うことになる
      - mmapした領域のメモリ管理
        
        新たなページをDBファイルからメモリに載せる際に、そのデータのためのメモリ領域を確保するためにページがevictされる場合、どのページがevictされるかはDBMSにおける（一種のキャッシュ機構の中で）重要な点である
        
        この点において、LMDBはmadvice関数を巧みに使うことで、evictされるページが適切なものになるようある程度コントロールしている可能性がある
        
        もはやバッファプールを実装した方が良いのではないか感もあるが
        
        確証があるわけではないが、実装の中にmadvice関数の呼び出しが存在することだけは確認できている

おまけ

nostrの元々冗長性を持つアーキテクチャや、ユーザがアプリケーションに求める信頼性が比較的緩い（あくまで筆者の認識）ことから、データのロストをある程度許容するようなDBMSでも良いような気はする
- ある時間帯のデータをロストしたとしても、他のリレーサーバから再度取得することは可能である
例えば、主記憶より大きなデータが扱えるRedisのようなもので、永続化はRedis同様に定期的なダンプで済ませるようなものがあれば、良さそうではないだろうか

おわりに

よいお年を！