作為一個(gè)存儲(chǔ)引擎步鉴，數(shù)據(jù)存儲(chǔ)自然是LevelDB重中之重的需求。我們已經(jīng)在庖丁解LevelDB之概覽中介紹了Leveldb的使用流程，以及數(shù)據(jù)在Memtable泉孩，Immutable，SST文件之間的流動(dòng)眨补。本文就將詳細(xì)的介紹LevelDB的數(shù)據(jù)存儲(chǔ)方式，包括數(shù)據(jù)在不同介質(zhì)中的存儲(chǔ)方式旗笔，數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)思路。

Memtable

Memtable對(duì)應(yīng)Leveldb中的內(nèi)存數(shù)據(jù)离例，LevelDB的寫入操作會(huì)直接將數(shù)據(jù)寫入到Memtable后返回换团。讀取操作又會(huì)首先嘗試從Memtable中進(jìn)行查詢。我們對(duì)Memtable的需求如下：

• 常駐內(nèi)存宫蛆；

• 可能會(huì)有頻繁的插入和查詢操作艘包；
• 不會(huì)有刪除操作；
• 需要支持阻寫狀態(tài)下的遍歷操作（Immutable的Dump過程）

LevelDB采用跳表SkipList實(shí)現(xiàn)耀盗，在給提供了O(logn)的時(shí)間復(fù)雜度的同時(shí)想虎，又非常的易于實(shí)現(xiàn)：

跳表

SkipList中單條數(shù)據(jù)存放一條Key-Value數(shù)據(jù)，定義為：

SkipList Node := InternalKey + ValueString
InternalKey := KeyString + SequenceNum + Type
Type := kDelete or kValue
ValueString := ValueLength + Value
KeyString := UserKeyLength + UserKey

Log

數(shù)據(jù)寫入Memtable之前叛拷，會(huì)首先順序?qū)懭隠og文件舌厨，以避免數(shù)據(jù)丟失。LevelDB實(shí)例啟動(dòng)時(shí)會(huì)從Log文件中恢復(fù)Memtable內(nèi)容忿薇。所以我們對(duì)Log的需求是：

• 磁盤存儲(chǔ)
• 大量的Append操作
• 沒有刪除單條數(shù)據(jù)的操作
• 遍歷的讀操作

LevelDB首先將每條寫入數(shù)據(jù)序列化為一個(gè)Record裙椭，單個(gè)Log文件中包含多個(gè)Record。同時(shí)署浩，Log文件又劃分為固定大小的Block單位揉燃，并保證Block的開始位置一定是一個(gè)新的Record。這種安排使得發(fā)生數(shù)據(jù)錯(cuò)誤時(shí)筋栋，最多只需丟棄一個(gè)Block大小的內(nèi)容炊汤。顯而易見地，不同的Record可能共存于一個(gè)Block弊攘，同時(shí)抢腐，一個(gè)Record也可能橫跨幾個(gè)Block。

Log format

Block := Record * N
Record := Header + Content
Header := Checksum + Length + Type
Type := Full or First or Midder or Last

Log文件劃分為固定長度的Block襟交，每個(gè)Block中包含多個(gè)Record迈倍；Record的前56個(gè)字節(jié)為Record頭，包括32位checksum用做校驗(yàn)捣域，16位存儲(chǔ)Record實(shí)際內(nèi)容數(shù)據(jù)的長度授瘦，8位的Type可以是Full、First竟宋、Middle或Last中的一種提完，表示該Record是否完整的在當(dāng)前的Block中，如果不是則通過Type指明其前后的Block中是否有當(dāng)前Record的前驅(qū)后繼丘侠。

SST文件

SST文件是Leveldb中數(shù)據(jù)的最終存儲(chǔ)角色徒欣，劃分為不同的Level，Level 0的SST文件由Memtable直接Dump產(chǎn)生蜗字。其他層次的SST文件則由其上一層文件在Compaction過程中歸并產(chǎn)生打肝。讀請(qǐng)求時(shí)可能會(huì)從SST文件中查找某條數(shù)據(jù)脂新。我們對(duì)SST文件的需求是：

• 支持順序?qū)懖僮?/li>
• 支持遍歷操作
• 查找操作

我們將從物理格式和邏輯格式兩個(gè)方面來介紹SST文件中的數(shù)據(jù)存儲(chǔ)方式。所謂物理格式指的是數(shù)據(jù)的存儲(chǔ)和解析方式粗梭；利用確定的物理格式争便，我們可以存儲(chǔ)不同意義的數(shù)據(jù)，這就是數(shù)據(jù)的邏輯格式断医。

物理格式

LevelDB將SST文件定義為Table滞乙，每個(gè)Table又劃分為多個(gè)連續(xù)的Block，每個(gè)Block中又存儲(chǔ)多條數(shù)據(jù)Entry：

SST物理格式

可以看出鉴嗤，單個(gè)Block作為一個(gè)獨(dú)立的寫入和解析單位斩启，會(huì)在其末尾存儲(chǔ)一個(gè)字節(jié)的Type和4個(gè)字節(jié)的Crc，其中Type記錄的是當(dāng)前Block的數(shù)據(jù)壓縮策略醉锅，而Crc則存儲(chǔ)Block中數(shù)據(jù)的校驗(yàn)信息兔簇。Block中每條數(shù)據(jù)Entry是以Key-Value方式存儲(chǔ)的，并且是按Key有序存儲(chǔ)硬耍，Leveldb很巧妙了利用了有序數(shù)組相鄰Key可能有相同的Prefix的特點(diǎn)來減少存儲(chǔ)數(shù)據(jù)量垄琐。如上圖所示，每個(gè)Entry只記錄自己的Key與前一個(gè)Entry Key的不同部分经柴，例如要順序存儲(chǔ)Key值“apple”和“applepen”的兩條數(shù)據(jù)狸窘，這里第二個(gè)Entry中只需要存儲(chǔ)“pen”的信息。在Entry開頭記錄三個(gè)長度值口锭，分別是當(dāng)前Entry和其之前Entry的公共Key Prefix長度、當(dāng)前Entry Key自有Key部分的長度和Value的長度介杆。通過這些長度信息和其后相鄰的特有Key及Value內(nèi)容鹃操，結(jié)合前一條Entry的Key內(nèi)容，我們可以方便的獲得當(dāng)前Entry的完整Key和Value信息春哨。

這種方式非常好的減少了數(shù)據(jù)存儲(chǔ)荆隘，但同時(shí)也引入一個(gè)風(fēng)險(xiǎn)，如果最開頭的Entry數(shù)據(jù)損壞赴背，其后的所有Entry都將無法恢復(fù)椰拒。為了降低這個(gè)風(fēng)險(xiǎn)，leveldb引入了重啟點(diǎn)凰荚，每隔固定條數(shù)Entry會(huì)強(qiáng)制加入一個(gè)重啟點(diǎn)燃观，這個(gè)位置的Entry會(huì)完整的記錄自己的Key，并將其shared值設(shè)置為0便瑟。同時(shí)缆毁，Block會(huì)將這些重啟點(diǎn)的偏移量及個(gè)數(shù)記錄在所有Entry后邊的Tailer中。

邏輯格式

Table中不同的Block物理上的存儲(chǔ)方式一致到涂，如上文所示脊框，但在邏輯上可能存儲(chǔ)不同的內(nèi)容颁督，包括存儲(chǔ)數(shù)據(jù)的Block，存儲(chǔ)索引信息的Block浇雹，存儲(chǔ)Filter的Block：

SST邏輯格式

• Footer：為于Table尾部沉御，記錄指向Metaindex Block的Handle和指向Index Block的Handle。需要說明的是Table中所有的Handle是通過偏移量Offset以及Size一同來表示的昭灵，用來指明所指向的Block位置吠裆。Footer是SST文件解析開始的地方，通過Footer中記錄的這兩個(gè)關(guān)鍵元信息Block的位置虎锚，可以方便的開啟之后的解析工作硫痰。另外Footer種還記錄了用于驗(yàn)證文件是否為合法SST文件的常數(shù)值Magicnum。

• Index Block：記錄Data Block位置信息的Block窜护，其中的每一條Entry指向一個(gè)Data Block效斑，其Key值為所指向的Data Block最后一條數(shù)據(jù)的Key，Value為指向該Data Block位置的Handle?柱徙。

• Metaindex Block：與Index Block類似缓屠，由一組Handle組成，不同的是這里的Handle指向的Meta Block护侮。

• Data Block：以Key-Value的方式存儲(chǔ)實(shí)際數(shù)據(jù)敌完，其中Key定義為：

  DataBlock Key := UserKey + SequenceNum + Type
  Type := kDelete or kValue
  

  對(duì)比Memtable中的Key，可以發(fā)現(xiàn)Data Block中的Key并沒有拼接UserKey的長度在UserKey前羊初，這是由于上面講到的物理結(jié)構(gòu)中已經(jīng)有了Key的長度信息滨溉。

• Meta Block：比較特殊的Block，用來存儲(chǔ)元信息长赞，目前LevelDB使用的僅有對(duì)布隆過濾器的存儲(chǔ)晦攒。寫入Data Block的數(shù)據(jù)會(huì)同時(shí)更新對(duì)應(yīng)Meta Block中的過濾器。讀取數(shù)據(jù)時(shí)也會(huì)首先經(jīng)過布隆過濾器過濾得哆。Meta Block的物理結(jié)構(gòu)也與其他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
  

  其中每個(gè)filter節(jié)對(duì)應(yīng)一段Key Range脯颜，落在某個(gè)Key Range的Key需要到對(duì)應(yīng)的filter節(jié)中查找自己的過濾信息，base指定這個(gè)Range的大小贩据。

總結(jié)

本文重點(diǎn)介紹了LevelDB不同介質(zhì)角色中數(shù)據(jù)的存儲(chǔ)方式栋操，并沒有過多的涉及代碼細(xì)節(jié)。因?yàn)橐坏┯辛司唧w的存儲(chǔ)格式饱亮，相關(guān)的代碼不過就是在讀寫兩端的序列化反序列化矾芙。同樣，之后幾篇博客將要介紹的版本控制近上，迭代器蠕啄，緩存等方面的內(nèi)容也都非常緊密的依賴這些存儲(chǔ)格式。

參考

Source Code：https://github.com/google/leveldb

LevelDB Doc: https://raw.githubusercontent.com/google/leveldb/master/doc/table_format.txt

LevelDB Doc: https://raw.githubusercontent.com/google/leveldb/master/doc/log_format.txt

庖丁解LevelDB之概覽: http://catkang.github.io/2017/01/07/leveldb-summary.html