2019 年秋天，Mail.ru Cloud iOS 團隊發生了期待已久的事件。 用於持久存儲應用程序狀態的主數據庫對於移動世界來說已經變得非常奇特了 閃電內存映射數據庫 （LMDB）。 下切，請您注意其分四部分的詳細評述。 首先，讓我們談談做出這樣一個非平凡而艱難的選擇的原因。 然後讓我們繼續考慮 LMDB 體系結構核心的三個鯨魚：內存映射文件、B+ 樹、用於實現事務和多版本控制的寫時復制方法。 最後，甜點 - 實用部分。 在其中，我們將研究如何在低級鍵值 API 之上設計和實現具有多個表（包括索引表）的基本模式。

Содержание

1. 實施動機
2. 定位LMDB
3. 三頭鯨LMDB
   3.1. 鯨魚 #1。 內存映射文件
   3.2. 鯨魚 #2。 B+樹
   3.3. 鯨魚 #3。 寫時復制
4. 在鍵值 API 之上設計數據模式
   4.1. 基本抽象
   4.2. 表格建模
   4.3. 表之間的建模關係

1.實施動機

每年一次，在 2015 年，我們負責衡量一個指標，即我們的應用程序界面滯後的頻率。 我們不只是這樣做。 我們越來越多地抱怨有時應用程序會停止響應用戶操作：按鈕未按下、列表不滾動等。 關於測量力學 告訴 在 AvitoTech 上，所以這裡我只給出數字的順序。

測量結果對我們來說成了冷水澡。 事實證明，凍結引起的問題比其他任何問題都多。 如果在意識到這一事實之前，質量的主要技術指標是無碰撞的，那麼在關注之後 轉移 無冷凍。

建成後 凍結的儀表板 並且花費了 定量的 и 質量 分析它們的原因，主要的敵人變得清晰了——在應用程序的主線程中執行繁重的業務邏輯。 對這種恥辱的自然反應是強烈希望將其推入工作流程。 為了系統地解決這個問題，我們求助於基於輕量級參與者的多線程架構。 我將她的改編獻給了 iOS 世界 兩個線程 在集體推特和 關於哈布雷的文章. 作為當前故事的一部分，我想強調影響數據庫選擇的決策方面。

系統組織的參與者模型假設多線程成為它的第二個本質。 其中的模型對象喜歡跨越線程邊界。 他們不是有時在某些地方這樣做，而是幾乎無處不在。

數據庫是所呈現圖表中的基石組件之一。 它的主要任務是實現一個宏模式 共享數據庫. 如果在企業世界中它用於組織服務之間的數據同步，那麼在 actor 架構的情況下，線程之間的數據。 因此，我們需要這樣一個數據庫，在多線程環境中使用它不會造成哪怕是最小的困難。 特別是，這意味著從它派生的對象必須至少是線程安全的，理想情況下根本不可變。 如您所知，後者可以從多個線程同時使用，而無需求助於任何類型的鎖，這對性能有好處。

影響數據庫選擇的第二個重要因素是我們的雲 API。 它的靈感來自 git 同步方法。 像他一樣我們的目標 離線優先API，這看起來非常適合雲客戶端。 假設他們只會一次抽出雲的完整狀態，然後在絕大多數情況下同步將通過滾動更改發生。 las，這種可能性仍然只存在於理論領域，而在實踐中，客戶還沒有學會如何使用補丁。 這其中有很多客觀原因，為了不耽誤介紹，我們先不加括號。 現在更有趣的是關於當 API 說“A”而它的消費者沒有說“B”時會發生什麼的課程的指導性結果。

所以，如果你想像 git，它在執行拉命令時，不是將補丁應用到本地快照，而是將其完整狀態與完整服務器狀態進行比較，那麼你將對如何同步有一個相當準確的想法發生在雲客戶端。 很容易猜到，為了實現它，有必要在內存中分配兩棵 DOM 樹，其中包含有關所有服務器和本地文件的元信息。 事實證明，如果一個用戶在雲端存儲了 500 萬個文件，那麼要同步它，就需要重新創建和銷毀兩棵具有 1 萬個節點的樹。 但是每個節點都是一個包含子對像圖的聚合。 有鑑於此，分析結果是意料之中的。 事實證明，即使不考慮合併算法，創建然後銷毀大量小對象的過程也花費了相當多的錢。基本同步操作包含在大量對像中這一事實使情況更加惡化用戶腳本。 因此，我們確定了選擇數據庫的第二個重要標準——無需動態分配對象即可實現 CRUD 操作的能力。

其他要求更為傳統，其完整列表如下。

1. 線程安全。
2. 多重處理。 由希望使用同一個數據庫實例不僅在線程之間同步狀態，而且在主應用程序和 iOS 擴展之間同步狀態的願望所決定。
3. 將存儲的實體表示為非可變對象的能力。
4. CRUD 操作中缺少動態分配。
5. 基本屬性的交易支持 ACID關鍵詞：原子性、一致性、隔離性和可靠性。
6. 加快處理最受歡迎的案例。

有了這組需求，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 作為他們項目的基礎非常不滿。 遠離簡陋的圖書館 樹, Howard Chu 創造了我們這個時代最流行的替代品之一。 他將他非常酷的報告獻給了這個故事，以及 LMDB 的內部結構 “閃電內存映射數據庫”. 列昂尼德·尤里耶夫（又名 伊萊奧) 來自 Positive Technologies 在 Highload 2015 上的演講 “LMDB 引擎是一個特殊的冠軍”. 在其中，他在實現 ReOpenLDAP 的類似任務的背景下談到了 LMDB，而 LevelDB 已經受到了比較批評。 作為實施的結果，Positive Technologies 甚至得到了一個積極開發的分支 MDBX 具有非常美味的功能、優化和 bug修復.

LMDB 也經常用作原樣存儲。 例如，Mozilla Firefox 瀏覽器 選擇了 它滿足多種需求，並且從版本 9 開始，Xcode 首選 它的 SQLite 用於存儲索引。

該引擎還流行於移動開發領域。 它的使用痕跡可以 發現 在 Telegram 的 iOS 客戶端中。 LinkedIn 更進一步，選擇 LMDB 作為其自主研發的數據緩存框架 Rocket Data 的默認存儲。 告訴 在 2016 年的一篇文章中。

LMDB正在BerkeleyDB轉型後在甲骨文的控制下留下的小眾市場中，成功地在陽光下爭得一席之地。 該庫因其速度和可靠性而廣受喜愛，甚至與同類庫相比也是如此。 如您所知，天下沒有免費的午餐，我想強調在 LMDB 和 SQLite 之間進行選擇時您將不得不面對的權衡。 上圖清楚地展示瞭如何實現提高的速度。 首先，我們不為磁盤存儲之上的額外抽象層付費。 當然，在一個好的架構中，你還是離不開它們，應用代碼中也難免會出現它們，只是它們會薄很多。 它們不會具有特定應用程序不需要的功能，例如，支持 SQL 語言的查詢。 其次，可以優化地實現應用程序操作到磁盤存儲請求的映射。 如果 SQLite 在我的工作中 來自普通應用程序的平均需求，那麼作為應用程序開發人員的您很清楚主要的負載場景。 為了獲得更高效的解決方案，您將不得不為初始解決方案的開發及其後續支持支付更高的價格。

3.三頭鯨LMDB

鳥瞰了 LMDB 之後，是時候深入了解一下了。 接下來的三個部分將專門分析存儲架構所依賴的主要鯨魚：

1. 內存映射文件作為一種使用磁盤和同步內部數據結構的機制。
2. B+樹作為一種存儲數據的組織結構。
3. 寫時復製作為一種提供 ACID 事務屬性和多版本控制的方法。

3.1. 鯨魚 #1。 內存映射文件

內存映射文件是一個非常重要的架構元素，它們甚至出現在存儲庫的名稱中。 緩存和同步訪問存儲信息的問題完全取決於操作系統。 LMDB 本身不包含任何緩存。 這是作者的一個有意識的決定，因為直接從映射文件讀取數據可以讓您在引擎的實現中走捷徑。 以下是其中一些遠非完整的列表。

1. 當從多個進程使用數據時，維護存儲中數據的一致性成為操作系統的責任。 在下一節中，將詳細討論此機制並附上圖片。
2. 沒有緩存完全減輕了 LMDB 與動態分配相關的開銷。 在實踐中讀取數據就是將指針設置為虛擬內存中的正確地址，僅此而已。 聽起來很玄幻，但是在repository源碼中，所有的calloc調用都集中在repository配置函數中。
3. 沒有緩存也意味著沒有與同步相關聯的鎖來訪問它們。 可以同時存在任意數量的讀取器在訪問數據的過程中不會遇到單個互斥鎖。 正因為如此，讀取速度在CPU數量方面具有理想的線性可擴展性。 在 LMDB 中，只有修改操作是同步的。 一次只能有一個作家。
4. 最少的緩存和同步邏輯可以避免代碼出現與在多線程環境中工作相關的極其複雜的錯誤類型。 Usenix OSDI 2014 會議上有兩個有趣的數據庫研究： “並非所有文件系統都是生來平等的：關於製作崩潰一致應用程序的複雜性” и 為了樂趣和利潤而折磨數據庫. 從他們那裡，您可以獲得有關 LMDB 前所未有的可靠性以及事務的 ACID 屬性幾乎完美實現的信息，這在同一個 SQLite 中超過了它。
5. LMDB 的極簡主義允許其代碼的機器表示完全放置在處理器的 L1 緩存中，並具有由此產生的速度特性。

不幸的是，在 iOS 中，內存映射文件並不像我們希望的那樣美好。 要更有意識地談論與它們相關的缺點，有必要回顧一下在操作系統中實現這種機制的一般原則。

有關內存映射文件的一般信息

對於每個可執行應用程序，操作系統都將一個稱為進程的實體關聯起來。 每個進程都分配了一個連續的地址範圍，其中放置了它需要工作的所有內容。 最低地址包含帶有代碼和硬編碼數據和資源的部分。 接下來是向上增長的動態地址空間塊，我們稱之為堆。 它包含程序運行期間出現的實體的地址。 最上面是應用程序棧使用的內存區域。 它要么增長要么收縮，換句話說，它的大小也具有動態性。 為了棧和堆不互相壓入和乾擾，它們被分隔在地址空間的不同端，頂部和底部的兩個動態部分之間有一個空洞。 操作系統使用中間部分的地址來關聯各種實體的進程。 特別是，它可以將一組特定的連續地址映射到磁盤上的一個文件。 這樣的文件稱為內存映射文件。

分配給進程的地址空間是巨大的。 從理論上講，地址的數量僅受指針大小的限制，而指針的大小由系統的位數決定。 如果物理內存以 1 合 1 的方式分配給它，那麼第一個進程將吞噬整個 RAM，並且不存在任何多任務處理的問題。

然而，我們從經驗中知道，現代操作系統可以同時運行任意數量的進程。 這是可能的，因為它們僅在紙面上為進程分配了大量內存，但實際上它們僅將此時此地需要的那部分加載到主物理內存中。 因此，與進程關聯的內存稱為虛擬內存。

操作系統將虛擬內存和物理內存組織成一定大小的頁面。 一旦需要某個虛擬內存頁面，操作系統就會將其加載到物理內存中，並在一個特殊的表中記錄它們之間的對應關係。 如果沒有空閒插槽，則將先前加載的頁面之一複製到磁盤，並由請求的頁面取代它。 我們稍後將返回的這個過程稱為交換。 下圖說明了所描述的過程。 在其上，地址為 0 的頁面 A 被加載並放置在地址為 4 的主內存頁面上。這一事實反映在單元格編號 0 的對應表中。

對於內存映射文件，情況完全相同。 從邏輯上講，它們應該是連續且完整地放置在虛擬地址空間中的。 但是，它們只能按需逐頁進入物理內存。 此類頁面的修改與磁盤上的文件同步。 因此，您可以執行文件 I/O，只需使用內存中的字節 - 所有更改都會由操作系統內核自動傳輸到原始文件。

下圖演示了 LMDB 在使用來自不同進程的數據庫時如何同步其狀態。 通過將不同進程的虛擬內存映射到同一個文件，我們實際上迫使操作系統將它們的地址空間的某些塊相互傳遞同步，這就是 LMDB 的樣子。

一個重要的細微差別是LMDB默認通過write系統調用機制修改數據文件，文件本身以只讀模式顯示。 這種方法有兩個重要的含義。

第一個結果是所有操作系統共有的。 其本質是增加保護，防止錯誤代碼無意中損壞數據庫。 如您所知，進程的可執行指令可以從其地址空間中的任何位置自由訪問數據。 同時，我們剛才還記得，以讀寫方式顯示一個文件，意味著任何指令也可以對其進行附加修改。 如果她錯誤地這樣做，例如，嘗試實際覆蓋一個不存在的索引處的數組元素，那麼她可能會意外更改映射到該地址的文件，這將導致數據庫損壞。 如果文件以只讀模式顯示，則嘗試更改與其對應的地址空間將導致程序崩潰並發出信號 SIGSEGV，文件將保持不變。

第二個結果已經特定於 iOS。 作者和任何其他來源都沒有明確提及它，但如果沒有它，LMDB 將不適合在這個移動操作系統上運行。 下一節專門討論它。

iOS 中內存映射文件的細節

2018年WWDC上有精彩報導 iOS 內存深入探究. 它表明在 iOS 中，位於物理內存中的所有頁面都屬於 3 種類型之一：臟的、壓縮的和乾淨的。

乾淨內存是可以安全地換出物理內存的頁面集合。 它們包含的數據可以根據需要從其原始來源重新加載。 只讀內存映射文件屬於此類。 iOS 不怕隨時從內存中卸載映射到文件的頁面，因為它們保證與磁盤上的文件同步。

所有修改過的頁面都會進入臟內存，無論它們最初位於何處。 特別是，通過寫入與其關聯的虛擬內存而修改的內存映射文件也將按這種方式分類。 用標誌打開 LMDB MDB_WRITEMAP，修改之後，大家可以自己看看。

一旦應用程序開始佔用過多的物理內存，iOS 就會壓縮其臟頁。 臟頁和壓縮頁佔用的內存集合就是應用程序所謂的內存佔用。 當達到一定的閾值時，OOM killer系統守護進程追上來，強行終止。 與桌面操作系統相比，這是 iOS 的特殊性。 相比之下，iOS 並沒有提供通過將頁面從物理內存交換到磁盤來降低內存佔用，原因只能猜測。 也許密集地將頁面移動到磁盤和返回的過程對於移動設備來說太耗能了，或者 iOS 節省了在 SSD 驅動器上重寫單元格的資源，或者也許設計者對系統的整體性能不滿意，一切都在不斷交換。 不管怎樣，事實依然如此。

前面已經提到的好消息是 LMDB 默認不使用 mmap 機制來更新文件。 因此，渲染數據被 iOS 歸類為乾淨內存，不會影響內存佔用。 這可以使用名為 VM Tracker 的 Xcode 工具進行驗證。 下面的屏幕截圖顯示了 iOS Cloud 應用程序在運行期間的虛擬內存狀態。 一開始，裡面初始化了2個LMDB實例。 第一個被允許將其文件映射到 1GiB 的虛擬內存，第二個 - 512MiB。 儘管這兩個存儲都佔用一定數量的常駐內存，但它們都不會影響臟大小。

現在是壞消息的時候了。 由於 64 位桌面操作系統中的交換機制，每個進程可以佔用與硬盤上的可用空間允許其潛在交換一樣多的虛擬地址空間。 在 iOS 中用壓縮代替交換大大降低了理論上的最大值。 現在，所有活動進程都必須適合主（讀取 RAM）內存，所有不適合的進程都將被強制終止。 如上所述 報告所以 官方文檔. 因此，iOS 嚴格限制了可通過 mmap 分配的內存量。 這裡 這裡 您可以使用此系統調用查看可在不同設備上分配的內存量的經驗限制。 在最現代的智能手機型號上，iOS 增加了 2 GB，在 iPad 的頂級版本上增加了 4 GB。當然，在實踐中，你必須關注最年輕的受支持設備型號，那裡的一切都很糟糕。 更糟糕的是，在 VM Tracker 中查看應用程序的內存狀態，您會發現 LMDB 遠非唯一聲稱內存映射內存的。 好的塊會被系統分配器、資源文件、圖像框架和其他較小的捕食者吃掉。

根據云中的實驗結果，我們得出以下折衷值 LMDB 分配的內存：384 位設備為 32 兆字節，768 位設備為 64 兆字節。 此卷用完後，任何修改操作開始以代碼完成 MDB_MAP_FULL. 我們在監控中觀察到此類錯誤，但在現階段它們足夠小，可以忽略不計。

存儲消耗過多內存的一個不明顯的原因可能是長期事務。 要了解這兩種現象之間的關係，將有助於我們考慮剩餘的兩條 LMDB 鯨魚。

3.2. 鯨魚 #2。 B+樹

要在鍵值存儲之上模擬表，其 API 中必須存在以下操作：

1. 插入新元素。
2. 搜索具有給定鍵的元素。
3. 刪除一個元素。
4. 按排序順序迭代關鍵間隔。

可以輕鬆實現所有四種操作的最簡單的數據結構是二叉搜索樹。 它的每個節點都是一個鍵，將子鍵的整個子集劃分為兩個子樹。 左邊是比父級小的，右邊是比父級大的。 獲得一組有序的鍵是通過一種經典的樹遍歷實現的。

二叉樹有兩個基本缺點，使它們無法作為有效的磁盤數據結構。 首先，它們的平衡程度是不可預測的。 獲得樹的風險很大，其中不同分支的高度可能有很大差異，與預期相比，這大大惡化了搜索的算法複雜性。 其次，節點之間大量的交叉鏈接剝奪了二叉樹在內存中的局部性。關閉的節點（就它們之間的鏈接而言）可以位於虛擬內存中完全不同的頁面上。 因此，即使是對樹中幾個相鄰節點的簡單遍歷，也可能需要訪問相當數量的頁面。 即使當我們談論二叉樹作為內存中數據結構的有效性時，這也是一個問題，因為在處理器緩存中不斷旋轉頁面並不便宜。 當談到頻繁從磁盤中提取與節點相關的頁面時，事情變得非常糟糕。 可悲的。

B 樹是二叉樹的一種演變，解決了上一段中確定的問題。 首先，它們是自我平衡的。 其次，他們的每個節點不是將子鍵集合拆分成2個，而是拆分成M個有序的子集，M的數目可以很大，在幾百甚至幾千的數量級。

從而：

1. 每個節點都有大量已經排序的鍵，樹很低。
2. 這棵樹在內存中具有局部性，因為值接近的鍵自然地位於一個節點或相鄰節點上。
3. 在搜索操作期間降低樹時減少中轉節點的數量。
4. 減少為範圍查詢讀取的目標節點數量，因為它們中的每一個都已經包含大量有序鍵。

LMDB 使用稱為 B+ 樹的 B 樹變體來存儲數據。 上圖顯示了它包含的三種類型的節點：

1. 頂部是根。 它具體化了存儲庫中數據庫的概念。 在單個 LMDB 實例中，您可以創建共享映射虛擬地址空間的多個數據庫。 他們每個人都從自己的根開始。
2. 最低層是樹葉（leaf）。 只有它們包含存儲在數據庫中的鍵值對。 順便說一下，這就是 B+ 樹的特性。 如果一個普通的 B-tree 在所有級別的節點存儲值部分，那麼 B+-variation 僅在最低的一個。 解決了這個問題後，接下來我們將把 LMDB 中使用的樹的子類型簡稱為 B 樹。
3. 在根和葉之間，有 0 個或多個帶有導航（分支）節點的技術級別。 他們的任務是在葉子之間劃分已排序的鍵集。

在物理上，節點是預定長度的內存塊。 它們的大小是操作系統中內存頁面大小的倍數，我們在上面談到過。 節點結構如下圖所示。 標頭包含元信息，其中最明顯的是校驗和。 接下來是有關偏移量的信息，其中包含數據的單元格位於其中。 數據的角色可以是鍵，如果我們談論的是導航節點，或者在葉子的情況下是整個鍵值對。你可以在工作中閱讀更多關於頁面結構的信息 《高性能鍵值存儲的評估》.

處理完頁面節點的內部內容後，我們將進一步以以下形式簡化表示 LMDB B 樹。

具有節點的頁面按順序排列在磁盤上。 編號較大的頁面位於文件末尾。 所謂的元頁面（meta page）包含了關於偏移量的信息，可以用來找到所有樹的根。 當一個文件被打開時，LMDB 會從末尾到開頭逐頁掃描文件以搜索有效的元頁面，並通過它找到現有的數據庫。

現在，了解了數據組織的邏輯和物理結構，我們可以繼續考慮 LMDB 的第三隻鯨魚。 正是在它的幫助下，所有存儲修改都以事務方式發生並且彼此隔離，從而使數據庫作為一個整體也具有多版本屬性。

3.3. 鯨魚 #3。 寫時復制

一些 B 樹操作涉及對其節點進行一系列更改。 一個示例是向已達到其最大容量的節點添加新密鑰。 在這種情況下，首先，有必要將節點一分為二，其次，在其父節點中添加到新分離出的子節點的鏈接。 此過程可能非常危險。 如果由於某種原因（崩潰、斷電等）僅發生了系列中的一部分更改，則樹將保持不一致狀態。

使數據庫容錯的一種傳統解決方案是在 B 樹旁邊添加一個額外的基於磁盤的數據結構，即事務日誌，也稱為預寫日誌 (WAL)。 它是一個文件，在文件的末尾，嚴格地在 B 樹本身的修改之前，寫入了預期的操作。 因此，如果在自診斷過程中檢測到數據損壞，數據庫會查詢日誌以進行自我清理。

LMDB 選擇了一種不同的方法作為其容錯機制，稱為寫時復制。 它的本質是，它不是更新現有頁面上的數據，而是首先完全複製它，並在副本中進行所有修改。

此外，為了使更新的數據可用，有必要改變到與其相關的父節點中已變為最新的節點的鏈接。 由於這個也需要修改，所以也預先拷貝過來。 該過程一直遞歸地繼續到根。 元頁面上的數據是最後更改的。

如果進程在更新過程中突然崩潰，那麼要么不會創建新的元頁面，要么直到最後才將其寫入磁盤，並且其校驗和將不正確。 在這兩種情況中的任何一種情況下，新頁面都將無法訪問，而舊頁面不會受到影響。 這消除了 LMDB 預寫日誌以保持數據一致性的需要。 事實上，磁盤上的數據存儲結構，如上所述，同時發揮其功能。 沒有顯式事務日誌是 LMDB 的特點之一，它提供了高數據讀取速度。

生成的構造稱為僅附加 B 樹，自然提供事務隔離和多版本控制。 在 LMDB 中，每個打開的事務都有一個與之關聯的最新樹根。 只要事務未完成，與之關聯的樹的頁面將永遠不會更改或重新用於新版本的數據。因此，您可以根據需要使用與當時相關的數據集工作多久事務打開的時間，即使此時存儲繼續被主動更新。 這是多版本化的本質，使 LMDB 成為我們心愛的人的理想數據源 UICollectionView. 開啟交易後，你不需要增加應用程序的內存佔用，匆忙將當前數據抽出到內存中的某個結構中，生怕什麼都沒有。 此功能將 LMDB 與相同的 SQLite 區分開來，後者不能誇耀這種完全隔離。 在後者打開了兩個事務，刪除了其中一個中的某條記錄，在剩下的第二個中無法再獲取相同的記錄。

硬幣的另一面是虛擬內存的消耗可能會顯著增加。 該幻燈片顯示瞭如果數據庫結構同時被修改，同時有 3 個打開的讀取事務查看不同版本的數據庫，則該數據庫結構將是什麼樣子。 由於 LMDB 無法重用與實際事務關聯的根可到達的節點，因此存儲別無選擇，只能在內存中分配另一個四分之一根，並再次將修改後的頁面克隆到其下。

在這裡回顧內存映射文件部分並不是多餘的。 虛擬內存的額外消耗似乎不會讓我們太在意，因為它不會增加應用程序的內存佔用量。 但同時，也有人指出iOS在分配上非常吝嗇，我們不能站在主人的肩上在服務器或桌面上提供一個1TB的LMDB區域而不考慮這個特性。 如果可能，您應該盡量縮短事務的生命週期。

4. 在鍵值 API 之上設計數據模式

讓我們通過查看 LMDB 提供的基本抽象來開始解析 API：環境和數據庫、鍵和值、事務和游標。

關於代碼清單的註釋

LMDB 公共 API 中的所有函數都以錯誤代碼的形式返回它們的工作結果，但在所有後續清單中，為了簡潔起見，省略了它的檢查。在實踐中，我們使用自己的代碼與存儲庫進行交互。 叉 C++ 包裝器 LMDBXX，其中錯誤具體化為 C++ 異常。

作為將 LMDB 連接到 iOS 或 macOS 項目的最快方式，我提供了我的 CocoaPod POSLM數據庫.

4.1. 基本抽象

環境

結構 MDB_env is 是 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 Cloud 應用程序中，我們僅更改了兩個參數的默認值。

第一個是存儲文件映射到的虛擬地址空間的大小。 不幸的是，即使在同一台設備上，每次運行的具體值也會有很大差異。 考慮到 iOS 的這個特性，我們動態選擇最大存儲量。 從某個值開始，依次減半，直到函數 mdb_env_open 不會返回除以下以外的結果 ENOMEM. 理論上，有一種相反的方式——首先為引擎分配最少的內存，然後，當接收到錯誤時 MDB_MAP_FULL, 增加它。 然而，它更棘手。 原因是使用函數重新映射內存的過程 mdb_env_set_map_size 使先前從引擎接收到的所有實體（游標、事務、鍵和值）無效。 在代碼中考慮這種事件的轉變將導致其嚴重的複雜化。 儘管如此，如果虛擬內存對您來說非常重要，那麼這可能是查看已經走得很遠的分叉的原因。 MDBX，其中聲明的功能中有“自動實時數據庫大小調整”。

第二個參數，其默認值不適合我們，調節確保線程安全的機制。 不幸的是，至少在 iOS 10 中，線程本地存儲支持存在問題。 出於這個原因，在上面的例子中，存儲庫是用標誌打開的 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;​​

商店使用比較器按升序對鍵進行排序。 如果您不將其替換為您自己的，則將使用默認的，按字典順序逐字節排序。

交易

交易設備在詳細描述 上一章，所以在這裡我將用簡短的一行重複它們的主要屬性：

1. 支持所有基本屬性 ACID關鍵詞：原子性、一致性、隔離性和可靠性。 我不禁注意到，就 macOS 和 iOS 的持久性而言，MDBX 中修復了一個錯誤。 你可以在他們的網站上閱讀更多 自述.
2. 多線程的方法由“單寫入器/多讀取器”方案描述。 作者互相屏蔽，但不屏蔽讀者。 讀者不會阻止作者或彼此。
3. 支持嵌套事務。
4. 多版本支持。

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 雲應用程序的這樣一個功能為例，即從系統媒體庫自動加載內容。 通過良好的連接，客戶端可以每秒向服務器添加幾張照片。 如果您在每次下載後更新 UICollectionView 對於用戶雲中的媒體內容，在此過程中您可以忘記 60 fps 和平滑滾動。 為了防止頻繁的屏幕更新，您需要以某種方式限制基礎中的數據更改率 UICollectionViewDataSource.

如果數據庫不支持多版本並且只允許您使用當前當前狀態，那麼要創建時間穩定的數據快照，您需要將其複製到某個內存數據結構或臨時表中。 這些方法中的任何一種都非常昂貴。 在內存存儲的情況下，我們得到了存儲構造對象引起的內存成本和與冗餘 ORM 轉換相關的時間成本。 至於臨時表，這是一種更昂貴的樂趣，只有在非平凡的情況下才有意義。

多版本 LMDB 以非常優雅的方式解決了維護穩定數據源的問題。 只需打開一個事務就足夠了，瞧 - 在我們完成它之前，數據集保證是固定的。 其更新速率的邏輯現在完全掌握在表示層手中，沒有大量資源的開銷。

光標

游標提供了一種通過遍歷 B 樹對鍵值對進行有序迭代的機制。 沒有它們，就不可能有效地對數據庫中的表進行建模，我們現在將轉向它。

4.2. 表格建模

鍵排序屬性允許您構建頂級抽象，例如在基本抽象之上的表格。 讓我們以雲客戶端的主表為例來考慮這個過程，其中緩存了有關用戶的所有文件和文件夾的信息。

表模式

應該銳化具有文件夾樹的表結構的常見場景之一是選擇位於給定目錄內的所有元素。這種高效查詢的良好數據組織模型是 鄰接表. 要在鍵值存儲之上實現它，有必要對文件和文件夾的鍵進行排序，使它們根據屬於父目錄進行分組。 此外，為了以 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 對於示例中的雙字節數字）。

如您所知，在編程中表示字符串的格式是一個整體 история. 如果字符串的語義以及在內存中用來表示它們的編碼表明每個字符可能有多個字節，那麼最好立即放棄使用默認比較器的想法。

要記住的第二件事是 對齊原則 結構字段編譯器。 因為它們，在字段之間的內存中可以形成具有垃圾值的字節，這當然會破壞字節排序。 要消除垃圾，您必須按照嚴格定義的順序聲明字段，牢記對齊規則，或者使用結構聲明中的屬性 packed.

通過外部比較器進行按鍵排序

密鑰比較邏輯對於二進制比較器來說可能過於復雜。 眾多原因之一是結構內部存在技術領域。 我將在我們已經熟悉的目錄元素的鍵示例中說明它們的出現。

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

儘管它很簡單，但在絕大多數情況下它會消耗太多內存。 標題緩衝區為 256 字節，但平均文件和文件夾名稱很少超過 20-30 個字符。

優化記錄大小的標準技術之一是修剪它以適合其實際大小。 其本質是將所有可變長度字段的內容存儲在結構末尾的緩衝區中，並將它們的長度存儲在單獨的變量中。按照這種方法，關鍵 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)。 偽代碼為 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 // ...
}​

只要數據庫中的所有鍵都是同一類型，無條件地將它們的字節表示形式轉換為鍵的應用程序結構的類型是合法的。 這裡有一個細微差別，但將在“閱讀記錄”小節中稍微討論一下。

值序列化

使用存儲記錄的鍵，LMDB 工作非常密集。 它們在任何應用程序操作的框架內相互比較，整個解決方案的性能取決於比較器的速度。 在理想情況下，默認的二進制比較器應該足以比較鍵，但如果你真的必須使用自己的，那麼反序列化鍵的過程應該盡可能快。

數據庫對記錄（值）的值部分不是特別感興趣。 它從字節表示到對象的轉換僅在應用程序代碼已經需要時才會發生，例如，將其顯示在屏幕上。 由於這種情況很少發生，所以對這個過程的速度要求不是那麼嚴格，而且在它的實現中我們可以更加自由地關注便利性。例如，要序列化關於尚未下載的文件的元數據，我們使用 NSKeyedArchiver.

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

但是，有時性能確實很重要。 例如，在保存有關用戶雲文件結構的元信息時，我們使用相同的對象內存轉儲。 生成序列化表示的任務的亮點是目錄的元素由類層次結構建模。

它在C語言中的實現是將繼承體的具體字段取出到單獨的結構體中，通過聯合類型的字段指定它們與基體的聯繫。 聯合的實際內容通過類型技術屬性指定。

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，幾乎免費提供非常高的數據讀取速度。 鑑於該方法的所有優點，有必要記住與之相關的幾個功能。

1. 對於只讀事務，指向值結構的指針保證僅在事務關閉之前保持有效。 如前所述，由於寫時復制原則，對象所在的 B 樹頁保持不變，只要至少有一個事務引用它們。 同時，一旦與它們關聯的最後一個事務完成，頁面就可以重新用於新數據。 如果對像有必要在創建它們的事務中存活下來，那麼它們仍然必須被複製。
2. 對於讀寫事務，指向結果結構值的指針僅在第一個修改過程（寫入或刪除數據）之前有效。
3. 儘管結構 NodeValue 不是完整的，而是經過修剪的（請參閱“通過外部比較器排序鍵”小節），通過指針，您可以輕鬆訪問其字段。 最主要的是不要取消引用它！
4. 在任何情況下都不能通過接收到的指針修改結構。 所有更改必須僅通過方法進行 mdb_put. 然而，儘管如此，它還是行不通，因為這個結構所在的內存區域是以只讀模式映射的。
5. 將文件重新映射到進程的地址空間，例如，使用函數增加最大存儲大小 mdb_env_set_map_size 一般而言，使所有事務和相關實體完全無效，尤其是指向讀取對象的指針。

最後，另一個特徵是如此陰險，以致於其本質的披露不適合再多一點。 在關於 B 樹的章節中，我給出了它的頁面在內存中的組織結構圖。 由此可見，帶有序列化數據的緩衝區的起始地址可以是絕對任意的。 因此，指向它們的指針，在結構中獲得 MDB_val 並轉換為指向結構的指針通常是未對齊的。 同時，一些芯片的架構（在 iOS 中是 armv7）要求任何數據的地址是機器字大小的倍數，或者換句話說，是系統的位數（對於 armv7，這是 32 位）。 換句話說，像這樣的操作 *(int *foo)0x800002 在他們身上等同於逃跑並導致死刑 EXC_ARM_DA_ALIGN. 有兩種方法可以避免這種悲慘的命運。

第一個歸結為將數據初步複製到已知對齊的結構中。 例如，在自定義比較器上，這將反映如下。

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 上可以達到同樣的效果 達到 並使用 packed 屬性。 考慮到它也有助於優化結構佔用的空間，這種方法在我看來更可取，雖然 приводит 增加數據訪問操作的成本。

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

範圍查詢

為了遍歷一組記錄，LMDB 提供了游標抽象。 讓我們使用我們已經熟悉的包含用戶雲元數據的表示例來了解如何使用它。

作為顯示目錄中文件列表的一部分，您需要找到與其子文件和文件夾關聯的所有鍵。 在前面的小節中，我們對鍵進行了排序 NodeKey 以便它們首先按其父目錄 ID 排序。 因此，從技術上講，獲取文件夾內容的任務被簡化為將光標放在一組具有給定前綴的鍵的上邊界，然後迭代到下邊界。

您可以通過順序搜索找到“額頭上”的上限。 為此，將光標置於數據庫中整個鍵列表的開頭，然後遞增，直到具有父目錄標識符的鍵出現在其下方。 這種方法有兩個明顯的缺點：

1. 搜索的線性複雜性，儘管如您所知，在一般的樹中，特別是在 B 樹中，它可以在對數時間內完成。
2. 徒勞的是，所需頁面之前的所有頁面都從文件中提升到主內存，這是非常昂貴的。

幸運的是，LMDB API提供了一種有效的方法來初始定位游標。為此，您需要形成這樣一個鍵，其值肯定小於或等於位於區間上界的鍵. 比如對於上圖中的列表，我們可以做一個key，其中的字段 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. 表之間的建模關係

迄今為止，我們已經設法考慮了設計和使用單表數據庫的所有方面。 我們可以說一個表是由相同類型的鍵值對組成的一組排序記錄。 如果將鍵顯示為矩形，將其關聯的值顯示為框，則會得到數據庫的可視化圖表。

然而，在現實生活中，鮮血很少能過得去。 通常在數據庫中，首先，需要有多個表，其次，以不同於主鍵的順序在其中進行選擇。 最後一節專門討論它們的創建和互連問題。

索引表

雲應用程序有一個“圖庫”部分。 它顯示來自整個雲的媒體內容，按日期排序。 為了實現這種選擇的最佳實施，您需要在主表旁邊創建另一個具有新型鍵的表。 它們將包含一個包含文件創建日期的字段，該字段將作為主要排序標準。 因為新鍵引用與基礎表中的鍵相同的數據，所以它們被稱為索引鍵。 它們在下圖中以橙色突出顯示。

為了在同一數據庫中將不同表的鍵彼此分開，所有這些都添加了一個額外的技術字段tableId。 通過使其成為排序的最高優先級，我們將首先按表對鍵進行分組，並且已經在表內 - 根據我們自己的規則。

索引鍵引用與主鍵相同的數據。 通過將主鍵的值部分的副本與其相關聯來直接實現此屬性，從多個角度來看都不是最優的：

1. 從空間佔用的角度來看，元數據可以相當豐富。
2. 從性能的角度來看，因為在更新節點元數據時，您將不得不覆蓋兩個鍵。
3. 從代碼支持的角度來看，畢竟，如果我們忘記更新其中一個鍵的數據，我們會在存儲中出現數據不一致的微妙錯誤。

接下來，我們將考慮如何消除這些缺點。

表間關係的組織

該模式非常適合將索引表與主錶鍊接起來 “鍵值”. 顧名思義，索引記錄的值部分是主鍵值的副本。 這種方法消除了上面列出的與存儲主記錄的值部分的副本相關的所有缺點。 唯一的費用是要通過索引鍵獲取值，您需要對數據庫進行 2 次查詢，而不是一次。 示意性地，生成的數據庫模式如下所示。

組織表之間關係的另一種模式是 “冗餘密鑰”. 它的本質是向鍵添加額外的屬性，這些屬性不是用於排序，而是用於重新創建關聯的鍵。但是，在 Mail.ru Cloud 應用程序中有使用它的真實示例，但是，為了避免深入研究具體 iOS 框架的上下文，我會舉一個虛構的，但更容易理解的例子。

雲移動客戶端有一個頁面，顯示用戶與其他人共享的所有文件和文件夾。 由於此類文件相對較少，並且有很多與它們相關的公開信息（授予誰訪問權限，具有什麼權利等），因此用價值部分來負擔它是不合理的主表中的條目。 但是，如果您想離線顯示此類文件，那麼您仍然需要將其存儲在某個地方。 一個自然的解決方案是為它創建一個單獨的表。 在下圖中，它的鍵以“P”為前綴，“propname”佔位符可以替換為更具體的值“public info”。

為此創建新表的所有唯一元數據都被移動到記錄的值部分。 同時，我不想複製已經存儲在主表中的文件和文件夾的數據。 相反，冗餘數據以“節點 ID”和“時間戳”字段的形式添加到“P”鍵。 多虧了它們，你可以構建一個索引鍵，通過它你可以獲得主鍵，最後你可以通過它獲得節點的元數據。

結論

我們積極評價 LMDB 實施的結果。 在此之後，應用程序凍結的數量減少了 30%。

所做工作的結果在 iOS 團隊之外得到了回應。 目前，Android 應用程序中的一個主要“文件”部分也已切換到使用 LMDB，其他部分也在進行中。 實現了key-value存儲的C語言，對於C++語言初步實現圍繞它的應用程序跨平台綁定起到了很好的幫助。 為了將生成的 C++ 庫與 Objective-C 和 Kotlin 中的平台代碼無縫連接，使用了代碼生成器 金尼 來自 Dropbox，但那是另一回事了。

來源： www.habr.com