LevelDB源碼解析7. 日誌格式

04-05

問題

要解決什麼問題？

struct Slice { char *data_; size_t size_;};

這樣一個長度不固定的結構體寫入到文件的時候應該怎麼處理？

限制條件

LevelDB主要想解決的問題就是想盡量地把隨機寫改成順序寫。如果過來的Slice都是非常小。那麼順序寫的想法也就無法實施。所以其中一種辦法是把多個slice放到一個block裡面壓縮好。寫入到文件裡面。在LevelDB裡面設定的大小是32KB。每次寫入文件的時候，就可以變成批量寫。這個時候基本可以認為是順序的。直接把slice寫入文件：

slice1slice2slice3slice4

由於每個slice的長度都是不一樣的。那麼在讀取的時候是非常難讀取的。所以還需要加一些Metadata信息。

struct header { uint32_t crc_; 校驗 uint8_t length_low_; 長度的低8位 uint8_t length_high_; 長度的高8位 uint8_t type_; 數據的類型};struct Record { unsigned char header_[7]; slice data_;};

兩個Record的示意圖

對齊的Block

一個block的大小是32KB。由於slice或者說record的大小並不是固定的。那麼可能存在以下幾種情況：

剛好對齊

Block裡面剛好對齊並且放下一個record

一個block裡面剛好放下多個record並且剛好對齊

三個record

超大的record

跨越多個block的record

對不齊

能夠對齊的情況是比較容易處理的。可能經常會遇到的是那種對不齊的情況。比如:

未對齊的情況

在這裡，開頭是7個byte的header。然後紅色部分是數據區。最後餘下3個byte。如果要把接下來的一個record放到這個block裡面就會很奇怪。因為只能把header前三個byte填到黑色的空餘位置裡面。對於這種情況。LevelDB裡面的處理方式是：

如果餘下的空間已經不足以放置一個Record的header。這個餘下的空間就用0來填。代碼裡面用的是"x00x00"表示多個.

所以可以回答下面這個問題了：

// Q1. 如果還餘下7個bytes的時候，還會從頭開始寫么？// A: 會把一個record的header寫在這7個byte裡面。後面的數據寫到接下來的一個block里。// Q2. 如果餘下的是6個byte呢？// A: 直接用0來進行填充。// Q3: 給定一個空的block，給特別多的數據。那麼中間block尾巴上的7個byte會空著么？// A: 不會。會直接用來填數據。下一個block的開頭就是一個header。// NOTE: 寫入文件的時候，並不是以block為單位。而是以record為單位。

尾巴的處理

通過前面的分析，可以知道。如果尾巴餘下<=6個byte的話，就是直接填0。但是如果剛好餘下7個byte的時候。應該是怎麼填充的呢？

餘下7個byte，用來填寫header（綠色表示header）

那麼問題來了。接下來的Block的開頭又應該是怎麼？

A: 接下來的Block的開頭就應該是一個新的header。前面7個bytes填寫的header，裡面記錄的數據區的長度就是0。

被切分的Record

由前面的描述可以知道。一個Record與Block的關係可以是下面這三種：

一個Record剛好在一個Block裡面
一個Record被分到兩個Block裡面
一個Record被切分到多個Block裡面。

Record與Block的關係圖

可以看出來。

FULL表示這個Recorc沒有跨越Block
First表示這是Record的開頭部分。
Middle表示這是Record的中間部分
Last表示是一個Record的尾巴部分

// log_format.henum RecordType { // Zero is reserved for preallocated files kZeroType = 0, kFullType = 1, // For fragments kFirstType = 2, kMiddleType = 3, kLastType = 4};static const int kMaxRecordType = kLastType;static const int kBlockSize = 32768; //32KB// Header is checksum (4 bytes), length (2 bytes), type (1 byte).static const int kHeaderSize = 4 + 2 + 1;

到這裡應該已經可以明白整個日誌結構了。

寫record

寫入文件的時候，是以Record為單位。而不是以Block為單位。但是需要注意的是，有可能Record只是Slice的一部分。也就是說，寫入的時候，有可能不是一個完整的Slice被寫到了文件中。

Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) { // 根據前面的代碼 fragment_length = min(avail, left) // 這裡加上這個限制，應該是為了防止後面 // block_offset_ + kHeaderSize + n溢出 assert(n <= 0xffff); // Must fit in two bytes // block_offset_是類成員變數。記錄了在一個Block裡面的偏移量。 // block_offset_一定不能溢出。 assert(block_offset_ + kHeaderSize + n <= kBlockSize); // leveldb是一種小端寫磁碟的情況 // LevelDB使用的是小端位元組序存儲，低位位元組排放在內存的低地址端 // Format the header // buf前面那個int是用來存放crc32的。 char header[kHeaderSize]; // 寫入長度: 這裡先寫入低8位 header[4] = static_cast<char>(n & 0xff); // 再寫入高8位 header[5] = static_cast<char>(n >> 8); // 再寫入類型 header[6] = static_cast<char>(t); // Compute the crc of the record type and the payload. // 這裡是計算header和數據區的CRC32的值。具體過程不去關心。 uint32_t data_crc = crc32c::Extend(type_crc_[t], ptr, n); data_crc = crc32c::Mask(data_crc); // Adjust for storage EncodeFixed32(header, data_crc); // Write the header and the payload Status s = dest_->Append(Slice(header, kHeaderSize)); if (s.ok()) { s = dest_->Append(Slice(ptr, n)); // 當寫完一個record之後，這裡就立馬flush // 但是有可能這個slice並不是完整的。 if (s.ok()) { s = dest_->Flush(); } } // 在一個block裡面的寫入位置往前移。 block_offset_ += kHeaderSize + n; return s;}

在這個函數裡面，block_offset_引用的是在Block裡面的位置。每次要寫入數據的時候。都會保證寫進來的數據不會超出一個block的大小。

assert(block_offset_ + kHeaderSize + n <= kBlockSize);

那麼，也就對調用EmitPhysicalRecord提出了要求。就是要求調用方，正確地設置寫入的數據。

恆等不變式

這裡需要看一下恆等不變式

0 <= block_offset_ <= kBlockSize - kHeaderSize

是如何確保的。

初始設置

首先當生成Writer的時候，

Writer::Writer(WritableFile* dest) : dest_(dest), block_offset_(0) { // 恆等不變式成立! InitTypeCrc(type_crc_);}// 注意這裡對kBlockSize進行了取模// 這裡不是表示的是文件的偏移量？// 那表示的是什麼？Writer::Writer(WritableFile* dest, uint64_t dest_length) : dest_(dest), block_offset_(dest_length % kBlockSize) { // 可能不成立。 InitTypeCrc(type_crc_);}

但是，每次客戶端調用AddRecord的時候，開始設置block_offset_。

// 餘下還需要多少才能填滿一個塊。 const int leftover = kBlockSize - block_offset_; assert(leftover >= 0); // 如果剩下的空間已經很小了。連個頭部都放不下了。 // 這裡需要分兩種case. // 1. leftover == 0 // 2. 0 < leftover < kHeaderSize if (leftover < kHeaderSize) { block_offset_ = 0; } assert(kBlockSize - block_offset_ - kHeaderSize >= 0); //.. EmitPhysicalRecord() // 在這裡調用

從這裡可以看出，一旦發現block_offset_ + kHeaderSize > blockSize的時候。就直接把block_offset_設置為0。

這裡就已經確保：

assert(kBlockSize - block_offset_ - kHeaderSize >= 0);

是肯定成立的。所以在每次寫入Record的時候，block_offset_就肯定不會到末尾的7個bytes那個區間裡面。

AddRecord

AddRecord的主要功能，就是把需要寫入文件的Slice，切分成一個一個的record。然後順序寫入到文件中。

Status Writer::AddRecord(const Slice& slice) { const char* ptr = slice.data(); size_t left = slice.size(); // Fragment the record if necessary and emit it. Note that if slice // is empty, we still want to iterate once to emit a single // zero-length record Status s; // begin是從數據的頭開始寫的么？ bool begin = true; do { // 餘下還需要多少才能填滿一個塊。 const int leftover = kBlockSize - block_offset_; assert(leftover >= 0); // 如果剩下的空間已經很小了。連個頭部都放不下了。 // 這裡需要分兩種case. // 1. leftover == 0 // 2. 0 < leftover < kHeaderSize if (leftover < kHeaderSize) { // Switch to a new block // Case 2. 如果不等於0，那麼還是需要把剩下的空間用0來填滿的。 if (leftover > 0) { // Fill the trailer (literal below relies on kHeaderSize being 7) assert(kHeaderSize == 7); dest_->Append(Slice("x00x00x00x00x00x00", leftover)); } // Case 1. 如果餘下的等於0，那麼也就什麼都不用做了 // 最後： // 移動到一個新的block的頭上 block_offset_ = 0; } // 這裡有個恆等不變式 // A. 也就是餘下的空間必須要能夠放一個header. // kBlockSize - block_offset = newOverLeft // newOverLeft - kHeaderSize >= 0 // Invariant: we never leave < kHeaderSize bytes in a block. assert(kBlockSize - block_offset_ - kHeaderSize >= 0); // 這裡不能直接換掉上面的assert // 這裡用的是size_t，如果換到上面，恆等不變式是一直成立的。 // avail指的就是當前這個block裡面的可用空間 // 如果直接看這裡的可用空間，就是kBlockSize - 0 - kHeaderSize // 所以也只是把當前record的header佔用的空間扣掉了。 const size_t avail = kBlockSize - block_offset_ - kHeaderSize; // left指的是sliceSizeToWrite.也就是dataToWrite // fragment_length指的就是後面需要寫的數據量。主要是指當前這個block // - 應該是在需要寫入的數據量，當前餘下空間裡面取最小值。 const size_t fragment_length = (left < avail) ? left : avail; RecordType type; // 根據能寫的數據的情況，來決定當前的這個record的類型。 const bool end = (left == fragment_length); // 如果是從頭開始寫的，並且又可以直接把slice數據寫完。 // 那麼肯定是fullType. if (begin && end) { type = kFullType; // 不能寫完，但是是從頭開始寫 } else if (begin) { type = kFirstType; // 不是從頭開始寫，但是可以把數據寫完 } else if (end) { type = kLastType; // 不能從頭開始寫，也不能把數據寫完。 } else { type = kMiddleType; } // 這裡提交一個物理的記錄 // 注意：可能這裡並沒有把一個slice寫完。 s = EmitPhysicalRecord(type, ptr, fragment_length); // 移動寫入指針。 ptr += fragment_length; // 需要寫入的數據相應減少 left -= fragment_length; // 當然也不是從頭開始寫了。因為已經寫過一次了。 begin = false; } while (s.ok() && left > 0); return s;}

尾巴的處理

if (leftover < kHeaderSize) { // Switch to a new block // Case 2. 如果不等於0，那麼還是需要把剩下的空間用0來填滿的。 if (leftover > 0) { // Fill the trailer (literal below relies on kHeaderSize being 7) assert(kHeaderSize == 7); dest_->Append(Slice("x00x00x00x00x00x00", leftover)); } // Case 1. 如果餘下的等於0，那麼也就什麼都不用做了 // 最後： // 移動到一個新的block的頭上 block_offset_ = 0; }

特別需要注意這一段關於尾巴的處理。也就是當餘下的空間不足7bytes的時候。直接留空。

這裡需要思考的是

1. Slice("x00x00x00x00x00x00", leftover) 這個字元串裡面只有6個0?萬一需要填滿7個byte的0的時候，應該怎麼辦呢？2. 前面的字元串固定的長度是7個byte的0.想想為什麼？那麼萬一下leftover的長度為不足7的時候為什麼leftover < 7的時候，還是可以生效?