原文地址：http://www.samecity.com/blog/Index.asp?SortID=12，

最近由于工作上的需求，需要用到leveldb，因此轉載此文章用于以后的查詢使用。

LevelDb日知錄之一：LevelDb 101

　　說起LevelDb也許您不清楚，但是如果作為IT工程師，不知道下面兩位大神級別的工程師，那您的領導估計會Hold不住了：Jeff Dean和Sanjay Ghemawat。這兩位是Google公司重量級的工程師，為數甚少的Google Fellow之二。

　　Jeff Dean其人：http://research.google.com/people/jeff/index.html，Google大規模分布式平臺Bigtable和MapReduce主要設計和實現者。

　　Sanjay Ghemawat其人：http://research.google.com/people/sanjay/index.html，Google大規模分布式平臺GFS，Bigtable和MapReduce主要設計和實現工程師。

　　LevelDb就是這兩位大神級別的工程師發起的開源項目，簡而言之，LevelDb是能夠處理十億級別規模Key-Value型數據持久性存儲的C++?程序庫。正像上面介紹的，這二位是Bigtable的設計和實現者，如果了解Bigtable的話，應該知道在這個影響深遠的分布式存儲系統中有兩個核心的部分：Master Server和Tablet Server。其中Master Server做一些管理數據的存儲以及分布式調度工作，實際的分布式數據存儲以及讀寫操作是由Tablet Server完成的，而LevelDb則可以理解為一個簡化版的Tablet Server。

　　LevelDb有如下一些特點：

　　　　首先，LevelDb是一個持久化存儲的KV系統，和Redis這種內存型的KV系統不同，LevelDb不會像Redis一樣狂吃內存，而是將大部分數據存儲到磁盤上。

　　　　其次，LevleDb在存儲數據時，是根據記錄的key值有序存儲的，就是說相鄰的key值在存儲文件中是依次順序存儲的，而應用可以自定義key大小比較函數，LevleDb會按照用戶定義的比較函數依序存儲這些記錄。

　　　　再次，像大多數KV系統一樣，LevelDb的操作接口很簡單，基本操作包括寫記錄，讀記錄以及刪除記錄。也支持針對多條操作的原子批量操作。

　　　　另外，LevelDb支持數據快照（snapshot）功能，使得讀取操作不受寫操作影響，可以在讀操作過程中始終看到一致的數據。

　　除此外，LevelDb還支持數據壓縮等操作，這對于減小存儲空間以及增快IO效率都有直接的幫助。

　　LevelDb性能非常突出，官方網站報道其隨機寫性能達到40萬條記錄每秒，而隨機讀性能達到6萬條記錄每秒。總體來說，LevelDb的寫操作要大大快于讀操作，而順序讀寫操作則大大快于隨機讀寫操作。至于為何是這樣，看了我們后續推出的LevelDb日知錄，估計您會了解其內在原因。

LevelDb日知錄之二：整體架構

??? ??LevelDb本質上是一套存儲系統以及在這套存儲系統上提供的一些操作接口。為了便于理解整個系統及其處理流程，我們可以從兩個不同的角度來看待LevleDb：靜態角度和動態角度。從靜態角度，可以假想整個系統正在運行過程中（不斷插入刪除讀取數據），此時我們給LevelDb照相，從照片可以看到之前系統的數據在內存和磁盤中是如何分布的，處于什么狀態等；從動態的角度，主要是了解系統是如何寫入一條記錄，讀出一條記錄，刪除一條記錄的，同時也包括除了這些接口操作外的內部操作比如compaction，系統運行時崩潰后如何恢復系統等等方面。

?????本節所講的整體架構主要從靜態角度來描述，之后接下來的幾節內容會詳述靜態結構涉及到的文件或者內存數據結構，LevelDb日知錄后半部分主要介紹動態視角下的LevelDb，就是說整個系統是怎么運轉起來的。

???? LevelDb作為存儲系統，數據記錄的存儲介質包括內存以及磁盤文件，如果像上面說的，當LevelDb運行了一段時間，此時我們給LevelDb進行透視拍照，那么您會看到如下一番景象：

圖1.1：LevelDb結構

????從圖中可以看出，構成LevelDb靜態結構的包括六個主要部分：內存中的MemTable和Immutable MemTable以及磁盤上的幾種主要文件：Current文件，Manifest文件，log文件以及SSTable文件。當然，LevelDb除了這六個主要部分還有一些輔助的文件，但是以上六個文件和數據結構是LevelDb的主體構成元素。

LevelDb的Log文件和Memtable與Bigtable論文中介紹的是一致的，當應用寫入一條Key:Value記錄的時候，LevelDb會先往log文件里寫入，成功后將記錄插進Memtable中，這樣基本就算完成了寫入操作，因為一次寫入操作只涉及一次磁盤順序寫和一次內存寫入，所以這是為何說LevelDb寫入速度極快的主要原因。

Log文件在系統中的作用主要是用于系統崩潰恢復而不丟失數據，假如沒有Log文件，因為寫入的記錄剛開始是保存在內存中的，此時如果系統崩潰，內存中的數據還沒有來得及Dump到磁盤，所以會丟失數據（Redis就存在這個問題）。為了避免這種情況，LevelDb在寫入內存前先將操作記錄到Log文件中，然后再記入內存中，這樣即使系統崩潰，也可以從Log文件中恢復內存中的Memtable，不會造成數據的丟失。

當Memtable插入的數據占用內存到了一個界限后，需要將內存的記錄導出到外存文件中，LevleDb會生成新的Log文件和Memtable，原先的Memtable就成為Immutable Memtable，顧名思義，就是說這個Memtable的內容是不可更改的，只能讀不能寫入或者刪除。新到來的數據被記入新的Log文件和Memtable，LevelDb后臺調度會將Immutable Memtable的數據導出到磁盤，形成一個新的SSTable文件。SSTable就是由內存中的數據不斷導出并進行Compaction操作后形成的，而且SSTable的所有文件是一種層級結構，第一層為Level 0，第二層為Level 1，依次類推，層級逐漸增高，這也是為何稱之為LevelDb的原因。

??? SSTable中的文件是Key有序的，就是說在文件中小key記錄排在大Key記錄之前，各個Level的SSTable都是如此，但是這里需要注意的一點是：Level 0的SSTable文件（后綴為.sst）和其它Level的文件相比有特殊性：這個層級內的.sst文件，兩個文件可能存在key重疊，比如有兩個level 0的sst文件，文件A和文件B，文件A的key范圍是：{bar, car}，文件B的Key范圍是{blue,samecity}，那么很可能兩個文件都存在key=”blood”的記錄。對于其它Level的SSTable文件來說，則不會出現同一層級內.sst文件的key重疊現象，就是說Level L中任意兩個.sst文件，那么可以保證它們的key值是不會重疊的。這點需要特別注意，后面您會看到很多操作的差異都是由于這個原因造成的。

??? SSTable中的某個文件屬于特定層級，而且其存儲的記錄是key有序的，那么必然有文件中的最小key和最大key，這是非常重要的信息，LevelDb應該記下這些信息。Manifest就是干這個的，它記載了SSTable各個文件的管理信息，比如屬于哪個Level，文件名稱叫啥，最小key和最大key各自是多少。下圖是Manifest所存儲內容的示意：

圖2.1：Manifest存儲示意圖

圖中只顯示了兩個文件（manifest會記載所有SSTable文件的這些信息），即Level 0的test.sst1和test.sst2文件，同時記載了這些文件各自對應的key范圍，比如test.sstt1的key范圍是“an”到?“banana”，而文件test.sst2的key范圍是“baby”到“samecity”，可以看出兩者的key范圍是有重疊的。

Current文件是干什么的呢？這個文件的內容只有一個信息，就是記載當前的manifest文件名。因為在LevleDb的運行過程中，隨著Compaction的進行，SSTable文件會發生變化，會有新的文件產生，老的文件被廢棄，Manifest也會跟著反映這種變化，此時往往會新生成Manifest文件來記載這種變化，而Current則用來指出哪個Manifest文件才是我們關心的那個Manifest文件。

以上介紹的內容就構成了LevelDb的整體靜態結構，在LevelDb日知錄接下來的內容中，我們會首先介紹重要文件或者內存數據的具體數據布局與結構。

LevelDb日知錄之三：log文件

?????上節內容講到log文件在LevelDb中的主要作用是系統故障恢復時，能夠保證不會丟失數據。因為在將記錄寫入內存的Memtable之前，會先寫入Log文件，這樣即使系統發生故障，Memtable中的數據沒有來得及Dump到磁盤的SSTable文件，LevelDB也可以根據log文件恢復內存的Memtable數據結構內容，不會造成系統丟失數據，在這點上LevelDb和Bigtable是一致的。

?????下面我們帶大家看看log文件的具體物理和邏輯布局是怎樣的，LevelDb對于一個log文件，會把它切割成以32K為單位的物理Block，每次讀取的單位以一個Block作為基本讀取單位，下圖展示的log文件由3個Block構成，所以從物理布局來講，一個log文件就是由連續的32K大小Block構成的。

圖3.1?log文件布局

? ??????在應用的視野里是看不到這些Block的，應用看到的是一系列的Key:Value對，在LevelDb內部，會將一個Key:Value對看做一條記錄的數據，另外在這個數據前增加一個記錄頭，用來記載一些管理信息，以方便內部處理，圖3.2顯示了一個記錄在LevelDb內部是如何表示的。

?

圖3.2?記錄結構

? ?????記錄頭包含三個字段，ChechSum是對“類型”和“數據”字段的校驗碼，為了避免處理不完整或者是被破壞的數據，當LevelDb讀取記錄數據時候會對數據進行校驗，如果發現和存儲的CheckSum相同，說明數據完整無破壞，可以繼續后續流程。“記錄長度”記載了數據的大小，“數據”則是上面講的Key:Value數值對，“類型”字段則指出了每條記錄的邏輯結構和log文件物理分塊結構之間的關系，具體而言，主要有以下四種類型：FULL/FIRST/MIDDLE/LAST。

????? ??如果記錄類型是FULL，代表了當前記錄內容完整地存儲在一個物理Block里，沒有被不同的物理Block切割開；如果記錄被相鄰的物理Block切割開，則類型會是其他三種類型中的一種。我們以圖3.1所示的例子來具體說明。

???????假設目前存在三條記錄，Record A，Record B和Record C，其中Record A大小為10K，Record B?大小為80K，Record C大小為12K，那么其在log文件中的邏輯布局會如圖3.1所示。Record A是圖中藍色區域所示，因為大小為10K<32K，能夠放在一個物理Block中，所以其類型為FULL；Record B?大小為80K，而Block 1因為放入了Record A，所以還剩下22K，不足以放下Record B，所以在Block 1的剩余部分放入Record B的開頭一部分，類型標識為FIRST，代表了是一個記錄的起始部分；Record B還有58K沒有存儲，這些只能依次放在后續的物理Block里面，因為Block 2大小只有32K，仍然放不下Record B的剩余部分，所以Block 2全部用來放Record B，且標識類型為MIDDLE，意思是這是Record B中間一段數據；Record B剩下的部分可以完全放在Block 3中，類型標識為LAST，代表了這是Record B的末尾數據；圖中黃色的Record C因為大小為12K，Block 3剩下的空間足以全部放下它，所以其類型標識為FULL。

?????從這個小例子可以看出邏輯記錄和物理Block之間的關系，LevelDb一次物理讀取為一個Block，然后根據類型情況拼接出邏輯記錄，供后續流程處理。

LevelDb日知錄之四：SSTable文件

?　　SSTable是Bigtable中至關重要的一塊，對于LevelDb來說也是如此，對LevelDb的SSTable實現細節的了解也有助于了解Bigtable中一些實現細節。

本節內容主要講述SSTable的靜態布局結構，我們曾在“LevelDb日知錄之二：整體架構”中說過，SSTable文件形成了不同Level的層級結構，至于這個層級結構是如何形成的我們放在后面Compaction一節細說。本節主要介紹SSTable某個文件的物理布局和邏輯布局結構，這對了解LevelDb的運行過程很有幫助。

　　LevelDb不同層級有很多SSTable文件（以后綴.sst為特征），所有.sst文件內部布局都是一樣的。上節介紹Log文件是物理分塊的，SSTable也一樣會將文件劃分為固定大小的物理存儲塊，但是兩者邏輯布局大不相同，根本原因是：Log文件中的記錄是Key無序的，即先后記錄的key大小沒有明確大小關系，而.sst文件內部則是根據記錄的Key由小到大排列的，從下面介紹的SSTable布局可以體會到Key有序是為何如此設計.sst文件結構的關鍵。

圖4.1 .sst文件的分塊結構

　　圖4.1展示了一個.sst文件的物理劃分結構，同Log文件一樣，也是劃分為固定大小的存儲塊，每個Block分為三個部分，紅色部分是數據存儲區，?藍色的Type區用于標識數據存儲區是否采用了數據壓縮算法（Snappy壓縮或者無壓縮兩種），CRC部分則是數據校驗碼，用于判別數據是否在生成和傳輸中出錯。

　　以上是.sst的物理布局，下面介紹.sst文件的邏輯布局，所謂邏輯布局，就是說盡管大家都是物理塊，但是每一塊存儲什么內容，內部又有什么結構等。圖4.2展示了.sst文件的內部邏輯解釋。

圖4.2?邏輯布局

　　從圖4.2可以看出，從大的方面，可以將.sst文件劃分為數據存儲區和數據管理區，數據存儲區存放實際的Key:Value數據，數據管理區則提供一些索引指針等管理數據，目的是更快速便捷的查找相應的記錄。兩個區域都是在上述的分塊基礎上的，就是說文件的前面若干塊實際存儲KV數據，后面數據管理區存儲管理數據。管理數據又分為四種不同類型：紫色的Meta Block，紅色的MetaBlock?索引和藍色的數據索引塊以及一個文件尾部塊。

　　LevelDb 1.2版對于Meta Block尚無實際使用，只是保留了一個接口，估計會在后續版本中加入內容，下面我們看看數據索引區和文件尾部Footer的內部結構。

圖4.3?數據索引

　　圖4.3是數據索引的內部結構示意圖。再次強調一下，Data Block內的KV記錄是按照Key由小到大排列的，數據索引區的每條記錄是對某個Data Block建立的索引信息，每條索引信息包含三個內容，以圖4.3所示的數據塊i的索引Index i來說：紅色部分的第一個字段記載大于等于數據塊i中最大的Key值的那個Key，第二個字段指出數據塊i在.sst文件中的起始位置，第三個字段指出Data Block i的大小（有時候是有數據壓縮的）。后面兩個字段好理解，是用于定位數據塊在文件中的位置的，第一個字段需要詳細解釋一下，在索引里保存的這個Key值未必一定是某條記錄的Key,以圖4.3的例子來說，假設數據塊i?的最小Key=“samecity”，最大Key=“the best”;數據塊i+1的最小Key=“the fox”,最大Key=“zoo”,那么對于數據塊i的索引Index i來說，其第一個字段記載大于等于數據塊i的最大Key(“the best”)同時要小于數據塊i+1的最小Key(“the fox”)，所以例子中Index i的第一個字段是：“the c”，這個是滿足要求的；而Index i+1的第一個字段則是“zoo”，即數據塊i+1的最大Key。

　　文件末尾Footer塊的內部結構見圖4.4，metaindex_handle指出了metaindex block的起始位置和大小；inex_handle指出了index Block的起始地址和大小；這兩個字段可以理解為索引的索引，是為了正確讀出索引值而設立的，后面跟著一個填充區和魔數。

圖4.4?Footer

　　上面主要介紹的是數據管理區的內部結構，下面我們看看數據區的一個Block的數據部分內部是如何布局的（圖4.1中的紅色部分），圖4.5是其內部布局示意圖。

圖4.5?數據Block內部結構

　　從圖中可以看出，其內部也分為兩個部分，前面是一個個KV記錄，其順序是根據Key值由小到大排列的，在Block尾部則是一些“重啟點”（Restart Point）,其實是一些指針，指出Block內容中的一些記錄位置。

　　“重啟點”是干什么的呢？我們一再強調，Block內容里的KV記錄是按照Key大小有序的，這樣的話，相鄰的兩條記錄很可能Key部分存在重疊，比如key i=“the Car”，Key i+1=“the color”,那么兩者存在重疊部分“the c”，為了減少Key的存儲量，Key i+1可以只存儲和上一條Key不同的部分“olor”，兩者的共同部分從Key i中可以獲得。記錄的Key在Block內容部分就是這么存儲的，主要目的是減少存儲開銷。“重啟點”的意思是：在這條記錄開始，不再采取只記載不同的Key部分，而是重新記錄所有的Key值，假設Key i+1是一個重啟點，那么Key里面會完整存儲“the color”，而不是采用簡略的“olor”方式。Block尾部就是指出哪些記錄是這些重啟點的。

圖4.6?記錄格式

　　在Block內容區，每個KV記錄的內部結構是怎樣的？圖4.6給出了其詳細結構，每個記錄包含5個字段：key共享長度，比如上面的“olor”記錄，?其key和上一條記錄共享的Key部分長度是“the c”的長度，即5；key非共享長度，對于“olor”來說，是4；value長度指出Key:Value中Value的長度，在后面的Value內容字段中存儲實際的Value值；而key非共享內容則實際存儲“olor”這個Key字符串。

　　上面講的這些就是.sst文件的全部內部奧秘。

LevelDb日知錄之五：MemTable詳解

?　　LevelDb日知錄前述小節大致講述了磁盤文件相關的重要靜態結構，本小節講述內存中的數據結構Memtable，Memtable在整個體系中的重要地位也不言而喻。總體而言，所有KV數據都是存儲在Memtable，Immutable Memtable和SSTable中的，Immutable Memtable從結構上講和Memtable是完全一樣的，區別僅僅在于其是只讀的，不允許寫入操作，而Memtable則是允許寫入和讀取的。當Memtable寫入的數據占用內存到達指定數量，則自動轉換為Immutable Memtable，等待Dump到磁盤中，系統會自動生成新的Memtable供寫操作寫入新數據，理解了Memtable，那么Immutable Memtable自然不在話下。

?　　LevelDb的MemTable提供了將KV數據寫入，刪除以及讀取KV記錄的操作接口，但是事實上Memtable并不存在真正的刪除操作,刪除某個Key的Value在Memtable內是作為插入一條記錄實施的，但是會打上一個Key的刪除標記，真正的刪除操作是Lazy的，會在以后的Compaction過程中去掉這個KV。

?　　需要注意的是，LevelDb的Memtable中KV對是根據Key大小有序存儲的，在系統插入新的KV時，LevelDb要把這個KV插到合適的位置上以保持這種Key有序性。其實，LevelDb的Memtable類只是一個接口類，真正的操作是通過背后的SkipList來做的，包括插入操作和讀取操作等，所以Memtable的核心數據結構是一個SkipList。

?　　SkipList是由William Pugh發明。他在Communications of the ACM June 1990, 33(6) 668-676?發表了Skip lists: a probabilistic alternative to balanced trees，在該論文中詳細解釋了SkipList的數據結構和插入刪除操作。

SkipList是平衡樹的一種替代數據結構，但是和紅黑樹不相同的是，SkipList對于樹的平衡的實現是基于一種隨機化的算法的，這樣也就是說SkipList的插入和刪除的工作是比較簡單的。

關于SkipList的詳細介紹可以參考這篇文章：http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html，講述的很清楚，LevelDb的SkipList基本上是一個具體實現，并無特殊之處。

　　SkipList不僅是維護有序數據的一個簡單實現，而且相比較平衡樹來說，在插入數據的時候可以避免頻繁的樹節點調整操作，所以寫入效率是很高的，LevelDb整體而言是個高寫入系統，SkipList在其中應該也起到了很重要的作用。Redis為了加快插入操作，也使用了SkipList來作為內部實現數據結構。

LevelDb日知錄之六?寫入與刪除記錄

??????在之前的五節LevelDb日知錄中，我們介紹了LevelDb的一些靜態文件及其詳細布局，從本節開始，我們看看LevelDb的一些動態操作，比如讀寫記錄，Compaction，錯誤恢復等操作。

? ? ???本節介紹levelDb的記錄更新操作，即插入一條KV記錄或者刪除一條KV記錄。levelDb的更新操作速度是非常快的，源于其內部機制決定了這種更新操作的簡單性。?

圖6.1?LevelDb寫入記錄

?? ? ???圖6.1是levelDb如何更新KV數據的示意圖，從圖中可以看出，對于一個插入操作Put(Key,Value)來說，完成插入操作包含兩個具體步驟：首先是將這條KV記錄以順序寫的方式追加到之前介紹過的log文件末尾，因為盡管這是一個磁盤讀寫操作，但是文件的順序追加寫入效率是很高的，所以并不會導致寫入速度的降低；第二個步驟是:如果寫入log文件成功，那么將這條KV記錄插入內存中的Memtable中，前面介紹過，Memtable只是一層封裝，其內部其實是一個Key有序的SkipList列表，插入一條新記錄的過程也很簡單，即先查找合適的插入位置，然后修改相應的鏈接指針將新記錄插入即可。完成這一步，寫入記錄就算完成了，所以一個插入記錄操作涉及一次磁盤文件追加寫和內存SkipList插入操作，這是為何levelDb寫入速度如此高效的根本原因。

?? ? ???從上面的介紹過程中也可以看出：log文件內是key無序的，而Memtable中是key有序的。那么如果是刪除一條KV記錄呢？對于levelDb來說，并不存在立即刪除的操作，而是與插入操作相同的，區別是，插入操作插入的是Key:Value?值，而刪除操作插入的是“Key:刪除標記”，并不真正去刪除記錄，而是后臺Compaction的時候才去做真正的刪除操作。

? ? ? ? levelDb的寫入操作就是如此簡單。真正的麻煩在后面將要介紹的讀取操作中。

LevelDb日知錄之七：讀取記錄

?　　LevelDb是針對大規模Key/Value數據的單機存儲庫，從應用的角度來看，LevelDb就是一個存儲工具。而作為稱職的存儲工具，常見的調用接口無非是新增KV，刪除KV，讀取KV，更新Key對應的Value值這么幾種操作。LevelDb的接口沒有直接支持更新操作的接口，如果需要更新某個Key的Value,你可以選擇直接生猛地插入新的KV，保持Key相同，這樣系統內的key對應的value就會被更新；或者你可以先刪除舊的KV，?之后再插入新的KV，這樣比較委婉地完成KV的更新操作。

?????假設應用提交一個Key值，下面我們看看LevelDb是如何從存儲的數據中讀出其對應的Value值的。圖7-1是LevelDb讀取過程的整體示意圖。

圖7-1??LevelDb讀取記錄流程

　　LevelDb首先會去查看內存中的Memtable，如果Memtable中包含key及其對應的value，則返回value值即可；如果在Memtable沒有讀到key，則接下來到同樣處于內存中的Immutable Memtable中去讀取，類似地，如果讀到就返回，若是沒有讀到,那么只能萬般無奈下從磁盤中的大量SSTable文件中查找。因為SSTable數量較多，而且分成多個Level，所以在SSTable中讀數據是相當蜿蜒曲折的一段旅程。總的讀取原則是這樣的：首先從屬于level 0的文件中查找，如果找到則返回對應的value值，如果沒有找到那么到level 1中的文件中去找，如此循環往復，直到在某層SSTable文件中找到這個key對應的value為止（或者查到最高level，查找失敗，說明整個系統中不存在這個Key)。

?　　那么為什么是從Memtable到Immutable Memtable，再從Immutable Memtable到文件，而文件中為何是從低level到高level這么一個查詢路徑呢？道理何在？之所以選擇這么個查詢路徑，是因為從信息的更新時間來說，很明顯Memtable存儲的是最新鮮的KV對；Immutable Memtable中存儲的KV數據對的新鮮程度次之；而所有SSTable文件中的KV數據新鮮程度一定不如內存中的Memtable和Immutable Memtable的。對于SSTable文件來說，如果同時在level L和Level L+1找到同一個key，level L的信息一定比level L+1的要新。也就是說，上面列出的查找路徑就是按照數據新鮮程度排列出來的，越新鮮的越先查找。

?　　為啥要優先查找新鮮的數據呢？這個道理不言而喻，舉個例子。比如我們先往levelDb里面插入一條數據?{key="www.samecity.com"? value="我們"},過了幾天，samecity網站改名為：69同城，此時我們插入數據{key="www.samecity.com"? value="69同城"}，同樣的key,不同的value；邏輯上理解好像levelDb中只有一個存儲記錄，即第二個記錄，但是在levelDb中很可能存在兩條記錄，即上面的兩個記錄都在levelDb中存儲了，此時如果用戶查詢key="www.samecity.com",我們當然希望找到最新的更新記錄，也就是第二個記錄返回，這就是為何要優先查找新鮮數據的原因。

　　前文有講：對于SSTable文件來說，如果同時在level L和Level L+1找到同一個key，level L的信息一定比level L+1的要新。這是一個結論，理論上需要一個證明過程，否則會招致如下的問題：為神馬呢？從道理上講呢，很明白：因為Level L+1的數據不是從石頭縫里蹦出來的，也不是做夢夢到的，那它是從哪里來的？Level L+1的數據是從Level L?經過Compaction后得到的（如果您不知道什么是Compaction，那么........也許以后會知道的），也就是說，您看到的現在的Level L+1層的SSTable數據是從原來的Level L中來的，現在的Level L比原來的Level L數據要新鮮，所以可證，現在的Level L比現在的Level L+1的數據要新鮮。

　　SSTable文件很多，如何快速地找到key對應的value值？在LevelDb中，level 0一直都愛搞特殊化，在level 0和其它level中查找某個key的過程是不一樣的。因為level 0下的不同文件可能key的范圍有重疊，某個要查詢的key有可能多個文件都包含，這樣的話LevelDb的策略是先找出level 0中哪些文件包含這個key（manifest文件中記載了level和對應的文件及文件里key的范圍信息，LevelDb在內存中保留這種映射表），?之后按照文件的新鮮程度排序，新的文件排在前面，之后依次查找，讀出key對應的value。而如果是非level 0的話，因為這個level的文件之間key是不重疊的，所以只從一個文件就可以找到key對應的value。

　　最后一個問題,如果給定一個要查詢的key和某個key range包含這個key的SSTable文件，那么levelDb是如何進行具體查找過程的呢？levelDb一般會先在內存中的Cache中查找是否包含這個文件的緩存記錄，如果包含，則從緩存中讀取；如果不包含，則打開SSTable文件，同時將這個文件的索引部分加載到內存中并放入Cache中。?這樣Cache里面就有了這個SSTable的緩存項，但是只有索引部分在內存中，之后levelDb根據索引可以定位到哪個內容Block會包含這條key，從文件中讀出這個Block的內容，在根據記錄一一比較，如果找到則返回結果，如果沒有找到，那么說明這個level的SSTable文件并不包含這個key，所以到下一級別的SSTable中去查找。

　　從之前介紹的LevelDb的寫操作和這里介紹的讀操作可以看出，相對寫操作，讀操作處理起來要復雜很多，所以寫的速度必然要遠遠高于讀數據的速度，也就是說，LevelDb比較適合寫操作多于讀操作的應用場合。而如果應用是很多讀操作類型的，那么順序讀取效率會比較高，因為這樣大部分內容都會在緩存中找到，盡可能避免大量的隨機讀取操作。

LevelDb日知錄之八：Compaction操作

?????前文有述，對于LevelDb來說，寫入記錄操作很簡單，刪除記錄僅僅寫入一個刪除標記就算完事，但是讀取記錄比較復雜，需要在內存以及各個層級文件中依照新鮮程度依次查找，代價很高。為了加快讀取速度，levelDb采取了compaction的方式來對已有的記錄進行整理壓縮，通過這種方式，來刪除掉一些不再有效的KV數據，減小數據規模，減少文件數量等。

???? levelDb的compaction機制和過程與Bigtable所講述的是基本一致的，Bigtable中講到三種類型的compaction: minor ，major和full。所謂minor Compaction，就是把memtable中的數據導出到SSTable文件中；major compaction就是合并不同層級的SSTable文件，而full compaction就是將所有SSTable進行合并。

???? LevelDb包含其中兩種，minor和major。

????我們將為大家詳細敘述其機理。

????先來看看minor Compaction的過程。Minor compaction?的目的是當內存中的memtable大小到了一定值時，將內容保存到磁盤文件中，圖8.1是其機理示意圖。?

圖8.1?minor compaction

?????從8.1可以看出，當memtable數量到了一定程度會轉換為immutable memtable，此時不能往其中寫入記錄，只能從中讀取KV內容。之前介紹過，immutable memtable其實是一個多層級隊列SkipList，其中的記錄是根據key有序排列的。所以這個minor compaction實現起來也很簡單，就是按照immutable memtable中記錄由小到大遍歷，并依次寫入一個level 0?的新建SSTable文件中，寫完后建立文件的index?數據，這樣就完成了一次minor compaction。從圖中也可以看出，對于被刪除的記錄，在minor compaction過程中并不真正刪除這個記錄，原因也很簡單，這里只知道要刪掉key記錄，但是這個KV數據在哪里?那需要復雜的查找，所以在minor compaction的時候并不做刪除，只是將這個key作為一個記錄寫入文件中，至于真正的刪除操作，在以后更高層級的compaction中會去做。

?????當某個level下的SSTable文件數目超過一定設置值后，levelDb會從這個level的SSTable中選擇一個文件（level>0），將其和高一層級的level+1的SSTable文件合并，這就是major compaction。

????我們知道在大于0的層級中，每個SSTable文件內的Key都是由小到大有序存儲的，而且不同文件之間的key范圍（文件內最小key和最大key之間）不會有任何重疊。Level 0的SSTable文件有些特殊，盡管每個文件也是根據Key由小到大排列，但是因為level 0的文件是通過minor compaction直接生成的，所以任意兩個level 0下的兩個sstable文件可能再key范圍上有重疊。所以在做major compaction的時候，對于大于level 0的層級，選擇其中一個文件就行，但是對于level 0來說，指定某個文件后，本level中很可能有其他SSTable文件的key范圍和這個文件有重疊，這種情況下，要找出所有有重疊的文件和level 1的文件進行合并，即level 0在進行文件選擇的時候，可能會有多個文件參與major compaction。

　　levelDb在選定某個level進行compaction后，還要選擇是具體哪個文件要進行compaction，levelDb在這里有個小技巧，?就是說輪流來，比如這次是文件A進行compaction，那么下次就是在key range上緊挨著文件A的文件B進行compaction，這樣每個文件都會有機會輪流和高層的level?文件進行合并。

如果選好了level L的文件A和level L+1層的文件進行合并，那么問題又來了，應該選擇level L+1哪些文件進行合并？levelDb選擇L+1層中和文件A在key range上有重疊的所有文件來和文件A進行合并。

?　　也就是說，選定了level L的文件A,之后在level L+1中找到了所有需要合并的文件B,C,D…..等等。剩下的問題就是具體是如何進行major?合并的？就是說給定了一系列文件，每個文件內部是key有序的，如何對這些文件進行合并，使得新生成的文件仍然Key有序，同時拋掉哪些不再有價值的KV?數據。

????圖8.2說明了這一過程。

圖8.2?SSTable Compaction

　　Major compaction的過程如下：對多個文件采用多路歸并排序的方式，依次找出其中最小的Key記錄，也就是對多個文件中的所有記錄重新進行排序。之后采取一定的標準判斷這個Key是否還需要保存，如果判斷沒有保存價值，那么直接拋掉，如果覺得還需要繼續保存，那么就將其寫入level L+1層中新生成的一個SSTable文件中。就這樣對KV數據一一處理，形成了一系列新的L+1層數據文件，之前的L層文件和L+1層參與compaction?的文件數據此時已經沒有意義了，所以全部刪除。這樣就完成了L層和L+1層文件記錄的合并過程。

　　那么在major compaction過程中，判斷一個KV記錄是否拋棄的標準是什么呢？其中一個標準是:對于某個key來說，如果在小于L層中存在這個Key，那么這個KV在major compaction過程中可以拋掉。因為我們前面分析過，對于層級低于L的文件中如果存在同一Key的記錄，那么說明對于Key來說，有更新鮮的Value存在，那么過去的Value就等于沒有意義了，所以可以刪除。

?

LevelDb日知錄之九?levelDb中的Cache

　　書接前文，前面講過對于levelDb來說，讀取操作如果沒有在內存的memtable中找到記錄，要多次進行磁盤訪問操作。假設最優情況，即第一次就在level 0中最新的文件中找到了這個key，那么也需要讀取2次磁盤，一次是將SSTable的文件中的index部分讀入內存，這樣根據這個index可以確定key是在哪個block中存儲；第二次是讀入這個block的內容，然后在內存中查找key對應的value。

　　levelDb中引入了兩個不同的Cache:Table Cache和Block Cache。其中Block Cache是配置可選的，即在配置文件中指定是否打開這個功能。

圖9.1?table cache

?　　圖9.1是table cache的結構。在Cache中，key值是SSTable的文件名稱，Value部分包含兩部分，一個是指向磁盤打開的SSTable文件的文件指針，這是為了方便讀取內容；另外一個是指向內存中這個SSTable文件對應的Table結構指針，table結構在內存中，保存了SSTable的index內容以及用來指示block cache用的cache_id ,當然除此外還有其它一些內容。

　　比如在get(key)讀取操作中，如果levelDb確定了key在某個level下某個文件A的key range范圍內，那么需要判斷是不是文件A真的包含這個KV。此時，levelDb會首先查找Table Cache，看這個文件是否在緩存里，如果找到了，那么根據index部分就可以查找是哪個block包含這個key。如果沒有在緩存中找到文件，那么打開SSTable文件，將其index部分讀入內存，然后插入Cache里面，去index里面定位哪個block包含這個Key 。如果確定了文件哪個block包含這個key，那么需要讀入block內容，這是第二次讀取。

圖9.2?block cache

?　　Block Cache是為了加快這個過程的，圖9.2是其結構示意圖。其中的key是文件的cache_id加上這個block在文件中的起始位置block_offset。而value則是這個Block的內容。

　　如果levelDb發現這個block在block cache中，那么可以避免讀取數據，直接在cache里的block內容里面查找key的value就行，如果沒找到呢？那么讀入block內容并把它插入block cache中。levelDb就是這樣通過兩個cache來加快讀取速度的。從這里可以看出，如果讀取的數據局部性比較好，也就是說要讀的數據大部分在cache里面都能讀到，那么讀取效率應該還是很高的，而如果是對key進行順序讀取效率也應該不錯，因為一次讀入后可以多次被復用。但是如果是隨機讀取，您可以推斷下其效率如何。

LevelDb日知錄之十?Version、VersionEdit、VersionSet

　　Version?保存了當前磁盤以及內存中所有的文件信息，一般只有一個Version叫做"current" version（當前版本）。Leveldb還保存了一系列的歷史版本，這些歷史版本有什么作用呢？

當一個Iterator創建后，Iterator就引用到了current version(當前版本)，只要這個Iterator不被delete那么被Iterator引用的版本就會一直存活。這就意味著當你用完一個Iterator后，需要及時刪除它。

　　當一次Compaction結束后（會生成新的文件，合并前的文件需要刪除），Leveldb會創建一個新的版本作為當前版本，原先的當前版本就會變為歷史版本。

　　VersionSet?是所有Version的集合，管理著所有存活的Version。

　　VersionEdit?表示Version之間的變化，相當于delta?增量，表示有增加了多少文件，刪除了文件。下圖表示他們之間的關系。

Version0?+VersionEdit-->Version1

　　VersionEdit會保存到MANIFEST文件中，當做數據恢復時就會從MANIFEST文件中讀出來重建數據。

　　leveldb的這種版本的控制，讓我想到了雙buffer切換，雙buffer切換來自于圖形學中，用于解決屏幕繪制時的閃屏問題，在服務器編程中也有用處。

　　比如我們的服務器上有一個字典庫，每天我們需要更新這個字典庫，我們可以新開一個buffer，將新的字典庫加載到這個新buffer中，等到加載完畢，將字典的指針指向新的字典庫。

leveldb的version管理和雙buffer切換類似，但是如果原version被某個iterator引用，那么這個version會一直保持，直到沒有被任何一個iterator引用，此時就可以刪除這個version。

注：博文參考了郎格科技博客：http://www.samecity.com/blog/Index.asp?SortID=12

總結

以上是生活随笔為你收集整理的LevelDb实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。