第二章 简单动态字符串 （SDS）

1、SDS的定义

struct sdshdr {
      // 记录数组中已经使用的字节数控，等于SDS所保存的字符串的长度
      int len;

       // 记录buf数组中未使用的字节数量 
       int free;
       
       // 字节数组，用于保存字符串
       char[] buf;
}

比如，free为0，则表示SDS没有分配任何未使用的空间，len属性位5，则表示这个SDS保存了一个五字节长的字符串，buf的最后一个字符为'\0'，这和c的字符串是一样的；
需要说明的是，在C语言中使用长度为N+1的字符数组来表示长度为N的字符串，最后一个空字符为'\0'，表示字符串结束。

2、SDS和C字符串的区别

2.1 常数复杂度获取字符串长度

对于C字符串来说，因为没有记录字符串长度，所以如果想要知道字符串长度，则需要遍历一次字符串，这个操作的时间复杂度为O(N)，而SDS中的len属性记录了SDS当前字符串的长度，所以可以直接获取，这个操作的时间复杂度是O(1)；而且SDS的len属性是在操作SDS API的时候自动完成的，不需要自己维护，所以不需要担心安全问题；

2.2 SDS杜绝缓冲区溢出

因为C字符串不记录自身长度的原因，所以容易造成缓冲区溢出，比如，有两个字符串在内存中紧挨着：

...   R E D I S \0 M O N G O D B \0 ...

其中S1为字符串 “REDIS”，s2为字符串 “MONGODB”，C语言中有个字符串操作函数 strcat(char* dest, har* src) 可以将src字符串拼接到dest字符串的后面，如果dest剩余的内存空间无法再容纳src，则就会发生缓冲区溢出，比如执行：
strcat(S1, "CLUSTER")，内存中的S2字符串就会被覆盖掉：

...   R E D I S  C L U S T E R \0 ...

而SDS在进行字符串修改之前，会先检查SDS的空间是否满足修改所需的空间要求，如果不满足，则会先扩展SDS的空间，然后再进行修改。

2.3 SDS减少修改字符串时带来的内存重分配次数

对于C字符串来说，将字符串变长或者缩短之前，都需要进行内存重新分配，否则会出现问题，如果字符串变长之前不进行内存重新分配，则会出现缓冲区溢出问题，如果在缩短字符串之前不进行内存重分配，则会发生内存泄漏问题；

SDS使用free属性来代表buf中还有多少字符可以使用，SDS使用空间预分配和惰性空间释放策略来避免这个问题；

2.3.1 空间预分配

SDS在需要对空间进行扩展的时候，会额外扩展一些空间，使用free属性来维护，避免频繁分配内存；额外分配的内存大小由以下公式决定：

• 如果对SDS进行修改之后，SDS的长度（len属性）将小于1MB，那么程序将分配和len属性同样大小的未使用空间，比如，在SDS进行修改之后，len属性变为13字节，那么程序也会分配13字节未使用的空间（free属性），此时free和len相等，buf的实际长度为13 + 1 + 13 = 27字节；
• 如果对SDS进行修改之后，SDS的长度大于1MB空间，那么SDS会分配1MB的未使用空间；

2.3.2 惰性空间释放

在SDS字符串进行缩短字符串操作时，SDS并不会执行内存重分配将对于的空间进行回收，而是记录在free属性里面，等待后续字符串扩大时使用，这就避免了字符串造成时的频繁内存操作；当然，如果确认字符串空间已经足够，那么可以调用SDS的API进行内存回收。

2.4 二进制安全

C语言中使用空字符'\0'来表示字符串的末尾，也就是字符串中间不能存在空字符串，否则字符串就会被截断，而对于一些二进制数据，难免会使用到空字符，而C字符串就无法表示这些数据，SDS使用buf来存储字符串，存储的是什么，读出来的就是什么，是二进制安全的表示方式。所以Redis不仅可以保存字符串，还可以保存二进制文件，比如视频、图片等。

2.5 兼容部分C字符串函数

SDS的buf里面存储的字符串依然保持以'\0'结尾的惯例，所以可以使用部分C字符串函数，比如strcat，这样，SDS就不需要再重复编写一遍字符串操作函数了。

第三章 链表

3.1 Redis链表实现的特性

• 双端链表：每个链表节点带有prev和next指针，获取某个节点的前置或者后置节点的时间复杂度为O(1)；
• 无环：表头的prev和表尾的next都指向NULL，对链表的访问以NULL为结尾；
• 带表头指针和表位指针：通过list的head和tail指针，获取表头或者表尾的时间复杂度为O(1)；
• 带链表长度计数器：使用list结构的len属性来表示链表的长度，程序获取链表长度的时间复杂度为O(1)
• 多态：链表的每个节点使用void*指针来保存节点的值，并且通过dup、free、match三个属性为节点设置类型特定函数，所以链表合一用于保存各种不同类型的值；

第四章 字典

字典：又被称为符号表、关联数组、映射（map），是哈希键的底层实现
Redis的字典使用哈希表作为底层实现；

4.1 哈希表

dict.h/dictht

typedef struct dictht {
    
      // 哈希表数组
      dictEntry ** table;

      // 哈希表大小
      unsigned long size;

       // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
       unsigned long sizemask;

       // 该哈希表已有节点的数量
       unsigned long used; 

} dictht;

4.2 哈希表节点

dictEntry 保存键值对信息。

typedef struct dictEntry {
    
      // 键
      void* key;

      // 值
      union {
            void* val;
              ...
       } v;

     // 下一个哈希节点，形成链表，用于解决哈希冲突的问题
     struct dictEntry* next;

} dictEntry;

4.3字典

dict.h/dict

typedef struct dict {
   
      // 类型特定函数
      dictType* type;

      // 私有数据
      void* privdata;

      // 哈希表
      dicthd ht[2];

      // rehash 索引，当rehash不在进行时，值为-1
      int rehashidx;  

} dict;

ht属性是包含两个哈希表的数组，一般情况下，只有ht[0]会被使用，ht[1]只有在rehash的时候才会用到，rehashidx用于标记rehash的进度，如果当前不在进行rehash操作，则rehashidx为-1；

4.4 哈希算法

当要将一个新的键值对添加到字典中时，需要先根据键值对的键来计算出哈希值和索引值，然后根据索引值将包含新键值对的哈希节点放到对应的位置上去；
计算哈希值的函数在字典的type属性里面；
当一个数组的长度是2的幂次方时，有一个很好的特性是，
index = hash & (len -1)
这可能就是sizemask的作用；

4.5 解决键冲突

当有两个以上的键被分配到同一个索引上的时候，称这些键发生了冲突，Redis使用链地址法来解决哈希冲突，每个键值对节点都是一个链表节点，包含next指针；

4.6 rehash

随着操作的不断执行，哈希表保存的键值对会逐渐的增多或者减少，为了让哈希表的负载因子保持在一个合理的范围，当哈希表的键值对太多或者太少时，程序需要进行rehash操作。

Redis进行rehash操作的步骤如下：

• 为字典ht[1]分配空间，分配的大小取决于要执行的操作，和ht[0]当前包含的键值对数量（ht[0].used）
  • 如果执行的扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used * 2 的2次幂；
  • 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2次幂；
• 将保存在ht[0]中的所有键值对rehash到ht[1]上面
• 当ht[0]的所有键值对都rehash到ht[1]之后，释放ht[0]，然后将ht[1]当做ht[0]；

4.7 哈希表的收缩与扩展

当以下条件任意一个满足时，程序会自动开始对哈希表进行扩展操作：

• 服务器目前没有执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；
• 服务器正在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5；

负载因子的计算公式为：
load_factor = ht[0].used / ht[0].size

Redis在执行BGSAVE或者BGREWRITEAOF命令时，需要fork出紫子进程，大多数操作系统采用写时复制的技术来优化进程的内存使用效率，如果在这个时候进行rehash，子进程也需要写，如果避免在这个时候进行扩展，则可以最大限度的节约内存。

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

4.8 渐进式rehash

rehash操作并不是一次性完成的，因为哈希表中的键值对数量可能非常大，如果一次性完成所有键值对的rehash操作，那么Redis可能会停止服务而进行rehash，为了避免这个问题，Redis采用分多次，渐进式的完成rehash操作；

下面是Redis进行渐进式rehash的详细步骤：

• 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
• 在字典中维护一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始；
• 在rehash进行期间，每次对字典的访问操作，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到ht[1]，当rehash完成之后，rehashidx + 1，表示下一次rehash操作的键值对索引是rehashidx + 1
• 随着字典的不断操作，到某个时间点，ht[0]上的所有键值对都会rehash到ht[1]，此时设置rehashidx = -1，表示rehash已经完成；

在rehash期间，字典会同时持有ht[0]和ht[1]两张哈希表，对于查找来说，会现在ht[0]找，找不到再去ht[1]找， 对于删除操作也是需要操作两张哈希表，而对于插入操作，所有新插入的键值对只会在ht[1]里面，所以保证了ht[0]里面的键值对只减不增，这样rehash总是会结束。

第五章 跳跃表

跳跃表是有序列表的底层实现数据结构，Redis的跳跃表实现包括zskiplist和zskiplistNode两个结构，每个跳跃表的层高都是1~32之间的随机数，在同一个跳跃表中，每一个节点的成员变量必须唯一（类似于Set），当多个节点的分值相同时，节点按照成员对象的大小进行排序。

https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
https://juejin.im/post/57fa935b0e3dd90057c50fbc

下面是一个跳跃表图片：

skiplist

查找的时候先从最高层开始找，逐渐二分下降层数，整体上就是一个二分查找算法的最佳实践。

下面是一个再跳跃表里面查找23这个值的例子：

search in skiplist

第六章 整数集合

• 整数集合是集合键的底层实现之一；
• 整数集合的底层实现为数组，这个数组以有序，无重复的方式存储集合元素，当有需要的时候会改变数组的类型（encode）
• 升级操作为整数集合带来了操作上的灵活性，并且尽可能的节约了内存；
• 整数集合只支持升级操作，不支持降级操作

第七章 压缩列表

压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量的列表项，并且每个列表项要么就是小整数值，要么就是简短的字符串，那么Redis就会使用压缩列表来进行实现；
当一个哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数，要么是简短的字符串，那么Redis就会使用压缩列表来实现哈希键。
压缩列表是Redis为了节约内存而开发的一种顺序存储数据结构。

第八章 对象

Redis基于前面介绍的那些数据结构，构建了一个对象系统，这个系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象五种类型的对象。
Redis通过引用计数技术，当程序不再使用某个对象时，这个对象所占用的内存就会被自动释放，还基于引用计数实现了对象共享机制，从而来实现节约内存的目的。
Redis的对象还记录了访问时间，这个信息可以用于计算数据库键的空转时间，空转时间较长的那些对象有可能被服务器删除掉。

8.1 对象类型和编码

Redis使用对象来表示数据库中的键值对，每当我们在数据库中新创建一个键值对时，我们至少会创建两个对象，一个键对象和一个值对象。Redis使用redisObject来表示对象：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    
    // 指向底层实现数据结构的指针
    void *ptr;
} robj;

8.1.1 类型

对象的type属性记录了对象的类型，这个属性值可以是下面几种中的一个：

REDIS_STRING        ：字符串对象
REDIS_LIST              ：列表对象  
REDIS_HASH            ：哈希对象
REDIS_SET               ：集合对象
REDIS_ZSET             ：有序集合对象

在Redis中，键值对的键总是一个字符串对象，而值可以是上面说到的五种对象之一，可以使用TYPE命令来查看一个键值对的值的对象类型。

8.1.2 编码

编码决定了底层实现的数据结构。可以通过OBJECT ENCODING 命令来查看编码信息；Redis没有将一种类型关联到一种特定类型的编码上，极大的提升了Redis的灵活性和效率，Redis可以根据对象的特征进行不同的编码，比如，在一个列表键包含较少的列表项时，Redis就会使用压缩列表来实现，而当压缩列表不再适应的情况下，就会使用列表来实现。

8.2 字符串对象

字符串对象的编码可以是int、raw或者embstr。

• 如果一个字符串保存的是整数值，那么编码就是int；
• 如果字符串对象保存的是一个字符串，并且字符串长度大于32字节，那么就会使用SDS来表示，编码为raw；
• 如果字符串对象保存的是一个长度小于等于32字节的字符串，那么就会使用embstr编码来保存；
• 如果保存的是浮点数，那么也是使用字符串的方式保存；

embstr编码和raw的效果是一样的，但是embstr使用一次内存分配/回收来管理RedisObject结构和sdshdr结构，而raw会调用两次内存分配。并且embstr的redisObject和sdshdr是连续分布的，所以可以更好的利用缓存带来的优势。

8.3 列表对象

列表对象的编码可以是ziplist或者linkedlist。当列表对象可以同时满足下面两个条件时，使用ziplist来保存：

• 列表对象保存的所有字符串长度都小于64字节；
• 列表对象保存的元素数量少于512个；
  如果不能满足这两个对象，则使用linkedlist来实现；对于使用ziplist的列表对象，如果其中一个条件不再满足的时候，就会进行编码转换，转换成使用linkedlist来进行保存。

8.4 哈希对象

哈希对象的编码可以是ziplist或者hashtable，当哈希对象可以同时满足下面两个条件时，使用ziplist，否则使用hashtab：

• 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
• 哈希对象保存的键值对数量小于512个；

8.5 集合对象

集合对象的编码可以是intset、hashtable，当集合对象可以同时满足下面两个条件时，使用intset，否则使用hashtabe：

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

8.6 有序集合对象

有序集合对象的编码可以是ziplist或者skiplist，在Redis中，同时使用了跳跃表和字典来实现有序集合，zset的zsl属性是一个跳跃表，它按照元素的分值从小打到的保存元素，这样就可以实现比如范围操作之类的功能，而zset的dict属性使用字段来存储了集合的成员到分值的映射，这样基于成员查找分值的时间复杂度就是O(1)，同时需要说明的是，Redis使用对象共享技术，所以同时使用跳跃表和字典不会造成内存浪费。

同时使用跳跃表和字典来实现有序集合，主要是为了实现效率上的考虑，如果只使用字典来实现，那么虽然根据成员查询分值的时间复杂度是O(1)，但是因为字典以无序的方式存储元素，所以在执行范围操作的时候，就需要先排序再操作，时间复杂度是O(NlogN)，还要创建一个额外的数组来存储排序后的元素（O(N)），如果只使用跳跃表，那么虽然范围查找没问题，但是基于成员查询分值的操作就会从O(1)提升到O(N)，所以同时使用两种数据结构来实现。

当有序集合对象可以同时满足下面两个条件时，对象使用ziplist来实现，否则使用skiplist来实现：

• 有序集合保持的元素数量小于128个；
• 有序集合保存的所有元素的长度小于64字节；

8.8 内存回收

Redis使用引用计数来实现对象跟踪，对象的引用计数会随着对象的使用而发生变化：

• 在创建一个新对象时，引用计数的值会被初始化为1；
• 当一个对象被一个程序引用时，它的引用计数值会加1；
• 当对象不再被一个程序使用时，它的引用计数会减1；
• 当对象的引用计数变为0时，对象所占用的内存会被释放；

8.9 对象共享

当A和B需要的对象一样时，Redis就会使用对象共享技术，不会创建多个对象，而是会复用现有的对象。Redis只会共享包含整数值的字符串对象，因为其他的字符串对象的对比需要消耗更多的CPU，得不偿失；

8.10 对象的空转时常

每个对象都会记录对象最后一次被访问的时间戳，当执行命令OBJECT IDLETIME时，就是将当前时间减去对象的这个时间戳，需要注意的是，这个命令执行时，对象的lru（最后访问时间戳）不会被更新。空转时间还可以用于Redis服务器淘汰键值对，如果开启了maxmemory选项，并且服务器用于回收内存的算法为valatile-lru或者allkeys-lru时，那么服务器占用的内存数超过maxmemory时，就会将空转时间较长的部分键值对优先释放内存；

第九章 数据库

Redis默认情况下会初始化16个数据库，每个数据库由redisDb结构表示。
每个Redis客户端都会有自己的目标数据库，在客户端执行读写数据库的时候，目标数据库就会成员操作对象。默认情况下，目标数据库为0号数据库，可以通过执行SELECT命令来切换数据库；在服务器内部的redisClient结构的db属性记录了客户端当前的目标数据库，这个属性是指向redisDb结构的指针；

Redis的redisDb结构里面有一个dict属性，它记录了数据库中的所有键值对，我们将这个字段称为键空间。

Redis的redisDb结构中的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典，当执行了为键值对设置过期时间的命令之后，就会在expires字典里面插入一个新的键值对，值为过期时间。当为某个键移除过期时间时，相应的也会在过期字典里面将其删掉。

9.1 过期键删除策略

如果一个键过期了，那么它被删除的策略有三种：

• 定时删除：在设置键的过期时间的同时，设置一个定时器，定时器在键的过期时间来临时，立即删除键；
• 惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查键是否已经过期，如果过期的话，则删除键，否则返回；
• 定期删除：每隔一段时间，就对数据库进行一次检查，删除里面的过期键，至于要删除多少键，以及检查多少个数据库，则由算法决定；

定时删除对内存最优化，那些过期的键都能及时被清理，而如果有大量的键需要清理则对CPU不太友好，需要大量的CPU时间；惰性删除对内存不太友好，但是对CPU友好；定期删除策略是对前两种策略的折中方案：

• 定期删除策略每隔一段时间执行一次过期键删除操作，并通过限制删除操作执行的时常和频率来减少删除操作对CPU时间的影响；
• 除此之外，通过定期删除过期键，可以减少过期键带来的内存浪费；

Redis实际使用的是惰性删除和定期删除两种策略，服务器可以很好的在合理使用CPU和避免内存空间浪费之间取得平衡；

9.1.1 惰性删除策略的实现

过期键的惰性删除由db.c/expireIfNeeded函数实现，所有读写Redis数据库的命令在执行之前都会调用这个函数进行键过期检查；

• 如果输入键已经过期，那么函数将输入键从数据库中删除；
• 如果输入键不过期，那么这个函数什么也不做；

9.1.2 定期删除策略的实现

定期删除由redis.c/activeExpieCycle函数实现，每当Redis的服务器周期性的执行serverCorn函数时，activeExpieCycle函数也会被调用，它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键。

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

9.2.1 生成RDB文件

在执行SAVE或者BGSACE命令时，程序会对数据库中的键进行检查，已经过期的键不会被保存到数据库中；

9.2.2 载入RDB文件

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

• 如果服务器以主服务器模式运行，那么在载入RDB文件时，程序会对保存的键进行检查，未过期的键会被保存到数据库中，而过期的键则会被忽略。
• 如果服务器以从服务器运行，那么在载入RDB文件时，文件中保存的所有键都会被载入到数据库中，不过，因为主服务器在进行数据同步时，从服务器的数据库就会被清空，所以一般来讲对从服务器也没有影响。

9.2.3 AOF文件写入

如果键过期被惰性删除或者定期删除了，那么会向AOF文件写入一条DEL命令，来显示的记录该键已经被删除；

9.2.4 复制

当服务器运行在复制模式下时，从服务器的过期键删除动作由主服务器控制：

• 主服务器在删除一个过期键之后，会显示的向所有从服务器发送一条DEL命令，告诉从服务器删除这个过期键；
• 从服务器没有权利删除过期键，所以从服务器在遇到过期键时不会删除过期键，它会等待主服务器来控制自己。

第十章 RDB持久化

RDB文件会将当前Redis数据库中的所有键值对记录到一个二进制文件中，有两个命令可以生成RDB文件，SAVE和BGSAVE；

SAVE命令会阻塞服务器进程，直到RDB文件生成完成，BGSAVE则会派生出一个子进程来负责生成RDB文件，而主进程依然可以处理Redis的其他命令。RDB文件的载入没有命令，是Redis在启动的时候自动完成的，只要Redis检测到RDB文件，就会自动载入RDB文件到内存，需要注意的是，因为AOF文件的更新频率更高，所以：

• 如果服务器开启了AOF持久化功能，那么服务器会优先使用AOF文件来还原数据库；
• 只有在AOF功能处于关闭状态，服务器才会使用RDB文件来还原数据库；

第十一章 AOF持久化

AOF和RDB不一样，AOF保存的是执行过的命令，Redis会将所有执行过写命令追加到AOF文件中去，启动Redis服务器的时候恢复这个数据库；

AOF分为命令追加、文件写入、文件同步三个部分；

11.1 命令追加

当AOF持久化功能处于打开状态时，服务器在执行完一个命令之后，会按照协议格式将被执行的命令追加到服务器状态的aof_buf缓冲区的末尾；

11.2 文件写入 与同步

Redis的服务器其实就是一个事件循环，包括文件循环和时间循环，服务器在处理文件事件时可能会往aof_buf里面写入内容，所以在每次结束一次循环之前，会调用flushAppendOnlyFile函数，考虑是否需要将aof_buf里面的内容保存到AOF文件里面去。flushAppendOnlyFile函数的行为由appendfasync选项的值来决定：

• always：将aof_buf里面的内容写入并同步到AOF文件；
• everysec：将aof_buf里面的内容写入到AOF文件，如果上次同步aof文件的时间距离现在超过1秒，那么再次对AOF文件进行同步，并且这个事情由一个专门的线程负责；
• no：将aof_buf里面的内存写入到AOF文件，但并不对AOF文件进行同步，何时同步由操作系统决定；

默认为everysec。

11.3 AOF重写

因为AOF持久化是通过保存redis执行的命令来实现的，随着服务器运行，这个文件会越来越大，甚至会影响redis服务器，所以需要重写AOF文件，重写是通过读取redis当前数据库状态来实现的；比如原来一个列表是通过10次添加元素构成的，重写之后只需要一条命令即可，大大缩短了命令的数量。

AOF重写需要执行大量的写入操作，所以这个函数的线程将长时间阻塞，这就会影响redis服务器处理正常的请求，所以AOF重写的任务被设计成一个后台进程来完成；

不过，这里需要注意的是，子进程在进行AOF重写的时候，主进程还在继续处理请求，而新的命令可能会对现有的数据库状态进行变更，从而使得当前的数据库状态和重写后的AOF文件所保存的数据库状态不一致，为了解决这个问题，Redis服务器设置了一个AOF重写缓冲区，这个缓存区在服务器创建子进程之后开始使用，当Redis服务器执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区，当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接收到这个信号之后，会进程信号处理：

• 将AOF重写缓冲区中的内容全部写入到新的AOF文件中；
• 对新的AOF文件进行改名，原子的覆盖原来的AOF文件；

第十二章 事件

Redis服务器是一个事件驱动的程序，服务器需要处理两类事件：

• 文件事件：也就是I/O事件，比如客户端的连接上的读写请求；
• 时间事件：某些操作（比如serverCorn）需要在给定的时间点运行，这就是时间事件；

12.1 文件事件

Redis基于Reactor模式开发了自己的事件处理器，这个处理器被称为文件事件处理器（file event handler）

• 文件事件处理器使用I/O多路复用技术，同时监听多个套接字，并根据套接字目前执行的任务设置不同的事件处理器；
• 当被监听的套接字上有读写事件发生时，文件事件处理器就会调用相应的处理器来处理这些事件；

12.2 时间事件

服务器将所有的时间事件都放在一个无序列表里面，每当时间事件执行器运行时，它就遍历整个列表，查找所有已到达的时间事件，并调用相应的时间处理器。一般情况下服务器只会执行serverCorn一个时间事件。

第十五章 复制

在Redis中，可以执行SLAVEOF命令或者设置slaveof选项，让一个服务器复制另外一个服务器，我们称呼被复制的服务器为主服务器（master），而对主服务器进行复制的则成为从服务器（slave）。

15.1 旧版本复制功能的实现（2.8版本之前）

Redis的复制分为同步（sync）和命令传播（command propagate）两个操作：

• 同步：同步操作用于将从服务器的数据库状态更新至服务器所处的数据库状态；
• 命令传播：命令传播用于在主服务器的数据库状态被修改，导致主从服务器数据库状态不一致时，让主从服务器的数据库重新回到一致状态；

15.1.1 同步（sync）

当客户端向从服务器发送SLAVEOF命令，要求复制主服务器时，从服务器首先需要执行同步操作，首先将从服务器的数据库状态更新到主服务器一致。
从服务器通过向主服务器发送SYNC命令来完成同步操作，以下是SYNC命令的执行步骤：

• 从服务器向主服务器发送SYNC命令；
• 收到SYNC命令的主服务器开始执行BGSAVE命令，在后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有写命令；
• 当主服务器的BGSAVE命令执行完成时，主服务器会将生成的RDB文件发送给从服务器，从服务器接收并载入这个RDB文件；
• 主服务器将记录在缓存区里面的所有写命令发送给从服务器，从服务器执行这些写命令，将自己的状态更新至主服务器当前的状态。

15.1.2 命令传播（command propagate）

当同步操作完成之后，主从服务器两者的数据库状态将达到一致状态，但是这种状态并不是一成不变的，如果主服务器的数据库被改变，则一致就不再存在。

为了让从服务器和主服务器保持一致，主服务器需要对从服务器执行命令传播，主服务器会将自己执行的写命令，也就是会造成主从数据库状态不一致的命令，发送给从服务器执行，当从服务器执行之后，主从数据库状态又会变成一致。

15.2 旧版（2.8版本之前）复制功能的缺陷

在Redis中，从服务器对主服务器的复制可以分为以下两种情况：

• 初次复制：从服务器以前没用复制过任何主服务器，或者从服务器当前要复制的主服务器和上一次复制的主服务器不同；
• 断线后重新复制：处于命令传播阶段的主从服务器因为网络原因中断了复制，但从服务器通过自动重连连接上了主服务器，并继续复制主服务器；

对于初次复制来说，旧版复制功能没有问题，但是对于断线重连后的复制，旧版虽然也可以让主从服务器重新回到一致状态，但是效率却非常低。因为断线重连后从服务器将重新进行同步，执行SYNC命令，这个命令是消除消耗资源的。

15.3 新版复制功能的实现

为了解决旧版复制功能在处理断线重新复制情况下的低效问题，从Redis 2.8开始，使用PSYNC命令进行复制中的同步操作，PSYC命令有完整重同步和部分重同步两种模式：

• 完整重同步用于初次复制的情况：完整重同步和SYNC命令操作基本是一样的；
• 部分重同步用于断线后重复制的情况：当从服务器断线后重新连接到主服务器，如果条件允许，主服务器可以将断线期间执行过的写命令发送给从服务器，就可以将从服务器的数据库更新成和主服务器一致；

15.4 部分重同步实现

部分重同步由三部分组成

• 主服务器的复制偏移量和从服务器的复制偏移量（replication offset）
• 主服务器的复制积压缓冲区（replication backlog）
• 服务器的运行ID（run ID）

15.4.1 复制偏移量

执行复制的双方会分别维护一个复制偏移量：

• 主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量加上N；
• 从服务器每次收到主服务器传播来的N字节数据时，就将自己的复制偏移量加上N；

通过对比主从服务器的复制偏移量，可以很容易的发现主从数据库是否一致：

15.4.2 复制积压缓冲区

复制积压缓冲区是主服务器维护的一个固定长度的FIFO队列，默认大小为1Mb；当主服务器在进行命令传播时，它不仅会将写命令发送给从服务器，还会将写命令入队到复制积压缓冲区里面。

因此，复制积压缓冲区会保持这一部分最近传播的写命令，并且赋值积压缓冲区会为队列中的每个字节记录相应的复制偏移量。当断线后从服务器重新连接上主服务器，从服务器会通过PSYNC命令将自己的复制偏移量发送给主服务器，主服务器会根据这个偏移量来决定执行何种同步：

• 如果offset偏移量之后的数据任然存在于复制积压缓冲区里面，那么主服务器对从服务器执行部分重同步操作；
• 否则，就会执行完整重同步操作，这和SYNC命令是一样的；

15.4.3 服务器运行ID

除了复制偏移量和复制积压缓冲区，还需要服务器运行ID，才能实现PSYNC部分重同步功能；

每个Redis服务器，无论是主服务器还是从服务器，都会有一个自己的运行ID；这个运行ID从服务器启动时自动生成，由40个随机的十六进制字符组成。

当从服务器初次复制主服务器时，主服务器会将自己的运行ID传送给从服务器，而从服务器会将这个ID保存起来。当从服务器断线并重新连接上主服务器时，从服务器向当前连接的主服务器发送这个ID：如果主服务器发现这个ID和自己一样，那么可以执行部分重同步功能，否则说明这是一个新的从服务器，需要执行完整重同步。

15.5 复制的实现

• 设置主服务器的地址和端口
• 和主服务器建立套接字连接
• 向主服务器发送PING命令
• 主服务器进行身份验证
• 从服务器向主服务器发送端口信息
• 同步
• 命令传播
• 心跳检测（每秒一次）
  • 检测主从服务器的网络连接状态
  • 辅助实现min-slaves配置，就是最少需要几个slave（当然还可以配置如果所有的slave的延时都大于多少时）拒绝执行写命令；
  • 检测命令丢失，在网络传输中命令传播可能丢失，通过offset主服务器就会发现这种问题，将数据重传；

第十六章 Sentinel

Sentinel（哨兵）是Redis高可用解决方案，由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器，以及这些主服务器的从服务器，当监视的主服务器下线时，自动将下线主服务器属下的某个从服务器升级为新的主服务器。

当主服务器的下线时长超过用户设定的阈值时，Sentinel系统就会对主服务器进行故障转移操作：

• 首先，Sentinel会挑选出一个故障主服务器下面的其中一个从服务器，并将这个从服务器升级为主服务器；
• 之后，Sentinel系统会向故障主服务器的所有从服务器发送新的复制命令，让他们成为新的主服务器的从服务器，当所有的从服务器都开始复制新的主服务器时，故障转移操作完毕；
• 另外，Sentinel系统还会继续监视已下线的服务器，如果它重新上线，那么会让他成为新的主服务器的从服务器；

16.1 启动并初始化Sentinel

当一个Sentinel启动时，他需要执行以下步骤：

• 初始化服务器

Sentinel本质上只是一个运行在特殊模式下的Redis服务器，所以启动Sentinel的第一步，就是初始化一个普通的Redis服务器，但是不需要像普通Redis服务器那样载入RDB文件之类的操作，因为它不需要使用Redis数据库功能；

• 将普通Redis服务器使用的代码替换成Sentinel专用的代码

• 初始化Sentinel状态

• 根据给定的配置文件，初始化Sentinel的监视主服务器列表

• 创建连向主服务器的网络连接

16.2 获取主服务器信息

Sentinel默认会以十秒一次的频率通过命令连接向被监视的主服务器发送INFO命令，通过分析主服务器返回的INFO命令回复，Sentinel可以获取以下两方面的信息：

• 一方面是关于主服务器本身的信息，比如runID；
• 另一方面是关于该主服务器下的从服务器的信息，根据这些信息，Sentinel就可以自动发现从服务器；

16.3 获取从服务器信息

Sentinel默认也会以十秒一次的频率通过命令通道向从服务器发送INFO命令，获取从服务器的信息。

16.4 向主服务器和从服务器发送信息

在默认情况下，Sentinel会以每两秒一次的频率，通过命令连接，向所有被监视的Redis服务器发送一个命令，向服务器的sentinel:hello频道发送一条信息；

16.5 接收来自被监视服务器的频道信息

Sentinel不仅会向所有被监视的Redis服务器发送频道信息，还会接收频道信息，如果一个Redis服务器被多个Sentinel实例监视，那么一个Sentinel向某个被监视的Redis服务器发送的频道信息，会被其他所有监视这个Redis服务器的Sentinel实例接收到，这些Sentinel接收到不是自己发送的频道信息之后，会对其他Sentinel发送的频道信息进行解析；

16.5.1 更新sentinels字典

Sentinel为主服务器创建的sentinels字段保存了所有监视这个Redis服务器的Sentinel的资料：

• sentinels字典的键是Sentinel的名字，格式为ip:port
• sentinels字典的值是对应的Sentinel实例结构

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

当Sentinel通过频道信息发现一个新的Sentinel时，不仅会在sentinels 字典中未该Sentinel创建相应的实例结构，还会创建一个连接到这个Sentinel的命令连接，最终监视同一个Redis服务器的所有Sentinel实例会成为一个网状结构；

16.6 检测主观下线状态

默认情况下，Sentinel会以每秒一次的频率向所有它创建了命令连接的实例（包括主从服务器，其他Sentinel）发送PING命令，并通过实例返回来判断实例是否在线；

在Sentinel配置文件中有一个配置：down-after-milliseconeds，如果一个实例在down-after-milliseconeds毫秒后依然没有返回有效的PING回应，那么Sentinel就会判断该实例为下线；

16.7 检测客观下线状态

当Sentinel将一个主服务器判断为主观下线后，为了确认这个服务器是否真的下线，它会询问所有监视这个服务器的Sentinel，看看其他Sentinel是否也认为这个服务器已经下线，如果从其他Sentinel那里得到了足够数量的下线判断后（这个数量是配置的），Sentinel就会认为服务器为客观下线，并会对该主服务器进行故障转移操作。不同的Sentinel对主服务器的下线判断可能不一样，这个是因为不同的Sentinel配置可能是不一样的。

16.8 选举领头Sentinel

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

• 所有在线的Sentinel都有资格成为领头Sentinel；
• 每次选举之后，不论选举是否成功，所有Sentinel的纪元都会增加1（一个计数器）
• 每个发现主服务器进入客观下线的Sentinel都会要求别人选举自己成为领头
• 最想向目标Sentinel发送选举自己要求的Sentinel将获得选举，其他后来的选举要求将被目标Sentinel拒绝；
• 如果某个Sentinel被半数以上的Sentinel设置为leader，那么这个Sentinel将成为leader；
• 如果在给定的时间内没有选举出一个领头Sentinel，那么就会过一段时间再继续选举，直到产生leader；

16.9 故障转移

在选举产生领头Sentinel之后，领头Sentinel就会对已下线的主服务器执行故障转移操作：

• 在已下线的主服务器的所有从服务器里，挑选出一个从服务器，并将其转换为新的主服务器；
• 让已下线的主服务器的所有从服务器改为复制新的主服务器；
• 将已下线服务器作为新的主服务器的从服务器，当这个旧的主服务器开始重新上线时，他就会成为新的主服务器的从服务器；

16.9.1 选出新的主服务器

故障转移的第一步就是需要在故障的主服务器的所有从服务器中挑选一个状态良好、数据完整的从服务器，然后向这个从服务器发送SLAVEOF no one命令，将这个从服务器转换成主服务器；

领头Sentinel会将已下线的Sentinel服务器的所有从服务器保存在一个列表里面，然后按照下面的规则过滤：

• 删除列表中出于下线或者断线状态的服务器，保证剩余的从服务器都是正常在线的；
• 删除列表中所有最近五秒内没有回复过领头Sentinel的INFO命令的从服务器，保证剩余的从服务器都是最近成功进行过通信的；
• 删除所有与已下线服务器连接断开超过 down-after-milliseconds * 10 毫秒的从服务器，保证剩余的从服务器没有过早的与主服务器断开连接，也就是保证剩余的从服务器保存的数据都是比较新的；

之后，领头Sentinel对列表中剩余的从服务器进行优先级处理，取得优先级最高的一个从服务器，称为最终被挑选出来的从服务器。

排序的规则是：

首先看服务器优先级，然后是复制偏移量，最后是服务器运行ID；

16.9.2 修改从服务器的复制目标

16.9.3 将旧的主服务器变为从服务器

最后，需要注意的是，Sentinel只会和主服务器和从服务器创建命令连接和订阅连接，Sentinel之间则只创建命令连接。

第十七章 集群

Redis集群是Redis提供的分布式解决方案，复制（replication）提供了主从数据库方案，Sentinel提供了高可用（故障转移）方案，而Redis集群则在此基础上提供了负载均衡（通过分片）的分布式方案。

集群主要包括下面一些内容：节点、槽指派、命令执行、重新分片、转向、故障转移、消息等；

17.1 节点

一个Redis集群由多个节点组成（node），在刚开始的时候，每个节点都是相互独立的，他们都处于一个只包含自己的集群当中，我们可以通过CLUSTER MEET <ip> <port> 命令来完成这个工作，当向一个节点执行这个命令时，可以让当前节点将ip和port所代表的节点添加到当前集群中；

一个节点就是一个运行在集群模式的Redis服务器，Redis服务器会在启动的时候根据cluster-enbale配置是否为yes来确定是否开启集群模式；集群模式的Redis服务器依然会继续使用单机模式下的Redis服务器组件，比如复制等功能；

clusterNode结构是一个节点的数据结构：

typedef struct clusterNode {
    mstime_t ctime; /* Node object creation time. */
    char name[CLUSTER_NAMELEN]; /* Node name, hex string, sha1-size */
    int flags;      /* CLUSTER_NODE_... */
    uint64_t configEpoch; /* Last configEpoch observed for this node */
    unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */
    int numslots;   /* Number of slots handled by this node */
    int numslaves;  /* Number of slave nodes, if this is a master */
    struct clusterNode **slaves; /* pointers to slave nodes */
    struct clusterNode *slaveof; /* pointer to the master node. Note that it
                                    may be NULL even if the node is a slave
                                    if we don't have the master node in our
                                    tables. */
    mstime_t ping_sent;      /* Unix time we sent latest ping */
    mstime_t pong_received;  /* Unix time we received the pong */
    mstime_t fail_time;      /* Unix time when FAIL flag was set */
    mstime_t voted_time;     /* Last time we voted for a slave of this master */
    mstime_t repl_offset_time;  /* Unix time we received offset for this node */
    mstime_t orphaned_time;     /* Starting time of orphaned master condition */
    long long repl_offset;      /* Last known repl offset for this node. */
    char ip[NET_IP_STR_LEN];  /* Latest known IP address of this node */
    int port;                   /* Latest known clients port of this node */
    int cport;                  /* Latest known cluster port of this node. */
    clusterLink *link;          /* TCP/IP link with this node */
    list *fail_reports;         /* List of nodes signaling this as failing */
} clusterNode;

每个节点都保存这一个clusterState：

typedef struct clusterState {
    clusterNode *myself;  /* This node */
    uint64_t currentEpoch;
    int state;            /* CLUSTER_OK, CLUSTER_FAIL, ... */
    int size;             /* Num of master nodes with at least one slot */
    dict *nodes;          /* Hash table of name -> clusterNode structures */
    dict *nodes_black_list; /* Nodes we don't re-add for a few seconds. */
    clusterNode *migrating_slots_to[CLUSTER_SLOTS];
    clusterNode *importing_slots_from[CLUSTER_SLOTS];
    clusterNode *slots[CLUSTER_SLOTS];
    uint64_t slots_keys_count[CLUSTER_SLOTS];
    rax *slots_to_keys;
    /* The following fields are used to take the slave state on elections. */
    mstime_t failover_auth_time; /* Time of previous or next election. */
    int failover_auth_count;    /* Number of votes received so far. */
    int failover_auth_sent;     /* True if we already asked for votes. */
    int failover_auth_rank;     /* This slave rank for current auth request. */
    uint64_t failover_auth_epoch; /* Epoch of the current election. */
    int cant_failover_reason;   /* Why a slave is currently not able to
                                   failover. See the CANT_FAILOVER_* macros. */
    /* Manual failover state in common. */
    mstime_t mf_end;            /* Manual failover time limit (ms unixtime).
                                   It is zero if there is no MF in progress. */
    /* Manual failover state of master. */
    clusterNode *mf_slave;      /* Slave performing the manual failover. */
    /* Manual failover state of slave. */
    long long mf_master_offset; /* Master offset the slave needs to start MF
                                   or zero if stil not received. */
    int mf_can_start;           /* If non-zero signal that the manual failover
                                   can start requesting masters vote. */
    /* The followign fields are used by masters to take state on elections. */
    uint64_t lastVoteEpoch;     /* Epoch of the last vote granted. */
    int todo_before_sleep; /* Things to do in clusterBeforeSleep(). */
    /* Messages received and sent by type. */
    long long stats_bus_messages_sent[CLUSTERMSG_TYPE_COUNT];
    long long stats_bus_messages_received[CLUSTERMSG_TYPE_COUNT];
    long long stats_pfail_nodes;    /* Number of nodes in PFAIL status,
                                       excluding nodes without address. */
} clusterState;

这个结构记录着当前节点的视角下集群目前所处的状态。

17.1.1 CLUSTER MEET命令的实现

通过向节点A发送CLUSTER MEET命令，可以让节点A将另外一个节点B添加到节点A当前所在的集群里面，收到命令的节点A将于节点B进行握手，以此来确认彼此的存在：

• （1） 节点A会为节点B创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面；
• （2）之后，节点A将给节点B发送一条MEET消息；
• （3）节点B接收到节点A发送的MEET消息，B会为A创建一个clusterNode结构，并将该结构添加到自己的clusterState.nodes字典里面；
• （4）之后，节点B将给节点A返回一条PONG消息；
• （5）节点A收到B的PONG消息，A就知道B已经成功的接收到自己的消息了；
• （6）之后，节点A将给B发送一条PING消息；
• （7）节点B收到A的PING消息，B就知道A已经接收到自返回的PONG消息，握手结束；
• （8）之后，节点A会将B的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与B握手，最终，经过一段时间，节点B会被集群中的所有节点认识；

17.2 槽指派

Redis集群通过分片的方式来保存数据库中的键值对，集群的整个数据库被分为16384（2^14）个槽（slot），数据库中的每个键都属于这16384个槽中的一个，集群中的每个节点可以处理0个或最多16384个槽；
当数据库中的16384个槽都被处理时，集群状态出于上线状态（ok），如果数据库中任意一个槽没有被处理，那么集群出于下线状态（fail）；

可以通过命令 CLUSTER ADDSLOTS命令将一个或者多个槽指派给某个节点负责；

节点的clusterNode结构的slots 属性和 numslots 记录了节点负责处理那些槽，slots属性是一个二进制位数组，这个数组的长度是16384 / 8 = 2048个字节，一共包含16384个二进制位。

Redis以0为起始索引，16383为终止索引，对slots数组中的16384个二进制位进行编号，并根据第i位上的二进制值来判断槽是否是该节点负责；

一个节点会将自己负责的槽信息发送给其他集群中的节点，以此来告诉其他节点自己负责哪些槽；节点A通过消息接收到节点B负责的槽信息，会在A节点自己的clusterState.nodes字典里面找到B对应的clusterNode结构，并对其中的slots属性进行更新，因为集群中的每个节点都会将自己的slots数组发送给其他节点，所以集群中的所有节点都知道16384个槽都是由哪些节点负责的；

这里需要注意的一点是，如果只将16384个槽记录在clusterNode的slots数组里，那么如果需要知道第i个槽是哪个节点负责的，就需要遍历clusterState.nodes字典中的所有clusterNode.slots数组，这个负责度为O(N)，所以，clusterState.slots数组会保存每一个槽是由哪个节点负责的。这样的话，如果想要检测槽i是否已经被指派，只需要检测clusterState.slots数组的第i个项即可；
当然，是否只需要在clusterState.slots数组就可以了呢？clusterNode.slots是否还需要呢？答案是需要的，因为节点需要将自己负责的slots传播给其他节点，现在只需要将clusterNode.slots发送出去即可，但是如果没有clusterNode.slots，就需要在clusterStste.slots里面遍历，找出所有某个节点负责的slot，然后再发送给其他节点，这就有点麻烦了；

17.3 在集群中执行命令

在对集群中的16384个槽都指派完成之后，集群就进入上线状态，这时客户端就可以向集群发送数据命令了；

当客户端向节点发送数据库相关命令时，接收到命令的节点会计算出命令要处理的数据库键属于哪个槽：

• 如果这个槽是自己负责的，那么节点直接执行这个命令；
• 如果键所在的槽不是当前节点负责的，那么节点会向客户端返回一个MOVED错误，指引客户端转向正确的节点执行命令；

节点首先需要计算出键所对应的槽，Redis使用CRC16（key） & 16383来计算这个值，当节点计算出键所对应的槽之后，节点就会检查自己在数组clusterState.slots的第i项是否是自己，如果是，则说明这个键是由自己负责的，否则，会指引客户端转向clusterState.slots[i]所指向的节点执行命令；

需要注意的是，节点只能使用0号数据库，而单机则没有这个限制；

17.4 重新分片

Redis集群的重新分片操作可以将任意已经分配给某个节点的槽改为指派给其他的另外一个节点，重新分片操作可以在线进行，不需要下线，源节点和目标节点都可以继续处理命令请求；

Redis集群的重新分片操作由Redis的集群管理软件redis-trib执行，redis-trib对集群的单个槽slot进行重新分片的步骤如下：

• （1）redis-trib向目标节点发送CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，让目标节点准备好从源节点导入属于槽slot的键值对；
• （2）redis-trib对源节点发送CLUSTER SETSLOT <slot> MIGRATING <target_id>命令，让源节点准备好将属于槽slot的键值对迁移到目标节点；
• （3）redis-trib向源节点发送CLUSTER GETKEYSINSLOT <slot> <count>命令，获取最多count个属于槽slot的键值对的键名字；
• （4）对于步骤3得到的每个键，redis-trib都将向源节点发送命令，原子的将这些键迁移到目标节点；
• （5）重复步骤3和4，直到源节点保存的所有属于槽slot的键值对都被迁移到目标节点为止；
• （6）redis-trib会向集群中的任意一个节点发送CLUSTER SETSLOT <slot> NODE <taregt_id>命令，将槽slot指派给目标节点，这一信息会通过消息发送给集群中的所有节点，最终集群中的所有节点都将知道槽slot已经指派给了目标节点；

17.5 ASK错误

在进行重新分片的过程中，因为集群正常在线，所以可能出现一种情况，属于被迁移槽的一部分键在源节点中，而另一部分已经迁移到目标节点，这时候如果客户端向源节点发送一个数据库操作命令，而这个被操作的键刚好在被迁移的键中时：

• 源节点会现在自己的数据库中查找给定的键，如果找到了，那么就直接处理；
• 如果没找到，那么源节点会向客户端返回一个ASK错误，指引客户端向目标节点发起请求；

ASK错误和MOVED错误的区别：

• MOVED错误表示槽的负责权已经从一个节点转向另外一个节点了，所以在客户端收到MOVED错误之后，客户端每次都可以使用转向后的节点；
• ASK错误是一种临时方案，是一次性的，ASK错误之后应该会出现一次MOVED错误；

17.6 复制与故障转移

Redis集群的节点分为主节点（master）和从节点（slave），主节点负责处理槽，而从节点负责复制某个主节点，并在主节点下线时代替主节点；

向一个节点发送CLUSTER REPLICATION <node_id>，可以让收到命令的节点对主节点进行复制：

• 接收到命令的节点首先会在自己的clusterState.modes字典中找到主节点的clusterNode结构，然后将自己的clusterState.myself.slaveof指针指向这个clusterNode，以此来表示当前节点正在复制这个主节点；
• 然后会修改自己的clusterState.myself.flags中的属性，关闭原本的master属性，打开slave属性，表示节点变成一个从节点；
• 然后，会复用复制的代码对master节点进行复制；

一个节点成为从节点，并开始复制某个主节点这个消息会被集群的其他节点知道，集群中的所有节点都会在代表主节点的clusterNode.slaves属性中记录正在复制该节点的从节点信息；

集群中的每个节点都会定期向其他节点发送PING消息，以此来检测对方是都还在线，如果接收PING消息的节点没有在规定时间内返回PONG消息，那么发送PING消息的节点就会将接受PING消息的节点标记为疑似下线（probable fail ，PFAIL）；
集群中的每个节点都会通过互相发送消息来交互集群各个节点的状态信息，如果一个集群里面超过半数以上负责处理槽的主节点将某个节点标记为疑似下线状态，那么这个主节点将被标记为下线，将这个主节点标记为下线的节点将会向集群广播这个消息，所有收到这条消息的节点都会立即标记这个节点已下线。

当一个从节点发现自己复制的主节点已下线时，从节点开始对下线主节点进行故障转移操作：

• （1）在所有复制主节点的从节点里面会有一个从节点被选中；
• （2）选中的从节点执行SLAVE no one命令，成为新的主节点；
• （3）新的主节点会认领所有下线主节点的槽指派；
• （4）新的主节点向集群广播一条PONG消息，集群中的其他节点会基于这条消息知道这个节点成为了新的主节点，并接管了原来主节点下的所有从节点；
• （5）新的主节点开始处理自己负责的槽的相关命令，故障转移完成；

选举新的主节点的步骤为：

• （1）在每次选举中，负责处理槽的主节点有一次投票机会；
• （2）当从节点发现自己正在复制的主节点已下线时，它会向集群广播一条消息，要求所有具备选举权的节点给自己投票；
• （3）接收到这条消息的节点，如果是负责处理槽的主节点，并且自己还没有投票，那么就会给这个节点投票；
• （4）如果一个从节点收集到大于集群主节点数量一半的票数，那么这个从节点就选举为新的主节点；
• （5）如果一个纪元里面没有从节点获得的票数符合要求，那么就会进入下一个纪元；

17.7 消息

消息类型：MEET PING PONG FAIL PUBLISH

gossip
redis cluster something

第十九章 事务

Redis通过MULTI、EXEC、WATCH等命令实现事务功能，事务提供了一种将多个命令请求打包，然后一次性的，按顺序的执行多个命令的机制，并且在事务执行期间，服务器不会中断事务而去执行其他客户端的请求，它会将事务中的命令都执行完成，然后才去执行其他客户端的命令；

19.1 事务

一个事务从开始到结束通常会经历以下三个阶段：

• 事务开始

MULTI命令可以让执行该命令的客户端从非事务状态切换到事务状态，这一切换是通过在客户端状态的flags属性打开REDIS_MULTI标志来完成；

• 命令入队

如果一个客户端处于非事务状态时，那么这个客户端发送的命令就会立即被执行，否则就会有不同的执行路径：

• 如果客户端发送的命令是EXEC DISCARD WATCH MULTI四个命令中的一个，那么服务器立即执行这个命令；
• 否则，就会将客户端的命令放到一个事务队列里面，然后给客户端返回QUEUED回复；

• 事务执行

当一个处于事务状态的客户端向服务器发送EXEC命令时，这个命令将被立即执行，服务器会遍历这个客户端的事务队列，执行队列里面保存的所有命令，最后将执行命令的结果全部返回给客户端。

19.2 WATCH命令的实现

WATCH是一个乐观锁，它可以在EXEC执行前，监视任意数量的数据库键，并在EXEC执行时，检查被监视的键是否至少有一个已经被修改过了，如果是的话，服务器将拒绝执行事务，并向客户端返回事务执行失败的空回复。

19.3 Redis事务的ACID性质

19.3.1 A（原子性）

原子性指的是数据库事务将多个操作当做一个整体执行，要么都执行，要么一个也不执行，对于Redis来说，要么全部执行Redis事务队列中的所有命令，要么一个也不执行，所以具备原子性；

需要注意的是，Redis的事务与传统关系型数据库事务的最大区别就是Redis不支持事务回滚，即使事务队列中的某个命令在执行时出错，事务也不会停止，会继续执行下去，直到将事务中的命令全部执行完成；

19.3.1 C（一致性）

一致性是指，如果数据库在执行事务之前是一致的，那么事务执行之后也应该是一致的，无论事务是否执行成功。一致是指数据符合数据库本身的定义，没有包含非法或者无效的错误数据：

• 入队错误：如果命令在入队的时候出现了比如命令不存在等错误，那么Redis将拒绝执行这个事务；
• 执行错误，执行错误一般是对数据库键执行了错误的类型操作导致，这种错误会被Redis识别并进行错误处理，这些命令不会对数据库进行任何修改，所以不会造成影响
• 服务器停机：服务器停机之后，如果开启了Redis持久化，那么服务器重启之后会将数据库状态还原到一个一致的状态，如果没有开启持久化，那么Redis重启之后数据库是空白的，是一致的状态；

19.3.1 I （隔离性）

事务的隔离性是指，即使数据库中多个事务并发的执行，各个事务之间也不会互相影响，并且在并发状态下执行的事务和串行执行的事务产生的结果一致；

对于Redis来说，它使用单线程的方式执行事务（以及事务队列中的命令），并且服务器保证，在执行事务期间，不会对事务进行中断，因此，Redis事务总是以串行的方式执行的；

19.3.1 D（耐久性）

事务的耐久性是指，当一个事物执行完毕时，执行这个事务所得的结果已被保存到永久存储介质里面了，即使服务器停机，执行事务的结果也不会丢失。

https://cloud.tencent.com/developer/article/1189074
https://juejin.im/post/5cc165816fb9a03202221dd5
https://mp.weixin.qq.com/s?__biz=MzU5ODUwNzY1Nw==&mid=2247484155&idx=1&sn=0c73f45f2f641ba0bf4399f57170ac9b&scene=21#wechat_redirect

Redis分布式锁

• （1） setnx (set if not exist)

public boolean tryLock_with_lua(String key, String UniqueId, int seconds) {
    String lua_scripts = "if redis.call('setnx',KEYS[1],ARGV[1]) == 1 then" +
            "redis.call('expire',KEYS[1],ARGV[2]) return 1 else return 0 end";
    List<String> keys = new ArrayList<>();
    List<String> values = new ArrayList<>();
    keys.add(key);
    values.add(UniqueId);
    values.add(String.valueOf(seconds));
    Object result = jedis.eval(lua_scripts, keys, values);
    //判断是否成功
    return result.equals(1L);
}

*（2） SET key value[EX seconds][PX milliseconds][NX|XX]

• EX seconds: 设定过期时间，单位为秒
• PX milliseconds: 设定过期时间，单位为毫秒
• NX: 仅当key不存在时设置值
• XX: 仅当key存在时设置值

• （3） RedLock

在Redis的分布式环境中，我们假设有N个Redis master。这些节点完全互相独立，不存在主从复制或者其他集群协调机制。我们确保将在N个实例上使用与在Redis单实例下相同方法获取和释放锁。现在我们假设有5个Redis节点，同时我们需要在5台服务器上面运行这些Redis实例，这样保证他们不会同时都宕掉。

为了取到锁，客户端应该执行以下操作:

• 获取当前Unix时间，以毫秒为单位。
• 依次尝试从5个实例，使用相同的key和具有唯一性的value（例如UUID）获取锁。当向Redis请求获取锁时，客户端应该设置一个网络连接和响应超时时间，这个超时时间应该小于锁的失效时间。例如你的锁自动失效时间为10秒，则超时时间应该在5-50毫秒之间。这样可以避免服务器端Redis已经挂掉的情况下，客户端还在死死地等待响应结果。如果服务器端没有在规定时间内响应，客户端应该尽快尝试去另外一个Redis实例请求获取锁。
• 客户端使用当前时间减去开始获取锁时间（步骤1记录的时间）就得到获取锁使用的时间。当且仅当从大多数（N/2+1，这里是3个节点）的Redis节点都取到锁，并且使用的时间小于锁失效时间时，锁才算获取成功。
• 如果取到了锁，key的真正有效时间等于有效时间减去获取锁所使用的时间（步骤3计算的结果）。
• 如果因为某些原因，获取锁失败（没有在至少N/2+1个Redis实例取到锁或者取锁时间已经超过了有效时间），客户端应该在所有的Redis实例上进行解锁（即便某些Redis实例根本就没有加锁成功，防止某些节点获取到锁但是客户端没有得到响应而导致接下来的一段时间不能被重新获取锁）。

无论如何，在解锁的时候需要check设置的value，这应该是一个唯一的值，不是每个客户端都可以解锁，只有设置这个可以的客户端才能解锁。