一. 数据结构

我们知道redis有5种基本类型：string、list、hash、set、zset，我们来看一下他们是怎么实现的。

1. 简单动态字符串（Simple Dynamic String，SDS）

Redis中的可变字符串都是由SDS实现，比如键值对的键和值，list的键和list中的字符串等...。

SDS结构

可以看到它由三部分组成：

• free（表示空闲字节数）
• len（表示字符串长度）
• buf（指向字符数组，存在占位符兼容C语言字符串，但它对用户、free、len不可见；并且buf中可能包含多余的空字节）

SDS的内存优化策略：
（1）空间预分配

• SDS只在free空间不够时，才进行扩容
• 扩容的SDS的长度小于1M时，分配的空间时len的2倍，如“redis”，会分配11个字节的buf（包含占位符）；
• SDS的长度大于1M时，每次多分配1M。

（2）惰性空间释放
SDS字符串变短时，并不马上缩短buf长度，而是通过free字段暂时保存着部分字节。

SDS的优点如下：

• 获取长度的复杂度为O(1)，适合于Redis高性能的场景
• 通过free字段，我们可以杜绝缓冲区溢出
• 减少字符串修改带来的内存重分配次数
• 可以存储二进制信息
• 兼容部分C字符串函数

2.链表

（1）在Redis中，链表应用于列表键、发布与订阅、慢查询、监视器。
（2）redis的list，是双向链表，且包含链表长度等信息。

3.字典

（1）在Redis中，字典使用时非常广泛的，Redis数据库的底层就是使用字典实现；字典也是hash、set的底层实现之一。（redis有0-15，16个数据库，默认连接0数据库，可以通过select 2 切换数据库）
（2）在Redis中，字典中哈希表的实现和JDK中HashMap的实现类似，数组用于保存键值对节点，当发生冲突时，采用链表法解决冲突。
（3）字典中包含两个哈希表ht0、ht1，一个多余的哈希表用于rehash。
（4）渐进式rehash，每次更新操作，都会对其所在的id位置进行复制到备份节点。（防止哈希表过大，复制影响性能）

4.跳跃表

跳跃表的查询效率可以和平衡树媲美，并且是实现更简单，所以不少程序使用跳跃表代替平衡树，它支持平均O(logN)，最坏O(N)的复杂度。
（1）Redis采用跳跃表作为有序集合（zset）的底层实现之一（当zset中元素较多，或者成员是比较长的字符串的时候）；
（2）跳跃表的实现：跳跃表由若干个跳跃表节点组成。

skiplist

5.整数集合

（1）整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值，且元素树木不多时，Redis就会采用整数集合作为集合键的底层实现。
（2）intset由一个int变量表示编码类型，一个int8数组表示存储的数据，实际存储的类型由编码决定，还有一个表示长度的int变量

intset

（3）intset只支持编码的升级，不支持降级。

6.压缩列表

（1）压缩列表是列表键和哈希键的底层实现之一；列表键或哈希键只包含少量元素时，会使用压缩列表；
（2）压缩列表的每个节点氛围三部分：前一节点长度、编码、content；
通过前一节点长度我们可以从任意位置遍历列表（可能是1字节，可能是5字节，比较trick的技巧），编码由编码前两位决定编码长度，content记录内容；
（3）连锁更新，删除或新增节点，导致list中的元素长度连续变化，造成连锁更新；不过连锁更新的性能虽然比较差，但是出现的几率是很小的。

7.对象

Redis没有采用底层的数据结构直接表示数据类型，而是基于这些数据结构创造了一个对象系统，这样做的好处有：

• 采用对象封装，方便编写代码，方便使用；
• 封装为对象，可以优化其在不同场景下的使用效率；
• 实现了基于引用计数的内存回收机制；
• 可以基于引用计数实现对象共享机制；
• 对象包含访问时间，当内存超过maxmemory时，可以优先剔除未访问时间较长的键。

Redis中的对象都是由一个RedisObject的数据结构表示，与保存数据有关的是type、encoding、*ptr三个属性，分别表示类型、编码、实际数据的指针。

RedisObject

（1）类型
Redis数据库保存的是键值对，键是“字符串对象”，而值可能是“字符串对象”，“列表对象”，“哈希对象”，“集合对象”，“有序集合对象”。
type命令查看的实际是值的类型。
（2）编码
*ptr指向的数据所采用的数据结构由“编码”决定，每个Redis的数据对象都有多种编码方式。
编码为Redis提供了在性能和存储空间之前平衡的灵活性，在不同的场景下，可以使用不同的编码，以适应当前的场景。

1.字符串对象

字符串对象有int、raw、embstr三种编码。
一个比较特殊的是embstr和raw，他们都是SDS类型，但不同的是raw分两次创建redisObject和sdshdr结构，embstr一次分配内存创建，这样分配、释放内存更快，并且更容易利用缓存；另外，embstr是只读的。

2.列表对象

列表对象有ziplist、linkedlist两种编码。
满足2个条件使用ziplist，不满足则使用linkedlist：
（1）列表对象保存的所有字符串元素小于64字节；
（2）列表元素数目小于512个；

3.哈希对象

列表对象有ziplist、hashtable两种编码。
使用ziplist存储键值对时，键先入队，值再入队。
满足2个条件使用ziplist，不满足则使用hashtable：
（1）哈希表中保存的所有字符串元素小于64字节；
（2）哈希表中元素数目小于512个；

4.集合对象

集合对象的编码可以时intset或者hashtable。
满足2个条件使用intset，不满足则使用hashtable：
（1）集合中保存的元素都是整数值；
（2）集合中元素数目小于512个；

5.有序集合对象（zset根据元素的分值进行排序）

有序集合的编码可以是ziplist或者skiplist（该编码方式同时存在skiplist和hashtable两种数据结构）

满足2个条件使用ziplist，不满足则使用skiplist：
（1）有序集合中保存的所有元素成员小于64字节；
（2）有序集合中元素数目小于128个；

skiplist同时存在skiplist和hashtable两种编码，skiplist用于对有序集合进行范围操作，hashtable用于查找给定成员的分值。skiplist和hashtable共享相同元素的成员和分值，不浪费额外的内存。
同时使用这两种编码是为了兼顾随机查询和范围查询。

类型检查与命令多态

类型由值对象的type决定，多态选择由值对象的编码类型决定。

llen命令执行过程

内存回收

redisObject内部有一个参数refcount，记录该对象的引用数目。
引用计数为0时，对象所占内存会被回收。
object refcount B 可以得到对象的引用数目。

对象共享

redisObject可以通过refcount数字维护对象的共享。
redisObject会共享0-9999的字符串对象。

对象的空转时长

redisObject还有一个参数——lru，用来记录对象最后一次被访问的时间。
object idletime B可以得到对象的空转时长。

二. 单机数据库实现

1.数据库

1.Redis数据库概述

Redis数据库由redisServer数据结构内的redisDb数组保存。
Redis默认有16个数据库，可以通过select 0，... ，select 15来选择，默认连接的是数据库0。

2.Redis数据库的结构

• Redis是一个键值对数据库，redisDb结构中实际是用一个字典dict存储所有的键值对，也就是我们平时使用的键值对。
• redisDb结构中expires字典保存了数据库中所有键的过期时间。
• 过期键删除策略：
  三种可能的策略：
  （1）定时删除：
  创建键的时候，创建定时器，到时间删除这个键，因为消耗CPU（需要用到redis的时间事件机制，复杂度O(n)）
  （2）惰性删除：
  访问这个键的时候才看它的过期时间，过期了才删除，节省CPU，但是可能会占用大量内存，造成内存泄漏。
  （3）定期删除：
  每隔一段时间，执行一次删除过期键的操作，并通过限制删除操作的时长和频率减少对CPU的影响。
  Redis结合使用“惰性删除”和“定期删除”两种策略。
  其中定期删除，会在规定时间内，分多次遍历服务器中的各个数据库，随机检查一些键的过期时间，并删除其中的过期键。

持久化中，删除键的处理：
RDB不会保存过期的键；由RDB或AOF恢复数据的时候，也不会写入过期的键；一个键被删除后，会向AOF加DEL命令。
从服务器发现键过期也不会删除它，而是等待主服务器的DEL命令。

2.持久化

1.RDB持久化（Redis DataBase）

（1）RDB文件的创建与载入
Redis中有SAVE和BGSAVE两个命令可以生成RDB快照，其中SAVE使用当前进程会阻塞其他Redis命令，而BGSAVE会新起一个子进程。同时他们之间是互斥的。
Redis启动时，会检测RDB文件是否存在，存在的话就自动载入。
（2）间隔保存
Redis可以设置save参数，定制规则，定期的对Redis进行BGSAVE。（一个周期性操作）
（3）RDB存储的是实际数据压缩后的结果

RDB文件存储结构

2.AOF持久化（Append Only File）

（1）AOF存储的是客户端发来的命令；
（2）AOF时机
Redis就是一个事件循环，每个循环中，先处理文件事件，再处理时间事件，在结束循环之前，会调用flushAppendOnlyFile函数，考虑是否将aof_buf中的内容写入和保存到AOF文件里。
关于flushAppendOnlyFile的行为，有三种方式：

• always：每次都进行同步
• everysec：每秒进行同步（默认）

• no：何时同步由操作系统决定

  
  Redis事件循环
  

  （3）AOF文件的载入
  RedisServer只能接收客户端的命令，所以，载入AOF文件需要建立一个伪客户端与Server通信。
  （4）AOF重写
  随着执行的命令越来越多，AOF日志会膨胀，BGREWRITE命令能够重写AOF日志，即新的日志与原日志执行结果相同，但所占空间更小（实际上后台创建一个子进程，直接读数据，变为命令）。

3.事件

Redis服务器是一个事件驱动程序，它包含两类事件：文件事件、时间事件。
文件事件：Redis服务器与客户端（以及其他Redis服务器）通信所产生的事件；
时间事件：Redis的一些操作需要在给定事件执行（比如serverCon），即对定时操作的抽象。

1. 文件事件

Redis文件事件处理器基于Reactor模式使用IO多路复用技术，单线程监听多个套接字；当发生网络事件时，根据事件类型，选择合适的文件事件处理器，处理该网络事件；
（1）“单线程”和“IO多路复用”保证了该通信模型的高性能；
（2）Reactor模式保证了单线程设计的简单性和扩展性；
（3）不同的事件由不同的处理器进行处理。

文件事件处理器

注：
Reactor模式首先是事件驱动的，有一个或多个并发输入源，有一个Service Handler，有多个Request Handlers；这个Service Handler会同步的将输入的请求（Event）多路复用的分发给相应的Request Handler。（以往，我认为Reactor模型必然是多线程的。）
Reactor模型的优势：
解耦、提升复用性、模块化、可移植性、事件驱动、细力度的并发控制等。

2. 时间事件

Redis中时间事件有两种：周期性时间事件，定时事件事件。
Redis目前只使用“周期性时间事件”，在Redis中就是serverCon函数。

实现：
Redis将所有的时间事件都放在一个无序链表上，每次遍历整个链表，执行所有到期的事件对应的处理器（实际上Redis只有serverCon一个事件，无序链表退化为指针，不影响性能）。

serverCon的实例：

• 更新服务器各类统计信息
• 清理数据库内过期键值对
• 关闭、清理失效的连接
• 尝试进行AOF或RDB持久化
• 主从服务器之间的同步

3. 事件的调度与执行

当服务器未关闭时，循环执行如下步骤：

• 限时等待文件事件到达
• 处理到达的文件事件

• 处理到达的时间事件（所以时间事件可能稍有延迟）

  
  文件事件和时间事件调度流程

4.客户端与服务器

三. 集群实现

1.复制

Redis可以使用SLAVEOF命令或者设置slaveof选项，让一个服务器去复制（replicate）另一个Redis服务器。

Redis 2.8以前的实现

Redis主从同步分为两个步骤：
（1）同步（SYNC）
从服务器向主服务器发送SYNC命令，主服务器通过BGSAVE生成一个RDB快照，发送给从服务器，从服务器从RDB快照中恢复数据。
（2）命令传播
同步完毕后， 主服务器会把新执行的写操作发送给从服务器，以保持二者的一致状态。
实际上，从服务器相当于主服务器的客户端。

缺陷：
主从服务器初次复制是没有问题的，但是如果主从服务断开连接，从服务器再次连上时，需要再次获得主服务器当前的RDB，这就可能导致，只丢失了一小部分数据，却耗费大量资源重新复制。

Redis 2.8及以后的实现

Redis2.8用PSYNC代替了SYNC，PSYNC会根据情况选择“全量同步”或者“部分同步”。
具体实现：在server端设置固定大小的缓冲区，并且每条语句在主服务器端都有对应的偏移量，从服务器端也记录当前的偏移量；重连时，若偏移量在缓冲区内，则进行“部分同步”，也就是把缓冲区内的更新语句发给从服务器；另外还要记录从服务器的id。（复制偏移量、复制积压缓冲区、从服务ID）

2.Sentinel

哨兵是Redis的高可用性解决方案，由一个或多个Sentinel组成的哨兵系统可以见识任意多个主服务器以及其下的从服务器；当主服务器下线时，会将其下的某个从服务器代替其为主服务器。（故障自动迁移）

• Sentinel是一个运行在特殊模式下的Redis服务器，只是启动时的命令不同，并且在启动时指定了主服务器的地址端口。

• Sentinel向主服务器发送INFO命令来获取从服务器信息，Sentinel每十秒向主服务器和从服务器发送INFO命令（命令连接）；

• Sentinel还会向主从服务器的指定频道发送信息，再从订阅这些主从服务器该频道上的信息，以此来获得其他Sentinel的信息（遇到本Sentinel的消息会丢弃）；维护主服务器到Sentinel列表的映射（用于后续的主管下线和客观下线）。

• 主管下线和客观下线。
  （1）主管下线：
  Sentinel会每秒向其他服务器（Sentinel、Master、Slave）发送Ping消息，当超过一定时间无响应，会判断该服务主管下线（各Sentinel时间期限配置可能不同）
  （2）客观下线
  Sentinel发现某服务下线，则通过向其他Sentinel发送查询命令，确认该服务是否下线，超过指定数目确认后，认为该服务客观下线。（概数目可配置）。
  （Sentinel的三个定时任务：INFO 、发送指定频道消息、Ping）

• 领头Sentinel选择
  实际上是Raft算法的实现。

• 故障自动转移
  （1）选取从服务器为主服务器，根据最近应答时间、复制偏移量、优先级、默认排序等规则选取
  （2）设置其他从服务器
  （3）设置重新上线的主服务器

3.集群

• Redis启动后，添加其他节点进入集群；
• Redis集群采用哈希槽分配数据到各个节点，总共16384个哈希槽；
• Redis接收到一个命令，会查看这个key是否在自己的哈希槽内，在就返回，不在就返回一个Moved响应，让客户端到合适的节点取数据；
• 集群中主节点下线后，从节点能够升级为主节点，代替主节点之前的作用（也是Raft协议实现）。

至此，我们看到了Redis使用的四种架构：Redis单机、Redis主从、Redis Sentinel、Redis集群。

四. 其他功能的实现

1. 发布订阅功能

可以在Redis发布订阅“频道”，也可以订阅“模式”（频道是一个字符串键，模式则是一个正则匹配表达式，用来匹配符合条件的频道）。下面来看下具体的实现：
（1）订阅频道
SUBSCRIBE命令可以订阅一个或多个频道，UNSUBSCRIBE可以退订一个或多个频道；具体的实现是，在pubsub_channels字典上查看该频道是否存在，若不存在则在插入key为频道名和value为空链表的元素，并在链表上加入该客户端信息；若存在则直接找到对应的链表加入客户端信息（退订相反操作）。
（2）订阅模式
PSUBSCRIBE订阅模式，PUNSUBSCRIBE退订模式。
Redis中存在pubsub_patterns的链表用于保存模式，链表中每个元素存储了模式以及该模式对应的客户端链表。
（3）发送消息
Publish 发送消息，会将对应的频道以及匹配到的模式，链表上的客户端得到，然后向他们发送该消息。（会遍历模式链表）
（4）查看订阅信息
通过PUBSUB命令可以查看频道与模式的订阅信息。

2. 事务功能

（1）Redis事务

    MULTI开启事务
    EXEC执行事务
    DISCARD放弃事务
    WATCH实现乐观锁，当被WATCH的值改变事务提交失败

（2）Redis事务的实现
如下图，当服务端的Client对象处于事务状态时，会特殊处理上述四个命令，遇到其他命令则先入队列，而不提交。

Redis事务的实现

（3）Redis事务总是具有ACI特性，当运行在AOF模式下，且appendfsync为always时，也具有D特性。

3. 慢查询日志

SLOWLOG GET 可以查看Redis的慢查询日志（链表实现）。
可以设置时间阈值、以及最多保存的日志条数。

4. Lua脚本

Redis2.6引入了对Lua脚本的支持，redis客户端可以执行Lua脚本，原子的执行任务。