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是Google開源的持久化KV單機資料庫，具有很高的随機寫，順序讀/寫性能，但是随機讀的性能很一般，也就是說，LevelDB很适合應用在查詢較少，而寫很多的場景。LevelDB應用了LSM (Log Structured Merge) 政策，lsm_tree對索引變更進行延遲及批量處理，并通過一種類似于歸并排序的方式高效地将更新遷移到磁盤，降低索引插入開銷，關于LSM，本文在後面也會簡單提及。
根據Leveldb官方網站的描述，LevelDB的特點和限制如下：
特點：
1、key和value都是任意長度的位元組數組；
2、entry（即一條K-V記錄）預設是按照key的字典順序存儲的，當然開發者也可以重載這個排序函數；
3、提供的基本操作接口：Put()、Delete()、Get()、Batch()；
4、支援批量操作以原子操作進行；
5、可以建立資料全景的snapshot(快照)，并允許在快照中查找資料；
6、可以通過前向（或後向）疊代器周遊資料（疊代器會隐含的建立一個snapshot）；
7、自動使用Snappy壓縮資料；
8、可移植性；
限制：
1、非關系型資料模型（NoSQL），不支援sql語句，也不支援索引；
2、一次隻允許一個程序通路一個特定的資料庫；
3、沒有内置的C/S架構，但開發者可以使用LevelDB庫自己封裝一個server；）
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。