redis系列：压缩列表

基本结构

在3.0版本中基本结构如下图所示：

源码通过宏定义来实现：

/* Utility macros */
//zlbytes
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
// zltail
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
//zl+8指向zllen字段
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
//zl+zltail指向尾元素首地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
//zlend
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

• zlbytes： 压缩列表的字节长度，占4个字节，因此压缩列表最多有2^32 -1个字节。
• zltail： 压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节。
• zllen： 压缩列表的元素个数，占2个字节。zllen无法存储元素个数超过65535（2^16 -1）的压缩列表，必须遍历整个压缩列表才能获取到元素个数。
• entryX： 压缩列表存储的元素，可以是字节数组或者整数，长度不限。
• zlend： 压缩列表的结尾，占1个字节，恒为0xFF。

节点的构成

压缩列表的节点组成如下所示：

• previous_entry_length字段:
  表示前一个元素的字节长度，占1个或者5个字节，当前一个元素的长度小于254字节时，用1个字节表示；当前一个元素的长度大于或等于254字节时，用5个字节来表示。而此时previous_entry_length字段的第1个字节是固定的0xFE，后面4个字节才真正表示前一个元素长度。
• encoding字段:
  表示当前元素的编码，即content字段存储的数据类型（整数或者字节数组），数据内容存储在content字段。
• content字段：
  负责保存节点的值，节点值可以是字节数组或者整数。
  在redis中，压缩链表项如下定义：

  typedef struct zlentry {
      unsigned int prevrawlensize, prevrawlen;
      unsigned int lensize, len;
      unsigned int headersize;
      unsigned char encoding;
      unsigned char *p;
  } zlentry;

  回顾压缩列表元素的编码结构，可变因素实际上不止3个：previous_entry_length字段的长度（prevrawlensize）、previous_entry_length字段存储的内容（prevrawlen）、encoding字段的长度（lensize）、encoding字段的内容（len表示元素数据内容的长度，encoding表示数据类型）和当前元素首地址（p）；而headersize则表示当前元素的首部长度，previous_entry_length字段长度与encoding字段长度之和.

连锁更新

简单来说就是增加或者删除元素的时候，对应的previous_entry_length会发生变化，当元素长度处于临界值的时候