leveldb學習之初識

基本概念

leveldb是一個寫性能十分優秀的存儲引擎，是典型的LSM樹(Log Structured-Merge Tree)實作。LSM樹的核心思想就是放棄部分讀的性能，換取最大的寫入能力。

LSM樹寫性能極高的原理，簡單地來說就是盡量減少随機寫的次數。對于每次寫入操作，并不是直接将最新的資料駐留在磁盤中，而是将其拆分成（1）一次日志檔案的順序寫（2）一次記憶體中的資料插入。leveldb正是實踐了這種思想，将資料首先更新在記憶體中，當記憶體中的資料達到一定的門檻值，将這部分資料真正重新整理到磁盤檔案中，因而獲得了極高的寫性能（順序寫60MB/s, 随機寫45MB/s）。

在本文中，将介紹一下leveldb的基本架構、概念。

整體架構

1、memtable

leveldb的一次寫入操作并不是直接将資料重新整理到磁盤檔案，而是首先寫入到記憶體中作為代替，memtable就是一個在記憶體中進行資料組織與維護的結構。memtable中，所有的資料按使用者定義的排序方法排序之後按序存儲，等到其存儲内容的容量達到門檻值時（預設為4MB），便将其轉換成一個不可修改的memtable，與此同時建立一個新的memtable，供使用者繼續進行讀寫操作。memtable底層使用了一種跳表資料結構，這種資料結構效率可以比拟二叉查找樹，絕大多數操作的時間複雜度為O(log n)。

2、 immutable memtable

memtable的容量到達門檻值時，便會轉換成一個不可修改的memtable，也稱為immutable memtable。這兩者的結構定義完全一樣，差別隻是immutable memtable是隻讀的。當一個immutable memtable被建立時，leveldb的背景壓縮程序便會将利用其中的内容，建立一個sstable，持久化到磁盤檔案中。

3、log

leveldb的寫操作并不是直接寫入磁盤的，而是首先寫入到記憶體。假設寫入到記憶體的資料還未來得及持久化，leveldb程序發生了異常，抑或是主控端器發生了當機，會造成使用者的寫入發生丢失。是以leveldb在寫記憶體之前會首先将所有的寫操作寫到日志檔案中，也就是log檔案。當以下異常情況發生時，均可以通過日志檔案進行恢複：

• 寫log期間程序異常；
• 寫log完成，寫記憶體未完成；
• write動作完成（即log、記憶體寫入都完成）後，程序異常；
• Immutable memtable持久化過程中程序異常；

當第一類情況發生時，資料庫重新開機讀取log時，發現異常日志資料，抛棄該條日志資料，即視作這次使用者寫入失敗，保障了資料庫的一緻性；

當第二類，第三類，第四類情況發生了，均可以通過redo日志檔案中記錄的寫入操作完成資料庫的恢複。

每次日志的寫操作都是一次順序寫，是以寫效率高，整體寫入性能較好。

此外，leveldb的使用者寫操作的原子性同樣通過日志來實作。

4、sstable

雖然leveldb采用了先寫記憶體的方式來提高寫入效率，但是記憶體中資料不可能無限增長，且日志中記錄的寫入操作過多，會導緻異常發生時，恢複時間過長。是以記憶體中的資料達到一定容量，就需要将資料持久化到磁盤中。除了某些中繼資料檔案，leveldb的資料主要都是通過sstable來進行存儲。

雖然在記憶體中，所有的資料都是按序排列的，但是當多個memetable資料持久化到磁盤後，對應的不同的sstable之間是存在交集的，在讀操作時，需要對所有的sstable檔案進行周遊，嚴重影響了讀取效率。是以leveldb背景會“定期“整合這些sstable檔案，該過程也稱為compaction。随着compaction的進行，sstable檔案在邏輯上被分成若幹層，由記憶體資料直接dump出來的檔案稱為level 0層檔案，後期整合而成的檔案為level i 層檔案，這也是leveldb這個名字的由來。

注意，所有的sstable檔案本身的内容是不可修改的，這種設計哲學為leveldb帶來了許多優勢，簡化了很多設計。具體将在接下來的文章中具體解釋。

5、manifest

leveldb中有個版本的概念，一個版本中主要記錄了每一層中所有檔案的中繼資料，中繼資料包括（1）檔案大小（2）最大key值（3）最小key值。該版本資訊十分關鍵，除了在查找資料時，利用維護的每個檔案的最大／小key值來加快查找，還在其中維護了一些進行compaction的統計值，來控制compaction的進行。

6、current

這個檔案的内容隻有一個資訊，就是記載目前的manifest檔案名。

因為每次leveldb啟動時，都會建立一個新的Manifest檔案。是以資料目錄可能會存在多個Manifest檔案。Current則用來指出哪個Manifest檔案才是我們關心的那個Manifest檔案。