redis 源码探索:ziplist结构分析与使用

在我们日常开发中,经常有使用到 Redis 来作缓存.主要是由于 Redis 有着多种数据结构,而非单一的 Key-Value 存储,由于存储在内存中,读取速度自然是比存放在硬盘中要快很多.

那么为了节约内存的使用 Redis 在配置中有提供一个 ziplist 的配置项, 本次就让我们来探究一下

关于 ZipList

上面提到了 ziplist 是用来对redis数据结构来做内存优化的一种短结构, 它是对 list,hash, zset这些长结构的一种结构压缩.

关于以上三种结构的本质:

列表本质是一个双链表结构
散列是哈希表的结构
有序列表是哈希表加跳表实现的

本次我们拿列表结构举例子

链表这种结构,以前的文章PHP 实现单向链表中有提到过.单链表有个缺点,那就是只能从头遍历到位,不能从未遍历到头.那么双链表结构就是在单链表基础上增加了一个prev节点,让它可以从两种方向都能遍历.所以我们在使用 redis 的列表结构时,都有lpush,rpush,lpop,rpop等命令能操作链表左右两端.

下面是源码中对 list 结构的定义,其中主要的是listNode与list

// ../src/adlist.h
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

listNode 结构里是三个指针,也就是说如果是64位编译器编译, 不算value本身占用大小,该结构需要24个字节长度.而结构中 value 本身也需要两个整数(字符串长度,字符串剩余可用空间)来标识值的偏移量,以便读取.

那么 ziplist 的结构如下:

<zlbytes> <zltail> <zllen> <entry> <entry> … <entry> <zlend>
该结构是直接一字节形式存储在内存中,其中

zlbytes: 长度为 32 位,用来表示整个 ziplist 长度

zltail: 长度为 32 位,用来表示最后一个 entry 所在偏移量.一般用于反向遍历时使用

zllen: 长度为 8 位,用于表示 entry 数量

entry: 为节点

zlend: 是整个结构的结束符标示, 值为 0xFF

而 entry 节点本身也有结构标示,共有三部分:

<prevlength> <encoding> <data>

prevlength:长度为 8 位,用来表示上个节点长度,反向遍历时使用
encoding:长度为 8 位,用于标示 data 数据类型
data:长度不限,为值本身

当然前节点长度也有过大的时候,prevlength 在长度超过 254时(255为0xFF,容易与结束符混淆),程序会向后偏移32位长度,这32位长度用于标识真正的字节长度.

我们知道 8 位为1字节,所以使用ziplist会相对更省内存一点儿.

ziplist的使用

在 redis的 config 文件中,有一下相关配置

#hash 结构的ziplist
hash-max-ziplist-entries 512 
hash-max-ziplist-value 64
#zset 结构的ziplist
zset-max-ziplist-entries 512
zset-max-ziplist-value 64

list-max-ziplist-size -2

其中已entries结尾的表示节点数量,以value结尾的标识值最多占用字节大小

凡是长度数量位超过该配置的键,都会转为ziplist结构存储,否则程序会自动转换回原有结构.

ziplist的缺点

有优点,那自然也会有缺点. 在上面我们对ziplist结构做了解析可以看出, ziplist在读取时可以非常快,但它本事数据存储是连续且相关的,在修改起来就非常困难,特别是在节点量过多的时候,性能更会降低.

所以在实际开发中控制好对 entry 和 value 长度的限制也是非常必要的.