redis的几个数据结构——quicklist

背景

redis的内存管理以追求极致著称,我们来看看它怎么管理容易产生内存碎片的链表。

双向链表

双向链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。

ziplist

ziplist由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。

quicklist

解决方案就是把双向链表和ziplist结合起来,就是redis的quicklist,如下图所示:
redisxiancheng12

其中,由ziplist充当节点的双向链表,默认每个ziplist 8k字节,超出了这个字节数,就会新起一个 ziplist。所有的ziplist通过双向链表连在一起。

这里说一下ziplist大小的选择:这是一个需要找平衡点的难题。

我们只从存储效率上分析一下:
每个quicklist节点上的ziplist越短,则内存碎片越多。内存碎片多了,有可能在内存中产生很多无法被利用的小碎片,从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项,这就蜕化成一个普通的双向链表了。
每个quicklist节点上的ziplist越长,则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间(它们加起来很多),但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点,所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。

comments powered by Disqus