這篇“LevelDB數(shù)據(jù)文件SSTable結(jié)構(gòu)是怎樣的”文章的知識點大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“LevelDB數(shù)據(jù)文件SSTable結(jié)構(gòu)是怎樣的”文章吧。

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比連江網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式連江網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋連江地區(qū)。費用合理售后完善，十載實體公司更值得信賴。

SSTable 文件的內(nèi)容分為 5 個部分，F(xiàn)ooter、IndexBlock、MetaIndexBlock、FilterBlock 和 DataBlock。其中存儲了鍵值對內(nèi)容的就是 DataBlock，存儲了布隆過濾器二進制數(shù)據(jù)的是 FilterBlock，DataBlock 有多個，F(xiàn)ilterBlock 也可以有多個，但是通常最多只有 1 個，之所以設(shè)計成多個是考慮到擴展性，也許未來會支持其它類型的過濾器。另外 3 個部分為管理塊，其中 IndexBlock 記錄了 DataBlock 相關(guān)的元信息，MetaIndexBlock 記錄了過濾器相關(guān)的元信息，而 Footer 則指出 IndexBlock 和 MetaIndexBlock 在文件中的偏移量信息，它是元信息的元信息，它位于 sstable 文件的尾部。下面我們至頂向下挨個分析每個結(jié)構(gòu)

Footer 結(jié)構(gòu)

它的占用空間很小只有 48 字節(jié)，內(nèi)部只存了幾個字段。下面我們用偽代碼來描述一下它的結(jié)構(gòu)

// 定義了數(shù)據(jù)塊的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

struct Footer {
  BlockHandler metaIndexHandler;  // MetaIndexBlock的文件偏移量和長度
  BlockHandler indexHandler; // IndexBlock的文件偏移量和長度
  byte[n] padding;  // 內(nèi)存墊片
  int32 magicHighBits;  // 魔數(shù)后32位
  int32 magicLowBits; // 魔數(shù)前32位
}

Footer 結(jié)構(gòu)的中間部分增加了內(nèi)存墊片，其作用就是將 Footer 的空間撐到 48 字節(jié)。結(jié)構(gòu)的尾部還有一個 64位的魔術(shù)數(shù)字 0xdb4775248b80fb57，如果文件尾部的 8 字節(jié)不是這個數(shù)字說明文件已經(jīng)損壞。這個魔術(shù)數(shù)字的來源很有意思，它是下面返回的字符串的前64bit。

$ echo http://code.google.com/p/leveldb/ | sha1sum
db4775248b80fb57d0ce0768d85bcee39c230b61

IndexBlock 和 MetaIndexBlock 都只有唯一的一個，所以分別使用一個 BlockHandler 結(jié)構(gòu)來存儲偏移量和長度。

Block 結(jié)構(gòu)

除了 Footer 之外，其它部分都是 Block 結(jié)構(gòu)，在名稱上也都是以 Block 結(jié)尾。所謂的 Block 結(jié)構(gòu)是指除了內(nèi)部的有效數(shù)據(jù)外，還會有額外的壓縮類型字段和校驗碼字段。

struct Block {
  byte[] data;
  int8 compressType;
  int32 crcValue;
}

每一個 Block 尾部都會有壓縮類型和循環(huán)冗余校驗碼（crcValue），這會要占去 5 字節(jié)。如果是壓縮類型，塊內(nèi)的數(shù)據(jù) data 會被壓縮。校驗碼會針對壓縮和的數(shù)據(jù)和壓縮類型字段一起計算循環(huán)冗余校驗和。壓縮算法默認是 snappy ，校驗算法是 crc32。

crcValue = crc32(data, compressType)

在下面介紹的所有 Block 結(jié)構(gòu)中，我們不再提及壓縮和校驗碼。

DataBlock 結(jié)構(gòu)

DataBlock 的大小默認是 4K 字節(jié)（壓縮前），里面存儲了一系列鍵值對。前面提到 sst 文件里面的 Key 是有序的，這意味著相鄰的 Key 會有很大的概率有共同的前綴部分。正是考慮到這一點，DataBlock 在結(jié)構(gòu)上做了優(yōu)化，這個優(yōu)化可以顯著減少存儲空間。

Key = sharedKey + unsharedKey

Key 會劃分為兩個部分，一個是 sharedKey，一個是 unsharedKey。前者表示相對基準 Key 的共同前綴內(nèi)容，后者表示相對基準 Key 的不同后綴部分。

比如基準 Key 是 helloworld，那么 hellouniverse 這個 Key 相對于基準 Key 來說，它的 sharedKey 就是 hello，unsharedKey 就是 universe。

DataBlock 中存儲的是連續(xù)的一系列鍵值對，它會每隔若干個 Key 設(shè)置一個基準 Key。基準 Key 的特點就是它的 sharedKey 部分是空串。基準 Key 的位置，也就是它在塊中的偏移量我們稱之為「重啟點」RestartPoint，在 DataBlock 中會記錄所有「重啟點」位置。第一個「重啟點」的位置是零，也就是 DataBlock 中的第一個 Key。

struct Entry {
  varint sharedKeyLength;
  varint unsharedKeyLength;
  varint valueLength;
  byte[] unsharedKeyContent;
  byte[] valueContent;
}

struct DataBlock {
  Entry[] entries;
  int32 [] restartPointOffsets;
  int32 restartPointCount;
}

DataBlock 中基準 Key 是默認每隔 16 個 Key 設(shè)置一個。從節(jié)省空間的角度來說，這并不是一個智能的策略。比如連續(xù) 26 個 Key 僅僅是最后一個字母不同，DataBlock 卻每隔 16 個 Key 強制「重啟」，這明顯不是最優(yōu)的。這同時也意味著 sharedKey 是空串的 Key 未必就是基準 Key。

一個 DataBlock 的默認大小只有 4K 字節(jié)，所以里面包含的鍵值對數(shù)量通常只有幾十個。如果單個鍵值對的內(nèi)容太大一個 DataBlock 裝不下咋整？

這里就必須糾正一下，DataBlock 的大小是 4K 字節(jié)，并不是說它的嚴格大小，而是在追加完最后一條記錄之后發(fā)現(xiàn)超出了 4K 字節(jié)，這時就會再開啟一個 DataBlock。這意味著一個 DataBlock 可以大于 4K 字節(jié)，如果 value 值非常大，那么相應(yīng)的 DataBlock 也會非常大。DataBlock 并不會將同一個 Value 值分塊存儲。

FilterBlock 結(jié)構(gòu)

如果沒有開啟布隆過濾器，F(xiàn)ilterBlock 這個塊就是不存在的。FilterBlock 在一個 SSTable 文件中可以存在多個，每個塊存放一個過濾器數(shù)據(jù)。不過就目前 LevelDB 的實現(xiàn)來說它最多只能有一個過濾器，那就是布隆過濾器。

布隆過濾器用于加快 SSTable 磁盤文件的 Key 定位效率。如果沒有布隆過濾器，它需要對 SSTable 進行二分查找，Key 如果不在里面，就需要進行多次 IO 讀才能確定，查完了才發(fā)現(xiàn)原來是一場空。布隆過濾器的作用就是避免在 Key 不存在的時候浪費 IO 操作。通過查詢布隆過濾器可以一次性知道 Key 有沒有可能在里面。

單個布隆過濾器中存放的是一個定長的位圖數(shù)組，該位圖數(shù)組中存放了若干個 Key 的指紋信息。這若干個 Key 來源于 DataBlock 中連續(xù)的一個范圍。FilterBlock 塊中存在多個連續(xù)的布隆過濾器位圖數(shù)組，每個數(shù)組負責指紋化 SSTable 中的一部分數(shù)據(jù)。

struct FilterEntry {
  byte[] rawbits;
}

struct FilterBlock {
  FilterEntry[n] filterEntries;
  int32[n] filterEntryOffsets;
  int32 offsetArrayOffset;
  int8 baseLg;  // 分割系數(shù)
}

其中 baseLg 默認 11，表示每隔 2K 字節(jié)（2<<11）的 DataBlock 數(shù)據(jù)（壓縮后），就開啟一個布隆過濾器來容納這一段數(shù)據(jù)中 Key 值的指紋。如果某個 Value 值過大，以至于超出了 2K 字節(jié)，那么相應(yīng)的布隆過濾器里面就只有 1 個 Key 值的指紋。每個 Key 對應(yīng)的指紋空間在打開數(shù)據(jù)庫時指定。

// 每個 Key 占用 10bit 存放指紋信息
options.SetFilterPolicy(levigo.NewBloomFilter(10))

這里的 2K 字節(jié)的間隔是嚴格的間隔，這樣才可以通過 DataBlock 的偏移量和大小來快速定位到相應(yīng)的布隆過濾器的位置 FilterOffset，再進一步獲得相應(yīng)的布隆過濾器位圖數(shù)據(jù)。

MetaIndexBlock 結(jié)構(gòu)

MetaIndexBlock 存儲了前面一系列 FilterBlock 的元信息，它在結(jié)構(gòu)上和 DataBlock 是一樣的，只不過里面 Entry 存儲的 Key 是帶固定前綴的過濾器名稱，Value 是對應(yīng)的 FilterBlock 在文件中的偏移量和長度。

key = "filter." + filterName
// value 定義了數(shù)據(jù)塊的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

就目前的 LevelDB，這里面最多只有一個 Entry，那么它的結(jié)構(gòu)非常簡單，如下圖所示

IndexBlock 結(jié)構(gòu)

它和 MetaIndexBlock 結(jié)構(gòu)一樣，也存儲了一系列鍵值對，每一個鍵值對存儲的是 DataBlock 的元信息，SSTable 中有幾個 DataBlock，IndexBlock 中就有幾個鍵值對。鍵值對的 Key 是對應(yīng) DataBlock 內(nèi)部最大的 Key，Value 是 DataBlock 的偏移量和長度。不考慮 Key 之間的前綴共享，不考慮「重啟點」，它的結(jié)構(gòu)如下圖所示

以上就是關(guān)于“LevelDB數(shù)據(jù)文件SSTable結(jié)構(gòu)是怎樣的”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

當前文章：LevelDB數(shù)據(jù)文件SSTable結(jié)構(gòu)是怎樣的
分享路徑：http://m.newbst.com/article12/jicpgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、域名注冊、標簽優(yōu)化、電子商務(wù)、搜索引擎優(yōu)化、App設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)