Home > programming > leveldb源码阅读笔记 — 基本数据结构

leveldb源码阅读笔记 — 基本数据结构

October 21st, 2019 Leave a comment Go to comments

我们先来看一下leveldb里面的主要的数据机构, 以方便后续代码阅读.

我们知道leveldb对于存入的数据首先是放在内存中的memory table(MemTable)中. 这个MemTable其实是一个SkipList, SkipList例如不同level的指向同level的下一个node指针来达到快速查找的目的. 如图(该图片下载自这里). SkipList的详细信息可以查看这里.

skiplist

当我们插入一个key-value pair到leveldb的时候, 我们用到的这个key叫做user-key. leveldb里面有好几个Key.

lookup key

图上有3个key, LookupKey, InternalKey和UserKey. 其中UserKey就是用户的数据的key, LookupKey是在做查询的时候使用的. InternalKey是leveldb内部使用的key. LookupKey是包含length, userkey以及sequence+type. 这里面, length是整个internalkey的数据长度. seq+type一起构成一个8byte的数据. 其中低8位是key的类型, 高56位是sequence.

这个sequence我们需要讲一下到底是个什么东西. 在向leveldb存储key-value pair的时候会给每一个key-value pair生成一个sequence, 每写入一个pair, sequence就加一. 这样可以保证每一个pair的InternalKey都是不一样的. 在查询的时候也会带上一个sequence, 可能是某个snapshot的sequence也可能是查找当时最新的sequence. 这样可以将查找过程限制在某个snapshot或者查询当时的基础上. 避免在查找的过程中找到刚刚新插入的数据.

LookupKey的的数据结构是这样的

class LookupKey {
public:
  // Return a key suitable for lookup in a MemTable.
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
private:
  const char* start_;
  const char* kstart_;
  const char* end_;
  char space_[200];  // Avoid allocation for short keys
};

我们可以看到LookupKey有一个200字节的space这个field. 这个是为了在userkey的长度 <= 187的时候不需要额外在堆上分配内存而设置的. leveldb里面使用LookupKey的时候都是直接在栈上使用的. 这样可以很好的减少对于对上内存分配的次数.

我们看LookupKey可以看到它在编码的时候使用了诸如Variant32, Fixed64这些方式. leveldb对于数字的存储方式主要有 Fixed32, Fixed64, Varint32, Varint64这四种. leveldb默认是按照小头在前的方式编码数字, 对于Fixed系列, 那么就是直接的内存拷贝就可以了. 对于Variant系列, 编码方式如下

static const int B = 128;
uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
while (v >= B) {
  //如果数据本身>=128, 那么首先当前只是用其最低7为并且将低8为置为1, 表明还有后续的数据
  *(ptr++) = v | B;
  v >>= 7;
}
*(ptr++) = static_cast<uint8_t>(v);

当然经过这种格式编码以后, 最极端情况下, 如果32bit数据大于等于1<<28会使用5bytes来存储, 或者64bit数据大于等于1<<56会使用8bytes来存储. 当然, 一般情况下如果数值越小节约的存储空间越多. 如下面这个图片.

Varint的读取是写入的逆过程, 首先读取当前的低7位. 然后当前byte的最高位为1的话就将下一个字节的低7位左移以后作为数据的高位, 且一直这样处理到数据结束或者高位为0. 下面的代码是读取Varint32的代码, Varint64的代码是类似的.

uint32_t result = 0;
for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
  uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
  p++;
  if (byte & 128) {
    // More bytes are present
    result |= ((byte & 127) << shift);
  } else {
    result |= (byte << shift);
    *value = result;
  }
}

当我们写入数据的时候, 会首先写入一个日志文件, 然后才会写入到memory table中. 那么这个日志文件是什么样子的呢. 实际上呢在leveldb有两种数据都会使用日志文件的格式来记录, 第一个就是我们插入key-value pair的数据的时候, 另外还有一个manifest文件记录数据的时候. 这两种文件记录的数据本身不一样, 但是在log文件这一层的格式是一致的. 我们这里先看看log文件本身的格式是啥样的.

log文件按照Block为单位来记录数据, 每一个Block都是固定的32Kbytes. 然后在每一个Block里面数据按照Record为单位记录数据. 每一个Record由RecordHeader和RecordBody构成, 如图

log record layout

RecordHeader一共7个字节, 分别是4byte是的CRC, 2bytes的length和1byte的type. 这里的length记录的是RecordBody的长度. Record的type有如下几种

enum RecordType {
  // Zero is reserved for preallocated files
  kZeroType = 0,

  kFullType = 1,

  // For fragments
  kFirstType = 2,
  kMiddleType = 3,
  kLastType = 4
};

由于Log的Record的长度是固定的, 但是一次数据的大小是不固定的, 所以leveldb使用不同的record来组成一个完整的数据. 如果一个record容纳不了数据, 那么就会将数据分成很多的record, 然后用type来表示当前的这个record是数据本身哪一段. 在读取的数据的时候会根据type来使用多个record合成原来的数据.如果record可以容纳数据, 那么很简单使用type为kFullType即可.

有一个需要注意的地方是, 如果一个Block在写入record后剩余的空间<7bytes,也就是无法容纳一个RecordHeader的话, 那么这些剩下的部分全部填0. 并且被忽略掉. 而如果Block的剩余空间刚好是7bytes, 这个时候level会记录一个length为0, 且crc为0x49258fd2的一个record.

接下面我们来看看leveldb里面的table文件的格式是什么样子的. leveldb记录的用户数据就保存在table文件中. 我们这里先不关心数据是如何记录到table文件的, 我们先看看table文件的格式是怎么样的.

每一个table文件由 DataBlock, FilterBlock, IndexBlock, Footer构成. 这里记录一下leveldb官方文档上对于table格式的描述

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]  (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

可以看出其实Table文件就是一堆的Block和一个Footer构成, 只是不同的Block记录了不同的数据. 当前一共有4中类型的Block. 分别是

  1. DataBlock, 这里记录着用户数据, 就是你调用Put方法放入的数据编码以后保存在这个地方.
  2. MetaBlock, 当前leveldb支持BloomFilter的MetaBlock.
  3. MetaIndex Block
  4. Index Block

这些不同Block承载的数据都有自己的格式, 但是Block本身的格式都是一样的. 我们来看看Block的格式.

block format

一个Block的原始数据是大约4K, 可以超过4K这个限制. 但是压缩以后就不知道具体是多大了. Block分为3个部分, 如图, 最上面的是数据区, 每一个key-value pair被编码以后一个接着一个的放到这里. 紧接着是记录restarts offset的区域, 每一个记录的restart offset都是Fixed32编码的. 这个restarts是用来干什么的呢? 这个和block里面存放数据的方式有关.

table key-value format

leveldb在存储用户数据的时候, 首先会对key和value进行编码. 如上图, 在向Block里写入key-value pair的时候并不是直接写入key和value的值. 而是对key做了一个前缀压缩, 因为在imm里面的key是有序的, 所以就有了做前缀压缩的基础. 这个前缀压缩的方式是找到当前的key和上一个key的longest common prefix. 然后记录这个prefix的长度记为shared, 当前key的剩下部分的长度记为non_shared. 上图中的前两个field就是shared和non_shared的Variant32编码后的数据, 紧接着的数据是value的size的Variant32编码数据. 然后对于key的数据就只保存non_shared部分.

这样每一个key的内容都依赖于前一个key的内容一直延续到该Block的第一个key. restarts就是中断这个依赖而设定的, restarts的最大值是16个, 也就是说每过16个key就会强制的将shared设置为0, 全量记录key的内容. 那么在对key进行复原的时候最大多只需要读取16个key的内容即可. restarts里面记录的是每一次全量记录key的时候的offset. 然后在Block的尾部记录一下当前的Block有多少的restarts. 以方便读取的时候找到所有的restarts的数据. 需要注意的是如果是index block的话, 那么允许的最大的restarts数量是1, 也就是全部全量记录.

现在我们来说一下leveldb里面的一个用于缓存Block数据的数据 结构, LRUCache.

LRUCache由一个HashTable和两个双向链表构成. 暂且称其为hash_table, lru_list和inuse_list. 这三个结构的关系是这样的. 所有的数据都在hash_table里面, 这样就可以快速找到这个数据. 如果一个数据正在被使用, 那么这个数据只会记录在inuse_list里面. 如果一个数据没有被使用, 那么这个数据只会被记录在lru_list里面. LRUCache有一个capacity, 这个不是缓存的条目的数量, 而是缓存的数据的size之和. 这个capacity默认是8M. 当插入到LRUCache的数据过多的时候, 超过设定的capacity就会从lru_list里面按照从老到新的顺序删除一部分数据. 如果一个数据本来在lru_list里面, 这个时候被使用了, 那么就会从lru_list里面摘除, 同时放入到inuse_list. 相反的, 如果一个在inuse_list里面的数据不被使用, 那么就会脱离inuse_list, 然后加入到lru_list中.

Categories: programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.