log日志文件-leveldb源码剖析(4)

往leveldb写一个KV对时先写log,再写MemTable,这样完成一次写入,写log是追加顺序写文件,写MemTable是跳表插入写内存,随机写转化成顺序写,只涉及一次磁盘IO及一次内存写,因此leveldb写入速度非常快。先写log也是为防止发生如进程挂掉时,MemTable的数据仍然可以从log进行重建恢复,不会造成数据丢失。

log文件的读写均是顺序IO,因此不需要额外的索引信息。

leveldb把每次写操作都会以日志文件记录下来,先来看格式,相关定义如下:

namespace log {

enum 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;

// Header is checksum (4 bytes), length (2 bytes), type (1 byte).
static const int kHeaderSize = 4 + 2 + 1;

}  

日志是分块写的,每块大小为32K,每条记录有7个字节的头部,前四字节为CRC校验,中间两字节为长度,最后一字节为记录类型。块大小固定有限,而记录有可能跨块,因此有三个枚举值kFirstType、kMiddleType、kLastType分别用来标记记录位置。

Writer类提供了AddRecord的写接口,再看具体实现:

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;
  bool begin = true;
  do {
    const int leftover = kBlockSize - block_offset_;
    assert(leftover >= 0);
    if (leftover < kHeaderSize) {
      // Switch to a new block
      if (leftover > 0) {
        // Fill the trailer (literal below relies on kHeaderSize being 7)
        assert(kHeaderSize == 7);
        dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));
      }
      block_offset_ = 0;
    }

    // Invariant: we never leave < kHeaderSize bytes in a block.
    assert(kBlockSize - block_offset_ - kHeaderSize >= 0);

    const size_t avail = kBlockSize - block_offset_ - kHeaderSize;
    const size_t fragment_length = (left < avail) ? left : avail;

    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;
    }

    s = EmitPhysicalRecord(type, ptr, fragment_length);
    ptr += fragment_length;
    left -= fragment_length;
    begin = false;
  } while (s.ok() && left > 0);
  return s;
}

Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) {
  assert(n <= 0xffff);  // Must fit in two bytes
  assert(block_offset_ + kHeaderSize + n <= kBlockSize);

  // Format the header
  char buf[kHeaderSize];
  buf[4] = static_cast(n & 0xff);
  buf[5] = static_cast(n >> 8);
  buf[6] = static_cast(t);

  // Compute the crc of the record type and the payload.
  uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);
  crc = crc32c::Mask(crc);                 // Adjust for storage
  EncodeFixed32(buf, crc);

  // Write the header and the payload
  Status s = dest_->Append(Slice(buf, kHeaderSize));
  if (s.ok()) {
    s = dest_->Append(Slice(ptr, n));
    if (s.ok()) {
      s = dest_->Flush();
    }
  }
  block_offset_ += kHeaderSize + n;
  return s;
}

块大小固定32K,可能跨块,分片写入,首先计算当前块剩余是否足够容纳记录头,若不能全部填充空串(ASCII码0),若恰好仅能容纳记录头则允许插入一次0长的记录;若当前块剩余大于记录头的7字节大小,则计算是否需要分片及设置相应记录标记;之后设置相应记录头和计算CRC校验,写入实际记录内容,写状态成功后flush数据到页面缓存(page cache)。

leveldb写记录使用了CRC32校验,这里来复习下CRC校验算法:
采用 CRC 校验时,发送方和接收方用同一个生成多项式g(x),g(x)是一个GF(2)多项式,并且g(x)的首位和最后一位的系数必须为1。
CRC的处理方法是:发送方用发送数据的二进制多项式t(x)除以g(x),得到余数y(x)作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。设生成多项式是r阶的(最高位是x^r)具体步骤如下面的描述。
发送方:
1 )在发送的 m 位数据的二进制多项式 t(x) 后添加 r 个 0 ,扩张到 m+ r 位,以容纳 r 位的校验码,追加 0 后的二进制多项式为 T(x) ;
2 )用 T(x) 除以生成多项式 g(x) ,得到 r 位的余数 y(x) ,它就是 CRC 校验码;
3 )把 y(x) 追加到 t(x) 后面,此时的数据 s(x) 就是包含了 CRC 校验码的待发送字符串;由于 s(x) = t(x) y(x) ,因此 s(x) 肯定能被 g(x) 除尽。
接收方:
1 )接收数据 n(x) ,这个 n(x) 就是包含了 CRC 校验码的 m+r 位数据;
2 )计算 n(x) 除以 g(x) ,如果余数为 0 则表示传输过程没有错误,否则表示有错误。从 n(x) 去掉尾部的 r 位数据,得到的就是原始数据。
生成多项式不是随意选择的,标准的CRC32生成多项式:
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11+ x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
以16进制表示就是0x04C11DB7。
实际的CRC32算法是面向字节的,而非低效的单比特处理,leveldb对该算法的具体代码实现,有时间再仔细分析。

为什么以32K这种固定块大小写数据?个人认为相对于写KV记录大小和读取记录的buffer数据块,32K可能是在性能上比较适宜的大小。

再来看日志记录的读取,Reader类提供了ReadRecord的读接口:

bool Reader::ReadRecord(Slice* record, std::string* scratch) {
  if (last_record_offset_ < initial_offset_) {
    if (!SkipToInitialBlock()) {
      return false;
    }
  }

  scratch->clear();
  record->clear();
  bool in_fragmented_record = false;
  // Record offset of the logical record that we're reading
  // 0 is a dummy value to make compilers happy
  uint64_t prospective_record_offset = 0;

  Slice fragment;
  while (true) {
    const unsigned int record_type = ReadPhysicalRecord(&fragment);

    // ReadPhysicalRecord may have only had an empty trailer remaining in its
    // internal buffer. Calculate the offset of the next physical record now
    // that it has returned, properly accounting for its header size.
    uint64_t physical_record_offset =
        end_of_buffer_offset_ - buffer_.size() - kHeaderSize - fragment.size();

    if (resyncing_) {
      if (record_type == kMiddleType) {
        continue;
      } else if (record_type == kLastType) {
        resyncing_ = false;
        continue;
      } else {
        resyncing_ = false;
      }
    }

    switch (record_type) {
      case kFullType:
        if (in_fragmented_record) {
          // Handle bug in earlier versions of log::Writer where
          // it could emit an empty kFirstType record at the tail end
          // of a block followed by a kFullType or kFirstType record
          // at the beginning of the next block.
          if (scratch->empty()) {
            in_fragmented_record = false;
          } else {
            ReportCorruption(scratch->size(), "partial record without end(1)");
          }
        }
        prospective_record_offset = physical_record_offset;
        scratch->clear();
        *record = fragment;
        last_record_offset_ = prospective_record_offset;
        return true;

      case kFirstType:
        if (in_fragmented_record) {
          // Handle bug in earlier versions of log::Writer where
          // it could emit an empty kFirstType record at the tail end
          // of a block followed by a kFullType or kFirstType record
          // at the beginning of the next block.
          if (scratch->empty()) {
            in_fragmented_record = false;
          } else {
            ReportCorruption(scratch->size(), "partial record without end(2)");
          }
        }
        prospective_record_offset = physical_record_offset;
        scratch->assign(fragment.data(), fragment.size());
        in_fragmented_record = true;
        break;

      case kMiddleType:
        if (!in_fragmented_record) {
          ReportCorruption(fragment.size(),
                           "missing start of fragmented record(1)");
        } else {
          scratch->append(fragment.data(), fragment.size());
        }
        break;

      case kLastType:
        if (!in_fragmented_record) {
          ReportCorruption(fragment.size(),
                           "missing start of fragmented record(2)");
        } else {
          scratch->append(fragment.data(), fragment.size());
          *record = Slice(*scratch);
          last_record_offset_ = prospective_record_offset;
          return true;
        }
        break;

      case kEof:
        if (in_fragmented_record) {
          // This can be caused by the writer dying immediately after
          // writing a physical record but before completing the next; don't
          // treat it as a corruption, just ignore the entire logical record.
          scratch->clear();
        }
        return false;

      case kBadRecord:
        if (in_fragmented_record) {
          ReportCorruption(scratch->size(), "error in middle of record");
          in_fragmented_record = false;
          scratch->clear();
        }
        break;

      default: {
        char buf[40];
        snprintf(buf, sizeof(buf), "unknown record type %u", record_type);
        ReportCorruption(
            (fragment.size() + (in_fragmented_record ? scratch->size() : 0)),
            buf);
        in_fragmented_record = false;
        scratch->clear();
        break;
      }
    }
  }
  return false;
}

Reader构造函数是可以指定初始读偏移(initial_offset_)的,如果上一次已读取记录的偏移(last_record_offset_)小于初始偏移,则在读取时首先需要校正读起始位置到当前块(32K)起始位置,若块内偏移在尾部不足记录头的大小范围内,则跳到下一块,如果skip调整失败直接返回读失败;下面是读取实际物理记录,初次读取可能需要resyncing跳过非初始块;也有可能读取到尾部0长的记录,其记录类型仅可能为kFirstType(某条新记录的初始),紧邻下一块可能为kFirstType或kFullType,Reader对这两种情形实现上做了兼容考虑;读取记录是否分片(fragment)跨块用in_fragmented_record来标记,结合该标记和记录类型,完成相应判断返回结果和读状态。
着重说明下几个成员变量,initial_offset_是指定的初始读偏移(相对于log文件),last_record_offset_是已读取到的记录偏移(相对于当前block块),end_of_buffer_offset_是已读取块偏移(相对于log文件),buffer_不仅用来缓存块数据,也用来配合计算实际读取的块内记录偏移。

下面看读取实际的记录过程:

unsigned int Reader::ReadPhysicalRecord(Slice* result) {
  while (true) {
    if (buffer_.size() < kHeaderSize) {
      if (!eof_) {
        // Last read was a full read, so this is a trailer to skip
        buffer_.clear();
        Status status = file_->Read(kBlockSize, &buffer_, backing_store_);
        end_of_buffer_offset_ += buffer_.size();
        if (!status.ok()) {
          buffer_.clear();
          ReportDrop(kBlockSize, status);
          eof_ = true;
          return kEof;
        } else if (buffer_.size() < kBlockSize) {
          eof_ = true;
        }
        continue;
      } else {
        // Note that if buffer_ is non-empty, we have a truncated header at the
        // end of the file, which can be caused by the writer crashing in the
        // middle of writing the header. Instead of considering this an error,
        // just report EOF.
        buffer_.clear();
        return kEof;
      }
    }

    // Parse the header
    const char* header = buffer_.data();
    const uint32_t a = static_cast(header[4]) & 0xff;
    const uint32_t b = static_cast(header[5]) & 0xff;
    const unsigned int type = header[6];
    const uint32_t length = a | (b << 8);
    if (kHeaderSize + length > buffer_.size()) {
      size_t drop_size = buffer_.size();
      buffer_.clear();
      if (!eof_) {
        ReportCorruption(drop_size, "bad record length");
        return kBadRecord;
      }
      // If the end of the file has been reached without reading |length| bytes
      // of payload, assume the writer died in the middle of writing the record.
      // Don't report a corruption.
      return kEof;
    }

    if (type == kZeroType && length == 0) {
      // Skip zero length record without reporting any drops since
      // such records are produced by the mmap based writing code in
      // env_posix.cc that preallocates file regions.
      buffer_.clear();
      return kBadRecord;
    }

    // Check crc
    if (checksum_) {
      uint32_t expected_crc = crc32c::Unmask(DecodeFixed32(header));
      uint32_t actual_crc = crc32c::Value(header + 6, 1 + length);
      if (actual_crc != expected_crc) {
        // Drop the rest of the buffer since "length" itself may have
        // been corrupted and if we trust it, we could find some
        // fragment of a real log record that just happens to look
        // like a valid log record.
        size_t drop_size = buffer_.size();
        buffer_.clear();
        ReportCorruption(drop_size, "checksum mismatch");
        return kBadRecord;
      }
    }

    buffer_.remove_prefix(kHeaderSize + length);

    // Skip physical record that started before initial_offset_
    if (end_of_buffer_offset_ - buffer_.size() - kHeaderSize - length <
        initial_offset_) {
      result->clear();
      return kBadRecord;
    }

    *result = Slice(header + kHeaderSize, length);
    return type;
  }
}

内部使用了buffer_缓存当前数据块,eof_用来标记文件是否读到结束,接着是解析头部,如果指定了CRC32校验,则对当前记录进行校验,更新buffer_已读取偏移以备下次顺序IO使用,最后构造实际数据填充结果。

leveldb作者在doc/log_format.txt中对这种日志格式设计的优缺点给予了说明,好处如下:
(1)不需要做额外的启发式resyncing,出错直接跳到下一块。
(2)支持如mapreduce所需的文件切分机制,按照完整逻辑记录切分即可。
(3)大记录读写无需添加外信息或buffer。
缺点:
(1)小记录无pack。
(2)不支持压缩。
这两点都可以通过添加新的记录类型支持。

refer:
1. http://blog.csdn.net/sparkliang/article/details/5671510

发表评论

电子邮件地址不会被公开。 必填项已用*标注