首页 > 代码库 > levelDB Log

levelDB Log

2024-07-17 00:12:19   223人阅读

分析完KV在内存中的存储，接下来就是操作日志。所有的写操作都必须先成功的append到操作日志中，然后再更新内存memtable。这样做有两个有点：1可以将随机的写IO变成append，极大的提高写磁盘速度；2防止在节点down机导致内存数据丢失，造成数据丢失，这对系统来说是个灾难。

在各种高效的存储系统中，这已经是口水技术了。

5.1 格式

在源码下的文档doc/log_format.txt中，作者详细描述了log格式：
The log file contents are a sequence of 32KB blocks.  The only exception is that the tail of thefile may contain a partial block.
Each block consists of a sequence of records:
    block:= record* trailer?
    record :=
    checksum: uint32    // crc32c of type and data[] ; little-endian
    length: uint16       // little-endian
    type: uint8          // One of FULL,FIRST, MIDDLE, LAST
    data: uint8[length]
A record never starts within the last six bytes of a block (since it won‘tfit).  Any leftover bytes here form thetrailer, which must consist entirely of zero bytes and must be skipped byreaders.
翻译过来就是：
Leveldb把日志文件切分成了大小为32KB的连续block块，block由连续的log record组成，log record的格式为：

，注意：CRC32, Length都是little-endian的。
Log Type有4种：FULL = 1、FIRST = 2、MIDDLE = 3、LAST = 4。FULL类型表明该log record包含了完整的user record；而user record可能内容很多，超过了block的可用大小，就需要分成几条log record，第一条类型为FIRST，中间的为MIDDLE，最后一条为LAST。也就是：
> FULL，说明该log record包含一个完整的user record；
> FIRST，说明是user record的第一条log record
> MIDDLE，说明是user record中间的log record
> LAST，说明是user record最后的一条log record
翻一下文档上的例子，考虑到如下序列的user records：
   A: length 1000
   B: length 97270
   C: length 8000
A作为FULL类型的record存储在第一个block中；B将被拆分成3条log record，分别存储在第1、2、3个block中，这时block3还剩6byte，将被填充为0；C将作为FULL类型的record存储在block 4中。如图5.1-1所示。

图5.1-1
由于一条logrecord长度最短为7，如果一个block的剩余空间<=6byte，那么将被填充为空字符串，另外长度为7的log record是不包括任何用户数据的。

写日志

写比读简单，而且写入决定了读，所以从写开始分析。

有意思的是在写文件时，Leveldb使用了内存映射文件，内存映射文件的读写效率比普通文件要高，关于内存映射文件为何更高效，这篇文章写的不错：

http://blog.csdn.net/mg0832058/article/details/5890688

图5.2-1

注意Write类的成员type_crc_数组，这里存放的为Record Type预先计算的CRC32值，因为Record Type是固定的几种，为了效率。

Writer类只有一个接口，就是AddRecord()，传入Slice参数，下面来看函数实现。

首先取出slice的字符串指针和长度，初始化begin=true，表明是第一条log record。

const char* ptr = slice.data();

size_t left = slice.size();

bool begin = true;

然后进入一个do{}while循环，直到写入出错，或者成功写入全部数据，如下：

S1 首先查看当前block是否<7，如果<7则补位，并重置block偏移。

dest_->Append(Slice("\x00\x00\x00\x00\x00\x00",leftover));

block_offset_ = 0;

S2 计算block剩余大小，以及本次log record可写入数据长度

    const size_t avail =kBlockSize - block_offset_ - kHeaderSize;

    const size_t fragment_length = (left <avail) ? left : avail;

S3 根据两个值，判断log type

    RecordType type;

    const bool end = (left ==fragment_length); // 两者相等，表明写完

    if (begin && end)  type = kFullType;

    else if (begin)     type = kFirstType;

    else if (end)       type = kLastType;

    else             type = kMiddleType;

 S4 调用EmitPhysicalRecord函数，append日志；并更新指针、剩余长度和begin标记。

    s = EmitPhysicalRecord(type, ptr,fragment_length);

    ptr += fragment_length;

    left -= fragment_length;

begin = false;

接下来看看EmitPhysicalRecord函数，这是实际写入的地方，涉及到log的存储格式。函数声明为：StatusWriter::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n)

参数ptr为用户record数据，参数n为record长度，不包含log header。

S1 计算header，并Append到log文件，共7byte格式为：

| CRC32 (4 byte) | payload length lower + high (2 byte) | type (1byte)|

char buf[kHeaderSize];

  buf[4] = static_cast<char>(n& 0xff);

  buf[5] =static_cast<char>(n >> 8);

  buf[6] =static_cast<char>(t);

  // 计算record type和payload的CRC校验值

  uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);

  crc = crc32c::Mask(crc);        // 空间调整

  EncodeFixed32(buf, crc);

  dest_->Append(Slice(buf,kHeaderSize));

S2 写入payload，并Flush，更新block的当前偏移

    s =dest_->Append(Slice(ptr, n));

    s = dest_->Flush();

    block_offset_ += kHeaderSize +n;

以上就是写日志的逻辑，很直观。

 

 

[cpp] view plaincopy
 
  1. <span style="font-size:18px;">// 记录类型  
  2. enum RecordType {  
  3.             // Zero is reserved for preallocated files  
  4.             kZeroType = 0,  
  5.   
  6.             kFullType = 1,  
  7.   
  8.             // For fragments  
  9.             kFirstType = 2,  
  10.             kMiddleType = 3,  
  11.             kLastType = 4  
  12. };  
  13.   
  14. static const int kBlockSize = 32768;        // 32k Block  
  15.   
  16. // recored header is checksum (4 bytes), length (2 bytes), type (1 byte).  
  17. static const int kHeaderSize = 4 + 2 + 1;</span>  

 

写日志类Writer：

[cpp] view plaincopy
 
    1. <span style="font-size:18px;">  namespace log {  
    2.         class Writer {  
    3.             public:  
    4.             // Create a writer that will append data to "*dest".  
    5.             // "*dest" must be initially empty.  
    6.             // "*dest" must remain live while this Writer is in use.  
    7.             explicit Writer(WritableFile* dest);  
    8.             ~Writer(){}  
    9.   
    10.             Status AddRecord(const Slice& slice);                       // 添加一个记录  
    11.   
    12.             private:  
    13.             WritableFile* dest_;                                        // class WritableFile;为写文件类  
    14.             int block_offset_;       // Current offset in block  
    15.   
    16.             // crc32c values for all supported record types.  These are  
    17.             // pre-computed to reduce the overhead of computing the crc of the  
    18.             // record type stored in the header.  
    19.             uint32_t type_crc_[kMaxRecordType + 1];                     // 每种type都预先计算出CRC，kMaxRecordType = kLastType;  
    20.   
    21.             Status EmitPhysicalRecord(RecordType type, const char* ptr, size_t length);// 写入一个Record  
    22.   
    23.             // No copying allowed  
    24.             Writer(const Writer&);                                  // 禁止拷贝构造函数及赋值运算符重载  
    25.             void operator=(const Writer&);  
    26.             };  
    27.     }  
    28.   
    29.         Writer::Writer(WritableFile* dest)                              // 构造函数，参数：写文件句柄  
    30.          : dest_(dest),  
    31.          block_offset_(0) {  
    32.             for (int i = 0; i <= kMaxRecordType; i++) {  
    33.                 char t = static_cast<char>(i);  
    34.                 type_crc_[i] = crc32c::Value(&t, 1);                        // 首先计算每个Type对应的CRC  
    35.             }  
    36.         }  
    37.           
    38.         Status Writer::AddRecord(const Slice& slice) {                  // 添加一个记录  
    39.             const char* ptr = slice.data();  
    40.             size_t left = slice.size();  
    41.   
    42.             // Fragment the record if necessary and emit it.  Note that if slice  
    43.             // is empty, we still want to iterate once to emit a single     // 如果Slice为空，则增加一个zero-length的记录  
    44.             // zero-length record  
    45.             Status s;  
    46.             bool begin = true;  
    47.             do {  
    48.                 const int leftover = kBlockSize - block_offset_;            // 当前Block剩余容量  
    49.                 assert(leftover >= 0);  
    50.                 if (leftover < kHeaderSize) {                            // 剩余容量比kHeaderSize还小，则填充trailer  
    51.                     // Switch to a new block  
    52.                     if (leftover > 0) {  
    53.                         // Fill the trailer (literal below relies on kHeaderSize being 7)  
    54.                         assert(kHeaderSize == 7);  
    55.                         dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));  // leftover<7, dest_追加leftover个0  
    56.                     }  
    57.                     block_offset_ = 0;  
    58.                 }  
    59.   
    60.                 // Invariant: we never leave < kHeaderSize bytes in a block.  
    61.                 assert(kBlockSize - block_offset_ - kHeaderSize >= 0);  
    62.   
    63.                 const size_t avail = kBlockSize - block_offset_ - kHeaderSize; // 当前block剩余可用大小(除去kHeaderSize)  
    64.                 const size_t fragment_length = (left < avail) ? left : avail;  // 分片  
    65.   
    66.                 RecordType type;  
    67.                 const bool end = (left == fragment_length);                    // 是否为最后一个  
    68.                 if (begin && end) {                                   // 开始 && 结束，则type为FullType  
    69.                     type = kFullType;  
    70.                 } else if (begin) {                                   // 开始 && 非结束，则type为kFirstType  
    71.                     type = kFirstType;  
    72.                 } else if (end) {                                         // 非开始 && 结束，则type为kLastType  
    73.                     type = kLastType;  
    74.                 } else {                                              // 其它为kMiddleType  
    75.                     type = kMiddleType;  
    76.                 }  
    77.   
    78.                 s = EmitPhysicalRecord(type, ptr, fragment_length);           // 保存一条fragment_length字节长度的数据到log文件，类型为type，开始地址为ptr  
    79.                 if(!s.ok()){                                          // 写入失败，则跳出循环  
    80.                     break ;  
    81.                 }  
    82.                 ptr += fragment_length;  
    83.                 left -= fragment_length;  
    84.                 begin = false;  
    85.             } while (/*s.ok() &&*/ left > 0);  
    86.             return s;  
    87.         }  
    88.           
    89.         // 保存一条n字节长度的记录，记录类型为t，记录数据开始地址为ptr  
    90.         Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n)   
    91.         {  
    92.             assert(n <= 0xffff);  // Must fit in two bytes  
    93.             assert(block_offset_ + kHeaderSize + n <= kBlockSize);  
    94.   
    95.             // Format the header  
    96.             char buf[kHeaderSize];                              // 7bytes: CheckSum(4) + 记录长度(2) + Type(1)  
    97.             buf[4] = static_cast<char>(n & 0xff);  
    98.             buf[5] = static_cast<char>(n >> 8 & 0xff);              // 长度高位在后  
    99.             buf[6] = static_cast<char>(t);  
    100.   
    101.             // Compute the crc of the record type and the payload.  
    102.             uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);    // 计算CRC  
    103.             crc = crc32c::Mask(crc);                            // Adjust for storage  
    104.             EncodeFixed32(buf, crc);                                // 将CRC放入header前4字节  
    105.   
    106.             // Write the header and the payload  
    107.             Status s = dest_->Append(Slice(buf, kHeaderSize));       // header写入文件  
    108.             if (s.ok()) {                                           // header写入成功  
    109.                 s = dest_->Append(Slice(ptr, n));                    // 将记录数据写入文件  
    110.                 if (s.ok()) {  
    111.                     s = dest_->Flush();                              // flush到文件  
    112.                 }  
    113.             }  
    114.             block_offset_ += kHeaderSize + n;                       // Block offset移动  
    115.             return s;  
    116.         }  
    117.         </span>  


联系
我们