写点什么

Redis - 列表

发布于: 2021 年 05 月 16 日
Redis - 列表

Redis 是键值对数据库,值支持几种数据结构,列表是其中一种。和其他语言或者中间件中的数据结构在功能上并没有特殊支持,只是 Redis 专门对存储的数据结构进行了内存优化,这一点可能不太一样。


基本数据结构

说到列表,总得来说有两种实现方式:基于数组和基于链表。

这两者之间主要区别为内存分布的设计,从而也带来 CRUD 的不同侧重。

内存

数组的每个元素占用内存空间一定是相同的,也一定是连续分配的。带来几点结果:

1、每个元素的地址很容易通过首地址 + N * SIZE 计算出来

2、内存连续,不易导致内存碎片

3、需要为元素预分配内存,才能保证内存连续;元素个数超过预分配需要扩展时,往往需要重新整个分配内存,再把原来的元素拷贝过来


链表元素的内存空间没有要求连续,往往是分离的,通过前后元素地址指针形成一个列表。带来几点结果:

1、要找到某个元素不太容易,需要从首/尾元素开始遍历才能找到

2、内存不连续,容易导致内存碎片;需保存指针,占多余内存

3、不需要预分配内存,扩展很方便,在当前的列表继续扩展即可。

CRUD 侧重

上述不同的内存特性,带了两种结果在 CRUD 操作时的不同侧重或者说优劣。


Redis 的选择

Redis 在 3.2 版本之前有两种列表实现:ziplist 和 linkedlist。

初始化创建时,会使用 ziplist,但当达到以下条件时会切换为 linkedlist 结构。

1、某元素字符串长度大于 64 字节;

2、列表元素个数大于 512

为什么有两种实现?为什么有切换的需求?实质都是为了内存,在内存占用比较小时,ziplist 比较省内存,但内存占用较大时,增删元素的复杂度太高,不得已要切换到 linkedlist,以降低复杂度。

ziplist

ziplist 实际是一种特殊的双向链表,特殊在哪里?内存是连续分配的,但每个元素的大小是变化的。

ziplist 的结构如下,entry 是实际存放数据的地方,可以存放一个数值或者字符串。

非空 ziplist 示例图
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte +---------+--------+-------+--------+--------+--------+--------+-------+component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend | +---------+--------+-------+--------+--------+--------+--------+-------+ ^ ^ ^address | | | ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END | ZIPLIST_ENTRY_TAIL*/
复制代码

<zlbytes> 是一个无符号整数,保存着 ziplist 使用的内存数量。

<zltail> 保存着到达列表中最后一个节点的偏移量。

<zllen> 保存着列表中的节点数量。

<zlend> 的长度为 1 字节,值为 255 ,标识列表的末尾。


entry 的结构体如下:

/* * 保存 ziplist 节点信息的结构 */typedef struct zlentry {
// prevrawlen :前置节点的长度 从后往前遍历需要 // prevrawlensize :编码 prevrawlen 所需的字节大小 unsigned int prevrawlensize, prevrawlen;
// len :当前节点值的长度 从前往后遍历需要 // lensize :编码 len 所需的字节大小 unsigned int lensize, len;
// 当前节点 header 的大小 // 等于 prevrawlensize + lensize unsigned int headersize;
// 当前节点值所使用的编码类型 unsigned char encoding;
// 指向当前节点的指针 unsigned char *p;
} zlentry;
复制代码

这里需要强调下,上述结构体并不是真正的内存存储结构,只是某些场景方便计算,会将 entry 转换成上述的结构。真正的内存结构实际上就是一堆字节

unsigned int prevrawlensize, prevrawlen;表示的意思实际就是要用少个字节表示长度,长度是多少


ziplist 这种结构既没有享受到快速查询的好处(因为元素变长)也没有享受到增删的快捷(因为内存连续),唯一的好处就是省内存,时间换空间。

所以当元素规模上升到一定程度,那么时间这一点将会变得非常严峻,所以 redis 此时的应对策略就是切换成 linkedlist。

linkedlist

普通的双端列表,不再详说。


quicklist

ziplist 有些缺点,linkedlist 也有缺点,总得解决这个问题。那最终 3.2 版本后出来了个 quicklist,实际就是基于 ziplist 和 linkedlist 的折中,取代了 ziplist 和 linkedlist,作为列表的底层实现。

quicklist 大致思路:

ziplist 省内存增删慢

linkedlist 不省内存增删快

那就建一个链表,但其中元素是一个 ziplist(可以存多个字符串或者数值),这样既一定程度上得到了链表的好处,也一定程度得到了 ziplist 省内存的好处

用户头像

还未添加个人签名 2020.04.30 加入

还未添加个人简介

评论

发布
暂无评论
Redis - 列表