你的位置:首页 > 数据库

[数据库]LevelDB源码之二MemTable


MemTable是内存表,在LevelDB中,内存表共两份,分别为:

MemTable* mem_;
MemTable* imm_; // Memtable being compacted

按数据的新旧程度,顺序依次为mem_,imm_,level0,level1,......

关于LevelDB的结构,原理请参见http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html

 

MemTable内部使用了前面介绍的SkipList做为数据存储,其自身封装的主要目的如下:

1. 以一种业务形态出现,即业务抽象

2. LevelDB是Key-Value存储系统,而SkipList的实现为单值存储,需执行用户数据->SkipList数据的编解码处理。

3. MemTable自身特点设计,主要特点如下:

a). 只添加不删除,客户端的删除动作将被转换为一次类型为Deletion的添加动作

b). 按key值及插入顺序排序。

MemTable的实现非常简单,但其中也包含了作者各种设计技巧。

 

在备忘MemTable本身之前,先看几个相关的结构:

  class Arena {  public:    Arena();    ~Arena();    // Return a pointer to a newly allocated memory block of "bytes" bytes.    char* Allocate(size_t bytes);    // Allocate memory with the normal alignment guarantees provided by malloc    char* AllocateAligned(size_t bytes);    // Returns an estimate of the total memory usage of data allocated    // by the arena (including space allocated but not yet used for user    // allocations).    size_t MemoryUsage() const {      return blocks_memory_ + blocks_.capacity() * sizeof(char*);    }    ......}

Arena实际上就是一个Allocator,在Heap上执行内存管理,其好处有二:

1. 提高程序性能:减少Heap调用次数,专有Arena统一分配后返回到应用层。

2. 统一内存管理:分配后无需执行dealloc,当Arena对象释放时,统一释放由其创建的所有内存。

当然,这是个功能并不完善的Allocator,但适用于MemTable的特点3.a。

  class Slice {  public:      ......  private:    const char* data_;    size_t size_;    // Intentionally copyable  };  

Slice的含义和其名称一致,代表了一个数据块,data_为数据地址,size_为数据长度。

Slice一般和Arena配合使用,其仅保持了数据信息,并未拥有数据的所有权。而数据在Arena对象的整个声明周期内有效。

Slice在LevelDB中一般用于传递Key、Value或编解码处理后的数据块。

和string相比,Slice具有的明显好处包括:避免不必要的拷贝动作、具有比string更丰富的语义(可包含任意内容)。

class MemTableIterator : public Iterator{......}

MemTableIterator为SkipList::Iterator的封装类,简单,略。

在LevelDB中,共有三种Key:

1. User Key: 用户传入的Key内容,下表中的Part2.

2. Internal Key: LevelDB内部存储时使用的Key,下表中的Part2-Part3。除User Key外,还包括了本次操作的序号及操作类型信息。

3. MemTable Key: 下表中的Part1-Part3。

Part 1 Part 2Part 3Part 4Part 5
Key Size + 8Key ContentSeq Number << 8 | ValueTypeValue Size Value Content

表1

最后一个比较重要的类InternalKeyComparator,这是Internal Key的比较器,其中的关键在于Compare方法:

  int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {    // Order by:    //  increasing user key (according to user-supplied comparator)    //  decreasing sequence number    //  decreasing type (though sequence# should be enough to disambiguate)    int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));  //首先调用user comparator进行键值比较    if (r == 0) {      const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);      const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);      if (anum > bnum) {  //序号及类型比较比较,即操作版本号比较。较新的操作版本号较高,比较器认为较新的版本<较老的版本或者老版本>新版本        r = -1;      }      else if (anum < bnum) {        r = +1;      }    }    return r;  }

值得注意的是序号及类型的比较,实际上由于任意操作序号的唯一性,类型比较时非必须的。这里同时进行了类型比较也是出于性能的考虑(减少了从中分离序号、类型的工作)。

序号或者说版本号采用的是降序原则,这导致的效果是,比较器认为老版本>新版本,为什么不是新版本>老版本呢?因为Snapshot机制的支持,当用户想查看Snapshot(快照)时,希望找到指定版本号之前的数据。

 

有了以上储备后,再来看MemTable就比较简单了,首先看插入方法Add:

  void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key, const Slice& value)   {    // 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()]    size_t key_size = key.size();    size_t val_size = value.size();    size_t internal_key_size = key_size + 8;    //总长度    const size_t encoded_len =      VarintLength(internal_key_size) + internal_key_size +      VarintLength(val_size) + val_size;    char* buf = arena_.Allocate(encoded_len);    //Key    char* p = EncodeVarint32(buf, internal_key_size);    memcpy(p, key.data(), key_size);    p += key_size;    //Seq Number + Value Type    EncodeFixed64(p, (s << 8) | type);    p += 8;    //Value    p = EncodeVarint32(p, val_size);    memcpy(p, value.data(), val_size);    assert((p + val_size) - buf == encoded_len);        table_.Insert(buf);  }

以下几点备注:

1. MemTable将用户数据编码为表1的结构进行存储,其中Part1、Part4采用了Variant32的存储方式,Part3则采用Fixed64。LevelDB中何处采用Variant、何处采用Fixed的方式,规律尚未摸清,想必也和性能有关?

2. MemTable不提供删除方法,客户端的删除动作将被转换为一次ValueType为Deletion的添加动作,等MemTable需要被Compaction到磁盘时方执行真正的删除。

3. 数据编码完毕后,将数据插入到SkipList中(table_)。

再来看Get方法:

 1   bool MemTable::Get(const LookupKey& key, std::string* value, Status* s)  2   { 3     Slice memkey = key.memtable_key();   4  5     Table::Iterator iter(&table_); 6     iter.Seek(memkey.data()); 7  8     if (iter.Valid()) { 9       // entry format is:10       //  klength varint3211       //  userkey char[klength - 8]12       //  tag   uint6413       //  vlength varint3214       //  value  char[vlength]15       // Check that it belongs to same user key. We do not check the16       // sequence number since the Seek() call above should have skipped17       // all entries with overly large sequence numbers.18       const char* entry = iter.key();19       uint32_t key_length;20       const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);21       if (comparator_.comparator.user_comparator()->Compare(22         Slice(key_ptr, key_length - 8), key.user_key()) == 0) 23       {24         // Correct user key25         const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);26         switch (static_cast<ValueType>(tag & 0xff)) {27         case kTypeValue: {28           Slice v = GetLengthPrefixedSlice(key_ptr + key_length);29           value->assign(v.data(), v.size());30           return true;31         }32         case kTypeDeletion:33           *s = Status::NotFound(Slice());34           return true;35         }36       }37     }38     return false;39   }

Line3的memtable_key即表1中Part1-Part3内容,其中Seq Number在指定了Snapshot时为Snapshot的Seq Number,否则为最后一次更新的Seq Nmuber。

Line6调用SkipList的Seek方法定位,随后校验找到的iter是否和指定的key一致,如果一致并且ValueType为kTypeValue,返回找到的数据,否则查找失败。

 

小结:

1. 性能是第一要义:Arena、Slice、甚至数据编码的Variant都是为此准备的。

2. Seq Number在LevelDB中扮演了重要角色,在数据查找、Snapshot中至关重要。

3. MemTable是SkipList的必要封装。