Redis源码阅读(七) 压缩字典

发表于 | 分类于

1. 定义

zipmap是为了优化string==>string的映射而实现的特殊编码结构，它由7部分组成，zmlen,klen,key,vlen,free,val,end，但实际上讲只有4部分，zmlen,len(klen,vlen,end),data(key,val),free。

属性 描述
zmlen 1字节大小，存储了压缩字典中kv对的个数，当超过254时，需要遍历才能获取结点数
klen key的长度，0~253时使用1字节，254表示由后4字节表示长度
key 字典的key值
vlen val的长度，0~253时使用1字节，254表示由后4字节表示长度
free 1字节大小，value数据缩小后，产生的内存空间剩余
val 结点的val值
end 结束标志，实际上是len属性，当len=255时表示压缩字典结束

zipmap并没有像ziplist连锁更新之类的特殊操作，只是对内存进行一些移动，扩展，收缩等待。

2. 源码剖析

  • 查找结点
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
/**
 * 根据key查询zipmap中的kv结点
 */
static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
    unsigned char *p = zm+1, *k = NULL;
    unsigned int l,llen;

    // 遍历zipmap中的结点
    while(*p != ZIPMAP_END) {
        unsigned char free;

        /* Match or skip the key */
        // 当前结点的长度
        l = zipmapDecodeLength(p);

        // 计算存储该长度需要的字节数
        llen = zipmapEncodeLength(NULL,l);

        if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {
            /* Only return when the user doesn't care
             * for the total length of the zipmap. */
            // 我们不需要关系zipmap的长度时直接返回
            if (totlen != NULL) {
                k = p;
            } else {
                return p;
            }
        }

        // 获取value的地址
        p += llen+l;

        /* Skip the value as well */

        // 获取value的长度
        l = zipmapDecodeLength(p);

        // 跳过value，指向下一个地址
        p += zipmapEncodeLength(NULL,l);

        // 获取value后剩余未使用空间大小
        free = p[0];

        // +l表示跳过value结点长度
        // +1表示跳过存储free长度
        // +free表示跳过value剩余空间
        p += l+1+free; /* +1 to skip the free byte */
    }
    // 记录总长度
    if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
    return k;
}
  • 添加结点
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * 在压缩字典中添加kv对
 * 若update不为NULL，那么key存在在update=1，否则为0
 */
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;

    // 存储kv对总共需要多少字节
    freelen = reqlen;
    if (update) *update = 0;

    // 查找key是否存在，并存储总字节数
    p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p == NULL) {
        /* Key not found: enlarge */

        // 不存在扩展内存空间
        zm = zipmapResize(zm, zmlen+reqlen);

        // 压缩列表末尾处
        p = zm+zmlen-1;

        // 扩展后的总字节数
        zmlen = zmlen+reqlen;

        /* Increase zipmap length (this is an insert) */
        // <zmlen> 存储kv个数，kv个数+1
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
        /* Key found. Is there enough space for the new value? */
        /* Compute the total length: */

        // 找到该key，则判断是否有空间存储下value
        if (update) *update = 1;

        // 计算结点总字节数
        freelen = zipmapRawEntryLength(p);
        if (freelen < reqlen) {
            /* Store the offset of this key within the current zipmap, so
             * it can be resized. Then, move the tail backwards so this
             * pair fits at the current position. */

            // 存储不下，则需要扩展内存
            offset = p-zm;
            zm = zipmapResize(zm, zmlen-freelen+reqlen);
            p = zm+offset;

            /* The +1 in the number of bytes to be moved is caused by the
             * end-of-zipmap byte. Note: the *original* zmlen is used. */
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
            zmlen = zmlen-freelen+reqlen;
            freelen = reqlen;
        }
    }

    /* We now have a suitable block where the key/value entry can
     * be written. If there is too much free space, move the tail
     * of the zipmap a few bytes to the front and shrink the zipmap,
     * as we want zipmaps to be very space efficient. */
    
    // 此时已经有足够的空间存储
    // 计算剩余空间,若大于最大free，则缩小其内存
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {
        /* First, move the tail <empty> bytes to the front, then resize
         * the zipmap to be <empty> bytes smaller. */
        offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
        zmlen -= empty;
        zm = zipmapResize(zm, zmlen);
        p = zm+offset;
        vempty = 0;
    } else {
        vempty = empty;
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    // 添加kv数据到压缩字典中中
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    /* Value: */
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
}
  • 删除结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
    unsigned int zmlen, freelen;

    // 查找key结点
    unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p) {
        // 计算该key+value的内存大小
        freelen = zipmapRawEntryLength(p);
        // 删除kv数据
        memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
        zm = zipmapResize(zm, zmlen-freelen);

        /* Decrease zipmap length */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;

        if (deleted) *deleted = 1;
    } else {
        if (deleted) *deleted = 0;
    }
    return zm;
}