转载

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 2	Part 3	Part 4	Part 5
Key Size + 8	Key Content	Seq Number << 8 \| ValueType	Value 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  varint32 11             //    userkey  char[klength - 8] 12             //    tag      uint64 13             //    vlength  varint32 14             //    value    char[vlength] 15             // Check that it belongs to same user key.  We do not check the 16             // sequence number since the Seek() call above should have skipped 17             // 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 key 25                 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     }