Redis之压缩列表

2021-08-22  本文已影响0人  slxixiha

压缩列表的应用场景

压缩列表(ziplist)是hash键的底层实现之一。

当一个hash键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会用压缩列表来做hash键的底层实现。

压缩列表的定义

压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序性数据结构。

单个节点的定义如下:

属性 previous_entry_length encoding content
大小 1或者5字节 1字节、2字节或5字节 不定

previous_entry_length:记录了前一个entry的长度。大小可以是1个字节或者5个字节。1个字节就不用说了,5个字节时,第一个字节会被赋值成0xFE,后面4个字节才是真实的大小。

encoding:记录了节点的content属性所保存数据的类型及长度。

编码 编码长度 content属性保存的值
00bbbbbb 1字节 长度小于等于63字节的字节数组(2^6)
01bbbbbb xxxxxxxx 2字节 长度小于等于16383字节的字节数组(2^14)
10xxxxxxx aaaaaaaa bbbbbbbb cccccccc dddddddd 5字节 长度小于等于4294967295字节的字节数组(2^32),最前面6位不用
编码 编码长度 content属性保存的值
11000000 1字节 int16_t类型的整数
11010000 1字节 int32_t类型的整数
11100000 1字节 int64_t类型的整数
11110000 1字节 24位有符号整数
11111110 1字节 8位有符号整数
1111xxxx 1字节 不存在content,需要保存的值(0-12)已经存放在encoding的后四位xxxx中

content:节点保存的内容,既可以是字符数组,也可以是整数值。

添加节点时,统一传入的都是unsigned char类型的字节数组,添加过程中会根据能否转化为数字进行判断具体的数值类型

/* Check if string pointed to by 'entry' can be encoded as an integer.
 * Stores the integer value in 'v' and its encoding in 'encoding'. */
int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
    long long value;

    if (entrylen >= 32 || entrylen == 0) return 0;
    // string转换成long long
    if (string2ll((char*)entry,entrylen,&value)) {
        /* Great, the string can be encoded. Check what's the smallest
         * of our encoding types that can hold this value. */
        if (value >= 0 && value <= 12) {
            *encoding = ZIP_INT_IMM_MIN+value;
        } else if (value >= INT8_MIN && value <= INT8_MAX) {
            *encoding = ZIP_INT_8B;
        } else if (value >= INT16_MIN && value <= INT16_MAX) {
            *encoding = ZIP_INT_16B;
        } else if (value >= INT24_MIN && value <= INT24_MAX) {
            *encoding = ZIP_INT_24B;
        } else if (value >= INT32_MIN && value <= INT32_MAX) {
            *encoding = ZIP_INT_32B;
        } else {
            *encoding = ZIP_INT_64B;
        }
        *v = value;
        return 1;
    }
    return 0;
}

压缩列表构成如下:

属性 zlbytes zltail zllen entry0 ... entryX zlend
类型 uint32_t uint32_t uint16_t ziplistEntry ziplistEntry ziplistEntry uint8_t
长度 4字节 4字节 2字节 1字节
说明 整个压缩列表的大小 压缩列表尾节点距离列表起始地址的偏移量 节点数量,当这个值等于UINT16_MAX时需要遍历统计 压缩列表的节点 压缩列表的节点 压缩列表的节点 特殊值0xFF,用于标记压缩列表的末端

压缩列表的结构图

压缩列表.PNG

连锁更新

如果在头部或者中间插入节点的话,由于新插入的节点与之前节点的大小不一样,会导致后续节点保存的前一节点的大小发生变化,从而需要连锁更新后续节点的内容。不过一般只要不是正好在254字节左右,都不会引发大量的连锁更新。

上一篇下一篇

猜你喜欢

热点阅读