TheRiver | blog

You have reached the world's edge, none but devils play past here

0%

leveldb源码分析(4) memtable and log

Posted on Edited on
Symbols count in article: 3k Reading time ≈ 3 mins.

项目有用到leveldb,打算最近看看源码，整理个系列文章，这是第4篇memtable and log。源码注释地址

代码细节在github fork的仓库注释了，这里主要记录下大概的流程。从put开始。

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// slice是一个简单的c风格字符串的封装，记录了地址和大小
// 用户传入的string的key和value经由slice对应的ctor进行转换
Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {
  WriteBatch batch; // ctor让rep_ resize为kHeader(12bytes = 8-seq + 4-count)
  batch.Put(key, value);
  return Write(opt, &batch);
}

void WriteBatch::Put(const Slice& key, const Slice& value) {
  // 以第9个字节为起始地址，设置count(int32, 小端字节序)大小
  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);
  // 第13个字节记录type, 0->delete 1->value
  rep_.push_back(static_cast<char>(kTypeValue));  
  PutLengthPrefixedSlice(&rep_, key);   // 第14个字节开始记录varint32(key的大小)+char*(key的data)
  PutLengthPrefixedSlice(&rep_, value); // 继续在后面写入varint32(value的大小)+char*(value的data)
  // 至此，WriteBatch的rep_中记录了一些信息，我画个图表示下
}

1
2
3
4
5
6
7
8
9
10
11
// write主要干了三件事
Status DBImpl::Write(...) {
    // step 1: 判断memtable还有空间没，是否需要新建memtable, 以及level-0的sstable文件个数是否达到阈值，需要慢速写/停止写, 具体在代码仓库记录
    // 这里会new memtable
    MakeRoomForWrite(...)
    // step 2: 生成Log用的格式，并写入
    log_->AddRecord(WriteBatchInternal::Contents(write_batch));
    // step 3: 生成memtable用的格式，并写入
    status = WriteBatchInternal::InsertInto(write_batch, mem_);
    // 2 3步下文分别梳理
}

log

AddRecord(…)

这块比较麻烦，代码里面我都注释了，这块只画个图描述下。日志是按block来处理的，代码里面一个block是32768字节，block由若干个record组成。每次put一个kv就是若干个record, 因为这里分段存储的，先看一个record的格式：

如果一个put的kv可以在block的avail剩余空间内存储，则type=kFullType, 只需要一个record:

如果block遗留空间不够，则要拆分为多个block, 可能是一个begin(1个) + middle(0-n个) + end(1个),如图：

另外需要注意的，如果一个block的剩余空间小于一个header(7个字节)，则去下一个block存储，也就是说data会被拆分到多个block, 但一个header是不能被拆分的。还有就是每次拼成一个record都会被flush刷盘。record里面的data就是rep_ ，没有再转换。

memtable

1
2
3
4
5
6
7
WriteBatchInternal::InsertInto(write_batch, mem_)
    Iterate(&inserter)
        remove rep_前面13个字节
        handler->Put(key, value)
            mem_->Add(sequence_, kTypeValue, key, value)
        handler->Delete(key)
            mem_->Add(sequence_, kTypeDeletion, key, Slice())

memtable先将数据存在heap, 然后把地址放到skiplist, 这里有一些数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MemTable::Add(...)
{
    // Format of an entry is concatenation of:
    //  key_size     : varint32 of internal_key.size()
    //  key bytes    : char[internal_key.size()]
    //  value_size   : varint32 of value.size()
    //  value bytes  : char[value.size()]
    const size_t encoded_len = VarintLength(internal_key_size) +
                             internal_key_size + VarintLength(val_size) +
                             val_size;
    arena_.Allocate(encoded_len);
    EncodeVarint32(buf, internal_key_size);
    memcpy(p, key.data(), key_size);
    EncodeFixed64(p, (s << 8) | type);
    EncodeVarint32(p, val_size);
    memcpy(p, value.data(), val_size);

    table_.Insert(buf);
}

这里申请了一块内存，保存了key和value的值，大小是:

1
2
3
4
    encoded_len
    (key-len + key-data) + (seq) + (val-len + val-data)
->  (varint32 + char*) + (int64) + (varint32 + char*)
->  (1-5 + n) + 8 + (1-5 + n)bytes

然后把这块内存地址传给skiplist, 建立索引，这块我画个图记录下。skiplist初始化后是new了一块空间，用head_指过去，如图：

插入节点后：

1
2
3
4
5
Insert
    FindGreaterOrEqual  // 找插入点
    RandomHeight        // 随机生成高度
    NewNode             // new heap
    SetNext             // 完善链表

reference

https://web.archive.org/web/20120131105110/http://rdc.taobao.com/blog/cs/wp-content/plugins/leveldb%E5%AE%9E%E7%8E%B0%E8%A7%A3%E6%9E%90.pdf

----------- ending -----------