前文回顧
SSTable 全稱 Sorted String Table，顧名思義，里面的 key-value 都是有序保存的患整。除了兩個(gè) MemTable砸民，LevelDB 中的大部分?jǐn)?shù)據(jù)是以 SSTable 的形式保存在外存上。
SSTable 由 compaction 生成：
- Minor Compaction：一個(gè) MemTable 直接 dump 成 level-0 的一個(gè) SSTable浓恶。
- Major Compaction：多個(gè) SSTable 進(jìn)行合并玫坛、重整，生成 1～多個(gè) SSTable包晰。
SSTable 的格式
在一個(gè) SSTable 中湿镀，文件末尾的 Footer 是定長(zhǎng)的，其他數(shù)據(jù)都被劃分成一個(gè)個(gè)變長(zhǎng)的 block：index block伐憾、metaindex block勉痴、meta blocks、data blocks树肃。
Footer
Footer 的大小為 48 字節(jié)蒸矛，內(nèi)容是一個(gè) 8 字節(jié)的 magic number 和兩個(gè) BlockHandle —— index handle 和 meta index handle，index handle 指向 index block胸嘴，meta index handle 指向 meta index block雏掠。BlockHandle 相當(dāng)于一個(gè) block 的“指針”，由這個(gè) block 的 offset(varint64) 和 size(varint64) 組成劣像。由于采用 varint64 進(jìn)行編碼乡话，每個(gè) varint64 最多占用 10 字節(jié)，所以一個(gè) BlockHandle 最多占用 20 字節(jié)驾讲。因?yàn)?BlockHandle 是定長(zhǎng)蚊伞，而 BlockHandle 編碼的結(jié)果是變長(zhǎng)的，所以 Footer 編碼的時(shí)候需要進(jìn)行 padding吮铭。Index Block
Index block 中的每條 key-value 指向一個(gè) data block时迫。value 比較簡(jiǎn)單直接，就是對(duì)應(yīng)的 data block 的 BlockHandle谓晌。key 是一個(gè)大于等于當(dāng)前 data block 中最大的 key 且小于下一個(gè) block 中最小的 key掠拳，這一塊的邏輯可以參考 FindShortestSeparator 的調(diào)用和實(shí)現(xiàn)。這樣做是為了減小 index block 的體積纸肉，畢竟我們希望程序運(yùn)行的時(shí)候溺欧，index block 被盡可能 cache 在內(nèi)存中喊熟。Meta Index Block
Meta index block 中的每條 key-value 指向一個(gè) meta block。目前 LevelDB 中只有一個(gè) meta block姐刁，保存的是這個(gè) SSTable 中的 key 組成的 bloom filter芥牌。Data Block
Data block 是實(shí)際的 key-value 數(shù)據(jù)。
Block
Index block聂使、meta index block壁拉、data block 都是通過(guò) BlockBuilder 來(lái)生成，通過(guò) Block 來(lái)讀取的柏靶。最簡(jiǎn)單的方式弃理，block 里面只需要將一個(gè)個(gè) key-value 有序保存。但是為了節(jié)省空間屎蜓，LevelDB 在 block 的內(nèi)部實(shí)現(xiàn)了前綴壓縮痘昌。
前綴壓縮利用了 key 的有序性（前綴相同的有序 key 會(huì)聚集在一起）對(duì) key 進(jìn)行壓縮，每個(gè) key 與前一個(gè) key 相同的前綴部分可以不用保存炬转。讀取的時(shí)候再根據(jù)規(guī)則進(jìn)行解碼即可辆苔。
LevelDB 將 block 的一個(gè) key-value 稱為一條 entry。每條 entry 的格式如下：
- shared_bytes：和前一個(gè) key 相同的前綴長(zhǎng)度返吻。
- unshared_bytes：和前一個(gè) key不同的后綴部分的長(zhǎng)度姑子。
- value_length：value 數(shù)據(jù)的長(zhǎng)度。
- key_delta：和前一個(gè) key不同的后綴部分测僵。
- value：value 數(shù)據(jù)街佑。
一個(gè) block 的數(shù)據(jù)格式如下：
- restarts：在 LevelDB 中，默認(rèn)每 16 個(gè) key 就會(huì)重新計(jì)算前綴壓縮捍靠，重新開(kāi)始計(jì)算前綴壓縮到第一個(gè) key 稱之為重啟點(diǎn)（restart point）沐旨。restarts 數(shù)組記錄了這個(gè) block 中所有重啟點(diǎn)的 offset。
- num_restarts：是 restarts 數(shù)組的長(zhǎng)度榨婆。
在 block 中查找一個(gè) key（Block::Iter::Seek）：
Filter
Meta block（bloom filter）由 FilterBlockBuilder 來(lái)生成谊迄，通過(guò) FilterBlockReader 來(lái)讀取。
后面會(huì)單獨(dú)寫一篇介紹 filter烟央。
