关于list:Redis数据结构二ListHashSet及Sorted-Set的结构实现

35次阅读

共计 6698 个字符，预计需要花费 17 分钟才能阅读完成。

1 引言

之前介绍了 Redis 的数据存储及 String 类型的实现，接下来再来看下 List、Hash、Set 及 Sorted Set 的数据结构的实现。

2 List

List 类型通常被用作异步音讯队列、文章列表查问等；存储有序可反复数据或做为简略的音讯推送机制时，能够应用 Redis 的 List 类型。对于这些数据的存储通常会应用链表或者数组作为存储构造。

  • 应用数组存储，随机拜访节点通过索引定位工夫复杂度为 O(1)。但在初始化时须要调配间断的内存空间；在减少数据时，如果超过以后调配空间，须要将数据整体搬迁徙到新数组中。
  • 应用链表存储，在进行前序遍历或后续遍历，以后节点中要存储前指针和后指针，这两个指针在别离须要 8byte 共 16byte 空间存储，存在大量节点会因指针占用过多空间。链表尽管不须要间断空间存储能够进步内存利用率，但频繁的减少和删除操作会使内存碎片化，影响数据读写速率。

如果咱们可能将链表和数组的特点联合起来就可能很好解决 List 类型的数据存储。

2.1 ZipList

3.2 之前 Redis 应用的是 ZipList，具体构造如下：

  • zlbytes: 4byte 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重调配，或者计算 zlend 的地位时应用。
  • zltail：4byte 记录压缩列表表尾节点间隔压缩列表的起始地址有多少字节：通过这个偏移量，程序毋庸遍历整个压缩列表就能够确定表尾节点的地址。
  • zllen：2byte 记录了压缩列表蕴含的节点数量：当这个属性的值小于 UINT16\_MAX（65535）时，这个属性的值就是压缩列表蕴含节点的数量；当这个值等于 UINT16\_MAX 时，节点的实在数量须要遍历整个压缩列表能力计算得出。
  • entry X：压缩列表蕴含的各个节点，节点的长度由节点保留的内容决定。蕴含属性如下：
  • prerawlen：记录前一个节点所占内存的字节数，不便查找上一个元素地址
  • len：data 依据 len 的首个 byte 选用不同的数据类型来存储 data
  • data：本元素的信息
  • zlend: 尾节点 恒等于 255

ziplist 是一个间断的内存块，由表头、若干个 entry 节点和压缩列表尾部标识符 zlend 组成，通过一系列编码规定，进步内存的利用率，应用于存储整数和短字符串。每次减少和删除数据时，所有数据都在同一个 ziplist 中都会进行搬移操作。如果将一个组数据按阈值进行拆分出多个数据，就能保障每次只操作某一个 ziplist。3.2 之后应用的 quicklist 与 ziplist。

2.2 QuickList

quicklist 就是保护了一种宏观上的双端链表(相似于 B 树)，链表的节点为对 ziplist 包装的 quicklistNode，每个 quciklistNode 都会通过前后指针互相指向，quicklist 蕴含头、尾 quicklistNode 的指针。

  1. typedef struct quicklist {
  2. quicklistNode *head;
  3. quicklistNode *tail;
  4. unsigned long count; /* total count of all entries in all ziplists */
  5. unsigned long len; /* number of quicklistNodes */
  6. int fill : QL_FILL_BITS; /* fill factor for individual nodes */
  7. unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
  8. ...
  9. } quicklist;
  • *head：表头节点
  • *tail：表尾节点
  • count：节点蕴含 entries 数量
  • len：quicklistNode 节点计数器
  • fill：保留 ziplist 的大小，配置文件设定
  • compress：保留压缩水平值，配置文件设定

quicklistNode：

  1. typedef struct quicklistNode {
  2. struct quicklistNode *prev;
  3. struct quicklistNode *next;
  4. unsigned char *zl;
  5. unsigned int sz; /* ziplist size in bytes */
  6. unsigned int count : 16; /* count of items in ziplist */
  7. 。。。
  8. } quicklistNode;
  • *prev：前置节点
  • *next：后置节点
  • *zl：不进行压缩时指向一个 ziplist 构造，压缩时指向 quicklistLZF 构造(具体内容请参考下方链接)
  • sz：ziplist 个数
  • count：ziplist 中蕴含的节点数

在 redis.conf 通过设置每个 ziplist 的最大容量，quicklist 的数据压缩范畴, 晋升数据存取效率, 单个 ziplist 节点最大能存储量，超过则进行决裂，将数据存储在新的 ziplist 节点中

-5: max size: 64 Kb <— not recommended for normal workloads

-4: max size: 32 Kb <— not recommended

-3: max size: 16 Kb <— probably not recommended

-2: max size: 8 Kb <— good

-1: max size: 4 Kb <— good

List-max-ziplist-size -2
0 代表所有节点，都不进行压缩，1. 代表从头节点往后一个，尾结点往前一个不必压缩，其它值以此类推
List-compress-depth 1

Redis 的链表实现的个性能够总结如下：

  • 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)。
  • 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的拜访以 NULL 为起点。
  • 带表头指针和表尾指针：通过 list 构造的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1)。
  • 带链表长度计数器：程序应用 list 构造的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1)。

3 Hash

存储一个对象，能够间接将该对象进行序列化后应用 String 类型存储，再通过反序列化获取对象。对于只须要获取对象的某个属性的场景，能够将将每个属性别离存储；但这样在 Redis 的 dict 中就会存在大量的 key，对于键时效后的回收效率存在很大影响。应用 Map 构造就能够再 dict 的存储中只存在一个 key 并将属性与值再做关联。

Redis 的 Hash 数据结构也是应用的 dict(具体实现能够查看上一篇，浅谈 Redis 数据结构 (上)-Redis 数据存储及 String 类型的实现) 实现。当数据量比拟小，或者单个元素比拟小时，底层应用 ziplist 存储，数据量大小和元素数量有如下配置：

ziplist 元素个数超过 512，将改为 hashtable 编码
hash-max-ziplist-entries 512
单个元素大小超过 64byte 时，将改为 hashtable 编码
hash-max-ziplist-value 64

4 Set

Set 类型能够在对不反复汇合操作时应用，能够判断元素是否存在于汇合中。Set 数据结构底层实现为 value 为 null 的 dict，当数据能够应用整形示意时，Set 汇合将被编码为 intset 构造。

  1. typedef struct intset {
  2. uint32_t encoding;
  3. uint32_t length;
  4. int8_t contents[];
  5. } intset;

整数汇合是一个有序的，存储整型数据的构造。整型汇合在 Redis 中能够保留 xxxx 的整型数据，并且能够保障汇合中不会呈现反复数据。

应用 intset 能够节俭空间，会依据最大元素范畴确定所有元素类型；元素有序存储在判断某个元素是否存在时能够基于二分查找。但在以下任意条件不满足时将会应用 hashtable 存储数据。

  • 元素个数大于配置的 set-max-inset-entries 值
  • 元素无奈用整型示意

5 Sorted Set

间断空间存储数据，每次减少数据都会对全量数据进行搬运。对于有序链表查找指定元素，只能通过头、尾节点遍历形式进行查找，如果将每个数据减少不定层数的索引，索引之间互相关联，寻找指定或范畴的元素时就能够通过遍历层级的索引来确定元素所处范畴，缩小空间复杂度。跳跃表是一种能够对有序链表进行近似二分查找的数据结构，redis 在两个中央用到了跳跃表，一个是实现有序汇合，另一个是在集群节点中用作外部数据结构。

跳跃表 (skiplist) 是一种有序数据结构，主动去重的汇合数据类型，ZSet 数据结构底层实现为字典(dict) + 跳表(skiplist)。它通过在每个节点中维持多个指向其余节点的指针，从而达到快速访问节点的目标。反对均匀 O (logN)、最坏 O(N) 复杂度的节点查找，还能够通过程序性操作来批量解决节点。

数据比拟少时，用 ziplist 编码构造存储，蕴含的元素数量比拟多，又或者有序汇合中元素的成员(member) 是比拟长的字符串时，Redis 就会应用跳跃表来作为有序汇合键的底层实现。

元素个数超过 128，将用 skiplist 编码
zset-max-ziplist-entries 128

单个元素大小超过 64 byte，将用 skiplist 编码
zset-max-ziplist-value 64

5.1 跳跃表

zset 构造如下：

  1. typedef struct zset {
  2. // 字典，存储数据元素
  3. dict *dict;
  4. // 跳跃表，实现范畴查找
  5. zskiplist *zsl;
  6. } zset;
  7. robj *createZsetObject(void) {
  8. // 调配空间
  9. zset *zs = zmalloc(sizeof(*zs));
  10. robj *o;
  11. // dict 用来查问数据到分数的对应关系，zscore 能够间接依据元素拿到分值
  12. zs->dict = dictCreate(&zsetDictType,NULL);
  13. // 创立 skiplist
  14. zs->zsl = zslCreate();
  15. o = createObject(OBJ_ZSET,zs);
  16. o->encoding = OBJ_ENCODING_SKIPLIST;
  17. return o;
  18. }

zskiplist

  1. typedef struct zskiplist {
  2. // 头、尾节点; 头节点不存储元素，领有最高层高
  3. struct zskiplistNode *header, *tail;
  4. unsigned long length;
  5. // 层级, 所有节点中的最高层高
  6. int level;
  7. } zskiplist;
  8. typedef struct zskiplistNode {
  9. // 元素 member 值
  10. sds ele;
  11. // 分值
  12. double score;
  13. // 后退指针
  14. struct zskiplistNode *backward;
  15. // 节点中用 L1、L2、L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。
  16. struct zskiplistLevel {
  17. // 指向本层下一个节点，尾节点指向 null
  18. struct zskiplistNode *forward;
  19. // *forward 指向的节点与本节点之间的元素个数，span 值越大，跳过的节点个数越多
  20. unsigned long span;
  21. } level[];
  22. } zskiplistNode;

结构图如下：

5.2 创立节点及插入流程

SkipList 初始化，创立一个有最高层级的空节点：

  1. zskiplist *zslCreate(void) {
  2. int j;
  3. zskiplist *zsl;
  4. // 调配空间
  5. zsl = zmalloc(sizeof(*zsl));
  6. // 设置起始档次
  7. zsl->level = 1;
  8. // 元素个数
  9. zsl->length = 0;
  10. // 初始化表头，表头不存储元素，领有最高的层级
  11. zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
  12. // 初始化层高
  13. for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
  14. zsl->header->level[j].forward = NULL;
  15. zsl->header->level[j].span = 0;
  16. }
  17. // 设置表头后退指针为 NULL
  18. zsl->header->backward = NULL;
  19. // 初始表尾为 NULL
  20. zsl->tail = NULL;
  21. return zsl;
  22. }

新增元素：

  1. zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
  2. zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  3. unsigned int rank[ZSKIPLIST_MAXLEVEL];
  4. int i, level;
  5. serverAssert(!isnan(score));
  6. x = zsl->header;
  7. // 遍历所有层高，寻找插入点：高位 -> 低位
  8. for (i = zsl->level-1; i >= 0; i--) {
  9. // 存储排位，便于更新
  10. rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
  11. while (x->level[i].forward &&
  12. // 找到第一个比新分值大的节点，后面一个地位即是插入点
  13. (x->level[i].forward->score < score ||
  14. (x->level[i].forward->score == score &&
  15. // 雷同分值则按字典程序排序
  16. sdscmp(x->level[i].forward->ele,ele) < 0)))
  17. {
  18. // 累加跨度
  19. rank[i] += x->level[i].span;
  20. x = x->level[i].forward;
  21. }
  22. // 每一层的拐点
  23. update[i] = x;
  24. }
  25. // 随机生成层高，以 25% 的概率决定是否呈现下一层，越高的层呈现概率越低
  26. level = zslRandomLevel();
  27. // 随机层高大于以后的最大层高，则初始化新的层高
  28. if (level > zsl->level) {
  29. for (i = zsl->level; i < level; i++) {
  30. rank[i] = 0;
  31. update[i] = zsl->header;
  32. update[i]->level[i].span = zsl->length;
  33. }
  34. zsl->level = level;
  35. }
  36. // 创立新的节点
  37. x = zslCreateNode(level,score,ele);
  38. for (i = 0; i < level; i++) {
  39. // 插入新节点，将新节点的以后层前指针更新为被批改节点的前指针
  40. x->level[i].forward = update[i]->level[i].forward;
  41. update[i]->level[i].forward = x;
  42. // 新节点跨度为后一节点的跨度 - 两个节点之间的跨度
  43. x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
  44. update[i]->level[i].span = (rank[0] - rank[i]) + 1;
  45. }
  46. // 新节点退出，更新顶层 span
  47. for (i = level; i < zsl->level; i++) {
  48. update[i]->level[i].span++;
  49. }
  50. // 更新后退指针和尾指针
  51. x->backward = (update[0] == zsl->header) ? NULL : update[0];
  52. if (x->level[0].forward)
  53. x->level[0].forward->backward = x;
  54. else
  55. zsl->tail = x;
  56. zsl->length++;
  57. return x
  58. }

5.3 SkipList 与均衡树的比拟

skiplist 是为了实现 sorted set 相干性能，红黑树也能实现，并且 sorted set 会存储更多的冗余数据。Redis 作者 antirez 曾答复过这个问题，原文见 https://news.ycombinator.com/item?id=1171423

大抵内容如下：

skiplist 只须要调整下节点到更高 level 的概率，就能够做到比 B 树更少的内存耗费。
sorted set 面对大量的 zrange 和 zreverange 操作，作为单链表遍历的实现性能不亚于其它的均衡树。
实现比较简单。

6 参考学习

  • 《Redis 设计与实现》：https://www.w3cschool.cn/hdclil/cnv2lozt.html
  • 双端列表：https://blog.csdn.net/qq_20853741/article/details/111946054

作者：盛旭

正文完
List
发表至： List
2022-10-26
 0
关于list:我要在for循环List中删除元素
关于list:java-List分页取值
关于list:大数据列表渲染系列二极简实现
关于list:Redis数据结构二ListHashSet及Sorted-Set的结构实现