LevelDB原理及应用
LevelDB
LevelDB之概覽
LevelDB是Google傳奇工程師Jeff Dean和Sanjay Ghemawat開源的KV存儲引擎。?
了解原理之前首先要用起來，下面動手實現個例子：安裝調試(mac上直接命令行下brew install leveldb即可安裝，編譯時候記得加上-lleveldb)?
example:
#include <assert.h>
#include <string.h>
#include <leveldb/db.h>
#include <iostream>
int main(int argc, char** argv)
{
? ? leveldb::DB* db;
? ? leveldb::Options options;
? ? // 如果打開已存在數據庫的時候，需要拋出錯誤，將以下代碼插在leveldb::DB::Open方法前面
? ? options.create_if_missing = true;
? ? // 打開一個數據庫實例
? ? leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
? ? assert(status.ok());
? ? // LevelDB提供了Put、Get和Delete三個方法對數據庫進行添加、查詢和刪除
? ? std::string key = "key";
? ? std::string value = "value";
? ? // 添加key=value
? ? status = db->Put(leveldb::WriteOptions(), key, value);
? ? assert(status.ok());
? ? // 根據key查詢value
? ? status = db->Get(leveldb::ReadOptions(), key, &value);
? ? assert(status.ok());
? ? std::cout<<value<<std::endl;
? ? // 修改操作（原生沒有提供）由添加和刪除合起來實現
? ? std::string key2 = "key2";
? ? // 添加key2=value
? ? status = db->Put(leveldb::WriteOptions(),key2,value);
? ? assert(status.ok());
? ? // 刪除key
? ? status = db->Delete(leveldb::WriteOptions(), key);
? ? // 查詢key2
? ? assert(status.ok());
? ? status = db->Get(leveldb::ReadOptions(), key2, &value);
? ? assert(status.ok());
? ? std::cout<<key2<<"=="<<value<<std::endl;
? ? // 查詢key
? ? status = db->Get(leveldb::ReadOptions(), key, &value);
? ? if (!status.ok()) {
? ? ? ? std::cerr << key << ": " << status.ToString() << std::endl;
? ? } else {
? ? ? ? std::cout << key << "==" << value << std::endl;
? ? }
? ? delete db;
? ? return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
設計思路
LevelDB的數據是存儲在磁盤上的，采用LSM-Tree的結構實現。LSM-Tree將磁盤的隨機寫轉化為順序寫，從而大大提高了寫速度。?
?
為了做到這一點LSM-Tree的思路是將索引樹結構拆成一大一小兩顆樹，較小的一個常駐內存，較大的一個持久化到磁盤，他們共同維護一個有序的key空間。?
?
寫入操作會首先操作內存中的樹，隨著內存中樹的不斷變大，會觸發與磁盤中樹的歸并操作，而歸并操作本身僅有順序寫。隨著數據的不斷寫入，磁盤中的樹會不斷膨脹，為了避免每次參與歸并操作的數據量過大，以及優化讀操作的考慮，LevelDB將磁盤中的數據又拆分成多層，每一層的數據達到一定容量后會觸發向下一層的歸并操作，每一層的數據量比其上一層成倍增長。這也就是LevelDB的名稱來源。
整體結構
內存數據的Memtable，分層數據存儲的SST文件，版本控制的Manifest、Current文件，以及寫Memtable前的WAL。
WAL: Write-Ahead Logging預寫日志系統?
數據庫中一種高效的日志算法，對于非內存數據庫而言，磁盤I/O操作是數據庫效率的一大瓶頸。在相同的數據量下，采用WAL日志的數據庫系統在事務提交時，磁盤寫操作只有傳統的回滾日志的一半左右，大大提高了數據庫磁盤I/O操作的效率，從而提高了數據庫的性能。
?
Memtable：
對應Leveldb中的內存數據，LevelDB的寫入操作會直接將數據寫入到Memtable后返回。讀取操作又會首先嘗試從Memtable中進行查詢，允許寫入和讀取。當Memtable寫入的數據占用內存到達指定數量，則自動轉換為Immutable Memtable，等待Dump到磁盤中，系統會自動生成新的Memtable供寫操作寫入新數據。?
LevelDB采用跳表SkipList實現，在給提供了O(logn)的時間復雜度的同時，又非常的易于實現：?
?
跳表作為一種數據結構通常用于取代平衡樹，與紅黑樹不同的是，skiplist對于樹的平衡的實現是基于一種隨機化的算法的，也就是說skiplist的插入和刪除的工作是比較簡單地。
SkipList中單條數據存放一條Key-Value數據，定義為：
SkipList Node := InternalKey + ValueString
InternalKey := KeyString + SequenceNum + Type
Type := kDelete or kValue
ValueString := ValueLength + Value
KeyString := UserKeyLength + UserKey
1
2
3
4
5
Log文件
當應用寫入一條Key:Value記錄的時候，LevelDb會先往log文件里寫入，成功后將記錄插進Memtable中，這樣基本就算完成了寫入操作，Log文件在系統中的作用主要是用于系統崩潰恢復而不丟失數據，假如沒有Log文件，因為寫入的記錄剛開始是保存在內存中的，此時如果系統崩潰，內存中的數據還沒有來得及Dump到磁盤，所以會丟失數據（Redis就存在這個問題）。?
因為一次寫入操作只涉及一次磁盤順序寫和一次內存寫入，所以這是為何說LevelDb寫入速度極快的主要原因。?
LevelDB首先將每條寫入數據序列化為一個Record，單個Log文件中包含多個Record。同時，Log文件又劃分為固定大小的Block單位，并保證Block的開始位置一定是一個新的Record。這種安排使得發生數據錯誤時，最多只需丟棄一個Block大小的內容。顯而易見地，不同的Record可能共存于一個Block，同時，一個Record也可能橫跨幾個Block。?
?
?
Log文件劃分為固定長度的Block，由連續的32K為單位的物理Block構成的，每次讀取的單位是以一個Block作為基本單位；每個Block中包含多個Record；Record的前56個位為Record頭，包括32位checksum用做校驗，16位存儲Record實際內容數據的長度，8位的Type可以是Full、First、Middle或Last中的一種，表示該Record是否完整的在當前的Block中，如果Type不是Full，則通過Type指明其前后的Block中是否有當前Record的前驅后繼。?
Block := Record * N
Record := Header + Content
Header := Checksum + Length + Type
Type := Full or First or Midder or Last
1
2
3
4
Immutable Memtable
當Memtable插入的數據占用內存到了一個界限后，需要將內存的記錄導出到外存文件中，LevleDb會生成新的Log文件和Memtable，Memtable會變為Immutable，為之后向SST文件的歸并做準備。顧名思義，Immutable Mumtable不再接受用戶寫入，只能讀不能寫入或者刪除，同時會有新的Log文件和Memtable生成，LevelDb后臺調度會將Immutable Memtable的數據導出到磁盤，形成一個新的SSTable文件。
SST文件
SSTable就是由內存中的數據不斷導出并進行Compaction操作(壓縮操作，下文會講到)后形成的，而且SSTable的所有文件是一種層級結構，第一層為Level 0，第二層為Level 1，依次類推，層級逐漸增高，這也是為何稱之為LevelDb的原因。?
磁盤數據存儲文件。分為Level 0到Level N多層，每一層包含多個SST文件；單個SST文件容量隨層次增加成倍增長；文件內數據有序；其中Level 0的SST文件由Immutable直接Dump產生，其他Level的SST文件由其上一層的文件和本層文件歸并產生；SST文件在歸并過程中順序寫生成，生成后僅可能在之后的歸并中被刪除，而不會有任何的修改操作。?
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}:
level N?? ?.sst?? ?max?? ?min
Level 0?? ?A.sst?? ?“bar”?? ?“car”
Level 0?? ?B.sst?? ?“blue”?? ?“samecity”
那么很可能兩個文件都存在key=”blood”的記錄。對于其它Level的SSTable文件來說，則不會出現同一層級內。
SST文件的物理格式
LevelDb不同層級有很多SSTable文件（以后綴.sst為特征），所有.sst文件內部布局都是一樣的。上節介紹Log文件是物理分塊的，SSTable也一樣會將文件劃分為固定大小的物理存儲塊，但是兩者邏輯布局大不相同，根本原因是：Log文件中的記錄是Key無序的，即先后記錄的key大小沒有明確大小關系，而.sst文件內部則是根據記錄的Key由小到大排列的。?
LevelDB將SST文件定義為Table，每個Table又劃分為多個連續的Block，每個Block中又存儲多條數據Entry：?
?
可以看出，單個Block作為一個獨立的寫入和解析單位，會在其末尾存儲一個字節的Type和4個字節的Crc，其中Type記錄的是當前Block的數據壓縮策略（Snappy壓縮或者無壓縮兩種），而Crc則存儲Block中數據的校驗信息。?
Block中每條數據Entry是以Key-Value方式存儲的，并且是按Key有序存儲，Leveldb很巧妙了利用了有序數組相鄰Key可能有相同的Prefix的特點來減少存儲數據量。如上圖所示，每個Entry只記錄自己的Key與前一個Entry Key的不同部分，?
在Entry開頭記錄三個長度值，分別是當前Entry和其之前Entry的公共Key Prefix長度、當前Entry Key自有Key部分的長度和Value的長度。通過這些長度信息和其后相鄰的特有Key及Value內容，結合前一條Entry的Key內容，我們可以方便的獲得當前Entry的完整Key和Value信息。?
例如要順序存儲Key值“apple” = value1和“applepen” = value2的兩條數據，這里第二個Entry中，key共享長度為5，key非共享長度為3，value長度為6，key非共享內容為“pen”，value內容為“value2”.
這種方式非常好的減少了數據存儲，但同時也引入一個風險，如果最開頭的Entry數據損壞，其后的所有Entry都將無法恢復。為了降低這個風險，leveldb引入了重啟點，每隔固定條數Entry會強制加入一個重啟點，這個位置的Entry會完整的記錄自己的Key，并將其shared值設置為0。同時，Block會將這些重啟點的偏移量及個數記錄在所有Entry后邊的Tailer中。
SST文件的邏輯格式
Table中不同的Block物理上的存儲方式一致，如上文所示，但在邏輯上可能存儲不同的內容，包括存儲數據的Block，存儲索引信息的Block，存儲Filter的Block：?
Data Block:?
從圖中可以看出，其內部也分為兩個部分，前面是一個個KV記錄，其順序是根據Key值由小到大排列的，在Block尾部則是一些“重啟點”（Restart Point）,其實是一些指針，指出Block內容中的一些記錄位置。
Footer：為于Table尾部，記錄指向Metaindex Block的Handle和指向Index Block的Handle。需要說明的是Table中所有的Handle是通過偏移量Offset以及Size一同來表示的，用來指明所指向的Block位置。Footer是SST文件解析開始的地方，通過Footer中記錄的這兩個關鍵元信息Block的位置，可以方便的開啟之后的解析工作。另外Footer中還記錄了用于驗證文件是否為合法SST文件的常數值Magic num。
Index Block：記錄Data Block位置信息的Block，其中的每一條Entry指向一個Data Block，其Key值為所指向的Data Block最后一條數據的Key，Value為指向該Data Block位置的Handle。
Metaindex Block：與Index Block類似，由一組Handle組成，不同的是這里的Handle指向的Meta Block。
Data Block：以Key-Value的方式存儲實際數據，其中Key定義為：
DataBlock Key := UserKey + SequenceNum + Type?
//對比Memtable中的Key，可以發現Data Block中的Key并沒有拼接UserKey的長度在UserKey前，
//這是由于上面講到的物理結構中已經有了Key的長度信息。
Type := kDelete or kValue
1
2
3
4
5
Meta Block：比較特殊的Block，用來存儲元信息，目前LevelDB使用的僅有對布隆過濾器的存儲。寫入Data Block的數據會同時更新對應Meta Block中的過濾器。讀取數據時也會首先經過布隆過濾器過濾。Meta Block的物理結構也與其他Block有所不同：
?[filter 0]
?[filter 1]
?[filter 2]
?...?
?[filter N-1]
?[offset of filter 0] : 4 bytes
?[offset of filter 1] : 4 bytes
?[offset of filter 2] : 4 bytes
?...?
?[offset of filter N-1] : 4 bytes
?[offset of beginning of offset array] : 4 bytes
?lg(base) : 1 byte
1
2
3
4
5
6
7
8
9
10
11
12
其中每個filter節對應一段Key Range，落在某個Key Range的Key需要到對應的filter節中查找自己的過濾信息，base指定這個Range的大小。
Manifest文件
Manifest文件中記錄SST文件在不同Level的分布，單個SST文件的最大最小key，以及其他一些LevelDB需要的元信息。?
SSTable中的某個文件屬于特定層級，而且其存儲的記錄是key有序的，那么必然有文件中的最小key和最大key，這是非常重要的信息，LevelDb應該記下這些信息。Manifest就是干這個的
Current文件
從上面的介紹可以看出，LevelDB啟動時的首要任務就是找到當前的Manifest，而Manifest可能有多個。Current文件簡單的記錄了當前Manifest的文件名，從而讓這個過程變得非常簡單。?
Current文件的內容只有一個信息，就是記載當前的manifest文件名。因為在LevleDb的運行過程中，隨著Compaction的進行，SSTable文件會發生變化，會有新的文件產生，老的文件被廢棄，Manifest也會跟著反映這種變化，此時往往會新生成Manifest文件來記載這種變化，而Current則用來指出哪個Manifest文件才是我們關心的那個Manifest文件。
主要操作
讀寫操作
寫流程
LevelDB的寫操作包括設置key-value和刪除key兩種。需要指出的是這兩種情況在LevelDB的處理上是一致的，刪除操作其實是向LevelDB插入一條標識為刪除的數據。?
Memtable并不存在真正的刪除操作，刪除某個Key的Value在Memtable內是作為插入一條記錄實施的，但是會打上一個Key的刪除標記，真正的刪除操作是Lazy的，會在以后的Compaction過程中去掉這個KV。?
?
從圖中可以看出，對于一個插入操作Put(Key,Value)來說，完成插入操作包含兩個具體步驟：?
首先是將這條KV記錄以順序寫的方式追加到之前介紹過的log文件末尾，因為盡管這是一個磁盤讀寫操作，但是文件的順序追加寫入效率是很高的，所以并不會導致寫入速度的降低；?
第二個步驟是:如果寫入log文件成功，那么將這條KV記錄插入內存中的Memtable中，前面介紹過，Memtable只是一層封裝，其內部其實是一個Key有序的SkipList列表，插入一條新記錄的過程也很簡單，即先查找合適的插入位置，然后修改相應的鏈接指針將新記錄插入即可。完成這一步，寫入記錄就算完成了。?
所以一個插入記錄操作涉及一次磁盤文件追加寫和內存SkipList插入操作，這是為何levelDb寫入速度如此高效的根本原因。?
LevelDb的接口沒有直接支持更新操作的接口，如果需要更新某個Key的Value,你可以選擇直接生猛地插入新的KV，保持Key相同，這樣系統內的key對應的value就會被更新；或者你可以先刪除舊的KV， 之后再插入新的KV，這樣比較委婉地完成KV的更新操作。
讀流程
首先，生成內部查詢所用的Key，用生成的Key，依次嘗試從 Memtable，Immtable以及SST文件中讀取，直到找到（或者查到最高level，查找失敗，說明整個系統中不存在這個Key)。?
從信息的更新時間來說，很明顯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",我們當然希望找到最新的更新記錄，也就是第二個記錄返回，這就是為何要優先查找新鮮數據的原因。
從SST文件中查找需要依次嘗試在每一層中讀取，得益于Manifest中記錄的每個文件的key區間，我們可以很方便的知道某個key是否在文件中。Level 0的文件由于直接由Immutable Dump 產生，不可避免的會相互重疊，所以需要對每個文件依次查找。對于其他層次，由于歸并過程保證了其互相不重疊且有序，二分查找的方式提供了更好的查詢效率。?
可以看出同一個Key出現在上層的操作會屏蔽下層的。也因此刪除Key時只需要在Memtable壓入一條標記為刪除的條目即可。被其屏蔽的所有條目會在之后的歸并過程中清除。?
相對寫操作，讀操作處理起來要復雜很多，所以寫的速度必然要遠遠高于讀數據的速度，也就是說，LevelDb比較適合寫操作多于讀操作的應用場合。而如果應用是很多讀操作類型的，那么順序讀取效率會比較高，因為這樣大部分內容都會在緩存中找到，盡可能避免大量的隨機讀取操作。
levelDb中的Cache
讀取操作如果沒有在內存的memtable中找到記錄，要多次進行磁盤訪問操作。假設最優情況，即第一次就在level 0中最新的文件中找到了這個key，那么也需要讀取2次磁盤，一次是將SSTable的文件中的index部分讀入內存，這樣根據這個index可以確定key是在哪個block中存儲；第二次是讀入這個block的內容，然后在內存中查找key對應的value。?
levelDb中引入了兩個不同的Cache： Table Cache 和 Block Cache。其中Block 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內容，這是第二次讀取。
File?
cache_id + block_offset?? ?block內容
File?
cache_id + block_offset?? ?block內容
File?
cache_id + block_offset?? ?block內容
File?
cache_id + block_offset?? ?block內容
Block Cache是為了加快這個過程的，如上圖。其中的key是文件的cache_id加上這個block在文件中的起始位置block_offset。而value則是這個Block的內容。?
如果levelDb發現這個block在block cache中，那么可以避免讀取數據，直接在cache里的block內容里面查找key的value就行，如果沒找到呢？那么讀入block內容并把它插入block cache中。levelDb就是這樣通過兩個cache來加快讀取速度的。?
從這里可以看出，如果讀取的數據局部性比較好，也就是說要讀的數據大部分在cache里面都能讀到，那么讀取效率應該還是很高的，而如果是對key進行順序讀取效率也應該不錯，因為一次讀入后可以多次被復用。但是如果是隨機讀取，您可以推斷下其效率如何。
壓縮操作
為了加快讀取速度，levelDb采取了compaction的方式來對已有的記錄進行整理壓縮，通過這種方式，來刪除掉一些不再有效的KV數據，減小數據規模，減少文件數量等。?
數據壓縮是LevelDB中重要的部分，即上文提到的歸并。冷數據會隨著Compaction不斷的下移，同時過期的數據也會在合并過程中被刪除。?
LevelDB的壓縮操作由單獨的后臺線程負責。這里的Compaction包括兩個部分，Memtable向Level 0 SST文件的Compaction，以及SST文件向下層的Compaction。?
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大小到了一定值時，將內容保存到磁盤文件中：
當memtable數量到了一定程度會轉換為immutable memtable，此時不能往其中寫入記錄，只能從中讀取KV內容。之前介紹過，immutable memtable其實是一個多層級隊列SkipList，其中的記錄是根據key有序排列的。所以這個minor compaction實現起來也很簡單，就是按照immutable memtable中記錄由小到大遍歷，并依次寫入一個level 0的新建SSTable文件中，寫完后建立文件的index數據，這樣就完成了一次minor compaction。?
CompactMemTable函數會將Immutable中的數據整體Dump為Level 0的一個文件，這個過程會在Immutable Memtable存在時被Compaction后臺線程調度。?
過程比較簡單，首先會獲得一個Immutable的Iterator用來遍歷其中的所有內容，創建一個新的Level 0 SST文件，并將Iterator讀出的內容依次順序寫入該文件。之后更新元信息并刪除Immutable Memtable。
major 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。?
同層的文件輪流來compaction，比如這次是文件A進行compaction，那么下次就是在key range上緊挨著文件A的文件B進行compaction，這樣每個文件都會有機會輪流和高層的level 文件進行合并。如果選好了level L的文件A和level L+1層的文件進行合并，那么問題又來了，應該選擇level L+1哪些文件進行合并？levelDb選擇L+1層中和文件A在key range上有重疊的所有文件來和文件A進行合并。?
?
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就等于沒有意義了，所以可以刪除。?
BackgroundCompaction函數?
SST文件的Compaction可以由用戶通過接口手動發起，也可以自動觸發。LevelDB中觸發SST Compaction的因素包括Level 0 SST的個數，其他Level SST文件的總大小，某個文件被訪問的次數。Compaction線程一次Compact的過程如下：
首先根據觸發Compaction的原因以及維護的相關信息找到本次要Compact的一個SST文件。對于Level 0的文件比較特殊，由于Level 0的SST文件由Memtable在不同時間Dump而成，所以可能有Key重疊。因此除該文件外還需要獲得所有與之重疊的Level 0文件。這時我們得到一個包含一個或多個文件的文件集合，處于同一Level。
SetupOtherInputs： 在Level+1層獲取所有與當前的文件集合有Key重合的文件。
DoCompactionWork：對得到的包含相鄰兩層多個文件的文件集合，進行歸并操作并將結果輸出到Level + 1層的一個新的SST文件，歸并的過程中刪除所有過期的數據。刪除之前的文件集合里的所有文件。
通過上述過程我們可以看到，這個新生成的文件在其所在Level不會跟任何文件有Key的重疊。
LevelDb 的特點：
首先，LevelDb是一個持久化存儲的KV系統，和Redis這種內存型的KV系統不同，LevelDb不會像Redis一樣狂吃內存，而是將大部分數據存儲到磁盤上。
其次，LevelDb在存儲數據時，是根據記錄的key值有序存儲的，就是說相鄰的key值在存儲文件中是依次順序存儲的，而應用可以自定義key大小比較函數，LevelDb會按照用戶定義的比較函數依序存儲這些記錄。
再次，像大多數KV系統一樣，LevelDb的操作接口很簡單，基本操作包括寫記錄，讀記錄以及刪除記錄。也支持針對多條操作的原子批量操作。
另外，LevelDb支持數據快照(snapshot)功能，使得讀取操作不受寫操作影響，可以在讀操作過程中始終看到一致的數據。
除此外，LevelDb還支持數據壓縮等操作，這對于減小存儲空間以及增快IO效率都有直接的幫助。
LevelDb性能非常突出，官方網站報道其隨機寫性能達到40萬條記錄每秒，而隨機讀性能達到6萬條記錄每秒。總體來說，LevelDb的寫操作要大大快于讀操作，而順序讀寫操作則大大快于隨機讀寫操作。
http://www.frankyang.cn/2017/09/04/%E5%8D%8A%E5%B0%8F%E6%97%B6%E5%AD%A6%E4%BC%9Aleveldb%E5%8E%9F%E7%90%86%E5%8F%8A%E5%BA%94%E7%94%A8/
----------------
總結
以上是生活随笔為你收集整理的LevelDB原理及应用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： HBase、Redis、MongoDB、
- 下一篇： TokuMX