正常情况下我们选择使用 Redis
就是为了提升查询速度,然而让人意外的是,Redis
当中却有一种比较有意思的数据结构,这种数据结构通过牺牲部分读写速度来达到节省内存的目的,这就是 ziplist
(压缩列表),Redis
为什么要这么做呢?难道真的是觉得自己的速度太快了,牺牲一点速度也不影响吗?
什么是压缩列表
ziplist
是为了节省内存而设计出来的一种数据结构。ziplist
是由一系列特殊编码组成的连续内存块的顺序型数据结构,一个 ziplist
可以包含任意多个 entry
,而每一个 entry
又可以保存一个字节数组或者一个整数值。
ziplist
作为一种列表,其和普通的双端列表,如 linkedlist
的最大区别就是 ziplist
并不存储前后节点的指针,而 linkedlist
一般每个节点都会维护一个指向前置节点和一个指向后置节点的指针。那么 ziplist
不维护前后节点的指针,它又是如何寻找前后节点的呢?
ziplist
虽然不维护前后节点的指针,但是它却维护了上一个节点的长度和当前节点的长度,然后每次通过长度来计算出前后节点的位置。既然涉及到了计算,那么相对于直接存储指针的方式肯定有性能上的损耗,这就是一种典型的用时间来换取空间的做法。因为每次读取前后节点都需要经过计算才能得到前后节点的位置,所以会消耗更多的时间,而在 Redis
中,一个指针是占了 8
个字节,但是大部分情况下,如果直接存储长度是达不到 8
个字节的,所以采用存储长度的设计方式在大部分场景下是可以节省内存空间的。
ziplist 的存储结构
ziplist
的组成结构为:
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
其中 zlbytes
,zltail
,zllen
为 ziplist
的 head
部分,entry
为 ziplist
的 entries
部分,每一个 entry
代表一个数据,最后 zlend
表示 ziplist
的 end
部分,如下图所示:
ziplist
中每个属性代表的含义如下表格所示:
属性
类型
长 度
说明
zlbytes
uint32_t
4字节
记录压缩列表占用内存字节数(包括本身所占用的 4
个字节)。
zltail
uint32_t
4字节
记录压缩列表尾节点距离压缩列表的起始地址有多少个字节(通过这个值可以计算出尾节点的地址)
zllen
uint16_t
2字节
记录压缩列表中包含的节点数量,当列表值超过可以存储的最大值(65535
)时,此值固定存储 65535
(即 2
的 16
次方 减 1
),因此此时需要遍历整个压缩列表才能计算出真实节点数。
entry
节点
-
压缩列表中的各个节点,长度由存储的实际数据决定。
zlend
uint8_t
1字节
特殊字符 0xFF
(即十进制 255
),用来标记压缩列表的末端(其他正常的节点没有被标记为 255
的,因为 255
用来标识末尾,后面可以看到,正常节点都是标记为 254
)。
entry 存储结构
ziplist
的 head
和 end
存的都是长度和标记,而 entry
存储的是具体元素,这又是经过特殊的设计的一种存储格式,每个 entry
都以包含两段信息的元数据作为前缀,每一个 entry
的组成结构为:
<prevlen> <encoding> <entry-data>
prevlen
prevlen
属性存储了前一个 entry
的长度,通过此属性能够从后到前遍历列表。 prevlen
属性的长度可能是 1
字节也可能是 5
字节:
当链表的前一个 entry
占用字节数小于 254
,此时 prevlen
只用 1
个字节进行表示。
<prevlen from 0 to 253> <encoding> <entry>
当链表的前一个 entry
占用字节数大于等于 254
,此时 prevlen
用 5
个字节来表示,其中第 1
个字节的值固定是 254
(相当于是一个标记,代表后面跟了一个更大的值),后面 4
个字节才是真正存储前一个 entry
的占用字节数。
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>