雲原生資料庫-浪潮云溪分散式資料庫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本身48個位元組不能佔用一個磁碟儲存塊.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的方式對齊,浪費儲存空間。
- 浪潮云溪分散式資料庫協議程式碼解析(1)
- 分散式資料庫 Tracing (一)— Opentracing
- BadgerDB原理及分散式資料庫的中應用與優化
- 解析分散式雲原生資料庫中Raft演算法的訊息型別
- io_uring技術在分散式雲原生資料庫中的應用
- 分散式資料庫--SQL優化之Plan Hint
- 深入淺出RedisTimeSeries-分散式資料庫
- 深入淺出RedisTimeSeries-分散式資料庫
- 雲原生分散式資料庫雲平臺技術選擇
- 分散式資料庫Snapshot快照功能實現解密
- 分散式資料庫--ZBConverter資料轉換工具
- 分散式資料庫--ZMP資料遷移平臺
- WAL的概念與實踐分析
- 浪潮云溪資料庫--關於副本的功能特性和使用方法
- 云溪資料庫執行器概述
- Kubernetes使用云溪資料庫簡介
- 雲原生資料庫-浪潮云溪分散式資料庫SST檔案結構
- 云溪雲原生分散式資料庫安全功能以及實現介紹
- 雲原生分散式資料庫事務隔離級別(下)
- 雲原生分散式資料庫事務隔離級別(上)