宁阳网站定制,海口网站建设设计,常用网页设计软件,重庆seo技术分享目录标题 quicklist为什么要设计 quicklist#xff1f;quicklist特点ziplist quicklist数据结构 listpacklistpack是什么#xff1f;listpack数据结构ziplist干啥去了#xff1f;为什么有listpack?什么是ziplist的连锁更新#xff1f;listpack 如何避免连锁更新#xff1… 目录标题 quicklist为什么要设计 quicklistquicklist特点ziplist quicklist数据结构 listpacklistpack是什么listpack数据结构ziplist干啥去了为什么有listpack?什么是ziplist的连锁更新listpack 如何避免连锁更新 listpack替代了quicklist吗 quicklist
为什么要设计 quicklist
ziplist 有两个问题
不能保存过多的元素否则访问性能会下降不能保存过大的元素否则容易导致内存重新分配甚至引起连锁更新
quicklist特点
quicklist 的设计其实是结合了链表和 ziplist 各自的优势。简单来说一个 quicklist 就是一个链表而链表中的每个元素又是一个 ziplist。
结构定义quicklist.h实现quicklist.c
ziplist
Ziplist压缩列表之所以在特定场景下效率高主要是因为它在内存使用方面进行了优化特别是在存储小数据集时能够显著减少内存占用。
内存效率 Ziplist 通过对存储的数据进行紧凑编码来减少内存使用。它不仅记录了数据的实际内容还记录了每个元素的长度信息使得读取时可以快速确定每个元素的边界。这样做的好处是对于短字符串或小整数Ziplist 可以以非常紧凑的方式存储从而节省内存。
快速访问 Ziplist 中每个元素的长度信息是显式存储的这意味着访问特定元素时可以直接跳转到相应的位置无需遍历整个列表。这样即使列表中有许多元素访问特定元素的效率仍然很高。 Ziplist中的显式长度信息确实有助于定位元素但它并不提供真正的随机访问能力。对于连续访问或数据量较小的情况Ziplist的表现是不错的但在需要频繁随机访问的场景下可能需要考虑其他数据结构如哈希表或索引结构。 假设Ziplist中存储了三个元素“foo”长度3、“bar”长度3和baz长度3。为了找到第三个元素baz你需要先读取第一个元素的长度3字节然后加上第二个元素的长度再加3字节才能定位到第三个元素的位置。 适合小数据集 Ziplist 主要适用于存储少量且大小适中的元素。当列表或哈希中的元素数量不多且每个元素的大小也不大时使用Ziplist可以大大节省内存。例如对于包含少量字符串或整数的列表Ziplist的紧凑存储方式可以减少内存开销。
紧凑存储 Ziplist使用紧凑的数据格式存储整数和字符串通过使用不同的编码方式来适应不同类型的数据。例如对于整数Ziplist会根据整数值的大小选择合适的字节数如1字节、2字节、4字节或8字节来存储这样可以有效地利用内存。
适用场景 Ziplist特别适用于内存敏感的应用场景例如在存储大量小字符串或小整数时。当数据量不大时Ziplist可以提供较高的性能和较低的内存使用。
自动转换 当Ziplist中的元素数量或大小超过了预先设定的阈值时Redis会自动将其转换为其他数据结构如linkedlist或hashtable以保持良好的性能。这种机制确保了在数据量增长时Redis仍能保持高效。
Ziplist通过紧凑的数据编码和显式的长度信息记录能够在存储小数据集时提供高效的内存使用和快速的数据访问。然而对于大型数据集Ziplist的性能优势会减弱此时Redis会自动选择更合适的数据结构来替代。
quicklist数据结构
quicklist 是一个链表所以每个 quicklistNode 中都包含了分别指向它前序和后序节点的指针* prev 和* next。同时每个 quicklistNode 又是一个 ziplist所以在 quicklistNode 的结构体中还有指向 ziplist 的指针* zl。
每个元素节点 quicklistNode 的定义如下
typedef struct quicklistNode {// 前一个 quicklistNodestruct quicklistNode *prev;// 后一个 quicklistNodestruct quicklistNode *next;// quicklistNode 指向的 ziplistunsigned char *zl;// ziplist 的字节大小unsigned int sz;// ziplist 的元素个数unsigned int count: 16;// 编码方式『原生字节数组』或「压缩存储」unsigned int encoding: 2;// 存储方式NONE1 or ZIPLIST2unsigned int container: 2;// 数据是否被压缩unsigned int recompress: 1;// 数据能否被压缩unsigned int attempted_compress: 1;// 预留的 bit 位unsigned int extra: 10;
} quicklistNode;
quicklist 的结构体定义如下
typedef struct quicklist {// quicklist 的链表头quicklistNode *head;// quicklist 的链表尾quicklistNode *tail;// 所有 ziplist 中的总元素个数unsigned long count;// quicklistNodes 的个数unsigned long len;……
} quicklist;
图示
typedef struct quicklistEntry {const quicklist *quicklist;quicklistNode *node;unsigned char *zi;unsigned char *value;long long longval;unsigned int sz;int offset;
} quicklistEntry;
quicklistCreate
quicklist *quicklistCreate(void) {struct quicklist *quicklist;quicklist zmalloc(sizeof(*quicklist));quicklist-head quicklist-tail NULL;quicklist-len 0;quicklist-count 0;quicklist-compress 0;quicklist-fill -2;quicklist-bookmark_count 0;return quicklist;
}
quicklistDelIndex 删除节点
REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,unsigned char **p) {int gone 0;// 在该节点下的 ziplist 中删除node-zl ziplistDelete(node-zl, p);// count-1node-count--;// ziplist 数量为空直接删除该节点if (node-count 0) {gone 1;__quicklistDelNode(quicklist, node);} else {quicklistNodeUpdateSz(node);}// 更新所有 ziplist 中的总元素个数quicklist-count--;return gone ? 1 : 0;
}
quicklistDelEntry 删除节点
核心还是调用了 quicklistDelIndex但是 quicklistDelEntry 要维护 quicklistNode 的节点包括迭代器。
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {quicklistNode *prev entry-node-prev;quicklistNode *next entry-node-next;int deleted_node quicklistDelIndex((quicklist *)entry-quicklist,entry-node, entry-zi);iter-zi NULL;// 如果当前节点被删除更新 iteratorif (deleted_node) {if (iter-direction AL_START_HEAD) {iter-current next;iter-offset 0;} else if (iter-direction AL_START_TAIL) {iter-current prev;iter-offset -1;}}
}
quicklistInsertBefore, quicklistInsertAfter 前插和后插 插入分为两种
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,void *value, const size_t sz);
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,void *value, const size_t sz);
其底层都调用了_quicklistInsert 函数
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry,void *value, const size_t sz) {_quicklistInsert(quicklist, entry, value, sz, 0);
}void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,void *value, const size_t sz) {_quicklistInsert(quicklist, entry, value, sz, 1);
}
_quicklistInsert 函数比较长但是逻辑很简单就是判断应该在哪里插入新元素
在后面插入当前 entry 的 ziplist 未满直接插入
当前 entry 的 ziplist 已满
entry-next 的 ziplist 未满在其头部插入
entry-next 的 ziplist 已满拆分当前 entry在前面插入当前 entry 的 ziplist 未满直接插入
当前 entry 的 ziplist 已满
entry-prev 的 ziplist 未满在其尾部插入
entry-prev 的 ziplist 已满拆分当前 entry省略 _quicklistInsert函数实现。。。listpack
listpack是什么
紧凑列表用一块连续的内存空间来紧凑保存数据同时使用多种编码方式表示不同长度的数据字符串、整数。
结构定义listpack.h实现listpack.c
listpack数据结构 编码类型 在 listpack.c 文件中有大量的 LP_ENCODING__XX_BIT_INT 和 LP_ENCODING__XX_BIT_STR 的宏定义
#define LP_ENCODING_7BIT_UINT 0
#define LP_ENCODING_7BIT_UINT_MASK 0x80
#define LP_ENCODING_IS_7BIT_UINT(byte) (((byte)LP_ENCODING_7BIT_UINT_MASK)LP_ENCODING_7BIT_UINT)#define LP_ENCODING_6BIT_STR 0x80
#define LP_ENCODING_6BIT_STR_MASK 0xC0
#define LP_ENCODING_IS_6BIT_STR(byte) (((byte)LP_ENCODING_6BIT_STR_MASK)LP_ENCODING_6BIT_STR)……
listpack 元素会对不同长度的整数和字符串进行编码。
整数编码 以 LP_ENCODING_7BIT_UINT 为例元素的实际数据是一个 7 bit 的无符号整数。
整数其余的编码方式有
LP_ENCODING_16BIT_INTLP_ENCODING_24BIT_INTLP_ENCODING_32BIT_INTLP_ENCODING_64BIT_INT
字符串编码
3 种类型
LP_ENCODING_6BIT_STRLP_ENCODING_12BIT_STRLP_ENCODING_32BIT_STR
ziplist干啥去了为什么有listpack? ziplist是存储在连续内存空间节省内存空间。quicklist是个节点为ziplist的双向链表其通过控制quicklistNode结构里的压缩列表的大小或者元素个数来减少连锁更新带来的性能影响但这并没有完全解决连锁更新的问题。这是因为压缩列表连锁更新的问题来源于它的结构设计。 从Redis 5.0版本开始设计了一个新的数据结构叫做listpack 目的是替代原来的压缩列表。在每个listpack节点中不再保存前一个节点的长度所以也就不存在出现连锁更新的情况了。
Redis7.0 才将 listpack 完整替代 ziplist。
什么是ziplist的连锁更新
ziplist中元素个数多了其查找效率就降低。若是在ziplist里新增或修改数据ziplist占用的内存空间还需要重新分配更糟糕的是ziplist新增或修改元素时候可能会导致后续元素的previous_entry_length占用空间都发生变化从而引起连锁更新导致每个元素的空间都需要重新分配更加导致其访问性能下降。
listpack 如何避免连锁更新
为了应对这些问题Redis先是在3.0版本实现了quicklist结构。其是在ziplist基础上使用链表将多个ziplist串联起来即链表的每个元素是一个ziplist。这样可以减少数据插入时内存空间的重新分配及内存数据的拷贝。而且quicklist也限制了每个节点上ziplist的大小要是某个ziplist的元素个数多了会采用新增节点的方法。
但是因为quicklist使用节点结构指向了每个ziplist,这又增加了内存开销。而为了减少内存开销并进一步避免ziplist连锁更新的问题所以就有了listpack结构。
listpack每个列表项都只记录自己的长度不会像 ziplist 的列表项会记录前一项的长度。所以在 listpack 中新增或修改元素只会涉及到列表项自身的操作不会影响后续列表项的长度变化进而避免连锁更新。
listpack是沿用了ziplist紧凑型的内存布局。而listpack中每个节点不再包含前一节点的长度所以当某个节点中的数据发生变化时候导致节点的长度变化也不会影响到其他节点这就可以避免连锁更新的问题了。
listpack相比ZipList的主要优势就在于解决了连锁更新的问题提高了Redis的处理性能
listpack替代了quicklist吗
在Redis 7.0版本之前quicklist是由双向链表和压缩列表构成的。然而在Redis 7.0版本中quicklist的底层实现由双向链表和压缩列表变为了由双向链表和listpack构成的结构。
这表明虽然listpack在Redis 7.0版本中被引入并用于替代压缩列表ziplist的部分功能但quicklist的结构仍然存在只是其中的压缩列表部分被listpack所替代。因此listpack并没有完全替代quicklist而是作为quicklist的一部分改变了其原有的实现方式
