Skip to content

Latest commit

 

History

History
373 lines (207 loc) · 30.3 KB

2019-03-17.md

File metadata and controls

373 lines (207 loc) · 30.3 KB
Raw

Redis 设计与实现

《Redis 设计与实现》这本书是一位 90 后的大佬写的，他叫黄健宏，在国内 Redis 业界算是一位比较有名的人物了。

这应该是我看过的较为通俗易懂的一本技术类书籍了。虽然是 2014 年出版，距离现在有好几年时间了，而近几年 Redis 也还在不断发展、增添新特性，但总体来说本书知识点还算比较全面（基于 Redis 3.0 版本）。读这本书，可以复习到基本的数据结构知识点，也能深入了解 Redis 底层运行原理。

以下是我的一些读书笔记。

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

C 字符串和 SDS 之间的区别

区别有以下 5 个。

  1. SDS 有 len 属性，能在 O(1) 时间内获取字符串长度。
  2. SDS 有 free 属性，能在扩展字符串的时候做检查，空间不足时分配新的空间，避免缓冲区溢出。
  3. SDS 能减少由于字符串变化而导致的内存空间重分配次数，主要是通过预分配和惰性释放实现。扩展时若 len < 1M，那么会多分配 len 的空间，也就是 free 的值与 len 一致，若 len >= 1M，那么会多分配 1M 的空间。缩减时，不会释放空间，而是通过提供 API，让我们在需要的时候去手动释放，这样能减少内存空间重分配的次数。
  4. SDS 是二进制安全的，数据以二进制的方式存储在 buf 数组，可以存储多种类型的数据。
  5. SDS 的 buf 数组采用与 C 字符串一样的方式，以 '\0' 结尾，这样可以复用 C 部分字符串函数。

链表和链表节点的实现

redis 的链表 list 是双端无环链表，有头指针和尾指针（每个链表节点 listNode 都有 prev 和 next 指针，方便从前往后、从后往前遍历），len 属性记录了链表节点的个数，采用了多态方式 void* 指针来保存节点的值，因此 redis 的链表可以保存各种不同类型的值。

字典

redis 使用 dict 作为 db 的底层实现，通过对 dict 的操作来实现 db 的增删改查。

Redis 的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

当达到一定的阈值（e.g. 键值对数量较多，或者值的长度较大）时，使用 dict 作为哈希键的底层实现。本书后面还会提到压缩列表 ziplist，也是哈希键的一种底层实现。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现。

这里来捋一下。

redis 中的 dict 是 hash 键的底层实现之一，而 dict 的底层又是采用 hash 表。 hash 表 dictht 包含了一个 dictEntry 数组，size 记录了 hash 表的大小，sizemask 始终等于 size-1，还有一个 used 记录了已有节点的数量。 hash 表节点 dictEntry 很明显是一个键值对对象，另外还有一个 next 指针，指向下一个 dictEntry，通过指针连接在一起，可以解决键冲突的问题。

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

首先，先计算 key 的 hash 值，然后与 sizemask 按位与，得到索引值。即 idx = key.hash & sizemask。 这里 sizemask 始终等于 size-1，而 size 的值必须是 2 的 幂次方。比如 size=16，那么掩码 sizemask=15，二进制表示就是 01111，这样的话，与 hash 值按位与，也就是对 hash 值的二进制取最后的 4 位。 其实 size 之所以需要是 2 的 幂次方，就是为了确保掩码 sizemask 是 1111 这种形式。如果中间哪一位出现了 0，那么按位与之后，总会导致索引值的一些位始终是 0，这样子索引分布不均，容易造成 hash 冲突。 这里不采用 hash % size 的方式，是为了加快计算的速度，Java 中的 hashmap 同样采用了这种方式。

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为 O（1））

对于扩展操作，假设 ht[0].used = 20，那么第一个大于等于 20*2(即 40) 的 2^n 数字就是 64。

如果执行的是扩展操作，那么 ht[1]的大小为第一个大于等于 ht[0].used*2 的 2^n）；

对于收缩操作，假设 ht[0].used = 20，那么第一个大于等于 20 的 2^n 数字就是 32。

如果执行的是收缩操作，那么 ht[1]的大小为第一个大于等于 ht[0].used 的 2^n。

哈希表扩容与缩容的规则：

  1. 当服务器没有在执行 BGSAVE or BGREWRITEAOF 命令，且负载因子大于等于 1 的时候自动扩容；
  2. 当服务器在执行 BGSAVE or BGREWRITEAOF 命令，且负载因子大于等于 5 的时候自动扩容；
  3. 当负载因子小于 0.1 的时候自动缩容。

数据量过大，若一次性全部进行 rehash，可能导致服务器在一段时间停止服务，影响性能。

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面，但是，这个 rehash 动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

因为在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

跳跃表

跳跃表每个节点可以有多个 Level，从底向上是 L1~Ln，理想情况下，上层元素个数是下层元素个数的 1/2。遍历时，从上层元素遍历下个节点，找不到则跳到下层去遍历。插入元素的时候，从 L1 层插入，至于上层元素插不插，可以用概率的方式，尽量确保上层个数是下层个数的 1/2 就好。

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

和链表、字典等数据结构被广泛地应用在 Redis 内部不同，Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在 Redis 里面没有其他用途。

幂次定律，就是二八法则，重要的东西占少数。大小与出现的次数成反比，数越大，次数越少。

每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。

整数集合

来了个类型较大的，那么整数集合先前所有元素的类型都会升级成为类型最大的那个。

根据整数集合的升级规则，当向一个底层为 int16_t 数组的整数集合添加一个 int64_t 类型的整数值时，整数集合已有的所有元素都会被转换成 int64_t 类型，所以 contents 数组保存的四个整数值都是 int64_t 类型的

整数集合如何升级？看个具体例子。集合原先有 1、2、3，来了个很大的，需要先扩展空间至能存放下升级后的所有元素。之后 3、2、1 依次按照顺利放到对应位置，最后把新来的那个大元素放在最后的一个位置上。

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

一旦升级，就回不去了。

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表

Redis 决定是否应用压缩列表作为当前数据结构的编码，依赖于一个开关和阈值。开关用来决定是否启用压缩列表，阈值通常指当前结构存储的 key 数量有没有达到一个数值，或者 value 值是否达到一定长度。 不同场景应用不同策略，因为压缩列表新增、删除操作的平均复杂度为 O(N)，随着 N 的增大，时间必然增加，不像 hash 表可以在 O(1) 时间找到存取位置。

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现

将数据压缩在一个连续的内存块，可以防止内存碎片的产生，从而减少内存空间的浪费，节约内存。

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

注意，zllen 固定是两个字节 2^16=65536 长度，表示压缩列表包含的节点个数。源码中指出，当节点个数大于 2^16-2 的时候，该值将无效，此时需要遍历列表来计算节点的个数。

zllen

对于五字节长的字节数组，似乎并不是简单去掉最高两位，因为 5*8-2 = 38，而实际上长度 4,294,967,295 的字节数组，是 2^32，也就是只使用了后面的 32 位。

数组的长度由编码除去最高两位之后的其他位记录

对象

通过 encoding 属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了 Redis 的灵活性和效率，因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

电子书这里写错了，原书是以 39 字节划分 raw 和 embstr 的。 但在 redis 3.2 之后，不再以 39 字节为界了，而是 44 字节。

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为 raw。

int 编码的字符串，如果添加了非整数字符串，那么字符串对象会从 int -> raw。 redis 没有为 embstr 编写修改程序，所以，当对 embstr 执行修改操作时，比如 append，那么字符串对象会从 embstr -> raw。

编码的转换

embstr 编码的字符串对象在执行修改命令之后，总会变成一个 raw 编码的字符串对象。

在 redis 3.2 版本之后，列表的底层统一采用 quicklist 实现。

我们仍然可以把 quicklist 看作是一个双向列表，但是列表的每个节点都是一个 ziplist，其实就是 linkedlist 和 ziplist 的结合。 以下使用 redis 3.2 版本进行测试。

127.0.0.1:6379> RPUSH blah "hello" "world" "again"
(integer) 3
127.0.0.1:6379> OBJECT ENCODING blah
"quicklist"

当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码

同时满足以下两个条件的 hash 对象，采用压缩列表作为底层实现：

  1. 所有键和值的字符串长度均小于 64 字节
  2. 键值对数量少于 512 个。

否则采用 hashtable 作为底层实现。

当哈希对象可以同时满足以下两个条件时，哈希对象使用 ziplist 编码

当集合对象可以同时满足以下两个条件时，对象使用 intset 编码：

  1. 集合对象保存的所有元素都是整数值；
  2. 集合对象保存的元素数量不超过 512 个。

不能满足这两个条件的集合对象需要使用 hashtable 编码。

为什么 zset 要使用跳跃表和字典两种结构？跳跃表简化了 zrank，zrange 等范围查找操作；而字典能在 O(1) 时间获取某个 key 对应的 score。

理论上，有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。举个例子，如果我们只使用字典来实现有序集合，那么虽然以 O（1）复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作——比如 ZRANK、ZRANGE 等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少 O（NlogN）时间复杂度，以及额外的 O（N）内存空间（因为要创建一个数组来保存排序后的元素）。

另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从 O（1）上升为 O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码：

  1. 有序集合保存的元素数量小于 128 个；
  2. 有序集合保存的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

初始化时，创建 0-9999 这 1w 个字符串对象，使用的时候，直接引用这些对象就好了，并将引用计数 +1。

目前来说，Redis 会在初始化服务器时，创建一万个字符串对象，这些对象包含了从 0 到 9999 的所有整数值，当服务器需要用到值为 0 到 9999 的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。

typedef struct redisObject {
    unsigned type:4; // 类型
    unsigned encoding:4; // 编码
    unsigned lru:REDIS_LRU_BITS; // 对象最后一次被访问的时间
    int refcount; // 引用计数
    void *ptr; // 指向实际值的指针
} robj;

除了前面介绍过的 type、encoding、ptr 和 refcount 四个属性之外，redisObject 结构包含的最后一个属性为 lru 属性，该属性记录了对象最后一次被命令程序访问的时间。

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

redisClient 中有指向 db 指针，表示当前正在使用的数据库，SELECT 命令就是通过修改 redisClient.db 的指针，让它指向服务器中的不同数据库，从而实现数据库的切换。

通过修改 redisClient.db 指针，让它指向服务器中的不同数据库，从而实现切换目标数据库的功能——这就是 SELECT 命令的实现原理。

SETEX 命令可以在设置一个字符串键的同时为键设置过期时间，因为这个命令是一个类型限定的命令（只能用于字符串键）

PERSIST 命令就是 PEXPIREAT 命令的反操作： PERSIST 命令在过期字典中查找给定的键，并解除键和值（过期时间）在过期字典中的关联。

创建一个定时器需要用到 Redis 服务器中的时间事件，而当前时间事件的实现方式——无序链表，查找一个事件的时间复杂度为 O（N）——并不能高效地处理大量时间事件。

在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的 expires 字典中随机检查一部分键的过期时间，并删除其中的过期键。

SAVE 命令是执行一个同步保存的操作，将当前 redis 实例的所有数据快照以 RDB 形式保存到磁盘，期间服务器不能处理客户端的任何请求；BGSAVE 命令执行后立刻返回，然后 redis fork 出一个新的子进程，原来的 redis 进程继续处理客户端请求，而子进程则将数据保存到磁盘。

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

RDB 文件保存在磁盘上，启动 redis 时，服务器会将磁盘上的 RDB 加载进内存。如果服务器是以主服务器模式运行，就只会加载未过期的键；如果是以从服务器模式运行，就会加载所有键，即便某些键已经过期了。

启动 Redis 服务器时，如果服务器开启了 RDB 功能，那么服务器将对 RDB 文件进行载入

写命令不断写入 AOF 文件中，AOF 文件会越来越大，所以 redis 引入 AOF 重写机制来压缩 AOF 文件。 AOF 文件的压缩主要是去除 AOF 中的无效命令。比如，a. 同一个 key 的多次写入操作只保留最后一个命令；b. 已删除、已过期的 key 的写命令不再保留。

AOF 重写

RDB 持久化

BGSAVE 命令执行期间，其它的 SAVE or BGSAVE 都会被拒绝，因为 SAVE、BGSAVE 都会调用 rdbSave 函数，从而产生竞争。BGSAVE 执行期间，若有 BGREWRITEAOF 命令，则 BGREWRITEAOF 会延后(等 BGSAVE 执行完)执行；而如果在 BGREWRITEAOF 执行期间，BGSAVE 命令会被拒绝。虽然它们其实是在不同的子进程中执行，互不影响，但并发写操作过多会影响功能。

在 BGSAVE 命令执行期间，服务器处理 SAVE、BGSAVE、BGREWRITEAOF 三个命令的方式会和平时有所不同。

每隔 100ms 检查是否该执行 BGSAVE 命令了。

Redis 的服务器周期性操作函数 serverCron 默认每隔 100 毫秒就会执行一次，该函数用于对正在运行的服务器进行维护，它的其中一项工作就是检查 save 选项所设置的保存条件是否已经满足，如果满足的话，就执行 BGSAVE 命令。

如果字符串的长度小于等于 20 字节，那么这个字符串会直接被原样保存。如果字符串的长度大于 20 字节，那么这个字符串会被压缩之后再保存。

AOF 持久化

appendfsync 的配置不同，决定了何时将操作系统级别的缓存同步（或者称为“刷新”）到 AOF 文件中。 对于 flushAppendOnlyFile 函数来说，都会先将 aof_buf 缓冲区的内容“写入”操作系统级别的缓存(OS Cache)，然后再根据 appendfsync 配置的时间，到点了就将 OS Cache 的数据“同步”到 AOF 文件中。 简单来说，就是写入操作系统缓存，再同步到 AOF 文件。后文作者再次提到了文件的写入和同步，可以好好看看。

flushAppendOnlyFile 函数的行为由服务器配置的 appendfsync 选项的值来决定。

就是说，当我在忙的时候，先别来打扰我，你的事先放一边，等我处理完后，再来处理你这个。

在执行 BGREWRITEAOF 命令时，Redis 服务器会维护一个 AOF 重写缓冲区，该缓冲区会在子进程创建新 AOF 文件期间，记录服务器执行的所有写命令。当子进程完成创建新 AOF 文件的工作之后，服务器会将重写缓冲区中的所有内容追加到新 AOF 文件的末尾，使得新旧两个 AOF 文件所保存的数据库状态一致。最后，服务器用新的 AOF 文件替换旧的 AOF 文件，以此来完成 AOF 文件重写操作。

事件

Reactor 模式就是基于事件驱动的模型，适用于多个客户端并发向服务端请求服务的场景。服务端会将请求分派给不同的事件处理器来处理。

Reactor 模式

整个过程是这样的。

首先，要明确客户端与服务端是通过 socket 也就是套接字进行通信的。客户端 socket 请求与 redis 服务端建立连接，服务端 server socket 会产生 AE_READABLE 事件，由于前面 redis 初始化的时候，已经将 AE_READABLE 事件与连接应答处理器关联，所以连接应答处理器对该事件进行处理，并创建一个客户端套接字 socket1 用于与客户端 socket 进行通信，同时将 socket1 的 AE_READABLE 事件与命令请求处理器关联。

客户端 socket 向服务端发起一次写请求的时候，服务端 socket1 产生 AE_READABLE 事件，由于前面的关联，命令请求处理器处理该请求，并将 socket1 的 AE_WRITEABLE 事件与命令回复处理器关联。

在客户端 socket 准备好接收回复时，服务端 socket1 产生 AE_WRITEABLE 事件，命令回复处理器处理该事件，将回复写入 socket1，解除 socket1 与命令回复处理器的关联。socket1 将回复传回客户端 socket。 说明一下，上面过程忽略了 IO 多路复用程序、队列与事件分派器，实际上这一块比较容易理解。IO 多路复用程序监听多个服务端 socket，产生事件的 socket 会进入队列中，一个个传给事件分派器，事件分派器根据事件类型，选择对应的事件处理器进行处理。

一次完整的客户端与服务器连接事件

说白了，就是先等待/处理文件事件，如果在处理文件事件的过程中，时间事件到点了、该处理了，也是等当前文件事件处理完再处理时间事件。所以，时间事件的处理通常比设定的时间晚一丢丢。

一次完整的事件调度和执行过程

客户端

目前 Redis 服务器会在两个地方用到伪客户端，一个用于载入 AOF 文件并还原数据库状态，而另一个则用于执行 Lua 脚本中包含的 Redis 命令。

服务器

就是记录那些执行时间较长的命令(“慢操作”)

慢查询日志功能

就是累加数组每一项(每次取样结果)，然后除以数组的长度来求平均值。

当客户端执行 INFO 命令时，服务器就会调用 getOperationsPerSecond 函数，根据 ops_sec_samples 环形数组中的抽样结果，计算出 instantaneous_ops_per_sec 属性的值

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

Sentinel

Sentinel 需要通过接收主服务器或者从服务器发来的频道信息来发现未知的新 Sentinel，所以才需要建立订阅连接，而相互已知的 Sentinel 只要使用命令连接来进行通信就足够了。

多个 Sentinel 设置的主观下线时长可能不同。 down-after-milliseconds 选项另一个需要注意的地方是，对于监视同一个主服务器的多个 Sentinel 来说，这些 Sentinel 所设置的 down-after-milliseconds 选项的值也可能不同，因此，当一个 Sentinel 将主服务器判断为主观下线时，其他 Sentinel 可能仍然会认为主服务器处于在线状态。

这个 leader 的选举有点意思。如果有多个 sentinel 都判定某个主服务器为客观下线，它们就会参与 leader 的竞选。

每个参与竞选的 sentinel 都希望自己能成为其它 sentinel 的局部 leader。因为其它每个 sentinel 只有一次设置局部 leader 的机会，竞选 leader 的 sentinel 先到了，那么好，局部 leader 这一票给你。其它 sentinel 后续到了，对不起，名额没了。

最后，每个竞选的 sentinel 会统计自己获得的局部 leader 的票数，若超过半数，那么它就成为了真正的 leader，执行后续的故障转移。

如果此次没有任何一个 sentinel 能获得超过半数的票，则重新竞选。

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

sentinel leader 如何从一堆从服务器中挑出一个成为新的 master？淘汰的规则有三个。

  1. 已经宕机或处于断线状态的干掉。
  2. 最近 5s 内没回复 leader 我 INFO 命令的干掉。
  3. 与主机的连接断开时间超过 down-after-milliseconds*10ms 的干掉。

再从剩余的从服务器中选出优先级最高的一个。

新的主服务器是怎样挑选出来的

在一般情况下，Sentinel 以每十秒一次的频率向被监视的主服务器和从服务器发送 INFO 命令，当主服务器处于下线状态，或者 Sentinel 正在对主服务器进行故障转移操作时，Sentinel 向从服务器发送 INFO 命令的频率会改为每秒一次。

集群

redisClient 结构和 clusterLink 结构都有自己的套接字描述符和输入、输出缓冲区，这两个结构的区别在于，redisClient 结构中的套接字和缓冲区是用于连接客户端的，而 clusterLink 结构中的套接字和缓冲区则是用于连接节点的。

必须把 16384 个槽指派给集群中的一个或者多个节点后，集群才会进入上线状态。

槽指派

节点使用以下算法来计算给定键 key 属于哪个槽：

def slot_number(key):
    return CRC16(key) & 16383

在写这篇文章的时候，集群模式的 redis-cli 并未支持 ASK 自动转向，上面展示的 ASK 自动转向行为实际上是根据 MOVED 自动转向行为虚构出来的。因此，当集群模式的 redis-cli 真正支持 ASK 自动转向时，它的行为和上面展示的行为可能会有所不同。

REDIS_NODE_PFAIL

集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点，然后对这五个节点中最长时间没有发送过 PING 消息的节点发送 PING 消息，以此来检测被选中的节点是否在线。

集群节点数较多时，用 Gossip 协议进行消息互通会存在延迟，而 FAIL 消息可以让集群所有节点立即知道某个主节点下线了。

在集群的节点数量比较大的情况下，单纯使用 Gossip 协议来传播节点的已下线信息会给节点的信息更新带来一定延迟，因为 Gossip 协议消息通常需要一段时间才能传播至整个集群，而发送 FAIL 消息可以让集群里的所有节点立即知道某个主节点已下线，从而尽快判断是否需要将集群标记为下线，又或者对下线主节点进行故障转移。

实际上，要让集群的所有节点都执行相同的 PUBLISH 命令，最简单的方法就是向所有节点广播相同的 PUBLISH 命令，这也是 Redis 在复制 PUBLISH 命令时所使用的方法，不过因为这种做法并不符合 Redis 集群的“各个节点通过发送和接收消息来进行通信”这一规则，所以节点没有采取广播 PUBLISH 命令的做法。

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

pubsub_channels 字典中，key 是某个被订阅的频道，value 是订阅这个频道的客户端，以链表形式串起来。新订阅了频道的客户端会挂在链表尾部；退订时，从链表删除该客户端，删除客户端后的链表若无任何客户端退订，程序会将频道这个 key 从字典中删除。

Redis 将所有频道的订阅关系都保存在服务器状态的 pubsub_channels 字典里面，这个字典的键是某个被订阅的频道，而键的值则是一个链表，链表里面记录了所有订阅这个频道的客户端

这样的话，当有多个 client 订阅了同一个模式的话，其实是会创建多个 pubsubPattern 节点的，这些节点有相同 pattern 属性，client 则不同。

pubsub_patterns 属性是一个链表，链表中的每个节点都包含着一个 pubsub Pattern 结构，这个结构的 pattern 属性记录了被订阅的模式，而 client 属性则记录了订阅模式的客户端

事务

我的理解，如果前面命令入队的过程中，有出现错误，即 命令不符合格式要求，比如，原本需要 GET value，而你却只输入 GET，那么事务中的所有命令都不会执行；如果都能成功入队，那么之后的命令执行结果互不影响，即便有排在前面的命令执行错误了，也不影响后面命令的正常执行。比如你对字符串 key 执行 rpush 操作 RPUSH key value，这条命令可以入队，但执行会出错，而即便出错了，也会接着执行事务内的后续命令，不做回滚。

Redis 的作者在事务功能的文档中解释说，不支持事务回滚是因为这种复杂的功能和 Redis 追求简单高效的设计主旨不相符，并且他认为，Redis 事务的执行时错误通常都是编程错误产生的，这种错误通常只会出现在开发环境中，而很少会在实际的生产环境中出现，所以他认为没有必要为 Redis 开发事务回滚功能。

Lua 脚本

为了消除这些命令带来的不确定性，服务器会为 Lua 环境创建一个排序辅助函数rediscompare_helper，当 Lua 脚本执行完一个带有不确定性的命令之后，程序会使用 rediscompare_helper 作为对比函数，自动调用 table.sort 函数对命令的返回值做一次排序，以此来保证相同的数据集总是产生相同的输出。

如果某个脚本所对应的函数在 Lua 环境中被定义过至少一次，那么只要记得这个脚本的 SHA1 校验和，服务器就可以在不知道脚本本身的情况下，直接通过调用 Lua 函数来执行脚本，这是 EVALSHA 命令的实现原理

Redis 要求主服务器在传播 EVALSHA 命令的时候，必须确保 EVALSHA 命令要执行的脚本已经被所有从服务器载入过，如果不能确保这一点的话，主服务器会将 EVALSHA 命令转换成一个等价的 EVAL 命令，然后通过传播 EVAL 命令来代替 EVALSHA 命令。

二进制位数组

SETBIT key pos value 命令，表示将第 pos 个位置设置为 value，pos 从自右向左 从 0 开始，value 值为 0 or 1。

SETBIT 命令用于为位数组指定偏移量上的二进制位设置值，位数组的偏移量从 0 开始计数，而二进制位的值则可以是 0 或者 1

慢查询日志

慢查询日志链表使用头插法新增日志节点。

slowlog 链表包含了 id 为 5 至 1 的慢查询日志，最新的 5 号日志排在链表的表头，而最旧的 1 号日志排在链表的表尾，这表明 slowlog 链表是使用插入到表头的方式来添加新日志的。