Java技术

《Redis设计与实现》读书笔记

2020-08-23  本文已影响0人  一字马胡

第二章 简单动态字符串 （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属性来维护，避免频繁分配内存；额外分配的内存大小由以下公式决定：

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链表实现的特性

第四章 字典

字典：又被称为符号表、关联数组、映射（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操作的步骤如下：

4.7 哈希表的收缩与扩展

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

负载因子的计算公式为：
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的详细步骤：

在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

第六章 整数集合

第七章 压缩列表

压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量的列表项，并且每个列表项要么就是小整数值，要么就是简短的字符串，那么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。

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

8.3 列表对象

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

8.4 哈希对象

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

8.5 集合对象

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

8.6 有序集合对象

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

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

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

8.8 内存回收

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

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友好；定期删除策略是对前两种策略的折中方案：

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文件进行载入：

9.2.3 AOF文件写入

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

9.2.4 复制

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

第十章 RDB持久化

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

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

第十一章 AOF持久化

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

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

11.1 命令追加

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

11.2 文件写入 与同步

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

默认为everysec。

11.3 AOF重写

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

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

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

第十二章 事件

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

12.1 文件事件

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

12.2 时间事件

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

第十五章 复制

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

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

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

15.1.1 同步（sync）

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

15.1.2 命令传播（command propagate）

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

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

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

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

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

15.3 新版复制功能的实现

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

15.4 部分重同步实现

部分重同步由三部分组成

15.4.1 复制偏移量

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

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

15.4.2 复制积压缓冲区

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

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

15.4.3 服务器运行ID

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

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

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

15.5 复制的实现

第十六章 Sentinel

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

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

16.1 启动并初始化Sentinel

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

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

16.2 获取主服务器信息

Sentinel默认会以十秒一次的频率通过命令连接向被监视的主服务器发送INFO命令，通过分析主服务器返回的INFO命令回复，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的资料：

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，负责执行故障转移操作：

16.9 故障转移

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

16.9.1 选出新的主服务器

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

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

之后，领头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进行握手，以此来确认彼此的存在：

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个槽都指派完成之后，集群就进入上线状态，这时客户端就可以向集群发送数据命令了；

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

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

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

17.4 重新分片

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

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

17.5 ASK错误

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

ASK错误和MOVED错误的区别：

17.6 复制与故障转移

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

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

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

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

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

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

17.7 消息

消息类型：MEET PING PONG FAIL PUBLISH

gossip
redis cluster something

第十九章 事务

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

19.1 事务

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

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

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

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

19.2 WATCH命令的实现

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

19.3 Redis事务的ACID性质

19.3.1 A（原子性）

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

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

19.3.1 C（一致性）

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

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分布式锁

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]

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

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

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

上一篇下一篇

猜你喜欢

热点阅读