はじめに

これはデータベース・システム系 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の設計について

このセクションの内容は、主たる開発者である Howard Chu氏の以下の論文から筆者が読解したLMDBの設計のポイントおよび興味深いと感じた点である
- Howard Chu “MDB: A Memory-Mapped Database and Backend for OpenLDAP”
mmapを利用している
- （組み込みDBでは特別珍しいことでもないが）
- 論文ではmmapを利用することで、バッファプールを用いるよりI/Oの効率が上がると主張しているが、それが誤りであることを示す論文が2022にでている
  - Andrew Crotty, Viktor Leis, Andrew Pavlo, “Are You Sure You Want to Use MMAP in Your Database Management System?”
- 近年では当たり前となったマルチコア（マルチプロセッサでも同様だったはずではあるが）な計算機ではmmapを用いるとTLB shootdownが頻発するが、それが輪をかけて状況を悪化させているようである
  - LMDBの論文に関しては、それが書かれた時期も踏まえて解釈する必要があるかもしれない
- 結局のところ、2023年現在において、mmapを用いることのメリットは、今年のアドベントカレンダーの中の記事でも紹介されている Pointer Swizzlingと同様のことがより簡易かつ低オーバヘッドで可能になるところぐらいなのではないかと考えている
  - その手のことを行っているというのは推測である（実装の確認はできていない）
  - 推測通り行っていたとしても、Andrew Crotty他が示したmmap利用のディスアドバンテージを挽回できるだけの効用があるかと言えば、厳しいところではないかと考えている
Read Optimized
- CCプロトコルはMVCC（MultiVersion Concurrency Control）
- 並行トランザクション実行をしても、あるトランザクションが別のトランザクションの実行をブロックしたりAbortさせることがない
- readも、writeも
- ただし、writeトランザクションは同時に1つだけしか実行しないという制約を設けている
  - データ整合性維持のためのよう
    - mmap利用に関する説明の中でもリファーした下の論文の “3.1 Problem #1: Transactional Safety” の最後のところで言及されている
      - Andrew Crotty, Viktor Leis, Andrew Pavlo, “Are You Sure You Want to Use MMAP in Your Database Management System?”
Copy on Write（一度書いたページは変更不可）というセマンティクス
- 更新操作の際は該当するページを書き換えるのではなく、その内容をコピーしたページを新たに作成し、それに更新を加える形をとる。そのような方法でなぜうまくいくかは後述
Append Only B+tree
- Copy on Write というセマンティクスを採用している場合、どのような形でノード間のリンクを表現しているにせよ、既にあるノードを直接書き換えることができない以上、writeトランザクションが木に変化を加えるためには通常と異なる方法を取る必要がある。そこで Append Only B+treeというデータ構造というか、アルゴリズムというかを用いる
- これについて解説しているのが下のリンク先である
  - how the append-only btree works
- リンク先の内容を補足も挟みつつ説明すると...
  - 木の末端のページをリーフと呼ぶとして、keyとvalueのペアはリーフに格納する
  - 探索は木の頂点（root）からリーフに向かって行う
  - リーフの内容を更新（新たなリーフを追加する場合も同様のはず）する場合、対象のリーフからrootのノードに至るまでのページを全てCopy on Writeの考え方で置き換える
    - リーフ以外は、リンク情報を適切に書き換えたものに置き換える
  - トランザクションがデータにアクセスする際にスタートするrootページの情報はメタページと呼ばれるページに記録されていて、それもCopy on Writeで新たに作成し、図示されている木の中のページとは別途DBファイルの末尾に書き込まれる。mmapによってメモリ上のrootページの情報はよしなに置き換わるように作りこまれている（はず）
  - これらを行うことで、実質的にリーフの内容が更新された木になる。が、しばらくの間は更新が行われていない方の木も存在する状態になる
    - （置き換えられたページは、不要になったと分かったタイミングで再利用可能なページのリストに追加され、論理的に削除された状態になる）
  - このことは複数のトランザクションを並行・並列に実行する上では重要な点で、どういうことかというと、木の更新を始めた時点で別のreadトランザクションが木を辿っているという場合もあり得るが、そのreadトランザクションは更新が行われていない木の上でそのまま処理を継続できるのである
    - この場合、readトランザクションは更新前のリーフの値を読む可能性もあるわけだが、それでも問題ないことは後述する
  - つまり、Append Only B+tree というものの採用により、LMDBは特に排他制御を行わずとも、readトランザクションとwriteトランザクションをデータの整合性を壊すことなく実行できている
上の2つによるデータ整合性の維持とクラッシュ耐性担保の手法
- データ整合性の維持
  - 結局のところ、おおざっぱに言えば、Append Only B+treeのところで説明した方法でConcurrency Controlをしているということになる
  - writeトランザクションが動作した際に古い木と新しい木が併存し、古い方の値を読むreadトランザクションも存在し得ることを述べたが、これはつまり、keyとvalueのペアをエントリと呼ぶとした時に、エントリ（実質的にはページ）に複数のバージョンが存在する状態が生まれ、個々のトランザクションごとに見える（参照する）バージョンが異なる場合があることを意味する
  - そう、このような形でトランザクション間のConcurrency Controlを行う方法が皆さんご存じMutiVersion Concurrency Control(MVCC) である
  - 説明したような振る舞いを下敷きにすることで、比較的容易にデータの整合性の維持が可能であろうことは、この記事を読んでいるような者にとって自明かと思われるので本記事では省略する！
    - writeトランザクションが1つしか存在しないという制約も念頭に置きつつ
- クラッシュ耐性の担保
  - 多くのデータベースシステムではWrite Ahead Logging（WAL）と呼ばれる手法に基づき、writeトランザクションの開始、終了、行った操作等についてログをファイルに書き出しておくことでクラッシュしてもリカバリできるようにしているが、LMDBではこの手法を採用していない
  - LMDBの論文でも明に説明されていなかったと思われるが、筆者の理解（推測含）はこうである
    - ①ログを書かない代わりにページを新たに作成（再利用した場合も含）した際は、その内容はメタページとともに都度ファイルに書き出される
    - ②writerトランザクションは同時に1つしか実行されないので、上ポチの書き出しが終わった時点で、脇で書き出しが必要もしくは、書き出しの最中であるというトランザクションというのは存在し得ない
    - ③mmapしたメモリ領域に存在するデータはread onlyでマップされているため、当該領域にdirtyなページというものは存在し得ず、OSがマップ領域のデータをファイルに書き出すということも無い
    - これら3点から、基本的にDBファイルの内容は常にオンメモリの内容と同期されており、また、いずれのデータの整合性も正しい状態であるためクラッシュが起きてもDBファイルを読み込み直すだけでリカバリが可能
    - writeトランザクションがデータを書き出している最中にクラッシュが起きた場合
      - この場合、DBファイルの内容は整合性の崩れた状態になっている可能性がある
      - しかし、①に記述の通りメタページも同時に書き出すので、その書き出しまでが終了しているかを確認することで、未コミットのデータか否かの区別がつくようになっているのだと思われる
        
        WALと同様に、全ての書き出しが完了するまでトランザクションの完了をアプリケーションに通知しないようにすればよい
        
        論文か公式のWebページにDBファイルがログでもある、といったような記述があったが、このあたりのことを意味しているのだろう
      - 区別さえつけば、Redo/Undoで言うところのUndoと同様にして、ロールバックを行える。未コミットのwriteのデータは破棄してしまい、該当データはwrite前のバージョンに置き換えればよいはずである。設計上、前のバージョンのデータを内包しているページも再利用されることなく残っているはず
ディスクへのI/Oはmmapされた領域を介さずファイルに直接書く
- 原則、mmapする際はマップするメモリ領域をread onlyとする設計
  - LMDBを利用するアプリケーションにメモリ領域をそのまま渡すので、書き込みを可にすると、アプリケーションコードが誤って書き込みを行った場合にDBのデータが壊されてしまうため
- writeトランザクションがwrite操作を行う場合は、再利用可能なページ（もう参照されないことが分かっているページ）があれば、それを利用する形でファイル側の該当領域に直接writeする（と思われる）。再利用可能なページがなければ、DBファイルの末尾に追記する
  - Copy on Writeのセマンティクスであるためwrite操作が行われると、DBファイル上に参照されることがなくなったページ（領域）が生まれる。これを再利用していかないと、DBファイルはあっというまに大きくなっていってしまう、らしい
ゼロコピーでアプリケーションにデータを渡す
- mmapでマップされたメモリ領域のポインタをアプリケーションにそのまま渡す
- すなわち、readトランザクションではLMDBのレイヤでメモリコピーを行わないということで、メモリコピーの回数はゼロ
- アプリケーションに渡したポインタをいつまでもアクセス可にしておくと、古くなったページの再利用ができなくなってしまうので、アプリケーション側にはトランザクションの開始と終了をLMDBが把握するための明示的な関数呼び出しを要求する。トランザクションが終了した後は渡されたメモリ領域にアクセスできることは保証されなくなる
- このI/Fには注意すべき点があって、トランザクションを終了させないでいる間は、トランザクションの中でアクセスしたデータが入っていたページの再利用ができない状態が続くので、長いこと開いたままにするな、とドキュメントに記述がある
  - 他のトランザクションの実行を妨げることはないのでまだマシだとは思うが
- つまり、アプリケーションは、取得したデータはさっさと何かに利用して不要な状態にするか、メモリコピーをして別の場所に退避するといったことが求められる
  - 参照をどこかに置いておくというのはNGであるし、前者が難しいアプリケーションは少なくないだろう。一方で後者はせっかくゼロコピーで取得したのにメモリコピーしてしまうのは避けたい、というジレンマを抱えることになるので、ユーザにとっては悩ましいポイントとなるかもしれない
Copy on WriteのセマンティクスによるシーケンシャルディスクI/O
- writeを行う場合、再利用可能なページが無ければファイルの末尾にデータを追記することは上述の通りであるが、これによりwriteトランザクションはcommit時にそれらのデータをファイル末尾にできる限りまとめて書き込むことができる。これによりI/Oを効率の良いシーケンシャルアクセスの形で行える
- 余談だが、LSM-tree系のDBMSでも同じような話があった気がする

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

他のシステムに対するアドバンテージとしては以下あたりぐらいしかないはず
- （だが、それだけでそんなに速くなるものなのか。有識者の意見求む）
- ゼロコピー
- 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同様に定期的なダンプで済ませるようなものがあれば、良さそうではないだろうか

おわりに

よいお年を！