如何理解LevelDB源碼中的SSTable

如何理解LevelDB源碼中的SSTable，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

瓊結(jié)ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來(lái)市場(chǎng)廣闊！成為成都創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！

MemTable是內(nèi)存表，而當(dāng)內(nèi)存表增長(zhǎng)到一定程度時(shí)(memtable.size>  Options::write_buffer_size)，會(huì)將當(dāng)前的MemTable數(shù)據(jù)持久化(LevelDB中實(shí)際有兩份MemTable，后面LevelDB數(shù)據(jù)庫(kù)備忘時(shí)會(huì)講)。持久化的文件(sst文件)稱之為Table，LevelDB中的Table分為不同的層級(jí)，當(dāng)前版本的***層級(jí)為7(0-6),table中l(wèi)evel0的數(shù)據(jù)***，level6的數(shù)據(jù)最舊。

Compaction動(dòng)作負(fù)責(zé)觸發(fā)內(nèi)存表到SSTable的轉(zhuǎn)換，LOG恢復(fù)時(shí)也會(huì)執(zhí)行，這里不關(guān)心Compaction或恢復(fù)的任何細(xì)節(jié)，后面會(huì)單獨(dú)備忘。

LevelDB通過(guò)BuildTable方法完成SSTable的構(gòu)建，其創(chuàng)建SSTable文件并將memtable中的記錄依次寫入文件。BuildTable帶了一個(gè)輸出參數(shù)，F(xiàn)ileMetaData：

1     struct FileMetaData {  2         int refs;  3         int allowed_seeks;          // Seeks allowed until compaction  4         uint64_t number;  5         uint64_t file_size;         // File size in bytes  6         InternalKey smallest;       // Smallest internal key served by table  7         InternalKey largest;        // Largest internal key served by table  8  9         FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }

number為一個(gè)遞增的序號(hào)，用于創(chuàng)建文件名，allowed_seeks作者有提到，是當(dāng)前文件在Compaction到下一級(jí)之前允許Seek的次數(shù)，這個(gè)次數(shù)和文件大小相關(guān)，文件越大，Compaction之前允許Seek的次數(shù)越多，這個(gè)Version備忘時(shí)也會(huì)提。

BuildTable方法中真正做事的時(shí)TableBuilder，通過(guò)調(diào)用Add方法將所有記錄添加到數(shù)據(jù)表中，完成SSTable創(chuàng)建。

TableBuilder主要做了如下幾件事：

創(chuàng)建Index Block：用于Data Block的快速定位

將數(shù)據(jù)分為一個(gè)個(gè)的Data Block

如文件需要壓縮，執(zhí)行壓縮動(dòng)作

依次寫入Data Block、Meta Block、Index Block、Footer Block，形成完整的SSTable文件結(jié)構(gòu)

其中階段1-3由Add方法完成，階段4由Finish方法完成，先來(lái)看Add方法：

1 void TableBuilder::Add(const Slice& key, const Slice& value) {  2         Rep* r = rep_;  3         assert(!r->closed);  4         if (!ok()) return;  5         if (r->num_entries > 0) {  6             assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);  7         }  8  9         //Index Block：Data Block的索引元數(shù)據(jù)。 10         if (r->pending_index_entry) { 11             assert(r->data_block.empty()); 12             r->options.comparator->FindShortestSeparator(&r->last_key, key); 13             std::string handle_encoding; 14             r->pending_handle.EncodeTo(&handle_encoding); 15             r->index_block.Add(r->last_key, Slice(handle_encoding)); 16             r->pending_index_entry = false; 17         } 18 19         r->last_key.assign(key.data(), key.size()); 20         r->num_entries++; 21         r->data_block.Add(key, value); 22 23         const size_t estimated_block_size = r->data_block.CurrentSizeEstimate(); 24         if (estimated_block_size >= r->options.block_size) { 25             Flush();    //超過(guò)單數(shù)據(jù)塊大小，寫入文件。 26         } 27     }

Add方法創(chuàng)建Data Block、IndexBlock，DataBlcok通過(guò)Flush刷入磁盤文件。

再來(lái)看Finish方法：

1     Status TableBuilder::Finish() {  2         //Data Block  3         Rep* r = rep_;  4         Flush();  5  6         assert(!r->closed);  7         r->closed = true;  8          9         //Meta Block 10         BlockHandle metaindex_block_handle; 11         BlockHandle index_block_handle; 12         if (ok())  13         { 14             BlockBuilder meta_index_block(&r->options); 15             // TODO(postrelease): Add stats and other meta blocks 16             WriteBlock(&meta_index_block, &metaindex_block_handle); 17         } 18 19         //Index Block 20         if (ok()) { 21             if (r->pending_index_entry) { 22                 r->options.comparator->FindShortSuccessor(&r->last_key); 23                 std::string handle_encoding; 24                 r->pending_handle.EncodeTo(&handle_encoding); 25                 r->index_block.Add(r->last_key, Slice(handle_encoding)); 26                 r->pending_index_entry = false; 27             } 28             WriteBlock(&r->index_block, &index_block_handle); 29         } 30 31         //Footer 32         if (ok())  33         { 34             Footer footer; 35             footer.set_metaindex_handle(metaindex_block_handle);    // 36             footer.set_index_handle(index_block_handle); 37             std::string footer_encoding; 38             footer.EncodeTo(&footer_encoding); 39             r->status = r->file->Append(footer_encoding); 40             if (r->status.ok()) { 41                 r->offset += footer_encoding.size(); 42             } 43         } 44         return r->status; 45     }

Finish依次寫入：尚未寫入的***一塊Data Block及Meta Block、Index Block、Footer。Meta  Block暫未使用，F(xiàn)ooter則保存了meta block、index block的位置信息。

Block

Data Block、Meta Block、Index  Block是業(yè)務(wù)劃分，分別代表用戶數(shù)據(jù)塊、元數(shù)據(jù)塊及用戶數(shù)據(jù)索引塊。其存儲(chǔ)格式均為Block結(jié)構(gòu)：

Record代表一條數(shù)據(jù)，藍(lán)色及紅色部分(統(tǒng)一稱作”重啟點(diǎn)”)為附加信息，而這些是做什么的呢?兩點(diǎn)：性能優(yōu)化、節(jié)省空間。

我們先來(lái)看Restart列表的構(gòu)建邏輯：

1 void BlockBuilder::Add(const Slice& key, const Slice& value) {  2         Slice last_key_piece(last_key_);  3         ......  4         size_t shared = 0;  5         if (counter_ < options_->block_restart_interval) {  6             // See how much sharing to do with previous string  7             const size_t min_length = std::min(last_key_piece.size(), key.size());  8             while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {  9                 shared++; 10             } 11         } 12         else {    //restart時(shí)保存完整的key值 13             // Restart compression 14             restarts_.push_back(buffer_.size()); 15             counter_ = 0; 16         } 17         const size_t non_shared = key.size() - shared; 18 19         //Record信息 20         // shared size | no shared size | value size | no shared key data | value data 21         // Add "<shared><non_shared><value_size>" to buffer_ 22         PutVarint32(&buffer_, shared); 23         PutVarint32(&buffer_, non_shared); 24         PutVarint32(&buffer_, value.size()); 25         // Add string delta to buffer_ followed by value 26         buffer_.append(key.data() + shared, non_shared); 27         buffer_.append(value.data(), value.size()); 28 29         // Update state 30         last_key_.resize(shared); 31         last_key_.append(key.data() + shared, non_shared); 32         assert(Slice(last_key_) == key); 33         counter_++; 34     }

每隔一定間隔(block_restart_interval)Record就會(huì)創(chuàng)建一個(gè)新的重啟點(diǎn)，重啟點(diǎn)內(nèi)容為當(dāng)前block的大小，即重啟點(diǎn)在block內(nèi)的偏移。

每當(dāng)添加一個(gè)新的重啟點(diǎn)時(shí)，重啟點(diǎn)指向位置的Record中一定保存了完整的key值(shared size =  0),隨后的Record中保存的key值僅為和上一個(gè)Record的差異值。因?yàn)镵ey在Block中是有序排列的，所以相鄰key值重疊區(qū)域節(jié)省的空間還是非?？捎^的。

基于上述實(shí)現(xiàn)，問(wèn)題來(lái)了：當(dāng)需要定位一條記錄時(shí)，因?yàn)閞ecord中key的信息是不完整的，僅包含了和上一條的差異項(xiàng)，但上一條記錄本身也只包含了和再上一條的差異項(xiàng)，那么定位一條記錄時(shí)如何做key比較?如果需要一直向上查找完成key值拼接，性能上會(huì)不會(huì)有損傷?

分析這個(gè)問(wèn)題就要了解重啟點(diǎn)的定位：Block的一級(jí)索引，SSTable的二級(jí)索引(Index  Block是SSTable的一級(jí)索引)。本文將每個(gè)重啟點(diǎn)記錄位置所屬的Record列表稱為一個(gè)Restart Block

假設(shè)每條record記錄的都是完整的key值時(shí)，從SSTable中查找一條記錄的工作流如下：

根據(jù)Key值從Index Block中找到所屬的Data Block

根據(jù)Key值從“重啟點(diǎn)”列表中找到所屬的Restart Block，從Restart Block的起始位置進(jìn)行key值比較，找到正確的記錄。

在上述流程中，我們必定會(huì)先找到一個(gè)Restart Point，隨后進(jìn)行key值比較，而Restart  Point記錄本身包含了完整的key值信息，后續(xù)key值均可基于此key得到。

Restart列表本身做為索引，提升了查找性能，而key值存儲(chǔ)的小技巧又降低了空間使用率，在不損傷性能的情況小降低空間利用率，這是一個(gè)很好的例子。

即使這樣，作者覺(jué)得還不夠，空間利用率還可以進(jìn)一步優(yōu)化，并且不損傷任何讀取數(shù)據(jù)的性能。

做法和Restart列表的做法類似，是在Index Block中，通過(guò)調(diào)用FindShortestSeparator /  FindShortSuccessor方法實(shí)現(xiàn)。

1         // If *start < limit, changes *start to a short string in [start,limit). 2         // Simple comparator implementations may return with *start unchanged, 3         // i.e., an implementation of this method that does nothing is correct. 4         virtual void FindShortestSeparator(std::string* start, const Slice& limit) const = 0; 5 6         // Changes *key to a short string >= *key. 7         // Simple comparator implementations may return with *key unchanged, 8         // i.e., an implementation of this method that does nothing is correct. 9         virtual void FindShortSuccessor(std::string* key) const = 0;

FindShortestSeparator找到start、limit之間最短的key值，如“helloworld”和”hellozoomer”之間最短的key值可以是”hellox”。FindShortSuccessor則更極端，用于找到比key值大的最小key，如傳入“helloworld”，返回的key值可能是“i”而已。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

網(wǎng)頁(yè)名稱：如何理解LevelDB源碼中的SSTable
網(wǎng)站網(wǎng)址：http://muchs.cn/article2/jchgic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、關(guān)鍵詞優(yōu)化、搜索引擎優(yōu)化、商城網(wǎng)站

廣告

聲明：本網(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)