《Redis设计与实现》 笔记

字符串

Redis自己构建了一种简单动态字符串(SDS)

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

why？

  1. 常数复杂度获取字符串长度

  2. 杜绝缓冲区溢出

  3. 减少修改字符串时带来的内存重分配次数(传统的C语言字符串每次修改都要重新分配内存)

    • 空间预分配策略： sds小于1MB翻倍，大于1MB 留1MB空间

    • 惰性空间释放：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节数量先记录起来，并等待将来回收，避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。

  4. 二进制安全。sds可以用来保存二进制数据，c字符串不行

  5. 兼容部分C字符串函数

链表

字典

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

当要将一个新的键值对加到字典里面时，先根据键值对的键计算出哈希值和索引值，再根据索引值将新的哈希表节点放到指定的位置上。

键冲突怎么解决？

  1. 采用链地址法构成一个单向链表，总是将新节点添加到链表的表头位置（这样速度比较快）

  2. rehash

    • 当哈希表保存的键值对数量太多或太少时，程序需要对哈希表进行rehash操作

      1. 构建一个新的字典ht[1]并分配空间
      2. 将保存在ht[0]中所有的键值对rehash到ht[1]
      3. 释放ht[0]，将ht[1]设置为ht[0]

    • 这个rehash动作是分多次、渐进式完成的(如果一次性完成，可能导致服务器在一段时间内停止服务),在rehash进行期间，程序除了执行指定操作以外，还会顺带将ht[0]哈希表上的某个索引上的所有键值对移动到ht[1]

    • 在渐进式rehash过程中，有ht[0]和ht[1]两个哈希表。如果要查找一个键，现在ht[0]查找，再去ht[1]查找。新添加的键值对一律被保存在ht[1]

哈希表的扩展与收缩

​ 当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而实现快速访问。

如果一个有序集合包含的元素数量较多，又或者有序集合中元素的成员是比较长的字符串时，Redis会使用跳跃表来作为有序集合键的底层实现。

（以后有时间的话自己尝试一下实现一个Java的跳跃表）

整数集合

整数是集合键的底层实现之一，当一个集合只包含整数值元素，并且数量不多时，Redis使用整数集合作为集合键的底层实现。

压缩列表

对象

  1. 字符串对象
  2. 列表对象
  3. 哈希对象
  4. 集合对象
  5. 有序集合对象

内存回收

Redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制

对象共享

如果采用lru算法，空转时长较高的那部分键会优先被服务器释放。

数据库

struct redisServer{
    // 服务器的数据库数量
    int dbnum;
    // 一个数组，保存着服务器中的所有数据库
    redisDb *db;
    // ...
};
复制代码
typedef struct redisClient{
    // ...
    // 记录客户端当前正在使用的数据库
    redisDb * Db;
    // ...
}redisClient;
复制代码
typedef struct redisDb{
    // ...
    // 数据库键空间，保存着数据库中所有的键值对
    dict *dict;
    // 过期字典，保存着键的过期时间
    dict * expires;
}redisDb;
复制代码

键的过期时间

可以通过 EXPIRE、EXPIREAT、PEXPIRE、PEXPIREAT、

redisDb结构的expires字典保存了数据库所有键的过期时间。

  • 过期字典的键是一个指针，这个指针指向键空间中的某个键对象（也即是某个数据库键）。

  • 过期字典的值是一个long long类型的整数，这个整数保存了键所指向的数据库键的过期时间—一个毫秒精度的UNIX时间戳。

PERSIST可以移除一个键的过期时间

过期键删除策略

  1. 定时删除

    • 通过使用定时器，保证过期键会尽快被删除并释放内存
    • 对内存友好，但对CPU不友好

  2. 惰性删除

    • 程序只会在取出键的时候对键进行过期检查
    • 对内存极不友好，对CPU友好
    • 如果一个过期键永远没有被访问到，那么会导致内存泄漏

  3. 定期删除

    • 每隔一段时间执行一次删除过期键操作，并通过限制删除操作的时长和频率减少对CPU的影响

    • 定期删除策略的难点是确定删除操作执行的时长和频率

      如果删除操作执行得太频繁 ，或者执行得时间太长，定期删除策略就会退化成定时删除策略

      相反，则和惰性删除策略一样，出现浪费内存的情况。

Redis的过期键删除策略

​ Redis服务器采用的是惰性删除和定期删除两种策略

  1. 惰性删除
    • 所有读写Redis命令在执行之前都会对输入键进行检查
      • 如果键已过期，则将其从数据库删除
  2. 定期删除
    • 在规定时间内，分多次遍历各个数据库，从expires字典中随机检查一部分键的过期时间，并删除其中的过期键
    • 全局变量current_db会记录函数检查的进度，并在下一次函数调用时，接着上一次的进度进行处理

AOF、RDB和复制功能对过期键的处理

  1. 生成RDB。在执行SAVE或BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，已过期的键不会被保存到新的RDB文件中

  2. 载入RDB。

    • 如果是主服务器，对键进行检查，未过期的键载入到数据库。
    • 如果是从服务器，文件中保存的所有键都会被载入，因为主从同步的时候，从服务器的数据库会被清空，过期键无影响。

  3. AOF写入

    • 不会因为过期键产生任何影响
    • 程序向AOF文件追加一条DEL命令

  4. AOF重写

    • 在执行AOF重写的过程中，程序会对数据库中的键进行检查，已过期的键不会被保存到重写后的AOF文件里

  5. 复制

    • 当服务器运行在复制模式下，从服务器的过期键策略由主服务器控制

RDB持久化

RDB持久化——将Redis在内存中的数据保存到磁盘里

SAVE和BGSAVE

  • SAVE 保存是阻塞主进程，客户端无法连接redis，等SAVE完成后，主进程才开始工作，客户端可以连接

  • BGSAVE 是fork一个save的子进程，在执行save过程中，不影响主进程，客户端可以正常链接redis，等子进程fork执行save完成后，通知主进程，子进程关闭。很明显BGSAVE方式比较适合线上的维护操作。

自动间隔性保存

可以通过设置服务器配置的save选项设置多个保存条件，只要其中一个条件被满足，服务器就会执行BGSAVE命令

struct redisServer{
    // 记录了保存条件的数组
    struct saveparam *saveparams;
}
复制代码

saveparams属性是一个数组，数组中的每个元素都是一个savaparam结构，每个saveparam结构都保存了一个save选项设置的保存条件

struct saveparam{
	// 秒数
	time_t seconds;
	// 修改数
	int changes;
}
复制代码

除了saveparams数组之外，服务器还维持着一个dirty计数器，以及一个lastsave属性:

  • dirty计数器记录距离上一次成功执行save或bgsave命令后，服务器对数据库状态进行了多少次修改。
  • lastsave属性记录了上一次成功执行save命令或bgsave命令的时间

检查保存条件

Redis服务器的周期性操作函数serverCron默认每隔100毫秒就会执行一次，它的其中一项工作就是检查save选项设置的保存条件是否已满足。

程序会遍历并检查saveparams数组中的所有保存条件，只要有一个条件满足，服务器就会执行BGSAVE命令。

AOF持久化

AOF持久化是通过保存Redis服务器执行的写命令来记录数据库状态

  1. 命令追加
  2. 文件写入
  3. 文件同步

AOF文件的载入与数据还原

  1. 创建一个不带网络连接的伪客户端。（Redis使用了一个没有网络连接的伪客户端来执行AOF文件的写命令）
  2. 从AOF文件中分析并读取一条写命令
  3. 伪客户端执行被读出的写命令

AOF重写

AOF持久化是通过保存被执行的写命令来记录数据库状态的，随着服务器运行时间的流逝，AOF文件的内容会越来越多。

为了解决AOF文件体积膨胀的问题，需执行AOF重写。

AOF重写是通过读取服务器当前的数据库状态来实现的。

AOF后台重写

AOF重写会使调用这个函数的线程长时间阻塞。

因为Redis采用单个线程来处理请求，如果被阻塞，将无法处理客户端发来的请求。

所以Redis决定将AOF重写程序放到子进程执行，目的

  • 子进程进行AOF重写期间，服务器进程可以继续处理命令请求
  • 子进程带有服务器进程的数据副本，使用子进程而不是线程,可以在避免使用锁的情况下，保证数据的安全性。

问题：子进程在AOF重写期间，服务器会继续处理命令请求，从而使得服务器当前的数据库状态与重写后的AOF文件不一致。

解决方法：Redis设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程后开始使用，当Redis服务器执行完一个写命令后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区

服务器

复制

用户可执行SLAVEOF让一个服务器去复制另一个服务器

旧版复制功能

实现

命令传播

主服务器执行了命令后，会将命令传播给从服务器，使主从服务器再次回到一致状态

缺陷

(因为断线重连后，从服务器重新向主服务器发送SYNC命令，需要把整个流程再走一遍)

新版复制功能

Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作。

PSYNC命令具有完整重同步和部分重同步两种模式

  • 完整重同步用于处理初次复制情况，和SYNC命令基本一样
  • 部分重同步用于处理断线后重复制情况。从服务器断线重连后，如果条件允许，主服务器可以将断开期间执行的写命令发送给从服务器，然后从服务器执行这些写命令。

部分重同步的实现

复制偏移量
复制积压缓冲区

当主服务器进行命令传播时，它不仅会将写命令发送给所有的，还会将写命令入队到复制积压缓冲区里面。

因此，复制积压缓冲区会保存一部分最近传播的写命令，为队列中每个字节记录相应的复制偏移量。

当从服务器重新连上主服务器，从服务器会通过PSYNC命令将自己的复制偏移量发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作。

  • 如果offset偏移量之后的数据仍然存在于复制积压缓冲区，则主服务器对从服务器执行部分重同步。
  • 否则，执行完整重同步。
服务器运行ID

每个Redis服务器都有自己的运行ID

心跳检测

Sentinel

初始化服务器

获取主服务器信息

获取从服务器信息

创建连向其他Sentinel的命令连接

检查主观下线状态

检查客观下线状态

选举领头Sentinel

当一个主服务器被判断为客观下线时，监视这个下线服务器的各个Sentinel会进行协商，选举出一个领头Sentinel，并由领头Sentinel对下线服务器进行故障转移操作。

故障转移

选举出领头Sentinel后，领头sentinel将对已下线的主服务器进行故障转移操作。

Lua脚本

伪客户端

EVAL命令的实现

EVALSHA命令的实现

慢查询日志

监视器