Redis-压缩列表内部结构

redis数据结构与内部编码.png
之前介绍了 Redis-String内部结构，这里介绍在数据结构中使用频繁的ziplist。

zipList结构

压缩列表是一块连续的内存空间，元素之间是连续存储的，没有任何冗余空隙。如上图在hash、list、zset容器对象中，在元素个数较少的时候，会使用ziplist进行存储。
ziplist结构大概如下:

struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个
节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储 int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

ziplist内存结构图.jpg

zip entry结构

了解了ziplist，再来了解下列表中元素结构，大概如下：

struct entry {
  int<var> prevlen; // 前一个 entry 的字节长度 
  int<var> encoding; // 元素类型编码
  optional byte[] content; // 元素内容
}

prevlen

这里prevlen记录上一个entry的字节长度是为了list倒着遍历时，通过这个长度快速定位到上一个元素位置。
prevlen是一个可变长度的整数：

1. 长度小于254(0xFE)时，使用一个字节表示

2. 长度达到254(0xFE)及以上时，使用五个字节表示

   
   ZipEntity中prelen内存模型.jpg

encoding

encoding字段存储了元素内容的编码类型信息，ziplist通过这个字段来决定后面的content内容的形式。
redis为了节约存储空间，对encoding字段进行了相当复杂的设计。redis通过这个字段的前缀位来识别具体存储的数据形式。具体规则有很多，这里列举其中几种：

前缀	内容
00xxxxxx	最大63的短字符串，后面6个位存储字符串的位数
01xxxxxx xxxxxxxx	中等长度的字符串，后面14位表示字符串长度
11000000	表示int16，后跟两个字节表示整数
11010000	表示int32，后面四个字节表示整数
11100000	表示int64，后面八个字节表示整数
11110000	表示int24，后面四个字节表示整数
11111110	表示int8，后面四个字节表示整数
11111111	表示ziplist结束，也就是zlend的值0xFF

增加元素

因为ziplist都是紧凑存储，没有冗余空间，意味着插入一个新的元素就需要realloc扩展内存。realloc可能会重新分配的内存空间，将之前的内容一次性拷贝到新的地址，也可能在原有的地址上扩展，这是不需要拷贝旧数据。
如果ziplist占据内存太大，重新分配内存和拷贝内存都会有很大的消耗。所以ziplist不适合存储大型字符串，存储的元素也不宜过多。

级联更新

因为entry结构中存储了之前元素的大小，在某个元素更新时，会级联更新这个元素后面的元素，来刷新prevlen数据，无论是修改导致的元素长度变大变小，还是删除数据。