Redis 压缩列表

压缩链表简介

压缩列表(ziplist)是List类型和Hash类型的底层编码实现之一。比如List底层的编码有两种:ziplist和linkedlist,hash类型也有两种:ziplist和hashtable。这两种Redis的基本类型都用到了ziplist编码。

为什么List和Hash都用到了ziplist去做底层实现呢?因为ziplist对空间的利用节省到了极致,先来看下ziplist的数据结构,在源码ziplist.c文件中注释中可以看到,但是我并没有找到相关结构体的定义,只找到了entry节点的结构体定义。ziplist是个连续的entry节点组成的列表。

压缩列表数据结构

ziplist结构:
ziplist_2.png

<zlbytes><zltail><zllen><entry><entry><zlend>
  • zlbytes:记录着ziplist总大小(byte)
  • zltail:ziplist表尾的entry节点距ziplist起始位置有多少个字节,用zltail通过计算可以很快得出ziplist表尾的位置
  • zllen:压缩列表中entry节点的个数
  • entry:节点,在ziplist中连续排列
  • zlend:用于标记ziplist的结束位置,相当于字符串用'\0'来标记结束位置

entry结构:

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;	// prevrawlen前一个entry的长度
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;	// p的实际类型
    unsigned char *p;	// 节点的值
} zlentry;
  • p:节点内容,节点可以是个字节数组或者整数,它的类型和长度由encoding属性决定
  • prevrawlen:前一个entry的长度,如果前一节点的长度小于 254 字节, 那么 prevrawlen 属性的长度为 1 字节,如果前一节点的长度大于等于 254 字节, 那么prevrawlen属性的长度为 5 字节
  • encoding:p属性的实际类型,这个是ziplist节省空间的关键,如果可以动态调整p的类型大小
    ziplist_1.png

连锁更新

前面说过, 每个节点的 prevrawlen 属性都记录了前一个节点的长度:

  • 如果前一节点的长度小于 254 字节, 那么 prevrawlen 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节, 那么 prevrawlen 属性需要用 5 字节长的空间来保存这个长度值。

ziplist_1.jpg

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作, 而每次空间重分配的最坏复杂度为 O(N)

# Redis 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×