Archive

Archive for October, 2019

leveldb阅读笔记—数据写入

October 24th, 2019 No comments

leveldb的写入可以简单的调用方法.

Status Put(const WriteOptions& options, const Slice& key,
                   const Slice& value) = 0;

其中key和value都可以是任何byte数据. 且可以是任意长度. 但是key的长度尽量越短越好, 这样有助于提供效率.

向leveldb的写入过程是比较简单的. 下图是一个 简化以后的流程, 大致上描述了写入的全过程. 去掉了诸如后台压缩线程的启动等内容.

write flow

首先, 不管是调动DB::Put 还是DB::Write最终都会走到Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates)这个函数来.

首先, leveldb会把updates写入一个deque变量writers_中.

Writer w(&mutex_);
w.batch = updates;
w.sync = options.sync;
w.done = false;

MutexLock l(&mutex_);
writers_.push_back(&w);

然后, leveldb会去检查当前的memory table是否还有足够的空间可以容纳下当前的这一次写入. 不行的话就flush当前的数据到disk, 然后启动新的memory table.

Status DBImpl::MakeRoomForWrite(bool force) {
  bool allow_delay = !force;
  Status s;
  while (true) {
    if (!bg_error_.ok()) {
      // 后台压缩线程如果出现了错误, 就在这里把错误返回出去
      s = bg_error_; 
      break;
    } else if (allow_delay && versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger) {
      // level0的文件数量太多, 此时后台压缩线程应该还在工作中. 
      // 所以这里暂停一下, 不要让大量的写入让level0的文件数量越来越多.
      // 这里因为释放了mutex_这把锁. 所以可能会造成writers_中有多个writeBatch
      mutex_.Unlock();
      env_->SleepForMicroseconds(1000);
      allow_delay = false;  // Do not delay a single write more than once
      mutex_.Lock();
    } else if (!force &&
               (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)) {
      // 当前memory table还可用.
      break;
    } else if (imm_ != nullptr) {
      // imm还存在着, 表明后台的压缩线程还未执行完毕
      background_work_finished_signal_.Wait();
    } else if (versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger) {
      // level0的文件实在是太多, 强行等待压缩线程完成其工作.
      background_work_finished_signal_.Wait();
    } else {
      // memory table使用的内存已经超标了, 而且imm也已经被flush到disk
      // 在这里将当前的memory table设置为imm(也就是imutable memory table)
      // 然后再产生一个新的memory table. writes_里面包含的数据都往这个心的
      // memory table中写入了.
      ...
      log_ = new log::Writer(lfile);
      imm_ = mem_;
      has_imm_.store(true, std::memory_order_release);
      mem_ = new MemTable(internal_comparator_);
      mem_->Ref();
      force = false;
      // 这里尝试着启动一下后台压缩线程, 因为产生了一个新的imm.
      MaybeScheduleCompaction();
    }
  }

上述代码描述了MakeRoomForWrite所做的事情

  • 如果后台压缩线程出错了, 那么将这个错误通过write这个线程返回回去
  • 如果level 0的文件数量超过了8个, 那么稍微等一下后台压缩线程, 免得写入太快导致后台压缩线程来不及工作. 不过这里只是稍微等待1ms时间.
  • 如果immutable memory table(imm)还没有被flush到disk, 那么等待后台线程完成这个工作
  • 如果文件实在是太多了, 超过了12个, 那么久强行等待后台压缩线程工作结束
  • 上述条件都不满足, 并且当前的memory table(mm)使用的空间已经超过预设的4M, 那么使用当前mm替换imm, 然后产生一个新的mm供后续写入

运行到这里, 表明mm有足够的空间可以容纳当前的数据. leveldb开始对writers_里面的数据进行打包. 上面MakeRoomForWrite里面如果level 0的文件数量超过8, leveldb会等待1ms时间, 在这个等待的时间里面, leveldb暂时会释放mutex锁. 这就可能导致在这个等待期间内.有新的线程插入新的数据. 所以这时writers里面可能会有多个batch形成的一个batchlist. 打包的任务就是将这些batch打包在一起形成一个新的batch. 但是也有一些限制. 新的batch的size不能超过1M. 并且如果batchlist[0]的大小不超过128K的话, 那么新的batch size不超过batchlist[0].size() + 128K.

数据打包好了以后, leveldb会暂时释放开mutex, 然后向log文件中写入打包好的数据. 然后把这个打包的数据写入memory table. memory table的主体数据结构是一个SkipList. 所以写入的时候实际上又会把刚才打包的数据一个一个拆开成key-value pair. 实际上写入到memory table的时候的key并不是用户传入的key, 而是InternalKey(参见数据结构篇). InternalKey有一个sequenceNumber和一个Type. type很简单, 如果是插入数据,type=1(kTypeValue). 如果是删除数据, type=0(kTypeDeletetion). 而sequence number在每次向skip list插入一个数据以后sequence number都会加一. 这样可以保证在skip list里面的数据是没有重复key的. 我猜这也是为何leveldb的skiplist不允许有重复key的理由.当后台线程被启动以后, 会将imm的数据flush到level0的sst文件中去, 同时该文件的一些metadata如最小的key和最大的key以及文件的size会同version记录到manifest文件中去. 至此, write的流程结束. 后续leveldb会在压缩(整理)后台线程中将imm的数据flush到level0的文件中去.

Categories: programming Tags: ,

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

October 21st, 2019 No 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: ,

renew

October 10th, 2019 No comments

这个地方已经荒的不像样了, 近来整理一下以前记录的东西放到这里来. 也算作一个知识的renew.

Categories: mutter Tags: