前言

之前整理的 Bigtable 論文中文翻譯中提及了 SSTable，但在該論文中并沒有給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。在查詢相關(guān)分布式的書籍后，找到了 SSTable 的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)將其作為筆記記錄下來。以下內(nèi)容源自《大規(guī)模分布式存儲系統(tǒng)》。

?

哪里用到了 SSTable？

Bigtable 采用?LSM 樹存儲引擎。數(shù)據(jù)寫入時(shí)需要先寫操作日志，成功后應(yīng)用到內(nèi)存中的 MemTable 中，寫操作日志是往磁盤中的日志文件追加數(shù)據(jù)，很好地利用了磁盤設(shè)備的特性。當(dāng)內(nèi)存中的 MemTable 達(dá)到一定大小，需要將 MemTable 轉(zhuǎn)儲（Dump）到磁盤中生成 SSTable 文件。由于數(shù)據(jù)同時(shí)存在 MemTable 和可能多個 SSTable 中，讀取操作需要按從舊到新的時(shí)間順序合并 SSTable 和內(nèi)存中的 MemTable 數(shù)據(jù)。數(shù)據(jù)在 SSTable 中連續(xù)存放，因此可以同時(shí)滿足隨機(jī)讀取和順序讀取兩種需求。為了防止磁盤中的 SSTable 文件過多，需要定時(shí)將多個 SSTable 通過 Compaction 過程合并（Merge）成一個 SSTable ，從而減少后續(xù)讀操作需要讀取的文件個數(shù)。一般情況下，如果寫操作比較少，我們總是能夠使得對每一份數(shù)據(jù)同時(shí)只存在一個 SSTable 和一個 MemTable，也就是說，隨機(jī)讀取和順序讀取都只需要訪問一次磁盤。插入、刪除、更新、增加等操作在 Merge-Dump 中都看成一回事，除了最早生成的 SSTable 外，SSTable 中記錄的只是操作，而不是最終的結(jié)果，需要等到讀取時(shí)才合并到最終結(jié)果。

?

Compaction 策略

Bigtable中包含三種 Compaction 策略：Minor Compaction、Merging Compaction 和 Major Compaction。其中，Minor Compaction 把內(nèi)存中的?MemTable 轉(zhuǎn)儲到 GFS 中，Merging Compaction 和 Major ?Compaction 合并 GFS 中的多個 SSTable 文件生成一個更大的 SSTable。Minor ?Compaction 主要是為了防止內(nèi)存占用過多，Merging 和 Major Compaction 則是為了防止讀取文件個數(shù)過多。Merging Compaction 和 Major?Compaction?的區(qū)別在于?Major?Compaction?會合并所有的 SSTable 文件和內(nèi)存中的 MemTable，生成最終結(jié)果；而?Merging Compaction?生成的 SSTable 文件可能包含一些操作，比如刪除、增加等。

?

SSTable 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)在 SSTable 中按照主鍵有序存儲，每個 SSTable 由若干個大小相近的數(shù)據(jù)塊組成，每個數(shù)據(jù)塊包含若干行。數(shù)據(jù)塊的大小一般在8~64KB之間，允許用戶配置。Tablet Server 的緩存包括兩種：塊緩存和行緩存。其中，塊緩存的單位為 SSTable 中的數(shù)據(jù)塊，行緩存的單位為一行記錄。隨機(jī)讀取時(shí)，首先查找行緩存；如果行緩存不命中，接著再查找塊緩存。另外，Bigtable 還支持布隆過濾器（Bloom Filter），如果讀取的數(shù)據(jù)行在 SSTable 中不存在，可以通過布隆過濾器發(fā)現(xiàn)，從而避免一次讀取 GFS 文件操作。注：布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識別率和刪除困難。

SSTable 中的數(shù)據(jù)按主鍵排序后存放在連續(xù)的數(shù)據(jù)塊（Block）中，塊之間也有序。接著，存放數(shù)據(jù)塊索引，由每個 Block 最后一行的主鍵組成，由于數(shù)據(jù)查詢中的 Block 定位。接著，存放布隆過濾器和表格的 Schema 信息。最后，存放固定大小的 Trailer 以及 Trailer 的偏移位置。

查找 SSTable 時(shí)，首先從子表的索引信息中讀取 SSTable Trailer 的偏移位置，接著獲取 Trailer 信息。根據(jù) Trailer 中記錄的信息，可以獲取塊索引的大小和偏移，從而將整個塊索引加載到內(nèi)存中。根據(jù)塊索引記錄的每個 Block 的最后一行的主鍵，可以通過二分查找定位到查找的 Block。最后將 Block 加載到內(nèi)存中，通過二分查找 Block 中記錄的行索引查找到具體某一行。本質(zhì)上看，SSTable 是一個兩級索引結(jié)構(gòu)：塊索引以及行索引；而整個 ChunkServer 是一個三級索引結(jié)構(gòu)：子表索引、塊索引以及行索引。

SSTable 分為兩種格式：稀疏格式和稠密格式。對于稀疏格式，某些列可能存在，也可能不存在，因此，每一行只存儲包含實(shí)際值的列，每一列存儲的內(nèi)容為：<列ID，列值>(<Column ID, Column Value>); 而稠密格式中每一行都需要存儲所有列，每一列只需要存儲列值，不需要存儲列 ID，這是因?yàn)榱?ID 可以從表格 Schema 中獲取。

假設(shè)有一張表格包含 10 列，列 ID 為 1~10，表格中有一行的數(shù)據(jù)內(nèi)容為：

那么，采用稀疏格式存儲，內(nèi)容為：<2, 20>,<3, 30>,<5, 50>,<7, 70>,<8, 80>；如果采用稠密格式存儲，內(nèi)容為：null，20，30，null，50，null，70，80，null，null。

ChunkServer 中的 SSTable 為稠密格式，而 UpdateServer 中的 SSTable 為稀疏格式，且存儲了多張表格的數(shù)據(jù)。另外，SSTable 支持列組，將同一個列組下的多個列的內(nèi)容存儲在一起。列組是一種行列混合存儲模式，將每一行的所有列分成多個組（稱為列組），每個列組內(nèi)部按行存儲。

當(dāng)一個 SSTable 中包含多個表格/列組時(shí)，數(shù)據(jù)按照[表格ID，列組ID，行主鍵]?([table_id, column group id, row_key]) 的形式有序存儲。

總結(jié)

以上是生活随笔為你收集整理的SSTable数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。