leveldb(十一)：SSTable之2寫sstable檔案

個人總結：

1.由上一篇我們知道了一個sstable檔案是由很多個不同的block組成的，其中最重要的兩個是 Data Block和Index Block。我們知道除了第0層，其他層的sstable都是按key增長的順序存儲kv對的。Data Block就是存儲這些kv對的block。每個Data Block管一段key的範圍。Index Block就是負責記錄每段key是在哪個Data Block上，這樣就能快速查找kv對了，首先根據Index Block快速找到對應的Data Block，然後在利用二分查找在Data Block中快速找到kv對。

2.Index Block是怎麼存儲各個Data Block的索引資訊的。

1.    r->pending_handle.EncodeTo(&handle_encoding);  
2.    r->index_block.Add(r->last_key, Slice(handle_encoding)); 

可以看出， Index Block的key是last_key，它的含義就是大于目前Data Block中的所有key，并且小于下一個Data Block中的所有key。 比如上一個data block最後一個k/v的key是"the quick brown fox"，其後繼data block的第一個key是"the who"，我們就可以用一個較短的字元串"the r"作為上一個data block的index block entry的key。

 value是BlockHandle，它由uint64_t offset 和uint64_t size_組成，其含義就是小于last_key的kv對所在的Data Block所在的檔案偏移以及長度。

3.在寫sstable檔案時，往檔案中寫一個Data Block後便向記憶體中的index_block插入一條記錄，當所有 Data Block全部寫入檔案後，才将記憶體中的index_block寫入sstable檔案中。

6.4 建立sstable檔案

了解了sstable檔案的存儲格式，以及Data Block的組織，下面就可以分析如何建立sstable檔案了。相關代碼在table_builder.h/.cc以及block_builder.h/.cc（建構Block）中。

6.4.1 TableBuilder類

建構sstable檔案的類是TableBuilder，該類提供了幾個有限的方法可以用來添加k/v對，Flush到檔案中等等，它依賴于BlockBuilder來建構Block。

TableBuilder的幾個接口說明下：

> void Add(const Slice& key, const Slice& value)，向目前正在建構的表添加新的{key, value}對，要求根據Option指定的Comparator，key必須位于所有前面添加的key之後；

> void Flush()，将目前緩存的k/v全部flush到檔案中，一個進階方法，大部分的client不需要直接調用該方法；

> void Finish()，結束表的建構，該方法被調用後，将不再會使用傳入的WritableFile；

> void Abandon()，結束表的建構，并丢棄目前緩存的内容，該方法被調用後，将不再會使用傳入的WritableFile；【隻是設定closed為true，無其他操作】

一旦Finish()/Abandon()方法被調用，将不能再次執行Flush或者Add操作。

下面來看看涉及到的類，如圖6.3-1所示。

圖6.3-1

其中WritableFile和op log一樣，使用的都是記憶體映射檔案。Options是一些調用者可設定的選項。

TableBuilder隻有一個成員變量Rep* rep_，實際上Rep結構體的成員就是TableBuilder所有的成員變量；這樣做的目的，可能是為了隐藏其内部細節。Rep的定義也是在.cc檔案中，對外是透明的。

簡單解釋下成員的含義：

[cpp]  view plain  copy

1. Options options;   // data block的選項  
2. Options index_block_options; // index block的選項  
3. WritableFile* file;  // sstable檔案  
4. uint64_t offset; // 要寫入data block在sstable檔案中的偏移，初始0  
5. Status status; //目前狀态-初始ok  
6. BlockBuilder data_block; //目前操作的data block  
7. BlockBuilder index_block; // sstable的index block  
8. std::string last_key; //目前data block最後的k/v對的key  
9. int64_t num_entries; //目前data block的個數，初始0  
10. bool closed;          //調用了Finish() or Abandon()，初始false  
11. FilterBlockBuilder*filter_block; //根據filter資料快速定位key是否在block中  
12. bool pending_index_entry; //見下面的Add函數，初始false  
13. BlockHandle pending_handle; //添加到index block的data block的資訊  
14. std::string compressed_output;//壓縮後的data block，臨時存儲，寫入後即被清空  

Filter block是存儲的過濾器資訊，它會存儲{key, 對應data block在sstable的偏移值}，不一定是完全精确的，以快速定位給定key是否在data block中。

下面分析如何向sstable中添加k/v對，建立并持久化sstable。其它函數都比較簡單，略過。另外對于Abandon，簡單設定closed=true即傳回。

6.4.2 添加k/v對

這是通過方法Add(constSlice& key, const Slice& value)完成的，沒有傳回值。下面分析下函數的邏輯：

S1 首先保證檔案沒有close，也就是沒有調用過Finish/Abandon，以及保證目前status是ok的；如果目前有緩存的kv對，保證新加入的key是最大的。

[cpp]  view plain  copy

1. Rep* r = rep_;  
2. assert(!r->closed);  
3. if (!ok()) return;  
4. if (r->num_entries > 0) {  
5.    assert(r->options.comparator->Compare(key, Slice(r->last_key))> 0);  
6. }  

S2 如果标記r->pending_index_entry為true，表明遇到下一個data block的第一個k/v，根據key調整r->last_key，這是通過Comparator的FindShortestSeparator完成的。

[cpp]  view plain  copy

1. if (r->pending_index_entry) {  
2.    assert(r->data_block.empty());  
3.    r->options.comparator->FindShortestSeparator(&r->last_key,key);  
4.    std::string handle_encoding;  
5.    r->pending_handle.EncodeTo(&handle_encoding);  
6.    r->index_block.Add(r->last_key, Slice(handle_encoding));  
7.    r->pending_index_entry =false;  
8. }  

接下來将pending_handle加入到index block中{r->last_key, r->pending_handle’sstring}。最後将r->pending_index_entry設定為false。

值得講講pending_index_entry這個标記的意義，見代碼注釋：

直到遇到下一個databock的第一個key時，我們才為上一個datablock生成index entry，這樣的好處是：可以為index使用較短的key；比如上一個data block最後一個k/v的key是"the quick brown fox"，其後繼data block的第一個key是"the who"，我們就可以用一個較短的字元串"the r"作為上一個data block的index block entry的key。

簡而言之，就是在開始下一個datablock時，Leveldb才将上一個data block加入到index block中。标記pending_index_entry就是幹這個用的，對應data block的index entry資訊就儲存在（BlockHandle）pending_handle。

S3 如果filter_block不為空，就把key加入到filter_block中。

[cpp]  view plain  copy

1. if (r->filter_block != NULL) {  
2.    r->filter_block->AddKey(key);  
3. }  

S4 設定r->last_key = key，将(key, value)添加到r->data_block中，并更新entry數。

[cpp]  view plain  copy

1. r->last_key.assign(key.data(), key.size());  
2. r->num_entries++;  
3. r->data_block.Add(key,value);  

S5 如果data block的個數超過限制，就立刻Flush到檔案中。

[cpp]  view plain  copy

1. const size_testimated_block_size = r->data_block.CurrentSizeEstimate();  
2. if (estimated_block_size >=r->options.block_size) Flush();  

6.4.3 Flush檔案

該函數邏輯比較簡單，直接見代碼如下：

[cpp]  view plain  copy

1. Rep* r = rep_;  
2. assert(!r->closed); // 首先保證未關閉，且狀态ok  
3. if (!ok()) return;  
4. if (r->data_block.empty())return; // data block是空的  
5. // 保證pending_index_entry為false，即data block的Add已經完成  
6. assert(!r->pending_index_entry);  
7. // 寫入data block，并設定其index entry資訊—BlockHandle對象  
8. WriteBlock(&r->data_block, &r->pending_handle);  
9. //寫入成功，則Flush檔案，并設定r->pending_index_entry為true，  
10. //以根據下一個data block的first key調整index entry的key—即r->last_key  
11. if (ok()) {  
12.   r->pending_index_entry =true;  
13.   r->status =r->file->Flush();  
14. }  
15. if (r->filter_block != NULL){ //将data block在sstable中的便宜加入到filter block中  
16.   r->filter_block->StartBlock(r->offset); // 并指明開始新的data block  
17. }  

6.4.4 WriteBlock函數

在Flush檔案時，會調用WriteBlock函數将data block寫入到檔案中，該函數同時還設定data block的index entry資訊。原型為：

void WriteBlock(BlockBuilder* block, BlockHandle* handle)

該函數做些預處理工作，序列化要寫入的data block，根據需要壓縮資料，真正的寫入邏輯是在WriteRawBlock函數中。下面分析該函數的處理邏輯。

S1 獲得block的序列化資料Slice，根據配置參數決定是否壓縮，以及根據壓縮格式壓縮資料内容。對于Snappy壓縮，如果壓縮率太低<12.5%，還是作為未壓縮内容存儲。

BlockBuilder的Finish()函數将data block的資料序列化成一個Slice。

[cpp]  view plain  copy

1. Rep* r = rep_;  
2. Slice raw = block->Finish(); // 獲得data block的序列化字元串  
3. Slice block_contents;  
4. CompressionType type =r->options.compression;  
5. switch (type) {  
6.   case kNoCompression: block_contents= raw; break; // 不壓縮  
7.   case kSnappyCompression: { // snappy壓縮格式  
8.     std::string* compressed =&r->compressed_output;  
9.     if(port::Snappy_Compress(raw.data(), raw.size(), compressed) &&  
10.         compressed->size()< raw.size() - (raw.size() / 8u)) {  
11.         block_contents =*compressed;  
12.     } else { // 如果不支援Snappy，或者壓縮率低于12.5%，依然當作不壓縮存儲  
13.       block_contents = raw;  
14.       type = kNoCompression;  
15.     }  
16.     break;  
17.   }  
18. }  

S2 将data内容寫入到檔案，并重置block成初始化狀态，清空compressedoutput。

[cpp]  view plain  copy

1. WriteRawBlock(block_contents,type, handle);  
2. r->compressed_output.clear();  
3. block->Reset();  

6.4.5 WriteRawBlock函數

在WriteBlock把準備工作都做好後，就可以寫入到sstable檔案中了。來看函數原型：

void WriteRawBlock(const Slice& data, CompressionType, BlockHandle*handle);

函數邏輯很簡單，見代碼。

[cpp]  view plain  copy

1. Rep* r = rep_;  
2. handle->set_offset(r->offset); // 為index設定data block的handle資訊  
3. handle->set_size(block_contents.size());  
4. nbsp;r->status =r->file->Append(block_contents); // 寫入data block内容  
5. if (r->status.ok()) {// 寫入1byte的type和4bytes的crc32  
6.   chartrailer[kBlockTrailerSize];  
7.   trailer[0] = type;  
8.   uint32_t crc = crc32c::Value(block_contents.data(),block_contents.size());  
9.   crc = crc32c::Extend(crc, trailer, 1);  // Extend crc tocover block type  
10.   EncodeFixed32(trailer+1, crc32c::Mask(crc));  
11.   r->status =r->file->Append(Slice(trailer, kBlockTrailerSize));  
12.   if (r->status.ok()) { // 寫入成功更新offset-下一個data block的寫入偏移  
13.     r->offset +=block_contents.size() + kBlockTrailerSize;  
14.   }  
15. }  

6.4.6 Finish函數

調用Finish函數，表明調用者将所有已經添加的k/v對持久化到sstable，并關閉sstable檔案。

該函數邏輯很清晰，可分為5部分。

S1 首先調用Flush，寫入最後的一塊data block，然後設定關閉标志closed=true。表明該sstable已經關閉，不能再添加k/v對。

[cpp]  view plain  copy

1. Rep* r = rep_;  
2. Flush();  
3. assert(!r->closed);  
4. r->closed = true;  

BlockHandle filter_block_handle,metaindex_block_handle, index_block_handle;

S2 寫入filter block到檔案中

[cpp]  view plain  copy

1. if (ok() &&r->filter_block != NULL) {  
2.   WriteRawBlock(r->filter_block->Finish(), kNoCompression,&filter_block_handle);  
3. }  

S3 寫入meta index block到檔案中

如果filterblock不為NULL，則加入從"filter.Name"到filter data位置的映射。通過meta index block，可以根據filter名字快速定位到filter的資料區。

[cpp]  view plain  copy

1. if (ok()) {  
2.   BlockBuildermeta_index_block(&r->options);  
3.   if (r->filter_block !=NULL) {  
4.     //加入從"filter.Name"到filter data位置的映射  
5.     std::string key ="filter.";  
6.     key.append(r->options.filter_policy->Name());  
7.     std::string handle_encoding;  
8.     filter_block_handle.EncodeTo(&handle_encoding);  
9.     meta_index_block.Add(key,handle_encoding);  
10.   }  
11.   // TODO(postrelease): Add stats and other metablocks  
12.   WriteBlock(&meta_index_block, &metaindex_block_handle);  
13. }  

S4 寫入index block，如果成功Flush過data block，那麼需要為最後一塊data block設定index block，并加入到index block中。

[cpp]  view plain  copy

1. if (ok()) {  
2.   if (r->pending_index_entry){ // Flush時會被設定為true  
3.     r->options.comparator->FindShortSuccessor(&r->last_key);  
4.     std::string handle_encoding;  
5.     r->pending_handle.EncodeTo(&handle_encoding);  
6.     r->index_block.Add(r->last_key, Slice(handle_encoding)); // 加入到index block中  
7.     r->pending_index_entry =false;  
8.   }  
9.   WriteBlock(&r->index_block, &index_block_handle);  
10. }  

S5 寫入Footer。

[cpp]  view plain  copy

1. if (ok()) {  
2.   Footer footer;  
3.   footer.set_metaindex_handle(metaindex_block_handle);  
4.   footer.set_index_handle(index_block_handle);  
5.   std::string footer_encoding;  
6.   footer.EncodeTo(&footer_encoding);  
7.   r->status =r->file->Append(footer_encoding);  
8.   if (r->status.ok()) {  
9.     r->offset +=footer_encoding.size();  
10.   }  
11. }  

整個寫入流程就分析完了，對于Datablock和Filter Block的操作将在Data block和Filter Block中單獨分析，下面的讀取相同。