Redis源码分析-底层数据结构盘点 (3)

答:如果用链表的方式来保存节点,会占用离散空间,离散的空间容易产生内存碎片、并且不易导入内存,而用数组的方式,则可以使用连续内存空间。比起离散空间的链表,连续空间的数组更有利于将ziplist导入内存,这就是ziplist使用数组实现的原因。

问:ziplist使用字节数组实现,但是由于每个节点的字节数不固定,ziplist又该如何区分两个节点呢?

答:为了区分两个节点,ziplist中的节点需要保存自身节点的长度,通过自身节点的长度,从而可以定位到该节点下一个节点的首字节,相当于是下一个节点的指针。

另外,ziplist中的节点还保存了前一个节点的长度,通过它,可以定位到该节点的前一个节点的首字节,相当于是前一个节点的指针。从这个角度上来讲,ziplist又是一个双向链表。

 

4.zpilist格式

 

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

zlbytes:ziplist占总字节数

zltail:最后一个元素的偏移量,相当于ziplist的尾指针。

zllen:entry元素个数

zlend :ziplist结束标志位

entry:ziplist的各个节点

ziplist的entry 的格式:

<prevlen> <encoding> <entry-data>

prevlen :前一个元素的长度,相当于节点保存前一个元素的指针。

encoding: 记录了当前节点保存的数据的类型以及当前节点长度,相当于节点保存后一个元素的指针。

entry-data :经过压缩后的数据

 

 5.ziplist总结

 

通过观察ziplist结构体的定义可知,ziplist就是用一个字节数组,保存了双向链表,既压缩了数据,又保证了存储空间的连续性,从而极大方便了将数据从硬盘导入内存进行快速处理。

 

五、quicklist(快速链表)

 

Redis对外暴露的list数据结构,其底层实现所依赖的内部数据结构就是quicklist。quicklist就是一个块状的双向压缩链表。

 

考虑到双向链表在保存大量数据时需要更多额外内存保存指针并容易产生大量内存碎片,以及ziplist的插入删除的高时间复杂度,两个数据结构的缺陷会导致在数据量很大或插入删除操作频繁的极端情况时,性能极其低下。

Redis为了避免数据结构在极端情况下的低性能,将双向链表和ziplist综合起来,成为了较双向链表及ziplist性能更加稳定的quicklist。quicklist结构体定义:

typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* 列表中所有数据项的个数总和 total count of all entries in all ziplists */ unsigned int len; /* quicklist节点的个数,即ziplist的个数 number of quicklistNodes */ int fill : 16; /* / / ziplist大小限定,由list-max-ziplist-size给定 fill factor for individual nodes */ unsigned int compress : 16; /* 节点压缩深度设置,由list-compress-depth给定 depth of end nodes not to compress;0=off */ } quicklist; typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *zl; // 数据指针,如果没有被压缩,就指向ziplist结构,反之指向quicklistLZF结构 unsigned int sz; /* 表示指向ziplist结构的总长度(内存占用长度)ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* 编码方式,1--ziplist,2--quicklistLZF RAW==1 or LZF==2 */ unsigned int container : 2; /* 预留字段,存放数据的方式,1--NONE,2--ziplist NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /*解压标记,当查看一个被压缩的数据时,需要暂时解压,标记此参数为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;

需要特别说明的一点是,REDIS使用quicklist的目的是使数据结构在最坏情况下也能有较稳定的性能,然而为了获得稳定的性能,quicklist在最好情况下的操作的性能不如单纯的adlist或者ziplist。

这一点在新人刚开始学习复杂数据结构的时候常常会被忽略,所以说,没有最好的数据结构,只有最适用的场景

六、dict(字典)

 

在redis中数据结构中,dict字典,就是hash表。

它的实现原理与jdk中的hashmap的实现原理非常类似,都是通过链表的方式(jdk1.8后引入红黑树)解决hash冲突。

dict与hashmap的不同主要体现在在扩容时的rehash操作。 

 

jdk中的hashmap的rehash操作是一次性rehash,被调用后就会将整表rehash完之后再允许操作;

redis中的dict的rehash操作是渐进式rehash,渐进式rehash是指,分多次将hash表中的元素进行rehash;

 

redis dict使用渐进式rehash的好处是,避免保存大量数据的的dict在rehash时使redis一段时间内无法响应用户指令。

 

渐进式rehash原理:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzwdyj.html