前段时间翻看了 Redis 的源代码(C 语言版本, Git 地址: https://github.com/antirez/redis ),
过了一遍 Redis 数据结构, 包括 SDS,ADList,dict,intset,ziplist,quicklist,skiplist.
在此进行总结
一, SDS(Simple Dynamic String) 简单动态字符串
SDS 是 Redis 最简单的数据结构
sds(简单动态字符串)特点, 预先分配内存, 记录字符串长度, 在原字符串数组里新增加一串字符串.
新长度 newlen 为原 len+addlen, 若 newlen 小于 1M, 则为 SDS 分配新的内存大小为 2*newlen; 若 newlen 大于等于 1M, 则 SDS 分配新的内存大小为 newlen + 1M
SDS 是以 len 字段来判断是否到达字符串末尾, 而不是以'\0'判断结尾. 所以 sds 存储的字符串中间可以出现'\0', 即 sds 字符串是二进制安全的.
当要清空一个 SDS 时, 并不真正释放其内存, 而是设置 len 字段为 0 即可, 这样当之后再次使用到该 SDS 时, 可避免重新分配内存, 从而提高效率.
SDS 的好处就是通过预分配内存和维护字符串长度, 实现动态字符串.
二, ADList(A generic doubly linked list) 双向链表
ADList 就是个具有头尾指针的双向链表, 没什么可以多说的, 看一下结构体的定义
- 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;
三, skipList 跳表
Redis 使用跳跃表作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员 (member) 是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现.
1. 跳表描述
先看一下比较抽象的描述
1. 跳表是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的.
2. 跳跃表支持平均 O(log N) 复杂度的节点查找, 还可以通过顺序性操作来批量处理节点.
3. 在大部分情况下, 跳跃表的效率可以和平衡树相媲美, 并且因为跳跃表的实现比平衡树要来得更为简单, 所以有不少程序都使用跳跃表来代替平衡树.
这样的描述对数据结构理解不够深刻的同学或许难以理解, 别着急, 下面看楼主对跳表给出的解释.
1. 跳表本质是一个有序链表.(此刻你应想一下一个有序链表是怎样的)
2. 跳表的查询, 插入, 删除的时间复杂度均为 O(logn), 跟平衡二叉树的时间复杂度是一样的.
3. 跳表是一种通过空间冗余来换取时间效率的数据结构.(怎么样的空间冗余的有序链表能换取更高的查询效率呢?)
下来看一下跳表的数据结构的示意图
注意观察示意图中圈起来的链表, 它是有序的原始链表, 存入跳表的数据, 就存在这张链表中.
那么上面额外的两条链表又是什么呢, 他们有什么作用呢?
上面的两条链表就是所谓的冗余空间, 他们相当于是跳表的索引, 通过这样的冗余空间就可以在有序链表的基础上实现更高效率的查询.
2. 跳表如何提高效率
举个例子
譬如查询 59 这个元素, 如果只有原始链表, 你需要依次遍历 14-23-34-43-50-59, 总共 6 个节点, 而通过上面 2 条链表, 你将依次遍历 14-50-59, 总共 3 个节点.
这个例子已经说明了跳表通过冗余空间对查询效率的优化, 但是我们还需要理论证明它带来的查询效率的优化对于所有 case 存在而不是仅仅某些特定的 case.
3. 跳表查询优化证明
跳表查询优化实际上利用了二分查找的思想, 基于有序链表的二分查找.
观察跳表结构, 从最底层开始, 每隔一个或者两个节点向上抽取一个节点作为索引链表, 当抽取到最顶层时, 最终只剩两个元素.
查询时, 从顶层链表开始将查询关键字与链表节点进行对比, 逐层向下进行查找.
譬如查询 59 这个元素的过程如下:
对比 59,14, 发现 59>14.
对比 59,50, 发现 59>50.
50 在顶层是最后一个元素, 从 50 节点下降一层.
对比 59,72, 发现 59<72.
即 59>50 且 59<72, 从 50 节点下降一层.
对比 59,59, 查找成功返回节点
通过这样的查找方式, 优化了时间效率.
一般来说, 跳表存储的关键字越多, 跳表的冗余数据也会越多, 跳表的层数也越高, 并且,
实际上, 到底隔多少个节点向上抽取一个节点并不是固定的.
若抽取节点的间距越大, 则使用冗余空间越少, 跳表总层数越小, 查询效率越低 .
若抽取节点的间距越小(最小为 1), 则使用冗余空间越多, 跳表总层数越大, 查询效率越高.
这便是以空间换取时间.
4. 跳表结构体 c 语言定义
跳表的示意图看起来很复杂, 那么怎么用 c 语言实现跳表呢. 其实, 跳表的实现非常简单, 看一下跳表结构体的基本定义.
- struct skipList{
- int lenth;
- skipListNode* head;
- }skiplist;
跳表结构体记录了存储的元素个数和跳表头节点.
- struct skipListNode{
- skipListNode* levelnext[3];
- int currentlevel;
- int totallevel;
- int value;
- }
跳表节点结构体除了维护保存的关键字外还保存下一个链表节点指针 levelnext 和当前层数 currentlevel. 可以看见, 下一个链表节点指针是一个大小为 3 的数组.
数组中的元素指向该节点在某一层的下一个节点.
譬如示意图中的 14 节点, 它的 level[0]指向 23,level[1]指向 34,level[2]指向 50. 当需要降层查询时, 只需要将 clevel-1 即可. 这样便实现了跳表的基本查询逻辑.
而跳表的插入删除逻辑, 在经过 O(logn)复杂度查找到待删除节点或插入位置后, 经过 O(1)的时间复杂度即可完成.
5. 跳表索引更新
下面考虑这样的问题
如果我往例子中的跳表插入 24,25,26,27, 那么在 14-34 之间元素就会新增加 4 个, 那么如果我在这之间继续插入更多元素, 但又不更新索引, 那么随着插入元素的增加, 跳表的查询效率将会退化成 O(n).
其实, 这就像二叉排序树的失衡问题, 平衡二叉树通过额外的翻转操作来维护树的左右平衡来确保它的效率, 在跳表中, 这个额外的操作就是更新索引, 那么, 跳表是怎么更新索引的呢?
在 Redis 中是通过一个随机函数, 来决定将这个结点插入到哪几层索引中, 比如随机函数生成了值 K, 那么我就将这个结点添加到第一级的到第 K 级的索引中, 以此来避免复杂度的退化.
最后补充一点, Redis 中的 跳表实际上是双向的, 并且保存头尾指针, 支持双向遍历.
四, ziplist(压缩链表)
1.ziplist 介绍
ziplist 是经过特殊编码的方式压缩的集合
Redis 中, 当 list 和 hash 元素较少并且数值较小时, 使用 ziplist 实现, 因为在数据量小的时候 ziplist 的查询效率接近于 O(1), 与 hash 效率相似, ziplist 是一整块连续内存, 实质是个数组, 不利于插入删除和查找. 删除节点时, 将节点之后的所有节点前移. 由于节点保存前一个节点的长度(可能一个字节, 可能 4 个字节), 如果删除某节点后导致之后的节点长度发生变化, 需要级联更新之后的各个节点长度, 直到不用更新长度的节点为止.
ziplist 唯一的优势: 以字节为单位, 通过压缩变长编码的方式节省大量存储空间, 当需要使用时, 数据可以从磁盘中快速导入内存中处理, 而数据在内存中的操作速度是极快的, 通过节省存储空间的方式节省了时间.
2.ziplist 数据结构
我们先看一个普通数组 arr[100]的空间利用情况
- struct Node{
- int value1;
- long value2;
- }arr[100];
arr 数组内存 2 个变量 value1,value2, 分别是 int 及 long 类型, 分别占用 4 个字节和 8 个字节, 当我们存储小数值时, 就会导致内存的浪费, 如 arr[0].value1=100, 实际上 100 仅使用了 1 个字节, 但是却占用了 4 个字节.
而 ziplisl 就是 Redis 为充分利用存储空间所设计的数据结构, 实际上就是一个字节数组.
char ziplist[];
所有类型的数据, 包括 long,int, 指针类型, 字符串类型, 在存入 ziplist 时都会先被压缩编码.
3. 关于 ziplist 的两个问题
问: 由于保存进 ziplist 的元素都会被压缩编码, ziplist 中每个节点所占的字节数并不是固定的, 那么 ziplist 能否用链表来存储呢?
答: 如果用链表的方式来保存节点, 会占用离散空间, 离散的空间容易产生内存碎片, 并且不易导入内存, 而用数组的方式, 则可以使用连续内存空间. 比起离散空间的链表, 连续空间的数组更有利于将 ziplist 导入内存, 这就是 ziplist 使用数组实现的原因.
问: ziplist 使用字节数组实现, 但是由于每个节点的字节数不固定, ziplist 又该如何区分两个节点呢?
答: 为了区分两个节点, ziplist 中的节点需要保存自身节点的长度, 通过自身节点的长度, 从而可以定位到该节点下一个节点的首字节, 相当于是下一个节点的指针.
另外, ziplist 中的节点还保存了前一个节点的长度, 通过它, 可以定位到该节点的前一个节点的首字节, 相当于是前一个节点的指针. 从这个角度上来讲, ziplist 又是一个双向链表.
4.zpilist 格式
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
zlbytes:ziplist 占总字节数
zltail: 最后一个元素的偏移量, 相当于 ziplist 的尾指针.
zllen:entry 元素个数
zlend :ziplist 结束标志位
entry:ziplist 的各个节点
ziplist 的 entry 的格式:
<prevlen> <encoding> <entry-data>
prevlen : 前一个元素的长度, 相当于节点保存前一个元素的指针.
encoding: 记录了当前节点保存的数据的类型以及当前节点长度, 相当于节点保存后一个元素的指针.
entry-data : 经过压缩后的数据
5.ziplist 总结
通过观察 ziplist 结构体的定义可知, ziplist 就是用一个字节数组, 保存了双向链表, 既压缩了数据, 又保证了存储空间的连续性, 从而极大方便了将数据从硬盘导入内存进行快速处理.
五, quicklist(快速链表)
1.quicklist 介绍
Redis 对外暴露的 list 数据结构, 其底层实现所依赖的内部数据结构就是 quicklist.quicklist 就是一个块状的双向压缩链表.
考虑到双向链表在保存大量数据时需要更多额外内存保存指针并容易产生大量内存碎片, 以及 ziplist 的插入删除的高时间复杂度, 两个数据结构的缺陷会导致在数据量很大或插入删除操作频繁的极端情况时, 性能极其低下.
Redis 为了避免数据结构在极端情况下的低性能, 将双向链表和 ziplist 综合起来, 成为了较双向链表及 ziplist 性能更加稳定的 quicklist.
2.quicklist 结构体定义
- typedef struct quicklist {
- quicklistNode *head;
- quicklistNode *tail;
- unsigned long count; /* 列表中所有数据项的个数总和 total count of all entries in all ziplists */
- unsigned int len; /* quicklist 节点的个数, 即 ziplist 的个数 number of quicklistNodes */
- int fill : 16; /*// ziplist 大小限定, 由 list-max-ziplist-size 给定 fill factor for individual nodes */
- unsigned int compress : 16; /* 节点压缩深度设置, 由 list-compress-depth 给定 depth of end nodes not to compress;0=off */
- } quicklist;
- typedef struct quicklistNode {
- struct quicklistNode *prev;
- struct quicklistNode *next;
- unsigned char *zl; // 数据指针, 如果没有被压缩, 就指向 ziplist 结构, 反之指向 quicklistLZF 结构
- unsigned int sz; /* 表示指向 ziplist 结构的总长度(内存占用长度)ziplist size in bytes */
- unsigned int count : 16; /* count of items in ziplist */
- unsigned int encoding : 2; /* 编码方式, 1--ziplist,2--quicklistLZF RAW==1 or LZF==2 */
- unsigned int container : 2; /* 预留字段, 存放数据的方式, 1--NONE,2--ziplist NONE==1 or ZIPLIST==2 */
- unsigned int recompress : 1; /* 解压标记, 当查看一个被压缩的数据时, 需要暂时解压, 标记此参数为 1, 之后再重新进行压缩 was this node previous compressed? */
- unsigned int attempted_compress : 1; /* 测试相关 node can't compress; too small */
- unsigned int extra : 10; /* 扩展字段, 暂时没用 more bits to steal for future usage */
- } quicklistNode;
需要特别说明的一点是, Redis 使用 quicklist 的目的是使数据结构在最坏情况下也能有较稳定的性能, 然而为了获得稳定的性能, quicklist 在最好情况下的操作的性能不如单纯的 adlist 或者 ziplist.
这一点在新人刚开始学习复杂数据结构的时候常常会被忽略, 所以说, 没有最好的数据结构, 只有最适用的场景
六, dict(字典)
1.dict 介绍
在 Redis 中数据结构中, dict 字典, 就是 hash 表.
它的实现原理与 jdk 中的 hashmap 的实现原理非常类似, 都是通过链表的方式 (jdk1.8 后引入红黑树) 解决 hash 冲突.
2.dict rehash
dict 与 hashmap 的不同主要体现在在扩容时的 rehash 操作.
jdk 中的 hashmap 的 rehash 操作是一次性 rehash, 被调用后就会将整表 rehash 完之后再允许操作;
Redis 中的 dict 的 rehash 操作是渐进式 rehash, 渐进式 rehash 是指, 分多次将 hash 表中的元素进行 rehash;
Redis dict 使用渐进式 rehash 的好处是, 避免保存大量数据的的 dict 在 rehash 时使 Redis 一段时间内无法响应用户指令.
3. 渐进式 rehash 原理
Redis dict 结构体包含两个 hash 表, ht[0],ht[1], 其中 ht[0]指向优先被使用的 hash 表, ht[1]指向扩容用的 hash 表, rehash 使用 dict 结构体中的 rehashidx 属性辅助完成, rehashidx 属性指向哪个 slot, 每次就将 ht[0]的那个 slot 的元素移动到 ht[1]中, 然后自增 rehashidx, 直到遍历完整个 hash 表. 由于不是一次性完成 rehash,rehash 进行时可能穿插着查找等操作, 查找的过程是先从 ht[0]中查找, 若查找不到, 则在 ht[1]中查找元素.
Redis 的 rehash 包括了 lazy rehashing 和 active rehashing 两种方式
lazy rehashing: 在每次对 dict 进行操作的时候执行一个 slot 的 rehash
active rehashing: 每 100ms 里面使用 1ms 时间进行 rehash. 这种方式在 Redis 的事件循环, servercron 中有相应体现.
(欢迎加 qq:1363890602, 讨论 qq 群: 297572046, 备注: 编程艺术)
来源: https://www.cnblogs.com/coding-nerver-die/p/10869450.html