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

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

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

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

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

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

struct Footer {
  BlockHandler metaIndexHandler;  // MetaIndexBlock的文件偏移量和長(zhǎng)度
  BlockHandler indexHandler; // IndexBlock的文件偏移量和長(zhǎng)度
  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)的尾部還有一個(gè) 64位的魔術(shù)數(shù)字 0xdb4775248b80fb57，如果文件尾部的 8 字節(jié)不是這個(gè)數(shù)字說(shuō)明文件已經(jīng)損壞。這個(gè)魔術(shù)數(shù)字的來(lái)源很有意思，它是下面返回的字符串的前64bit。

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

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

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

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

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

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

crcValue = crc32(data, compressType)

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

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

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

Key = sharedKey + unsharedKey

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

比如基準(zhǔn) Key 是 helloworld，那么 hellouniverse 這個(gè) Key 相對(duì)于基準(zhǔn) Key 來(lái)說(shuō)，它的 sharedKey 就是 hello，unsharedKey 就是 universe。

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

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

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

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

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

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

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

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

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

單個(gè)布隆過(guò)濾器中存放的是一個(gè)定長(zhǎng)的位圖數(shù)組，該位圖數(shù)組中存放了若干個(gè) Key 的指紋信息。這若干個(gè) Key 來(lái)源于 DataBlock 中連續(xù)的一個(gè)范圍。FilterBlock 塊中存在多個(gè)連續(xù)的布隆過(guò)濾器位圖數(shù)組，每個(gè)數(shù)組負(fù)責(zé)指紋化 SSTable 中的一部分?jǐn)?shù)據(jù)。

struct FilterEntry {
  byte[] rawbits;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

廣告

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