lmdb簡介
lmdb是openLDAP項目開發(fā)的嵌入式（作為一個庫嵌入到宿主程序）存儲引擎雄嚣。其主要特性有：
- 基于文件映射IO（mmap）
- 基于B+樹的key-value接口
- 基于MVCC（Multi Version Concurrent Control）的事務處理
- 類bdb（berkeley db）的api
實現(xiàn)
底層讀寫的實現(xiàn)
lmdb的基本思路是使用mmap訪問存儲，不管這個存儲實在內存上還是在持久存儲上。
lmdb的所有讀取操作都是通過mmap將要訪問的文件只讀地裝載到宿主進程的地址空間园欣，直接訪問相應的地址锭汛，這減少了硬盤昵慌、內核地址控件和用戶地址空間之間的拷貝秃臣，也簡化了平坦的“索引空間”上的實現(xiàn)瞻润，因為使用了read-only的mmap，規(guī)避了因為宿主程序錯誤將存儲結構寫壞的風險甜刻。IO的調度由操作系統(tǒng)的頁調度機制完成。
而寫操作正勒，則是通過write系統(tǒng)調用進行的得院，這主要是為了利用操作系統(tǒng)的文件系統(tǒng)一致性，避免在被訪問的地址上進行同步章贞。
基于MVCC的存儲引擎
我們在前面提及祥绞，lmdb上的讀取操作，直接讀取了mmap所裝載的內存地址，那么蜕径，如果所讀取的內容被修改了两踏，不是出現(xiàn)了不一致的結果嗎？事實是兜喻，lmdb上的所有內容都不會被修改梦染。
lmdb用MVCC處理并發(fā)讀寫訪問的問題。其要點在于：
- 每一個變更對應一個版本
- 變更發(fā)生的時候不修改原來的版本
- 讀者進入的時候會取得一個版本朴皆，它只讀取這個版本的內容
對于一個樹形數(shù)據(jù)結構帕识，當它的一個節(jié)點上發(fā)生變更的時候，就創(chuàng)建一個新的節(jié)點遂铡，在新的節(jié)點上容納這些變更肮疗，由于這個節(jié)點的父節(jié)點也要發(fā)生變更（從指向原來的節(jié)點變更為指向新的這個節(jié)點），那么重復上述過程扒接，即伪货，實際發(fā)生變更的節(jié)點通往根節(jié)點路徑上的所有節(jié)點都必須重新創(chuàng)建一份，當變更工作完成的時候钾怔，我們通過一個原子操作提交這個變更版本碱呼。大體是這樣一個過程：
如上圖所示，每個新的版本就會產生一個新的跟節(jié)點蒂教，按照上述處理巍举，最終的存儲中就會保留歷史上所有的版本，當然凝垛，所有版本中就包括了當前所有讀者所讀的版本懊悯，因此，變更不會對讀者產生任何影響梦皮，所以炭分，寫可以不被讀阻塞。
上面剑肯，我們討論了讀的情況捧毛，上述方法承諾給每一個讀一個一致的版本（就是它進入時所得到的那個版本），但沒有承諾給它一個最新的版本让网，我們考慮在一個事務中呀忧，依據(jù)一個值變更另一個值的情況，很顯然溃睹，當我們想要提交變更的時候而账，很可能我們進入時所得到的版本已經(jīng)不是最新的，也就是說因篇，在我們的進入和提交之間發(fā)生了另一個提交泞辐，這種情況下笔横，如果提交了變更就會發(fā)生不一致的狀況，譬如一個單調遞增的計數(shù)器咐吼，就因此可能“吃掉”多個遞增吹缔。為了解決這個問題，我們只要在提交時檢查我們進入的版本是否最新版本即可锯茄，這常诚崽粒可以通過一個CAS原子操作完成，如果這個操作失敗撇吞，就重新進入存儲俗冻，重做整個事務。這樣牍颈，讀也可以不被（可能的）寫阻塞迄薄。
按照上述描述，我們的存儲中保存了所有的歷史版本煮岁，這是否必要呢讥蔽？事實上，我們所以保存歷史版本画机，是因為有可能有讀者讀它冶伞，新的讀者總是讀到最新的版本，老的版本就沒有用了步氏，如果一個版本上沒有任何讀者（和寫者）响禽，那它就沒有必要存在了。我們可以依據(jù)上述原理實現(xiàn)舊版本的回收荚醒，不過lmdb做了一些改進：
- 一個基本的事實是芋类，新的讀者總是去讀最新的版本，因此界阁，保留所有版本的根節(jié)點是不必要的侯繁，我們只需要保存一個最新版本的根節(jié)點和一個用于提交更加新的變更的節(jié)點即可。
- 所有讀者進入的時候泡躯，都復制當前的根節(jié)點的一個snapshot（因為它隨后很可能被改變）
- 當一個變更被提交的時候贮竟，它清楚因為這個提交，哪些節(jié)點遲早會變成沒用的---所有因為這次變更發(fā)生過修改的節(jié)點较剃，都會在相應版本的讀者退出后變成無用的節(jié)點咕别，因此可以回收
- 因為上述理由，最新的版本可以收集所有需要被回收的節(jié)點和它們所屬的版本
- 維護一個讀者的slot写穴，可以從這里面查到最小的版本顷级，比這個版本小的版本所屬的可回收節(jié)點都可以進行回收
如上所述，我們現(xiàn)在只有兩個根節(jié)點确垫，所有變更最終都要修改這個根節(jié)點弓颈，這樣，所有的寫事實上要被序列化删掀。這并沒有降低性能翔冀，理由是這樣的，如我們上面所述的披泪，當兩個變更并發(fā)進行的時候纤子，確切的說，是進入同一個版本款票，并依據(jù)這個版本進行了某些變更控硼，然后要提交這些變更，兩者中必有一個事務必須重做艾少，因為在它的提交和進入之間有別的提交卡乾，這個結論可以推廣到多個并發(fā)的情況。也就是說缚够，變更事實上是序列化的幔妨，由于不同的變更之間沒有阻塞，MVCC的方案消耗了更多的計算資源（所有失敗的提交都要被重做）谍椅。因此误堡，lmdb用一把鎖序列化了所有的變更操作。
以上就是lmdb實現(xiàn)中大部分要點雏吭。
