注明：《Redis设计与实现》的个人学习总结，这本书对redis的讲解清晰易懂，如果深入学习可以看看这本书。

前言

几个问题。

• Redis的五种数据类型分别是由什么数据结构实现的？
• Redis的字符串数据类型既可以存储字符串（比如“hello world”），又可以存储整数和浮点数（比如10086和3.14），甚至是二 进制位（使用SETBIT等命令），Redis在内部是怎样存储这些值的？
• Redis的一部分命令只能对特定数据类型执行（比如APPEND只能 对字符串执行，HSET只能对哈希表执行），而另一部分命令却可以对 所有数据类型执行（比如DEL、TYPE和EXPIRE），不同的命令在执行 时是如何进行类型检查的？Redis在内部是否实现了一个类型系统？
• Redis的数据库是怎样存储各种不同数据类型的键值对的？数据库 里面的过期键又是怎样实现自动删除的？
• 除了数据库之外，Redis还拥有发布与订阅、脚本、事务等特性， 这些特性又是如何实现的？
• Redis使用什么模型或者模式来处理客户端的命令请求？一条命令 请求从发送到返回需要经过什么步骤？

第1章：引言

• 介绍了书本的整体结构由这几部分组成“数据结构与对象”、“单机数据库的实现”、“多机数据库的 实现”、“独立功能的实现”四个部分组成。
• 数据库的键值对就是一个对象

第2章 简单动态字符串

• redis没有使用c语言的字符，而是使用了自己定义的SDS(simple dynamic string)简单动态字符串
• c语言字符仅仅只作为字面量

SET msg "hello world"

• 对于上面的语句，key=msg这个msg是一个字符串对象，这个对象的底层就是SDS进行保存的，对于value=hello world也是同样的逻辑保存。

RPUSH fruits "apple" "banana" "cherry"

• 这里的fruits就是一个SDS对象，而且后面的3个列表值都是使用3个SDS进行保存的。

2.1 SDS的定义

那么为什么会使用SDS而不是直接使用c语言的字符？

struct sdshdr {//记录buf数组中已使用字节的数量//等于SDS所保存字符串的长度int len;//记录buf数组中未使用字节的数量int free;//字节数组，用于保存字符串char buf[];};

• free是0说明SDS已经没有任何分配空间了

• len说明SDS保存一个5个字节长的字符串。

• buf就是一个char数组,保存前5个字节的字符，最后一个字符串是’/0’

• sds的/0结尾是通过sds函数处理，方便调用c语言的函数。比如printf("%s", s->buf)；

• 上面是包含5个字节未使用空间的sds

2.2 SDS与C字符串的区别

• 下面这个就是传统的c语言字符串的保存方式
• 不能满足安全性、效率和功能的要求。

2.2.1 常数复杂度获取字符串长度

• c语言字符串没有存储数组的长度导致每次都需要去计算字符串的长度，时间复杂度是n
• 但是sds只需要时间复杂度1，而且sds的长度更新可以通过sds的内部函数自动完成拓展和处理，不需要我们手动处理。

也就是说c语言的字符串获取长度时间复杂度高，但是sds结构可以解决这个问题

2.2.2 杜绝缓冲区溢出

• 对于c语言的字符串来说不记录长度如果字符串太长就会导致溢出。

• string.h/strcat函数可以帮助把旧的字符串迁移到新的长度的字符串完成长度上的更新。

• 下面这个案例的意思就是s1和s2内存上紧挨在一起，这个时候需要把 Cluster合并到s1，但是由于s1没有分配足够空间，导致cluster覆盖了s2的字符串。

strcat(s1, " Cluster");

• 但是对于sds来说每次调用api，优先检查sds的一个空间是否足够，不足够就调用sds拓展空间，然后再调用合并字符串。
• sdscat(s, " Cluster");这个是sds的拼接字符串操作，先判断空间够不够，然后拓展之后再拼接

2.2.3 减少修改字符串时带来的内存重分配次数

• 对于c语言的字符串拓展，每次都需要重新分配新的大小数组。
  • 每次如果需要增长字符串就需要重新分配字符数组
  • 如果要缩短，那么也要重新分配释放内存防止内存泄露

strcat(s, " Cluster");//s=Redis

• 对于上面的的字符串，需要进行拓展空间操作也就是重新分配内存

strcat(s, " Tutorial");//s=Redis Cluster

• 由于分配内存是一个系统调用，如果是对于增长字符串很多的程序，那么执行速度可能非常慢
  • 修改字符串长度不常见，偶尔一次没问题
  • redis对速度要求高，如果频繁修改就会导致性能被拉低
• 所以SDS通过free来进行空间预分配和惰性空间释放

1.空间预分配

• 对sds进行拓展不仅仅只是长度，而且还会预分配一些空间
• 未使用空间分配数量
  • 长度小于1MB那么预分配和len一样，也就是free=len
  • 如果大于1MB那么每次预分配空间就是1MB。
• 所以SDS可以减少内存重新分配的次数。

2.惰性空间释放

• 对于下面的移除操作，实际上是不会直接释放内存的，防止后面需要增长字符串。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UukUwins-1637070235390)(C:/Users/11914/AppData/Roaming/Typora/typora-user-images/image-20211116123133740.png)]

sdstrim(s, "XY"); //移除SDS字符串中的所有"X"和"Y"

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J1rXMBxY-1637070235391)(C:/Users/11914/AppData/Roaming/Typora/typora-user-images/image-20211116123145031.png)]

2.2.4 二进制安全

• 对于c语言的字符串数组来说如果遇到/0空字符那么就会停止扫描。后面的字符串就会被忽略，所以这样的存储是无法存储视频、图片
• 对于sds的api来说字符串数组被叫做字节数组的原因就是因为它处理字符串数组是通过二进制方式来进行处理，也就是写入是什么，读出来就是什么。而不会截断。这个c的函数处理方式是不一样的。也就是说sds实际上保存的是二进制数据。
• 所以对于sds来说空字符不是判断字符串的结束。

2.2.5 兼容部分C字符串函数

• sds使用空字符的原因就是为了兼容c语言的函数，比如string.h库的函数

• string.h/strcasecmp函数用来对比sds和c语言字符串，那么就不需要redis自己写一个新的函数

strcasecmp(sds->buf, "hello world");

• strcat(c_string, sds->buf);也可以把sds的字符串送到一个c语言的字符串数组上

2.2.6 总结

2.3 SDS API

2.4 重点回顾

sds优点

• 常数复杂度获取字符串长度，直接有一个len进行记录
• 杜绝缓冲区溢出，这种防止通过sds的api可以对sds的长度进行一个判断
• 保存更多格式的数据，二进制格式保存防止c语言字符串空字符直接结束字符串。写入什么读出的就是什么
• 减少重分配，通过惰性空闲释放和预分配
• 兼容部分c语言的函数，所以这就是为什么sds每个字符串结尾都需要加上/0。

第3章 链表

• 下面代码的integers的列表键底层就是链表。

redis> LLEN integers(integer) 1024redis> LRANGE integers 0 101)"1"2)"2"3)"3"4)"4"5)"5"6)"6"7)"7"8)"8"9)"9"10)"10"11)"11"

3.1 链表和链表节点的实现

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

• 上面的代码其实就组成了一个双端链表结构
• adlist.h/list来持有链表操作会更方便

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;

• list结构提供头尾指针，而且提供链表长度和一些函数
  • dup函数：复制链表节点保存的值
  • free函数：释放链表节点保存的值
  • match函数：用于对比链表节点保存的值和输入值是否相等

redis链表的特性

• 双端
• 无环
• 带头尾指针
• 带链表长度计数器
• 多态

3.2 链表和链表节点的API

3.3 重点回顾

• 链表实现功能，列表键，发布和订阅，慢查询和监视器
• 链表由多个listNode组成，有list结构管理。

第4章 字典

• 字典被称为符号表、关联数组、映射、保存键值对的数据结构
• 字典的键都是独一无二的，可以通过键查找对应的值
• redis数据库的增删改都是建立在对字典的操作之上

SET msg "hello world"

• 这里 msg和hello world就是保存在字典上面的。
• 如果哈希键的键值对很多的时候底层就会使用到字典。
• 比如website是一个包含10086个键值对的哈希键，键是数据库名，值是网站名称。

redis> HLEN website(integer) 10086redis> HGETALL website1)"Redis"2)"Redis.io"3)"MariaDB"4)"MariaDB.org"5)"MongoDB"6)"MongoDB.org"# ...

4.1 字典的实现

• 字典使用哈希表作为底层实现，每个哈希节点就是对应一个键值对。

4.1.1 哈希表

typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码，用于计算索引值//总是等于size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;} dictht;

• table是一个dict.h/dictEntry数组。包含很多个dict.h/dictEntry节点。每个dicEntry都保存着一个键值对。
• size记录了哈希表的大小
• used说明哈希表现在有的节点的多少。
• sizemask=size-1这个属性和哈希值决定键应该被放到哪一个位置。

4.1.2 哈希表节点

typedef struct dictEntry {//键void *key;//值union{void *val;uint64_tu64;int64_ts64;} v;//指向下个哈希表节点，形成链表struct dictEntry *next;} dictEntry;

• dictEntry保存着一个键值对
• next指向另一个哈希节点的指针。可以把多个哈希值相同的键值对连接在一起。解决哈希冲突

4.1.3 字典

typedef struct dict {//类型特定函数dictType *type;//私有数据void *privdata;//哈希表dictht ht[2];// rehash索引//当rehash不在进行时，值为-1in trehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;

• type和privdata属性针对不同类型的键值对。为了创建多态字典。
  • type指向dictType，dictType保存操作不同类型键值对的函数。不同类型的字典使用不同的函数类型。
  • privdata保存传给特定类型函数的参数。

typedef struct dictType {//计算哈希值的函数unsigned int (*hashFunction)(const void *key);//复制键的函数void *(*keyDup)(void *privdata, const void *key);//复制值的函数void *(*valDup)(void *privdata, const void *obj);//对比键的函数int (*keyCompare)(void *privdata, const void *key1, const void *key2);//销毁键的函数void (*keyDestructor)(void *privdata, void *key);//销毁值的函数void (*valDestructor)(void *privdata, void *obj);} dictType;

• ht两个项都是dictht哈希表，通常只会是调用ht[0],ht[1]用于对ht[0]rehash使用的。

• rehashidx记录rehash进度。如果没有rehash那么就是-1。

• 下面这个就是普通状态下的字典。

4.2 哈希算法

• 在加入新的键值对之前，需要对键计算出哈希值和索引值才能够放入到哈希表。

#使用字典设置的哈希函数，计算键key的哈希值hash = dict->type->hashFunction(key);#使用哈希表的sizemask属性和哈希值，计算出索引值#根据情况不同，ht[x]可以是ht[0]或者ht[1]index = hash & dict->ht[x].sizemask;

• 可以通过dictType的hashFunction计算出hash，然后hash和mask进行一个相与获取索引的值。

• 比如现在加入一个键值对。按照上面的计算方式

• 如果字典被用作数据库底层实现或者是哈希底层实现，redis会使用murmurhash算法计算哈希值，这种算法好处就是给的键如果有规律那么就能做到很好的随机分布，计算速度也很快

4.3 解决键冲突

• redis使用链地址法解决hash冲突。

4.4 rehash

• 键值对增加，导致哈希因子也在上升，也就是哈希表的已用大小和哈希表大小的比值，这个时候就需要进行扩容。

• 可以通过rehash重新散列进行扩容。

  • ht[1]重新分配空间ht[1]的大小就是第一个大于等于ht[0].used*2的2^n
  • 如果是收缩也是ht[1]的大小第一个大于等于ht[0].used的2^n

• 把ht[0]的键值对rehash到ht[1]中。

• 转移之后释放ht[0]将ht[1]设置为ht[0],为下一次rehash做准备

• 可以看看下面的扩容used原本是4，现在扩容到used*2的第一个2^n也就是8。

哈希表的扩展与收缩

满足一下条件就要执行拓展

• 服务器没有执行bgsave或者bgrewriteaof，而且负载因子大于等于1
• 服务器执行BGSAVE命令或者BGREWRITEAOF命令，而且负载因子大于等于5.

负载因子的计算公式。

负载因子=哈希表已保存节点数量/哈希表大小load_factor = ht[0].used / ht[0].size

• 根据BGSAVE命令或BGREWRITEAOF命令是否正在执行，执行拓展的判断负载因子不同，redis需要创建服务器的子进程，这个时候服务器需要提高拓展操作所需的负载因子。避免子进程操作的同时进行rehash。避免不必要的内存写入。

4.5 渐进式rehash

• rehash不是一次性完成，而是分多次，渐进式的
• 现在键值对少所以移动快，但是如果数据量很大的时候，那么移动就会导致整个服务器停止
• 渐进式的逻辑

1. 给ht[1]分配空间
2. 维护一个reindex，初始值是0
3. 在rehash期间，对字典的查找，增删改一个同时仍然需要把节点移动到ht[1]，移动之后reindex+1
4. 所有键值对移动完之后，reindexid设置为-1。表示已经完成。

• 下面就是整个rehash的过程。

渐进式rehash执行期间的哈希表操作

• 如果执行查找，优先在ht[0]中查找，然后再去ht[1]查找
• 新增全部都到ht[1]中插入

4.6 字典API

4.7 重点回顾

• 字典可以实现哈希键和数据库
• 字典的底层就是哈希表
• 通常使用murmurhash2算法来计算数据库的hash值
• 对于rehash操作是一个渐进式的操作

第5章 跳跃表

• 跳跃表是有序数据结构，每个节点维持跳跃到多个节点的指针，能够快速访问节点。
• 支持logn和n复杂度的节点查找。
• 和平衡树媲美而且操作更简单。
• redis使用跳跃表作为有序集合键底层实现之一。
• 比如fruit-price是一个有序集合键

redis> ZRANGE fruit-price 0 2 WITHSCORES1)"banana"2)"5"3)"cherry"4)"6.5"5)"apple"6)"8"redis> ZCARD fruit-price(integer)130

• 有序集合所有数据都放到一个跳跃表，每个节点都保存了水果的价格信息。从低到高进行排序
• 跳跃表应用
  • 有序集合键
  • 集群节点用作内部数据结构

5.1 跳跃表的实现

• 跳跃表通过redis.h/zskiplistNode和redis.h/zskiplist两个结构定义。
  • zskiplistNode跳跃表节点
  • zskiplist跳跃表节点的相关信息。节点数量，表头和表尾。

• 最左边就是zskiplist结构
  • header头结点
  • tail：跳跃表表尾节点
  • level：层数最大的那个节点的层数
  • length：跳跃表的长度。表头节点不算。
• 右边是四个zskiplistNode结构
  • level：L1、L2、L3标记节点的各个层。每个层带有前进节点和跨度。
    • 前进指针：访问位于表尾方向的其它节点
    • 跨度：记录前进指向节点和当前节点的距离。
  • 访问的时候就会沿着前进指针方向前进
  • 后退（backward）指针：bw指向前一个节点
  • 分值（score）：节点按照分值进行排序，比如1，2,3
  • 成员对象（obj）：o1和o2这些就是对象

5.1.1 跳跃表节点

typedef struct zskiplistNode {//层struct zskiplistLevel {//前进指针struct zskiplistNode *forward;//跨度unsigned int span;} level[];//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj;} zskiplistNode;

1.层

• 跳跃表节点和level数组可以包含多个元素。每个元素包含指向其他节点的指针，程序可以通过这些层快速访问其他节点。层多访问节点越快。
• 每次创建一个节点的时候根据幂次定律（越大的数出现概率越小），随机生成1-32作为level的大小。就是层的高度。

2.前进指针

• 表头向表尾方向指向的指针。访问其他节点。虚线是从表头访问到表尾的路径

1. 访问表头，从第4层前进指针找到第二个节点
2. 然后找到第二个节点的第二层前进指针找到第三个节点
3. 第三个节点的第二层指针找到第四个节点
4. 最后就是null

3.跨度

• 记录两个节点的距离。

• 指向null那么就是0

• 跨度用于计算排位的。查找某个节点走过的所有层跨度就是目标节点在跳跃表的排位。

• 比如找o3，这个时候只是通过第一个节点L5到最后一个节点的L5而且跨度是3。所以目标节点排位也是3。

• 现在如果要找o2而且得分是2的相当于就是走了2个跨度，所以目标节点的排序是2.

4.后退指针

• 后退指针只有一个所以每次只能后退到前一个节点

5.分值和成员

• 分值是一个double的浮点数。节点都是按照分值从小到大进行的排序。
• 节点的成员对象（obj属性）是一个指针，指向字符串对象，这个对象保存着一个sds。
• 保存的对象一定要唯一。
• 分值相同按照字典成员对象的大小进行排序。

5.1.2 跳跃表

• header和tail指向表头和表尾
• length能够在时间复杂度是1的情况下获取
• level最高层数

typedef struct zskiplist {//表头节点和表尾节点structz skiplistNode *header, *tail;//表中节点的数量unsigned long length;//表中层数最大的节点的层数int level;} zskiplist;

5.2 跳跃表API

5.3 重点回顾

• 跳跃表是有序集合的底层实现之一
  • 通过zskiplist和zskiplistNode两个结构组成
  • 层高是1-32之间
  • 可以有多个分值相同的点，但是节点对象一定是唯一的
  • 按照分值排序，如果分值相同那么就是按照对象在字典的大小排序。