Lightning メモリマップデータベース

Lightning Memory-Mapped Database ( LMDB ) は、キー値ストア形式の組み込みトランザクションデータベースです。LMDB はCで記述されており、いくつかのプログラミング言語の API バインディングを備えています。LMDB は任意のキー/データ ペアをバイト配列として保存し、範囲ベースの検索機能を持ち、1 つのキーに対して複数のデータ項目をサポートし、一貫性をチェックせずにレコードを追加するための特別なモード (MDB_APPEND) を備えています。^{[1] LMDB は}リレーショナル データベースではなく、 Berkeley DBや DBMのようなキー値ストアです。

LMDB は、マルチスレッドまたはマルチプロセス環境で同時に使用することもできます。読み取りパフォーマンスは設計上、直線的に拡張されます。LMDB データベースには一度に 1 つの書き込みしか存在できませんが、多くの同様のキー値データベースとは異なり、書き込みトランザクションは読み取りをブロックせず、読み取りは書き込みをブロックしません。LMDB は、パフォーマンスを拡張する手段として、同じシステム上の複数のアプリケーションが同時に同じ LMDB ストアを開いて使用できるという点でも異なります。また、LMDB は設計上、本質的にデータの整合性を維持するため、トランザクション ログを必要としません (そのため、データを 2 回書き込む必要がないため、書き込みパフォーマンスが向上します)。

LMDBの設計は、 OpenLDAP開発者メーリングリストへの2009年の投稿^{[2]で初めて議論されました。これは、プロジェクトが}Berkeley DBに依存していることによって引き起こされたキャッシュ管理の難しさに対する解決策を模索する文脈の中で行われました。具体的な目標は、Berkeley DBの設計に固有の複数のレイヤーの構成とキャッシュを、ホストオペレーティングシステムの制御下で自動的に管理される単一のキャッシュに置き換えることでした。

その後、開発はOpenBSD ldapdプロジェクトの同様の実装のフォークとして始まりました。 ^[3]最初の公開バージョンは2011年6月にOpenLDAPソースリポジトリに登場しました。^[4]

このプロジェクトは2012年11月までMDBとして知られていましたが、その後、既存のソフトウェアとの競合を避けるために名前が変更されました。^[5]

LMDB は内部的にB+ ツリーデータ構造を使用しています。その設計の効率性と小さなフットプリントは、良好な書き込みパフォーマンスも提供するという意図しない副作用をもたらしました。LMDB には、Berkeley DBやdbmに似たAPIがあります。LMDB は、コンピュータのメモリを単一のアドレス空間として扱い、コピーオンライトセマンティクスを備えた共有メモリを使用して複数のプロセスまたはスレッド間で共有します(歴史的にはシングルレベルストアとして知られています)。以前のほとんどの最新のコンピューティングアーキテクチャは 32 ビットのメモリアドレス空間を持っていたため、シングルレベルストアに直接マップされたデータベースのサイズには 4 GB というハード制限がありました。しかし、今日の 64 ビットプロセッサは現在、ほとんどが 48 ビットアドレス空間を実装しており、47 ビットアドレスまたは 128 TB のデータベースサイズにアクセスできるため、^[6]共有メモリを使用するデータベースが実際のアプリケーションで再び有用になっています。

LMDB の注目すべき技術的特徴は次のとおりです。

• B+ツリーの使用。LMDBインスタンスが共有メモリにあり、B+ツリーのブロックサイズがOSのページサイズに設定されているため、LMDBストアへのアクセスはメモリ効率が非常に高くなります^[7]
• 新しいデータは、既存のデータを上書きまたは移動することなく書き込まれます。これにより、トランザクション ログやクリーンアップ サービスを必要とせずに、データの整合性と信頼性が保証されます。
• 独自の追加書き込みモード（MDB_APPEND）^{[1]の提供は、新しいレコードを}B+ツリーの末尾に直接追加できるようにすることで実装されています。これにより、ページの読み取りと書き込みの操作の回数が減り、パフォーマンスが大幅に向上しますが、プログラマーはDBに格納するときにキーがすでにソートされていることを確認する必要があります。
• コピーオンライトセマンティクスは、データの整合性を保証するだけでなく、トランザクションの保証と、ロックを必要とせずに読み取り側 (現在の書き込み側も) による同時アクセスを提供します。データ変更中に内部的に必要な新しいメモリ ページは、基盤となる OS によってコピーオンライト セマンティクスを通じて割り当てられます。LMDB ライブラリ自体は、読み取り側がアクセスする古いデータを実際に変更することはありません。これは、単に変更できないためです。共有メモリの更新では、書き込み先のメモリ ページの完全に独立したコピーが自動的に作成されます。
• LMDB はメモリマップされているため、 API を通じてキーと値のメモリ アドレスへの直接ポインタを返すことができ、不要なコストのかかるメモリのコピーを回避できます。これにより、パフォーマンスが大幅に向上し (特に格納されている値が非常に大きい場合)、LMDB の潜在的な使用ケースが拡大します。
• LMDB は未使用のメモリ ページも追跡し、B+ ツリーを使用してトランザクション中に解放された (不要になった) ページを追跡します。未使用のページを追跡することで、ガベージ コレクション (および CPU サイクルを消費するガベージ コレクション フェーズ) の必要性が完全に回避されます。新しいページを必要とするトランザクションには、まずこの未使用の空きページ ツリーからページが与えられます。これらのページが使い果たされた後にのみ、基礎となるメモリ マップ ファイルの以前は未使用だった領域に拡張されます。スパース ファイルをサポートする最新のファイル システムでは、これにより実際のディスク使用量を最小限に抑えることができます。

LMDBのファイル形式は、Berkeley DBとは異なり、アーキテクチャに依存します。つまり、データベースを32ビットマシンから64ビットマシンに移動する前に、またはエンディアンの異なるコンピュータ間でデータベースを移動する前に、変換を行う必要があります。^{[8] [9]}

LMDB は、マルチバージョン同時実行制御(MVCC) を採用しており、複数のプロセス内の複数のスレッドがデータベースへの同時アクセスを調整できます。リーダーは設計上、線形に拡張されます。^{[10] [11]書き込みトランザクションは}mutexを介してグローバルにシリアル化されますが、読み取り専用トランザクションは、書き込みトランザクションがある場合も含め、並列で動作します。スレッド上の最初の読み取り専用トランザクションを除いて、待機は完全にありません。データベースから読み取る各スレッドは、共有メモリ配列内の要素の所有権を取得し、トランザクション内にあることを示すためにそれを更新する場合があります。ライターは配列をスキャンして、アクティブなリーダーとの直接の同期を必要とせずに、トランザクションが保持する必要がある最も古いデータベース バージョンを決定します。

2011年、Googleは、ユーザーがLevelDBのパフォーマンスをさまざまなシナリオでSQLiteやKyoto Cabinetと比較するマイクロベンチマークを生成できるソフトウェアを公開しました。 ^[12] 2012年、SymasはLMDBとBerkeley DBのサポートを追加し、更新されたベンチマークソフトウェアを一般に公開しました。^[13]結果として得られたベンチマークでは、LMDBが読み取りおよびバッチ書き込み操作で他のすべてのデータベースよりも優れていることが示されました。LMDBを使用したSQLiteは書き込み操作に優れており、特に同期/トランザクション書き込みで優れていました。

ベンチマークでは、基盤となるファイルシステムがパフォーマンスに大きな影響を与えていることが示されました。外部ジャーナルを備えたJFSは、特にBtrfsやZFSなどの他の最新システムと比較して優れたパフォーマンスを発揮します。^{[14] [15]} Zimbra は OpenLDAP で back-mdb と back-hdb のパフォーマンスを比較テストしましたが、LMDB は明らかに BDB ベースの back-hdb よりも優れたパフォーマンスを発揮しました。^[16]他の多くの OpenLDAP ユーザーも同様の利点を確認しています。^[17]

2012年に行われた最初のベンチマーク作業以来、複数のCPUとレコードサイズにわたるパフォーマンスを特徴付ける、メモリ内^[18]とディスク上^[19]の両方のワークロードに対して追加のデータベースエンジンを使用した複数のフォローアップテストが実施されてきました。これらのテストでは、LMDBのパフォーマンスがすべてのメモリ内ワークロードで比類のないものであり、大きなレコードサイズを使用するすべてのディスクバウンド読み取りワークロードとディスクバウンド書き込みワークロードで優れていることが示されています。ベンチマークドライバーコードはその後GitHub ^[20]で公開され、データベースの範囲がさらに拡大されました。

LMDB は、システムやアプリケーションのクラッシュによるデータ損失を防ぐように設計されています。そのコピーオンライト方式では、現在使用中のデータが上書きされることはありません。上書きを回避するということは、ディスク/ストレージ上の構造が常に有効であることを意味します。そのため、アプリケーションやシステムのクラッシュによってデータベースが破損した状態になることはありません。デフォルト モードでは、最悪の場合、クラッシュによって最後のコミットされていない書き込みトランザクションのデータが失われる可能性があります。すべての非同期モードが有効になっている場合でも、データ破損につながる可能性があるのは、アプリケーション クラッシュではなく、 OS の壊滅的な障害またはハードウェアの電源喪失^{[21]イベントのみです。}

USENIX OSDIシンポジウム^[22]の2つの学術論文では、突然の電源喪失やシステムクラッシュ時のDBエンジン（LMDBを含む）の障害モードについて取り上げています。^{[23] [24]} Pillaiらの論文では、検討した実際のファイルシステムで発生するような障害はLMDBには見つかりませんでした。LMDBの研究で特定された単一の障害は、仮想的なファイルシステムにのみ関係しています。^[25] Mai Zhengらの論文では、LMDBの障害を指摘していると主張していますが、結論はfsyncとfdatasyncのどちらが使用されているかによって異なります。fsyncを使用すると、問題が改善されます。fdatasyncではなくfsyncを選択することは、コンパイル時のスイッチであり、LMDBの現在のLinuxビルドではデフォルトの動作ではありませんが、macOS、*BSD、Android、およびWindowsではデフォルトです。したがって、LMDBのデフォルトのLinuxビルドは、zhengmaiの研究者によって発見された問題に対して脆弱な唯一のものですが、LinuxユーザーはLMDBを再構築して代わりにfsyncを使用することもできます。^[26]

ファジングによって生成されたような破損したデータベースが提供されると、LMDBはクラッシュする可能性があります。LMDBの作者は、このケースが問題になる可能性は低いと考えていますが、別のブランチで部分的な修正を作成しました。^[27]

2013年6月、OracleはBerkeley DB（関連プロジェクト）のライセンスをSleepycatライセンスからAffero General Public Licenseに変更し、^[28]さまざまなアプリケーションでの使用を制限しました。これにより、Debianプロジェクトは6.0以降、このライブラリを除外しました。このライセンスは商用再配布者に優しくないという批判もありました。同じライセンス変更がLMDBにも行われるかどうかについて議論が巻き起こりました。著者のHoward Chuは、LMDBはOpenLDAPプロジェクトの一部であり、彼が参加する前はBSDスタイルのライセンスを使用しており、今後もそのライセンスを維持することを明確にしました。チェックインによって著作権が誰かに譲渡されることはないため、Oracleのような同様の動きは不可能です。^{[29] [30] [31] [32] [33] [34] [35] [36] [37]}

Berkeley DBのライセンス問題により、 Debianなどの主要なLinuxディストリビューションはBerkeley DBの使用を完全に廃止し、LMDBを優先するようになりました。^[38]

C++、^{[39] [40]} Java、^[41] Python、^{[42] [43]} Lua、^[44] Rust、^{[45] [46]} Go、^[47] Ruby、^[48] Objective C、^[49] Javascript、^[50] C#、^[51] Perl、^[52] PHP、^[53] Tcl ^[54] Common Lisp ^[55]など、いくつかのプログラミング言語用のラッパーがあります。ラッパーの完全なリストは、メインのWebサイトにあります。^[56]

Howard Chu はSQLite 3.7.7.1 を移植し、元のB ツリーコードの代わりに LMDB を使用し、その結果を SQLightning と名付けました。^[57]ある引用されたテストでは、1000 レコードの挿入が 20 倍高速でした (元の SQLite の B ツリー実装より)。^{[58] LMDB は、Cyrus SASL、 [59]} Heimdal Kerberos、^[60] OpenDKIMなどの他のオープン ソース プロジェクトのバッキング ストアとして使用できます。 ^{[61]また、MemcacheDB [62]}や Mapkeeperなどの他の NoSQL プロジェクトでも使用できます。 ^[63] LMDB は、メモリ内ストアRedis がディスクにデータを永続化するために使用されました。Redis の既存のバックエンドはまれに異常な動作を示したため、代替が求められました。ただし、LMDB のバロック API は批判され、単純なことを行うために多くのコーディングを強いられました。ただし、テスト中のパフォーマンスと信頼性は、試された代替バックエンド ストアよりもかなり優れていました。^[64]

独立したサードパーティのソフトウェア開発者が、高性能環境でLMDBへのPythonバインディング^[65]を活用し、システムが1秒あたり20万回の同時読み取り、書き込み、削除操作（合計1秒あたり60万回のデータベース操作）を維持することに成功した方法をテクノロジーニュースサイトSlashdotに公開しました。 ^{[66] [67]}

LMDBを使用しているアプリケーションの最新リストはメインのウェブサイトで管理されています。^[68]

多くの人気のあるフリー ソフトウェアプロジェクトでは、多くの場合、主要なまたは唯一のストレージ メカニズムとして LMDB のサポートを配布または組み込んでいます。

• Debian ^[69]、Ubuntu ^[70]、Fedora ^[71]、OpenSuSE ^[72]の各オペレーティングシステム。
• LMDBはもともとback-mdb経由で開発されたOpenLDAPである。^[73]
• lmdb_tableアダプタ経由のPostfix。^[74]
• PowerDNS、DNS サーバー。
• CFEngineはバージョン3.6.0以降、デフォルトでLMDBを使用します。^[75]
• ShopifyはSkyDBシステムでLMDBを使用しています。^[76]
• Knot DNS は高性能 DNS サーバーです。
• Monero は、プライバシー、分散化、スケーラビリティに重点を置いて 2014 年 4 月に作成されたオープン ソースの暗号通貨です。
• Enduro/Xミドルウェアは、オプションの XATMI マイクロサービス (SOA) キャッシュに LMDB を使用します。最初のリクエストでは実際のサービスが呼び出され、次のリクエストではクライアント プロセスが保存された結果を LMDB から直接読み取ります。
• Sambaアクティブ ディレクトリ ドメイン コントローラ
• Nano は、2015 年に作成された、高速かつ手数料無料のトランザクションを優先するピアツーピアのオープンソース暗号通貨です。
• Meilisearchはオープンソースで、超高速、使いやすく、関連性の高い検索エンジンです。^[77]
• LMDB-IndexedDBはIndexedDBをJavaScriptでラッパーしたもので、WebブラウザでLMDBのサポートを提供します。^[78]

LMDB は、コピーオンライトセマンティクスやB+ ツリーなどのよく知られたコンピュータサイエンスの手法を斬新に利用して、アトミック性と信頼性の保証とパフォーマンスを提供します。このライブラリは比較的単純で、他の同様のキーバリューストアデータベースでは同じ保証や全体的なパフォーマンスが提供されていないことを考えると、このパフォーマンスは受け入れがたいものです。著者はプレゼンテーションで、LMDB は書き込み最適化ではなく読み取り最適化であると明確に述べています。さらに、LMDB は主にOpenLDAPで使用するために開発されたため、その開発者は LMDB 自体ではなく、主に OpenLDAP の開発と保守に重点を置いています。開発者が最初のベンチマーク結果の発表に費やした時間を限っていたため、制限を述べておらず、エンジニアの態度に対処するのに十分ではない「万能薬のような印象」を与えたと批判されました^[79] (ただし、提起された懸念は、LMDB の背後にいる主要な開発者によって、レビュー担当者が満足する形で適切に対処されたことを指摘する必要があります。^[80] )

このプレゼンテーションは、他のデータベース開発者がコードを詳細に分析して、それがどのように、なぜ機能するのかを理解するきっかけとなった。レビューは、簡潔なものから詳細なものまでさまざまである^。データベース開発者の Oren Eini は、2013 年 7 月 9 日から 12 回にわたって LMDB の分析に関する記事を執筆した。結論は、「印象的なコードベース... もう少し手を加える必要がある」というもので、主な理由は、メソッドが長すぎることとコードの重複である。 ^{[82]このレビューは、} Cの経験がない .NET 開発者によって実施され、2013 年 8 月 22 日に「コードに関する問題はさておき、実装は非常に優れています。LMDB が何もせずに多くの機能を詰め込む方法は非常に印象的です... このプロジェクトから多くのことを学びました。これは、苛立たしく、苛立たしく、そして魅力的な経験でした」と結論づけられている。^[83]

他にも、中国語を含む様々な言語でLMDB ^{[84] [85]}を扱ったレビューが多数あります。 ^[86]