Redis底层的几个数据结构

简单动态字符串

1. 对C语言字符串进行了封装
2. 保存了字符串的长度，避免了内存溢出
3. 动态的进行内存重分配。
   1. 扩容。如果字符串长度小于1MB，分配相同长度的未使用空间；如果字符串长度大于1MB，分配1MB的未使用空间
   2. 缩容。惰性释放，不会主动释放。

链表

使用的是双向链表

字典

1. 根据哈希算法进行映射
2. 使用链地址法解决哈希冲突，采用头插法
3. rehash步骤
   1. 为新哈希表分配空间
   2. 重新哈希到新的哈希表
   3. 释放原来的哈希表，将新哈希表赋值到旧的引用上
   4. 为了避免对服务器性能造成影响，rehash是分多次、渐进式完成的，每次rehash一个index。rehash期间对字典操作时，操作两个哈希表，操作时还会顺带把ht[0]在索引的所有键值rehash到ht[1]

跳跃表

redis在两个地方使用了跳跃表：有序集合、集群节点的内部数据结构

跳跃表的几个字段：

1. level数组。每次创建新跳跃表节点时，随机生成一个1～32之间的数组所谓level数组的大小，这个大小就是层的高度。层数越多，访问其他节点的速度越快。
2. 前进指针和跨度。每层都有一个前进指针（指向后面某个节点）和两个节点之间的跨度。跨度用来计算节点在跳跃表中的排位。
3. 跳跃表的节点按分值大小排序，当分值相同时，节点按成员对象的大小排序。

整数集合

1. 当一个集合只包含整数元素，并且这个集合的元素数量不多时，redis就是使用整数集合作为集合键的底层实现。
2. 整数集合的底层为数组，以有序、无重复的方式保存集合元素。
3. 整数集合的数据类型取决于最大整数的大小
4. 当添加一个比较大的整数时，需要对整数类型进行升级
5. 升级策略的好处是节约内存
6. 不支持降级

压缩列表(ziplist)

1. 压缩列表是列表键和哈希键的实现方式之一，当一个列表键/哈希键只有少量元素，且每个元素是小整数或短字符串时，就会使用压缩列表。
2. 压缩列表的目的是节约内存
3. 压缩列表的数据结构：总长度、距离最后一个节点的距离（字节数）、节点数量、节点、标志位
4. 每个节点的数据结构：
   1. 前一个节点的长度previous_entry_length，用于计算前一个节点的起始地址，用于反向遍历。这个字段的长度是变长的，1字节（长度小于254时）或5字节（第一个字节会设置为0xFE）
   2. 当前节点的数据类型和长度
   3. 当前节点的值
5. 连锁更新/删除。如果一个节点的长度发生了更新，那么由于后续的每个节点previous_entry_length都记录了前一个节点的长度，所以可能后续的节点全都要更新
6. 连锁更新的对性能的影响：1.概率很低；2.节点很少，影响很小

对象

redis使用简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象。

redis对象系统还实现了基于引用计数的内存回收机制和对象共享机制。（不会存在循环引用）

redis对象带有访问时间记录信息，用于计算数据库键的空转时长。

redis对象中的字段有：

1. 类型。类型指对象类型
2. 编码类型。编码类型指对象的底层数据结构类型
3. 指向底层数据结构的指针
4. 引用计数
5. 对象最后一次被访问的时间

类型常量	对象名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REDIS_ZET	有序集合对象

类型常量	编码常量	实现方式
REDIS_STRING	REDIS_ENCODING_INT	long类型整数（用来保存整数）
REDIS_STRING	REDIS_ENCODING_EMBSTR	embstr编码的简单动态字符串(调用一次内存分配函数来来为对象和字符串分配一块连续的空间），字符串长度小于39字节时使用embstr
REDIS_STRING	REDIS_ENCODING_RAW	简单动态字符串
–	–	–
REDIS_LIST	REDIS_ENCODING_ZIPLIST	压缩列表。当列表对象同时满足两个条件时使用压缩列表：1.所有字符串长度小于64字节；2.元素个数小于512个
REIDS_LIST	REDIS_ENCODING_LINKEDLIST	链表
–	–	–
REDIS_HASH	REDIS_ENCODING_ZIPLIST	压缩列表。当哈希对象同时满足两个条件时，使用压缩列表：1.键和值长度都小于64字节；键值对数量小于512
REDIS_HASH	REDIS_HT	字典
–	–	–
REDIS_SET	REDIS_ENCODING_INTSET	整数集合。都是整数且数量不超过512时使用整数集合
REDIS_SET	REDIS_ENCODING_HT	字典
–	–	–
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	压缩列表。成员长度都小于64字节且数量小于128个时使用压缩列表
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	跳表和字典，共享元素和scope

• redis执行命令时会先检查key的对象是否支持命令
• redis通过多态调用不同编码的接口
• redis支持对象共享，但只会共享字符串，不会共享包含字符串的对象，可以避免循环引用，还可以避免不断比较两个对象是否相等，降低程序复杂度。
• redis服务器初始化时，会创建0～9999一万个字符串对象。

数据库的基本实现

Redis客户端

服务器使用链表保存多个客户端状态

客户端数据结构（redisClient）保存的字段有

1. 客户端名称。默认没有
2. 客户端套接字描述符。是个整数，伪客户端的值为-1
3. 标志。记录客户端角色，主从客户端？2.8版本以下？正在被阻塞
4. 正在使用的数据库的指针
5. 客户端输入缓冲区。输入缓冲区最大不超过1GB
6. 客户端输出缓冲区。每个客户端有2个，一个大小固定（用于简短的回复），一个变长
7. 当前执行的命令、参数信息
8. 事务状态
9. 身份验证信息
10. 客户端创建时间、最后一次较交互时间、空转时间
11. 处理lua脚本的伪客户端从服务器启动一直存在，直到服务器关闭。
12. 载入AOF文件时使用的伪客户端在载入时创建，载入完成之后关闭

Redis服务器

服务器启动过程

1. 根据配置初始化服务器
2. 载入AOF文件

数据库

1. 数据库中默认16个db(每个client保存自己的当前db)。每个db中都有一个字典保存了数据库的所有键
2. 键的过期时间在单独的字典中。命令有：expire、pexpire，exprieat、pexpireat、persist

过期键的删除策略

1. 定时删除。定时任务执行时对内存友好，对cpu不友好
2. 惰性删除。对cpu友好，对内存不友好。如果过期键再也没有被访问的话，就永远不会被删除

redis：定时+惰性。难点：时长和频率不好控制

1. RDB文件生成时不会保存已过期键，载入时会忽略过期键
2. AOF文件生成时会保存过期键，重写时会忽略过期键，载入时会忽略过期键
3. 主从复制模式下，主服务器会广播DEL命令删除，从服务器过期也不删除等待主服务器的广播

命令请求的过程

1. 客户端发送命令
2. 服务器读取命令请求
3. 查找命令实现函数
4. 检查参数（个数、身份验证、检查服务器内存占用情况）
5. 调用实现函数
6. 执行后续工作。记录慢查询日志、修改计数器、命令写入AOF缓冲、广播命令给从服务器、记录服务器hit次数
7. 将命令回复发送给客户端
8. 客户端接收并打印

ServerCron函数默认每100ms执行1次

1. 更新服务器时间缓存。键的过期时间、慢查询日志不会使用缓存，仍然会进行系统调用
2. 抽样估算服务器最近一秒执行的命令次数(（当前总次数-上次总次数）/时间间隔)
3. 更新内存峰值
4. 判断是否要关闭服务器
5. 调用clientsCron，释放超时的客户端
6. 调用databasesCron，判断是否满足bgsave
7. 执行被bgsave阻塞的bgrewriteaof
8. AOF缓冲区写入AOF文件

RDB文件持久化

• RDB文件用于保存和还原redis服务器所有数据库中的所有键值对
• SAVE: 阻塞服务器进程创建RDB文件
• BGSAVE：启动新的子进程创建RDB文件。执行期间后续的BGSAVE会被拒绝，BGREWRITEAOF延迟执行
• RDB文件允许间隔性保存，只要有一个满足了条件就会执行。
• RDB文件是一个经过压缩的二进制文件

AOF文件持久化

• AOF持久化是通过保存redis服务器所执行的写命令来记录数据库状态的。
• AOF持久化的实现分为命令追加、文件写入、文件同步三个步骤

• 命令追加。写命令执行之后会追加到aof_buf缓冲区
• 文件写入与同步。redis服务器每次结束一个事件循环之前，会将aof_buf写入到AOF文件。根据参数可以分为三种：1.缓冲区写入并同步到AOF文件；2.缓冲区写入AOF文件，如果距上次 同步超过1秒则同步；3.写入AOF文件，何时同步由操作系统决定。

• AOF重写，重写是为了解决AOF文件体积膨胀的问题。虽然reids将生成新AOF文件替换旧AOF文件命名为“AOF文件重写”，但实际上，AOF文件重写并不需要对旧的AOF文件进行任何读取、分析或写入，这个是通过读取服务器当前的数据库状态实现的。为了解决重写AOF文件期间的请求对数据库修改的问题，redis增加了AOF重写缓冲区，redis执行完命令后，会同时发送到AOF缓冲区和AOF重写缓冲区。

Redis的多种部署模式

redis有四种部署方式：

• 单机部署
• 主从复制
• 哨兵模式
• 集群模式

主从复制

slaveof 异步的让一个服务器复制另一个服务器

当发送slaveof命令时

1. 从服务器向主服务器发送sync命令
2. 主服务器执行bgsave，在后台生成RDB文件，并使用缓冲区记录RDB文件之后的写命令
3. 主服务器将RDB文件发送给从服务器
4. 从服务器载入RDB文件更新自己的状态，载入期间阻塞
5. 主服务器将缓冲区的写命令发送给从服务器
6. 之后每当主服务器执行客户端的写命令时，会将这条写命令广播给所有从服务器
7. 从服务器默认每秒向主服务器发送心跳命令replconf ack ，用于：
   1. 检查网络连接：
   2. 实现min-slaves（当从服务器数量小于配置或延迟都大于配置时，主服务器拒绝执行写命令）
   3. 同步offset，命令重传

在旧版本的redis中，主从断线后不能续传，只能从头复制（重同步），sync命令和bgsave命令会消耗大量的内存、CPU、磁盘I/O和网络资源

在新版本的redis中psync命令实现了完整重同步和部分重同步。主服务器同步期间会维护一个复制偏移量和复制积压缓冲区。如果从服务器的复制偏移量还在积压缓冲区内，就不需要重同步，只需要把缓冲区的命令重新发送即可。

Sentinel哨兵模式

哨兵模式是redis高可用性解决方案；监视多个主从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务器下的某个从服务器升级为新的主服务器

启动sentinel

• redis-sentinel
• redis-server –sentinel

1. sentinel默认每10秒一次的频率，通过命令连接向被监视的主服务器发送info命令
2. sentinel默认每2秒一次的频率，向所有主服务器发送publish命令
3. sentinel会订阅subscribe __sentinel__:hello topic命令
4. 检测下线
   1. 检测主观下线状态：连续一段时间发送ping命令没有有效回复，不同哨兵配置的时间可能不同
   2. 检测客观下线状态：主观下线后才会判断是否客观下线，如果n个哨兵都认为该服务器下线，则认定为下线
   3. 选择领头哨兵：主服务器客观下线后，需要从从服务器选一个主服务器。首先选择领头哨兵，每个哨兵发送询问，然后其它哨兵回复，先到先得。回复多的就是领头
   4. 领头哨兵负责从从服务器选一个主服务：首先根据服务器的优先级排序，优先级相同则选择偏移量最大的从服务器
   5. 修改其它从服务器的主服务器地址

集群模式

redis集群是redis提供的分布式数据库方案，通过分片来进行数据共享，并提供复制和故障转移功能

每节点都会维护其它所有主从节点的信息。整个集群被划分为16384个槽，数据库中每个键都属于其中的1个槽。

哪个节点负责哪些槽是通过位图（二维数组）维护的，同时redis维护了每个槽的节点的映射。

集群节点只能使用0号数据库。

集群槽支持重新分片，重新分片期间，对某个键进行操作时，可能会访问两个节点。

集群支持故障转移，如果一半以上的主节点都认为某个节点下线，则认为下线。从节点发现主节点下线后会重新选举主节点。

启动redis集群： cluster meet

向节点分配槽：cluster addslots

集群状态：cluster info

其它

发布与订阅

事务

lua脚本

其它实现

慢日志

监视器

排序

二进制数组

使用variable precision swar算法，统计数组中1个个数

分布式锁

命令

1. type
2. object encoding
3. object idletime
4. client list 列出所有连接到服务器的普通客户端
5. info status
6. subscribe __keyspace@0__:message 获取0号数据库中针对message执行的所有命令
7. slaveof  让一个服务器复制另一个服务器
8. redis-sentinel  哨兵模式