雲原生資料庫-浪潮云溪分散式資料庫SST檔案結構

LSM tree保證資料庫是有序寫入（memtable-skiplist），起高了寫效能，但是因為其本身的分層結構，犧牲了讀效能（一個key如儲存在了低級別的level，從上到下每一層都要進行查詢，代價極大）。所以，針對讀的效能提升有了很多的優化：bloom filter （高校判讀一個key是否不存在），index-filter（二分查詢，消耗低記憶體的情況下）所以key-value資料。這一些資料庫都需要儲存在SST檔案之中，用來進行k-v資料的有序管理。

 

SST檔案格式概覽

1）Footer ： 固定48位元組，指出 IndexBlock 和 MetaIndexBlock 在檔案中的偏移量資訊，它是元資訊的元資訊，它位於 sstable 檔案的尾部

2）IndexBlock：佔用一個 block 空間，記錄了 DataBlock 相關的元資訊

3）MetaIndexBlock：佔用一個 block 空間，各個元資訊的Block，包括Filter、Properties(整個table的屬性資訊)、Compression dictionary、Range deletion tombstone

4）MetaBlock：可能佔用多個 block空間，儲存布隆過濾器的二進位制資料 及其他元資訊資料

5）DataBlock：可能佔用多個 block空間，儲存實際的資料即鍵值對內容

 

Footer 結構

 

Footer固定48個位元組大小，位於SSTable檔案尾部；MetaBlockIndex和DataBlockIndex的offset和size組成BlockHandlel型別，用於定址MetaBlockIndex和DataBlcokIndex的塊所在的位置，size和offset採用varint變長編碼，以節省空間，offset和size最少佔用1個位元組長度、最多佔用9個位元組長度，因此MetaBlockIndex和DataBlockIndex的offset和size最多佔用4*9=36個位元組，通過padding補齊到40個位元組（8位元組對齊）；比如DataBlockIndex.offset = 64、DataBlockIndex.size=216，表示DataBlockIndex位於SSTable檔案的第64個位元組至280個位元組。

 

Block 結構

5個部分的資料結構，除了 Footer，其他的物理結構都是 Block 形式。每個 Block 對應物理磁碟的一個儲存塊，因此， Block 的大小與磁碟儲存塊的大小一致．這也是Footer放到檔案末尾的原因，Footer本身４８個位元組不能佔用一個磁碟儲存塊．Block 在硬碟上儲存的時候，會在實際資料之後加上5個位元組的額外內容：compression type、crc。

 

Data Block 結構

DataBlcok Key 的儲存採用了字首壓縮機制，字首壓縮，就是對於 key 的相同字首，儘量只儲存一次以節省空間。但是對於 SSTable 來說它並不是對整個 block 的所有 key 進行一次性地字首壓縮，而是設定了很多區段，處於同一區段的 key 進行一次字首壓縮，每個區段的起點就是一個重啟點。字首壓縮機制導致每條記錄需要記住它對應的 key 的共享長度和非共享長度。所 謂 key 的共享長度，是指當前這條記錄的 key 與上一條記錄的 key 公共字首的長 度，非共享長度則是去掉相同部分後的不同部分的長度。這樣當前這條記錄只需要儲存不同的那部分 key 的值即可。

第一部分(Entry)用來儲存key-value資料。由於sstable中所有的key-value對都是嚴格按序儲存的，用了節省儲存空間，並不會為每一對key-value對都儲存完整的key值，而是儲存與上一個key非共享的部分，避免了key重複內容的儲存。每間隔若干個key-value對，將為該條記錄重新儲存一個完整的key。重複該過程（預設間隔值為16），每個重新儲存完整key的點稱之為Restart point。

Restart point的目的是在讀取sstable內容時，加速查詢的過程。由於每個Restart point儲存的都是完整的key值，因此在sstable中進行資料查詢時，可以首先利用restart point點的資料進行鍵值比較，以便於快速定位目標資料所在的區域；當確定目標資料所在區域時，再依次對區間內所有資料項逐項比較key值，進行細粒度地查詢；該思想有點類似於跳錶中利用高層資料迅速定位，底層資料詳細查詢的理念，降低查詢的複雜度。

 

KV 資料儲存結構

• shared key length: 與　restart point 相同的key字首位元組長度．
• unshared key length:　當前key減去restart point 相同字首長度後，剩餘的位元組長度
• value length:　數值的位元組長度
• unshared key content:　key與restart point中的key不相同部分的key內容．
• value: 儲存真實的數值

 

Index Block 結構 

index block包含若干條記錄，每一條記錄代表一個data block的索引資訊，用於快速定位到包含特定key的Data Block；Index Block首先是一個block，因此包含三部分KeyValue、Type（固定1位元組）、CRC檢驗碼（固定4位元組）；Type標識該部分資料是否採用壓縮演算法，CRC是KeyValue + Type的檢驗碼。

一條索引包括以下內容：

• key，取值是大於等於其索引block的最大key，並且小於下一個block的最小key；
• 該data block起始地址在sstable中的偏移量；
• 該data block的大小；

IndexBlock和 DataBlock 一樣，採取了字首壓縮，只不過間隔為2（DataBlock 預設為16）。

 

主要目的是節省空間；假設其索引的block的最大key為"acknowledge"，下一個block最小的key為"apple"，如果DataBlockIndex的key採用其索引block的最大key，佔用長度為len("acknowledge")；採用後一種方式，key值可以為"ad"（"acknowledge" < "ad" < "apple"），長度僅為2，並且檢索效果是一樣的。

 

因為SSTable中的block大小是不固定的，雖然option中可以指定block_size引數，但SSTable中儲存資料時，並未嚴格按照block_size對齊，所以offset和size指的是偏移位元組數和長度位元組數。這樣做主要有兩個原因：  

（1）可以儲存任意長度的key和任意長度的value，而同一個key-value是不能跨block儲存的，極端情況下，比如我們的單個 value 就很大，已經超過了 block_size，那麼對於這種情況，SSTable 就沒法進 行儲存了。所以通常，實際的 Block 大小都是要略微大於 block_size 的；

（2）從另外一個角度看，如果嚴格按照block_size對齊儲存資料，必然有很多block通過補0的方式對齊，浪費儲存空間。