Staskaer

Hi, this is Staskaer

0%

levelDB源码剖析(11)--内部的key结构

Posted on Edited on In Valine:

内部的key结构

源码位置与说明

db/dbformat.h db/dbformat.cc: 定义了Internal Key、Lookup Key、InternalKeyComparator和InternalFilterPolicy

在levelDB中，存在着多种类型的key，而由于levelDB本身又是kv型的数据库，所以弄清楚这些key的结构与作用都是十分重要的。

其中，在levelDB中主要有以下三种类型的key，分别是User Key、Internal Key和Lookup Key，我们后面就针对这三种类型的key进行阐述。

User Key

User Key顾名思义，其实就是用户插入的key-value中的key，是原始的key的形式，这种是最简单的情况，也就是读写键值对时提供的键，只是一个简单的字符串，一般用Slice来表示。

程序与levelDB交互式，使用的key就是Usr Key。

Internal Key

第二种类型的key是Internal Key，这是SSTable中实际存储的key，也就是这个持久化有序的Map的键。但同时Internal Key是一个复合概念，是有几个部分组合成的一个key，ParsedInternal Key就是对Internal Key分拆后的结果，先来看看ParsedInternal Key的定义，这是一个结构体struct：

1
2
3
4
5
6
7
8
9
10
11
12
13

struct ParsedInternalKey
{
    Slice user_key;
    SequenceNumber sequence;
    ValueType type;

    ParsedInternalKey() {} // Intentionally left uninitialized (for speed)
    ParsedInternalKey(const Slice &u, const SequenceNumber &seq, ValueType t)
        : user_key(u), sequence(seq), type(t) {}
    std::string DebugString() const;
};

这个结构体说明ParsedInternalKey由三部分组成：user_key、序列号以及类型组成。而实际上ParsedInternalKey本身就可以看成是Internal key。

然后我们看一个比较重要的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 把ParsedInternalKey编码成字符串
void AppendInternalKey(std::string *result, const ParsedInternalKey &key)
{
    // 先把user key放进去
    result->append(key.user_key.data(), key.user_key.size());
    // 再把序列号和类型编码后放入
    PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
}

// 编码序列号和类型
static uint64_t PackSequenceAndType(uint64_t seq, ValueType t)
{
    assert(seq <= kMaxSequenceNumber);
    assert(t <= kValueTypeForSeek);
    return (seq << 8) | t;
}

这两个函数是将ParsedInternalKey编码成字符串，也就是把一个结构体编码成字符串，这样就成为了真正的Internal key。我们接来下看一下Internal key。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class InternalKey
{
private:
    std::string rep_;

public:
    // 默认构造函数，让rep_为空就说明其为非法的
    InternalKey() {}
    // 构造一个Internal Key，由userkey，序列号和类型组成
    // 先把后面的部分存储到结构体中，然后调用AppendInternalKey
    // 将ParsedInternalKey封装进rep_中
    InternalKey(const Slice &user_key, SequenceNumber s, ValueType t)
    {
        AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
    }

    // 解码字符串
    bool DecodeFrom(const Slice &s)
    {
        rep_.assign(s.data(), s.size());
        return !rep_.empty();
    }

    // 返回编码信息
    Slice Encode() const
    {
        assert(!rep_.empty());
        return rep_;
    }

    // 返回出user key
    Slice user_key() const { return ExtractUserKey(rep_); }

    // 使用p来更新rep_
    void SetFrom(const ParsedInternalKey &p)
    {
        rep_.clear();
        AppendInternalKey(&rep_, p);
    }

    // 清理
    void Clear() { rep_.clear(); }

    std::string DebugString() const;
};


InternalKey类中的私有对象就是存放编码后的Internal key，通过上面那两个函数，我们已经知道ParsedInternalKey是怎么转换成Internal key的，所以此处就给出Internal key的编码格式：

1
2
3

| User key (string) | sequence number (7 bytes) | value type (1 byte) |

可以看到Internal Key在User Key的后面增加了一个64位的整数，并且将这个整数分为两部分，低位的一个字节是一个ValueType，高位的7个字节是一个SequenceNumber。

ValueType是为了区分一个键是插入还是删除，删除其实也是一条数据的插入，但是是一条特殊的插入，通过在User Key后面附上kTypeDeletion来说明要删除这个键，而kTypeValue说明是插入这个键。

SequenceNumber是一个版本号，是全局的，每次有一个键写入时，都会加一，每一个Internal Key里面都包含了不同的SequenceNumber。SequenceNumber是单调递增的，SequenceNumber越大，表示这键越新，如果User Key相同，就会覆盖旧的键。所以就算User Key相同，对应的Internal Key也是不同的，Internal Key是全局唯一的。当我们更新一个User Key多次时，数据库里面可能保存了多个User Key，但是它们所在的Internal Key是不同的，并且SequenceNumber可以决定写入的顺序。

当用户写入时，将User Key封装成Internal Key，保留版本信息，存储到SSTable里，当需要读取时，将User Key从Internal Key里提取出来，所有User Key相同的Internal Key里面SequenceNumber最大的Internal Key就是当前的键，它对应的值就是当前值。

另外Internal Key的比较方式和User Key是不一样的，Options提供的是User Key的比较方式，而LevelDB内部会生成一个根据这个User Key的比较方式得到的Internal Key的比较方式。

当Internal Key里面包含的User Key不同时，直接用User Key的比较方式即可。否则，根据SequenceNumber比较，按SequenceNumber倒序排序。这样的好处就是，在全局有序的Map里，根据User Key排序，User Key相同的会排在一起，SequenceNumber大的Internal Key排在前面。当Seek一个User Key时，会定位到第一个符合条件的Internal Key，也就是具有最大的SequenceNumber的Internal Key。

除了比较器，布隆过滤器也会被改造，以适应User Key到Internal Key的转换。

我们再来分析以下Internal key向user key和ParsedInternalKey转换的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 解码出user key，其实就是去掉末尾的8字节
inline Slice ExtractUserKey(const Slice &internal_key)
{
    assert(internal_key.size() >= 8);
    return Slice(internal_key.data(), internal_key.size() - 8);
}

// 把InternalKey转换成ParsedInternalKey
inline bool ParseInternalKey(const Slice &internal_key,
                             ParsedInternalKey *result)
{
    const size_t n = internal_key.size();
    if (n < 8)
        return false;
    uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
    uint8_t c = num & 0xff;
    result->sequence = num >> 8;
    result->type = static_cast<ValueType>(c);
    result->user_key = Slice(internal_key.data(), n - 8);
    return (c <= static_cast<uint8_t>(kTypeValue));
}

这部分其实也是很简单的，就是对应关系而已。

Lookup Key

Lookup Key其实就是简单的在Internal Key前面加上键的长度，使用varint32编码，主要用在MemTable的查找上。

由于MemTable的底层是一个Skiplist，而LevelDB的Skiplist只存储了一个键，而没有值。LevelDB在存储Kv时，又是将键和值编码在一起存储的，使用的就是字符串的长度前缀编码。所以在MemTable里查找Key时，提供的Lookup Key就是编码值的一个前缀，刚好可以定位MemTable里相应的键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class LookupKey
{
private:
    // We construct a char array of the form:
    //    klength  varint32               <-- start_
    //    userkey  char[klength]          <-- kstart_
    //    tag      uint64
    //                                    <-- end_
    // The array is a suitable MemTable key.
    // The suffix starting with "userkey" can be used as an InternalKey.
    const char *start_;  // 指向开头
    const char *kstart_; // 指向internal_key
    const char *end_;    //指向结尾
    char space_[200];    // Avoid allocation for short keys

public:
    // 构造函数析构函数
    LookupKey(const Slice &user_key, SequenceNumber sequence);
    LookupKey(const LookupKey &) = delete;
    LookupKey &operator=(const LookupKey &) = delete;
    ~LookupKey();

    // 返回memtable_key，其实就是全部
    Slice memtable_key() const { return Slice(start_, end_ - start_); }

    // 返回internal_key，从internal_key开始到计数
    Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

    // 返回user_key，就是internal_key的前面
    Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
};

// 构造函数，使用userkey和序列号来构造looupkey
LookupKey::LookupKey(const Slice &user_key, SequenceNumber s)
{
    size_t usize = user_key.size();
    size_t needed = usize + 13; // 7(序列号) + 1(类型) + 5(最长5字节可变整数编码)
    char *dst;
    if (needed <= sizeof(space_))
    {
        dst = space_;
    }
    else
    {
        dst = new char[needed];
    }
    start_ = dst;
    dst = EncodeVarint32(dst, usize + 8);
    kstart_ = dst;
    std::memcpy(dst, user_key.data(), usize);
    dst += usize;
    EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
    dst += 8;
    end_ = dst;
}

我们可以看到LookupKey类中的接口可以返回memtable_key、internal_key和user_key。为了理解这一点，我们先来看一下LookupKey的构造。

其内部成员作为指针分别指向了memtable_key开头、internal_key开头和结束位置。通过这几个特殊位置的指针就可以解析出所有的三种类型key。

从memtable_key()可知MemtableKey就是LookupKey，即：memtableKey == lookupKey，而不是internalKey，是klength+internalKey。

有一个部分感觉需要重点说一下，就是虽然跳表说是不存储值，只存储键(key)，但是MemTable的Add方法会把需要保存的key-value编码成长度前缀码，即相当于将key-value编码成一个'key'放入跳表中存储。

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

几种key的联系与区别

首先，用户直接插入的key就是user key，这个key没有经过任何的变化和编码。

然后在levelDB中，会将user key的后面添加上序列号和类型，编程Internal key，这个key是用于SSTable的存储的。序列号是一个单调递增的数字，类型分为插入类型和删除类型。因为levelDB中不存在删除数据的说法，想要实现删除就需要插入一条类型为删除的数据。由于越大的序列号数据越新，所以读取时会返回序列号最大的数据。

在Internal key前面插入Internal key的长度，就形成了lookup key。这个lookup key用于MemTable，因为MemTable内部是跳表，只存储键(注意这句话该如何理解，按照上面的说法，其实是键和值都被编码成键了)。构造出lookupkey后就可以用于查找，迭代器会被定位到大于等于lookupkey的第一个键的位置，读出这个键，然后比对里面的键和查找的键是否相同，相同的话，才会读取对应的值，否则就是键不存在。

总结

以上就是LevelDB的三种键，是包含的关系：

  • User Key是用户提供的键，是我们看到的键
  • Internal Key是实际存储的键，支持版本号和Tag的功能
  • Lookup Key则是为了查找MemTable而构造的键