2019 年の秋、Mail.ru Cloud iOS チームで待望のイベントが開催されました。アプリケーションの状態を永続的に保存するためのメインデータベースは、モバイル世界にとって非常に珍しいものになっています。 Lightning メモリマップドデータベース (LMDB)。カットの下では、XNUMX 部構成の詳細なレビューに注目してください。まず、このような簡単ではなく難しい選択をした理由について話しましょう。次に、LMDB アーキテクチャの中心となる XNUMX つのクジラ、つまりメモリマップトファイル、B + ツリー、トランザクションおよびマルチバージョンを実装するためのコピーオンライトアプローチの検討に移りましょう。最後に、デザートの実践的な部分です。その中で、低レベルのキーと値の API の上に、インデックステーブルを含む複数のテーブルを含むデータベーススキーマを設計および実装する方法を見ていきます。

ページ内容

実装の動機
LMDBの位置決め
XNUMX 頭のクジラ LMDB
3.1. クジラその１。メモリマップされたファイル
3.2. クジラその２。 B+ツリー
3.3. クジラその３。コピーオンライト
Key-Value API に基づくデータスキーマの設計
4.1. 基本的な抽象化
4.2. テーブルモデリング
4.3. テーブル間の関係のモデル化

1. 導入動機

2015 年に年に XNUMX 回、アプリケーションのインターフェースがどのくらいの頻度で遅延するかという指標を削除しました。私たちはこれをただやっただけではありません。ボタンが押されない、リストがスクロールしないなど、アプリケーションがユーザーのアクションに応答しなくなる場合があるという事実に関する苦情が増えています。測定の仕組みについて私は言いました AvitoTech に掲載されているので、ここでは番号の順序のみを示します。

測定結果は私たちにとって冷水シャワーとなりました。フリーズによって引き起こされる問題は、他の問題よりもはるかに多いことが判明しました。この事実に気づく前に、品質の主要なテクニカル指標がクラッシュフリーだった場合、焦点が当てられた後は、ずれたフリーズフリーで。

構築したダッシュボードがフリーズするそして過ごした定量的 и 品質原因を分析すると、アプリケーションのメインスレッドで実行される重いビジネスロジックが主な敵であることが明らかになりました。この不名誉に対する自然な反応は、それを仕事の流れに押し込みたいという燃えるような願望でした。この問題を体系的に解決するために、私たちは軽量アクターに基づくマルチスレッドアーキテクチャに頼りました。私は彼女の適応を iOS の世界に捧げました XNUMXつのスレッド集合ツイッターやハブレに関する記事。今回の話の一環として、データベースの選択に影響を与えた決定の側面を強調したいと思います。

システム組織のアクターモデルは、マルチスレッドがその XNUMX 番目の本質になることを前提としています。その中のモデルオブジェクトはスレッドの境界を越えることを好みます。そして、彼らはこれを時々、いくつかの場所で行うのではなく、ほぼ常に、どこでも行います。

データベースは、提示された図の基礎となるコンポーネントの XNUMX つです。その主なタスクはマクロパターンを実装することです。共有データベース。エンタープライズ環境ではサービス間のデータ同期を組織するために使用され、アクターアーキテクチャの場合はスレッド間のデータ同期に使用されます。したがって、マルチスレッド環境での作業が最小限の問題さえ引き起こさないようなデータベースが必要でした。特に、これは、そこから派生したオブジェクトが少なくともスレッドセーフでなければならず、理想的にはまったく変更不可能であることを意味します。ご存知のとおり、後者はロックを使用せずに複数のスレッドから同時に使用できるため、パフォーマンスに有益な効果があります。

データベースの選択に影響を与えた XNUMX 番目の重要な要素は、クラウド API でした。これは、同期に対する git アプローチからインスピレーションを得たものです。彼のように私たちが目指したのはオフラインファーストAPIこれはクラウドクライアントに適しています。クラウドの完全な状態を一度だけ取り出すだけで、その後はほとんどの場合、ローリング変更を通じて同期が行われると想定されていました。残念なことに、この可能性はまだ理論上の領域にすぎず、実際には、クライアントはパッチの使い方を学んでいません。これには客観的な理由が多数ありますが、導入を遅らせないために括弧書きから外します。ここで、API が「A」と言い、その消費者が「B」と言わなかった場合に何が起こるかについてのレッスンの有益な結果は、さらに興味深いものです。

したがって、プルコマンドを実行するときに、ローカルスナップショットにパッチを適用するのではなく、その完全な状態をサーバー全体の状態と比較する git を想像すると、同期の仕組みについてかなり正確に理解できるでしょう。クラウドクライアントで発生します。その実装には、すべてのサーバーファイルとローカルファイルに関するメタ情報を含む 500 つの DOM ツリーをメモリに割り当てる必要があることは容易に推測できます。ユーザーが 1 万個のファイルをクラウドに保存している場合、それを同期するには、XNUMX 万ノードを持つ XNUMX つのツリーを再作成して破棄する必要があることがわかりました。ただし、各ノードはサブオブジェクトのグラフを含む集合体です。この観点から、プロファイリングの結果は予想通りでした。マージアルゴリズムを考慮しなくても、膨大な数の小さなオブジェクトを作成して破棄する手順自体にかなりの費用がかかることが判明しました。基本的な同期操作が多数のオブジェクトに含まれているという事実により、状況はさらに悪化しています。ユーザースクリプトの。その結果、データベースを選択する際の XNUMX 番目の重要な基準、つまりオブジェクトを動的に割り当てずに CRUD 操作を実装できる機能が修正されました。

他の要件はより伝統的なもので、その完全なリストは次のとおりです。

スレッドの安全性。
マルチプロセッシング。同じデータベースインスタンスを使用して、スレッド間だけでなく、メインアプリケーションと iOS 拡張機能の間でも状態を同期したいという要望によって決まります。
保存されたエンティティを変更不可能なオブジェクトとして表す機能。
CRUD 操作内での動的割り当ての欠如。
基本プロパティのトランザクションサポート ACIDキーワード: 原子性、一貫性、分離性、信頼性。
最も人気のあるケースをスピードアップします。

この一連の要件を考慮すると、SQLite は今も昔も優れた選択肢です。しかし、代替案を検討する中で、ある本に出会いました。「LevelDB 入門」。彼女のリーダーシップの下、実際のクラウドシナリオでさまざまなデータベースの作業速度を比較するベンチマークが作成されました。結果は最も予想を上回りました。最も一般的なケースでは、すべてのファイルのソートされたリスト上でカーソルを取得したり、指定されたディレクトリのすべてのファイルのソートされたリストを取得したりする場合、LMDB は SQLite より 10 倍高速であることが判明しました。選択は明白になりました。

2. LMDBの位置付け

LMDB は、データベースの最も低い基本層であるストレージを実装する、非常に小さい (わずか 10K 行) ライブラリです。

上の図は、LMDB とさらに高いレベルを実装する SQLite を比較することは、通常、SQLite と Core Data よりも正確ではないことを示しています。 BerkeleyDB、LevelDB、Sophia、RocksDB など、同じストレージエンジンを同等の競合他社として挙げる方が公平でしょう。LMDB が SQLite のストレージエンジンコンポーネントとして機能する開発さえあります。 2012年に初めてそのような実験が行われた行っ著者LMDB ハワード・チュー. 結果非常に興味深いものであることが判明したため、彼のイニシアチブは OSS 愛好家に取り上げられ、その継続が見出されました。 LumoSQL。 2020 年 XNUMX 月のこのプロジェクトの作成者は Den Shearer です提示された LinuxConfAu でご覧ください。

LMDB の主な用途は、アプリケーションデータベースのエンジンとしてです。ライブラリの外観は開発者のおかげです OpenLDAP彼らは、プロジェクトの基盤としての BerkeleyDB に強い不満を抱いていました。質素な図書館からの脱却ツリー, ハワード・チューは、現代で最も人気のある代替手段のXNUMXつを作成することができました。彼は、このストーリーと LMDB の内部構造について、非常にクールなレポートを作成しました。「ライトニングメモリマップドデータベース」。レオニード・ユリエフ（別名）イレオ) Highload 2015 での Positive Technologies の講演「LMDB エンジンは特別なチャンピオンです」。その中で彼は、ReOpenLDAP の実装という同様のタスクの文脈で LMDB について語っていますが、LevelDB はすでに比較批判を受けています。実装の結果、Positive Technologies は積極的に開発中のフォークを入手しました。 MDBX 非常に優れた機能、最適化、バグの修正.

LMDB は、そのままのストレージとしてもよく使用されます。たとえば、Mozilla Firefox ブラウザー選んだ多くのニーズに対応しており、バージョン 9 以降では Xcode 優先インデックスを保存するための SQLite。

このエンジンはモバイル開発の世界でも人気を博しました。使用の痕跡が残る可能性があります見つける Telegram の iOS クライアント内。 LinkedIn はさらに一歩進んで、自社開発のデータキャッシュフレームワークである Rocket Data のデフォルトストレージとして LMDB を選択しました。言った 2016年の記事で。

LMDB は、Oracle の管理下への移行後、BerkeleyDB が残したニッチな分野で、日の当たる場所をめぐって首尾よく戦っています。このライブラリは、同じ種類のライブラリと比較しても、その速度と信頼性で愛されています。ご存知のとおり、無料のランチはありません。LMDB と SQLite のどちらを選択するかについては、トレードオフに直面する必要があることを強調したいと思います。上の図は、高速化がどのように達成されるかを明確に示しています。まず、ディスクストレージ上の追加の抽象化レイヤーに対して料金を支払う必要はありません。もちろん、優れたアーキテクチャでは、依然としてそれらなしでは成り立ちません。必然的にアプリケーションコードにそれらが表示されますが、はるかに薄くなります。 SQL 言語でのクエリのサポートなど、特定のアプリケーションに必要のない機能は備えていません。第 XNUMX に、アプリケーションの操作とディスクストレージへのリクエストのマッピングを最適に実装できるようになります。 SQLiteの場合私の仕事で平均的なアプリケーションの平均的なニーズから生じている場合、アプリケーション開発者は主な負荷シナリオをよく知っています。より生産的なソリューションを実現するには、最初のソリューションの開発とその後のサポートの両方に高額な料金を支払う必要があります。

3. XNUMX 頭のクジラ LMDB

LMDB を俯瞰的に見た後は、さらに深く見ていきましょう。次の XNUMX つのセクションでは、ストレージアーキテクチャの基盤となる主な要素の分析に専念します。

ディスクを操作し、内部データ構造を同期するためのメカニズムとしてのメモリマップファイル。
保存されたデータ構造の組織としての B+ ツリー。
ACID トランザクションプロパティとマルチバージョン管理を提供するアプローチとしてのコピーオンライト。

3.1. クジラその１。メモリマップされたファイル

メモリマップされたファイルは、リポジトリの名前にも使用されるほど重要なアーキテクチャ要素です。保存された情報へのアクセスのキャッシュと同期の問題は、完全にオペレーティングシステムの判断に委ねられます。 LMDB 自体にはキャッシュが含まれません。マップされたファイルからデータを直接読み取ることで、エンジンの実装で多くの部分を省略できるため、これは作成者による意識的な決定です。以下は、それらの一部の完全なリストではありません。

複数のプロセスからストレージ内のデータを操作する場合、そのデータの一貫性を維持するのはオペレーティングシステムの責任になります。次のセクションでは、このメカニズムについて画像を使用して詳細に説明します。
キャッシュが存在しないため、LMDB は動的割り当てに関連するオーバーヘッドから完全に解放されます。実際のデータの読み取りとは、ポインタを仮想メモリ内の正しいアドレスに設定することだけであり、それ以上のものではありません。空想のように聞こえますが、リポジトリソースでは、すべての calloc 呼び出しがリポジトリ構成関数に集中しています。
キャッシュがないということは、キャッシュにアクセスするための同期に関連するロックがないことも意味します。同時に任意の数のリーダーが存在できますが、データにアクセスする途中で単一のミューテックスに遭遇することはありません。このため、読み取り速度は CPU の数に関して理想的な線形スケーラビリティを持ちます。 LMDB では、変更操作のみが同期されます。一度に存在できるライターは XNUMX 人だけです。
最小限のキャッシュと同期ロジックにより、マルチスレッド環境での作業に関連する非常に複雑なタイプのエラーからコードを節約できます。 Usenix OSDI 2014 カンファレンスでは、XNUMX つの興味深いデータベース研究がありました。「すべてのファイルシステムは同じように作られているわけではない: クラッシュコンシステントなアプリケーションの作成の複雑さについて」 и 娯楽と利益のためにデータベースを拷問する。これらから、LMDB の前例のない信頼性と、同じ SQLite でそれを上回るトランザクションの ACID プロパティのほぼ完璧な実装の両方に関する情報を得ることができます。
LMDB のミニマリズムにより、コードのマシン表現をプロセッサの L1 キャッシュに完全に配置でき、結果として速度特性が得られます。

残念ながら、iOS では、メモリマップされたファイルは私たちが望むほどバラ色ではありません。それらに関連する欠点についてより意識的に語るには、このメカニズムをオペレーティングシステムに実装するための一般原則を思い出す必要があります。

メモリマップトファイルに関する一般情報

オペレーティングシステムは、実行可能なアプリケーションごとに、プロセスと呼ばれるエンティティを関連付けます。各プロセスには連続したアドレス範囲が割り当てられ、動作するために必要なものすべてがそこに配置されます。最下位のアドレスには、コードとハードコードされたデータとリソースを含むセクションが含まれます。次に、ヒープとしてよく知られている、動的アドレス空間の上向きに成長するブロックが続きます。これには、プログラムの動作中に表示されるエンティティのアドレスが含まれます。一番上は、アプリケーションスタックによって使用されるメモリ領域です。大きくなったり、小さくなったり、つまりその大きさもダイナミックな性質を持っています。スタックとヒープが互いに押し合ったり干渉したりしないように、スタックとヒープはアドレス空間の異なる端で分離されており、上部と下部の XNUMX つの動的セクションの間には穴があります。この中間セクションのアドレスは、オペレーティングシステムによってさまざまなエンティティのプロセスに関連付けられるために使用されます。特に、特定の連続したアドレスのセットをディスク上のファイルにマッピングできます。このようなファイルはメモリマップトファイルと呼ばれます。

プロセスに割り当てられるアドレス空間は膨大です。理論的には、アドレスの数はポインタのサイズによってのみ制限されます。ポインタのサイズはシステムのビット深度によって決まります。物理メモリが 1-in-1 で割り当てられている場合、最初のプロセスが RAM 全体を使い果たし、マルチタスクが発生することは疑いの余地がありません。

しかし、私たちは経験から、最新のオペレーティングシステムでは同時に必要な数のプロセスを実行できることを知っています。これは、紙上のプロセスのみに多くのメモリを割り当てるという事実によって可能になりますが、実際には、現時点で必要な部分のみがメインの物理メモリにロードされます。したがって、プロセスに関連付けられたメモリは仮想と呼ばれます。

オペレーティングシステムは、仮想メモリと物理メモリを特定のサイズのページに編成します。仮想メモリの特定のページが必要になるとすぐに、オペレーティングシステムはそれを物理メモリにロードし、それらの対応関係を特別なテーブルに書き込みます。空きスロットがない場合は、以前にロードされたページの 0 つがディスクにコピーされ、要求されたページがその代わりになります。この手順については後で説明しますが、スワッピングと呼ばれます。以下の図は、説明されているプロセスを示しています。その上で、アドレス 4 のページ A がロードされ、アドレス 0 のメインメモリページに配置されました。この事実は、セル番号 XNUMX の対応表に反映されています。

メモリマップされたファイルの場合も、状況はまったく同じです。論理的には、それらは仮想アドレス空間に継続的かつ完全に配置されると考えられます。ただし、物理メモリにはページごとに、オンデマンドでのみアクセスされます。このようなページの変更は、ディスク上のファイルと同期されます。したがって、メモリ内のバイトを操作するだけで、ファイル I/O を実行できます。すべての変更は、オペレーティングシステムカーネルによって元のファイルに自動的に転送されます。
,war
以下の画像は、異なるプロセスからデータベースを操作するときに LMDB がどのように状態を同期するかを示しています。異なるプロセスの仮想メモリを同じファイルにマッピングすることにより、オペレーティングシステムは事実上、アドレス空間の特定のブロックを相互に推移的に同期することが義務付けられます。これが LMDB の目的です。
,war

重要な点は、LMDB が書き込みシステムコールメカニズムを通じてデフォルトでデータファイルを変更し、ファイル自体が読み取り専用モードで表示されることです。このアプローチには XNUMX つの重要な意味があります。

最初の結果は、すべてのオペレーティングシステムに共通です。その本質は、不正なコードによるデータベースへの不注意による損傷に対する保護を追加することです。ご存知のとおり、プロセスの実行可能命令は、アドレス空間内のどこからでもデータに自由にアクセスできます。同時に、先ほど思い出したように、ファイルを読み取り/書き込みモードで表示するということは、どの命令でもファイルをさらに変更できることを意味します。たとえば、存在しないインデックスにある配列要素を実際に上書きしようとするなど、誤ってこれを行った場合、この方法でこのアドレスにマップされているファイルを誤って変更する可能性があり、データベースの破損につながる可能性があります。ファイルが読み取り専用モードで表示されている場合、それに対応するアドレス空間を変更しようとすると、シグナルによるプログラムのクラッシュが発生します。 SIGSEGV、ファイルはそのまま残ります。

XNUMX 番目の結果は、すでに iOS に固有のものです。作者も他の情報源もそれについて明示的に言及していませんが、それがなければ、LMDB はこのモバイルオペレーティングシステムでの実行には適していません。次のセクションではその考察に専念します。

iOS のメモリマップされたファイルの詳細

2018年のWWDCでは素晴らしい報告がありました iOSメモリの詳細。 iOS では、物理メモリにあるすべてのページが、ダーティ、圧縮、クリーンの 3 つのタイプのいずれかに属することがわかります。

クリーンメモリは、物理メモリから安全にスワップアウトできるページのコレクションです。それらに含まれるデータは、必要に応じて元のソースから再ロードできます。読み取り専用のメモリマップファイルがこのカテゴリに分類されます。 iOS は、ファイルにマップされたページをディスク上のファイルと同期していることが保証されているため、いつでもメモリからアンロードすることを躊躇しません。
,war
変更されたすべてのページは、元の場所に関係なく、ダーティメモリに入ります。特に、関連付けられた仮想メモリへの書き込みによって変更されたメモリマップトファイルも、この方法で分類されます。フラグを使用して LMDB を開く MDB_WRITEMAP変更を加えた後は、自分の目で確認できます。

アプリケーションが物理メモリを過剰に占有し始めるとすぐに、iOS はダーティページを圧縮します。ダーティページや圧縮ページによって占有されているメモリの集合が、いわゆるアプリケーションのメモリフットプリントです。特定のしきい値に達すると、OOM キラーシステムデーモンがプロセスの後に来て強制的に終了します。これは、デスクトップオペレーティングシステムと比較した iOS の特殊性です。対照的に、物理メモリからディスクにページをスワップしてメモリ使用量を削減する機能は iOS には提供されておらず、その理由については推測するしかありません。おそらく、ページをディスクに集中的に移動したり、元に戻したりする手順は、モバイルデバイスにとってエネルギー消費が多すぎるか、iOS が SSD ディスク上のセルを書き換えるリソースを節約しているか、あるいは、すべてが揃っているシステムの全体的なパフォーマンスに設計者が満足していなかった可能性があります。常に交換されています。いずれにせよ、事実は変わりません。

良いニュースは、すでに前述したように、LMDB はデフォルトではファイルの更新に mmap メカニズムを使用しないことです。したがって、レンダリングされたデータは iOS によってクリーンメモリとして分類され、メモリフットプリントには影響しません。これは、VM Tracker と呼ばれる Xcode ツールを使用して確認できます。以下のスクリーンショットは、動作中の iOS クラウドアプリケーションの仮想メモリの状態を示しています。開始時には、2 つの LMDB インスタンスが初期化されました。 1 つ目はファイルを 512 GiB の仮想メモリにマップすることができ、XNUMX つ目は XNUMXMiB でした。どちらのストレージも一定量の常駐メモリを占有しますが、どちらもダーティサイズには影響しません。

さて、悪いニュースの時間です。 64 ビットデスクトップオペレーティングシステムのスワップメカニズムのおかげで、各プロセスは、ハードディスク上の空き領域がスワップの可能性を許容するのと同じだけ多くの仮想アドレス領域を占有することができます。 iOS でスワップを圧縮に置き換えると、理論上の最大値が大幅に減少します。現在、すべての生きているプロセスはメイン (RAM 読み取り) メモリに収まる必要があり、収まらないプロセスはすべて強制終了の対象となります。上記のように記載されていますが、レポート、および公式ドキュメント。結果として、iOS は mmap 経由で割り当て可能なメモリの量を厳しく制限します。ここここでこのシステムコールを使用して、さまざまなデバイスに割り当てられるメモリ量の経験的な制限を確認できます。スマートフォンの最新モデルでは、iOS の容量が 2 ギガバイト増加し、iPad の最上位バージョンでは 4 ギガバイト増加しています。もちろん、実際には、サポートされている最も若いデバイスモデルに注目する必要がありますが、そこではすべてが非常に残念です。さらに悪いことに、VM Tracker でアプリケーションのメモリ状態を確認すると、メモリマップドメモリを要求しているのは LMDB だけではないことがわかります。適切なチャンクは、システムアロケーター、リソースファイル、イメージフレームワーク、その他の小さな捕食者によって食い荒らされます。

クラウドでの実験の結果、LMDB によって割り当てられるメモリの妥協値として、384 ビットデバイスの場合は 32 メガバイト、768 ビットデバイスの場合は 64 メガバイトが見つかりました。このボリュームが使い果たされると、コードによる変更操作が完了し始めます。 MDB_MAP_FULL。モニタリングではこのようなエラーが観察されますが、この段階では無視できるほど小さいものです。

ストレージによる過剰なメモリ消費の明らかではない理由として、トランザクションの存続期間が長いことが考えられます。これら XNUMX つの現象がどのように関連しているかを理解するには、残りの XNUMX 頭の LMDB クジラを考慮することが役立ちます。

3.2. クジラその２。 B+ツリー

キー/値ストア上でテーブルをエミュレートするには、その API に次の操作が存在する必要があります。

新しい要素を挿入します。
指定されたキーを持つ要素を検索します。
要素を削除します。
ソート順にキー間隔を繰り返します。

XNUMX つの操作すべてを簡単に実装できる最も単純なデータ構造は、二分探索ツリーです。その各ノードは、子キーのサブセット全体を XNUMX つのサブツリーに分割するキーです。左側は親より小さいもの、右側は親より大きいものです。順序付けられたキーのセットの取得は、古典的なツリー走査の XNUMX つを通じて実現されます。

バイナリツリーには、ディスクデータ構造としての効果を妨げる XNUMX つの根本的な欠点があります。まず、そのバランスの度合いが予測できない。さまざまな枝の高さが大きく異なる可能性のあるツリーを取得することにはかなりのリスクがあり、これにより、予想されるものと比較して検索のアルゴリズムの複雑さが大幅に悪化します。第二に、ノード間のクロスリンクが豊富であるため、バイナリツリーのメモリ内での局所性が失われ、(ノード間のリンクという点で) 近いノードが仮想メモリ内のまったく異なるページに配置される可能性があります。その結果、ツリー内のいくつかの隣接ノードを単純に走査するだけでも、同等の数のページにアクセスする必要がある場合があります。プロセッサキャッシュ内でページを常に回転させるのはコストがかからないため、メモリ内データ構造としてのバイナリツリーの有効性について話す場合でも、これは問題になります。ノード関連のページをディスクから頻繁に呼び出すと、状況は非常に悪くなります。嘆かわしい。

B ツリーはバイナリツリーの進化版であり、前の段落で特定した問題を解決します。第一に、それらは自己バランスをとります。第 2 に、各ノードは子キーのセットを XNUMX つではなく、M 個の順序付きサブセットに分割します。M という数は、数百または数千のオーダーと非常に大きくなる可能性があります。

それによって：

各ノードにはすでに順序付けられた多数のキーがあり、ツリーは非常に低くなります。
値が近いキーは自然に XNUMX つまたは隣接するノード上で互いに隣り合って配置されるため、ツリーはメモリ内で局所性の特性を獲得します。
検索操作中にツリーを下降するときに通過ノードの数を減らします。
各ターゲットノードにはすでに大量の順序付けされたキーが含まれているため、範囲クエリで読み取られるターゲットノードの数が減ります。

LMDB は、B+ ツリーと呼ばれる B ツリーのバリアントを使用してデータを保存します。上の図は、それに含まれる XNUMX 種類のノードを示しています。

一番上にあるのが根です。これは、リポジトリ内のデータベースの概念を具体化したものにすぎません。単一の LMDB インスタンス内に、マップされた仮想アドレス空間を共有する複数のデータベースを作成できます。それぞれは独自のルートから始まります。
最下位レベルは葉 (リーフ) です。データベースに格納されているキーと値のペアを含むのは、それらだけです。ちなみに、これがB+-treeの特徴です。通常の B ツリーがすべてのレベルのノードに値部分を格納する場合、B+ 変動は最下位のノードにのみ存在します。この事実を修正したので、以下では、LMDB で使用されるツリーのサブタイプを単に B ツリーと呼びます。
ルートとリーフの間には、ナビゲーション (分岐) ノードを持つ 0 個以上の技術レベルがあります。彼らのタスクは、ソートされたキーのセットをリーフ間で分割することです。

物理的には、ノードは所定の長さのメモリのブロックです。それらのサイズは、上で説明したオペレーティングシステムのメモリページのサイズの倍数です。ノード構造を以下に示します。ヘッダーにはメタ情報が含まれており、その中で最も明白なものは、たとえばチェックサムです。次に、データを含むセルが位置するオフセットに関する情報が続きます。データの役割は、ナビゲーションノードについて話している場合はキー、またはリーフの場合はキーと値のペア全体のいずれかになります。ページの構造については、作品で詳しく読むことができます。「高性能 Key-Value ストアの評価」.

ページノードの内部コンテンツを扱ったので、次の形式で LMDB B ツリーをさらに簡略化して表します。

ノードを含むページはディスク上に順番に配置されます。番号が大きいページほど、ファイルの終わりに向かって配置されます。いわゆるメタページ (メタページ) には、すべてのツリーのルートを見つけるために使用できるオフセットに関する情報が含まれています。ファイルが開かれると、LMDB は有効なメタページを探してファイルをページごとに最後から最初までスキャンし、それを通じて既存のデータベースを見つけます。

データ構成の論理的および物理的構造を理解したので、LMDB の XNUMX 番目のクジラの検討に進むことができます。これにより、すべてのストレージ変更がトランザクション的に相互に分離して実行され、データベース全体にマルチバージョン特性も与えられます。

3.3. クジラその３。コピーオンライト

一部の B ツリー操作には、そのノードに対する一連の変更全体が含まれます。一例として、すでに最大容量に達しているノードに新しいキーを追加することが挙げられます。この場合、まずノードを XNUMX つに分割し、次にその親ノードに新しくスピンオフされた子ノードへのリンクを追加する必要があります。この手順は潜在的に非常に危険です。何らかの理由 (クラッシュ、停電など) でシリーズからの変更の一部のみが発生した場合、ツリーは不整合な状態のままになります。

データベースをフォールトトレラントにするための従来の解決策の XNUMX つは、追加のディスクベースのデータ構造であるトランザクションログ (WAL) を B ツリーの隣に追加することです。これは、B ツリー自体が変更される直前に、その末尾に意図した操作が記述されるファイルです。したがって、自己診断中にデータ破損が検出された場合、データベースはログを参照して自身をクリーンアップします。

LMDB は、フォールトトレランスメカニズムとして、コピーオンライトと呼ばれる別の方法を選択しました。その本質は、既存のページのデータを更新するのではなく、まずページ全体をコピーし、そのコピー内にすでに含まれているすべての変更を行うことです。

また、更新されたデータを利用できるようにするためには、親ノードにおいて最新になったノードへのリンクを、そのノードに関連して変更する必要がある。このためにも修正が必要なので、これも事前にコピーされます。このプロセスはルートに至るまで再帰的に続行されます。メタページ上のデータは最後に変更されます。

更新手順中にプロセスが突然クラッシュした場合、新しいメタページが作成されないか、最後までディスクに書き込まれず、そのチェックサムが不正確になります。これら XNUMX つのケースのいずれの場合も、新しいページにはアクセスできなくなりますが、古いページは影響を受けません。これにより、LMDB がデータの一貫性を維持するためにログを先行書き込む必要がなくなります。実際には、上で説明したディスク上のデータストレージの構造が同時にその機能を果たします。明示的なトランザクションログがないことは、高いデータ読み取り速度を提供する LMDB の機能の XNUMX つです。

追加専用 B ツリーと呼ばれる結果として得られる構造は、トランザクションの分離とマルチバージョン管理を自然に提供します。 LMDB では、開いている各トランザクションには、それに関連付けられた最新のツリールートがあります。トランザクションが完了しない限り、トランザクションに関連付けられたツリーのページが変更されたり、新しいバージョンのデータに再利用されたりすることはありません。したがって、トランザクション時に関連していたデータセットを正確に好きなだけ操作できます。この時点でストレージがアクティブに更新され続けている場合でも、トランザクションがオープンされた時点で。これがマルチバージョン管理の本質であり、LMDB を私たちの愛する人にとって理想的なデータソースにします。 UICollectionView。トランザクションを開いた後は、何も残らないことを恐れて、アプリケーションのメモリ使用量を増やしたり、現在のデータをメモリ内の構造に急いで送り込んだりする必要はありません。この機能は、LMDB を、そのような完全な分離を誇ることができない同じ SQLite と区別します。後者で XNUMX つのトランザクションを開き、そのうちの XNUMX つで特定のレコードを削除すると、XNUMX 番目に残ったトランザクションでは同じレコードを取得できなくなります。

コインの裏返しとして、仮想メモリの消費量が大幅に増加する可能性があります。このスライドは、データベースの異なるバージョンを参照する 3 つのオープン読み取りトランザクションを同時に変更した場合に、データベース構造がどのようになるかを示しています。 LMDB は実際のトランザクションに関連付けられたルートから到達可能なノードを再利用できないため、ストレージにはメモリ内に別の XNUMX 番目のルートを割り当て、その下に変更されたページをもう一度複製する以外に選択肢はありません。

ここで、メモリマップトファイルに関するセクションを思い出すのは不必要ではありません。仮想メモリの追加消費は、アプリケーションのメモリフットプリントに影響しないため、あまり気にする必要はないようです。しかし同時に、iOS はその割り当てを非常にケチであり、マスターの肩からサーバーまたはデスクトップ上に 1 テラバイトの LMDB 領域を提供し、この機能についてまったく考慮することはできません。可能であれば、トランザクションの存続期間をできるだけ短くするように努めてください。

4. Key-Value API に基づくデータスキーマの設計

LMDB が提供する基本的な抽象化 (環境とデータベース、キーと値、トランザクションとカーソル) を見て API の解析を始めましょう。

コードリストに関する注意

LMDB パブリック API のすべての関数は、作業の結果をエラーコードの形式で返しますが、後続のすべてのリストでは、簡潔にするためにそのチェックは省略されています。実際には、リポジトリと対話するために独自のコードを使用しました。フォーク C++ ラッパー lmdbxxこの場合、エラーは C++ 例外として発生します。

LMDB を iOS または macOS プロジェクトに接続する最速の方法として、CocoaPod を提供します。 POSLMDB.

4.1. 基本的な抽象化

環境

構造 MDB_env は、LMDB の内部状態のリポジトリです。接頭辞付き関数のファミリー mdb_env いくつかのプロパティを設定できます。最も単純なケースでは、エンジンの初期化は次のようになります。

mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

Mail.ru クラウドアプリケーションでは、XNUMX つのパラメーターのみのデフォルト値を変更しました。

XNUMX つ目は、ストレージファイルがマップされる仮想アドレス空間のサイズです。残念ながら、同じデバイスであっても、特定の値は実行ごとに大きく異なる可能性があります。 iOS のこの機能を考慮して、ストレージの最大量を動的に選択します。特定の値から開始して、関数が達成されるまで連続的に半分になります。 mdb_env_open 以外の結果は返されません ENOMEM。理論的には、逆の方法があります。まずエンジンに最小限のメモリを割り当て、次にエラーを受信したときに、 MDB_MAP_FULL、増やしてください。しかし、それははるかに厄介です。その理由は、関数を使用してメモリを再マッピングする手順が mdb_env_set_map_size 以前にエンジンから受け取ったすべてのエンティティ (カーソル、トランザクション、キー、値) を無効にします。コード内でこのような出来事の変化を考慮すると、コードが大幅に複雑になります。それでも、仮想メモリがあなたにとって非常に大切である場合、これははるか先の分岐点に注目する理由になるかもしれません。 MDBX, 宣言された機能の中には、「自動オンザフライデータベースサイズ調整」があります。

10 番目のパラメータは、デフォルト値が適切ではありませんでしたが、スレッドの安全性を確保するメカニズムを制御します。残念ながら、少なくとも iOS XNUMX では、スレッドローカルストレージのサポートに問題があります。このため、上記の例では、リポジトリは次のフラグで開かれます。 MDB_NOTLS。さらに、次のことも必要でしたフォーク C++ ラッパー lmdbxxこの属性を使用して変数を切り取ります。

データベース

データベースは、上で説明した B ツリーの別のインスタンスです。このオープンはトランザクション内で行われるため、最初は少し奇妙に思えるかもしれません。

MDB_txn *txn;
MDB_dbi dbi;
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);
mdb_txn_abort(txn);

実際、LMDB のトランザクションはストレージエンティティであり、特定のデータベースではありません。この概念により、異なるデータベースにあるエンティティに対してアトミックな操作を実行できます。理論的には、これにより、さまざまなデータベースの形式でテーブルをモデル化する可能性が開かれますが、後で詳しく説明するように、私はかつて別の方法をとりました。

キーと値

構造 MDB_val キーと値の両方の概念をモデル化します。リポジトリはそれらのセマンティクスについては知りません。彼女にとって、異なるものは、指定されたサイズのバイトの配列にすぎません。キーの最大サイズは 512 バイトです。

typedef struct MDB_val {
    size_t mv_size;
    void *mv_data;
} MDB_val;

ストアはコンパレータを使用してキーを昇順に並べ替えます。独自のものに置き換えない場合は、辞書編集順にバイトごとに並べ替えるデフォルトのものが使用されます。

取引

トランザクションデバイスについては、以下で詳しく説明されています。前の章そこで、ここではその主なプロパティを短い行で繰り返します。

すべての基本プロパティのサポート ACIDキーワード: 原子性、一貫性、分離性、信頼性。 macOS と iOS での耐久性の点で、MDBX で修正されたバグがあることに注意せずにはいられません。詳しくは、彼らの記事をご覧ください。 README.
マルチスレッドへのアプローチは、「単一ライター/複数リーダー」スキームで説明されます。ライターは互いにブロックしますが、リーダーはブロックしません。リーダーはライターをブロックしたり、相互にブロックしたりしません。
ネストされたトランザクションのサポート。
マルチバージョンのサポート。

LMDB のマルチバージョン管理は非常に優れているので、実際に動作を示したいと思います。以下のコードは、各トランザクションが、そのオープン時に関連していたバージョンのデータベースを正確に操作し、その後のすべての変更から完全に分離されていることを示しています。リポジトリを初期化したり、リポジトリにテストレコードを追加したりすることは重要ではないため、これらの儀式はスポイラーの下に残されます。

テストエントリの追加

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

必要に応じて、SQLite で同じトリックを試して、何が起こるかを確認することをお勧めします。

マルチバージョン化は、iOS 開発者の生活に非常に素晴らしいメリットをもたらします。このプロパティを使用すると、ユーザーエクスペリエンスの考慮事項に基づいて、画面フォームのデータソース更新レートを簡単かつ自然に調整できます。たとえば、システムメディアギャラリーからのコンテンツの自動読み込みなど、Mail.ru クラウドアプリケーションの機能を考えてみましょう。接続が良好であれば、クライアントは XNUMX 秒あたり数枚の写真をサーバーに追加できます。ダウンロードするたびに更新する場合 UICollectionView ユーザーのクラウド内のメディアコンテンツでは、このプロセス中に 60 fps やスムーズなスクロールのことを忘れることができます。頻繁な画面更新を防ぐには、ベース内のデータ変更速度を何らかの方法で制限する必要があります。 UICollectionViewDataSource.

データベースがマルチバージョンをサポートしておらず、現在の状態でのみ作業できる場合、時間安定したデータスナップショットを作成するには、それをメモリ内のデータ構造または一時テーブルにコピーする必要があります。これらのアプローチはいずれも非常に高価です。インメモリストレージの場合、構築されたオブジェクトの保存によって発生するメモリコストと、冗長な ORM 変換に関連する時間コストの両方が発生します。一時テーブルに関しては、これはさらに高価な楽しみであり、重要な場合にのみ意味があります。

LMDB のマルチバージョン化は、安定したデータソースを維持するという問題を非常にエレガントな方法で解決します。トランザクションを開くだけで十分です。トランザクションが完了するまで、データセットは修正されることが保証されます。更新レートのロジックは完全にプレゼンテーション層の手に委ねられており、大量のリソースのオーバーヘッドは発生しません。

カーソル

カーソルは、B ツリーを走査することにより、キーと値のペアを規則的に反復するためのメカニズムを提供します。これらがなければ、データベース内のテーブルを効果的にモデル化することは不可能であり、ここで注目します。

4.2. テーブルモデリング

キー順序付けプロパティを使用すると、基本的な抽象化の上にテーブルなどのトップレベルの抽象化を構築できます。このプロセスを、ユーザーのすべてのファイルとフォルダーに関する情報がキャッシュされているクラウドクライアントのメインテーブルの例で考えてみましょう。

テーブルスキーマ

フォルダーツリーを含むテーブルの構造を明確にする必要がある一般的なシナリオの XNUMX つは、特定のディレクトリ内にあるすべての要素を選択することです。この種の効率的なクエリに適したデータ編成モデルは次のとおりです。隣接リスト。これをキーと値のストレージ上に実装するには、親ディレクトリに属しているかどうかに基づいてグループ化されるように、ファイルとフォルダーのキーを並べ替える必要があります。さらに、ディレクトリの内容を Windows ユーザーに馴染みのある形式 (最初にフォルダー、次にファイル、どちらもアルファベット順にソート) で表示するには、対応する追加フィールドをキーに含める必要があります。

下の図は、タスクに基づいて、バイトの配列としてのキーの表現がどのように見えるかを示しています。まず、親ディレクトリ識別子 (赤) を持つバイトが配置され、次にタイプ (緑) が配置され、すでに名前 (青) が末尾に配置されます。デフォルトの LMDB コンパレータによって辞書順に並べ替えられるため、次のように並べられます。必要な方法。同じ赤い接頭辞を持つキーを順次走査すると、追加の後処理を必要とせずに、ユーザーインターフェイスに表示される順序でそれらに関連付けられた値が得られます (右)。

キーと値のシリアル化

オブジェクトをシリアル化する方法は世界中に数多くあります。速度以外の要件はなかったため、C 言語構造のインスタンスによって占有されるメモリダンプという、可能な限り高速なものを選択しました。したがって、ディレクトリ要素のキーは次の構造でモデル化できます。 NodeKey.

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameBuffer[256];
} NodeKey;

保存する NodeKey オブジェクト内のストレージが必要です MDB_val データへのポインタを構造体の先頭のアドレスに配置し、関数でサイズを計算します。 sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

データベースの選択基準に関する最初の章では、CRUD 操作の一部として動的割り当てを最小限に抑えることが重要な選択要素であると述べました。機能コード serialize は、LMDB の場合、新しいレコードがデータベースに挿入されるときにこれらのエラーを完全に回避できる方法を示しています。サーバーから受信したバイト配列は、まずスタック構造に変換され、その後、ストレージに簡単にダンプされます。 LMDB 内には動的割り当てがないため、iOS の標準では素晴らしい状況が得られます。ネットワークからディスクに至るまでのデータの処理にはスタックメモリのみを使用します。

バイナリコンパレータを使用したキーの順序付け

キーの順序関係は、コンパレータと呼ばれる特別な関数によって与えられます。エンジンは、含まれるバイトのセマンティクスについて何も知らないため、デフォルトのコンパレーターは、バイトごとの比較に頼って、キーを辞書編集順に配置する以外に選択肢がありません。これを使用して構造物を配置することは、彫刻斧で削ることに似ています。ただし、単純な場合には、この方法が受け入れられると思います。代替案については以下で説明しますが、ここでは途中に散在するいくつかの熊手に注目します。

最初に覚えておくべきことは、プリミティブデータ型のメモリ表現です。したがって、すべての Apple デバイスでは、整数変数は次の形式で保存されます。リトルエンディアン。これは、最下位バイトが左側に配置され、バイトごとの比較を使用して整数を並べ替えることができないことを意味します。たとえば、0 から 511 までの一連の数値を使用してこれを実行しようとすると、次の結果が得られます。

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

この問題を解決するには、バイトコンパレータに適した形式で整数をキーに格納する必要があります。家族の役割は、必要な変革を実行するのに役立ちます。 hton* （特に htons 例の全角数字の場合)。

ご存知のとおり、プログラミングで文字列を表現するための形式は、 история。文字列のセマンティクス、およびメモリ内で文字列を表すために使用されるエンコーディングによって、XNUMX 文字あたり複数のバイトが存在する可能性があることが示唆される場合は、デフォルトのコンパレータを使用するという考えを直ちに放棄した方がよいでしょう。

XNUMX番目に留意すべきことは、調整の原則構造体フィールドコンパイラ。そのため、フィールド間のメモリ内にガベージ値を含むバイトが形成される可能性があり、当然、バイトソートが中断されます。ガベージを排除するには、位置合わせ規則を念頭に置いて厳密に定義された順序でフィールドを宣言するか、構造体宣言で属性を使用する必要があります。 packed.

外部コンパレータによるキーの順序付け

重要な比較ロジックは、バイナリコンパレータにとっては複雑すぎることが判明する場合があります。多くの理由のうちの XNUMX つは、構造内に技術分野が存在することです。ディレクトリ要素としてすでによく知られているキーの例で、その発生を説明します。

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameBuffer[256];
} NodeKey;

非常にシンプルであるにもかかわらず、ほとんどの場合、メモリを大量に消費します。タイトルバッファーは 256 バイトですが、平均してファイル名やフォルダー名が 20 ～ 30 文字を超えることはほとんどありません。

レコードのサイズを最適化するための標準的な手法の XNUMX つは、実際のサイズに合わせてレコードを「カット」することです。その本質は、すべての可変長フィールドの内容が構造体の最後にあるバッファーに格納され、その長さが別の変数に格納されるということです。 NodeKey 以下のように変形されます。

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

なお、シリアル化時はデータサイズとして指定されません。 sizeof 構造全体であり、すべてのフィールドのサイズは固定長にバッファの実際に使用される部分のサイズを加えたものになります。

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

リファクタリングの結果、キーが占めるスペースが大幅に節約されました。ただし、技術的な分野のため、 nameLength、デフォルトのバイナリコンパレータはキー比較には適さなくなりました。これを独自のものに置き換えない場合、並べ替えでは名前自体よりも名前の長さが優先されることになります。

LMDB を使用すると、各データベースに独自のキー比較機能を持たせることができます。これは関数を使用して行われます mdb_set_compare 厳密には開封前です。明らかな理由により、データベースはその存続期間を通じて変更することができません。コンパレータは入力時に 1 つのキーをバイナリ形式で受け取り、出力時に比較結果 (-1 より小さい、0 より大きい、または XNUMX) を返します。の疑似コード NodeKey そのようです。

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey * const aKey = (NodeKey * const)a->mv_data;
    NodeKey * const bKey = (NodeKey * const)b->mv_data;
    return // ...
}

データベース内のすべてのキーが同じ型である限り、そのバイト表現をキーのアプリケーション構造の型に無条件にキャストすることは合法です。ここにはニュアンスが XNUMX つありますが、それについては「読書記録」のサブセクションで少し下で説明します。

値のシリアル化

保存されたレコードのキーを使用して、LMDB は非常に集中的に動作します。これらは、アプリケーション操作のフレームワーク内で相互に比較され、ソリューション全体のパフォーマンスはコンパレーターの速度に依存します。理想的には、キーを比較するにはデフォルトのバイナリコンパレータで十分であるはずですが、どうしても独自のバイナリコンパレータを使用する必要がある場合は、その中でキーを逆シリアル化する手順をできるだけ高速にする必要があります。

データベースは、レコードの値部分 (値) には特に関心がありません。バイト表現からオブジェクトへの変換は、アプリケーションコードですでに必要とされている場合 (たとえば、画面上に表示する場合) にのみ行われます。これは比較的まれに発生するため、この手順の速度に関する要件はそれほど重要ではなく、実装では利便性をより自由に重視できます。たとえば、まだダウンロードされていないファイルに関するメタデータをシリアル化するには、次を使用します。 NSKeyedArchiver.

NSData *data = serialize(object);
MDB_val value = {
    .mv_size = data.length,
    .mv_data = (void *)data.bytes
};

ただし、パフォーマンスが重要な場合もあります。たとえば、ユーザークラウドのファイル構造に関するメタ情報を保存する場合、同じオブジェクトメモリダンプを使用します。シリアル化された表現を生成するタスクのハイライトは、ディレクトリの要素がクラス階層によってモデル化されるという事実です。

C 言語での実装では、継承者の特定のフィールドが別の構造体に取り出され、基本フィールドとの接続が共用体型のフィールドを通じて指定されます。共用体の実際の内容は、type 技術属性によって指定されます。

typedef struct NodeValue {
    EntityId localId;
    EntityType type;
    union {
        FileInfo file;
        DirectoryInfo directory;
    } info;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeValue;

レコードの追加と更新

シリアル化されたキーと値をストアに追加できます。このために、関数が使用されます mdb_put.

// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

構成段階で、リポジトリが同じキーを持つ複数のレコードを保存することを許可または禁止できます。キーの重複が禁止されている場合、レコードを挿入するときに、既存のレコードの更新を許可するかどうかを決定できます。ほつれがコード内のエラーの結果としてのみ発生する可能性がある場合は、フラグを指定することでほつれを防ぐことができます。 NOOVERWRITE。

読書記録

LMDBのレコードを読み取る関数は次のとおりです。 mdb_get。キーと値のペアが以前にダンプされた構造によって表されている場合、この手順は次のようになります。

NodeValue * const readNode(..., NodeKey * const key) {
    MDB_val rawKey = serialize(key);
    MDB_val rawValue;
    mdb_get(..., &rawKey, &rawValue);
    return (NodeValue * const)rawValue.mv_data;
}

提示されたリストは、構造のダンプによるシリアル化によって、データの書き込み時だけでなく読み取り時に動的割り当てをどのように取り除くことができるかを示しています。関数から派生 mdb_get ポインタは、データベースがオブジェクトのバイト表現を格納する仮想メモリアドレスを正確に参照します。実際、非常に高速なデータ読み取りを提供する一種の ORM をほぼ無料で入手できます。このアプローチの美しさとともに、それに関連するいくつかの機能を覚えておく必要があります。

読み取り専用トランザクションの場合、値構造体へのポインターは、トランザクションが終了するまでのみ有効であることが保証されます。前述したように、オブジェクトが存在する B ツリーのページは、コピーオンライトの原則により、少なくとも XNUMX つのトランザクションが参照している限り変更されません。同時に、それらに関連付けられた最後のトランザクションが完了するとすぐに、ページを新しいデータ用に再利用できます。オブジェクトを作成したトランザクションを存続させる必要がある場合でも、オブジェクトをコピーする必要があります。
読み書きトランザクションの場合、結果の構造値へのポインタは、最初の変更プロシージャ (データの書き込みまたは削除) が実行されるまでのみ有効です。
構造にしても、 NodeValue 本格的ではありませんが、トリミングされており (サブセクション「外部コンパレータによるキーの順序付け」を参照)、ポインタを介してそのフィールドに簡単にアクセスできます。重要なことは、それを逆参照しないことです。
いかなる場合でも、受信したポインタを介して構造を変更することはできません。すべての変更はメソッドを通じてのみ行う必要があります mdb_put。ただし、この構造が配置されているメモリ領域は読み取り専用モードでマップされているため、これを実行したいと考えても機能しません。
たとえば、関数を使用して最大ストレージサイズを増やすために、ファイルをプロセスのアドレス空間に再マップします。 mdb_env_set_map_size 一般にすべてのトランザクションと関連エンティティ、特に読み取りオブジェクトへのポインタを完全に無効にします。

最後に、もう XNUMX つの特徴は非常に陰険なので、その本質の開示はもう XNUMX つの点だけに当てはまりません。 B ツリーに関する章では、メモリ内のページの構成を図で示しました。このことから、シリアル化されたデータを含むバッファの先頭アドレスは完全に任意であることがわかります。このため、構造体で取得されるそれらへのポインタは、 MDB_val 構造体へのポインタへのキャストは、通常、整列されていません。同時に、一部のチップ (iOS の場合は armv7) のアーキテクチャでは、データのアドレスがマシンワードのサイズ、つまりシステムのビット数の倍数であることが必要です。 (armv7 の場合、これは 32 ビットです)。つまり、次のような操作です *(int *foo)0x800002 彼らにとっては逃亡と同等であり、評決による処刑につながる EXC_ARM_DA_ALIGN。このような悲しい運命を回避するにはXNUMXつの方法があります。

XNUMX つ目は、事前にデータを既知の位置合わせ構造にコピーすることです。たとえば、カスタムコンパレータでは、これは次のように反映されます。

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

別の方法は、キーと値を持つ構造体が属性を使用して整列されない可能性があることをコンパイラに事前に通知することです。 aligned(1)。 ARM でも同じ効果が得られます成し遂げるそしてパックされた属性を使用します。構造体が占めるスペースの最適化にも貢献することを考えると、この方法が好ましいように思えますが、 приводит データアクセス操作のコストを増加させるため。

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

範囲クエリ

レコードのグループを反復処理するために、LMDB はカーソル抽象化を提供します。すでによく知られているユーザークラウドメタデータを含むテーブルの例を使用して、その操作方法を見てみましょう。

ディレクトリ内のファイルのリストを表示する一環として、その子ファイルとフォルダが関連付けられているすべてのキーを検索する必要があります。前のサブセクションでは、キーを並べ替えました。 NodeKey したがって、最初に親ディレクトリ ID によって順序付けされます。したがって、技術的には、フォルダーのコンテンツを取得するタスクは、特定のプレフィックスを持つキーのグループの上部境界にカーソルを置き、その後下部境界まで反復することになります。

順次検索で「額の上」の上限を見つけることができます。これを行うには、データベース内のキーのリスト全体の先頭にカーソルを置き、その下に親ディレクトリ識別子を持つキーが表示されるまでカーソルを増やします。このアプローチには明らかな欠点が 2 つあります。

検索の線形複雑さは、ご存知のとおり、ツリー一般、特に B ツリーでは対数時間で実行できます。
無駄に、目的のページに先行するすべてのページがファイルからメインメモリに引き上げられるため、非常にコストがかかります。

幸いなことに、LMDB API はカーソルを最初に配置するための効率的な方法を提供します。これを行うには、間隔の上限にあるキー以下の値を持つことがわかっているキーを作成する必要があります。たとえば、上図のリストに関連して、フィールドに次のようなキーを作成できます。 parentId は 2 になり、残りはすべてゼロで埋められます。このような部分的に入力されたキーは関数の入力に供給されます。 mdb_cursor_get 指示操作 MDB_SET_RANGE。

NodeKey upperBoundSearchKey = {
    .parentId = 2,
    .type = 0,
    .nameLength = 0
};
MDB_val value, key = serialize(upperBoundSearchKey);
MDB_cursor *cursor;
mdb_cursor_open(..., &cursor);
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

キーのグループの上限が見つかった場合は、キーが一致するか、キーが別のキーに一致するまで、それを繰り返します。 parentIdそうでないとキーがまったくなくなりません。

do {
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
    // processing...
} while (MDB_NOTFOUND != rc && // check end of table
         IsTargetKey(key));    // check end of keys group

素晴らしいのは、mdb_cursor_get を使用した反復の一部として、キーだけでなく値も取得できることです。選択条件を満たすために、特にレコードの値部分のフィールドをチェックする必要がある場合、追加のジェスチャなしでフィールド自体にアクセスできます。

4.3. テーブル間の関係のモデル化

これまでに、私たちは単一テーブルデータベースの設計と操作のあらゆる側面を考慮することができました。テーブルは、同じタイプのキーと値のペアで構成される、ソートされたレコードのセットであると言えます。キーを長方形として表示し、それに関連付けられた値をボックスとして表示すると、データベースの視覚的な図が得られます。

,war

しかし、現実の生活では、それほど少量の出血で済んでしまうことはほとんどありません。多くの場合、データベースでは、まず、複数のテーブルが必要であり、次に、主キーとは異なる順序でそれらのテーブル内で選択を実行する必要があります。この最後のセクションでは、その作成と相互接続の問題について説明します。

インデックステーブル

クラウドアプリには「ギャラリー」セクションがあります。クラウド全体のメディアコンテンツが日付順に表示されます。このような選択を最適に実装するには、メインテーブルの隣に、新しいタイプのキーを使用して別のテーブルを作成する必要があります。これらには、ファイルの作成日を含むフィールドが含まれており、これが主な並べ替え基準として機能します。新しいキーは基になるテーブルのキーと同じデータを参照するため、インデックスキーと呼ばれます。下の図ではオレンジ色でハイライトされています。

同じデータベース内で異なるテーブルのキーを互いに分離するために、追加の技術フィールド tableId がすべてのテーブルに追加されました。ソートの優先順位を最優先にすることで、独自のルールに従って、キーを最初にテーブルごとにグループ化し、すでにテーブル内にグループ化します。

インデックスキーは、主キーと同じデータを参照します。主キーの値部分のコピーを関連付けてこのプロパティを直接実装することは、いくつかの観点から一度に最適とは言えません。

占有スペースの観点から見ると、メタデータは非常に豊富になる可能性があります。
パフォーマンスの観点から見ると、ノードのメタデータを更新するときに XNUMX つのキーを上書きする必要があるためです。
コードサポートの観点から見ると、結局のところ、いずれかのキーのデータの更新を忘れると、ストレージ内でデータの不整合という微妙なバグが発生することになります。

次に、これらの欠点を解消する方法を考えます。

テーブル間の関係の構成

このパターンは、インデックステーブルをメインのテーブルにリンクするのに適しています。 「値としてのキー」。その名前が示すように、インデックスレコードの値部分は主キー値のコピーです。このアプローチにより、プライマリレコードの値部分のコピーの保存に関連する上記の欠点がすべて解消されます。唯一の料金は、インデックスキーによって値を取得するには、データベースに対して 2 つではなく XNUMX つのクエリを実行する必要があることです。概略的には、結果として得られるデータベーススキーマは次のとおりです。

テーブル間の関係を整理する別のパターンは次のとおりです。 「冗長キー」。その本質は、キーに追加の属性を追加することですが、これは並べ替えのためではなく、関連付けられたキーを再作成するために必要です。ただし、Mail.ru クラウドアプリケーションでの実際の使用例があります。特定の iOS フレームワークのコンテキストで、架空の、しかしよりわかりやすい例を示します。

クラウドモバイルクライアントには、ユーザーが他の人と共有したすべてのファイルとフォルダーを表示するページがあります。このようなファイルは比較的少数であり、それらに関連する宣伝に関する具体的な情報 (誰にアクセスが許可されているか、どのような権利が付与されているかなど) が多数あるため、ファイルにファイルの値の部分を負担させるのは合理的ではありません。メインテーブルのレコード。ただし、そのようなファイルをオフラインで表示したい場合は、やはりどこかに保存する必要があります。自然な解決策は、それ用に別のテーブルを作成することです。以下の図では、キーの先頭に「P」が付いており、「propname」プレースホルダーはより具体的な値「public info」に置き換えることができます。

新しいテーブルを作成するために作成されたすべての一意のメタデータは、レコードの値部分に移動されます。同時に、メインテーブルに既に保存されているファイルやフォルダーに関するデータを複製したくありません。代わりに、冗長データが「ノード ID」および「タイムスタンプ」フィールドの形式で「P」キーに追加されます。これらのおかげで、インデックスキーを構築し、それによって主キーを取得し、最終的にノードのメタデータを取得できます。

結論

LMDBの導入結果は前向きに評価しています。その後、アプリケーションのフリーズ数が 30% 減少しました。

行われた作業の結果、iOS チーム以外からも反響が得られました。現在、Android アプリケーションの主要な「ファイル」セクションの XNUMX つも LMDB の使用に切り替えられており、他の部分も準備中です。キーと値のストレージが実装されている C 言語は、最初に C++ 言語でクロスプラットフォームのアプリケーションバインディングを作成するのに役立ちました。結果の C++ ライブラリと Objective-C および Kotlin のプラットフォームコードをシームレスに接続するには、コードジェネレーターが使用されました。ジンニ Dropbox からですが、それはまた別の話です。

出所： habr.com

iOS アプリケーションにおける Key-Value データベース LMDB の優秀さと貧弱さ

ページ内容

1. 導入動機

2. LMDBの位置付け

3. XNUMX 頭のクジラ LMDB

3.1. クジラその１。メモリマップされたファイル

メモリマップトファイルに関する一般情報

iOS のメモリマップされたファイルの詳細

3.2. クジラその２。 B+ツリー

3.3. クジラその３。コピーオンライト

4. Key-Value API に基づくデータスキーマの設計

4.1. 基本的な抽象化

環境

データベース

キーと値

取引

カーソル

4.2. テーブルモデリング

テーブルスキーマ

キーと値のシリアル化

バイナリコンパレータを使用したキーの順序付け

外部コンパレータによるキーの順序付け

値のシリアル化

レコードの追加と更新

読書記録

範囲クエリ

4.3. テーブル間の関係のモデル化

インデックステーブル

テーブル間の関係の構成

結論

コメントを追加します返信をキャンセル

iOS アプリケーションにおける Key-Value データベース LMDB の優秀さと貧弱さ

ページ内容

1. 導入動機

2. LMDBの位置付け

3. XNUMX 頭のクジラ LMDB

3.1. クジラその１。 メモリマップされたファイル

メモリマップトファイルに関する一般情報

iOS のメモリマップされたファイルの詳細

3.2. クジラその２。 B+ツリー

3.3. クジラその３。 コピーオンライト

4. Key-Value API に基づくデータ スキーマの設計

4.1. 基本的な抽象化

環境

データベース

キーと値

取引

カーソル

4.2. テーブルモデリング

テーブルスキーマ

キーと値のシリアル化

バイナリコンパレータを使用したキーの順序付け

外部コンパレータによるキーの順序付け

値のシリアル化

レコードの追加と更新

読書記録

範囲クエリ

4.3. テーブル間の関係のモデル化

インデックステーブル

テーブル間の関係の構成

結論

コメントを追加します 返信をキャンセル

3.1. クジラその１。メモリマップされたファイル

3.3. クジラその３。コピーオンライト

4. Key-Value API に基づくデータスキーマの設計

コメントを追加します返信をキャンセル