分析完KV在内存中的存储,接下来就是操作日志。所有的写操作都必须先成功的append到操作日志中,然后再更新内存memtable。这样做有两个有点:1可以将随机的写IO变成append,极大的提高写磁盘速度;2防止在节点down机导致内存数据丢失,造成数据丢失,这对系统来说是个灾难。
在各种高效的存储系统中,这已经是口水技术了。
在源码下的文档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;
以上就是写日志的逻辑,很直观。
写日志类Writer:
- <span style="font-size:18px;"> namespace log {
- class Writer {
- public:
- // Create a writer that will append data to "*dest".
- // "*dest" must be initially empty.
- // "*dest" must remain live while this Writer is in use.
- explicit Writer(WritableFile* dest);
- ~Writer(){}
- Status AddRecord(const Slice& slice); // 添加一个记录
- private:
- WritableFile* dest_; // class WritableFile;为写文件类
- int block_offset_; // Current offset in block
- // crc32c values for all supported record types. These are
- // pre-computed to reduce the overhead of computing the crc of the
- // record type stored in the header.
- uint32_t type_crc_[kMaxRecordType + 1]; // 每种type都预先计算出CRC,kMaxRecordType = kLastType;
- Status EmitPhysicalRecord(RecordType type, const char* ptr, size_t length);// 写入一个Record
- // No copying allowed
- Writer(const Writer&); // 禁止拷贝构造函数及赋值运算符重载
- void operator=(const Writer&);
- };
- }
- Writer::Writer(WritableFile* dest) // 构造函数,参数:写文件句柄
- : dest_(dest),
- block_offset_(0) {
- for (int i = 0; i <= kMaxRecordType; i++) {
- char t = static_cast<char>(i);
- type_crc_[i] = crc32c::Value(&t, 1); // 首先计算每个Type对应的CRC
- }
- }
- 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 // 如果Slice为空,则增加一个zero-length的记录
- // zero-length record
- Status s;
- bool begin = true;
- do {
- const int leftover = kBlockSize - block_offset_; // 当前Block剩余容量
- assert(leftover >= 0);
- if (leftover < kHeaderSize) { // 剩余容量比kHeaderSize还小,则填充trailer
- // 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)); // leftover<7, dest_追加leftover个0
- }
- 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; // 当前block剩余可用大小(除去kHeaderSize)
- const size_t fragment_length = (left < avail) ? left : avail; // 分片
- RecordType type;
- const bool end = (left == fragment_length); // 是否为最后一个
- if (begin && end) { // 开始 && 结束,则type为FullType
- type = kFullType;
- } else if (begin) { // 开始 && 非结束,则type为kFirstType
- type = kFirstType;
- } else if (end) { // 非开始 && 结束,则type为kLastType
- type = kLastType;
- } else { // 其它为kMiddleType
- type = kMiddleType;
- }
- s = EmitPhysicalRecord(type, ptr, fragment_length); // 保存一条fragment_length字节长度的数据到log文件,类型为type,开始地址为ptr
- if(!s.ok()){ // 写入失败,则跳出循环
- break ;
- }
- ptr += fragment_length;
- left -= fragment_length;
- begin = false;
- } while (/*s.ok() &&*/ left > 0);
- return s;
- }
- // 保存一条n字节长度的记录,记录类型为t,记录数据开始地址为ptr
- 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]; // 7bytes: CheckSum(4) + 记录长度(2) + Type(1)
- buf[4] = static_cast<char>(n & 0xff);
- buf[5] = static_cast<char>(n >> 8 & 0xff); // 长度高位在后
- buf[6] = static_cast<char>(t);
- // Compute the crc of the record type and the payload.
- uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n); // 计算CRC
- crc = crc32c::Mask(crc); // Adjust for storage
- EncodeFixed32(buf, crc); // 将CRC放入header前4字节
- // Write the header and the payload
- Status s = dest_->Append(Slice(buf, kHeaderSize)); // header写入文件
- if (s.ok()) { // header写入成功
- s = dest_->Append(Slice(ptr, n)); // 将记录数据写入文件
- if (s.ok()) {
- s = dest_->Flush(); // flush到文件
- }
- }
- block_offset_ += kHeaderSize + n; // Block offset移动
- return s;
- }
- </span>