键值存储系统 Redis

引言

本文整理了 Redis 相关的知识，方便以后查阅。

简介

简单来说 redis 就是一个数据库，不过与传统数据库不同的是 redis 的数据是存在内存中的，所以读写速度非常快，因此 redis 被广泛应用于缓存方向。另外，redis 也经常用来做分布式锁。redis 提供了多种数据类型来支持不同的业务场景。除此之外，redis 支持事务 、持久化、LUA 脚本、LRU 驱动事件、多种集群方案。

作用

高性能：假如用户第一次访问数据库中的某些数据。这个过程会比较慢，因为是从硬盘上读取的。将该用户访问的数据存在数缓存中，这样下一次再访问这些数据的时候就可以直接从缓存中获取了。操作缓存就是直接操作内存，所以速度相当快。如果数据库中的对应数据改变的之后，同步改变缓存中相应的数据即可！高并发：直接操作缓存能够承受的请求是远远大于直接访问数据库的，所以我们可以考虑把数据库中的部分数据转移到缓存中去，这样用户的一部分请求会直接到缓存这里而不用经过数据库。

缓存分为本地缓存和分布式缓存。以 Java 为例，使用自带的 map 或者 guava 实现的是本地缓存，最主要的特点是轻量以及快速，生命周期随着 jvm 的销毁而结束，并且在多实例的情况下，每个实例都需要各自保存一份缓存，缓存不具有一致性。

使用 redis 之类的称为分布式缓存，在多实例的情况下，各实例共用一份缓存数据，缓存具有一致性。缺点是需要保持 redis 或 memcached 服务的高可用，整个程序架构上较为复杂。

常用数据结构

String

常用命令: set,get,decr,incr,mget 等。

String 数据结构是简单的 key-value 类型，value 其实不仅可以是 String，也可以是数字。常规 key-value 缓存应用；常规计数：微博数，粉丝数等。

Hash

常用命令：hget,hset,hgetall 等。

hash 是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象，后续操作的时候，你可以直接仅仅修改这个对象中的某个字段的值。比如我们可以 hash 数据结构来存储用户信息，商品信息等等。比如下面我就用 hash 类型存放了我本人的一些信息：

key=JavaUser293847
value={
  “id”: 1,
  “name”: “SnailClimb”,
  “age”: 22,
  “location”: “Wuhan, Hubei”
}

List

常用命令: lpush,rpush,lpop,rpop,lrange 等

list 就是列表，Redis list 的应用场景非常多，也是 Redis 最重要的数据结构之一，比如微博的关注列表，粉丝列表，消息列表等功能都可以用 Redis 的 list 结构来实现。

Redis list 的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。

另外可以通过 lrange 命令，就是从某个元素开始读取多少个元素，可以基于 list 实现分页查询，这个很棒的一个功能，基于 redis 实现简单的高性能分页，可以做类似微博那种下拉不断分页的东西（一页一页的往下走），性能高。

Set

常用命令：sadd,spop,smembers,sunion 等

set 对外提供的功能与 list 类似是一个列表的功能，特殊之处在于 set 是可以自动排重的。

当你需要存储一个列表数据，又不希望出现重复数据时，set 是一个很好的选择，并且 set 提供了判断某个成员是否在一个 set 集合内的重要接口，这个也是 list 所不能提供的。可以基于 set 轻易实现交集、并集、差集的操作。

比如：在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。Redis 可以非常方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程，具体命令如下：sinterstore key1 key2 key3 将交集存在key1内

Sorted Set

常用命令：zadd,zrange,zrem,zcard 等

和 set 相比，sorted set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列。

举例：在直播系统中，实时排行信息包含直播间在线用户列表，各种礼物排行榜，弹幕消息（可以理解为按消息维度的消息排行榜）等信息，适合使用 Redis 中的 Sorted Set 结构进行存储。

底层数据

SDS

Redis 里，C 字符串只会作为字符串字面量用在一些无需对字符串值进行修改的地方，比如打印日志。Redis 构建了 简单动态字符串（simple dynamic string，SDS）来表示字符串值。

在 Redis 里，包含字符串值的键值对在底层都是由 SDS 实现的。除此之外，SDS 还被用作缓冲区：AOF 缓冲区，客户端状态中的输入缓冲区。

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


   记录buf数组中未使用字节的数量
  int free;


   字节数组，用于保存字符串
  char buf[];
}

SDS 遵循 C 字符串以空字符结尾的管理，空字符不计算在 len 属性中。这样，SDS 可以重用一部分 C 字符串函数库，如 printf。优点

• 常数复杂度获取字符串长度 C 字符串必须遍历整个字符串才能获得长度，复杂度是 O(N)。SDS 在 len 属性中记录了 SDS 的长度，复杂度为 O(1)。

• 杜绝缓冲区溢出 C 字符串不记录长度的带来的另一个问题是缓冲区溢出。假设 s1 和 s2 是紧邻的两个字符串，对 s1 的 strcat 操作，有可能污染 s2 的内存空间。SDS 的空间分配策略杜绝了缓冲区溢出的可能性：但 SDS API 修改 SDS 时，会先检查 SDS 的空间是否满足修改所需的要求，不满足的话，API 会将 SDS 的空间扩展至执行修改所需的大小，然后再执行实际的修改操作。

• 减少修改字符串时带来的内存重分配次数 每次增长或缩短一个 C 字符串，程序都要对保存这个 C 字符串的数组进行一次内存重分配操作。Redis 作为数据库，数据会被频繁修改，如果每次修改字符串都会执行一次内存重分配的话，会性能该造成影响。SDS 通过未使用空间解除了字符串长度和底层数组长度的关联：在 SDS 中，buf 数组的长度不一定就是字符数量+1，数组里面可以包含未使用的字节，由 free 属性记录。对于未使用空间，SDS 使用了空间预分配和惰性空间释放两种优化策略：- 空间预分配 当 SDS 的 API 对 SDS 修改并需要空间扩展时，程序不仅为 SDS 分配修改所需的空间，还会分配额外的未使用空间（取决于长度是否小于 1MB）。- 惰性空间释放 当 SDS 的 API 需要缩短时，程序不立即触发内存重分配，而是使用 free 属性将这些字节的数量记录下来，并等待将来使用。与此同时，SDS API 也可以让我们真正释放未使用空间，防止内存浪费。

• 二进制安全 C 字符串中的字符必须复合某种编码（如 ASCII），除了字符串末尾之外，字符串里不能包含空字符。这些限制使得 C 字符串只能保存文本，而不是不能保存二进制数据。SDS API 会以处理二进制的方式处理 SDS 存放在 buf 数组中的数据，写入时什么样，读取时就是什么样。

• 兼容部分 C 字符串函数 遵循 C 字符串以空字符结尾的管理，SDS 可以重用<string.h>函数库。

链表

Redis 构建了自己的链表实现。列表键的底层实现之一就是链表。发布、订阅、慢查询、监视器都用到了链表。Redis 服务器还用链表保存多个客户端的状态信息，以及构建客户端输出缓冲区。

typedef struct listNode {
  struct listNode *prev;
  struct listNode *next;
  void *value;
} listNode;


typedef struct list {
  listNode *head;
  listNode *tail;
  unsigned long len;
  void *(dup)(void *ptr);  节点复制函数
  void (*free)(void *ptr); / 节点释放函数
  int (*match)(void *ptr, void *key); // 节点值对比函数
} list;

特点

• 双向

• 无环。表头结点的 prev 和表尾节点的 next 都指向 NULL

• 带表头指针和表尾指针

• 带链表长度计数器

• 多态。使用 void*指针来保存节点值，并通过 list 结构的 dup、free。match 三个属性为节点值设置类型特定函数

字典

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

字典还是哈希键的底层实现之一，但一个哈希键包含的键值对比较多，又或者键值对中的元素都是较长的字符串时，Redis 就会用字典作为哈希键的底层实现。

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

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


typedef struct dictEntry {
  void *key; // 键


  // 值
  union {
    void *val;
    uint64_t u64;
    int64_t s64;
  } v;


  // 指向下个哈希表节点，形成链表。一次解决键冲突的问题
  struct dictEntry *next;
}


typedef struct dict {
  dictType *type; // 类型特定函数
  void *privdata; // 私有数据


  /*
  哈希表
  一般情况下，字典只是用ht[0]哈希表，ht[1]只会在对ht[0]哈希表进行rehash时使用
  */
  dictht ht[2];


  // rehash索引，但rehash不在进行时，值为-1
  // 记录了rehash的进度
  int trehashidx;
} dict;

哈希算法

Redis 计算哈希值和索引值的方法如下：

# 使用字典设置的哈希函数，计算key的哈希值
hash = dict.type.hashFucntion(key)
# 使用哈希表的sizemask属性和哈希值，计算出索引值
# 根据情况的不同，ht[x]可以使ht[0]或ht[1]
index = hash & dict.ht[x].sizemask

当字典被用作数据库或哈希键的底层实现时，使用 MurmurHash2 算法来计算哈希值，即使输入的键是有规律的，算法仍能有一个很好的随机分布性，计算速度也很快。

解决冲突

Redis 使用链地址法解决键冲突，每个哈希表节点都有个 next 指针。

rehash

随着操作的不断执行，哈希表保存的键值对会增加或减少。为了让哈希表的负载因子维持在合理范围，需要对哈希表的大小进行扩展或收缩，即通过执行 rehash（重新散列）来完成：

1. 为字典的 ht[1]哈希表分配空间：

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

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

2. 将保存在 ht[0]中的所有键值对 rehash 到 ht[1]上。rehash 是重新设计的计算键的哈希值和索引值

3. 释放 ht[0]，将 ht[1]设置为 ht[0]，并为 ht[1]新建一个空白哈希表

扩展收缩

满足以下任一条件，程序会自动对哈希表执行扩展操作：

1、服务器目前没有执行 BGSAVE 或 BGREWRITEAOF，且哈希表负载因子大于等于 1 2、服务器正在执行 BGSAVE 或 BGREWRITEAOF，且负载因子大于 5

其中负载因子的计算公式：

# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

注：执行 BGSAVE 或 BGREWRITEAOF 过程中，Redis 需要创建当前服务器进程的子进程，而多数操作系统都是用写时复制来优化子进程的效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间扩展哈希表，避免不避免的内存写入，节约内存。

渐进式 rehash

将 ht[0]中的键值对 rehash 到 ht[1]中的操作不是一次性完成的，而是分多次渐进式的：

1. 为 ht[1]分配空间

2. 在字典中维持一个索引计数器变量 rehashidx，设置为 0，表示 rehash 工作正式开始

3. rehash 期间，每次对字典的增删改查操作，会顺带将 ht[0]在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，rehash 完成之后，rehashidx 属性的值+1

4. 最终 ht[0]会全部 rehash 到 ht[1]，这是将 rehashidx 设置为-1，表示 rehash 完成

渐进式 rehash 过程中，字典会有两个哈希表，字典的增删改查会在两个哈希表上进行。

跳表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问的目的。跳跃表支持平均 O(logN)、最坏*O(N)*的查找，还可以通过顺序性操作来批量处理节点。

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

在集群节点中，跳跃表也被 Redis 用作内部数据结构。

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; # 指向跳跃表的表头结点 指向跳跃表的表尾节点
  unsigned long length; # 记录跳跃表的长度， 即跳跃表目前包含节点的数量（表头结点不计入）
  int leve; # 记录跳跃表内，层数最大的那个节点的层数（表头结点不计入）
} zskiplist;


typedef struct zskiplistNode {
  struct zskiplistLevel {
    struct zskiplistNode *forward;
    unsigned int span; // 跨度
  } level[];


  struct zskiplistNode *backward;
  double score;
  robj *obj;
} zskiplistNode;

level：节点中用 L1、L2、L3 来标记节点的各个层，每个层都有两个属性：前进指针和跨度。前进指针用来访问表尾方向的其他节点，跨度记录了前进指针所指向节点和当前节点的距离（图中曲线上的数字）。level 数组可以包含多个元素，每个元素都有一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点。层数越多，访问速度就越快。每创建一个新节点的时候，根据幂次定律（越大的数出现的概率越小）随机生成一个介于 1-32 之间的值作为 level 数组的大小。这个大小就是层的高度。跨度用来计算排位（rank）：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到就是目标节点的排位。后退指针：BW，指向位于当前节点的前一个节点。只能回退到前一个节点，不可跳跃。分值（score）：节点中的 1.0/2.0/3.0 保存的分值，节点按照各自保存的分值从小到大排列。节点的分值可以相同。成员对象（obj）：节点中的 o1/o2/o3。它指向一个字符串对象，字符串对象保存着一个 SDS 值。

整数集合

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

整数集合，可以保存 int16_t、int32_t 或者 int64_t 的整数值，且元素不重复，intset.h/intset 结构表示一个整数集合：

typedef struct intset {
  uint32_t encoding; // 决定contents保存的真正类型
  uint32_t length;
  int8_t contents[]; // 各项从小到大排序
} inset;

上图中，contents 数组的大小为 sizeof(int16_t) * 5 = 80 位。

升级

每当添加一个新元素到整数集合中，且新元素的类型比现有所有元素的类型都要长时，整数集合需要先升级（update），然后才能添加新元素：

• 根据新元素的类型，扩展底层数组的空间大小，并为新元素分配空间。

• 将底层数组现有元素转换成与新元素相同的类型，并放置在正确的位置上（从后向前遍历）。放置过程中，维持底层数组的有序性质不变。

• 将新元素添加到底层数组里。

• 因为每次升级都可能对所有元素进行类型转换，所以复杂度为 O(N)。

因为引发升级的新元素长度比当前元素都大，所以它的值要么大于当前所有元素，要么就小于。前种情况放置在底层数组的末尾，后种情况放置在头部。

升级有两个好处

• 提升整数集合的灵活性 我们可以随意地将 int16_t、int32_t 添加到集合中，不必担心出现类型错误，毕竟 C 是个静态语言。

• 尽可能节约内存 避免用一个 int64_t 的数组包含所有元素。

压缩列表

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

当一个哈希键只包含少量键值对，并且每个键值对要么是小整数值，要么是长度较短的字符串，Redis 就会使用压缩列表来实现哈希键。

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

压缩列表的各组成部分：zlbytes | zltail | zllen | entry1 | entry2 | … | entryN | zlend

压缩列表的节点可以保存一个字节数组或者一个整数值。压缩节点的各个组成部分：previous_entry_length | encoding | content

previous_entry_length 以字节为单位，记录前一个节点的长度。previous_entry_length 属性的长度可以是 1 字节或 5 字节：

• 若前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度就是 1 字节。前一节点的长度保存在其中。

• 若前一节点的长度大于 254 字节，那么 previous_entry_length 属性的长度就是 5 字节：其中属性的第一个字节被设置为 0xFE（十进制 254），而之后的四个字节则用于保存前一节点的长度。

程序可以通过指针运算，根据当前节点的起始地址来计算出前一个结点的起始地址。压缩列表的从尾向头遍历就是据此实现的。

节点的 encoding 记录了节点的 content 属性所保存的数据的类型和长度：

• 1 字节、2 字节或者 5 字节长，值的最高位为 00、01 或 10 的是字节数组编码：这种编码表示节点的 content 保存的是字节数组，数组的长度由编码除去最高两位置后的其他位记录。

• 1 字节长。值的最高位以 11 开头的是整数编码：表示 content 保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

content 保存节点的值，可以是字节数组或整数，值的类型和长度由 encoding 属性决定。

连锁更新

因为 previous_entry_length 的长度限制，添加或删除节点都有可能引发「连锁更新」。在最坏的情况下，需要执行 N 次重分配操作，而每次空间重分配的最坏复杂度是 O(N)，合起来就是 O(N^2)。

尽管如此，连锁更新造成性能问题的概率还是比较低的：

• 压缩列表里有多个连续的、长度介于 250 和 253 字节之间的节点，连锁更新才有可能触发。

• 即使出现连锁更新，只要需要更新的节点数量不多，性能也不会受影响。

对象

Redis 并没有使用 SDS、双端链表、字典、压缩列表、整数集合来实现键值对数据库，而是基于这些数据结构创建了一个对象系统。这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象。

通过这五种类型的对象，Redis 可以在执行命令之前，根据对象的类型判断一个对象是否执行给定的命令。使用对象的好处是，可以针对不同的场景，为对象设置多种不同的数据结构的实现，从而优化使用效率。

除此之外，Redis 还实现了引用计数的内存回收机制。当程序不再需要某个对象的时候，它所占用的内存会被自动释放。另外，Redis 还用引用计数实现了对象共享，让多个数据库键共享同一个对象来节约内存。

最后，Redis 的对象带有访问时间记录信息，空转时长较大的键可能被优先删除。

Redis 使用对象来表示数据库中的键和值。创建一个新键值对时，至少会创建两个对象，一个对象用作键，一个对象用作值。每个对象都由一个 redisObject 结构表示：

typedef struct redisObject {
  unsigned type: 4; // 类型
  unsigned encoding: 4; // 编码
  void *ptr; // 指向底层实现数据结构的指针
  // ...
} robj;

键总是一个字符串对象，值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象。

但数据库执行 TYPE 命令时，返回的结果为数据库键对应的值对象的类型，而不是键对象的类型。

线程模型

redis 内部使用文件事件处理器 file event handler，这个文件事件处理器是单线程的，所以 redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket，根据 socket 上的事件来选择对应的事件处理器进行处理。

文件事件处理器的结构包含 4 个部分：

• 多个 socket

• IO 多路复用程序

• 文件事件分派器

• 事件处理器（连接应答处理器、命令请求处理器、命令回复处理器）

多个 socket 可能会并发产生不同的操作，每个操作对应不同的文件事件，但是 IO 多路复用程序会监听多个 socket，会将 socket 产生的事件放入队列中排队，事件分派器每次从队列中取出一个事件，把该事件交给对应的事件处理器进行处理。

过期时间

Redis 中有个设置时间过期的功能，即对存储在 redis 数据库中的值可以设置一个过期时间。作为一个缓存数据库，这是非常实用的。如我们一般项目中的 token 或者一些登录信息，尤其是短信验证码都是有时间限制的，按照传统的数据库处理方式，一般都是自己判断过期，这样无疑会严重影响项目性能。

我们 set key 的时候，都可以给一个 expire time，就是过期时间，通过过期时间我们可以指定这个 key 可以存活的时间。

如果假设你设置了一批 key 只能存活 1 个小时，1 小时后，redis 会通过定期删除+惰性删除进行删除：

• 定期删除：redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。注意这里是随机抽取的。为什么要随机呢？你想一想假如 redis 存了几十万个 key ，每隔 100ms 就遍历所有的设置过期时间的 key 的话，就会给 CPU 带来很大的负载！

• 惰性删除：定期删除可能会导致很多过期 key 到了时间并没有被删除掉。所以就有了惰性删除。假如你的过期 key，靠定期删除没有被删除掉，还停留在内存里，除非你的系统去查一下那个 key，才会被 redis 给删除掉。这就是所谓的惰性删除。

但是仅仅通过设置过期时间还是有问题的。我们想一下：如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时会怎么样？如果大量过期 key 堆积在内存里，导致 redis 内存块耗尽了。怎么解决这个问题呢？redis 内存淘汰机制。

内存淘汰策略

• volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰

• volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰

• volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰

• allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）

• allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰

• no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。

• volatile-lfu：从已设置过期时间的数据集(server.db[i].expires)中挑选最不经常使用的数据淘汰

• allkeys-lfu：当内存不足以容纳新写入数据时，在键空间中，移除最不经常使用的 key

持久化

Redis 支持持久化，而且支持两种不同的持久化操作。Redis 的一种持久化方式叫快照（snapshotting，RDB）,另一种方式是只追加文件（append-only file,AOF）。

RDB

Redis 可以通过创建快照来获得存储在内存里面的数据在某个时间点上的副本。Redis 创建快照之后，可以对快照进行备份，可以将快照复制到其他服务器从而创建具有相同数据的服务器副本（Redis 主从结构，主要用来提高 Redis 性能），还可以将快照留在原地以便重启服务器的时候使用。创建快照的办法有如下几种：

• BGSAVE 命令：客户端向 Redis 发送 BGSAVE 命令 来创建一个快照。对于支持 BGSAVE 命令的平台来说（基本上所有平台支持，除了 Windows 平台），Redis 会调用 fork 来创建一个子进程，然后子进程负责将快照写入硬盘，而父进程则继续处理命令请求。

• SAVE 命令：客户端还可以向 Redis 发送 SAVE 命令 来创建一个快照，接到 SAVE 命令的 Redis 服务器在快照创建完毕之前不会再响应任何其他命令。SAVE 命令不常用，我们通常只会在没有足够内存去执行 BGSAVE 命令的情况下，又或者即使等待持久化操作执行完毕也无所谓的情况下，才会使用这个命令。

• save 选项：如果用户设置了 save 选项（一般会默认设置），比如 save 60 10000，那么从 Redis 最近一次创建快照之后开始算起，当“60 秒之内有 10000 次写入”这个条件被满足时，Redis 就会自动触发 BGSAVE 命令。

• SHUTDOWN 命令：当 Redis 通过 SHUTDOWN 命令接收到关闭服务器的请求时，或者接收到标准 TERM 信号时，会执行一个 SAVE 命令，阻塞所有客户端，不再执行客户端发送的任何命令，并在 SAVE 命令执行完毕之后关闭服务器。

• 一个 Redis 服务器连接到另一个 Redis 服务器：当一个 Redis 服务器连接到另一个 Redis 服务器，并向对方发送 SYNC 命令来开始一次复制操作的时候，如果主服务器目前没有执行 BGSAVE 操作，或者主服务器并非刚刚执行完 BGSAVE 操作，那么主服务器就会执行 BGSAVE 命令

如果系统真的发生崩溃，用户将丢失最近一次生成快照之后更改的所有数据。因此，快照持久化只适用于即使丢失一部分数据也不会造成一些大问题的应用程序。不能接受这个缺点的话，可以考虑 AOF 持久化。

AOF

与 RDB 持久化相比，AOF 持久化 的实时性更好，因此已成为主流的持久化方案。开启 AOF 持久化后每执行一条会更改 Redis 中的数据的命令，Redis 就会将该命令写入硬盘中的 AOF 文件。

在 Redis 的配置文件中存在三种同步方式，它们分别是：

appendfsync always     #每次有数据修改发生时都会调用fsync写入AOF文件,这样会严重降低Redis的速度
appendfsync everysec   #每秒钟调用fsync同步一次，显示地将多个写命令同步到硬盘
appendfsync no         #所有数据写入操作系统的文件缓存，让操作系统决定何时进行同步

appendfsync always 可以实现将数据丢失减到最少，不过这种方式需要对硬盘进行大量的写入而且每次只写入一个命令，十分影响 Redis 的速度。另外使用固态硬盘的用户谨慎使用 appendfsync always 选项，因为这会明显降低固态硬盘的使用寿命。不过，我个人觉得可以将 redis 服务器连上带写缓存和电源保护的 RAID，这样 AOF 文件顺序写入也很快，而且每次都是写入到 RAID 的缓存中，并不是实际写盘，电池保护也保证了数据的持久性。

为了兼顾数据和写入性能，用户可以考虑 appendfsync everysec 选项 ，让 Redis 每秒同步一次 AOF 文件，Redis 性能几乎没受到任何影响。而且这样即使出现系统崩溃，用户一般只会丢失一秒之内产生的数据，但如果 redis 的写入压力很大时，最多还会多写入 1 秒的数据量（相对于 AOF 文件缓冲区），所以理论上最多会丢失 2 秒的数据。当硬盘忙于执行写入操作的时候，Redis 还会优雅的放慢自己的速度以便适应硬盘的最大写入速度。

appendfsync no 选项一般不推荐，这种方案会使 Redis 丢失不定量的数据而且如果用户的硬盘处理写入操作的速度不够的话，那么当缓冲区被等待写入的数据填满时，Redis 的写入操作将被阻塞，这会导致 Redis 的请求速度变慢。

虽然 AOF 持久化非常灵活地提供了多种不同的选项来满足不同应用程序对数据安全的不同要求，但 AOF 持久化也有缺陷——AOF 文件的体积太大。

AOF 重写

AOF 虽然在某个角度可以将数据丢失降低到最小而且对性能影响也很小，但是极端的情况下，体积不断增大的 AOF 文件很可能会用完硬盘空间。另外，如果 AOF 体积过大，那么还原操作执行时间就可能会非常长。

为了解决 AOF 体积过大的问题，用户可以向 Redis 发送 BGREWRITEAOF 命令 ，这个命令会通过移除 AOF 文件中的冗余命令来重写（rewrite）AOF 文件来减小 AOF 文件的体积。BGREWRITEAOF 命令和 BGSAVE 创建快照原理十分相似，所以 AOF 文件重写也需要用到子进程，这样会导致性能问题和内存占用问题，和快照持久化一样。更糟糕的是，如果不加以控制的话，AOF 文件的体积可能会比快照文件大好几倍。

持久化机制优化

Redis 4.0 开始支持 RDB 和 AOF 的混合持久化（默认关闭，可以通过配置项 aof-use-rdb-preamble 开启）。

如果把混合持久化打开，AOF 重写的时候就直接把 RDB 的内容写到 AOF 文件开头。这样做的好处是可以结合 RDB 和 AOF 的优点, 快速加载同时避免丢失过多的数据。当然缺点也是有的，RDB 部分是压缩格式不再是 AOF 格式，可读性较差。

事务

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

• MULTI：表示要开始一个事务，之后的命令都会放入一个队列中，等待被执行

• EXEC：表示开始执行队列中的命令

• WATCH：可以 watch 一些 key，如果其中任何一个 key 被修改了，那么事务就会被驳回

watch key1 key2
multi
set key1 value1
set key2 value2
exec # 如果key1或者key2被其他人修改了那么上述的两条命令就不会执行，redis借此来实现事务机制

在传统的关系式数据库中，常常用 ACID 性质来检验事务功能的可靠性和安全性。在 Redis 中，事务总是具有原子性（Atomicity）、一致性（Consistency）和隔离性（Isolation），并且当 Redis 运行在某种特定的持久化模式下时，事务也具有持久性（Durability）。

复制

Redis 中，用户可以执行 SAVEOF 命令或设置 saveof 选项，让一个服务器去复制（replicate）另一个服务器。被复制的服务器叫做 master，对 master 进行复制的服务器叫做 slave。

进行复制中的 master 和 slave 应该保存相同的数据，这称作“数据库状态一致”。

旧版同步

复制开始时，slave 会先执行同步操作，步骤如下：

• slave 对 master 发送 SYNC 命令

• master 收到 SYNC 执行 BGSAVE，在后台生成一个 RDB 文件，并使用一个缓冲区记录从现在开始执行的所有写命令。

• master 的 BGSAVE 执行完毕后，将生成的 RDB 文件发送给 slave，slave 接收并载入这个 RDB，更新自己的数据库状态

• master 将记录在缓冲区中的所有写命令发送给 slave，后者执行这些操作，再次更新自己的数据库状态

命令传播

同步完成后，主从服务器的一致状态仍有可能改变，每当 master 执行写命令时，主从服务器的状态就会不一致。为此，master 执行写命令，并将其发送给 slave 一并执行。

旧版缺陷

Redis 的复制可以分为两种情况：

• 初次复制：slave 没有复制过，或者 slave 要复制的 master 和上一次复制的 master 不同。

• 断线后重复制：处于命令传播阶段的 master 和 slave 中断了复制，但重连后，slave 继续复制 master。

对于初次复制，旧版复制功能可以很好完成。但是断线后复制，效率却很低，因为重连后会浪费一次 SYNC 操作。

新版复制

为了解决旧版复制功能在断线后的低效问题，Redis 从 2.8 之后，使用 PSYNC 代替 SYNC 执行复制时的同步操作。PSYNC 具有完整重同步（full resynchronization)和部分重同步（partial resynchronization）两种模式：

• 完整重同步用于处理初次复制，执行步骤和 SYNC 命令基本一样。

• 部分重同步用于处理断线后重复制，重连后，如果条件允许，master 可以将断开期间的写命令发送给 slave 执行。

复制偏移量

master 和 slave 分别维护一个复制偏移量：

• master 每次向 slave 传播 N 个字节的数据时，就将自己的复制偏移量+N。

• slave 每次收到 master 的 N 个字节数据时，就将自己的复制偏移量+N。

对比两者的复制偏移量，就知道它们是否处于一致状态。

复制积压缓冲区

复制积压缓冲区是 master 维护的一个固定长度的 FIFO 队列，默认大小为 1MB。当服务器进行命令传播时，不仅会将命令发送给所有 slave，还会入队到积压缓冲区。因此，积压缓冲区保存了最近被传播的写命令，且为队列中的每个字节记录相应的复制偏移量。

slave 重连上 master 时，slave 通过 PSYNC 将自己的复制偏移量 offset 发送给 master，master 会根据这个 offset 决定 slave 执行何种同步操作：

• 如果 offset 之后的数据仍在复制积压缓冲区中，执行部分重同步操作。

• 否则，执行完整重同步操作。

服务器运行 ID

部分重同步还要用到服务器运行 ID，主从服务器都有自己的 ID。初次复制时，master 将自己的 ID 传给 slave，后者将其保存。

断线重连后，slave 向当前连接的 master 发送之前保存的 ID：

• master 发现接收的 ID 和自己的相同，那么说明断线之前复制的就是自己，继续执行部分重同步。

• 如果不同，完整重同步啦！

PSYNC 实现

PSYNC 的调用方式有两种：

• slave 没有复制过任何 master，则在开始一个新的复制时向 master 发送 PSYNC ? -1 命令，请求完整重同步。

• slave 复制过某个 master，则发送 PSYNC

  命令，接收到这个命令的 master 会根据 runid 和 offset 来判断执行哪种同步。

复制过程

1. 设置 master 的地址和端口

2. 建立套接字连接

3. 发送 PING 命令

4. 身份验证

5. 发送端口信息

• 身份验证之后，slave 将执行 REPLCONF listening-port

  ，向 master 发送 slave 的监听端口号。master 收到后，会将端口号放到客户端状态的 slave_listening_port 属性中该属性的唯一作用就是 master 执行 INFO replication 命令时打印 slave 的端口号。

6. 同步

• 这一步，slave 发送 PSYNC，执行同步操作。执行同步之后，master 也成了 slave 的客户端，master 发送写命令来改变 slave 的数据库状态。

7. 命令传播

• 完成同步之后，主从服务器就进入命令传播阶段，master 将自己执行写命令发送给 slave，slave 接到后就执行，这样两者的状态就一直保持一致了。

8. 心跳检测

• 检测网络连接状态

• 辅助实现 min-slaves 选项 该选项防止 master 在不安全的情况下执行写命令，比如 slave 数量小于 3 的时候。

• 检测命令丢失 这个根据复制偏移量来判断，如果两者不一致，master 就会把复制积压缓冲区的命令重新发送。

• 命令传播阶段，slave 默认每秒给 master 发送一次命令：REPLCONF ACK <replication_offset>，其中 replication_offset 对应当前 slave 的复制偏移量。该命令有三个作用：

Sentinel

Sentinel（哨兵）是 Redis 的高可用性解决方案，由一个或多个 Sentinel 实例组成的 Sentinel 系统可以监视任意多个 master 以及属下的所有 slave。Sentinel 在被监视的 master 下线后，自动将其属下的某个 slave 升级为新的 master，然后由新的 master 继续处理命令请求。

通讯建立

当一个 Sentinel 启动时，会执行以下几步：

• 初始化服务器

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

• 初始化 Sentinel 状态

• 根据配置文件，初始化监视的 master 列表

• 创建与 master 的网络连接

连接建立后，Sentinel 将成为 master 的客户端，可以向其发送命令。对于被监视的 master 来说，Sentinel 会创建两个异步网络连接：

• 命令连接，用于发送和接收命令。

• 订阅连接。用于订阅 master 的__sentinel__:hello
  频道。

Sentinel 以默认 10 秒一次的频率，向 master 发送 INFO 命令，获取其当前信息：

• master 本身的信息，包括运行 ID、role 等。据此，Sentinel 更新 master 实例的结构。

• master 的 slave 信息。据此，Sentinel 更新 master 实例的 slaves 字典。

Sentinel 发现 master 有新的 slave 时，除了会为这个 slave 创建相应的实例结构外，还会创建到它的命令连接和订阅连接。

通过命令连接，Sentinel 会向 slave 每 10 秒发送一次 INFO 命令，根据回复更新 slave 的实例结构：

• slave 的运行 ID

• slave 的角色 role

• master 的地址和端口

• 主从的连接状态

• slave 的优先级

• slave 的复制偏移量

默认情况下，Sentinel 会以两秒一次的频率，通过命令连接向所有被监视的 master 和 slave 发送：

PUBLISH __sentinel__:hello "<s_ip>, <s_port>, <s_runid>, <s_epoch>, <m_name>, <m_ip>, <m_port>, <m_epoch>"

其中以 s开头的参数表示 Sentinel 本身的信息，m开头的参数是 master 的信息。如果 Sentinel 正在监视的是 slave，那就是 slave 正在复制的 master 信息。

当 Sentinel 与一个 master 或 slave 建立订阅连接后，会向服务器发送以下命令：SUBSCRIBE __sentinel__:hello

Sentinel 对__sentinel__:hello
频道的订阅会持续到两者的连接断开为止。也就是说，Sentinel 既可以向服务器的__sentinel__:hello
频道发送信息，又通过订阅连接从__sentinel__:hello
频道接收信息。

对于监视同一个 server 的多个 Sentinel 来说，一个 Sentinel 发送的信息会被其他 Sentinel 收到。这些信息用于更新其他 Sentinel 队发送信息 Sentinel 和被监视 Server 的认知。

Sentinel 为 master 创建的实例结构中，有 sentinels 字典保存了其他监视这个 master 的 Sentinel：

• 键是 Sentinel 名字，格式为 ip: port。

• 值是 Sentinel 实例的结构。

当一个 Sentinel 收到其他 Sentinel 发来的信息时，目标 Sentinel 会从信息中提取出：

• 与 Sentinel 有关的参数：源 Sentinel 的 IP、端口、运行 ID、配置纪元。

• 与 master 有关的参数：master 的名字、IP、端口、配置纪元。

根据提取的参数，目标 Sentinel 会在自己的 Sentinel 状态中更新 sentinels 和 masters 字典。

Sentinel 通过频道信息发现一个新的 Sentinel 时，不仅会为其创建新的实例结构，还会创建一个连向新 Sentinel 的命令连接，新的 Sentinel 也会创建连向这个 Sentinel 的命令连接，最终，监视同一 master 的多个 Sentinel 成为相互连接的网络。各个 Sentinel 可以通过发送命令请求来交换信息。

故障检测

默认情况下，Sentinel 会每秒一次地向所有与它创建了命令连接的实例（master、slave、其他 sentinel）发送 PING 命令，并通过回复来判断其是否在线。只有+PONG/-LOADING/-MASERDOWN 三种有效回复。

Sentinel 的配置文件中 down-after-milliseconds 选项指定了判断实例主观下线所需的时间长度。在 down-after-milliseconds 毫秒内，如果连续返回无效回复，那么 Sentinel 会修改这个实例对应的实例结构，将 flags 属性中打开 SRI_S_DOWN 标识，标识主观下线。

当 Sentinel 将一个 master 判断为主观下线后，为了确认是真的下线，会向监视这一 master 的其他 Sentinel 询问。有足够数量（quorum）的已下线判断后，Sentinel 会将 master 判定为客观下线，并对 master 执行故障转移。

故障转移

master 被判定为客观下线后，监视这个 master 的所有 Sentinel 会进行协商，选举一个领头 Sentinel，并由其对该 master 执行故障转移。选举的规则如下：

• 所有 Sentinel 都可以成为领头。

• 每次进行领头 Sentinel 选举后，不论选举是否成功，所有 Sentinel 的配置纪元都会+1。这个配置纪元就是一个计数器。

• 一个配置纪元里，所有 Sentinel 都有一次将某个 Sentinel 设置为局部领头 Sentinel 的机会，且局部领头一旦设定，在这个配置纪元内就不可修改。

• 每个发现 master 进入客观下线的 Sentinel 都会要求其他 Sentinel 将自己设为局部领头 Sentinel。

• 当一个 Sentinel 向另一个 Sentinel 发送 SENTINEL is-master-down-by-addr，且命令中的 runid 参数是自己的运行 ID，这表明源 Sentinel 要求目标 Sentinel 将他设置为局部领头。

• Sentinel 设置局部领头的规则是先到先得。

• 目标 Sentinel 收到 SENTINEL is-master-down-by-addr 后，会返回一条命令回复，恢复中的 leader_runid 和 leader_epoch 参数分别记录了目标 Sentinel 的局部领头 Sentinel 的运行 ID 和配置纪元。

• 源 Sentinel 收到目标 Sentinel 的回复后，检查回复中的 leader_runid 和 leader_epoch 是否和自己相同。

• 如果某个 Sentinel 被半数以上的 Sentinel 设置为局部领头，那么这个 Sentinel 就成为领头 Sentinel。

• 因为领头 Sentinel 需要半数以上的支持，且每个 Sentinel 在每个配置纪元里只设置一次局部领头，所以一个配置纪元里，只能有一个领头。

• 如果给定时限内，没有产生领头 Sentinel，那么各个 Sentinel 过段时间再次选举，直到选出领头为止。

领头 Sentinel 会对已下线的 master 执行故障转移，包括以下三个步骤：

• 从已下线 master 属下的所有 slave 选出一个新的 master。

• 让已下线 master 属下的所有 slave 改为新复制新的 master。

• 让已下线 master 成为新 master 的 slave，重新上线后就是新 slave。

新 master 的挑选规则：

• 在线（必须）

• 五秒内回复过领头 Sentinel 的 INFO 命令（必须）

• 与已下线 master 在 down-after-milliseconds 毫秒内有过通信。（必须）

• salve 的自身的优先级最高选择

• 如果优先级相同，按复制偏移量最大选择

• 如果偏移量一致，按照 run id 最小选择

集群

Redis 集群是分布式的数据库方案，通过分片（sharding）来进行数据共享，并提供复制或故障转移功能。

启动

一个节点就是运行在集群模式下的 Redis 服务器，根据 cluster-endabled 配置选项是否为 yes 来决定是否开启集群模式。

节点在集群模式下会继续使用单机模式的组件，如：

• 文件事件处理器

• 时间事件处理器

• 使用数据库来保存键值对数据

• RDB 和 AOF 持久化

• 发布与订阅

• 复制模块

• Lua 脚本

连接

通过向节点 A 发送 CLUSTER MEET 命令，客户端可以让接受命令的节点 A 将另一个节点 B 接入到 A 所在的集群中。

收到 CLUSTER MEET 命令的节点 A，会进行以下操作：

• 为节点 B 创建一个 clusterNode 结构，并将该结构添加到自己的 clusterState.nodes 字典。

• 节点 A 根据 CLUSTER MEET 命令的 IP 和端口，先节点 B 发送 MEET 消息。

• 节点 B 收到 MEET 消息，为节点 A 创建一个 clusterNode 结构，并加入字典。

• 节点 B 回给节点 A 一条 PONG 消息。

• 节点 A 收到 PONG，知道节点 B 已经接收了自己的 MEET 消息。

• 节点 A 向节点 B 返回一条 PING 消息。

• 节点 B 收到 PING 之后，双方握手完成。

槽指派

Redis 集群通过分片的方式保存数据库中的键值对：集群中的整个数据库被分为 16384 个槽（slot），数据库中的每个键都属于其中的一个，集群中的每个节点可以处理 0 个或最多 16384 个槽。

当数据库中的 16384 个槽都有节点在处理时，集群处于上线状态（ok），如果任何一个槽都没有得到处理，就处于下线状态（fail）。

CLUSTER MEET 只是将节点连接起来，集群仍处于下线状态，通过向节点发送 CLUSTER ADDSLOTS，可以为一个或多个槽指派（assign）给节点负责。

记录节点的槽指派信息

struct clusterNode {
  unsigned char slots[16384/8];
  int numslots;
};

slots 数组中的索引 i 上的二进制位的值来判断节点是否负责处理槽 i。numslots 记录节点负责处理的槽的数量，即 slots 数组中二进制 1 的数量。

一个节点除了会将自己处理的槽记录在 clusterNode 结构中的 slots 和 numslots 属性之外，还会将自己的 slots 数组通过消息发送给集群中的其它节点。

节点 A 通过消息从节点 B 接收到节点 B 的 slots 数组会，会在自己的 clusterState.nodes 字典中查找节点 B 对应的 clusterNode 结构，并对结构中的 slots 数组进行更新。

最终，集群中的每个节点都知道数据库中的 16384 个槽分别被指派给了哪些节点。

执行命令

客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的键属于哪个槽，并检查这个槽是否被指派给了自己：

如果指派给了自己，节点直接执行命令。否则，节点向客户端返回一个 MOVED 错误，指引客户端转向（redirect）到正确的节点，再次发送命令。

计算槽：

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

节点计算出键所属的槽 i 之后，会检查自己在 clusterState.slots 数组中的第 i 项，判断键所在的槽是不是自己负责。

如果不是由自己负责，它会通过一个从 slot->node 的映射（跳表实现）来找到负责该槽的节点，并发送一个 MOVED 回应来通知客户端应该去找哪个节点。

重新分片

Redis 集群的重新分片指的是将任意数量已经指派给某个节点的槽改为指派给另一个节点，且相关槽所属的键也从源节点移动到目标节点。重新分片可以在线（online）进行，分片过程中，集群不需要下线，且源节点和目标节点都可以继续处理命令请求。

重新分片是由 Redis 的集群管理软件 redis-trib 负责的，Redis 提供了重新分片所需的所有命令，redis-trib 则通过向源节点和目标节点发送命令来实现重新分片：

• 向目标节点发送 CLUSTER SETSLOT

• 向源节点发送 CLUSTER SETSLOT

• 向源节点发送 CLUSTER GETKEYINSLOT

  命令，获得最多 count 个属于槽 slot 的键值对的键名。

• 对于步骤 3 获得的每个键名，向源节点发送一个 MIGRATE <target_ip> <target_port> <key_name> 0

  命令，将选中的键原子地从源节点迁移到目标节点。

• 充分执行步骤 3 和 4，知道所有键值对都被迁移至目标节点

• 向集群中的任一节点发送 CLUSTER SETSLOT

在重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现：属于被迁移槽的一部分键值对保存在源节点中，而另一部分保存在目标节点中。

当客户端向源节点发送一个与数据库键有关的命令，且要处理的键恰好就属于正在被迁移的槽时：

• 源节点现在自己的数据库中查找键，如果找到，直接执行命令。

• 否则，源节点向客户端返回 ASK 错误，指引客户端转向正在导入槽的目标节点，再次发送命令。

节点收到一个关于键 key 的命令请求，先查找 key 所属的槽 i 是否在自己的数据库里，如果在，直接执行命令。

如果不在，节点会检查自己的 clusterState.migrating_slots_to[i]，看槽 i 是否正在被迁移。如果是，返回客户端一个 ASK 错误。

接到 ASK 错误的客户端根据错误提供的 IP 地址和端口，转向目标节点，先向其发送一个 ASKING 命令，之后再重新发送原来要执行的命令。如果不先发送一个 ASKING 命令，那么会被节点拒绝执行，并返回 MOVED 错误。

ASKING 命令唯一要做的就是打开发送该命令的客户端的 REDIS_ASKING 标识。该标识是一次性标识，节点执行了一个带有该标识的客户端发来的命令后，标识就被移除。换句话说每次 ASKING 相当于通知 redis 节点我接下来要访问一次你正在迁移的 slot 中的数据。

ASK 和 MOVED 的区别：

• MOVED 错误代表槽的负责权已经转移。

• ASK 错误是迁移槽过程中的临时措施。接收 ASK 指引的转向，不会对客户端今后发送关于槽 i 的命令请求有任何影响，客户端仍会将请求发送至目前负责处理槽 i 的节点，除非 ASK 错误再次出现。

复制

Redis 集群中的 master 用于处理槽，slave 用于复制某个 master，并在被复制的 master 下线时，代替 master 继续处理命令请求。

故障转移

集群中的每个节点都会定期向其它节点发送 PING 消息，检测对方是否在线。各个节点都会通过消息来交换其它节点的状态信息。

当一个 master A 通过消息得知 master B 认为 master C 进入疑似下线状态。

如果在一个集群里，半数以上负责处理槽的 master 都将某个 master X 报告为疑似下线，那么 X 就被标记为下线。将 X 标记为下线的节点向集群广播关于 X 的 FAIL 消息，收到消息的节点会立即将 X 标记为已下线。

当一个 slave 发现自己正在复制的 master 已下线，会开始对其进行故障转移：

• 复制 master 的所有从节点里，会有一个 slave 被选中。

• 被选中的 slave 执行 SALVEOF no one 命令，成为新的 master。

• 新 master 会撤销所有对已下线 master 的槽指派，并指派给自己。

• 新 master 向集群广播一条 PONG 消息，宣布自己成为 master。

• 新 master 开始接收和处理自己负责的槽有关的命令请求。

新的 master 是选举产生的：

• 集群中的配置纪元是一个自增计数器，初始值为 0。

• 集群中的某个节点开始一次故障转移操作时，集群配置纪元的值+1。

• 对于每个配置纪元，集群中每个负责处理槽的 master 都有一次投票机会，而第一个向 master 要求投票的 slave 将获得投票权。

• 当 slave 发现自己正在复制的 master 已下线，会广播一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST，要求收到消息的 master 给自己投票。

• 如果一个 master 有投票权（正在处理槽），且未投票给其它 slave，那么 master 会向要求投票的 slave 返回一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，表示支持它成为新 master。

• 每个参与选举的 slave 都会接收到 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，根据消息的个数来统计自己获得几票。

• 一个 slave 收集到大于 N/2+1 的支持票后，会当选新 master。

• 因为每个配置纪元里，拥有投票权的 master 只有一票，因此新的 master 只会有一个。

• 如果一个配置纪元中没有选举出新 master，那么集群进入一个新的配置纪元，继续选举。

Redis 分布式锁

Redis 官方站的一篇文章提出了一种权威的基于 Redis 实现分布式锁的方式名叫 Redlock，此种方式比原先的单节点的方法更安全。它可以保证以下特性：

• 安全特性：互斥访问，即永远只有一个 client 能拿到锁

• 避免死锁：最终 client 都可能拿到锁，不会出现死锁的情况，即使原本锁住某资源的 client crash 了或者出现了网络分区

• 容错性：只要大部分 Redis 节点存活就可以正常提供服务

接下来我们会先后介绍单节点的实现，以及多节点的实现。

单节点实现

SET resource_name my_random_value NX PX 30000

主要依靠上述命令，该命令仅当 Key 不存在时（NX 保证）set 值，并且设置过期时间 3000ms （PX 保证），值 my_random_value 必须是所有 client 和所有锁请求发生期间唯一的，释放锁的逻辑是：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

上述实现可以避免释放另一个 client 创建的锁，如果只有 del 命令的话，那么如果 client1 拿到 lock1 之后因为某些操作阻塞了很长时间，此时 Redis 端 lock1 已经过期了并且已经被重新分配给了 client2，那么 client1 此时再去释放这把锁就会造成 client2 原本获取到的锁被 client1 无故释放了，但现在为每个 client 分配一个 unique 的 string 值可以避免这个问题。至于如何去生成这个 unique string，方法很多随意选择一种就行了。

RedLock

算法很易懂，起 5 个 master 节点，分布在不同的机房尽量保证可用性。为了获得锁，client 会进行如下操作：

1. 得到当前的时间，微秒单位

2. 尝试顺序地在 5 个实例上申请锁，当然需要使用相同的 key 和 random value，这里一个 client 需要合理设置与 master 节点沟通的 timeout 大小，避免长时间和一个 fail 了的节点浪费时间

3. 当 client 在大于等于 3 个 master 上成功申请到锁的时候，且它会计算申请锁消耗了多少时间，这部分消耗的时间采用获得锁的当下时间减去第一步获得的时间戳得到，如果锁的持续时长（lock validity time）比流逝的时间多的话，那么锁就真正获取到了。

4. 如果锁申请到了，那么锁真正的 lock validity time 应该是 origin（lock validity time） - 申请锁期间流逝的时间

5. 如果 client 申请锁失败了，那么它就会在少部分申请成功锁的 master 节点上执行释放锁的操作，重置状态

失败重试

如果一个 client 申请锁失败了，那么它需要稍等一会在重试避免多个 client 同时申请锁的情况，最好的情况是一个 client 需要几乎同时向 5 个 master 发起锁申请。另外就是如果 client 申请锁失败了它需要尽快在它曾经申请到锁的 master 上执行 unlock 操作，便于其他 client 获得这把锁，避免这些锁过期造成的时间浪费，当然如果这时候网络分区使得 client 无法联系上这些 master，那么这种浪费就是不得不付出的代价了。

放锁

放锁操作很简单，就是依次释放所有节点上的锁就行了

故障恢复

如果我们的节点没有持久化机制，client 从 5 个 master 中的 3 个处获得了锁，然后其中一个重启了，这是注意 整个环境中又出现了 3 个 master 可供另一个 client 申请同一把锁！违反了互斥性。如果我们开启了 AOF 持久化那么情况会稍微好转一些，因为 Redis 的过期机制是语义层面实现的，所以在 server 挂了的时候时间依旧在流逝，重启之后锁状态不会受到污染。但是考虑断电之后呢，AOF 部分命令没来得及刷回磁盘直接丢失了，除非我们配置刷回策略为 fsnyc = always，但这会损伤性能。解决这个问题的方法是，当一个节点重启之后，我们规定在 max TTL 期间它是不可用的，这样它就不会干扰原本已经申请到的锁，等到它 crash 前的那部分锁都过期了，环境不存在历史锁了，那么再把这个节点加进来正常工作。

RedLock 的问题

在分布式环境下，锁比 mutex 这类复杂，因为涉及到不同节点、网络通信并且他们随时可能无征兆的 fail 。假设了一个场景，一个 client 要修改一个文件，它先申请得到锁，然后修改文件写回，放锁。另一个 client 再申请锁 ... 代码流程如下：

// THIS CODE IS BROKEN
function writeData(filename, data) {
    var lock = lockService.acquireLock(filename);
    if (!lock) {
        throw 'Failed to acquire lock';
    }


    try {
        var file = storage.readFile(filename);
        var updated = updateContents(file, data);
        storage.writeFile(filename, updated);
    } finally {
        lock.release();
    }
}

可惜即使你的锁服务非常完美，上述代码还是可能跪，下面的流程图会告诉你为什么：上述图中，得到锁的 client1 在持有锁的期间 pause 了一段时间，例如 GC 停顿。锁有过期时间（一般叫租约，为了防止某个 client 崩溃之后一直占有锁），但是如果 GC 停顿太长超过了锁租约时间，此时锁已经被另一个 client2 所得到，原先的 client1 还没有感知到锁过期，那么奇怪的结果就会发生，曾经 HBase 就发生过这种 Bug。即使你在 client1 写回之前检查一下锁是否过期也无助于解决这个问题，因为 GC 可能在任何时候发生，即使是你非常不便的时候（在最后的检查与写操作期间）。如果你认为自己的程序不会有长时间的 GC 停顿，还有其他原因会导致你的进程 pause。例如进程可能读取尚未进入内存的数据，所以它得到一个 page fault 并且等待 page 被加载进缓存；还有可能你依赖于网络服务；或者其他进程占用 CPU；或者其他人意外发生 SIGSTOP 等。

时钟问题导致 RedLock 不可靠：

1. client1 从 ABC 三个节点处申请到锁，DE 由于网络原因请求没有到达

2. C 节点的时钟往前推了，导致 lock 过期

3. client2 在 CDE 处获得了锁，AB 由于网络原因请求未到达

4. 此时 client1 和 client2 都获得了锁

网络延时导致 RedLock 不可靠：

1. client1 从 ABCDE 处获得了锁

2. 当获得锁的 response 还没到达 client1 时 client1 进入 GC 停顿

3. 停顿期间锁已经过期了

4. client2 在 ABCDE 处获得了锁

5. client1 GC 完成收到了获得锁的 response，此时两个 client 又拿到了同一把锁

这些例子说明了，仅有在你假设了一个同步性系统模型的基础上，Redlock 才能正常工作，也就是系统能满足以下属性：

1. 进程停顿边界，即进程停顿一定在某个最大时间之内

2. 时钟错误边界，即不会从一个坏的 NTP 服务器处取得时间

3. 网络延时边界，即假设数据包一定能在某个最大延时之内到达

Redlock 实在不是一个好的选择，对于需求性能的分布式锁应用它太重了且成本高；对于需求正确性的应用来说它不够安全。因为它对高危的时钟或者说其他上述列举的情况进行了不可靠的假设，如果你的应用只需要高性能的分布式锁不要求多高的正确性，那么单节点 Redis 够了；如果你的应用想要保住正确性，那么不建议 Redlock，建议使用一个合适的一致性协调系统。

Fencing

为了解决 RedLock 的问题，有人提出每次写操作时加入一个 fencing token。这个场景下，fencing token 可以是一个递增的数字（lock service 可以做到），每次有 client 申请锁就递增一次：client1 申请锁同时拿到 token33，然后它进入长时间的停顿锁也过期了。client2 得到锁和 token34 写入数据，紧接着 client1 活过来之后尝试写入数据，自身 token33 比 34 小因此写入操作被拒绝。注意这需要存储层来检查 token，但这并不难实现。如果你使用 Zookeeper 作为 lock service 的话那么你可以使用 zxid 作为递增数字。但是对于 Redlock 来说，没什么生成 fencing token 的方式，那怎么修改 Redlock 算法使其能产生 fencing token 呢？这似乎并不简单，因为产生 token 需要单调递增，除非在单节点 Redis 上完成，但是这又没有高可靠性，这就需要引进一致性协议来让 Redlock 产生可靠的 fencing token。

Fencing 的依赖

我认为即便使用 Fencing 也需要建立在一个假设之上：确认 token+存储过程这个整体需要是原子性的并且是互斥的。也就说在存储的过程中不应该出现 clientX 获取到锁从而得到 token35，并且在 Client2 的存储过程还没结束的时候，开始了自己的存储过程。我觉得这个问题和引入 Fencing 机制的原因本质上是一致的，我们因为 client1 无法保证在锁的持有期间执行完互斥操作才引入了 Fencing，但是它只保证了明确得知锁超时后，无法执行互斥操作。但是如果在互斥操作的过程中锁超时了，另一个 clientX 获取到锁，也会和当前正在进行的操作冲突。

我们使用分布式锁一般都是用来控制多个节点之间对某一共享资源的访问，如前面提到的 Client1，Client2，和 Storage，一般来说他们都是互相独立的。

如果我们要进行的互斥操作（图中修改 Storage），是在单机上执行的，那么问题很好解决。可以对修改的操作入队，然后从队列中依次取出并按如下过程操作：

1. 确认 token 合法性

2. 如果 token 合法，执行存储过程，否则驳回

这样的话，就能达到前面提到的条件『确认 token+存储过程这个整体需要是原子性的并且是互斥的』，即便在存储过程中锁被另一个 ClientX 获得，ClientX 的操作也会在当前 Client2 的操作执行完成后才开始，并且整个过程也是逻辑上说的通的，Client2 先获得了锁，它的存储过程应该先于 ClientX 完成。而如果 ClientX 获得锁的时候，Client2 还没开始确认 token，那么 Client2 的操作就会被驳回。

但是如果图中的 Storage 是一个网络存储服务，并且网络存储服务没办法帮你确认 token 的可靠性，这时候 Fencing 机制就形同虚设，我们最终会绕回最初的问题。

很多人都认为，如果你想构建一个更安全的分布式锁，那么应该使用 ZooKeeper，而不是 Redis。那么，为了对比的目的，让我们先暂时脱离开本文的题目，讨论一下基于 ZooKeeper 的分布式锁能提供绝对的安全吗？它需要 fencing token 机制的保护吗？

ZooKeeper 锁

我们不得不提一下分布式专家 Flavio Junqueira 所写的一篇 blog，题目叫“Note on fencing and distributed locks”。他在文中给出了一个基于 ZooKeeper 构建分布式锁的描述（当然这不是唯一的方式）：

• 客户端尝试创建一个 znode 节点，比如/lock。那么第一个客户端就创建成功了，相当于拿到了锁；而其它的客户端会创建失败（znode 已存在），获取锁失败。

• 持有锁的客户端访问共享资源完成后，将 znode 删掉，这样其它客户端接下来就能来获取锁了。

• znode 应该被创建成 ephemeral 的。这是 znode 的一个特性，它保证如果创建 znode 的那个客户端崩溃了，那么相应的 znode 会被自动删除。这保证了锁一定会被释放。

看起来这个锁相当完美，没有 Redlock 过期时间的问题，而且能在需要的时候让锁自动释放。但仔细考察的话，并不尽然。

ZooKeeper 是怎么检测出某个客户端已经崩溃了呢？实际上，每个客户端都与 ZooKeeper 的某台服务器维护着一个 Session，这个 Session 依赖定期的心跳(heartbeat)来维持。如果 ZooKeeper 长时间收不到客户端的心跳（这个时间称为 Sesion 的过期时间），那么它就认为 Session 过期了，通过这个 Session 所创建的所有的 ephemeral 类型的 znode 节点都会被自动删除。

设想如下的执行序列：

• 客户端 1 创建了 znode 节点/lock，获得了锁。

• 客户端 1 进入了长时间的 GC pause。

• 客户端 1 连接到 ZooKeeper 的 Session 过期了。znode 节点/lock 被自动删除。

• 客户端 2 创建了 znode 节点/lock，从而获得了锁。

• 客户端 1 从 GC pause 中恢复过来，它仍然认为自己持有锁。

最后，客户端 1 和客户端 2 都认为自己持有了锁，冲突了。这与之前 Martin 在文章中描述的由于 GC pause 导致的分布式锁失效的情况类似。

看起来，用 ZooKeeper 实现的分布式锁也不一定就是安全的。该有的问题它还是有。但是，ZooKeeper 作为一个专门为分布式应用提供方案的框架，它提供了一些非常好的特性，是 Redis 之类的方案所没有的。像前面提到的 ephemeral 类型的 znode 自动删除的功能就是一个例子。

还有一个很有用的特性是 ZooKeeper 的 watch 机制。这个机制可以这样来使用，比如当客户端试图创建/lock 的时候，发现它已经存在了，这时候创建失败，但客户端不一定就此对外宣告获取锁失败。客户端可以进入一种等待状态，等待当/lock 节点被删除的时候，ZooKeeper 通过 watch 机制通知它，这样它就可以继续完成创建操作（获取锁）。这可以让分布式锁在客户端用起来就像一个本地的锁一样：加锁失败就阻塞住，直到获取到锁为止。这样的特性 Redlock 就无法实现。

最后分布式锁的问题又落到了资源服务器的责任上来，我们无法在一个不提供任何锁校验支持的共享资源服务上使用分布式锁。接下来让我们通过 Chubby 的例子来看一下，如果共享资源服务提供了锁校验支持，整个流程应该是什么样的。

Chubby 锁

Chubby 是 Google 内部使用的分布式锁服务，有点类似于 ZooKeeper，但也存在很多差异。

Chubby 自然也考虑到了延迟造成的锁失效的问题。论文里有一段描述如下：

a process holding a lock L may issue a request R, but then fail. Another process may ac- quire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on inconsistent data. （译文：一个进程持有锁 L，发起了请求 R，但是请求失败了。另一个进程获得了锁 L 并在请求 R 到达目的方之前执行了一些动作。如果后来请求 R 到达了，它就有可能在没有锁 L 保护的情况下进行操作，带来数据不一致的潜在风险。）

这跟我们之前的分析大同小异。

Chubby 给出的用于解决（缓解）这一问题的机制称为 sequencer，类似于 fencing token 机制。锁的持有者可以随时请求一个 sequencer，这是一个字节串，它由三部分组成：

• 锁的名字。

• 锁的获取模式（排他锁还是共享锁）。

• lock generation number（一个 64bit 的单调递增数字）。作用相当于 fencing token。

客户端拿到 sequencer 之后，在操作资源的时候把它传给资源服务器。然后，资源服务器负责对 sequencer 的有效性进行检查。检查可以有种方式：

• 调用 Chubby 提供的 API，CheckSequencer()，将整个 sequencer 传进去进行检查。这个检查是为了保证客户端持有的锁在进行资源访问的时候仍然有效。

• 将客户端传来的 sequencer 与资源服务器当前观察到的最新的 sequencer 进行对比检查。

当然，出于兼容性的考虑，资源服务本身可能是已经实现的产品，要想让其加入检查逻辑可能并不容易，所以 Chubby 还提供了一种自身的机制：

• lock-delay。Chubby 允许客户端为持有的锁指定一个 lock-delay 的时间值（默认是 1 分钟）。当 Chubby 发现客户端被动失去联系的时候，并不会立即释放锁，而是会在 lock-delay 指定的时间内阻止其它客户端获得这个锁。这是为了在把锁分配给新的客户端之前，让之前持有锁的客户端有充分的时间把请求队列排空(draining the queue)，尽量防止出现延迟到达的未处理请求。

可见，为了应对锁失效问题，Chubby 提供的三种处理方式：CheckSequencer()检查、与最新的 sequencer 对比、lock-delay，它们对于安全性的保证是从强到弱的。而且，这些处理方式本身都没有保证提供绝对的正确性(correctness)。但是，Chubby 确实提供了单调递增的 lock generation number，这就允许资源服务器在需要的时候，利用它提供更强的安全性保障。

看了很多文章，最后对分布式锁的讨论都止于 Chubby，似乎整个工业界就没有达到完全安全性的分布式锁实现。我觉得要想达到完全的安全性，可能就要求整个分布式资源服务中大部分节点进行原子性的 check and set，只有当大部分节点都成功 check and set 后，才算是本次加锁操作成功，如果最终只有低于一半的节点 check and set 成功，其他节点 check 时发现 token 失效，那么就要进行回滚。其中每一个节点确认超过半数节点修改成功或者自己回滚结束后，就可以处理下一次加锁写请求了，而在此之前下一次加锁写的请求需要被阻塞，以此来达成单节点的 check and set 的原子性。

常见问题

缓存雪崩

缓存同一时间大面积的失效，所以，后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。

解决办法：

• 事前：尽量保证整个 redis 集群的高可用性，发现机器宕机尽快补上。选择合适的内存淘汰策略。

• 事中：本地 ehcache 缓存 + hystrix 限流&降级，避免 MySQL 崩掉

• 事后：利用 redis 持久化机制保存的数据尽快恢复缓存

缓存穿透

一般是黑客故意去请求缓存中不存在的数据，导致所有的请求都落到数据库上，造成数据库短时间内承受大量请求而崩掉。

解决办法：有很多种方法可以有效地解决缓存穿透问题，最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的 bitmap 中，一个一定不存在的数据会被 这个 bitmap 拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法（我们采用的就是这种），如果一个查询返回的数据为空（不管是数 据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

缓存击穿

在平常高并发的系统中，大量的请求同时查询一个 key 时，此时这个 key 正好失效了，就会导致大量的请求都打到数据库上面去。这种现象我们称为缓存击穿。

解决办法：上面的现象是多个线程同时去查询数据库的这条数据，那么我们可以在第一个查询数据的请求上使用一个 互斥锁来锁住它。其他的线程走到这一步拿不到锁就等着，等第一个线程查询到了数据，然后做缓存。后面的线程进来发现已经有缓存了，就直接走缓存。

热点数据集中失效

我们在设置缓存的时候，一般会给缓存设置一个失效时间，过了这个时间，缓存就失效了。对于一些热点的数据来说，当缓存失效以后会存在大量的请求过来，然后打到数据库去，从而可能导致数据库崩溃的情况。

解决办法：为了避免这些热点的数据集中失效，那么我们在设置缓存过期时间的时候，我们让他们失效的时间错开。或者队列限流。

并发竞争 Key

所谓 Redis 的并发竞争 Key 的问题也就是多个系统同时对一个 key 进行操作，但是最后执行的顺序和我们期望的顺序不同，这样也就导致了结果的不同！

解决办法： 分布式锁（zookeeper 和 redis 都可以实现分布式锁）。

与数据库存储一致

你只要用缓存，就可能会涉及到缓存与数据库双存储双写，你只要是双写，就一定会有数据一致性的问题，那么你如何解决一致性问题？

一般来说，就是如果你的系统不是严格要求缓存+数据库必须一致性的话，缓存可以稍微的跟数据库偶尔有不一致的情况，最好不要做这个方案，读请求和写请求串行化，串到一个内存队列里去，这样就可以保证一定不会出现不一致的情况

串行化之后，就会导致系统的吞吐量会大幅度的降低，用比正常情况下多几倍的机器去支撑线上的一个请求。

参考内容

[1]https://github.com/Snailclimb/JavaGuide/blob/master/docs/database/Redis/Redis.md

[2]https://github.com/Snailclimb/JavaGuide/blob/master/docs/database/Redis/Redis持久化.md

[3]https://github.com/Snailclimb/JavaGuide/blob/master/docs/database/Redis/Redlock分布式锁.md

[4]https://www.icode9.com/content-4-234062.html

[5]https://github.com/Snailclimb/JavaGuide/blob/master/docs/database/Redis/如何做可靠的分布式锁，Redlock真的可行么.md

[6]https://github.com/hellokangning/TechNote/tree/master/sql/redis

[7]http://zhangtielei.com/posts/blog-redlock-reasoning-part2.html