《Redis 设计与实现》

Redis 设计与实现 — Redis 设计与实现

_images/cover.png

[TOC]

第一部分:数据结构与对象

2. 简单动态字符串

SDS 的定义
SDS 与 C 字符串的区别
SDS API

重点回顾

Redis 只会使用 C 字符串作为字面量, 在大多数情况下, Redis 使用 SDS (Simple Dynamic String,简单动态字符串)作为字符串表示。

比起 C 字符串, SDS 具有以下优点:

  • 常数复杂度获取字符串长度。
  • 杜绝缓冲区溢出。
  • 减少修改字符串长度时所需的内存重分配次数。
  • 二进制安全。
  • 兼容部分 C 字符串函数。

3. 链表

链表和链表节点的实现
链表和链表节点的 API

重点回顾

  • 链表被广泛用于实现 Redis 的各种功能, 比如列表键, 发布与订阅, 慢查询, 监视器, 等等。
  • 每个链表节点由一个 listNode 结构来表示, 每个节点都有一个指向前置节点和后置节点的指针, 所以 Redis 的链表实现是双端链表。
  • 每个链表使用一个 list 结构来表示, 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL , 所以 Redis 的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数, Redis 的链表可以用于保存各种不同类型的值。

4. 字典

字典的实现
哈希算法
解决键冲突
rehash

渐进式 rehash

rehash 的过程:

  1. 为 ht[1] 分配空间
  2. 将字典中 rehashidx 设为 0,表示 rehash 工作正式开始(rehashidx 表示 ht[0] 中下一个需要 rehash 的索引位置)
  3. 每次对字典进行增删改查,检测到 rehashidx>=0, 则程序除了处理指定的操作,还会顺带将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中,rehashidx++
  4. rehashidx 等于 ht[0] 的长度时,rehash结束,将 rehashidx 设为 -1

渐进式 rehash 的好处在于采取分而治之的方式,将 rehash 键值对的工作均摊到每次增删改查的操作上,避免了几种 rehash 而带来的庞大计算量。

字典 API

重点回顾

  • 字典被广泛用于实现 Redis 的各种功能, 其中包括数据库和哈希键。
  • Redis 中的字典使用哈希表作为底层实现, 每个字典带有两个哈希表, 一个用于平时使用, 另一个仅在进行 rehash 时使用。
  • 当字典被用作数据库的底层实现, 或者哈希键的底层实现时, Redis 使用 MurmurHash2 算法来计算键的哈希值。
  • 哈希表使用链地址法来解决键冲突, 被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时, 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面, 并且这个 rehash 过程并不是一次性地完成的, 而是渐进式地完成的。

5. 跳跃表

跳跃表的实现

跳跃表

包含的属性:

header

tail

level 目前跳跃表内,层数最大的节点的层数

length

跳跃表节点

包含的属性:

level: 每个节点的 level 数量可能不同。每个 level 包括当前 level 指向下一个节点的指针和这 2 个节点之间的跨度

backward 指针

score

obj

每次创建一个新跳跃表节点,程序根据幂次定律(越大的数出现的概率越小)随机生成一个 1~32之间的值作为 level 数组的大小,这个大小就是层的高度。如:高度为 3 的节点有 level[0] level[1] level[2] 三个向前的指针。

跳跃表 API

重点回顾

  • 跳跃表是有序集合的底层实现之一, 除此之外它在 Redis 中没有其他应用。
  • Redis 的跳跃表实现由 zskiplistzskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息(比如表头节点、表尾节点、长度), 而 zskiplistNode 则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是 132 之间的随机数。
  • 在同一个跳跃表中, 多个节点可以包含相同的分值, 但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序, 当分值相同时, 节点按照成员对象的大小进行排序。

6. 整数集合 intset

整数集合的实现

intset 包括的属性:

encoding

length

contents[]

encoding 可以是 intset_enc_int16 intset_enc_int32 intset_enc_int64,表示 contents 数组中元素的整数类型

升级

新增元素大于当前 intset 类型的整数上限是,需要对 intset 进行升级

升级的好处

降级

整数集合 API

重点回顾

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组, 这个数组以有序、无重复的方式保存集合元素, 在有需要时, 程序会根据新添加元素的类型, 改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性, 并且尽可能地节约了内存。
  • 整数集合只支持升级操作, 不支持降级操作。

7. 压缩列表

压缩列表的构成

压缩列表是为了节约内存开发的

压缩列表节点的构成

previous_entry_length

encoding

content

连锁更新
压缩列表 API

重点回顾

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表, 或者从压缩列表中删除节点, 可能会引发连锁更新操作, 但这种操作出现的几率并不高。

8. 对象

对象的类型与编码

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct redisObject{
// 类型
unsigned type: 4;
// 编码
unsigned encoding: 4;
// 指向底层实现数据结构的指针
void *ptr;
// 引用计数
int refcount;
// 最后一次被程序访问的时间
unsigned lru;
}

类型

指的是 Redis 数据库中保存的值的类型,可以是 redis_string , redis_list, redis_hash, redis_set, redis_zset

使用 type key 查询键对应的值的类型

编码

底层实际使用的数据结构

使用 object encoding key 可以查询编码

字符串对象

字符串 对象的编码可以是 int、raw、embstr,分别针对 整数 长字符 和 短字符

列表对象

列表 对象的编码可以是 ziplist 或者 linkedlist

某一类型采用不同的编码主要是综合考虑 空间和时间

编码使用 ziplsit 的条件:

  • 列表中所有字符串长度小于64字节
  • 元素数量少于 512 个

以上 2 个条件的上限值可以修改

哈希对象

哈希 对象的编码可以是 ziplist 和 hashtable

集合对象

集合 对象的编码可以是 intset 和 hashtable

有序集合对象

有序集合 对象的编码可以是 ziplist 和 skiplist

skiplist 编码的有序集合 同时用了 跳跃表 和 字典

原因:为了让查找元素的分值与范围查找的复杂度降到最低

  • 如果只用字典实现有序集合,每次范围操作时都要对所有元素进行排序,消耗 O(NlogN) 的时间复杂度和 O(N) 的额外内存空间。
  • 如果只使用跳跃表,查找分值的复杂度为 O(logN) , 利用字典可以将复杂度降到 O(1)

类型检查与命令多态

Redis 操作建的命令基本分为 2 类:一种可以操作所有类型的键,如 del expire rename type object 等

另一种只能对特定类型的键执行

redis 服务器收到命令后,会对命令的合法性进行检查

内存回收

c 语言不具备自动内存回收功能,索引 Redis 自己构造了利用引用计数技术实现的内存回收机制,程序可以根据对象的引用计数信息,在适当的时候自动释放对象并进行内存回收。

对象共享

Redis 在初始化服务器的时候,创建 0-9999 1 万个字符串对象,

对象的空转时长

根据对象的 lru 属性计算出对象的空转时长

object idletime key

重点回顾

  • Redis 数据库中的每个键值对的键和值都是一个对象。
  • Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象, 每种类型的对象至少都有两种或以上的编码方式, 不同的编码可以在不同的使用场景上优化对象的使用效率。
  • 服务器在执行某些命令之前, 会先检查给定键的类型能否执行指定的命令, 而检查一个键的类型就是检查键的值对象的类型。
  • Redis 的对象系统带有引用计数实现的内存回收机制, 当一个对象不再被使用时, 该对象所占用的内存就会被自动释放。
  • Redis 会共享值为 09999 的字符串对象。
  • 对象会记录自己的最后一次被访问的时间, 这个时间可以用于计算对象的空转时间。

第二部分:单机数据库的实现

9. 数据库

服务器中的数据库
切换数据库
数据库键空间
设置键的生存时间或过期时间
过期键删除策略
Redis 的过期键删除策略
AOF 、RDB 和复制功能对过期键的处理
数据库通知

重点回顾

  • Redis 服务器的所有数据库都保存在 redisServer.db 数组中, 而数据库的数量则由 redisServer.dbnum 属性保存。
  • 客户端通过修改目标数据库指针, 让它指向 redisServer.db 数组中的不同元素来切换不同的数据库。
  • 数据库主要由 dictexpires 两个字典构成, 其中 dict 字典负责保存键值对, 而 expires 字典则负责保存键的过期时间。
  • 因为数据库由字典构成, 所以对数据库的操作都是建立在字典操作之上的。
  • 数据库的键总是一个字符串对象, 而值则可以是任意一种 Redis 对象类型, 包括字符串对象、哈希表对象、集合对象、列表对象和有序集合对象, 分别对应字符串键、哈希表键、集合键、列表键和有序集合键。
  • expires 字典的键指向数据库中的某个键, 而值则记录了数据库键的过期时间, 过期时间是一个以毫秒为单位的 UNIX 时间戳。
  • Redis 使用惰性删除和定期删除两种策略来删除过期的键: 惰性删除策略只在碰到过期键时才进行删除操作, 定期删除策略则每隔一段时间, 主动查找并删除过期键。
  • 执行 SAVE 命令或者 BGSAVE 命令所产生的新 RDB 文件不会包含已经过期的键。
  • 执行 BGREWRITEAOF 命令所产生的重写 AOF 文件不会包含已经过期的键。
  • 当一个过期键被删除之后, 服务器会追加一条 DEL 命令到现有 AOF 文件的末尾, 显式地删除过期键。
  • 当主服务器删除一个过期键之后, 它会向所有从服务器发送一条 DEL 命令, 显式地删除过期键。
  • 从服务器即使发现过期键, 也不会自作主张地删除它, 而是等待主节点发来 DEL 命令, 这种统一、中心化的过期键删除策略可以保证主从服务器数据的一致性。
  • 当 Redis 命令对数据库进行修改之后, 服务器会根据配置, 向客户端发送数据库通知。

10. RDB 持久化

RDB 文件的创建与载入
自动间隔性保存
RDB 文件结构
分析 RDB 文件

重点回顾

  • RDB 文件用于保存和还原 Redis 服务器所有数据库中的所有键值对数据。
  • SAVE 命令由服务器进程直接执行保存操作,所以该命令会阻塞服务器。
  • BGSAVE 命令由子进程执行保存操作,所以该命令不会阻塞服务器。
  • 服务器状态中会保存所有用 save 选项设置的保存条件,当任意一个保存条件被满足时,服务器会自动执行 BGSAVE 命令。
  • RDB 文件是一个经过压缩的二进制文件,由多个部分组成。
  • 对于不同类型的键值对, RDB 文件会使用不同的方式来保存它们。

11. AOF 持久化

AOF 持久化的实现
AOF 文件的载入与数据还原
AOF 重写

重点回顾

  • AOF 文件通过保存所有修改数据库的写命令请求来记录服务器的数据库状态。
  • AOF 文件中的所有命令都以 Redis 命令请求协议的格式保存。
  • 命令请求会先保存到 AOF 缓冲区里面, 之后再定期写入并同步到 AOF 文件。
  • appendfsync 选项的不同值对 AOF 持久化功能的安全性、以及 Redis 服务器的性能有很大的影响。
  • 服务器只要载入并重新执行保存在 AOF 文件中的命令, 就可以还原数据库本来的状态。
  • AOF 重写可以产生一个新的 AOF 文件, 这个新的 AOF 文件和原有的 AOF 文件所保存的数据库状态一样, 但体积更小。
  • AOF 重写是一个有歧义的名字, 该功能是通过读取数据库中的键值对来实现的, 程序无须对现有 AOF 文件进行任何读入、分析或者写入操作。
  • 在执行 BGREWRITEAOF 命令时, Redis 服务器会维护一个 AOF 重写缓冲区, 该缓冲区会在子进程创建新 AOF 文件的期间, 记录服务器执行的所有写命令。 当子进程完成创建新 AOF 文件的工作之后, 服务器会将重写缓冲区中的所有内容追加到新 AOF 文件的末尾, 使得新旧两个 AOF 文件所保存的数据库状态一致。 最后, 服务器用新的 AOF 文件替换旧的 AOF 文件, 以此来完成 AOF 文件重写操作。(这跟 MySQL 的 recreate 重建表类似,为了不阻塞其他修改,将修改记录到日志,重建完成后将日志应用到新表)

12. 事件

这一节没有太看懂

文件事件

Redis 基于 Reactor 模式开发了自己的网络事件处理器: 这个处理器被称为文件事件处理器(file event handler):

  • 文件事件处理器使用 I/O 多路复用(multiplexing)程序来同时监听多个套接字, 并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
  • 当被监听的套接字准备好执行连接应答(accept)、读取(read)、写入(write)、关闭(close)等操作时, 与操作相对应的文件事件就会产生, 这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

虽然文件事件处理器以单线程方式运行, 但通过使用 I/O 多路复用程序来监听多个套接字, 文件事件处理器既实现了高性能的网络通信模型, 又可以很好地与 Redis 服务器中其他同样以单线程方式运行的模块进行对接, 这保持了 Redis 内部单线程设计的简单性

Redis 的 I/O 多路复用程序的所有功能都是通过包装常见的 selectepollevportkqueue 这些 I/O 多路复用函数库来实现的

时间事件
事件的调度与执行

重点回顾

  • Redis 服务器是一个事件驱动程序, 服务器处理的事件分为时间事件和文件事件两类。
  • 文件事件处理器是基于 Reactor 模式实现的网络通讯程序。
  • 文件事件是对套接字操作的抽象: 每次套接字变得可应答(acceptable)、可写(writable)或者可读(readable)时, 相应的文件事件就会产生。
  • 文件事件分为 AE_READABLE 事件(读事件)和 AE_WRITABLE 事件(写事件)两类。
  • 时间事件分为定时事件和周期性事件: 定时事件只在指定的时间达到一次, 而周期性事件则每隔一段时间到达一次。
  • 服务器在一般情况下只执行 serverCron 函数一个时间事件, 并且这个事件是周期性事件。
  • 文件事件和时间事件之间是合作关系, 服务器会轮流处理这两种事件, 并且处理事件的过程中也不会进行抢占。
  • 时间事件的实际处理时间通常会比设定的到达时间晚一些。

参考资料

13. 客户端

这一节没有太看懂

客户端属性
客户端的创建与关闭

重点回顾

  • 服务器状态结构使用 clients 链表连接起多个客户端状态, 新添加的客户端状态会被放到链表的末尾。
  • 客户端状态的 flags 属性使用不同标志来表示客户端的角色, 以及客户端当前所处的状态。
  • 输入缓冲区记录了客户端发送的命令请求, 这个缓冲区的大小不能超过 1 GB 。
  • 命令的参数和参数个数会被记录在客户端状态的 argvargc 属性里面, 而 cmd 属性则记录了客户端要执行命令的实现函数。
  • 客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用, 其中固定大小缓冲区的最大大小为 16 KB , 而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值。
  • 输出缓冲区限制值有两种, 如果输出缓冲区的大小超过了服务器设置的硬性限制, 那么客户端会被立即关闭; 除此之外, 如果客户端在一定时间内, 一直超过服务器设置的软性限制, 那么客户端也会被关闭。
  • 当一个客户端通过网络连接连上服务器时, 服务器会为这个客户端创建相应的客户端状态。 网络连接关闭、 发送了不合协议格式的命令请求、 成为 CLIENT_KILL 命令的目标、 空转时间超时、 输出缓冲区的大小超出限制, 以上这些原因都会造成客户端被关闭。
  • 处理 Lua 脚本的伪客户端在服务器初始化时创建, 这个客户端会一直存在, 直到服务器关闭。
  • 载入 AOF 文件时使用的伪客户端在载入工作开始时动态创建, 载入工作完毕之后关闭。

14. 服务器

命令请求的执行过程
serverCron 函数
初始化服务器

重点回顾

  • 一个命令请求从发送到完成主要包括以下步骤: 1. 客户端将命令请求发送给服务器; 2. 服务器读取命令请求,并分析出命令参数; 3. 命令执行器根据参数查找命令的实现函数,然后执行实现函数并得出命令回复; 4. 服务器将命令回复返回给客户端。
  • serverCron 函数默认每隔 100 毫秒执行一次, 它的工作主要包括更新服务器状态信息, 处理服务器接收的 SIGTERM 信号, 管理客户端资源和数据库状态, 检查并执行持久化操作, 等等。
  • 服务器从启动到能够处理客户端的命令请求需要执行以下步骤: 1. 初始化服务器状态; 2. 载入服务器配置; 3. 初始化服务器数据结构; 4. 还原数据库状态; 5. 执行事件循环。

第三部分:多机数据库的实现

复制

旧版复制功能的实现
旧版复制功能的缺陷
新版复制功能的实现
部分重同步的实现
PSYNC 命令的实现
复制的实现
心跳检测
重点回顾

Sentinel

启动并初始化 Sentinel
获取主服务器信息
获取从服务器信息
向主服务器和从服务器发送信息
接收来自主服务器和从服务器的频道信息
检测主观下线状态
检查客观下线状态
选举领头 Sentinel
故障转移
重点回顾
参考资料

集群

节点
槽指派
在集群中执行命令
重新分片
ASK 错误
复制与故障转移
消息
重点回顾

第四部分:独立功能的实现

发布与订阅

频道的订阅与退订
模式的订阅与退订
发送消息
查看订阅信息
重点回顾
参考资料

事务

事务的实现
WATCH 命令的实现
事务的 ACID 性质
重点回顾
参考资料

Lua 脚本

创建并修改 Lua 环境
Lua 环境协作组件
EVAL 命令的实现
EVALSHA 命令的实现
脚本管理命令的实现
脚本复制
重点回顾
参考资料

排序

SORT 命令的实现
ALPHA 选项的实现
ASC 选项和 DESC 选项的实现
BY 选项的实现
带有 ALPHA 选项的 BY 选项的实现
LIMIT 选项的实现
GET 选项的实现
STORE 选项的实现
多个选项的执行顺序
重点回顾

二进制位数组

位数组的表示
GETBIT 命令的实现
SETBIT 命令的实现
BITCOUNT 命令的实现
BITOP 命令的实现
重点回顾
参考资料

慢查询日志

慢查询记录的保存
慢查询日志的阅览和删除
添加新日志
重点回顾

监视器

成为监视器
向监视器发送命令信息
重点回顾

# 推荐文章
  1.biweekly-contest-22
  2.面试题 01.07 旋转矩阵
  3.chrome 插件
  4.biweekly-contest-23
  5.weekly-contest-180

评论


:D 一言句子获取中...