一. 引言
《Redis 设计与实现》一书主要分为四个部分, 其中第一个部分主要讲的是 Redis 的底层数据结构与对象的相关知识.
Redis 是一种基于 C 语言编写的非关系型数据库, 它的五种基本对象类型分别为: STRING,LIST,SET,HASH,ZSET. 然而, 对于每一种基本对象数据类型, 底层都至少有 2 种不同的实现方式.
二. 简单动态字符串(Simple Dynamic String, SDS)
SDS 是 Redis 的默认字符串表示, 包含字符串值的键值对底层都是由 SDS 实现的. 除了保存数据库中的字符串值之外, SDS 还被用作缓冲区.
示例:
- Redis>SET msg "hello world"
- OK
当执行上述代码之后, Redis 会创建一个 STRING 类型的键值对, 其中键和值均是一个字符串对象, 键对象的底层是一个保存着字符串 "msg" 的 SDS, 而值对象的底层是一个保存着字符串 "hello world" 的 SDS.
每个 SDS 都结构如下所示:
- struct sdshdr{
- // 记录 buf 数组中已使用的字节数量(也是 SDS 所保存的字符串长度)
- int len;
- //buf 数组中未使用的字节数量
- int free;
- // 字节数组, 用于存储字符串
- char buf[];
- };
如上图所示, SDS 遵循 C 字符串以空字符结尾的惯例, 但是保存空字符的一字节空间不计算在 SDS 的 len 属性中. 即对于 SDS 的结构满足: buf 的长度 = len + free + 1. 即当 SDS 的 len=5,free=0 字节时, 则 buf 的长度为 5+0+1=6 字节.
C 字符串本身的两个问题有: 1. 获取字符串长度的复杂度高 2. 由于 C 字符串不记录自身长度容易造成缓冲区溢出等问题. C 字符串修改字符串时会有大量的内存重分配操作, 如拼接字符串时, 如果不进行内存重分配, 可能会造成缓冲区溢出; 进行缩短字符串操作时, 不进行内存重分配释放不再使用的那部分空间, 则会产生内存泄露.
为了解决上述两个问题, SDS 做了一系列的改进操作.
(1)由于 SDS 将字符串的长度存储在 len 属性中, 所以 SDS 获取字符串长度的时间复杂度为 O(1).
(2)SDS 通过设计两种空间分配策略来减少字符串修改时带来的内存重分配次数, 同时杜绝了缓冲区溢出的可能性.
SDS 的两种空间分配优化策略:
SDS 的优化策略是通过未使用空间 (即 free 标记的空间) 实现的
(1)空间预分配: 用于优化 SDS 字符串增长操作. 当 SDS 的 API 对 SDS 进行修改并且需要进行空间扩展时, 程序不仅会为 SDS 分配修改所必要的空间, 还会为 SDS 分配额外的未使用空间. 其中主要分为两点: 当 len<1MB 时, 程序分配和 len 同样大小的未使用空间, 即 free=len; 当 len>=1MB 时, free=1MB.
(2)惰性空间释放: 用于优化 SDS 的字符串缩短操作. 当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序不会马上使用内存重分配来回收缩短后多出来的空间, 而是使用 free 属性将这些字节的数量记录起来, 以供将来使用.(缩短重分配操作, 并未将来可能有的增长操作进行了优化).
三. 链表
Redis 中链表可以用来实现列表键, 发布与订阅, 慢查询, 监视器等功能.
链表由两种结构组成, 分别是 list 结构和 listNode 结构, 它们的表示如下所示:
- typedef struct list{
- listNode *head;// 指向表头
- listNode *tail;// 指向表尾
- unsigned long len;// 节点数
- void *(*dup)(void *ptr)
- void *(*free)(void *ptr)
- int (*match)(void *ptr, void *key)
- }list;
- typedef struct listNode{
- struct listNode *prev;// 前置节点
- struct listNode *next;// 后置节点
- void *value;// 节点值
- }listNode;
根据代码可以知道, list 结构拥有一个指向链表表头和一个指向链表表尾的指针, 而 listNode 中有一个前置指针和后置指针, 因此, 链表获得头, 尾节点的时间复杂度为 O(1), 且可以从任意一端开始遍历. 此外, list 中还存有 len 属性保存链表长度, 因此获得链表长度的时间复杂度仅为 O(1).
四. 字典
Redis 中字典可用于实现数据库和哈希键等.
字典使用哈希表作为底层实现, 哈希表 dictht 和哈希表节点 dictEntry 结构如下所示:
- typedef struct dictht{
- disctEntry **table;// 哈希表数组
- unsigned long size;// 哈希表大小
- unsigned long sizemask;// 哈希表大小掩码, 为 size-1, 用于计算索引值
- unsigned long used;// 已有节点数
- } dictht;
- typedef struct dictEntry{
- void *key;// 键
- union{// 值
- void *val;
- unint64_t u64;
- int64_t s64;
- } v;
- struct dicEntry *next;// 指向下个哈希表节点
- } dictEntry;
由结构代码和图可知, dictht 结构中 size 属性为哈希表的总大小, used 为哈希表节点个数; dictEntry 节点中存储了键值对和指向下一个节点的指针. 而 dictht 中 sizemask 属性总等于 size-1, 该属性值用于哈希算法.
字典结构则如下所示:
- typedef struct dict{
- dictType *type;// 类型特定函数
- void *privdata;// 私有数据
- dictht ht[2];// 两个哈希表
- int rehashidx;// 用于标记是否处于 rehash 状态
- } dict;
字典由 dict 结构表示, 其属性 type 是指向 dictType 结构的指针, 该结构中保存了一簇用于操作特定类型键值对的函数; privdata 属性则保存了需要传给这些函数的可选参数; rehashIdx 则用于标记当前字典是否处于 rehash(重新哈希)状态, rehashidx=-1 时未进行 rehash.(图示中略有错误, 解决冲突时, 链地址法是将新节点插入头部, 即头插法, 所以应当 k2 在前, k1 在后)
字典的哈希算法: 每当一个新键值对添加到字典中时, 程序需要先根据键计算出哈希值和索引值, 再根据索引值将包含键值对的哈希节点放到哈希表数组的指定位置. 哈希值使用字典的 type 中存储的哈希函数 (hashFunction) 计算 (当字典被用作数据库或哈希键(HASH-key) 的底层实现时, Redis 使用 MurmurHash2 算法), 而索引值则根据哈希表的 sizemask 和哈希值计算, index = 哈希值 & sizemask. 例, 新增键的哈希值为 8, 则上图新增键在 ht[0]索引值为 8 & 3 = 0.
处理键冲突: Redis 的哈希表采用链地址法解决键冲突的问题, 且为了速度考虑, 每次都是将新节点添加到链表的表头位置(复杂度为 O(1)).
哈希表的扩展与收缩: 负载因子 load_factor = ht[0].used / ht[0].size
(1)当服务器未执行 BGSAVE 命令或者 BGREWRITEAOF 命令时, 且哈希表的负载因子大于等于 1 时, 自动扩展.
(2)当服务器正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令时, 且哈希表的负载因子大于等于 5 时, 自动扩展.
(3)当哈希表的负载因子小于 0.1 时, 程序对哈希表自动收缩.
之所以有 (1),(2) 的区别, 是因为在执行这些命令的过程中, Reis 需要创建当前服务器进程的子进程, 而大多数操作系统都采用写时复制技术来优化紫禁城的使用效率; 因此, 子进程存在期间, 服务器会提高进行扩展操作所需的负载因子, 尽可能避免子进程存在期间进行哈希表扩张操作, 避免不必要的内存写入, 最大限度的节约内存.
渐进式 rehash: 当程序需要对哈希表的大小进行扩展或者收缩时, 需要通过 rehash 操作来完成.
(1)字典会为 ht[1]的哈希表分配空间 (扩展操作, ht[1] 大小为第一个大于等于 ht[0].used*2 的 2n; 收缩操作, 则 ht[1]大小为第一个大于等于 ht[0].used 的 2n).
(2)将保存在 ht[0]上的键值对 rehash 到 ht[1]上(即重新计算键的哈希值和索引值).
(3)当 ht[0]上的键值对全部迁移完毕后, 释放 ht[0], 并将 ht[1]设置 ht[0], 再创建一个空白哈希表作为 ht[1], 为下次 rehash 准备.
值得注意的是, rehash 操作并不是一次性集中完成的, 而是分多次, 渐进式的完成. 为了避免 rehas 对服务器性能造成影响, rehash 采取了分而治之的方式, 将 rehash 键值对所需的计算工作平摊到对字典的添加, 删除, 查找和更新操作上, 从而避免集中式 rehash 带来了庞大计算量.
五. 跳跃表
跳跃表是有序集合键的底层实现之一, 它的结构由 zskiplist 和 zskiplistNode 组成, 其结构和代码如下图所示
- typedef struct zskiplistNode{
- struct zskiplistNode *backward;// 后退指针
- double score;// 分值
- robj *obj;// 成员对象
- struct zskiplistLevel {
- struct zskiplistNode *forward;// 前进指针
- unsigned int span;// 跨度
- }
- } zskiplistNode;
zskiplist 保存跳跃表信息, header 指向表头节点, tail 指向表尾节点, level 为跳跃表中的最大层数(表头节点层数不算在内),length 为跳跃表长度(不包含表头节点).
zskiplistNode 为跳跃表节点, level 数组中可以包含多个元素分为多个层 (每个跳跃表层高都是 1~32 之间的整数), 每个层都有一个 forward 前进指针(用于表头向表尾方向访问) 和一个 span 跨度(用于记录两个节点之间的距离以及记录排位的, 所有指向 NULL 的前进指针跨度都为 0);backward 指针用于从表尾向表头方向遍历时使用(每次只能后退一个节点);score 分值是一个 double 类型的浮点数, 跳跃表中节点都按分值从小到大排序; obj 属性是一个指向字符串对象的指针, 而字符串对象保存着一个 SDS 值.
同一个跳跃表中, 多个节点可以包含相同的分值, 但每个节点的成员对象必须是唯一的.
跳跃表中的节点按照分值大小顺序排列, 当分值相同时, 按照成员对象的大小排列.
六. 整数集合
整数集合时 Redis 中用于保存整数值的集合抽象数据结构, 其结构代码和图示如下所示:
- typedef struct intset{
- uint32_t encoding;// 编码方式
- uint32_t length;// 集合包含的元素数量
- int8_t contents;// 保存元素的数组
- } intset;
其中, encoding 为 intset 的编码方式, length 存储元素的数量, contents 数组是整数集合的底层实现, 其内的元素按从小到大的方式保存. contents 数组的真正类型取决于 encoding 的值.
整数集合的升级操作: 每当一个类型比整数集合现有所有元素的类型都要长的新元素添加到整数集合中时, 整数集合都需要先进行升级操作.
(1)根据新元素的类型, 扩展整数集合底层数组的空间大小, 并未新元素分配空间.
(2)将原来元素转换为新元素相同的类型, 并从后往前依次放置原来的元素(放置过程中需位置底层数组的有序性质不变)
(3)将新元素添加到底层数组中
从上可知, 向整数集合添加新元素的时间复杂度为 O(n).
升级的好处:
(1)通过自动升级来使用不同类型元素的数组, 提升了整数集合的灵活性
(2)尽可能节省内存.(如组织有在将 int32_t 类型存入时, 原来的 int16_t 类型数组才会转换, 不需要预先设定好)
七. 压缩列表
压缩列表式列表建和哈希键的底层实现之一, 是 Redis 为了节约内存而开发的, 是一系列特殊编码的连续内存块组成的顺序型数据结构. 其结构如下所示:
zlbytes 表示压缩列表总长度, zltail 表示偏移量(用于记录气质地址到表尾节点的距离有多少字节),zllen 为压缩列表节点个数, entry 等都是压缩列表的节点, zlend 用于标记压缩链表末端. 而压缩列表节点中, previous_entry_length 表示前一个节点长度(该属性长度可以是 1 字节或者 5 字节),encoding 表示 content 属性保存的数据类型与长度, content 负责保存节点值.
如果前一个节点长度小于 254 字节, previous_entry_length 长度为 1 字节; 如果前一个节点长度大于等于 254 字节, previous_entry_length 长度为 5 字节, 后面 4 个字节保存前一个节点长度, 第一个字节的值被设置为 0x05.
压缩列表从表尾向表头的遍历就是基于 previous_entry_length 属性实现的(先要获得起始地址, 再根据 zltail 获得指向表尾节点的指针, 然后 previous_entry_length 属性计算出前一个节点的地址, 便可依次从后往前遍历).
由于 previous_entry_length 属性记录前一个节点的长度, 且该属性的长度由前一个节点的长度决定, 因此在某些特殊情况下, 删除或者增加节点可能会造成连锁更新(即特殊情况下产生的连续多次空间扩展操作). 例如, 原来压缩列表节点长度都小于 254(确切的说是 250~253 之间), 此时将一个长度大于 254 的节点放到他们之前, 便会引起后一个节点 previous_entry_length 的长度变化, 从而使后一个节点长度大于等于 254, 依次类推, 就想多米诺骨牌一样造成连锁反应. 删除节点时的特殊情况则刚好相反.
连锁更新在最坏情况下复杂度为 O(N2), 但真正造成这种情况出现的操作并不多见.
来源: https://www.cnblogs.com/xiang9286/p/10847762.html