当前位置: 首页 > redis, 分布式系统, 缓存系统 > 正文

解读Redis中ziplist、zipmap、intset实现细节

关键字:
1 星2 星3 星4 星5 星 (1 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

ziplist
简介:

ziplist是一个直接在字节级别操作的双向列表实现,主要是为了节省空间的使用,比如减少了指针,使用浮动的长度大小。增加和删除元素都是O(1)。但同时最大的问题是每次增加元素,删除元素都需要重新重新分配内存,因此实际上,实际时间复杂度是与列表大小相关。
主要应用在小列表上和排序列表上。redis在存储上会具有非常多的小列表或小集合,小字典,所以在实现上用了非常节省内存的zip_方式

基本:

这里可以借用一篇文章Redis ziplist内部结构分析(http://blog.nosqlfan.com/html/3919.html),这篇文章已经比较详细的介绍整个ziplist的结构和实现细节,接口。

存取整数的方式

ziplist是直接在字节上存读整数,而且不同大小范围的整数采取不同长度存储的方式来极大减小了小数的空间使用。

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
static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
    int16_t i16;
    int32_t i32;
    int64_t i64;
    if (encoding == ZIP_INT_8B) {
        ((int8_t*)p)[0] = (int8_t)value;
    } else if (encoding == ZIP_INT_16B) {
        i16 = value;
        memcpy(p,&i16,sizeof(i16));
        memrev16ifbe(p);
    } else if (encoding == ZIP_INT_24B) {
        i32 = value<<8;
        memrev32ifbe(&i32);
        memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t));
    } else if (encoding == ZIP_INT_32B) {
        i32 = value;
        memcpy(p,&i32,sizeof(i32));
        memrev32ifbe(p);
    } else if (encoding == ZIP_INT_64B) {
        i64 = value;
        memcpy(p,&i64,sizeof(i64));
        memrev64ifbe(p);
    } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
        /* Nothing to do, the value is stored in the encoding itself. */
    } else {
        assert(NULL);
    }
}
 
static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
    int16_t i16;
    int32_t i32;
    int64_t i64, ret = 0;
    if (encoding == ZIP_INT_8B) {
        ret = ((int8_t*)p)[0];
    } else if (encoding == ZIP_INT_16B) {
        memcpy(&i16,p,sizeof(i16));
        memrev16ifbe(&i16);
        ret = i16;
    } else if (encoding == ZIP_INT_32B) {
        memcpy(&i32,p,sizeof(i32));
        memrev32ifbe(&i32);
        ret = i32;
    } else if (encoding == ZIP_INT_24B) {
        i32 = 0;
        memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t));
        memrev32ifbe(&i32);
        ret = i32>>8;
    } else if (encoding == ZIP_INT_64B) {
        memcpy(&i64,p,sizeof(i64));
        memrev64ifbe(&i64);
        ret = i64;
    } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
        ret = (encoding & ZIP_INT_IMM_MASK)-1;
    } else {
        assert(NULL);
    }
    return ret;
}

这个函数就是在不同大小级别上存储不同字节长度的整数,有8bits, 16bits, 24bits, 32bits, 64bits。在24bits中,因为没有C类型相应的支持。在这里值得注意的是一个细节,在存取上都进行了右移位操作,这是因为考虑到C是以补码的形式存储,如果不移位的话,会导致符号位的丢失,为了理解这一过程,可以用下面这个小程序来解释:

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
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
 
void print0x(unsigned char *v, int size)
{
    int i;
    unsigned char *t = v + size - 1;
    for (i = 0; i < size; i++, t--) {
        printf("%.2X", *t);
    }
}
 
int main()
{
    char store[3];
    int i = 0xFFF0F1F2;
    memcpy(store, &i, 3);
    int load;
    memcpy(&load, store, 3);
    printf("用3bytes存储整数-986638\n");
    printf("直接使用2次memcpy,此时不相等:%d,%d\n字节为:", i, load);
    print0x((unsigned char *)&load, 4);
    printf("\n左移:");
    load <<= 8;
    print0x((unsigned char *)&load, 4);
    printf("\n右移:");
    load >>= 8;
    print0x((unsigned char *)&load, 4);
    printf("\n相等");
    printf("%d,%d\n", i, load);
    return 0;
}

在github上的一个issue也很好解释了作者对24bits操作的解释:

https://github.com/antirez/redis/issues/469

级联更新操作

在ziplist实现上,一个非常重要的过程就是在增加或删除entry时,因为每个entry都保存了前一个entry的长度,所以在增删时都需要修改这个长度,但是又因为这个长度是浮动的,可以是1个字节或5个字节。因此,在增删时,需要修改后续entry的前置长度,并且又因为前置长度的改变而导致整个entry长度的改变,同时级联导致再下一个entry前置长度的改变。这个过程由下面这个函数实现:

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
static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;
 
    while (p[0] != ZIP_END) {
        cur = zipEntry(p);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipPrevEncodeLength(NULL,rawlen);
 
        /* Abort if there is no next entry. */
        if (p[rawlen] == ZIP_END) break;
        next = zipEntry(p+rawlen);
 
        /* Abort when "prevlen" has not changed. */
        if (next.prevrawlen == rawlen) break;
 
        if (next.prevrawlensize < rawlensize) {
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            offset = p-zl;
            extra = rawlensize-next.prevrawlensize;
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;
 
            /* Current pointer and offset for next element. */
            np = p+rawlen;
            noffset = np-zl;
 
            /* Update tail offset when next element is not the tail element. */
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }
 
            /* Move the tail to the back. */
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            zipPrevEncodeLength(np,rawlen);
 
            /* Advance the cursor */
            p += rawlen;
            curlen += extra;
        } else {
            if (next.prevrawlensize > rawlensize) {
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
            } else {
                zipPrevEncodeLength(p+rawlen,rawlen);
            }
 
            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

值得注意的是,当需要的长度的太多时,为了避免缩减,在实现上强制使用了较大的长度来存储。
其实因为ziplist主要用于小列表,因此大部分entry的长度都是小于254的,因此大部分前置长度都可以用1个字节来存储,这也是跟普通list用4个字节指针指向前一个entry在实现在空间上比较省的部分。

Issue

在__ziplistDelete()函数上,这是一个内部函数,是删除API的实现,在line 518行我发现
tail = zipEntry(p);
而根据上面的应该是
tail = zipEntry(p-nextdiff);
在发现问题后,我google了一下,发现正好在前几天已经有人发现了这个问题,并提交了Patch,在issue页,有人也很好的解释了为啥这个漏洞没有被测试覆盖到并且检测出的原因。

https://github.com/antirez/redis/issues/627

通过这个Issue可以得出,在字节上直接操作是很复杂的编程,即使在实现ziplist这么久后,还有这么明显的漏洞,而且在几百行实现ziplist的代码上,在字节操作起来让本来逻辑清楚的过程变得异常复杂。

intset

intset是redis的集合(set)类型的一个encoding方式之一,如果set类型只有整数,并且元素较少的话,redis会采用intset作为该类型的实现。

intset的特点跟ziplist差不多,压缩空间,在字节上操作,并且在结构上是有序的。从数据结构中,我们可以看出,contents就是存储数的位置,而encoding决定了用几个字节存储整数。如果set中整数大小都小于short的最大值,那么set就会采用2个字节存储。

数据结构

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

数据接口

1
2
3
4
5
6
7
8
intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(intset *is);
size_t intsetBlobLen(intset *is);

实现

在intset实现上,我们从intsetAdd()和intsetRemove()深入就可以了解intset的整个机制。

首先,调用_intsetValueEncoding()估计value的大小,决定value的编码(2,4,8个字节),如果intset的编码长度小于这个value,intsetUpgradeAndAdd()会升级整个intset的编码,并且重新分配每个数占用空间。然后调用intsetSearch(),intsetSearch()使用二分搜索检索整个intset,如果value不存在,返回参数的pos值会指向可以存储该value的位置。重新调整整个intset的大小,移动pos位置以后的地址到pos+1位置,让pos位置的空间存储value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } else {
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

跟add操作非常类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
 
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);
 
        /* We know we can delete */
        if (success) *success = 1;
 
        /* Overwrite value with tail and update length */
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

从add和remove的实现上,我们可以看出,intset的插入、删除操作如果成功,都需要二分搜索整个intset,然后重新resize整个intset,移动部分int。无疑,intset是适用于少量元素的集合类型实现,在大量元素的集合中,插入和删除操作的时间复杂度是不可接受的。

zipmap
淘宝核心系统团队博客的《Redis zipmap内存布局分析》对zipmap内存进行了详细的图解分析。

zipmap的首部长度zmlen过短导致的性能问题

zipmap由于在首部的zmlen只使用一个字节,而如果超出一个字节的长度,zipmap必须搜索整个zipmap来确定长度,这产生了很大的性能问题。在github的issue中(https://github.com/antirez/redis/issues/188),有人提出了这个问题,Redis的作者也同意了观点,但是如果改变zipmap的实现,会导致Redis之前版本的rdb文件无法读取,所以为了避免兼容性,Redis 2.6会使用ziplist代替zipmap,并且在(https://github.com/antirez/redis/pull/285)请求中,也证明了ziplist实现hash比zipmap相差无几。因此,Redis 2.6到Redis 3都不会有zipmap的调用,而Redis 3作者是否会增加zmlen到2个字节并且让small hash换回使用zipmap仍然是个疑问。

本文固定链接: http://www.chepoo.com/redis-ziplist-zipmap-intset-analysis.html | IT技术精华网

解读Redis中ziplist、zipmap、intset实现细节:等您坐沙发呢!

发表评论