levelDB源码剖析(10)--MemTable结构

MemTable结构

源码位置与说明
db/skiplist.h : 跳跃表实现
db/memtable.h db/memtable.cc : MemTable的实现

MemTable是levelDB的存储结构，并且其是内存中的组织结构，其内部是有序的。只有当大小到达一定程度时才会被写入到磁盘上的SSTable中，这也就是为什么SSTable中写入kv时要求key是按顺序排布的，因为key再内存中就已经被组织好了。

由于MemTable需要是按照键值对存储，且必须是有序的，所以就不能使用哈希表。对于SortedMap的实现，一般会采用红黑树，不过LevelDB采用的是Skiplist。Skiplist是一种概率性的数据结构，支持SortedMap的所有功能，性能和红黑树相当。

Skiplist

我们先来说一下跳跃表这种数据结构，跳跃表的本体其实就是一个链表，这个链表是有序的。但是链表的查找非常慢，需要从头开始一个一个遍历，考虑到链表本身也是有序的，我们可以为其增加一些索引。

每次查找时，先从最上层的索引开始查找，并且由于链表有序，其实这些索引相当于了二分查找，效率很高。不过这些索引其实是在插入key-value时有一定概率创建出来的，所以不是严格的二分查找。

另外，由于键是不重复的，所以不能保存相同的键。

跳跃表比红黑树的实现简单太多了，所以我们就看一下这部分的源码

template <typename Key, class Comparator>
class SkipList
{
private:
    struct Node; // 结点

private:
    enum
    {
        kMaxHeight = 12 // 跳跃表的最大索引高度
    };

    // 获取当前的最大高度，宽松内存序
    inline int GetMaxHeight() const
    {
        return max_height_.load(std::memory_order_relaxed);
    }

    // 在高度height处创建新的key
    Node *NewNode(const Key &key, int height);

    int RandomHeight();
    bool Equal(const Key &a, const Key &b) const { return (compare_(a, b) == 0); }

    // 如果档key在结点后面就返回true
    bool KeyIsAfterNode(const Key &key, Node *n) const;

    // 返回在key后面最小的结点
    Node *FindGreaterOrEqual(const Key &key, Node **prev) const;

    // 返回比key小的最大结点
    Node *FindLessThan(const Key &key) const;

    // 返回最后一个结点
    Node *FindLast() const;

    Comparator const compare_; // 比较用比较器
    Arena *const arena_;       // 使用Arena类来为结点分配内存

    Node *const head_; // 头结点

    // 最大索引高度
    std::atomic<int> max_height_;

    // Read/written only by Insert(). ？
    Random rnd_;

public:
    // 跳表使用cmp来进行比较key，使用arena来进行内存管理
    explicit SkipList(Comparator cmp, Arena *arena);

    SkipList(const SkipList &) = delete;
    SkipList &operator=(const SkipList &) = delete;

    // 插入key，需要保证没有重复的key
    void Insert(const Key &key);

    // 如果包含就返回true
    bool Contains(const Key &key) const;

    // 迭代器类，迭代key-value
    class Iterator
    {
    public:
        // Initialize an iterator over the specified list.
        // The returned iterator is not valid.
        explicit Iterator(const SkipList *list);

        // Returns true iff the iterator is positioned at a valid node.
        bool Valid() const;

        // Returns the key at the current position.
        // REQUIRES: Valid()
        const Key &key() const;

        // Advances to the next position.
        // REQUIRES: Valid()
        void Next();

        // Advances to the previous position.
        // REQUIRES: Valid()
        void Prev();

        // Advance to the first entry with a key >= target
        void Seek(const Key &target);

        // Position at the first entry in list.
        // Final state of iterator is Valid() iff list is not empty.
        void SeekToFirst();

        // Position at the last entry in list.
        // Final state of iterator is Valid() iff list is not empty.
        void SeekToLast();

    private:
        const SkipList *list_;
        Node *node_;
        // Intentionally copyable
    };
};

跳表是一个类模板，可以传递用于比较keys的比较器和结点的内存管理器，另外，其中还存在可以迭代跳表的迭代器，由于迭代器的实现比较简单，此处就不再赘诉了。由于MemTable位于内存中，所以需要考虑到多个线程对其进行读写的情况。

跳表的内部实现全部是内联函数，且涉及到迭代器和Node结点的成员，数目比较多但是相对比较简单。

需要注意的是，在levelDB中，跳表没有删除key-value的接口。

SkipList插入一个键时，需要分配内存给一个节点，malloc是一个比较耗时的系统调用，尤其对于小内存分配来说，而且会产生很多内存碎片。

LevelDB里面的SkipList和一般的Skiplist使用有很大的不同，只会分配内存，而不需要回收小部分内存。SkipList的内存是等待MemTable写满后，转换为Immutable MemTable，写入SSTable，写入完成后，一起被销毁。也就是内存的回收是针对整个Skiplist的。

可能会觉得传递一个管理内存的类很奇怪，我们来具体看一下调用arena类的部分。

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
    const Key& key, int height) {
  char* const node_memory = arena_->AllocateAligned(
      sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
  return new (node_memory) Node(key);
}

我们可以看到，arena类内部是通过new来分配出一整块内存(4kb)，然后NewNode在进行内存申请时，调用arena类的分配对齐内存的接口，这其实是arena类在内部移动已经申请的内存块的指针，并不涉及到系统调用，所以会节省时间。SkipList类没有定义析构函数，所以在结束时会调用默认的析构函数，默认析构函数又会调用arena类的析构函数，而arena类的析构函数会释放arena类在生存期间申请的所有内存，这样就避免了内存泄漏的问题。

MemTable

MemTable其实就是对跳跃表的一层封装，并且其是一个智能指针的形式，采用了引用计数，将对键的查找和插入的请求，代理到相应的SkipList，调用相应的接口。

在实现中有一点值得注意，LevelDB存储的是Kv，而SkipList存储的是键，所以在MemTable里需要做一个转换。

对于插入操作，MemTable会把键和值编码在一个字符串里面，如下图所示，先是键，再是值，使用了字符串的长度前缀编码，然后将这个字符串插入到SkipList里。这里面涉及到了很多的key类型，我们先搁置在一边，大致了解一下就可以了，后面会具体阐述的。

而对于查找操作，只会按照前缀编码键，构造上面图的前半部分，而SkipList::Iterator::Seek的实现，会将迭代器定位到大于等于查找键的第一个键的位置，读出这个键，然后比对里面的键和查找的键是否相同，相同的话，才会读取对应的值，否则就是键不存在。

class MemTable
{

private:
    friend class MemTableIterator; // 友元类，正反迭代器
    friend class MemTableBackwardIterator;

    struct KeyComparator // key比较器，有好多的key，这部分后面具体说
    {
        const InternalKeyComparator comparator;
        explicit KeyComparator(const InternalKeyComparator &c) : comparator(c) {}
        int operator()(const char *a, const char *b) const;
    };

    typedef SkipList<const char *, KeyComparator> Table; // Table是跳表的typedef

    // 私有析构函数，因为只有Unref能调用它
    ~MemTable();

    KeyComparator comparator_; // key比较器
    int refs_;                 // 引用次数
    Arena arena_;              // 内存管理类
    Table table_;              // memtable

public:
    // MemTables会执行引用计数，初始计数为0，调用者必须主席那个Ref()函数至少一次
    explicit MemTable(const InternalKeyComparator &comparator);

    MemTable(const MemTable &) = delete;
    MemTable &operator=(const MemTable &) = delete;

    // 增加引用计数
    void Ref() { ++refs_; }

    // 当没有引用计数时释放内存，就是一个智能指针
    void Unref()
    {
        --refs_;
        assert(refs_ >= 0);
        if (refs_ <= 0)
        {
            delete this;
        }
    }

    // 返回大约占用了多少内存，因为是多线程的，所以只能估计
    size_t ApproximateMemoryUsage();

    // 返回一个迭代器
    Iterator *NewIterator();

    // Add an entry into memtable that maps key to value at the
    // specified sequence number and with the specified type.
    // Typically value will be empty if type==kTypeDeletion.
    // 添加一个key，type可以用来指示删除key，即把对应的value设置为空
    void Add(SequenceNumber seq, ValueType type, const Slice &key,
             const Slice &value);

    // If memtable contains a value for key, store it in *value and return true.
    // If memtable contains a deletion for key, store a NotFound() error
    // in *status and return true.
    // Else, return false.
    // 查找一个key，如果是被删除的key不会返回success
    bool Get(const LookupKey &key, std::string *value, Status *s);
};

在头文件中，我们可以观察到，如果需要删除一个key，其实就是插入一条k-v，并且标注是删除即可。另外，由于levelDB中不存在相同的key，所以需要保证key-value是唯一的。下面我们来看一下具体的实现。

// 解析levelDB 中Varint32 类型的数据，在levelDB中数据一般先存储数据大小，然后存储真实的数据。
// p ：Varint32数据的起始地址；
// limit : Varint32数据最多用5位，所以limit 为p+5;
// v ：数据的长度；
// return 返回真实数据的起始地址
static Slice GetLengthPrefixedSlice(const char *data)
{
    uint32_t len;
    const char *p = data;
    p = GetVarint32Ptr(p, p + 5, &len); // +5: we assume "p" is not corrupted
    return Slice(p, len);
}

// 构造函数
MemTable::MemTable(const InternalKeyComparator &comparator)
    : comparator_(comparator), refs_(0), table_(comparator_, &arena_) {}

// 析构函数
MemTable::~MemTable() { assert(refs_ == 0); }

// 返回大约占用了多少字节
size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }

// 比较keys
int MemTable::KeyComparator::operator()(const char *aptr,
                                        const char *bptr) const
{
    // Internal keys are encoded as length-prefixed strings.
    Slice a = GetLengthPrefixedSlice(aptr);
    Slice b = GetLengthPrefixedSlice(bptr);
    return comparator.Compare(a, b);
}

// 完成数据的编码，前缀码，长度在前，数据在后
static const char *EncodeKey(std::string *scratch, const Slice &target)
{
    scratch->clear();
    PutVarint32(scratch, target.size());
    scratch->append(target.data(), target.size());
    return scratch->data();
}

// 迭代器
class MemTableIterator : public Iterator
{
public:
    explicit MemTableIterator(MemTable::Table *table) : iter_(table) {}

    MemTableIterator(const MemTableIterator &) = delete;
    MemTableIterator &operator=(const MemTableIterator &) = delete;

    ~MemTableIterator() override = default;

    bool Valid() const override { return iter_.Valid(); }
    void Seek(const Slice &k) override { iter_.Seek(EncodeKey(&tmp_, k)); }
    void SeekToFirst() override { iter_.SeekToFirst(); }
    void SeekToLast() override { iter_.SeekToLast(); }
    void Next() override { iter_.Next(); }
    void Prev() override { iter_.Prev(); }
    Slice key() const override { return GetLengthPrefixedSlice(iter_.key()); }
    Slice value() const override
    {
        Slice key_slice = GetLengthPrefixedSlice(iter_.key());
        return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
    }

    Status status() const override { return Status::OK(); }

private:
    MemTable::Table::Iterator iter_;
    std::string tmp_; // For passing to EncodeKey
};

Iterator *MemTable::NewIterator() { return new MemTableIterator(&table_); }

// 添加一个key-value
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()]
    //  tag          : uint64((sequence << 8) | type)
    //  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);
    char *p = EncodeVarint32(buf, internal_key_size);
    std::memcpy(p, key.data(), key_size);
    p += key_size;
    EncodeFixed64(p, (s << 8) | type);
    p += 8;
    p = EncodeVarint32(p, val_size);
    std::memcpy(p, value.data(), val_size);
    assert(p + val_size == buf + encoded_len);
    table_.Insert(buf);
}

// 获取一个key
bool MemTable::Get(const LookupKey &key, std::string *value, Status *s)
{
    Slice memkey = key.memtable_key();
    Table::Iterator iter(&table_);
    iter.Seek(memkey.data());
    if (iter.Valid())
    {
        // entry format is:
        //    klength  varint32
        //    userkey  char[klength]
        //    tag      uint64
        //    vlength  varint32
        //    value    char[vlength]
        // Check that it belongs to same user key.  We do not check the
        // sequence number since the Seek() call above should have skipped
        // all entries with overly large sequence numbers.
        const char *entry = iter.key();
        uint32_t key_length;
        const char *key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
        if (comparator_.comparator.user_comparator()->Compare(
                Slice(key_ptr, key_length - 8), key.user_key()) == 0)
        {
            // Correct user key
            const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
            switch (static_cast<ValueType>(tag & 0xff))
            {
            case kTypeValue:
            {
                Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
                value->assign(v.data(), v.size());
                return true;
            }
            case kTypeDeletion:
                *s = Status::NotFound(Slice());
                return true;
            }
        }
    }
    return false;
}

而对于查找操作，只会按照前缀编码键，构造上面图的前半部分，而SkipList::Iterator::Seek的实现，会将迭代器定位到大于等于查找键的第一个键的位置，读出这个键，然后比对里面的键和查找的键是否相同，相同的话，才会读取对应的值，否则就是键不存在。

总体而言，MemTable结构还是比较简单的。

总结

编程技巧

• 使用引用计数的类的析构函数可以作为私有成员来使用。