你是什么鬼靡努？
leveldb : 老子是一個單機(jī)的KV數(shù)據(jù)庫，適合寫多讀少晓折，支持持久化惑朦，支持故障恢復(fù)，咋樣漓概，牛逼吧漾月？
我：聽不懂！
leveldb : 老子就是一個main函數(shù)胃珍，管理一堆文件梁肿，給你存數(shù)據(jù)讀數(shù)據(jù)！
我：哦堂鲜！
開篇來個簡單傻逼的對話栈雳，不過卻道出數(shù)據(jù)庫的本質(zhì)。數(shù)據(jù)庫就是以格式化數(shù)據(jù)存儲起來然后提供增刪改查功能而已缔莲，只不過數(shù)據(jù)量大了之后事情變得有點(diǎn)復(fù)雜哥纫。那么leveldb也是這樣一個東西。leveldb提供的是KV格式的存儲痴奏，支持二進(jìn)制數(shù)據(jù)蛀骇，那么leveldb是如何實(shí)現(xiàn)的這個的呢？
讓我們從上層開始講起!
數(shù)據(jù)之旅
既然是KV數(shù)據(jù)庫读拆，那么開始我們肯定會有個叫DB的對象擅憔。這個叫DB的對象提供啥？簡化可以理解三個接口：
1. DB.Put(key, value)
2. DB.Get(key)
3. DB.Del(key)
簡單吧檐晕！這讓你想起啥暑诸？HashMap蚌讼！對，一樣的功能个榕，卻復(fù)雜了千百倍篡石。要實(shí)現(xiàn)一個完善的數(shù)據(jù)庫系統(tǒng)，還需要考慮很多東西西采，例如數(shù)據(jù)格式凰萨，例如持久化，例如高性能械馆。當(dāng)然胖眷，這些接下來慢慢聊，我們可以暫且忘記這么多煩惱霹崎，先記得這個HashMap的簡單玩具雛形珊搀。
這三個簡單的接口下面有啥啥東西？這時候應(yīng)該用一張圖說明：
當(dāng)我們寫入一個KV數(shù)據(jù)的時候仿畸，KV會經(jīng)過三個
table和一個log食棕。寫入數(shù)據(jù)的流程是
- KV寫操作會寫到
log文件中，順序?qū)?/code>错沽，做持久化（系統(tǒng)崩潰會從log文件中恢復(fù),log文件也是按照一定格式的二進(jìn)制數(shù)據(jù)）- 寫到log文件中后會寫入
memtable（一個叫跳躍表的數(shù)據(jù)結(jié)構(gòu)）- 之后write操作就返回成功了簿晓。
經(jīng)過上面幾步我們可以保證數(shù)據(jù)一定不會丟失了，內(nèi)存memtable丟失的數(shù)據(jù)會讀取log的操作記錄重跑一遍千埃，數(shù)據(jù)就恢復(fù)了憔儿。但是接下來數(shù)據(jù)還會被持久到磁盤中。
- 當(dāng)memtable的大小達(dá)到一個上限放可，那么memtable會變成
Immutale memtable谒臼。這兩個table的數(shù)據(jù)結(jié)構(gòu)是一樣的,都是跳躍表，只不過后者是只讀的耀里。- 這時候會產(chǎn)生一個新的memtable來支持新的寫操作
- Imutable memtable的內(nèi)容會定期刷到磁盤蜈缤，然后清楚對應(yīng)的log文件，生成新的log文件冯挎。
- 磁盤中數(shù)據(jù)的存儲格式叫sstable底哥。
由上面七步我們知道數(shù)據(jù)經(jīng)歷了memtable, imutable memtable, sstable三個table。數(shù)據(jù)的存儲格式幾乎說明了整個數(shù)據(jù)庫的精髓房官，所以這三個數(shù)據(jù)結(jié)構(gòu)后面都會詳細(xì)講解趾徽！現(xiàn)在我們先感性認(rèn)識一下數(shù)據(jù)流程以及l(fā)eveldb如何保證數(shù)據(jù)持久化的。
leveldb： 那么現(xiàn)在可以回答數(shù)據(jù)持久化是如何實(shí)現(xiàn)的嗎翰守？
我：嗯孵奶，好像跟一個log文件有關(guān)！
leveldb: 對頭蜡峰，一次寫KV操作需要一次磁盤的順序?qū)懀╨og文件）和一次內(nèi)存寫（寫入metable）了袁，所以寫效率是非常高的朗恳。如果內(nèi)存中數(shù)據(jù)丟失，我們會讀取log文件的操作指令重跑一遍早像，數(shù)據(jù)就可以恢復(fù)了僻肖。當(dāng)KV數(shù)據(jù)到達(dá)sstable之后肖爵，舊的log文件會被刪除并且產(chǎn)生新的log文件卢鹦。所以我們可以保證數(shù)據(jù)不丟失！
為啥叫l(wèi)eveldb劝堪？
還記得我們上面講那三個table嗎冀自？
1. memtable
2. Imuable memtable
3. sstable（ Sorted String Table）
其中1和2都是跳躍表，然而我們還沒講到3sstable是什么數(shù)據(jù)結(jié)構(gòu)秒啦？sstable什么鬼熬粗？就是傳說中g(shù)oogle三大論文之一的Bigtable中的那個sstable。這個東西大概長這樣：
圖中紅色框部分就是他的樣子余境。
level0是由Imuabletable memtable直接dump到磁盤中的驻呐，level1是由level0經(jīng)過compaction獲得，level2是由level1經(jīng)過compaction獲得芳来，以此類推含末。其中每個文件后綴為.sst, 每個level中的文件數(shù)都是有限制的，超過了限制則會被compaction到更高level的層次上去即舌，所以這個東西叫l(wèi)eveldb佣盒。其中每一個level符合以下規(guī)則：
1. level0中的單個文件（sst）是有序的，但是文件與文件之間是無序的并且有可能有重合的key
2. level 1 ~ level n 每一個level中在自己level中都是全局有序的
3. mainifest文件中包含了每一個sst文件的最小key和最大key顽聂，方便查找
上面只是簡單講解以下整體結(jié)構(gòu)肥惭，后面會深入其細(xì)節(jié)。但是在那之前紊搪，先建立一個宏觀感受是非常重要的蜜葱。
讀
前面我們講解了數(shù)據(jù)的存儲整體結(jié)構(gòu)，那么理解數(shù)據(jù)是怎么被查找的就非常簡單了耀石。查找依次經(jīng)過：
1. memtable
2. Imuable memtable
3. level 0
4. level 1
......
上面步驟非常清晰牵囤。首先查找會先經(jīng)過memtable查找，找不到就依次按順序往下找娶牌，一直找不到就返回empty了奔浅。當(dāng)然，中間有很多細(xì)節(jié)優(yōu)化诗良，這里先不深入去理解汹桦，例如會通過布隆算法過濾掉不存在的key。后面講到filter的時候會深入講解鉴裹。
刪除
數(shù)據(jù)庫的數(shù)據(jù)當(dāng)以一種格式化存儲在一起舞骆，要刪掉某部分就要移動剩下部分往前移動钥弯，這是代價很大的。所以：
leveldb沒有實(shí)際的刪除操作督禽，就是write一個刪除標(biāo)記和key進(jìn)去
啥意思脆霎？我們都知道所有key的插入都是時間有序的，從memtable到level n一路飛奔狈惫，從不回頭睛蛛。
所以我們假如我們添加了key為name, value 為戈風(fēng)的數(shù)據(jù)進(jìn)去之后，我們要刪除key為name的記錄胧谈，我們只需要再插入一條 name del（標(biāo)志）忆肾，這樣我們查找的時候就會先遇到name del表示key已經(jīng)被刪除，返回empty菱肖。
除了這個時間有序之外客冈，在level n compaction到level n + 1的時候如果發(fā)現(xiàn)有刪除的key，這時候就會真正刪除它稳强。
尾記
從前面的講述场仲，我相信我們應(yīng)該心中對leveldb有了一個大概的印象，下面我們會慢慢把印象具體起來退疫，把細(xì)節(jié)豐富出來渠缕，構(gòu)造一個3d立體的理解結(jié)構(gòu)。那么蹄咖，前面涉及到了幾個leveldb的模塊呢褐健？
1. memtable
2. Imuable memtable（其實(shí)我跟1是親兄弟啦）
3. sstable
4. log
5. filter
這幾個模塊就是leveldb的重中之重了。在有了一個大框架之后澜汤，我們需要進(jìn)入一點(diǎn)細(xì)節(jié)了蚜迅。好了，本章到此為止俊抵！
