LevelDB是一個(gè)可持久化的KV數(shù)據(jù)庫(kù)引擎着降，由Google傳奇工程師Jeff Dean和Sanjay Ghemawat開發(fā)并開源鹊碍。無(wú)論從設(shè)計(jì)還是代碼上都可以用精致優(yōu)雅來(lái)形容，非常值得細(xì)細(xì)品味侈咕。本文將從整體特性器紧、架構(gòu)和使用等幾方面做一個(gè)解釋，試圖通過(guò)本文的介紹讓大家對(duì)LevelDB有個(gè)整體的認(rèn)識(shí)并能夠使用熊尉。
設(shè)計(jì)思路
做存儲(chǔ)的同學(xué)都很清楚，對(duì)于普通機(jī)械磁盤順序?qū)懙男阅芤入S機(jī)寫大很多掌腰。比如對(duì)于15000轉(zhuǎn)的SAS盤，4K寫IO齿梁， 順序?qū)懺?00MB/s左右，而隨機(jī)寫性能可能只有1MB/s左右勺择。而LevelDB的設(shè)計(jì)思想正是利用了磁盤的這個(gè)特性。
LevelDB的數(shù)據(jù)是存儲(chǔ)在磁盤上的稿辙，采用LSM-Tree的結(jié)構(gòu)實(shí)現(xiàn)。LSM-Tree將磁盤的隨機(jī)寫轉(zhuǎn)化為順序?qū)懥诖ⅲ瑥亩蟠筇岣吡藢懰俣染稍搿榱俗龅竭@一點(diǎn)LSM-Tree的思路是將索引樹結(jié)構(gòu)拆成一大一小兩顆樹，較小的一個(gè)常駐內(nèi)存萌壳，較大的一個(gè)持久化到磁盤，他們共同維護(hù)一個(gè)有序的key空間袱瓮。寫入操作會(huì)首先操作內(nèi)存中的樹，隨著內(nèi)存中樹的不斷變大绊起，會(huì)觸發(fā)與磁盤中樹的歸并操作燎斩，而歸并操作本身僅有順序?qū)憽Ｈ缦聢D所示：
圖中2個(gè)紅色區(qū)域是要進(jìn)行歸并的數(shù)據(jù)塊笋鄙，計(jì)算出順序后會(huì)存儲(chǔ)到如圖下面的磁盤空間怪瓶，而這種存儲(chǔ)方式是追加式的，也就是順序?qū)懭氪疟P洗贰。
隨著數(shù)據(jù)的不斷寫入，磁盤中的樹會(huì)不斷膨脹许布，為了避免每次參與歸并操作的數(shù)據(jù)量過(guò)大绎晃，以及優(yōu)化讀操作的考慮蜜唾，LevelDB將磁盤中的數(shù)據(jù)又拆分成多層灵妨，每一層的數(shù)據(jù)達(dá)到一定容量后會(huì)觸發(fā)向下一層的歸并操作落竹，每一層的數(shù)據(jù)量比其上一層成倍增長(zhǎng)货抄。這也就是LevelDB的名稱來(lái)源。
主要特性
下面是LevelDB官方對(duì)其特性的描述积暖，主要包括如下幾點(diǎn)：
- key和value都是任意長(zhǎng)度的字節(jié)數(shù)組怪与；
- entry（即一條K-V記錄）默認(rèn)是按照key的字典順序存儲(chǔ)的，當(dāng)然開發(fā)者也可以重載這個(gè)排序函數(shù)；
- 提供的基本操作接口：Put()存淫、Delete()、Get()桅咆、Batch()坞笙；
- 支持批量操作以原子操作進(jìn)行；
- 可以創(chuàng)建數(shù)據(jù)全景的snapshot(快照)籍茧，并允許在快照中查找數(shù)據(jù)梯澜；
- 可以通過(guò)前向（或后向）迭代器遍歷數(shù)據(jù)（迭代器會(huì)隱含的創(chuàng)建一個(gè)snapshot）；
- 自動(dòng)使用Snappy壓縮數(shù)據(jù)腊徙；
- 可移植性；
編譯和使用
LevelDB的編譯也是比較簡(jiǎn)單的螟蝙，可以從官網(wǎng)直接克隆代碼民傻。https://github.com/google/leveldb，具體操作步驟如下(可以參考源代碼中的README文件)：
git clone https://github.com/google/leveldb.git
cd leveldb
mkdir -p build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .
完成上述幾步牵署，就可以編譯出一個(gè)靜態(tài)庫(kù)喧半、一個(gè)動(dòng)態(tài)庫(kù)和一些測(cè)試程序。我們可以自己寫一個(gè)測(cè)試代碼進(jìn)行測(cè)試取具。比如我們?cè)趌eveldb目錄下面創(chuàng)建一個(gè)test目錄扁耐， 然后將靜態(tài)庫(kù)libleveldb.a拷貝進(jìn)來(lái)，然后在其中創(chuàng)建一個(gè)名為test.cpp的文件婉称，文件內(nèi)容如下：
#include <assert.h>
#include <iostream>
#include <sstream>
#include "leveldb/db.h"
using namespace std;
int main(){
leveldb::DB* db;
leveldb::Options options;
options.create_if_missing = true;
//打開一個(gè)數(shù)據(jù)庫(kù)
leveldb::Status status = leveldb::DB::Open(options,"./testdb1",&db);
int count = 0;
//循環(huán)多次，不斷添加內(nèi)容
while (count < 1000) {
std::stringstream keys ;
std::string key;
std::string value = "shuningzhang@itworld123.com";
keys << "itworld123-" << count;
key = keys.str();
status = db->Put(leveldb::WriteOptions(), key, value);//添加內(nèi)容
assert(status.ok());
status = db->Get(leveldb::ReadOptions(), key, &value);//獲取
assert(status.ok());
std::cout<<value<<std::endl;
count ++;
}
delete db; //關(guān)閉數(shù)據(jù)庫(kù)
return 0;
}
測(cè)試程序功能很簡(jiǎn)單悔据，就是向KV數(shù)據(jù)庫(kù)添加1000個(gè)KV數(shù)據(jù)。后續(xù)我們還會(huì)用到這個(gè)程序铐姚，這里了解一下就行肛捍。具體通過(guò)如下命令可以編譯成可執(zhí)行程序。
g++ -o leveldbTest test.cpp libleveldb.a -lpthread -lsnappy
如果運(yùn)行一下該程序拙毫，可以看到在當(dāng)前目錄會(huì)生成一個(gè)名為testbd1的目錄，其中的內(nèi)容如下所示：
整體結(jié)構(gòu)
對(duì)LevelDB有一個(gè)整體的認(rèn)識(shí)之后峭跳，我們分析一下它的架構(gòu)缺前。這里面有一個(gè)重要的概念（或者模塊）需要理解，分別是內(nèi)存數(shù)據(jù)的Memtable拯刁，分層數(shù)據(jù)存儲(chǔ)的SST文件逝段，版本控制的Manifest、Current文件奶躯，以及寫Memtable前的WAL。這里簡(jiǎn)單介紹各個(gè)組件的作用和在整個(gè)結(jié)構(gòu)中的位置账嚎，更詳細(xì)的介紹本號(hào)將另外寫文章進(jìn)行介紹儡蔓。在介紹之前，我們先看一下整體架構(gòu)示意圖：
如圖3所示，對(duì)于寫數(shù)據(jù)檩小，接口會(huì)同時(shí)寫入內(nèi)存表（MemTable）和日志中。當(dāng)內(nèi)存表達(dá)到閾值時(shí)，內(nèi)存表凍結(jié)卵惦，變?yōu)镮mmutable MemTable瓦戚，并將數(shù)據(jù)寫入SST表中，其中SST表時(shí)在磁盤上的文件较解。下面是涉及到主要模塊的簡(jiǎn)單介紹：
- Memtable：內(nèi)存數(shù)據(jù)結(jié)構(gòu)，跳表實(shí)現(xiàn)啡捶，新的數(shù)據(jù)會(huì)首先寫入這里；
- Log文件：寫Memtable前會(huì)先寫Log文件奸焙，Log通過(guò)append的方式順序?qū)懭搿og的存在使得機(jī)器宕機(jī)導(dǎo)致的內(nèi)存數(shù)據(jù)丟失得以恢復(fù)与帆；
- Immutable Memtable：達(dá)到Memtable設(shè)置的容量上限后，Memtable會(huì)變?yōu)镮mmutable為之后向SST文件的歸并做準(zhǔn)備勿她，顧名思義茶凳，Immutable Mumtable不再接受用戶寫入，同時(shí)會(huì)有新的Memtable生成筒狠；
- SST文件：磁盤數(shù)據(jù)存儲(chǔ)文件。分為L(zhǎng)evel 0到Level N多層辩恼，每一層包含多個(gè)SST文件谓形；單層SST文件總量隨層次增加成倍增長(zhǎng)；文件內(nèi)數(shù)據(jù)有序聘萨；其中Level0的SST文件由Immutable直接Dump產(chǎn)生，其他Level的SST文件由其上一層的文件和本層文件歸并產(chǎn)生米辐；SST文件在歸并過(guò)程中順序?qū)懮桑珊髢H可能在之后的歸并中被刪除翘贮，而不會(huì)有任何的修改操作。
- Manifest文件： Manifest文件中記錄SST文件在不同Level的分布锨能，單個(gè)SST文件的最大最小key芍耘，以及其他一些LevelDB需要的元信息。
- Current文件: 從上面的介紹可以看出齿穗，LevelDB啟動(dòng)時(shí)的首要任務(wù)就是找到當(dāng)前的Manifest，而Manifest可能有多個(gè)跺株。Current文件簡(jiǎn)單的記錄了當(dāng)前Manifest的文件名脖卖，從而讓這個(gè)過(guò)程變得非常簡(jiǎn)單。
寫流程簡(jiǎn)析
了解了整體流程和架構(gòu)后袖扛，我們分析兩個(gè)基本的流程，也就是LevelDB的寫流程和讀流程蛆封。我們這里首先分析一下寫流程勾栗，畢竟要先有數(shù)據(jù)后才能讀數(shù)據(jù)。
LevelDB的寫操作包括設(shè)置key-value和刪除key兩種砸讳。需要指出的是這兩種情況在LevelDB的處理上是一致的界牡，刪除操作其實(shí)是向LevelDB插入一條標(biāo)識(shí)為刪除的數(shù)據(jù)。下面我們先看一下LevelDB插入值的整體流程宿亡，具體如圖4所示。
具體代碼請(qǐng)自行閱讀烈钞，本文不貼過(guò)多的代碼。這里需要重點(diǎn)說(shuō)明的是DBImpl::Write函數(shù)，如圖5是該函數(shù)的代碼片段臭脓，從這段代碼中我們可以很清楚的看到數(shù)據(jù)被分別寫入日志和內(nèi)存2個(gè)地方。其它代碼都比較簡(jiǎn)單来累，大家請(qǐng)自行對(duì)照流程圖閱讀。
讀流程簡(jiǎn)析
讀流程要比寫流程簡(jiǎn)單一些葫录，核心代碼邏輯如圖6所示米同。首先摔竿，生成內(nèi)部查詢所用的Key，該Key是由用戶請(qǐng)求的UserKey拼接上Sequence生成的熬苍。其中Sequence可以用戶提供或使用當(dāng)前最新的Sequence，LevelDB可以保證僅查詢?cè)谶@個(gè)Sequence之前的寫入柴底。然后粱胜，用生成的Key，依次嘗試從 Memtable凿歼，Immtable以及SST文件中讀取，直到找到答憔。
- 從SST文件中查找需要依次嘗試在每一層中讀取虐拓，得益于Manifest中記錄的每個(gè)文件的key區(qū)間傲武，我們可以很方便的知道某個(gè)key是否在文件中城榛。Level0的文件由于直接由Immutable Dump 產(chǎn)生，不可避免的會(huì)相互重疊狠持，所以需要對(duì)每個(gè)文件依次查找瞻润。對(duì)于其他層次，由于歸并過(guò)程保證了其互相不重疊且有序绍撞，二分查找的方式提供了更好的查詢效率。
- 可以看出同一個(gè)Key出現(xiàn)在上層的操作會(huì)屏蔽下層的章贞。也因此刪除Key時(shí)只需要在Memtable壓入一條標(biāo)記為刪除的條目即可非洲。被其屏蔽的所有條目會(huì)在之后的歸并過(guò)程中清除。
好了里覆，今天就先到這缆瓣，后續(xù)我們?cè)谏钊氲慕榻BLevelDB的其它部分的，并且逐步深入隧甚，理解其內(nèi)部的精髓渡冻。
關(guān)注微信公眾號(hào)，獲取信息更及時(shí)： itworld123
