Redis的早期版本存储list列表的数据结构是ziplist和普通的双向链表linkedlist,元素个数少时使用ziplist,多时用linkedlist。
//链表的节点 struct listNode<T> { listNode* prev; listNode* next; T value; } //链表 struct list { listNode *head; //64位OS占8个字节 listNode *tail; //64位OS占8个字节 long length; }
考虑到:
1.链表的信息占用存储空间相对较高
2.每个节点单独分配,会加剧内存的碎片化,影响管理效率
所以后续新版本对list的结构进行了改造,统一为quicklist
typedef struct quicklistNode { struct quicklistNode *prev; //上一个node节点 struct quicklistNode *next; //下一个node unsigned char *zl; //保存的数据 压缩前ziplist 压缩后压缩的数据 unsigned int sz; /* ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int extra : 10; /* more bits to steal for future usage */ } quicklistNode; typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[]; } quicklist;
为了进一步节约空间,Redis还会对ziplist进行压缩存储,使用LZF算法压缩,可以选择压缩深度。
【ziplist元素个数】
看完了整体结构,我们需要看看每个quicknode中的ziplist里有多少个元素。quicklist默认单个ziplist长度位8KB,超出这个字节数,就会另起一个ziplist。ziplist的长度由配置参数list-max-ziplist-size决定。
【quicklist压缩深度】
默认为0,即不压缩。实际深度由list-compress-depth决定。
压缩深度为1,即首尾第一个元素都不压缩,压缩深度为2,即首尾第一个以及第二个元素都不压缩。