Redis设计与实现总结

本文总结自《Redis设计与实现》一书，只打算总结Redis底层数据结构的实现。Redis的使用参考我的另一篇笔记Redis操作指南。

1 Redis概览

Redis是一个C语言编写的开源、非关系型内存数据库。它底层属于单线程、全内存操作，提供对象共享、引用计数和对象回收功能。它通过SDS(简单动态字符串)、链表、字典、跳跃表、整数集合和压缩表这几种简单数据结构，实现了五种对象:String、List、Set、ZSet、Hash。和对象同级别的数据结构和功能包括：计数统计、地理空间、发布订阅和bitMap操作。上层，Redis提供事务、主从复制、脚本、LRU驱动事件功能。高可用方面，Redis可以搭建集群，哨兵+自动选举机制保障，可以持久化、故障转移。
在这里插入图片描述

2 Redis数据结构

2.1 SDS

SDS简单动态字符串，这个名词区别于C语言中的字符串。C字符串以\0结尾，SDS不用，它的结构中有记录字符串长度和剩余空间长度的字段，buf指向真正保存字符的数组起始位置。
在这里插入图片描述

2.2 链表

Redis使用的是双向链表，由List和ListNode(节点)构成，值存储在节点下。
在这里插入图片描述

2.3 字典

字典的ht数组指向哈希表，type保存了指向各种函数的指针，rehashindex ！= -1时表明字典正在做reHash操作。哈希表指向一个entry数组，里面保存了NULL或者entry，根据负载因子决定是否扩容并重算哈希值。entry保存了键值对和指向下一个entry的指针next，当有两个以上entry的哈希值相同时，entry通过next指针连接成一条链来解决哈希冲突（拉链法）。可以看到它的实现和Java中的HashMap实现非常相似，不过JDK8以上的HashMap不再需要重算哈希，而且entry链长达到8以后会转换成红黑树提高查询效率。
在这里插入图片描述

2.4 跳跃表

一种类似链表的结构。链表的查询必须不断查询next，每次只能跳过一个节点，而跳跃表的next在不同的层可以跳过多个节点，它的查询可从高层向底层二分查找，直到找到需要的节点。节点中的BW指向前一个节点，score值必须从小到大，value存储节点值。每一层保存跨度和指向下一个节点的指针。跨度用来计算节点的Ranke(排位)，例如下图标节点[3]，从头结点L3开始累加跨度:1+2=3，得出标节点[3]排第三。
在这里插入图片描述

2.5 整数集合

存储了整数数组信息的数据结构。为了节省空间，它可以自动升级16->32->64bit，但是不能降级。它存储的元素都是升序排列且没有重复元素的。
在这里插入图片描述

2.6 压缩列表

压缩列表是由特殊编码的连续内存块组成的顺序型数据结构，为节约内存而生。它的entry数量不定，可根据实际情况增减。encoding代表content里面是字节数组还是整数值，还存储了content的长度。
在这里插入图片描述

3 Redis对象

Redis的对象把类型和底层数据结构做了抽象，对象的类型和具体数据结构通过常量/指针的方式来决定。一个存储类型的属性(type)，一个存储编码方式(encoding，也就是底层数据结构类型 ) 的属性，一个指向底层数据开始位置的指针(ptr)，一个保存最后访问时间的指针(lru)和一个引用计数（redcount，用于对象共享和对象回收）。Redis的基本数据结构撑起了Redis的五种数据类型(对象)：String、List、Set、ZSet、Hash。
在这里插入图片描述
类型和编码对照表

4 Redis数据库

Redis数据库大框架主要是由RedisServer、RedisClient、RedisDB三个结构体撑起来的。RedisServer记录RedisDB的数量和位置，RedisClient记录当前客户端连接指向的RedisDB，RedisDB则存储字典，字典中存储字符串值和5种类型的对象，这就把前面的基本数据结构、5种对象串了起来。下图完美的展示了这幅逻辑视图。
在这里插入图片描述

5 一些功能特性的原理

5.1 键空间

Redis数据库的 *dict 字典数组保存了所有的键值对，这个字典称为键空间，键空间的键就是数据库的键，键空间的值就是数据库的值，对数据库键值对的所有操作都是在键空间上的操作。

5.2 过期字典

过期字典保存了所有键的过期时间，它首先是一个字典，它的键是一个指针，值是long类型的毫秒精度UNIX时间戳(为了简洁，下图的key-value没有按照真实的字典来画)。
在这里插入图片描述

5.3 过期删除策略

定时删除：设置键过期时间的同时创建定时器，由定时器定时删除。
惰性删除：获取键的时候判断是否过期，过期则删除，否则返回查询结果。
定期删除：每隔一段时间就遍历检查一遍，删除已过期键，保留未过期键，每遍不一定全部删除。
Redis采用惰性删除和定期删除，提高单线程的效率。

5.4 持久化

先说一下RDB和AOF的恢复逻辑，服务器启动后会检查AOF持久化功能是否开启，若开启则载入AOF文件，否则载入RDB文件：
在这里插入图片描述

5.4.1 RDB

持久化：可以用save命令手动执行持久化，也可以在redis.conf配置文件设置多条自动持久化条件“save m n ”，意思是在m秒内执行了n次更新就触发RDB。持久化产生的文件后缀是 .rdb，默认在Redis根目录。RDB文件结构：
在这里插入图片描述
恢复：RDB的恢复在Redis重启后自动执行。

5.4.2 AOF

持久化：类似MySQL的binlog，保存客户端命令实现持久化，会追加客户端命令到一个缓冲区然后按某种策略保存到磁盘文件。AOF重写类似把MySQL数据备份成insert语句组成的文件，redis会fork一个子线程，然后根据当前数据库状态生成尽量少的命令保存到文件。
恢复：创建一个不带网络功能的伪客户端，从AOF文件循环读取命令并执行。

5.5 文件事件和时间事件

Redis的文件事件是指网络事件，Redis的事件处理是单线程，它采用IO多路复用来管理客户端连接，然后用事件分派器把就绪事件分发到不同的事件处理器，事件分派和处理在同一条线程中，其事件模型结构如下：
在这里插入图片描述
Redis的时间事件放在一个无序链表中，每当时间事件执行器运行就会遍历检查，执行已到期的事件。

时间事件和文件事件的处理也是在同一条线程中，它的逻辑如下：

def aeProcessEvents(){获取将会最先到期的时间事件；计算该事件是否已到期；if (未到期) {阻塞接收文件事件直到上述事件到期；} else {接收文件事件，立马返回，不阻塞；}处理所有文件事件；处理所有时间事件；}

5.6 Redis常见拓扑关系

下面介绍的几种拓扑结构其配置均不相同，特别是主从模式与集群模式，集群模式也有主从配置，然而配置方式与主从模式完全不同，博主也是踩了不少坑，而且搜遍网络竟然发现没有一篇文章能够讲清楚。Redis的高可用提供了自动故障恢复(failover)功能，很多文章把主从模式配置讲的细之又细，却断然不做故障恢复测试，又或者通篇都在讲故障恢复的理论却一字不提如何配置。下面的配置基于Windows，博主已经准备好一个windows版的集群配置，可以在这里下载，主从模式稍加修改就可以测试。

5.1 单机单点模式

这种模式下只有一个Redis服务节点，特点是管理简单，但是相对容易出现单点故障。

5.2 主从模式（+哨兵模式）

主从模式下，可以任意多主多从配置，要求是每个主节点可以有大于等于0个从节点，一个从节点只能有一个主节点。主从模式的目的是为了高可用，Redis的故障恢复(failover)有手动和自动两种方式，标题把哨兵模式括起来就是告诉大家，哨兵模式是可选方案而不是必备方案。但是有自动的情况下没有理由用手动来保证高可用，所以用主从的情况下几乎必用哨兵模式。下面开始配置（主：7000，从：7003 7004，哨兵：7006 7007）：

# master   redis.windows.conf配置文件：
port 7000

# 两个slave  redis.windows.conf配置文件分别：
port 7003    
slaveof 127.0.0.1 7003  port 7004    
slaveof 127.0.0.1 7004

# 两个哨兵(sentinel)，新建text，配置如下后改成.conf
#当前Sentinel服务运行的端口，另一个改成7007
port 7006
#只有一个 Sentinel进程将实例标记为主观下线并不一定会引起实例的自动故障迁移：只有在足够数量的Sentinel都将一个实例标记为主观下线之后，实例才会被标记为客观下线，这时自动故障迁移才会执行
sentinel myid db6466310f6b573d09842178d7a30520e2f2ad93
#Sentinel去监视一个名为mymaster的主redis实例，这个主实例的IP地址为本机地址127.0.0.1，端口号为7000，只有一个 Sentinel进程将实例标记为主观下线并不一定会引起实例的自动故障迁移：只有在足够数量的Sentinel都将一个实例标记为主观下线之后，实例才会被标记为客观下线，这时自动故障迁移才会执行
sentinel monitor master 127.0.0.1 7000 2
#指定了在执行故障转移时，最多可以有多少个从Redis实例在同步新的主实例，在从Redis实例较多的情况下这个数字越小，同步的时间越长，完成故障转移所需的时间就越长
sentinel down-after-milliseconds master 5000
#如果在该时间（ms）内未能完成failover操作，则认为该failover失败
sentinel config-epoch master 30
# Generated by CONFIG REWRITE，改成你自己的随便哪个路径
dir "D:\\App\\Redis\\cmd"
sentinel leader-epoch master 30
protected-mode yes
bind 127.0.0.1
sentinel current-epoch 30

启动主从的命令可以放到新建.bat里面，注意路径改成你自己的：

title redis-7000
D:\App\Redis-3.2.100\redis-server D:\App\Redis\Redis-7000\redis.windows.conf

启动哨兵的命令：

title redis-7006
D:\App\Redis-3.2.100\redis-server D:\App\Redis\Redis-7006\sentinel.conf --sentinel

这时可以测试主从复制是否有效，可以关掉主服务器，观察哨的failover过程。
哨兵（Sentinel）是一个运行在特殊模式下的Redis实例，可以有多个哨兵实例，它们记录了主从节点信息，当主节点挂掉之后，哨兵们协商出一个领头哨兵，领头哨兵负责故障转移。
故障转移：领头哨兵负从挂掉节点的从服务器中选出一个作为新的主节点，若挂掉的主节点恢复，哨兵会把它安排为从节点，从新的主节点复制数据。
哨兵模式主观下线、客观下线：主观下线是指哨兵第一次发现某节点没有响应；客观下线是指发现主观下线的哨兵向其他哨兵询问，如果它们观测到的也是下线状态，那该节点就变成客观下线，进入故障转移流程。

5.3 集群模式

Redis集群采用无中心结构，集群中的组成部分：主节点、从节点。
Redis集群的槽是一个分片，一个Redis集群必须有16384个槽，每个主节点映射一部分槽（不要求平分），key-value插入时会用CRC16计算key的校验码，校验码%16384 =它应该保存的槽。
集群的主节点之间相互保存其它主节点的连接信息、槽信息，向集群中存取数据可以向任意一个主节点发送命令，如果数据不在自己的槽范围，请求会自动跳转到正确的节点。
注意：集群模式需要用Ruby脚本构建，请先安装好（下载地址）。集群模式自带failover，不需要哨兵。集群模式的主从配置完全一致，从库不需要什么slaveof配置（主：7000 7001 7002 从：7003 7004 7005）：

# 主从配置都一样：
port  7000
appendfilename "appendonly.7000.aof"  
cluster-enabled yes                                    
cluster-config-file nodes.7000.conf
cluster-node-timeout 15000
cluster-slave-validity-factor 10
cluster-migration-barrier 1
cluster-require-full-coverage yes

上面只是配置，构建集群需要Ruby环境+官网的redis-trib.rb脚本，用下面的命令构建脚本：

# 说明：--replicas表示集群模式下的主从配置，--replicas 1表示每个主1个从，这里3个master，就必须有3个slave，不能多不能少。
# 下面的主从对应关系是 M7000S7003，M7001S7004，M7002S7005
redis-trib.rb create --replicas 1 127.0.0.1:7000 127.0.0.1:7001 127.0.0.1:7002 127.0.0.1:7003 127.0.0.1:7004 127.0.0.1:7005

中途需要输入yes同意构建。完成之后用下面的命令检查集群情况：

# 可以向任意节点check集群状态
redis-trib.rb check 127.0.0.1:7001

在这里插入图片描述
这个时候我们可以测试主从复制情况：

#说明：必须带-c参数，否则7000这个控制台只处理自己的槽范围的命令，加上之后则可能会请求跳转到其它节点D:\App\Redis\Redis-7000\redis-cli -c -p 7000

也可以测试failover，停掉7000，7003会变成master，7000重启后变成slave。
故障转移：集群超过一半的master节点发现7000下线，会在集群广播一条7000下线的消息，这些master会从7000的从节点选择一个作为新的作为主节点(这里是7003)，7003接管原来7000的槽，7003上线后广播一条消息，新的主节点开始工作。（《Redis设计与实现第17章第6节》）。

6 总结

实际上Redis并非绝对的单线程，只不过它在接收用户命令、处理并响应时是单线程，RDB save命令、AOF重写时会fork出一个子线程协助处理，都属于多线程；另外我们可以看到Redis为了加快客户端响应速度做出的许多努力：多线程持久化、优先处理文件事件等。本文总结了Redis的底层数据结构和对象的实现，以及在此基础上的一些特性原理，没有总结更高层次事务实现、统计计数等功能，因为要从底层说清楚高层次的东西是很有挑战性的，完整总结出来可能会变成一本厚厚的资料书，希望本文能够用浅显的方式引领看官更深入的学习Redis底层原理。Redis的使用参考我的另一篇笔记Redis操作指南。