LevelDB源码之二MemTable

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。

表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     }

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的必要封装。

LevelDB源码之二MemTable

标签：