Redis 设计与实现 6:五大数据类型之列表

列表对象有 3 种编码:ziplistlinkedlistquicklist

  • ziplistlinkedlist 是 3.2 版本之前的编码。
  • quicklist 是 3.2 版本新增的编码,ziplistlinkedlist 在 3.2 版本及后续版本将不再是列表对象的编码。

编码定义如下(server.h):

#define OBJ_ENCODING_LINKEDLIST 4#define OBJ_ENCODING_ZIPLIST 5#define OBJ_ENCODING_QUICKLIST 9

虽然 ziplistlinkedlist 不再被列表对象作为编码,但是我们还是有必要了解的。因为 quicklist 也是基于 ziplistlinkedlist 改良的。


ziplist

压缩列表 ziplist 在之前的文章 Redis 设计与实现 5:压缩列表 ziplist 有介绍过,结构如下:

我们使用命令操作列表的元素的时候,实际上就是在操作 entry 的数据。下面我们来举个栗子:

redis> RPUSH list_key 1 "ab" "d"

如果 list_keyziplist 编码,那么结构如下图:


linkedlist

链表 linkedlist 的数据结构如下(adlist.h),跟普通的链表差不多:

typedef struct list {    // 头结点    listNode *head;    // 尾节点    listNode *tail;    // 复制链表节点的值    void *(*dup)(void *ptr);    // 释放链表节点的值    void (*free)(void *ptr);    // 对比链表节点所保存的值跟输入的值是否相等    int (*match)(void *ptr, void *key);    // 链表包含的节点数    unsigned long len;} list;

链表节点的结构也很简单:

typedef struct listNode {    // 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 当前节点的值    void *value;} listNode;

结构示意图如下:

数据将存储在 listNode 的 value 中,数据是一个字符串对象,用 redisObject 包裹着 sds
例如可能是 embstr 编码的 sds :


下面我们来举个栗子:

redis> RPUSH list_key 1 "ab" "d"

假如 list_key 的编码是 linkedlist,那么结构如下图:


quicklist

快速列表 quicklist3.2 版本新添加的编码类型,结合了 ziplistlinkedlist 的一种编码。
同时在 3.2 版本中,列表也废弃了 ziplistlinkedlist

通过上面的介绍,我们可以看出。双向链表的内存开销很大,每个节点的地址不连续,容易产生内存碎片,quicklist 利用 ziplist减少节点数量,但 ziplist 插入和删除数都很麻烦,复杂度高,为避免长度较长的 ziplist修改时带来的内存拷贝开销,通过配置项配置合理的 ziplist长度。

quicklist 的结构如下:

从上图可以看出,quicklistlinkedlist 最大的不同就是,quicklist 的值指向的是 ziplistziplist 可比之前的 redisObject 节省了非常多的内存!
从另一个角度看,他就是把一个长的 ziplist 切割成多个小的 ziplist


代码实现在 quicklist.h:

typedef struct quicklist {    quicklistNode *head;    quicklistNode *tail;    // 所有 ziplist 中所有的节点数    unsigned long count;    // quicklistNode 的数量    unsigned long len;    // 限定 ziplist 的最大大小,可通过配置文件配置    int fill : QL_FILL_BITS;    // 压缩程度,0 表示不压缩,可通过配置文件配置    unsigned int compress : QL_COMP_BITS;    // ...} quicklist;

配置一:fill (控制 ziplist 大小)

太长的 ziplist 增删的复杂度高,所以 quicklistfill 参数来控制 ziplist 的大小,它是通过配置文件的list-max-ziplist-size配置。

  • 当数字为正数,表示:每个节点的 ziplist 最多包含的 entry 个数。
  • 当数字为负数:
    • -1:每个节点的 ziplist 字节大小不能超过4kb
    • -2:每个节点的 ziplist 字节大小不能超过8kb (redis默认值)
    • -3:每个节点的 ziplist 字节大小不能超过16kb
    • -4:每个节点的 ziplist 字节大小不能超过32kb
    • -5:每个节点的 ziplist 字节大小不能超过64kb

配置二:compress (控制压缩程度)

因为链表的特性,一般首尾两端操作较频繁,中部操作相对较少,所以 redis 提供压缩深度配置:list-compress-depth,也就是属性 compress

  • 0:表示都不压缩。这是Redis的默认值。
  • 1:表示 quicklist 两端各有1个节点不压缩,中间的节点压缩。
  • 2:表示 quicklist 两端各有2个节点不压缩,中间的节点压缩。
  • 3:表示 quicklist 两端各有3个节点不压缩,中间的节点压缩。

quicklist 节点

typedef struct quicklistNode {    struct quicklistNode *prev;    struct quicklistNode *next;    // 不设置压缩数据参数 recompress 时指向一个 ziplist 结构    // 设置压缩数据参数recompress 时指向 quicklistLZF 结构    unsigned char *zl;    // ziplist 的字节数    unsigned int sz;    // ziplist 中包含的节点数量    unsigned int count : 16;    // 编码。1 表示压缩过,2 表示没压缩    unsigned int encoding : 2;    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */    // 标记 quicklist 节点的 ziplist 之前是否被解压缩过    // 如果recompress 为 1,则等待被再次压缩    unsigned int recompress : 1;    // ...} quicklistNode;

压缩过的 ziplist 结构

typedef struct quicklistLZF {    // 表示被 LZF 算法压缩后的 ziplist 的大小    unsigned int sz;    // 压缩后的 ziplist 的数组,柔性数组    char compressed[];} quicklistLZF;

quick 的常用操作

1. 插入

(1) quicklist 可以在头部或者尾部插入数据:quicklist.c/quicklistPushHeadquicklist.c/quicklistPushTail,我们就挑一个从头部插入的代码来看看吧(插入尾部的代码也是差不多的)(代码格式略微调整了一下):

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {    quicklistNode *orig_head = quicklist->head;    // 判断头结点上的 ziplist 大小是否没超过限制    if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {    // 没超过限制,就插入到 ziplist 中。ziplistPush 是 ziplist.c 的方法        quicklist->head->zl = ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);        quicklistNodeUpdateSz(quicklist->head);    } else {    // ziplist 超过大小限制,则创新创建一个新的 quicklistNode        quicklistNode *node = quicklistCreateNode();        // 再创建新的 ziplist,然后把 ziplist 放到节点中        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);        quicklistNodeUpdateSz(node);        // 新的 quicklistNode 插入原来的头结点上,成为新的头结点        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);    }    quicklist->count  ;    quicklist->head->count  ;    return (orig_head != quicklist->head);}

(2) quicklist 也可以从任意指定的位置插入:quicklist.c/_quicklistInsert,实现相对来说比较复杂,我们就用文字说明(代码太长,感兴趣的读者自己去读吧):

  • 当前节点是 NULL:创建一个新的节点,插入就好。
  • 当前节点的 ziplist 大小没有超过限制时:直接插入到 ziplist 就好。
  • 当前节点的 ziplist 大小超过限制时:
    • 如果插入的位置是 ziplist两端

      • 如果相邻的节点的 ziplist 大小没有超过限制,那么就插入到相邻节点ziplist 中。
      • 如果相邻的节点的 ziplist 大小也超过限制,这时需要创建一个新的节点插入。
    • 如果插入的位置是 ziplist中间
      则需要把当前 ziplist 从插入位置 分裂 (_quicklistSplitNode) 为两个节点,然后把数据插入第二个节点上。

2. 查找

quicklist 支持通过 index 查找元素:quicklist.c/quicklistIndex
查找的本质就是遍历,先查看quicklistNode 的长度判断 index 是否在这个节点中,如果不是则跳到下个节点。
当定位到节点之后,对节点里面的 ziplist 进行遍历查找 (ziplistIndex)。

3 删除

(1) 指定值的删除,quicklist.c/quicklistDelEntry
这个指定的值的信息 quicklistEntry 的结构如下:

typedef struct quicklistEntry {    // 指向当前 quicklist 的指针    const quicklist *quicklist;    // 指向当前 quicklistNode 节点的指针    quicklistNode *node;    // 指向当前 ziplist 的指针    unsigned char *zi;    // 指向当前 ziplist 的字符串 vlaue 成员    unsigned char *value;    // 当前 ziplist 的整数 value 成员    long long longval;    // 当前 ziplist 的字节数大小    unsigned int sz;    // 在 ziplist 的偏移量    int offset;} quicklistEntry;

具体的删除代码如下(做了一些删减):

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {    quicklistNode *prev = entry->node->prev;    quicklistNode *next = entry->node->next;    // 通过 quicklistEntry 可以定位到 ziplist 中的元素位置,然后进行删除    // quicklist -> quicklistNode -> ziplist -> ziplistEntry    int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist, entry->node, &entry->zi);    // 下面是迭代器的参数调整,此处忽略...}

(2) 区间元素 index 删除: quicklist.c/quicklistDelRange(代码太长了,就不晾出来了)
先通过遍历找元素,会判断是否可以删除整个节点 entry.offset == 0 && extent >= node->count,可以的话不用遍历里面的ziplist直接删除整个节点。
否则计算出当前节点ziplist 要删除的范围,通过 ziplistDeleteRange 函数删除。


重点回顾

  • 列表对象有 3 种编码:ziplistlinkedlistquicklist
  • quicklist3.2 后新增的用于替代 ziplistlinkedlist 的编码。
  • ziplist 节省内存,但是太长的话性能低下。linkedlist 占用内存太多。
  • quicklist 可以看成由多个 ziplist 组成的 linkedlist,性能高,节省内存。

来源:https://www.icode9.com/content-2-804751.html

(0)

相关推荐

  • Redis 核心篇:唯快不破的秘密

    " 天下武功,无坚不摧,唯快不破! " 学习一个技术,通常只接触了零散的技术点,没有在脑海里建立一个完整的知识框架和架构体系,没有系统观.这样会很吃力,而且会出现一看好像自己会,过 ...

  • java开发技术之Redis类型技能入门篇

    字符串 首先Redis数据存储都会以key value 的形式进行存放, 所有的key都是字符串类型.此处所说的类型特指的是value中存放的类型.下文所讲的hash.列表都是基于value上进行讲解 ...

  • 一文搞定Redis五大数据类型及使用场景

    Redis 是一种基于键值对的NoSQL数据库,它的值主要由string(字符串),hash(哈希),list(列表),set(集合),zset(有序集合)五种基本数据结构构成,除此之外还支持一些其他 ...

  • redis五大数据类型使用场景

    Redis是一种基于键值对的NoSQL数据库,它的值主要由string(字符串),hash(哈希),list(列表),set(集合),zset(有序集合)五种基本数据结构构成,除此之外还支持一些其他的 ...

  • 设计被动房的五大原则

    "被动房"这个名字已经表明,被动房原理强调被动方式,即运用的技术中不需要运动部件(例如:阀门.泵.发动机等),不需要麻烦的控制方式,不需要要复杂的机械.而用到的主动式技术则简单,易 ...

  • Redis高频面试笔记:基础+缓存雪崩+哨兵+集群+Reids场景设计

    七月份,Redis之父Salvatore Sanfilippo在自己的博客上发布了一则公告,宣告自己退出了Redis维护者行列,正式成为一位二线"谋士". Redis 之父 Sal ...

  • redis数据类型之set,zset,hash

    上一篇说了string和list两种数据类型,现在说说剩下的几种数据类型: 继续敲命令每一个命令,害╮(╯_╰)╭ 1.set 这个就类似于java中的Set<Set<T>>, ...

  • 落地页设计的五大要素和两种类型

    诸葛君说:平时,在市场营销过程中,很多企业花大量的市场费用做矩阵式推广投放,但经常会遇到这种情况:做了很多广告投放,也做了很多优化,投放页面每天的流量和点击消费都很高,可是获取的客户线索和购买率就是上 ...

  • 花艺师必懂的五大设计要素,你都知道哪些?(一)

    花艺是指通过一定的技术手法,将花材排列组合或者搭配使其变得更加赏心悦目,体现自然与人以及环境的完美结合. 花艺设计的五大要素分别是线条.形态.空间.质感.颜色,下面小编就为大家一一介绍. 第一大要素: ...

  • 花艺师必懂的五大设计要素,你都知道哪些?(二)

    上一篇文章中小编给大家介绍了五大设计要素中的前面两种,那么现在让我们一起来看看后面的三种要素吧. 第三大要素:空间[学会做加减法] 空间在花艺设计中有两个基本含义:积极空间与消极空间的应用.空间不仅仅 ...

  • 学习下Redis这个核心数据类型

    string 字符串 tring 类型是二进制安全的,即 string 中可以包含任何数据. Redis 中的普通 string 采用 raw encoding 即原始编码方式,该编码方式会动态扩容, ...