Redis 基础知识

一、介绍一下Redis

首先，肯定是去官网看看官方是怎么介绍Redis的啦。https://redis.io/topics/introduction

如果像我一样，英语可能不太好的，可能看不太懂。没事，咱们Chrome浏览器可以切换成中文的，中文是我们的母语，肯定没啥压力了。Eumm…

读完之后，发现中文也就那样了。

一大堆没见过的技术：lua(Lua脚本)、replication(复制)、Redis Sentinel(哨兵)、Redis Cluster(Redis 集群)，当然我们也会有看得懂的技术：transactions(事务)、different levels of on-disk persistence(数据持久化)、LRU eviction(LRU淘汰机制)..

至少官方介绍Redis的第一句应该是可以很容易看懂：”Redis is an open source (BSD licensed),in-memory data structure store, used as a database,cache and message broker.”
Redis是一个开源的，基于内存的数据结构存储，可用作于数据库、缓存、消息中间件。

  • 从官方的解释上，我们可以知道：Redis是基于内存，支持多种数据结构。
  • 从经验的角度上，我们可以知道：Redis常用作于缓存。

就我个人认为：学习一种新技术，先把握该技术整体的知识(思想)，再扣细节，这样学习起来会比较轻松一些。所以我们先以“内存”、“数据结构”、“缓存”来对Redis入门。

1.1为什么要用Redis？

从上面可知：Redis是基于内存，常用作于缓存的一种技术，并且Redis存储的方式是以key-value的形式。
我们可以发现这不就是Java的Map容器所拥有的特性吗，那为什么还需要Redis呢？

  • Java实现的Map是本地缓存，如果有多台实例(机器)的话，每个实例都需要各自保存一份缓存，缓存不具有一致性
  • Redis实现的是分布式缓存，如果有多台实例(机器)的话，每个实例都共享一份缓存，缓存具有一致性。
  • Java实现的Map不是专业做缓存的，JVM内存太大容易挂掉的。一般用做于容器来存储临时数据，缓存的数据随着JVM销毁而结束。Map所存储的数据结构，缓存过期机制等等是需要程序员自己手写的。
  • Redis是专业做缓存的，可以用几十个G内存来做缓存。Redis一般用作于缓存，可以将缓存数据保存在硬盘中，Redis重启了后可以将其恢复。原生提供丰富的数据结构、缓存过期机制等等简单好用的功能。

参考资料：

  • 为什么要用redis而不用map做缓存?https://segmentfault.com/q/1010000009106416

    1.2为什么要用缓存？

    如果我们的网站出现了性能问题(访问时间慢)，按经验来说，一般是由于数据库撑不住了。因为一般数据库的读写都是要经过磁盘的，而磁盘的速度可以说是相当慢的(相对内存来说)

  • 科普文：让 CPU 告诉你硬盘和网络到底有多慢https://zhuanlan.zhihu.com/p/24726196

Redis 基础知识 - 图1
数据库撑不住了
如果学过Mybaits、Hibernate的同学就可以知道，它们有一级缓存、二级缓存这样的功能(终究来说还是本地缓存)。目的就是为了：不用每次读取的时候，都要查一次数据库。
有了缓存之后，我们的访问就变成这样了：
Redis 基础知识 - 图2
有了缓存提高了并发和性能

二、Redis的数据结构

本文不会讲述命令的使用方式，具体的如何使用可查询API。

Redis支持丰富的数据结构，常用的有string、list、hash、set、sortset这几种。学习这些数据结构是使用Redis的基础！
“Redis is written in ANSI C”—>Redis由C语言编写
首先还是得声明一下，Redis的存储是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset这几种常用的。
image.gifredis数据结构
但要值得注意的是：Redis并没有直接使用这些数据结构来实现key-value数据库，而是基于这些数据结构创建了一个对象系统。

  • 简单来说：Redis使用对象来表示数据库中的键和值。每次我们在Redis数据库中新创建一个键值对时，至少会创建出两个对象。一个是键对象，一个是值对象。

Redis中的每个对象都由一个redisObject结构来表示：

  1. typedef struct redisObject{
  2.     // 对象的类型
  3.     unsigned type 4:;
  4.     // 对象的编码格式
  5.     unsigned encoding:4;
  6.     // 指向底层实现数据结构的指针
  7.     void * ptr;
  8.     //.....
  9. }robj;

image.gif数据结构对应的类型与编码
简单来说就是Redis对key-value封装成对象，key是一个对象，value也是一个对象。每个对象都有type(类型)、encoding(编码)、ptr(指向底层数据结构的指针)来表示。
image.gif以值为1006的字符串对象为例
下面我就来说一下我们Redis常见的数据类型：string、list、hash、set、sortset。它们的底层数据结构究竟是怎么样的！

2.1SDS简单动态字符串

简单动态字符串(Simple dynamic string,SDS)

Redis中的字符串跟C语言中的字符串，是有点差距的。
Redis使用sdshdr结构来表示一个SDS值：

  1. struct sdshdr{
  2.     // 字节数组，用于保存字符串
  3.     char buf[];
  4.     // 记录buf数组中已使用的字节数量，也是字符串的长度
  5.     int len;
  6.     // 记录buf数组未使用的字节数量
  7.     int free;
  8. }

例子：
image.gifSDS例子

2.1.1使用SDS的好处

SDS与C的字符串表示比较

  1. sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要O(1)。
  2. SDS不会发生溢出的问题，如果修改SDS时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。
  3. SDS可以减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。
  4. SDS是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

    2.2链表

    对于链表而言，我们不会陌生的了。在大学期间肯定开过数据结构与算法课程，链表肯定是讲过的了。在Java中Linkedxxx容器底层数据结构也是链表+[xxx]的。我们来看看Redis中的链表是怎么实现的：
    使用listNode结构来表示每个节点：
    1. typedef strcut listNode{
    2.  //前置节点
    3.  strcut listNode  *pre;
    4.  //后置节点
    5.  strcut listNode  *pre;
    6.  //节点的值
    7.  void  *value;
    8. }listNode
    使用listNode是可以组成链表了，Redis中使用list结构来持有链表：
    1. typedef struct list{
    2.  //表头结点
    3.  listNode  *head;
    4.  //表尾节点
    5.  listNode  *tail;
    6.  //链表长度
    7.  unsigned long len;
    8.  //节点值复制函数
    9.  void *(*dup) (viod *ptr);
    10.  //节点值释放函数
    11.  void  (*free) (viod *ptr);
    12.  //节点值对比函数
    13.  int (*match) (void *ptr,void *key);
    14. }list
    具体的结构如图：
    image.gif

    2.2.1Redis链表的特性

    Redis的链表有以下特性：
  • 无环双向链表
  • 获取表头指针，表尾指针，链表节点长度的时间复杂度均为O(1)
  • 链表使用void *指针来保存节点值，可以保存各种不同类型的值

    2.3哈希表

    声明：《Redis设计与实现》里边有“字典”这么一个概念，我个人认为还是直接叫哈希表比较通俗易懂。从代码上看：“字典”也是在哈希表基础上再抽象了一层而已。

在Redis中，key-value的数据结构底层就是哈希表来实现的。对于哈希表来说，我们也并不陌生。在Java中，哈希表实际上就是数组+链表的形式来构建的。下面我们来看看Redis的哈希表是怎么构建的吧。
在Redis里边，哈希表使用dictht结构来定义：

  1. typedef struct dictht{
  2.         //哈希表数组
  3.         dictEntry **table;  
  4.         //哈希表大小
  5.         unsigned long size;    
  6.         //哈希表大小掩码，用于计算索引值
  7.         //总是等于size-1
  8.         unsigned long sizemark;     
  9.         //哈希表已有节点数量
  10.         unsigned long used;
  11.     }dictht

哈希表的数据结构
image.gif
哈希表的数据结构
我们下面继续写看看哈希表的节点是怎么实现的吧：

  1. typedef struct dictEntry {
  2.         //键
  3.         void *key;
  4.         //值
  5.         union {
  6.             void *value;
  7.             uint64_tu64;
  8.             int64_ts64;
  9.         }v;    
  10.         //指向下个哈希节点，组成链表
  11.         struct dictEntry *next;
  12.     }dictEntry;

从结构上看，我们可以发现：Redis实现的哈希表和Java中实现的是类似的。只不过Redis多了几个属性来记录常用的值：sizemark(掩码)、used(已有的节点数量)、size(大小)。
同样地，Redis为了更好的操作，对哈希表往上再封装了一层(参考上面的Redis实现链表)，使用dict结构来表示：

  1. typedef struct dict {
  2.     //类型特定函数
  3.     dictType *type;
  4.     //私有数据
  5.     void *privdata;
  6.     //哈希表
  7.     dictht ht[2];
  8.     //rehash索引
  9.     //当rehash不进行时，值为-1
  10.     int rehashidx;  
  11. }dict;
  12. //-----------------------------------
  13. typedef struct dictType{
  14.     //计算哈希值的函数
  15.     unsigned int (*hashFunction)(const void * key);
  16.     //复制键的函数
  17.     void *(*keyDup)(void *private, const void *key);
  18.     //复制值得函数
  19.     void *(*valDup)(void *private, const void *obj);  
  20.     //对比键的函数
  21.     int (*keyCompare)(void *privdata , const void *key1, const void *key2)
  22.     //销毁键的函数
  23.     void (*keyDestructor)(void *private, void *key);
  24.     //销毁值的函数
  25.     void (*valDestructor)(void *private, void *obj);  
  26. }dictType

所以，最后我们可以发现，Redis所实现的哈希表最后的数据结构是这样子的：
image.gif
从代码实现和示例图上我们可以发现，Redis中有两个哈希表：

  • ht[0]：用于存放真实的key-vlaue数据
  • ht[1]：用于扩容(rehash)

Redis中哈希算法和哈希冲突跟Java实现的差不多，它俩差异就是：

  • Redis哈希冲突时：是将新节点添加在链表的表头。
  • JDK1.8后，Java在哈希冲突时：是将新的节点添加到链表的表尾。

    2.3.1rehash的过程

    下面来具体讲讲Redis是怎么rehash的，因为我们从上面可以明显地看到，Redis是专门使用一个哈希表来做rehash的。这跟Java一次性直接rehash是有区别的。

    在对哈希表进行扩展或者收缩操作时，reash过程并不是一次性地完成的，而是渐进式地完成的。

Redis在rehash时采取渐进式的原因：数据量如果过大的话，一次性rehash会有庞大的计算量，这很可能导致服务器一段时间内停止服务。
Redis具体是rehash时这么干的：

  • (1:在字典中维持一个索引计数器变量rehashidx，并将设置为0，表示rehash开始。
  • (2:在rehash期间每次对字典进行增加、查询、删除和更新操作时，除了执行指定命令外；还会将ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。
  • (3:字典操作不断执行，最终在某个时间点，所有的键值对完成rehash，这时将rehashidx设置为-1，表示rehash完成

  • (4:在渐进式rehash过程中，字典会同时使用两个哈希表ht[0]和ht[1]，所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话，服务器会优先查找ht[0]，如果不存在，再查找ht[1]，诸如此类。此外当执行新增操作时，新的键值对一律保存到ht[1]，不再对ht[0]进行任何操作，以保证ht[0]的键值对数量只减不增，直至变为空表。

    2.4跳跃表(shiplist)

    跳跃表(shiplist)是实现sortset(有序集合)的底层数据结构之一！
    跳跃表可能对于大部分人来说不太常见，之前我在学习的时候发现了一篇不错的文章讲跳跃表的，建议大家先去看完下文再继续回来阅读：

  • 漫画算法：什么是跳跃表？http://blog.jobbole.com/111731/

Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成。其中zskiplist保存跳跃表的信息(表头，表尾节点，长度)，zskiplistNode则表示跳跃表的节点。
按照惯例，我们来看看zskiplistNode跳跃表节点的结构是怎么样的：

  1. typeof struct zskiplistNode {
  2.         // 后退指针
  3.         struct zskiplistNode *backward;
  4.         // 分值
  5.         double score;
  6.         // 成员对象
  7.         robj *obj;
  8.         // 层
  9.         struct zskiplistLevel {
  10.                 // 前进指针
  11.                 struct zskiplistNode *forward;
  12.                 // 跨度
  13.                 unsigned int span;
  14.         } level[];
  15. } zskiplistNode;

zskiplistNode的对象示例图(带有不同层高的节点)：
Redis 基础知识 - 图10
带有不同层高的节点
示例图如下：
Redis 基础知识 - 图11
跳跃表节点的示例图
zskiplist的结构如下：

  1. typeof struct zskiplist {
  2.         // 表头节点，表尾节点
  3.         struct skiplistNode *header,*tail;
  4.         // 表中节点数量
  5.         unsigned long length;
  6.         // 表中最大层数
  7.         int level;
  8. } zskiplist;

最后我们整个跳跃表的示例图如下：
image.png
image.gif跳跃表示例图

2.5整数集合(intset)

整数集合是set(集合)的底层数据结构之一。当一个set(集合)只包含整数值元素，并且元素的数量不多时，Redis就会采用整数集合(intset)作为set(集合)的底层实现。
整数集合(intset)保证了元素是不会出现重复的，并且是有序的(从小到大排序)，intset的结构是这样子的：

  1. typeof struct intset {
  2.         // 编码方式
  3.         unit32_t encoding;
  4.         // 集合包含的元素数量
  5.         unit32_t lenght;
  6.         // 保存元素的数组
  7.         int8_t contents[];
  8. } intset;

intset示例图：
image.png
image.gifintset示例图
说明：虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值：

  • INTSET_ENC_INT16
  • INTSET_ENC_INT32
  • INTSET_ENC_INT64

从编码格式的名字我们就可以知道，16,32,64编码对应能存放的数字范围是不一样的。16明显最少，64明显最大。
如果本来是INTSET_ENC_INT16的编码，想要存放大于INTSET_ENC_INT16编码能存放的整数值，此时就得编码升级(从16升级成32或者64)。步骤如下：

  • 1）根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
  • 2）将底层数组现有的所以元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
  • 3）将新元素添加到底层数组。

另外一提：只支持升级操作，并不支持降级操作。

2.6压缩列表(ziplist)

压缩列表(ziplist)是list和hash的底层实现之一。如果list的每个都是小整数值，或者是比较短的字符串，压缩列表(ziplist)作为list的底层实现。
压缩列表(ziplist)是Redis为了节约内存而开发的，是由一系列的特殊编码的连续内存块组成的顺序性数据结构。
压缩列表结构图例如下：
image.png
image.gif压缩列表的组成部分
下面我们看看节点的结构图：
image.png
image.gif

压缩列表从表尾节点倒序遍历，首先指针通过zltail偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。

三、Redis中数据结构的对象

再次看回这张图，觉不觉得就很好理解了？
image.png
数据结构对应的类型与编码

3.1字符串(stirng)对象

在上面的图我们知道string类型有三种编码格式：

  • int：整数值，这个整数值可以使用long类型来表示
    • 如果是浮点数，那就用embstr或者raw编码。具体用哪个就看这个数的长度了
  • embstr：字符串值，这个字符串值的长度小于32字节
  • raw：字符串值，这个字符串值的长度大于32字节

embstr和raw的区别：

  • raw分配内存和释放内存的次数是两次，embstr是一次
  • embstr编码的数据保存在一块连续的内存里面

编码之间的转换：

  • int类型如果存的不再是一个整数值，则会从int转成raw

  • embstr是只读的，在修改的时候回从embstr转成raw

    3.2列表(list)对象

    在上面的图我们知道list类型有两种编码格式：

  • ziplist：字符串元素的长度都小于64个字节&&总数量少于512个

  • linkedlist：字符串元素的长度大于64个字节||总数量大于512个

ziplist编码的列表结构：

  1. redis > RPUSH numbers 1 "three" 5
  2.     (integer) 3

image.png
image.gifziplist的列表结构
linkedlist编码的列表结构：
image.png
image.giflinkedlist编码的列表结构
编码之间的转换：

  • 原本是ziplist编码的，如果保存的数据长度太大或者元素数量过多，会转换成linkedlist编码的。

    3.3哈希(hash)对象

    在上面的图我们知道hash类型有两种编码格式：

  • ziplist：key和value的字符串长度都小于64字节&&键值对总数量小于512

  • hashtable：key和value的字符串长度大于64字节||键值对总数量大于512

ziplist编码的哈希结构：
image.png
image.gifziplist编码的哈希结构1
image.png
image.gifziplist编码的哈希结构2
hashtable编码的哈希结构：
image.png
image.gifhashtable编码的哈希结构
编码之间的转换：

  • 原本是ziplist编码的，如果保存的数据长度太大或者元素数量过多，会转换成hashtable编码的。

    3.4集合(set)对象

    在上面的图我们知道set类型有两种编码格式：

  • intset：保存的元素全都是整数&&总数量小于512

  • hashtable：保存的元素不是整数||总数量大于512

intset编码的集合结构：
Redis 基础知识 - 图31intset编码的集合结构
hashtable编码的集合结构：
Redis 基础知识 - 图32
hashtable编码的集合结构
编码之间的转换：

  • 原本是intset编码的，如果保存的数据不是整数值或者元素数量大于512，会转换成hashtable编码的。

    3.5有序集合(sortset)对象

    在上面的图我们知道set类型有两种编码格式：

  • ziplist：元素长度小于64&&总数量小于128

  • skiplist：元素长度大于64||总数量大于128

ziplist编码的有序集合结构：
Redis 基础知识 - 图33
ziplist编码的有序集合结构1
Redis 基础知识 - 图34
ziplist编码的有序集合结构2
skiplist编码的有序集合结构：
Redis 基础知识 - 图35
skiplist编码的有序集合结构
有序集合(sortset)对象同时采用skiplist和哈希表来实现：

  • skiplist能够达到插入的时间复杂度为O(logn)，根据成员查分值的时间复杂度为O(1)

编码之间的转换：

  • 原本是ziplist编码的，如果保存的数据长度大于64或者元素数量大于128，会转换成skiplist编码的。

    3.6Redis对象一些细节

  • (1：服务器在执行某些命令的时候，会先检查给定的键的类型能否执行指定的命令。

    • 比如我们的数据结构是sortset，但你使用了list的命令。这是不对的，服务器会检查一下我们的数据结构是什么才会进一步执行命令
  • (2：Redis的对象系统带有引用计数实现的内存回收机制。
    • 对象不再被使用的时候，对象所占用的内存会释放掉
  • (3：Redis会共享值为0到9999的字符串对象

  • (4：对象会记录自己的最后一次被访问时间，这个时间可以用于计算对象的空转时间。

    最后

    本文主要讲了一下Redis常用的数据结构，以及这些数据结构的底层设计是怎么样的。整体来说不会太难，因为这些数据结构我们在学习的过程中多多少少都接触过了，《Redis设计与实现》这本书写得也足够通俗易懂。
    至于我们在使用的时候挑选哪些数据结构作为存储，可以简单看看：

  • string—>简单的key-value

  • list—>有序列表(底层是双向链表)—>可做简单队列
  • set—>无序列表(去重)—>提供一系列的交集、并集、差集的命令
  • hash—>哈希表—>存储结构化数据
  • sortset—>有序集合映射(member-score)—>排行榜

如果大家有更好的理解方式或者文章有错误的地方还请大家不吝在评论区留言，大家互相学习交流~~~
参考博客：

参考资料：

  • 《Redis设计与实现》
  • 《Redis实战》

一、Redis服务器中的数据库

我们应该都用过MySQL，MySQL我们可以在里边创建好几个库：
Redis 基础知识 - 图36
MySQL创建几个数据库
同样地，Redis服务器中也有数据库这么一个概念。如果不指定具体的数量，默认会有16个数据库。
Redis 基础知识 - 图37
通过SELECT命令可以切换到0~15的数据库
上面的命令我们也可以发现：当切换到15号数据库，存进15号库的数据，再切换到0号数据库时，是获取不到的！

  • 这说明，数据库与数据库之间的数据是隔离的。

    1.1Redis数据库的原理

    Redis服务器用redisServer结构体来表示，其中redisDb是一个数组，用来保存所有的数据库，dbnum代表数据库的数量(这个可以配置，默认是16)
    1. struct redisServer{  
    2.   //redisDb数组,表示服务器中所有的数据库
    3.   redisDb *db;  
    4.   //服务器中数据库的数量
    5.   int dbnum;  
    6. };
    我们知道Redis是C/S结构，Redis客户端通过redisClient结构体来表示：
    1. typedef struct redisClient{  
    2.   //客户端当前所选数据库
    3.   redisDb *db;  
    4. }redisClient;
    Redis客户端连接Redis服务端时的示例图：
    Redis 基础知识 - 图38
    Redis客户端连接Redis服务端时的示例图
    Redis中对每个数据库用redisDb结构体来表示：
    1. typedef struct redisDb { 
    2.   int id;         // 数据库ID标识
    3.   dict *dict;     // 键空间，存放着所有的键值对              
    4.   dict *expires;  // 过期哈希表，保存着键的过期时间                          
    5.   dict *watched_keys; // 被watch命令监控的key和相应client    
    6.   long long avg_ttl;  // 数据库内所有键的平均TTL（生存时间）     
    7. } redisDb;
    从代码上我们可以发现最重要的应该是dict *dict，它用来存放着所有的键值对。对于dict数据结构(哈希表)我们在上一篇也已经详细说了。一般我们将存储所有键值对的dict称为键空间。
    键空间示意图：
    Redis 基础知识 - 图39
    键空间示意图

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

例如：

  1. redis > GET message
  2. "hello world"

Redis 基础知识 - 图40
查找键的示意图

1.2键的过期时间

Redis是基于内存，内存是比较昂贵的，容量肯定比不上硬盘的。就我们现在一台普通的机子，可能就8G内存，但硬盘随随便便都1T了。
因为我们的内存是有限的。所以我们会干掉不常用的数据，保留常用的数据。这就需要我们设置一下键的过期(生存)时间了。

  • 设置键的生存时间可以通过EXPIRE或者PEXPIRE命令。
  • 设置键的过期时间可以通过EXPIREAT或者PEXPIREAT命令。

其实EXPIRE、PEXPIRE、EXPIREAT这三个命令都是通过PEXPIREAT命令来实现的。
我们在redisDb结构体中还发现了dict *expires;属性，存放所有键过期的时间。
举个例子基本就可以理解了：

  1. redis > PEXPIREAT message 1391234400000
  2. (integer) 1

设置了message键的过期时间为1391234400000
Redis 基础知识 - 图41
新增一个过期时间的键
既然有设置过期(生存)时间的命令，那肯定也有移除过期时间，查看剩余生存时间的命令了：

  • PERSIST(移除过期时间)
  • TTL(Time To Live)返回剩余生存时间，以秒为单位

  • PTTL以毫秒为单位返回键的剩余生存时间

    1.2.1过期策略

    上面我们已经能够了解到：过期键是保存在哈希表中了。那这些过期键到了过期的时间，就会立马被删除掉吗？？
    要回答上面的问题，需要我们了解一下删除策略的知识，删除策略可分为三种

  • 定时删除(对内存友好，对CPU不友好)

    • 到时间点上就把所有过期的键删除了。
  • 惰性删除(对CPU极度友好，对内存极度不友好)
    • 每次从键空间取键的时候，判断一下该键是否过期了，如果过期了就删除。
  • 定期删除(折中)
    • 每隔一段时间去删除过期键，限制删除的执行时长和频率。

Redis采用的是惰性删除+定期删除两种策略，所以说，在Redis里边如果过期键到了过期的时间了，未必被立马删除的！

1.2.2内存淘汰机制

如果定期删除漏掉了很多过期key，也没及时去查(没走惰性删除)，大量过期key堆积在内存里，导致redis内存块耗尽了，咋整？
我们可以设置内存最大使用量，当内存使用量超出时，会施行数据淘汰策略。
Redis的内存淘汰机制有以下几种：
Redis 基础知识 - 图42
内存淘汰机制
一般场景：

使用 Redis 缓存数据时，为了提高缓存命中率，需要保证缓存数据都是热点数据。可以将内存最大使用量设置为热点数据占用的内存量，然后启用allkeys-lru淘汰策略，将最近最少使用的数据淘汰

二、Redis持久化

Redis是基于内存的，如果不想办法将数据保存在硬盘上，一旦Redis重启(退出/故障)，内存的数据将会全部丢失。

  • 我们肯定不想Redis里头的数据由于某些故障全部丢失(导致所有请求都走MySQL)，即便发生了故障也希望可以将Redis原有的数据恢复过来，这就是持久化的作用。

Redis提供了两种不同的持久化方法来讲数据存储到硬盘里边：

  • RDB(基于快照)，将某一时刻的所有数据保存到一个RDB文件中。

  • AOF(append-only-file)，当Redis服务器执行写命令的时候，将执行的写命令保存到AOF文件中。

    2.1RDB(快照持久化)

    RDB持久化可以手动执行，也可以根据服务器配置定期执行。RDB持久化所生成的RDB文件是一个经过压缩的二进制文件，Redis可以通过这个文件还原数据库的数据。
    Redis 基础知识 - 图43
    RDB文件还原数据
    有两个命令可以生成RDB文件：

  • SAVE会阻塞Redis服务器进程，服务器不能接收任何请求，直到RDB文件创建完毕为止。

  • BGSAVE创建出一个子进程，由子进程来负责创建RDB文件，服务器进程可以继续接收请求。

Redis服务器在启动的时候，如果发现有RDB文件，就会自动载入RDB文件(不需要人工干预)

  • 服务器在载入RDB文件期间，会处于阻塞状态，直到载入工作完成。

除了手动调用SAVE或者BGSAVE命令生成RDB文件之外，我们可以使用配置的方式来定期执行：
在默认的配置下，如果以下的条件被触发，就会执行BGSAVE命令

  1. save 900 1              #在900秒(15分钟)之后，至少有1个key发生变化，
  2.     save 300 10            #在300秒(5分钟)之后，至少有10个key发生变化
  3.     save 60 10000        #在60秒(1分钟)之后，至少有10000个key发生变化

原理大概就是这样子的(结合上面的配置来看)：

  1. struct redisServer{
  2.     // 修改计数器
  3.     long long dirty;
  4.     // 上一次执行保存的时间
  5.     time_t lastsave;
  6.     // 参数的配置
  7.     struct saveparam *saveparams;
  8. };

遍历参数数组，判断修改次数和时间是否符合，如果符合则调用besave()来生成RDB文件
Redis 基础知识 - 图44
Redis服务器的状态
总结：通过手动调用SAVE或者BGSAVE命令或者配置条件触发，将数据库某一时刻的数据快照，生成RDB文件实现持久化。

2.2AOF(文件追加)

上面已经介绍了RDB持久化是通过将某一时刻数据库的数据“快照”来实现的，下面我们来看看AOF是怎么实现的。

  • AOF是通过保存Redis服务器所执行的写命令来记录数据库的数据的。

Redis 基础知识 - 图45
AOF原理图
比如说我们对空白的数据库执行以下写命令：

  1. redis> SET meg "hello"
  2. OK
  3. redis> SADD fruits "apple" "banana" "cherry"
  4. (integer) 3
  5. redis> RPUSH numbers 128 256 512
  6. (integer) 3

Redis会产生以下内容的AOF文件：
Redis 基础知识 - 图46
AOF文件
这些都是以Redis的命令请求协议格式保存的。Redis协议规范(RESP)参考资料：

AOF持久化功能的实现可以分为3个步骤：

  • 命令追加：命令写入aof_buf缓冲区
  • 文件写入：调用flushAppendOnlyFile函数，考虑是否要将aof_buf缓冲区写入AOF文件中
  • 文件同步：考虑是否将内存缓冲区的数据真正写入到硬盘

Redis 基础知识 - 图47
AOF持久化步骤
flushAppendOnlyFile函数的行为由服务器配置的appendfsyn选项来决定的：

  1. appendfsync always     # 每次有数据修改发生时都会写入AOF文件。
  2.     appendfsync everysec   # 每秒钟同步一次，该策略为AOF的默认策略。
  3.     appendfsync no         # 从不同步。高效但是数据不会被持久化。

从字面上应该就更好理解了，这里我就不细说了…
下面来看一下AOF是如何载入与数据还原的：

  • 创建一个伪客户端(本地)来执行AOF的命令，直到AOF命令被全部执行完毕。

Redis 基础知识 - 图48
redis伪客户端载入AOF文件

2.2.1AOF重写

从前面的示例看出，我们写了三条命令，AOF文件就保存了三条命令。如果我们的命令是这样子的：

  1. redis > RPUSH list "Java" "3y"
  2. (integer)2
  3. redis > RPUSH list "Java3y"
  4. integer(3)
  5. redis > RPUSH list "yyy"
  6. integer(4)

同样地，AOF也会保存3条命令。我们会发现一个问题：上面的命令是可以合并起来成为1条命令的，并不需要3条。这样就可以让AOF文件的体积变得更小。
AOF重写由Redis自行触发(参数配置)，也可以用BGREWRITEAOF命令手动触发重写操作。

  • 要值得说明的是：AOF重写不需要对现有的AOF文件进行任何的读取、分析。AOF重写是通过读取服务器当前数据库的数据来实现的！

比如说现在有一个Redis数据库的数据如下：
Redis 基础知识 - 图49
Redis数据库的数据
新的AOF文件的命令如下，没有一条是多余的！
Redis 基础知识 - 图50
AOF重写后的命令

2.2.2AOF后台重写

Redis将AOF重写程序放到子进程里执行(BGREWRITEAOF命令)，像BGSAVE命令一样fork出一个子进程来完成重写AOF的操作，从而不会影响到主进程。
AOF后台重写是不会阻塞主进程接收请求的，新的写命令请求可能会导致当前数据库和重写后的AOF文件的数据不一致！
为了解决数据不一致的问题，Redis服务器设置了一个AOF重写缓冲区，这个缓存区会在服务器创建出子进程之后使用。
Redis 基础知识 - 图51
AOF后台重写过程

2.3RDB和AOF对过期键的策略

RDB持久化对过期键的策略：

  • 执行SAVE或者BGSAVE命令创建出的RDB文件，程序会对数据库中的过期键检查，已过期的键不会保存在RDB文件中。
  • 载入RDB文件时，程序同样会对RDB文件中的键进行检查，过期的键会被忽略。

RDB持久化对过期键的策略：

  • 如果数据库的键已过期，但还没被惰性/定期删除，AOF文件不会因为这个过期键产生任何影响(也就说会保留)，当过期的键被删除了以后，会追加一条DEL命令来显示记录该键被删除了
  • 重写AOF文件时，程序会对RDB文件中的键进行检查，过期的键会被忽略。

复制模式：

  • 主服务器来控制从服务器统一删除过期键(保证主从服务器数据的一致性)

    2.4RDB和AOF用哪个？

    RDB和AOF并不互斥，它俩可以同时使用。

  • RDB的优点：载入时恢复数据快、文件体积小。

  • RDB的缺点：会一定程度上丢失数据(因为系统一旦在定时持久化之前出现宕机现象，此前没有来得及写入磁盘的数据都将丢失。)
  • AOF的优点：丢失数据少(默认配置只丢失一秒的数据)。
  • AOF的缺点：恢复数据相对较慢，文件体积大

如果Redis服务器同时开启了RDB和AOF持久化，服务器会优先使用AOF文件来还原数据(因为AOF更新频率比RDB更新频率要高，还原的数据更完善)
可能涉及到RDB和AOF的配置：

  1. redis持久化，两种方式
  2. 1、rdb快照方式
  3. 2、aof日志方式
  4. ----------rdb快照------------
  5. save 900 1
  6. save 300 10
  7. save 60 10000
  8. stop-writes-on-bgsave-error yes
  9. rdbcompression yes
  10. rdbchecksum yes
  11. dbfilename dump.rdb
  12. dir /var/rdb/
  13. -----------Aof的配置-----------
  14. appendonly no # 是否打开 aof日志功能
  15. appendfsync always #每一个命令都立即同步到aof，安全速度慢
  16. appendfsync everysec
  17. appendfsync no 写入工作交给操作系统，由操作系统判断缓冲区大小，统一写入到aof  同步频率低，速度快
  18. no-appendfsync-on-rewrite yes 正在导出rdb快照的时候不要写aof
  19. auto-aof-rewrite-percentage 100
  20. auto-aof-rewrite-min-size 64mb 
  21. ./bin/redis-benchmark -n 20000

官网文档：

一、基础铺垫

在讲解Redis之前，我们先来一些基础的铺垫，有更好的阅读体验。

1.1网路编程

我们在初学Java的时候肯定会学过网络编程这一章节的，当时学完写的应用可能就是“网络聊天室”。
写出来的效果可能就是在console噼里啪啦的输入数据，然后噼里啪啦的返回数据，就完事了..(扎心了)
网络编程可简单分为TCP和UPD两种，一般我们更多关注的是TCP。TCP网络编程在Java中封装成Socket和SocketServer，我们来回顾一下最简单的TCP网络编程吧：
TCP客户端

  1. public class ClientDemo {
  2.     public static void main(String[] args) throws IOException {
  3.         //创建发送端的Socket对象
  4.         Socket s = new Socket("192.168.1.106",8888);
  5.         //Socket对象可以获取输出流
  6.         OutputStream os = s.getOutputStream();
  7.         os.write("hello,tcp,我来了".getBytes());
  8.         s.close();
  9.     }
  10. }

TCP服务端：

  1. public class ServerDemo {
  2.     public static void main(String[] args) throws IOException {
  3.         //创建接收端的Socket对象
  4.         ServerSocket ss = new ServerSocket(8888);
  5.         //监听客户端连接，返回一个对应的Socket对象
  6.         //侦听并接受到此套接字的连接，此方法会阻塞
  7.         Socket s = ss.accept();
  8.         //获取输入流，读取数据
  9.         InputStream is = s.getInputStream();
  10.         byte[] bys = new byte[1024];
  11.         int len = is.read(bys);
  12.         String str = new String (bys,0,len);
  13.         String ip = s.getInetAddress().getHostAddress();
  14.         System.out.println(ip + "    ---" +str);
  15.         //释放资源
  16.         s.close();
  17.         //ss.close();  
  18.     }
  19. }

上面的代码就可以实现：客户端向服务器发送数据，服务端能够接收客户端发送过来的数据。

1.2IO多路复用

之前我已经写过Java NIO的文章了，Java的NIO也是基于IO多路复用模型的，建议先去看一下再回来，文章写得挺详细和通俗的了：JDK10都发布了，nio你了解多少？
这里就简单回顾一下吧：

  • I/O多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符其中的任意一个进入读就绪状态、等等，select()函数就可以返回。
  • select/epoll的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。

说白了，使用IO多路复用机制的，一般自己会有一套事件机制，使用一个线程或者进程监听这些事件，如果这些事件被触发了，则调用对应的函数来处理。

二、Redis事件

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

  • 文件事件：文件事件其实就是对Socket操作的抽象，Redis服务器与Redis客户端的通信会产生文件事件，服务器通过监听并处理这些事件来完成一系列的网络操作
  • 时间事件：时间事件其实就是对定时操作的抽象，前面我们已经讲了RDB、AOF、定时删除键这些操作都可以由服务端去定时或者周期去完成，底层就是通过触发时间事件来实现的！

    2.1文件事件

    Redis开发了自己的网络事件处理器，这个处理器被称为文件事件处理器。
    文件事件处理器由四部分组成：
    Redis 基础知识 - 图52
    文件事件处理器组成

    文件事件处理器使用I/O多路复用程序来同时监听多个Socket。当被监听的Socket准备好执行连接应答(accept)、读取(read)等等操作时，与操作相对应的文件事件就会产生，根据文件事件来为Socket关联对应的事件处理器，从而实现功能。

要值得注意的是：Redis中的I/O多路复用程序会将所有产生事件的Socket放到一个队列里边，然后通过这个队列以有序、同步、每次一个Socket的方式向文件事件分派器传送套接字。也就是说：当上一个Socket处理完毕后，I/O多路复用程序才会向文件事件分派器传送下一个Socket。
首先，IO多路复用程序首先会监听着Socket的AE_READABLE事件，该事件对应着连接应答处理器

  • 可以理解简单成SocketServet.accpet()

Redis 基础知识 - 图53
监听着Socket的AE_READABLE事件
此时，一个名字叫做3y的Socket要连接服务器啦。服务器会用连接应答处理器处理。创建出客户端的Socket，并将客户端的Socket与命令请求处理器进行关联，使得客户端可以向服务器发送命令请求。

  • 相当于Socket s = ss.accept();，创建出客户端的Socket，然后将该Socket关联命令请求处理器
  • 此时客户端就可以向主服务器发送命令请求了

Redis 基础知识 - 图54
客户端请求连接，服务器创建出客户端Scoket，关联命令请求处理器
假设现在客户端发送一个命令请求set Java3y "关注、点赞、评论"，客户端Socket将产生AE_READABLE事件，引发命令请求处理器执行。处理器读取客户端的命令内容，然后传给对应的程序去执行。
客户端发送完命令请求后，服务端总得给客户端回应的。此时服务端会将客户端的Scoket的AE_WRITABLE事件与命令回复处理器关联。
Redis 基础知识 - 图55
客户端的Scoket的AE_WRITABLE事件与命令回复处理器关联
最后客户端尝试读取命令回复时，客户端Socket产生AE_WRITABLE事件，触发命令回复处理器执行。当把所有的回复数据写入到Socket之后，服务器就会解除客户端Socket的AE_WRITABLE事件与命令回复处理器的关联。
最后以《Redis设计与实现》的一张图来概括：
Redis 基础知识 - 图56
Redis事件交互过程

2.2时间事件

持续运行的Redis服务器会定期对自身的资源和状态进行检查和调整，这些定期的操作由serverCron函数负责执行，它的主要工作包括：

  • 更新服务器的统计信息(时间、内存占用、数据库占用)
  • 清理数据库的过期键值对
  • AOF、RDB持久化
  • 如果是主从服务器，对从服务器进行定期同步
  • 如果是集群模式，对进群进行定期同步和连接
  • …

Redis服务器将时间事件放在一个链表中，当时间事件执行器运行时，会遍历整个链表。时间事件包括：

  • 周期性事件(Redis一般只执行serverCron时间事件，serverCron时间事件是周期性的)

  • 定时事件

    2.3时间事件和文件事件

  • 文件事件和时间事件之间是合作关系，服务器会轮流处理这两种事件，并且处理事件的过程中不会发生抢占。

  • 时间事件的实际处理事件通常会比设定的到达时间晚一些

    三、Redis单线程为什么快？

  • 1）纯内存操作

  • 2）核心是基于非阻塞的IO多路复用机制

  • 3）单线程避免了多线程的频繁上下文切换问题

    四、客户端与服务器

    在《Redis设计与实现》中各用了一章节来写客户端与服务器，我看完觉得比较底层的东西，也很难记得住，所以我决定总结一下比较重要的知识。如果以后真的遇到了，再来补坑~
    服务器使用clints链表连接多个客户端状态，新添加的客户端状态会被放到链表的末尾
    Redis 基础知识 - 图57
    客户端—链表

  • 一个服务器可以与多个客户端建立网络连接，每个客户端可以向服务器发送命令请求，而服务器则接收并处理客户端发送的命令请求，并向客户端返回命令回复。

  • Redis服务器使用单线程单进程的方式处理命令请求。在数据库中保存客户端执行命令所产生的数据，并通过资源管理来维持服务器自身的运转。

    4.1客户端

    客户端章节中主要讲解了Redis客户端的属性(客户端状态、输入/输出缓冲区、命令参数、命令函数等等)

    1. typedef struct redisClient{
    2.   //客户端状态的输入缓冲区用于保存客户端发送的命令请求,最大1GB,否则服务器将关闭这个客户端
    3.   sds querybuf;  
    4.   //负责记录argv数组的长度。
    5.   int argc;   
    6.   // 命令的参数
    7.   robj **argv;  
    8.   // 客户端要执行命令的实现函数
    9.   struct redisCommand *cmd, *lastcmd;  
    10.   //记录了客户端的角色(role),以及客户端所处的状态。 (REDIS_SLAVE | REDIS_MONITOR | REDIS_MULTI) 
    11.   int flags;             
    12.   //记录客户端是否通过了身份验证
    13.   int authenticated;     
    14.   //时间相关的属性
    15.   time_t ctime;           /* Client creation time */       
    16.   time_t lastinteraction; /* time of the last interaction, used for timeout */
    17.   time_t obuf_soft_limit_reached_time;
    18.   //固定大小的缓冲区用于保存那些长度比较小的回复
    19.   /* Response buffer */
    20.   int bufpos;
    21.   char buf[REDIS_REPLY_CHUNK_BYTES];
    22.   //可变大小的缓冲区用于保存那些长度比较大的回复
    23.   list *reply; //可变大小缓冲区由reply 链表和一个或多个字符串对象组成
    24.   //...
    25. }

    4.2服务端

    服务器章节中主要讲解了Redis服务器读取客户端发送过来的命令是如何解析，以及初始化的过程。
    服务器从启动到能够处理客户端的命令请求需要执行以下的步骤：

  • 初始化服务器状态

  • 载入服务器配置
  • 初始化服务器的数据结构
  • 还原数据库状态
  • 执行事件循环

总的来说是这样子的：

  1. def main():
  2.     init_server();
  3.     while server_is_not_shutdown();
  4.         aeProcessEvents()
  5.     clean_server();

从客户端发送命令道完成主要包括的步骤：

  • 客户端将命令请求发送给服务器
  • 服务器读取命令请求，分析出命令参数
  • 命令执行器根据参数查找命令的实现函数，执行实现函数并得出命令回复
  • 服务器将命令回复返回给客户端

一、主从架构

1.1为什么要主从架构

Redis也跟关系型数据(MySQL)一样，如果有过多请求还是撑不住的。
Redis 基础知识 - 图58
一台Redis撑不住
因为Redis如果只有一台服务器的话，那随着请求越来越多：

  • Redis的内存是有限的，可能放不下那么多的数据
  • 单台Redis支持的并发量也是有限的。
  • 万一这台Redis挂了，所有的请求全走关系数据库了，那就更炸了。

显然，出现的上述问题是因为一台Redis服务器不够，所以多搞几台Redis服务器就可以了
Redis 基础知识 - 图59
多搞几台Redis服务器
为了实现我们服务的高可用性，可以将这几台Redis服务器做成是主从来进行管理
Redis 基础知识 - 图60
主从架构

tip:Redis作者已将Master/Slave架构改名为Master/Replica

1.2主从架构的特点

下面我们来看看Redis的主从架构特点：

  • 主服务器负责接收写请求
  • 从服务器负责接收读请求
  • 从服务器的数据由主服务器复制过去。主从服务器的数据是一致的

Redis 基础知识 - 图61
主从架构特点
主从架构的好处：

  • 读写分离(主服务器负责写，从服务器负责读)
  • 高可用(某一台从服务器挂了，其他从服务器还能继续接收请求，不影响服务)
  • 处理更多的并发量(每台从服务器都可以接收读请求，读QPS就上去了)

主从架构除了上面的形式，也有下面这种的(只不过用得比较少)：
Redis 基础知识 - 图62
从服务器又挂着从服务器

二、复制功能

主从架构的特点之一：主服务器和从服务器的数据是一致的。
因为主服务器是能接收写请求的，主服务器处理完写请求，会做什么来保证主从数据的一致性呢？如果主从服务器断开了，过一阵子才重连，又会怎么处理呢？下面将会了解到这些细节~

在Redis中，用户可以通过执行SALVEOF命令或者设置salveof选项，让一个服务器去复制(replicate)另一个服务器，我们称呼被复制的服务器为主服务器(master)，而对主服务器进行复制的服务器则被称为从服务器(salve)

Redis 基础知识 - 图63
复制

2.1复制功能的具体实现

复制功能分为两个操作：

  • 同步(sync)
    • 将从服务器的数据库状态更新至主服务器的数据库状态
  • 命令传播(command propagate)
    • 主服务器的数据库状态被修改，导致主从服务器的数据库状态不一致，让主从服务器的数据库状态重新回到一致状态。

Redis 基础知识 - 图64
主从数据一致性
从服务器对主服务器的同步又可以分为两种情况：

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

在Redis2.8以前，断线后复制这部分其实缺少的只是部分的数据，但是要让主从服务器重新执行SYNC命令，这样的做法是非常低效的。(因为执行SYNC命令是把所有的数据再次同步，而不是只同步丢失的数据)
接下来我们来详细看看Redis2.8以后复制功能是怎么实现的：

2.1.1复制的前置工作

首先我们来看一下前置的工作：

  • 从服务器设置主服务器的IP和端口
  • 建立与主服务器的Socket连接
  • 发送PING命令(检测Socket读写是否正常与主服务器的通信状况)
  • 身份验证(看有没有设置对应的验证配置)
  • 从服务器给主服务器发送端口的信息，主服务器记录监听的端口

Redis 基础知识 - 图65
Redis复制的前置工作
前面也提到了，Redis2.8之前，断线后同步会重新执行SYNC命令，这是非常低效的。下面我们来看一下Redis2.8之后是怎么进行同步的。

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

PSYNC命令具有完整重同步和部分重同步两种模式(其实就跟上面所说的初次复制和断线后复制差不多个意思)。

2.1.2完整重同步

下面先来看看完整重同步是怎么实现的：

  • 从服务器向主服务器发送PSYNC命令
  • 收到PSYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件。并用一个缓冲区来记录从现在开始执行的所有写命令。
  • 当主服务器的BGSAVE命令执行完后，将生成的RDB文件发送给从服务器，从服务器接收和载入RBD文件。将自己的数据库状态更新至与主服务器执行BGSAVE命令时的状态。
  • 主服务器将所有缓冲区的写命令发送给从服务器，从服务器执行这些写命令，达到数据最终一致性。

Redis 基础知识 - 图66
完整重同步

2.1.2部分重同步

接下来我们来看看部分重同步，部分重同步可以让我们断线后重连只需要同步缺失的数据(而不是Redis2.8之前的同步全部数据)，这是符合逻辑的！
部分重同步功能由以下部分组成：

  • 主从服务器的复制偏移量
  • 主服务器的复制积压缓冲区
  • 服务器运行的ID(run ID)

首先我们来解释一下上面的名词：
复制偏移量：执行复制的双方都会分别维护一个复制偏移量

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

通过对比主从复制的偏移量，就很容易知道主从服务器的数据是否处于一致性的状态！
Redis 基础知识 - 图67
复制偏移量
那断线重连以后，从服务器向主服务器发送PSYNC命令，报告现在的偏移量是36，那么主服务器该对从服务器执行完整重同步还是部分重同步呢？？这就交由复制积压缓冲区来决定。
当主服务器进行命令传播时，不仅仅会将写命令发送给所有的从服务器，还会将写命令入队到复制积压缓冲区里面(这个大小可以调的)。如果复制积压缓冲区存在丢失的偏移量的数据，那就执行部分重同步，否则执行完整重同步。
服务器运行的ID(run ID)实际上就是用来比对ID是否相同。如果不相同，则说明从服务器断线之前复制的主服务器和当前连接的主服务器是两台服务器，这就会进行完整重同步。
所以流程大概如此：
Redis 基础知识 - 图68
同步的流程

2.1.3命令传播

当完成了同步之后，主从服务器就会进入命令传播阶段。这时主服务器只要将自己的写命令发送给从服务器，而从服务器接收并执行主服务器发送过来的写命令，就可以保证主从服务器一直保持数据一致了！

在命令传播阶段，从服务器默认会以每秒一次的频率，向服务器发送命令REPLCONF ACK <replication_offset> 其中replication_offset是从服务器当前的复制偏移量
发送这个命令主要有三个作用：

  • 检测主从服务器的网络状态
  • 辅助实现min-slaves选项
  • 检测命令丢失

在上篇中抛出了一个问题：

抛个问题：如果从服务器挂了，没关系，我们一般会有多个从服务器，其他的请求可以交由没有挂的从服务器继续处理。如果主服务器挂了，怎么办？因为我们的写请求由主服务器处理，只有一台主服务器，那就无法处理写请求了？

Redis提供了哨兵(Sentinel)机制供我们解决上面的情况。如果主服务器挂了，我们可以将从服务器升级为主服务器，等到旧的主服务器(挂掉的那个)重连上来，会将它(挂掉的主服务器)变成从服务器。

  • 这个过程叫做主备切换(故障转移)

在正常的情况下，主从加哨兵(Sentinel)机制是这样子的：
Redis 基础知识 - 图69
正常情况下
主服务器挂了，主从复制操作就中止了，并且哨兵系统是可以察觉出主服务挂了。：
Redis 基础知识 - 图70
Sentinel可以察觉主服务掉线，复制操作中止。
Redis提供哨兵机制可以将选举一台从服务器变成主服务器
Redis 基础知识 - 图71
选举一台从服务器变成主服务器
然后旧的主服务器如果重连了，会变成从服务器：
Redis 基础知识 - 图72
旧的主服务器如果重连了，会变成从服务器
这篇文章主要讲讲Redis的哨兵(Sentinel)机制的一些细节。希望看完对大家有所帮助~

一、哨兵(Sentinel)机制

High Availability: Redis Sentinel is the official high availability solution for Redis.

哨兵(Sentinel)机制主要用于实现Redis的高可用性，主要的功能如下：

  • Monitoring. Sentinel constantly checks if your master and slave instances are working as expected.
    • Sentinel不停地监控Redis主从服务器是否正常工作
  • Notification. Sentinel can notify the system administrator, another computer programs, via an API, that something is wrong with one of the monitored Redis instances.
    • 如果某个Redis实例有故障，那么哨兵负责发送消息通知管理员
  • Automatic failover. If a master is not working as expected, Sentinel can start a failover process where a slave is promoted to master, the other additional slaves are reconfigured to use the new master, and the applications using the Redis server informed about the new address to use when connecting.
    • 如果主服务器挂掉了，会自动将从服务器提升为主服务器(包括配置都会修改)。
  • Configuration provider. Sentinel acts as a source of authority for clients service discovery: clients connect to Sentinels in order to ask for the address of the current Redis master responsible for a given service. If a failover occurs, Sentinels will report the new address.
    • Sentinel可以作为配置中心，能够提供当前主服务器的信息。

下面来具体讲讲Sentinel是如何将从服务器提升为主服务器的。

tips:Sentinel可以让我们的Redis实现高可用，Sentinel作为这么一个组件，自身也必然是高可用的(不可能是单点的)

1.1启动和初始化Sentinel

首先我们要知道的是：Sentinel本质上只是一个运行在特殊模式下的Redis服务器。因为Sentinel做的事情和Redis服务器是不一样的，所以它们的初始化是有所区别的(比如，Sentinel在初始化的时候并不会载入AOF/RDB文件，因为Sentinel根本就不用数据库)。
然后，在启动的时候会将普通Redis服务器的代码替换成Sentinel专用代码。(所以Sentinel虽然作为Redis服务器，但是它不能执行SET、DBSIZE等等命令，因为命令表的代码被替换了)
接着，初始化Sentinel的状态，并根据给定的配置文件初始化Sentinel监视的主服务器列表。
Redis 基础知识 - 图73
初始化
最后，Sentinel会创建两个连向主服务器的网络连接：

  • 命令连接(发送和接收命令)
  • 订阅连接(订阅主服务器的_sentinel_:hello频道)

Redis 基础知识 - 图74
创建网络连接

1.2获取和更新信息

Sentinel通过主服务器发送INFO命令来获得主服务器属下所有从服务器的地址信息，并为这些从服务器创建相应的实例结构。
Redis 基础知识 - 图75
更新实例结构
当发现有新的从服务器出现时，除了创建对应的从服务器实例结构，Sentinel还会创建命令连接和订阅连接。
Redis 基础知识 - 图76
创建连接
在Sentinel运行的过程中，通过命令连接会以每两秒一次的频率向监视的主从服务器的_sentinel_:hello频道发送命令(主要发送Sentinel本身的信息，监听主从服务器的信息)，并通过订阅连接接收_sentinel_:hello频道的信息。

  • 这样一来一回，我们就可以更新每个Sentinel实例结构的信息。

    1.3判断主服务器是否下线了

    判断主服务器是否下线有两种情况：

  • 主观下线

    • Sentinel会以每秒一次的频率向与它创建命令连接的实例(包括主从服务器和其他的Sentinel)发送PING命令，通过PING命令返回的信息判断实例是否在线
    • 如果一个主服务器在down-after-milliseconds毫秒内连续向Sentinel发送无效回复，那么当前Sentinel就会主观认为该主服务器已经下线了。
  • 客观下线
    • 当Sentinel将一个主服务器判断为主观下线以后，为了确认该主服务器是否真的下线，它会向同样监视该主服务器的Sentinel询问，看它们是否也认为该主服务器是否下线。
    • 如果足够多的Sentinel认为该主服务器是下线的，那么就判定该主服务为客观下线，并对主服务器执行故障转移操作。

      在多少毫秒内无效回复才认定主服务器是主观下线的，以及多少个Sentinel认为主服务器是下线的，才认定为客观下线。这都是可以配置的

1.4选举领头Sentinel和故障转移

当一个主服务器认为为客观下线以后，监视这个下线的主服务器的各种Sentinel会进行协商，选举出一个领头的Sentinel，领头的Sentinel会对下线的主服务器执行故障转移操作。

选举领头Sentinel的规则也比较多，总的来说就是先到先得(哪个快，就选哪个)

选举出领头的Sentinel之后，领头的Sentinel会对已下线的主服务器执行故障转移操作，包括三个步骤：

  • 在已下线主服务器属下的从服务器中，挑选一个转换为主服务器
  • 让已下线主服务器属下的所有从服务器改为复制新的主服务器
  • 已下线的主服务器重新连接时，让他成为新的主服务器的从服务器
  • (这三步实际上就是文章开头的图片)

挑选某一个从服务器作为主服务器也是有策略的，大概如下：

  • （1）跟master断开连接的时长
  • （2）slave优先级
  • （3）复制offset
  • （4）run id

    最后

    这篇文章主要讲解了Sentinel的作用和工作的基本过程(我觉得已经基本OK了)，其中也涉及到了很多的细节，这里我就没有一一整理出来了。想要深入学习的同学最好自己看看书或者文档~~

    tips:目前为止的主从+哨兵架构可以说Redis是高可用的，但要清楚的是：Redis还是会丢失数据的

丢失数据有两种情况：

  • 异步复制导致的数据丢失
    • 有部分数据还没复制到从服务器，主服务器就宕机了，此时这些部分数据就丢失了
  • 脑裂导致的数据丢失
    • 有时候主服务器脱离了正常网络，跟其他从服务器不能连接。此时哨兵可能就会认为主服务器下线了(然后开启选举，将某个从服务器切换成了主服务器)，但是实际上主服务器还运行着。这个时候，集群里就会有两个服务器(也就是所谓的脑裂)。
    • 虽然某个从服务器被切换成了主服务器，但是可能客户端还没来得及切换到新的主服务器，客户端还继续写向旧主服务器写数据。旧的服务器重新连接时，会作为从服务器复制新的主服务器(这意味着旧数据丢失)。

可以通过以下两个配置尽量减少数据丢失的可能：

  1. min-slaves-to-write 1
  2. min-slaves-max-lag 10

一、缓存雪崩

1.1什么是缓存雪崩？

回顾一下我们为什么要用缓存(Redis)：
image.png
现在有个问题，如果我们的缓存挂掉了，这意味着我们的全部请求都跑去数据库了。
image.png
在前面学习我们都知道Redis不可能把所有的数据都缓存起来(内存昂贵且有限)，所以Redis需要对数据设置过期时间，并采用的是惰性删除+定期删除两种策略对过期键删除。Redis对过期键的策略+持久化
如果缓存数据设置的过期时间是相同的，并且Redis恰好将这部分数据全部删光了。这就会导致在这段时间内，这些缓存同时失效，全部请求到数据库中。
这就是缓存雪崩：

  • Redis挂掉了，请求全部走数据库。
  • 对缓存数据设置相同的过期时间，导致某段时间内缓存失效，请求全部走数据库。

缓存雪崩如果发生了，很可能就把我们的数据库搞垮，导致整个服务瘫痪！

1.2如何解决缓存雪崩？

对于“对缓存数据设置相同的过期时间，导致某段时间内缓存失效，请求全部走数据库。”这种情况，非常好解决：

  • 解决方法：在缓存的时候给过期时间加上一个随机值，这样就会大幅度的减少缓存在同一时间过期。

对于“Redis挂掉了，请求全部走数据库”这种情况，我们可以有以下的思路：

  • 事发前：实现Redis的高可用(主从架构+Sentinel 或者Redis Cluster)，尽量避免Redis挂掉这种情况发生。
  • 事发中：万一Redis真的挂了，我们可以设置本地缓存(ehcache)+限流(hystrix)，尽量避免我们的数据库被干掉(起码能保证我们的服务还是能正常工作的)
  • 事发后：redis持久化，重启后自动从磁盘上加载数据，快速恢复缓存数据。

    二、缓存穿透

    2.1什么是缓存穿透

    比如，我们有一张数据库表，ID都是从1开始的(正数)：
    image.png
    但是可能有黑客想把我的数据库搞垮，每次请求的ID都是负数。这会导致我的缓存就没用了，请求全部都找数据库去了，但数据库也没有这个值啊，所以每次都返回空出去。

    缓存穿透是指查询一个一定不存在的数据。由于缓存不命中，并且出于容错考虑，如果从数据库查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库去查询，失去了缓存的意义。

image.png
这就是缓存穿透：

  • 请求的数据在缓存大量不命中，导致请求走数据库。

缓存穿透如果发生了，也可能把我们的数据库搞垮，导致整个服务瘫痪！

2.1如何解决缓存穿透？

解决缓存穿透也有两种方案：

  • 由于请求的参数是不合法的(每次都请求不存在的参数)，于是我们可以使用布隆过滤器(BloomFilter)或者压缩filter提前拦截，不合法就不让这个请求到数据库层！
  • 当我们从数据库找不到的时候，我们也将这个空对象设置到缓存里边去。下次再请求的时候，就可以从缓存里边获取了。
    • 这种情况我们一般会将空对象设置一个较短的过期时间。

参考资料：

  • 缓存系列文章—5.缓存穿透问题

    • https://carlosfu.iteye.com/blog/2248185

      三、缓存与数据库双写一致

      3.1对于读操作，流程是这样的

      上面讲缓存穿透的时候也提到了：如果从数据库查不到数据则不写入缓存。
      一般我们对读操作的时候有这么一个固定的套路：

  • 如果我们的数据在缓存里边有，那么就直接取缓存的。

  • 如果缓存里没有我们想要的数据，我们会先去查询数据库，然后将数据库查出来的数据写到缓存中。

  • 最后将数据返回给请求

    3.2什么是缓存与数据库双写一致问题？

    如果仅仅查询的话，缓存的数据和数据库的数据是没问题的。但是，当我们要更新时候呢？各种情况很可能就造成数据库和缓存的数据不一致了。

  • 这里不一致指的是：数据库的数据跟缓存的数据不一致

image.png
从理论上说，只要我们设置了键的过期时间，我们就能保证缓存和数据库的数据最终是一致的。因为只要缓存数据过期了，就会被删除。随后读的时候，因为缓存里没有，就可以查数据库的数据，然后将数据库查出来的数据写入到缓存中。
除了设置过期时间，我们还需要做更多的措施来尽量避免数据库与缓存处于不一致的情况发生。

3.3对于更新操作

一般来说，执行更新操作时，我们会有两种选择：

  • 先操作数据库，再操作缓存
  • 先操作缓存，再操作数据库

首先，要明确的是，无论我们选择哪个，我们都希望这两个操作要么同时成功，要么同时失败。所以，这会演变成一个分布式事务的问题。
所以，如果原子性被破坏了，可能会有以下的情况：

  • 操作数据库成功了，操作缓存失败了。
  • 操作缓存成功了，操作数据库失败了。

    如果第一步已经失败了，我们直接返回Exception出去就好了，第二步根本不会执行。

下面我们具体来分析一下吧。

3.3.1操作缓存

操作缓存也有两种方案：

  • 更新缓存
  • 删除缓存

一般我们都是采取删除缓存缓存策略的，原因如下：

  1. 高并发环境下，无论是先操作数据库还是后操作数据库而言，如果加上更新缓存，那就更加容易导致数据库与缓存数据不一致问题。(删除缓存直接和简单很多)
  2. 如果每次更新了数据库，都要更新缓存【这里指的是频繁更新的场景，这会耗费一定的性能】，倒不如直接删除掉。等再次读取时，缓存里没有，那我到数据库找，在数据库找到再写到缓存里边(体现懒加载)

基于这两点，对于缓存在更新时而言，都是建议执行删除操作！

3.3.2先更新数据库，再删除缓存

正常的情况是这样的：

  • 先操作数据库，成功；
  • 再删除缓存，也成功；

如果原子性被破坏了：

  • 第一步成功(操作数据库)，第二步失败(删除缓存)，会导致数据库里是新数据，而缓存里是旧数据。
  • 如果第一步(操作数据库)就失败了，我们可以直接返回错误(Exception)，不会出现数据不一致。

如果在高并发的场景下，出现数据库与缓存数据不一致的概率特别低，也不是没有：

  • 缓存刚好失效
  • 线程A查询数据库，得一个旧值
  • 线程B将新值写入数据库
  • 线程B删除缓存
  • 线程A将查到的旧值写入缓存

要达成上述情况，还是说一句概率特别低：

因为这个条件需要发生在读缓存时缓存失效，而且并发着有一个写操作。而实际上数据库的写操作会比读操作慢得多，而且还要锁表，而读操作必需在写操作前进入数据库操作，而又要晚于写操作更新缓存，所有的这些条件都具备的概率基本并不大。

对于这种策略，其实是一种设计模式：Cache Aside Pattern
image.png
删除缓存失败的解决思路：

  • 将需要删除的key发送到消息队列中
  • 自己消费消息，获得需要删除的key

  • 不断重试删除操作，直到成功

    3.3.3先删除缓存，再更新数据库

    正常情况是这样的：

  • 先删除缓存，成功；

  • 再更新数据库，也成功；

如果原子性被破坏了：

  • 第一步成功(删除缓存)，第二步失败(更新数据库)，数据库和缓存的数据还是一致的。
  • 如果第一步(删除缓存)就失败了，我们可以直接返回错误(Exception)，数据库和缓存的数据还是一致的。

看起来是很美好，但是我们在并发场景下分析一下，就知道还是有问题的了：

  • 线程A删除了缓存
  • 线程B查询，发现缓存已不存在
  • 线程B去数据库查询得到旧值
  • 线程B将旧值写入缓存
  • 线程A将新值写入数据库

所以也会导致数据库和缓存不一致的问题。
并发下解决数据库与缓存不一致的思路：

  • 将删除缓存、修改数据库、读取缓存等的操作积压到队列里边，实现串行化。

image.png

3.4对比两种策略

我们可以发现，两种策略各自有优缺点：

Redis内存回收:LRU算法

Redis中采用两种算法进行内存回收，引用计数算法以及LRU算法，在操作系统内存管理一节中，我们都学习过LRU算法(最近最久未使用算法),那么什么是LRU算法呢
LRU算法作为内存管理的一种有效算法,其含义是在内存有限的情况下，当内存容量不足时，为了保证程序的运行，这时就不得不淘汰内存中的一些对象，释放这些对象占用的空间，那么选择淘汰哪些对象呢？LRU算法就提供了一种策略，告诉我们选择最近一段时间内，最久未使用的对象将其淘汰，至于为什么要选择最久未使用的，可以想想，最近一段时间内使用的东西，我们是不是可能一会又要用到呢~，而很长一段时间内都没有使用过的东西，也许永远都不会再使用~
在操作系统中LRU算法淘汰的不是内存中的对象，而是页,当内存中数据不足时，通过LRU算法，选择一页(一般是4KB)将其交换到虚拟内存区(Swap区)
LRU算法演示
Redis 基础知识 - 图84

这张图应该画的还行吧，用的是www.draw.io,解释如下，假设前提，只有三块内存空间可以使用，每一块内存空间只能存放一个对象，如A、B、C…
1、最开始时，内存空间是空的，因此依次进入A、B、C是没有问题的
2、当加入D时，就出现了问题，内存空间不够了，因此根据LRU算法，内存空间中A待的时间最为久远，选择A,将其淘汰
3、当再次引用B时，内存空间中的B又处于活跃状态，而C则变成了内存空间中，近段时间最久未使用的
4、当再次向内存空间加入E时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是E->B->D
LRU算法的整体思路就是这样的
算法实现应该采用怎样的数据结构
队列？那不就是FIFO算法嘛~，LRU算法最为精典的实现，就是HashMap+Double LinkedList，时间复杂度为O(1),具体可以参考相关代码
REDIS中LRU算法的实际应用,在Redis 1.0中并未引入LRU算法，只是简单的使用引用计数法，去掉内存中不再引用的对象以及运行一个定时任务serverCron去掉内存中已经过期的对象占用的内存空间,以下是Redis 1.0中CT任务的释放内存中的部份代码

  1. //去掉一些过期的KEYS
  2. for (j = 0; j < server.dbnum; j++) {
  3.     redisDb *db = server.db+j;
  4.     int num = dictSize(db->expires);//计算hash表中过期Key的数目
  5.     if (num) {
  6.         time_t now = time(NULL);
  7.         //#define REDIS_EXPIRELOOKUPS_PER_CRON 100
  8.         if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
  9.             num = REDIS_EXPIRELOOKUPS_PER_CRON;
  10.         //循环100次，从过期Hash表中随机挑选出100个Key,判断Key是否过期，如果过期了，执行删除操作
  11.         while (num--) {
  12.             dictEntry *de;
  13.             time_t t;
  14.             //随机获取Key值(db->expires里面存储的均是即将过期的Keys)
  15.             if ((de = dictGetRandomKey(db->expires)) == NULL) break;
  16.             t = (time_t) dictGetEntryVal(de);
  17.             if (now > t) {
  18.                 //不仅要从存放过期keys的Hash表中删除数据，还要从存放实际数据的Hash表中删除数据
  19.                 deleteKey(db,dictGetEntryKey(de));
  20.             }
  21.         }
  22.     }
  23. }

如果没有看过Redis 1.0源码，理解起来可能有些困难，但看看1.0源码中的这个结构体，估计有点数据结构基础的人，都明白上面这几行代码的意思了(注释部份我也已经写的很清楚了)~

  1. typedef struct redisDb {
  2.     dict *dict;//用来存放实际Key->Value数据的位置
  3.     dict *expires;//用于记录Key的过期时间
  4.     int id;//表示选择的是第几个redis库
  5. } redisDb;

没有查证是从什么版本开始，Redis增加了LRU算法，以下是分析Redis 2.9.11代码中的LRU算法淘汰策略，在2.9.11版本中与LRU算法相关的代码主要位于object.c以及redis.c两个源文件中,　再分析这两个文件关于LRU源代码之前，让我们先看一下，Redis 2.9.11版本中关于LRU算法的配置,配置文件在redis.conf文件中,如下所示

  1. # maxmemory <bytes>
  3. # MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
  4. # is reached. You can select among five behaviors:
  5. #
  6. # volatile-lru -> remove the key with an expire set using an LRU algorithm
  7. # allkeys-lru -> remove any key accordingly to the LRU algorithm
  8. # volatile-random -> remove a random key with an expire set
  9. # allkeys-random -> remove a random key, any key
  10. # volatile-ttl -> remove the key with the nearest expire time (minor TTL)
  11. # noeviction -> don't expire at all, just return an error on write operations
  12. #
  13. # Note: with any of the above policies, Redis will return an error on write
  14. #       operations, when there are not suitable keys for eviction.
  15. #
  16. #       At the date of writing this commands are: set setnx setex append
  17. #       incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
  18. #       sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
  19. #       zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
  20. #       getset mset msetnx exec sort
  21. #
  22. # The default is:
  23. #
  24. # maxmemory-policy noeviction
  26. # LRU and minimal TTL algorithms are not precise algorithms but approximated
  27. # algorithms (in order to save memory), so you can tune it for speed or
  28. # accuracy. For default Redis will check five keys and pick the one that was
  29. # used less recently, you can change the sample size using the following
  30. # configuration directive.
  31. #
  32. # The default of 5 produces good enough results. 10 Approximates very closely
  33. # true LRU but costs a bit more CPU. 3 is very fast but not very accurate.
  34. #
  35. # maxmemory-samples 5

从上面的配置中，可以看出,高版本的Redis中当内存达到极限时，内存淘汰策略主要采用了6种方式进行内存对象的释放操作
1.volatile-lru:从设置了过期时间的数据集中，选择最近最久未使用的数据释放
2.allkeys-lru:从数据集中(包括设置过期时间以及未设置过期时间的数据集中)，选择最近最久未使用的数据释放
3.volatile-random:从设置了过期时间的数据集中，随机选择一个数据进行释放
4.allkeys-random:从数据集中(包括了设置过期时间以及未设置过期时间)随机选择一个数据进行入释放
5.volatile-ttl：从设置了过期时间的数据集中，选择马上就要过期的数据进行释放操作
6.noeviction：不删除任意数据(但redis还会根据引用计数器进行释放呦~),这时如果内存不够时，会直接返回错误
默认的内存策略是noeviction，在Redis中LRU算法是一个近似算法，默认情况下，Redis随机挑选5个键，并且从中选取一个最近最久未使用的key进行淘汰，在配置文件中可以通过maxmemory-samples的值来设置redis需要检查key的个数,但是栓查的越多，耗费的时间也就越久,但是结构越精确(也就是Redis从内存中淘汰的对象未使用的时间也就越久~),设置多少，综合权衡吧~~~
在redis.h中声明的redisObj定义的如下:

  1. #define REDIS_LRU_BITS 24
  2. #define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
  3. #define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
  4. typedef struct redisObject {<br>　　//存放的对象类型
  5.     unsigned type:4;
  6.     //内容编码
  7.     unsigned encoding:4;
  8.     //与server.lruclock的时间差值
  9.     unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */\
  10.     //引用计数算法使用的引用计数器
  11.     int refcount;
  12.     //数据指针
  13.     void *ptr;
  14. } robj;

从redisObject结构体的定义中可以看出，在Redis中存放的对象不仅会有一个引用计数器，还会存在一个server.lruclock,这个变量会在定时器中每次刷新时，调用getLRUClock获取当前系统的毫秒数，作为LRU时钟数,该计数器总共占用24位,最大可以表示的值为24个1即((1<server.lruclock在redis.c中运行的定时器中进行更新操作,代码如下(redis.c中的定时器被配置中100ms执行一次)

  1. int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
  2.     .....
  3.     run_with_period(100) trackOperationsPerSecond();
  5.     /* We have just REDIS_LRU_BITS bits per object for LRU information.
  6.      * So we use an (eventually wrapping) LRU clock.
  7.      *
  8.      * Note that even if the counter wraps it's not a big problem,
  9.      * everything will still work but some object will appear younger
  10.      * to Redis. However for this to happen a given object should never be
  11.      * touched for all the time needed to the counter to wrap, which is
  12.      * not likely.
  13.      *
  14.      * Note that you can change the resolution altering the
  15.      * REDIS_LRU_CLOCK_RESOLUTION define. */
  16.     server.lruclock = getLRUClock();
  17.     ....
  18.     return 1000/server.hz;
  19. }

看到这，再看看Redis中创建对象时，如何对redisObj中的unsigned lru进行赋值操作的，代码位于object.c中,如下所示

  1. robj *createObject(int type, void *ptr) {
  2.     robj *o = zmalloc(sizeof(*o));
  3.     o->type = type;
  4.     o->encoding = REDIS_ENCODING_RAW;
  5.     o->ptr = ptr;
  6.     o->refcount = 1;
  7.     //很关键的一步，Redis中创建的每一个对象，都记录下该对象的LRU时钟
  8.     /* Set the LRU to the current lruclock (minutes resolution). */
  9.     o->lru = LRU_CLOCK();
  10.     return o;
  11. }

该代码中最为关键的一句就是o->lru=LRU_CLOCK(),这是一个定义，看一下这个宏定义的实现,代码如下所示

  1. #define LRU_CLOCK() ((1000/server.hz <= REDIS_LRU_CLOCK_RESOLUTION) ? server.lruclock : getLRUClock())


其中REDIS_LRU_CLOCK_RESOLUTION为1000,可以自已在配置文件中进行配置，表示的是LRU算法的精度,在这里我们就可以看到server.lruclock的用处了，如果定时器执行的频率高于LRU算法的精度时，可以直接将server.lruclock直接在对象创建时赋值过去，避免了函数调用的内存开销以及时间开销~
有了上述的基础，下面就是最为关键的部份了，REDIS中LRU算法，这里以volatile-lru为例(选择有过期时间的数据集进行淘汰)，在Redis中命令的处理时，会调用processCommand函数，在ProcessCommand函数中，当在配置文件中配置了maxmemory时，会调用freeMemoryIfNeeded函数，释放不用的内存空间
以下是freeMemoryIfNeeded函数的关于LRU相关部份的源代码，其他代码类似

  1. //不同的策略，操作的数据集不同
  2. if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
  3.     server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
  4. {
  5.     dict = server.db[j].dict;
  6. } else {//操作的是设置了过期时间的key集
  7.     dict = server.db[j].expires;
  8. }
  9. if (dictSize(dict) == 0) continue;
  11. /* volatile-random and allkeys-random policy */
  12. //随机选择进行淘汰
  13. if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
  14.     server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
  15. {
  16.     de = dictGetRandomKey(dict);
  17.     bestkey = dictGetKey(de);
  18. }
  20. /* volatile-lru and allkeys-lru policy */
  21. //具体的LRU算法
  22. else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
  23.     server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
  24. {
  25.     struct evictionPoolEntry *pool = db->eviction_pool;
  27.     while(bestkey == NULL) {
  28.         //选择随机样式，并从样本中作用LRU算法选择需要淘汰的数据
  29.         evictionPoolPopulate(dict, db->dict, db->eviction_pool);
  30.         /* Go backward from best to worst element to evict. */
  31.         for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
  32.             if (pool[k].key == NULL) continue;
  33.             de = dictFind(dict,pool[k].key);
  34.             sdsfree(pool[k].key);
  35.             //将pool+k+1之后的元素向前平移一个单位
  36.             memmove(pool+k,pool+k+1,
  37.                 sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
  38.             /* Clear the element on the right which is empty
  39.              * since we shifted one position to the left.  */
  40.             pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
  41.             pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
  42.             //选择了需要淘汰的数据
  43.             if (de) {
  44.                 bestkey = dictGetKey(de);
  45.                 break;
  46.             } else {
  47.                 /* Ghost... */
  48.                 continue;
  49.             }
  50.         }
  51.     }
  52. }

看了上面的代码，也许你还在奇怪，说好的，LRU算法去哪去了呢，再看看这个函数evictionPoolPopulate的实现吧

  1. #define EVICTION_SAMPLES_ARRAY_SIZE 16
  2. void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
  3.     int j, k, count;
  4.     //EVICTION_SAMPLES_ARRAY_SIZE最大样本数，默认16
  5.     dictEntry *_samples[EVICTION_SAMPLES_ARRAY_SIZE];
  6.     dictEntry **samples;
  7.     //如果我们在配置文件中配置的samples小于16，则直接使用EVICTION_SAMPLES_ARRAY_SIZE
  8.     if (server.maxmemory_samples <= EVICTION_SAMPLES_ARRAY_SIZE) {
  9.         samples = _samples;
  10.     } else {
  11.         samples = zmalloc(sizeof(samples[0])*server.maxmemory_samples);
  12.     }
  14. #if 1 /* Use bulk get by default. */
  15.     //从样本集中随机获取server.maxmemory_samples个数据，存放在
  16.     count = dictGetRandomKeys(sampledict,samples,server.maxmemory_samples);
  17. #else
  18.     count = server.maxmemory_samples;
  19.     for (j = 0; j < count; j++) samples[j] = dictGetRandomKey(sampledict);
  20. #endif
  22.     for (j = 0; j < count; j++) {
  23.         unsigned long long idle;
  24.         sds key;
  25.         robj *o;
  26.         dictEntry *de;
  27.         de = samples[j];
  28.         key = dictGetKey(de);
  29.         if (sampledict != keydict) de = dictFind(keydict, key);
  30.         o = dictGetVal(de);
  31.         //计算LRU时间
  32.         idle = estimateObjectIdleTime(o);
  33.         k = 0;
  34.         //选择de在pool中的正确位置,按升序进行排序,升序的依据是其idle时间
  35.         while (k < REDIS_EVICTION_POOL_SIZE &&
  36.                pool[k].key &&
  37.                pool[k].idle < idle) k++;
  38.         if (k == 0 && pool[REDIS_EVICTION_POOL_SIZE-1].key != NULL) {
  39.             /* Can't insert if the element is < the worst element we have
  40.              * and there are no empty buckets. */
  41.             continue;
  42.         } else if (k < REDIS_EVICTION_POOL_SIZE && pool[k].key == NULL) {
  43.             /* Inserting into empty position. No setup needed before insert. */
  44.         } else {
  45.             //移动元素，memmove,还有空间可以插入新元素
  46.             if (pool[REDIS_EVICTION_POOL_SIZE-1].key == NULL) {
  47.                 memmove(pool+k+1,pool+k,
  48.                     sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
  49.             } else {//已经没有空间插入新元素时，将第一个元素删除
  50.                 /* No free space on right? Insert at k-1 */
  51.                 k--;
  52.                 /* Shift all elements on the left of k (included) to the
  53.                  * left, so we discard the element with smaller idle time. */
  54.                 //以下操作突出了第K个位置
  55.                 sdsfree(pool[0].key);
  56.                 memmove(pool,pool+1,sizeof(pool[0])*k);
  57.             }
  58.         }
  59.         //在第K个位置插入
  60.         pool[k].key = sdsdup(key);
  61.         pool[k].idle = idle;
  62.     }
  63.     //执行到此之后，pool中存放的就是按idle time升序排序
  64.     if (samples != _samples) zfree(samples);
  65. }

看了上面的代码，LRU时钟的计算并没有包括在内，那么在看一下LRU算法的时钟计算代码吧,LRU时钟计算代码在object.c中的estimateObjectIdleTime这个函数中，代码如下~~

  1. //精略估计LRU时间
  2. unsigned long long estimateObjectIdleTime(robj *o) {
  3.     unsigned long long lruclock = LRU_CLOCK();
  4.     if (lruclock >= o->lru) {
  5.         return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
  6.     } else {//这种情况一般不会发生，发生时证明redis中键的保存时间已经wrap了
  7.         return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
  8.                     REDIS_LRU_CLOCK_RESOLUTION;
  9.     }
  10. }

好了，先到此吧~~~　

基于Redis的分布式锁到底安全吗（上）

网上有关Redis分布式锁的文章可谓多如牛毛了，不信的话你可以拿关键词“Redis 分布式锁”随便到哪个搜索引擎上去搜索一下就知道了。这些文章的思路大体相近，给出的实现算法也看似合乎逻辑，但当我们着手去实现它们的时候，却发现如果你越是仔细推敲，疑虑也就越来越多。
实际上，大概在一年以前，关于Redis分布式锁的安全性问题，在分布式系统专家Martin Kleppmann和Redis的作者antirez之间就发生过一场争论。由于对这个问题一直以来比较关注，所以我前些日子仔细阅读了与这场争论相关的资料。这场争论的大概过程是这样的：为了规范各家对基于Redis的分布式锁的实现，Redis的作者提出了一个更安全的实现，叫做Redlock。有一天，Martin Kleppmann写了一篇blog，分析了Redlock在安全性上存在的一些问题。然后Redis的作者立即写了一篇blog来反驳Martin的分析。但Martin表示仍然坚持原来的观点。随后，这个问题在Twitter和Hacker News上引发了激烈的讨论，很多分布式系统的专家都参与其中。
对于那些对分布式系统感兴趣的人来说，这个事件非常值得关注。不管你是刚接触分布式系统的新手，还是有着多年分布式开发经验的老手，读完这些分析和评论之后，大概都会有所收获。要知道，亲手实现过Redis Cluster这样一个复杂系统的antirez，足以算得上分布式领域的一名专家了。但对于由分布式锁引发的一系列问题的分析中，不同的专家却能得出迥异的结论，从中我们可以窥见分布式系统相关的问题具有何等的复杂性。实际上，在分布式系统的设计中经常发生的事情是：许多想法初看起来毫无破绽，而一旦详加考量，却发现不是那么天衣无缝。
下面，我们就从头至尾把这场争论过程中各方的观点进行一下回顾和分析。在这个过程中，我们把影响分布式锁的安全性的那些技术细节展开进行讨论，这将是一件很有意思的事情。这也是一个比较长的故事。当然，其中也免不了包含一些小“八卦”。

Redlock算法

就像本文开头所讲的，借助Redis来实现一个分布式锁(Distributed Lock)的做法，已经有很多人尝试过。人们构建这样的分布式锁的目的，是为了对一些共享资源进行互斥访问。
但是，这些实现虽然思路大体相近，但实现细节上各不相同，它们能提供的安全性和可用性也不尽相同。所以，Redis的作者antirez给出了一个更好的实现，称为Redlock，算是Redis官方对于实现分布式锁的指导规范。Redlock的算法描述就放在Redis的官网上：

在Redlock之前，很多人对于分布式锁的实现都是基于单个Redis节点的。而Redlock是基于多个Redis节点（都是Master）的一种实现。为了能理解Redlock，我们首先需要把简单的基于单Redis节点的算法描述清楚，因为它是Redlock的基础。

基于单Redis节点的分布式锁

首先，Redis客户端为了获取锁，向Redis节点发送如下命令：

  1. SET resource_name my_random_value NX PX 30000

上面的命令如果执行成功，则客户端成功获取到了锁，接下来就可以访问共享资源了；而如果上面的命令执行失败，则说明获取锁失败。
注意，在上面的SET命令中：

  • my_random_value是由客户端生成的一个随机字符串，它要保证在足够长的一段时间内在所有客户端的所有获取锁的请求中都是唯一的。
  • NX表示只有当resource_name对应的key值不存在的时候才能SET成功。这保证了只有第一个请求的客户端才能获得锁，而其它客户端在锁被释放之前都无法获得锁。
  • PX 30000表示这个锁有一个30秒的自动过期时间。当然，这里30秒只是一个例子，客户端可以选择合适的过期时间。

最后，当客户端完成了对共享资源的操作之后，执行下面的Redis Lua脚本来释放锁：

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

这段Lua脚本在执行的时候要把前面的my_random_value作为ARGV[1]的值传进去，把resource_name作为KEYS[1]的值传进去。
至此，基于单Redis节点的分布式锁的算法就描述完了。这里面有好几个问题需要重点分析一下。
首先第一个问题，这个锁必须要设置一个过期时间。否则的话，当一个客户端获取锁成功之后，假如它崩溃了，或者由于发生了网络分割（network partition）导致它再也无法和Redis节点通信了，那么它就会一直持有这个锁，而其它客户端永远无法获得锁了。antirez在后面的分析中也特别强调了这一点，而且把这个过期时间称为锁的有效时间(lock validity time)。获得锁的客户端必须在这个时间之内完成对共享资源的访问。
第二个问题，第一步获取锁的操作，网上不少文章把它实现成了两个Redis命令：

  1. SETNX resource_name my_random_value
  2. EXPIRE resource_name 30

虽然这两个命令和前面算法描述中的一个SET命令执行效果相同，但却不是原子的。如果客户端在执行完SETNX后崩溃了，那么就没有机会执行EXPIRE了，导致它一直持有这个锁。
第三个问题，也是antirez指出的，设置一个随机字符串my_random_value是很有必要的，它保证了一个客户端释放的锁必须是自己持有的那个锁。假如获取锁时SET的不是一个随机字符串，而是一个固定值，那么可能会发生下面的执行序列：

  1. 客户端1获取锁成功。
  2. 客户端1在某个操作上阻塞了很长时间。
  3. 过期时间到了，锁自动释放了。
  4. 客户端2获取到了对应同一个资源的锁。
  5. 客户端1从阻塞中恢复过来，释放掉了客户端2持有的锁。

之后，客户端2在访问共享资源的时候，就没有锁为它提供保护了。
第四个问题，释放锁的操作必须使用Lua脚本来实现。释放锁其实包含三步操作：’GET’、判断和’DEL’，用Lua脚本来实现能保证这三步的原子性。否则，如果把这三步操作放到客户端逻辑中去执行的话，就有可能发生与前面第三个问题类似的执行序列：

  1. 客户端1获取锁成功。
  2. 客户端1访问共享资源。
  3. 客户端1为了释放锁，先执行’GET’操作获取随机字符串的值。
  4. 客户端1判断随机字符串的值，与预期的值相等。
  5. 客户端1由于某个原因阻塞住了很长时间。
  6. 过期时间到了，锁自动释放了。
  7. 客户端2获取到了对应同一个资源的锁。
  8. 客户端1从阻塞中恢复过来，执行DEL操纵，释放掉了客户端2持有的锁。

实际上，在上述第三个问题和第四个问题的分析中，如果不是客户端阻塞住了，而是出现了大的网络延迟，也有可能导致类似的执行序列发生。
前面的四个问题，只要实现分布式锁的时候加以注意，就都能够被正确处理。但除此之外，antirez还指出了一个问题，是由failover引起的，却是基于单Redis节点的分布式锁无法解决的。正是这个问题催生了Redlock的出现。
这个问题是这样的。假如Redis节点宕机了，那么所有客户端就都无法获得锁了，服务变得不可用。为了提高可用性，我们可以给这个Redis节点挂一个Slave，当Master节点不可用的时候，系统自动切到Slave上（failover）。但由于Redis的主从复制（replication）是异步的，这可能导致在failover过程中丧失锁的安全性。考虑下面的执行序列：

  1. 客户端1从Master获取了锁。
  2. Master宕机了，存储锁的key还没有来得及同步到Slave上。
  3. Slave升级为Master。
  4. 客户端2从新的Master获取到了对应同一个资源的锁。

于是，客户端1和客户端2同时持有了同一个资源的锁。锁的安全性被打破。针对这个问题，antirez设计了Redlock算法，我们接下来会讨论。
【其它疑问】
前面这个算法中出现的锁的有效时间(lock validity time)，设置成多少合适呢？如果设置太短的话，锁就有可能在客户端完成对于共享资源的访问之前过期，从而失去保护；如果设置太长的话，一旦某个持有锁的客户端释放锁失败，那么就会导致所有其它客户端都无法获取锁，从而长时间内无法正常工作。看来真是个两难的问题。
而且，在前面对于随机字符串my_random_value的分析中，antirez也在文章中承认的确应该考虑客户端长期阻塞导致锁过期的情况。如果真的发生了这种情况，那么共享资源是不是已经失去了保护呢？antirez重新设计的Redlock是否能解决这些问题呢？

分布式锁Redlock

由于前面介绍的基于单Redis节点的分布式锁在failover的时候会产生解决不了的安全性问题，因此antirez提出了新的分布式锁的算法Redlock，它基于N个完全独立的Redis节点（通常情况下N可以设置成5）。
运行Redlock算法的客户端依次执行下面各个步骤，来完成获取锁的操作：

  1. 获取当前时间（毫秒数）。
  2. 按顺序依次向N个Redis节点执行获取锁的操作。这个获取操作跟前面基于单Redis节点的获取锁的过程相同，包含随机字符串my_random_value，也包含过期时间(比如PX 30000，即锁的有效时间)。为了保证在某个Redis节点不可用的时候算法能够继续运行，这个获取锁的操作还有一个超时时间(time out)，它要远小于锁的有效时间（几十毫秒量级）。客户端在向某个Redis节点获取锁失败以后，应该立即尝试下一个Redis节点。这里的失败，应该包含任何类型的失败，比如该Redis节点不可用，或者该Redis节点上的锁已经被其它客户端持有（注：Redlock原文中这里只提到了Redis节点不可用的情况，但也应该包含其它的失败情况）。
  3. 计算整个获取锁的过程总共消耗了多长时间，计算方法是用当前时间减去第1步记录的时间。如果客户端从大多数Redis节点（>= N/2+1）成功获取到了锁，并且获取锁总共消耗的时间没有超过锁的有效时间(lock validity time)，那么这时客户端才认为最终获取锁成功；否则，认为最终获取锁失败。
  4. 如果最终获取锁成功了，那么这个锁的有效时间应该重新计算，它等于最初的锁的有效时间减去第3步计算出来的获取锁消耗的时间。
  5. 如果最终获取锁失败了（可能由于获取到锁的Redis节点个数少于N/2+1，或者整个获取锁的过程消耗的时间超过了锁的最初有效时间），那么客户端应该立即向所有Redis节点发起释放锁的操作（即前面介绍的Redis Lua脚本）。

当然，上面描述的只是获取锁的过程，而释放锁的过程比较简单：客户端向所有Redis节点发起释放锁的操作，不管这些节点当时在获取锁的时候成功与否。
由于N个Redis节点中的大多数能正常工作就能保证Redlock正常工作，因此理论上它的可用性更高。我们前面讨论的单Redis节点的分布式锁在failover的时候锁失效的问题，在Redlock中不存在了，但如果有节点发生崩溃重启，还是会对锁的安全性有影响的。具体的影响程度跟Redis对数据的持久化程度有关。
假设一共有5个Redis节点：A, B, C, D, E。设想发生了如下的事件序列：

  1. 客户端1成功锁住了A, B, C，获取锁成功（但D和E没有锁住）。
  2. 节点C崩溃重启了，但客户端1在C上加的锁没有持久化下来，丢失了。
  3. 节点C重启后，客户端2锁住了C, D, E，获取锁成功。

这样，客户端1和客户端2同时获得了锁（针对同一资源）。
在默认情况下，Redis的AOF持久化方式是每秒写一次磁盘（即执行fsync），因此最坏情况下可能丢失1秒的数据。为了尽可能不丢数据，Redis允许设置成每次修改数据都进行fsync，但这会降低性能。当然，即使执行了fsync也仍然有可能丢失数据（这取决于系统而不是Redis的实现）。所以，上面分析的由于节点重启引发的锁失效问题，总是有可能出现的。为了应对这一问题，antirez又提出了延迟重启(delayed restarts)的概念。也就是说，一个节点崩溃后，先不立即重启它，而是等待一段时间再重启，这段时间应该大于锁的有效时间(lock validity time)。这样的话，这个节点在重启前所参与的锁都会过期，它在重启后就不会对现有的锁造成影响。
关于Redlock还有一点细节值得拿出来分析一下：在最后释放锁的时候，antirez在算法描述中特别强调，客户端应该向所有Redis节点发起释放锁的操作。也就是说，即使当时向某个节点获取锁没有成功，在释放锁的时候也不应该漏掉这个节点。这是为什么呢？设想这样一种情况，客户端发给某个Redis节点的获取锁的请求成功到达了该Redis节点，这个节点也成功执行了SET操作，但是它返回给客户端的响应包却丢失了。这在客户端看来，获取锁的请求由于超时而失败了，但在Redis这边看来，加锁已经成功了。因此，释放锁的时候，客户端也应该对当时获取锁失败的那些Redis节点同样发起请求。实际上，这种情况在异步通信模型中是有可能发生的：客户端向服务器通信是正常的，但反方向却是有问题的。
【其它疑问】
前面在讨论单Redis节点的分布式锁的时候，最后我们提出了一个疑问，如果客户端长期阻塞导致锁过期，那么它接下来访问共享资源就不安全了（没有了锁的保护）。这个问题在Redlock中是否有所改善呢？显然，这样的问题在Redlock中是依然存在的。
另外，在算法第4步成功获取了锁之后，如果由于获取锁的过程消耗了较长时间，重新计算出来的剩余的锁有效时间很短了，那么我们还来得及去完成共享资源访问吗？如果我们认为太短，是不是应该立即进行锁的释放操作？那到底多短才算呢？又是一个选择难题。

Martin的分析

Martin Kleppmann在2016-02-08这一天发表了一篇blog，名字叫”How to do distributed locking “，地址如下：

Martin在这篇文章中谈及了分布式系统的很多基础性的问题（特别是分布式计算的异步模型），对分布式系统的从业者来说非常值得一读。这篇文章大体可以分为两大部分：

  • 前半部分，与Redlock无关。Martin指出，即使我们拥有一个完美实现的分布式锁（带自动过期功能），在没有共享资源参与进来提供某种fencing机制的前提下，我们仍然不可能获得足够的安全性。
  • 后半部分，是对Redlock本身的批评。Martin指出，由于Redlock本质上是建立在一个同步模型之上，对系统的记时假设(timing assumption)有很强的要求，因此本身的安全性是不够的。

首先我们讨论一下前半部分的关键点。Martin给出了下面这样一份时序图：
Redis 基础知识 - 图85
在上面的时序图中，假设锁服务本身是没有问题的，它总是能保证任一时刻最多只有一个客户端获得锁。上图中出现的lease这个词可以暂且认为就等同于一个带有自动过期功能的锁。客户端1在获得锁之后发生了很长时间的GC pause，在此期间，它获得的锁过期了，而客户端2获得了锁。当客户端1从GC pause中恢复过来的时候，它不知道自己持有的锁已经过期了，它依然向共享资源（上图中是一个存储服务）发起了写数据请求，而这时锁实际上被客户端2持有，因此两个客户端的写请求就有可能冲突（锁的互斥作用失效了）。
初看上去，有人可能会说，既然客户端1从GC pause中恢复过来以后不知道自己持有的锁已经过期了，那么它可以在访问共享资源之前先判断一下锁是否过期。但仔细想想，这丝毫也没有帮助。因为GC pause可能发生在任意时刻，也许恰好在判断完之后。
也有人会说，如果客户端使用没有GC的语言来实现，是不是就没有这个问题呢？Martin指出，系统环境太复杂，仍然有很多原因导致进程的pause，比如虚存造成的缺页故障(page fault)，再比如CPU资源的竞争。即使不考虑进程pause的情况，网络延迟也仍然会造成类似的结果。
总结起来就是说，即使锁服务本身是没有问题的，而仅仅是客户端有长时间的pause或网络延迟，仍然会造成两个客户端同时访问共享资源的冲突情况发生。而这种情况其实就是我们在前面已经提出来的“客户端长期阻塞导致锁过期”的那个疑问。
那怎么解决这个问题呢？Martin给出了一种方法，称为fencing token。fencing token是一个单调递增的数字，当客户端成功获取锁的时候它随同锁一起返回给客户端。而客户端访问共享资源的时候带着这个fencing token，这样提供共享资源的服务就能根据它进行检查，拒绝掉延迟到来的访问请求（避免了冲突）。如下图：
Redis 基础知识 - 图86
在上图中，客户端1先获取到的锁，因此有一个较小的fencing token，等于33，而客户端2后获取到的锁，有一个较大的fencing token，等于34。客户端1从GC pause中恢复过来之后，依然是向存储服务发送访问请求，但是带了fencing token = 33。存储服务发现它之前已经处理过34的请求，所以会拒绝掉这次33的请求。这样就避免了冲突。
现在我们再讨论一下Martin的文章的后半部分。
Martin在文中构造了一些事件序列，能够让Redlock失效（两个客户端同时持有锁）。为了说明Redlock对系统记时(timing)的过分依赖，他首先给出了下面的一个例子（还是假设有5个Redis节点A, B, C, D, E）：

  1. 客户端1从Redis节点A, B, C成功获取了锁（多数节点）。由于网络问题，与D和E通信失败。
  2. 节点C上的时钟发生了向前跳跃，导致它上面维护的锁快速过期。
  3. 客户端2从Redis节点C, D, E成功获取了同一个资源的锁（多数节点）。
  4. 客户端1和客户端2现在都认为自己持有了锁。

上面这种情况之所以有可能发生，本质上是因为Redlock的安全性(safety property)对系统的时钟有比较强的依赖，一旦系统的时钟变得不准确，算法的安全性也就保证不了了。Martin在这里其实是要指出分布式算法研究中的一些基础性问题，或者说一些常识问题，即好的分布式算法应该基于异步模型(asynchronous model)，算法的安全性不应该依赖于任何记时假设(timing assumption)。在异步模型中：进程可能pause任意长的时间，消息可能在网络中延迟任意长的时间，甚至丢失，系统时钟也可能以任意方式出错。一个好的分布式算法，这些因素不应该影响它的安全性(safety property)，只可能影响到它的活性(liveness property)，也就是说，即使在非常极端的情况下（比如系统时钟严重错误），算法顶多是不能在有限的时间内给出结果而已，而不应该给出错误的结果。这样的算法在现实中是存在的，像比较著名的Paxos，或Raft。但显然按这个标准的话，Redlock的安全性级别是达不到的。
随后，Martin觉得前面这个时钟跳跃的例子还不够，又给出了一个由客户端GC pause引发Redlock失效的例子。如下：

  1. 客户端1向Redis节点A, B, C, D, E发起锁请求。
  2. 各个Redis节点已经把请求结果返回给了客户端1，但客户端1在收到请求结果之前进入了长时间的GC pause。
  3. 在所有的Redis节点上，锁过期了。
  4. 客户端2在A, B, C, D, E上获取到了锁。
  5. 客户端1从GC pause从恢复，收到了前面第2步来自各个Redis节点的请求结果。客户端1认为自己成功获取到了锁。
  6. 客户端1和客户端2现在都认为自己持有了锁。

Martin给出的这个例子其实有点小问题。在Redlock算法中，客户端在完成向各个Redis节点的获取锁的请求之后，会计算这个过程消耗的时间，然后检查是不是超过了锁的有效时间(lock validity time)。也就是上面的例子中第5步，客户端1从GC pause中恢复过来以后，它会通过这个检查发现锁已经过期了，不会再认为自己成功获取到锁了。随后antirez在他的反驳文章中就指出来了这个问题，但Martin认为这个细节对Redlock整体的安全性没有本质的影响。
抛开这个细节，我们可以分析一下Martin举这个例子的意图在哪。初看起来，这个例子跟文章前半部分分析通用的分布式锁时给出的GC pause的时序图是基本一样的，只不过那里的GC pause发生在客户端1获得了锁之后，而这里的GC pause发生在客户端1获得锁之前。但两个例子的侧重点不太一样。Martin构造这里的这个例子，是为了强调在一个分布式的异步环境下，长时间的GC pause或消息延迟（上面这个例子中，把GC pause换成Redis节点和客户端1之间的消息延迟，逻辑不变），会让客户端获得一个已经过期的锁。从客户端1的角度看，Redlock的安全性被打破了，因为客户端1收到锁的时候，这个锁已经失效了，而Redlock同时还把这个锁分配给了客户端2。换句话说，Redis服务器在把锁分发给客户端的途中，锁就过期了，但又没有有效的机制让客户端明确知道这个问题。而在之前的那个例子中，客户端1收到锁的时候锁还是有效的，锁服务本身的安全性可以认为没有被打破，后面虽然也出了问题，但问题是出在客户端1和共享资源服务器之间的交互上。
在Martin的这篇文章中，还有一个很有见地的观点，就是对锁的用途的区分。他把锁的用途分为两种：

  • 为了效率(efficiency)，协调各个客户端避免做重复的工作。即使锁偶尔失效了，只是可能把某些操作多做一遍而已，不会产生其它的不良后果。比如重复发送了一封同样的email。
  • 为了正确性(correctness)。在任何情况下都不允许锁失效的情况发生，因为一旦发生，就可能意味着数据不一致(inconsistency)，数据丢失，文件损坏，或者其它严重的问题。

最后，Martin得出了如下的结论：

  • 如果是为了效率(efficiency)而使用分布式锁，允许锁的偶尔失效，那么使用单Redis节点的锁方案就足够了，简单而且效率高。Redlock则是个过重的实现(heavyweight)。
  • 如果是为了正确性(correctness)在很严肃的场合使用分布式锁，那么不要使用Redlock。它不是建立在异步模型上的一个足够强的算法，它对于系统模型的假设中包含很多危险的成分(对于timing)。而且，它没有一个机制能够提供fencing token。那应该使用什么技术呢？Martin认为，应该考虑类似Zookeeper的方案，或者支持事务的数据库。

Martin对Redlock算法的形容是：

neither fish nor fowl （非驴非马）

【其它疑问】

  • Martin提出的fencing token的方案，需要对提供共享资源的服务进行修改，这在现实中可行吗？
  • 根据Martin的说法，看起来，如果资源服务器实现了fencing token，它在分布式锁失效的情况下也仍然能保持资源的互斥访问。这是不是意味着分布式锁根本没有存在的意义了？
  • 资源服务器需要检查fencing token的大小，如果提供资源访问的服务也是包含多个节点的（分布式的），那么这里怎么检查才能保证fencing token在多个节点上是递增的呢？
  • Martin对于fencing token的举例中，两个fencing token到达资源服务器的顺序颠倒了（小的fencing token后到了），这时资源服务器检查出了这一问题。如果客户端1和客户端2都发生了GC pause，两个fencing token都延迟了，它们几乎同时到达了资源服务器，但保持了顺序，那么资源服务器是不是就检查不出问题了？这时对于资源的访问是不是就发生冲突了？
  • 分布式锁+fencing的方案是绝对正确的吗？能证明吗？

（未完，故事太长，下半部待续）

基于Redis的分布式锁到底安全吗（下）

自从我写完这个话题的上半部分之后，就感觉头脑中出现了许多细小的声音，久久挥之不去。它们就像是在为了一些鸡毛蒜皮的小事而相互争吵个不停。的确，有关分布式的话题就是这样，琐碎异常，而且每个人说的话听起来似乎都有道理。
今天，我们就继续探讨这个话题的后半部分。本文中，我们将从antirez反驳Martin Kleppmann的观点开始讲起，然后会涉及到Hacker News上出现的一些讨论内容，接下来我们还会讨论到基于Zookeeper和Chubby的分布式锁是怎样的，并和Redlock进行一些对比。最后，我们会提到Martin对于这一事件的总结。
还没有看过上半部分的同学，请先阅读：

  • 基于Redis的分布式锁到底安全吗（上）

    antirez的反驳

    Martin在发表了那篇分析分布式锁的blog (How to do distributed locking)之后，该文章在Twitter和Hacker News上引发了广泛的讨论。但人们更想听到的是Redlock的作者antirez对此会发表什么样的看法。
    Martin的那篇文章是在2016-02-08这一天发表的，但据Martin说，他在公开发表文章的一星期之前就把草稿发给了antirez进行review，而且他们之间通过email进行了讨论。不知道Martin有没有意料到，antirez对于此事的反应很快，就在Martin的文章发表出来的第二天，antirez就在他的博客上贴出了他对于此事的反驳文章，名字叫”Is Redlock safe?”，地址如下:

  • http://antirez.com/news/101

这是高手之间的过招。antirez这篇文章也条例非常清晰，并且中间涉及到大量的细节。antirez认为，Martin的文章对于Redlock的批评可以概括为两个方面（与Martin文章的前后两部分对应）：

  • 带有自动过期功能的分布式锁，必须提供某种fencing机制来保证对共享资源的真正的互斥保护。Redlock提供不了这样一种机制。
  • Redlock构建在一个不够安全的系统模型之上。它对于系统的记时假设(timing assumption)有比较强的要求，而这些要求在现实的系统中是无法保证的。

antirez对这两方面分别进行了反驳。
首先，关于fencing机制。antirez对于Martin的这种论证方式提出了质疑：既然在锁失效的情况下已经存在一种fencing机制能继续保持资源的互斥访问了，那为什么还要使用一个分布式锁并且还要求它提供那么强的安全性保证呢？即使退一步讲，Redlock虽然提供不了Martin所讲的递增的fencing token，但利用Redlock产生的随机字符串(my_random_value)可以达到同样的效果。这个随机字符串虽然不是递增的，但却是唯一的，可以称之为unique token。antirez举了个例子，比如，你可以用它来实现“Check and Set”操作，原话是：

When starting to work with a shared resource, we set its state to “<token>”, then we operate the read-modify-write only if the token is still the same when we write. （译文：当开始和共享资源交互的时候，我们将它的状态设置成“<token>”，然后仅在token没改变的情况下我们才执行“读取-修改-写回”操作。）

第一遍看到这个描述的时候，我个人是感觉没太看懂的。“Check and Set”应该就是我们平常听到过的CAS操作了，但它如何在这个场景下工作，antirez并没有展开说（在后面讲到Hacker News上的讨论的时候，我们还会提到）。
然后，antirez的反驳就集中在第二个方面上：关于算法在记时(timing)方面的模型假设。在我们前面分析Martin的文章时也提到过，Martin认为Redlock会失效的情况主要有三种：

  • 时钟发生跳跃。
  • 长时间的GC pause。
  • 长时间的网络延迟。

antirez肯定意识到了这三种情况对Redlock最致命的其实是第一点：时钟发生跳跃。这种情况一旦发生，Redlock是没法正常工作的。而对于后两种情况来说，Redlock在当初设计的时候已经考虑到了，对它们引起的后果有一定的免疫力。所以，antirez接下来集中精力来说明通过恰当的运维，完全可以避免时钟发生大的跳动，而Redlock对于时钟的要求在现实系统中是完全可以满足的。
Martin在提到时钟跳跃的时候，举了两个可能造成时钟跳跃的具体例子：

  • 系统管理员手动修改了时钟。
  • 从NTP服务收到了一个大的时钟更新事件。

antirez反驳说：

  • 手动修改时钟这种人为原因，不要那么做就是了。否则的话，如果有人手动修改Raft协议的持久化日志，那么就算是Raft协议它也没法正常工作了。
  • 使用一个不会进行“跳跃”式调整系统时钟的ntpd程序（可能是通过恰当的配置），对于时钟的修改通过多次微小的调整来完成。

而Redlock对时钟的要求，并不需要完全精确，它只需要时钟差不多精确就可以了。比如，要记时5秒，但可能实际记了4.5秒，然后又记了5.5秒，有一定的误差。不过只要误差不超过一定范围，这对Redlock不会产生影响。antirez认为呢，像这样对时钟精度并不是很高的要求，在实际环境中是完全合理的。
好了，到此为止，如果你相信antirez这里关于时钟的论断，那么接下来antirez的分析就基本上顺理成章了。
关于Martin提到的能使Redlock失效的后两种情况，Martin在分析的时候恰好犯了一个错误（在本文上半部分已经提到过）。在Martin给出的那个由客户端GC pause引发Redlock失效的例子中，这个GC pause引发的后果相当于在锁服务器和客户端之间发生了长时间的消息延迟。Redlock对于这个情况是能处理的。回想一下Redlock算法的具体过程，它使用起来的过程大体可以分成5步：

  1. 获取当前时间。
  2. 完成获取锁的整个过程（与N个Redis节点交互）。
  3. 再次获取当前时间。
  4. 把两个时间相减，计算获取锁的过程是否消耗了太长时间，导致锁已经过期了。如果没过期，
  5. 客户端持有锁去访问共享资源。

在Martin举的例子中，GC pause或网络延迟，实际发生在上述第1步和第3步之间。而不管在第1步和第3步之间由于什么原因（进程停顿或网络延迟等）导致了大的延迟出现，在第4步都能被检查出来，不会让客户端拿到一个它认为有效而实际却已经过期的锁。当然，这个检查依赖系统时钟没有大的跳跃。这也就是为什么antirez在前面要对时钟条件进行辩护的原因。
有人会说，在第3步之后，仍然可能会发生延迟啊。没错，antirez承认这一点，他对此有一段很有意思的论证，原话如下：

The delay can only happen after steps 3, resulting into the lock to be considered ok while actually expired, that is, we are back at the first problem Martin identified of distributed locks where the client fails to stop working to the shared resource before the lock validity expires. Let me tell again how this problem is common with all the distributed locks implementations, and how the token as a solution is both unrealistic and can be used with Redlock as well. （译文：延迟只能发生在第3步之后，这导致锁被认为是有效的而实际上已经过期了，也就是说，我们回到了Martin指出的第一个问题上，客户端没能够在锁的有效性过期之前完成与共享资源的交互。让我再次申明一下，这个问题对于所有的分布式锁的实现是普遍存在的，而且基于token的这种解决方案是不切实际的，但也能和Redlock一起用。）

这里antirez所说的“Martin指出的第一个问题”具体是什么呢？在本文上半部分我们提到过，Martin的文章分为两大部分，其中前半部分与Redlock没有直接关系，而是指出了任何一种带自动过期功能的分布式锁在没有提供fencing机制的前提下都有可能失效。这里antirez所说的就是指的Martin的文章的前半部分。换句话说，对于大延迟给Redlock带来的影响，恰好与Martin在文章的前半部分针对所有的分布式锁所做的分析是一致的，而这种影响不单单针对Redlock。Redlock的实现已经保证了它是和其它任何分布式锁的安全性是一样的。当然，与其它“更完美”的分布式锁相比，Redlock似乎提供不了Martin提出的那种递增的token，但antirez在前面已经分析过了，关于token的这种论证方式本身就是“不切实际”的，或者退一步讲，Redlock能提供的unique token也能够提供完全一样的效果。
另外，关于大延迟对Redlock的影响，antirez和Martin在Twitter上有下面的对话：

antirez: @martinkl so I wonder if after my reply, we can at least agree about unbound messages delay to don’t cause any harm. Martin: @antirez Agree about message delay between app and lock server. Delay between app and resource being accessed is still problematic. （译文： antirez问：我想知道，在我发文回复之后，我们能否在一点上达成一致，就是大的消息延迟不会给Redlock的运行造成损害。 Martin答：对于客户端和锁服务器之间的消息延迟，我同意你的观点。但客户端和被访问资源之间的延迟还是有问题的。）

通过这段对话可以看出，对于Redlock在第4步所做的锁有效性的检查，Martin是予以肯定的。但他认为客户端和资源服务器之间的延迟还是会带来问题的。Martin在这里说的有点模糊。就像antirez前面分析的，客户端和资源服务器之间的延迟，对所有的分布式锁的实现都会带来影响，这不单单是Redlock的问题了。
以上就是antirez在blog中所说的主要内容。有一些点值得我们注意一下：

  • antirez是同意大的系统时钟跳跃会造成Redlock失效的。在这一点上，他与Martin的观点的不同在于，他认为在实际系统中是可以避免大的时钟跳跃的。当然，这取决于基础设施和运维方式。
  • antirez在设计Redlock的时候，是充分考虑了网络延迟和程序停顿所带来的影响的。但是，对于客户端和资源服务器之间的延迟（即发生在算法第3步之后的延迟），antirez是承认所有的分布式锁的实现，包括Redlock，是没有什么好办法来应对的。

讨论进行到这，Martin和antirez之间谁对谁错其实并不是那么重要了。只要我们能够对Redlock（或者其它分布式锁）所能提供的安全性的程度有充分的了解，那么我们就能做出自己的选择了。

Hacker News上的一些讨论

针对Martin和antirez的两篇blog，很多技术人员在Hacker News上展开了激烈的讨论。这些讨论所在地址如下：

在Hacker News上，antirez积极参与了讨论，而Martin则始终置身事外。
下面我把这些讨论中一些有意思的点拿出来与大家一起分享一下（集中在对于fencing token机制的讨论上）。
关于antirez提出的“Check and Set”操作，他在blog里并没有详加说明。果然，在Hacker News上就有人出来问了。antirez给出的答复如下：

You want to modify locked resource X. You set X.currlock = token. Then you read, do whatever you want, and when you write, you “write-if-currlock == token”. If another client did X.currlock = somethingelse, the transaction fails.

翻译一下可以这样理解：假设你要修改资源X，那么遵循下面的伪码所定义的步骤。

  1. 先设置X.currlock = token。
  2. 读出资源X（包括它的值和附带的X.currlock）。
  3. 按照”write-if-currlock == token”的逻辑，修改资源X的值。意思是说，如果对X进行修改的时候，X.currlock仍然和当初设置进去的token相等，那么才进行修改；如果这时X.currlock已经是其它值了，那么说明有另外一方也在试图进行修改操作，那么放弃当前的修改，从而避免冲突。

随后Hacker News上一位叫viraptor的用户提出了异议，它给出了这样一个执行序列：

  • A: X.currlock = Token_ID_A
  • A: resource read
  • A: is X.currlock still Token_ID_A? yes
  • B: X.currlock = Token_ID_B
  • B: resource read
  • B: is X.currlock still Token_ID_B? yes
  • B: resource write
  • A: resource write

到了最后两步，两个客户端A和B同时进行写操作，冲突了。不过，这位用户应该是理解错了antirez给出的修改过程了。按照antirez的意思，判断X.currlock是否修改过和对资源的写操作，应该是一个原子操作。只有这样理解才能合乎逻辑，否则的话，这个过程就有严重的破绽。这也是为什么antirez之前会对fencing机制产生质疑：既然资源服务器本身都能提供互斥的原子操作了，为什么还需要一个分布式锁呢？因此，antirez认为这种fencing机制是很累赘的，他之所以还是提出了这种“Check and Set”操作，只是为了证明在提供fencing token这一点上，Redlock也能做到。但是，这里仍然有一些不明确的地方，如果将”write-if-currlock == token”看做是原子操作的话，这个逻辑势必要在资源服务器上执行，那么第二步为什么还要“读出资源X”呢？除非这个“读出资源X”的操作也是在资源服务器上执行，它包含在“判断-写回”这个原子操作里面。而假如不这样理解的话，“读取-判断-写回”这三个操作都放在客户端执行，那么看不出它们如何才能实现原子性操作。在下面的讨论中，我们暂时忽略“读出资源X”这一步。
这个基于random token的“Check and Set”操作，如果与Martin提出的递增的fencing token对比一下的话，至少有两点不同：

  • “Check and Set”对于写操作要分成两步来完成（设置token、判断-写回），而递增的fencing token机制只需要一步（带着token向资源服务器发起写请求）。
  • 递增的fencing token机制能保证最终操作共享资源的顺序，那些延迟时间太长的操作就无法操作共享资源了。但是基于random token的“Check and Set”操作不会保证这个顺序，那些延迟时间太长的操作如果后到达了，它仍然有可能操作共享资源（当然是以互斥的方式）。

对于前一点不同，我们在后面的分析中会看到，如果资源服务器也是分布式的，那么使用递增的fencing token也要变成两步。
而对于后一点操作顺序上的不同，antirez认为这个顺序没有意义，关键是能互斥访问就行了。他写下了下面的话：

So the goal is, when race conditions happen, to avoid them in some way. …… Note also that when it happens that, because of delays, the clients are accessing concurrently, the lock ID has little to do with the order in which the operations were indented to happen. （译文： 我们的目标是，当竞争条件出现的时候，能够以某种方式避免。 …… 还需要注意的是，当那种竞争条件出现的时候，比如由于延迟，客户端是同时来访问的，锁的ID的大小顺序跟那些操作真正想执行的顺序，是没有什么关系的。）

这里的lock ID，跟Martin说的递增的token是一回事。
随后，antirez举了一个“将名字加入列表”的操作的例子：

  • T0: Client A receives new name to add from web.
  • T0: Client B is idle
  • T1: Client A is experiencing pauses.
  • T1: Client B receives new name to add from web.
  • T2: Client A is experiencing pauses.
  • T2: Client B receives a lock with ID 1
  • T3: Client A receives a lock with ID 2

你看，两个客户端（其实是Web服务器）执行“添加名字”的操作，A本来是排在B前面的，但获得锁的顺序却是B排在A前面。因此，antirez说，锁的ID的大小顺序跟那些操作真正想执行的顺序，是没有什么关系的。关键是能排出一个顺序来，能互斥访问就行了。那么，至于锁的ID是递增的，还是一个random token，自然就不那么重要了。
Martin提出的fencing token机制，给人留下了无尽的疑惑。这主要是因为他对于这一机制的描述缺少太多的技术细节。从上面的讨论可以看出，antirez对于这一机制的看法是，它跟一个random token没有什么区别，而且，它需要资源服务器本身提供某种互斥机制，这几乎让分布式锁本身的存在失去了意义。围绕fencing token的问题，还有两点是比较引人注目的，Hacker News上也有人提出了相关的疑问：

  • （1）关于资源服务器本身的架构细节。
  • （2）资源服务器对于fencing token进行检查的实现细节，比如是否需要提供一种原子操作。

关于上述问题（1），Hacker News上有一位叫dwenzek的用户发表了下面的评论：

…… the issue around the usage of fencing tokens to reject any late usage of a lock is unclear just because the protected resource and its access are themselves unspecified. Is the resource distributed or not? If distributed, does the resource has a mean to ensure that tokens are increasing over all the nodes? Does the resource have a mean to rollback any effects done by a client which session is interrupted by a timeout? （译文：…… 关于使用fencing token拒绝掉延迟请求的相关议题，是不够清晰的，因为受保护的资源以及对它的访问方式本身是没有被明确定义过的。资源服务是不是分布式的呢？如果是，资源服务有没有一种方式能确保token在所有节点上递增呢？对于客户端的Session由于过期而被中断的情况，资源服务有办法将它的影响回滚吗？）

这些疑问在Hacker News上并没有人给出解答。而关于分布式的资源服务器架构如何处理fencing token，另外一名分布式系统的专家Flavio Junqueira在他的一篇blog中有所提及（我们后面会再提到）。
关于上述问题（2），Hacker News上有一位叫reza_n的用户发表了下面的疑问：

I understand how a fencing token can prevent out of order writes when 2 clients get the same lock. But what happens when those writes happen to arrive in order and you are doing a value modification? Don’t you still need to rely on some kind of value versioning or optimistic locking? Wouldn’t this make the use of a distributed lock unnecessary? （译文： 我理解当两个客户端同时获得锁的时候fencing token是如何防止乱序的。但是如果两个写操作恰好按序到达了，而且它们在对同一个值进行修改，那会发生什么呢？难道不会仍然是依赖某种数据版本号或者乐观锁的机制？这不会让分布式锁变得没有必要了吗？）

一位叫Terr_的Hacker News用户答：

I believe the “first” write fails, because the token being passed in is no longer “the lastest”, which indicates their lock was already released or expired. （译文： 我认为“第一个”写请求会失败，因为它传入的token不再是“最新的”了，这意味着锁已经释放或者过期了。）

Terr_的回答到底对不对呢？这不好说，取决于资源服务器对于fencing token进行检查的实现细节。让我们来简单分析一下。
为了简单起见，我们假设有一台（先不考虑分布式的情况）通过RPC进行远程访问文件服务器，它无法提供对于文件的互斥访问（否则我们就不需要分布式锁了）。现在我们按照Martin给出的说法，加入fencing token的检查逻辑。由于Martin没有描述具体细节，我们猜测至少有两种可能。
第一种可能，我们修改了文件服务器的代码，让它能多接受一个fencing token的参数，并在进行所有处理之前加入了一个简单的判断逻辑，保证只有当前接收到的fencing token大于之前的值才允许进行后边的访问。而一旦通过了这个判断，后面的处理不变。
现在想象reza_n描述的场景，客户端1和客户端2都发生了GC pause，两个fencing token都延迟了，它们几乎同时到达了文件服务器，而且保持了顺序。那么，我们新加入的判断逻辑，应该对两个请求都会放过，而放过之后它们几乎同时在操作文件，还是冲突了。既然Martin宣称fencing token能保证分布式锁的正确性，那么上面这种可能的猜测也许是我们理解错了。
当然，还有第二种可能，就是我们对文件服务器确实做了比较大的改动，让这里判断token的逻辑和随后对文件的处理放在一个原子操作里了。这可能更接近antirez的理解。这样的话，前面reza_n描述的场景中，两个写操作都应该成功。

基于ZooKeeper的分布式锁更安全吗？

很多人（也包括Martin在内）都认为，如果你想构建一个更安全的分布式锁，那么应该使用ZooKeeper，而不是Redis。那么，为了对比的目的，让我们先暂时脱离开本文的题目，讨论一下基于ZooKeeper的分布式锁能提供绝对的安全吗？它需要fencing token机制的保护吗？
我们不得不提一下分布式专家Flavio Junqueira所写的一篇blog，题目叫“Note on fencing and distributed locks”，地址如下：

Flavio Junqueira是ZooKeeper的作者之一，他的这篇blog就写在Martin和antirez发生争论的那几天。他在文中给出了一个基于ZooKeeper构建分布式锁的描述（当然这不是唯一的方式）：

  • 客户端尝试创建一个znode节点，比如/lock。那么第一个客户端就创建成功了，相当于拿到了锁；而其它的客户端会创建失败（znode已存在），获取锁失败。
  • 持有锁的客户端访问共享资源完成后，将znode删掉，这样其它客户端接下来就能来获取锁了。
  • znode应该被创建成ephemeral的。这是znode的一个特性，它保证如果创建znode的那个客户端崩溃了，那么相应的znode会被自动删除。这保证了锁一定会被释放。

看起来这个锁相当完美，没有Redlock过期时间的问题，而且能在需要的时候让锁自动释放。但仔细考察的话，并不尽然。
ZooKeeper是怎么检测出某个客户端已经崩溃了呢？实际上，每个客户端都与ZooKeeper的某台服务器维护着一个Session，这个Session依赖定期的心跳(heartbeat)来维持。如果ZooKeeper长时间收不到客户端的心跳（这个时间称为Sesion的过期时间），那么它就认为Session过期了，通过这个Session所创建的所有的ephemeral类型的znode节点都会被自动删除。
设想如下的执行序列：

  1. 客户端1创建了znode节点/lock，获得了锁。
  2. 客户端1进入了长时间的GC pause。
  3. 客户端1连接到ZooKeeper的Session过期了。znode节点/lock被自动删除。
  4. 客户端2创建了znode节点/lock，从而获得了锁。
  5. 客户端1从GC pause中恢复过来，它仍然认为自己持有锁。

最后，客户端1和客户端2都认为自己持有了锁，冲突了。这与之前Martin在文章中描述的由于GC pause导致的分布式锁失效的情况类似。
看起来，用ZooKeeper实现的分布式锁也不一定就是安全的。该有的问题它还是有。但是，ZooKeeper作为一个专门为分布式应用提供方案的框架，它提供了一些非常好的特性，是Redis之类的方案所没有的。像前面提到的ephemeral类型的znode自动删除的功能就是一个例子。
还有一个很有用的特性是ZooKeeper的watch机制。这个机制可以这样来使用，比如当客户端试图创建/lock的时候，发现它已经存在了，这时候创建失败，但客户端不一定就此对外宣告获取锁失败。客户端可以进入一种等待状态，等待当/lock节点被删除的时候，ZooKeeper通过watch机制通知它，这样它就可以继续完成创建操作（获取锁）。这可以让分布式锁在客户端用起来就像一个本地的锁一样：加锁失败就阻塞住，直到获取到锁为止。这样的特性Redlock就无法实现。
小结一下，基于ZooKeeper的锁和基于Redis的锁相比在实现特性上有两个不同：

  • 在正常情况下，客户端可以持有锁任意长的时间，这可以确保它做完所有需要的资源访问操作之后再释放锁。这避免了基于Redis的锁对于有效时间(lock validity time)到底设置多长的两难问题。实际上，基于ZooKeeper的锁是依靠Session（心跳）来维持锁的持有状态的，而Redis不支持Sesion。
  • 基于ZooKeeper的锁支持在获取锁失败之后等待锁重新释放的事件。这让客户端对锁的使用更加灵活。

顺便提一下，如上所述的基于ZooKeeper的分布式锁的实现，并不是最优的。它会引发“herd effect”（羊群效应），降低获取锁的性能。一个更好的实现参见下面链接：

我们重新回到Flavio Junqueira对于fencing token的分析。Flavio Junqueira指出，fencing token机制本质上是要求客户端在每次访问一个共享资源的时候，在执行任何操作之前，先对资源进行某种形式的“标记”(mark)操作，这个“标记”能保证持有旧的锁的客户端请求（如果延迟到达了）无法操作资源。这种标记操作可以是很多形式，fencing token是其中比较典型的一个。
随后Flavio Junqueira提到用递增的epoch number（相当于Martin的fencing token）来保护共享资源。而对于分布式的资源，为了方便讨论，假设分布式资源是一个小型的多备份的数据存储(a small replicated data store)，执行写操作的时候需要向所有节点上写数据。最简单的做标记的方式，就是在对资源进行任何操作之前，先把epoch number标记到各个资源节点上去。这样，各个节点就保证了旧的（也就是小的）epoch number无法操作数据。
当然，这里再展开讨论下去可能就涉及到了这个数据存储服务的实现细节了。比如在实际系统中，可能为了容错，只要上面讲的标记和写入操作在多数节点上完成就算成功完成了（Flavio Junqueira并没有展开去讲）。在这里我们能看到的，最重要的，是这种标记操作如何起作用的方式。这有点类似于Paxos协议（Paxos协议要求每个proposal对应一个递增的数字，执行accept请求之前先执行prepare请求）。antirez提出的random token的方式显然不符合Flavio Junqueira对于“标记”操作的定义，因为它无法区分新的token和旧的token。只有递增的数字才能确保最终收敛到最新的操作结果上。
在这个分布式数据存储服务（共享资源）的例子中，客户端在标记完成之后执行写入操作的时候，存储服务的节点需要判断epoch number是不是最新，然后确定能不能执行写入操作。如果按照上一节我们的分析思路，这里的epoch判断和接下来的写入操作，是不是在一个原子操作里呢？根据Flavio Junqueira的相关描述，我们相信，应该是原子的。那么既然资源本身可以提供原子互斥操作了，那么分布式锁还有存在的意义吗？应该说有。客户端可以利用分布式锁有效地避免冲突，等待写入机会，这对于包含多个节点的分布式资源尤其有用（当然，是出于效率的原因）。

Chubby的分布式锁是怎样做fencing的？

提到分布式锁，就不能不提Google的Chubby。
Chubby是Google内部使用的分布式锁服务，有点类似于ZooKeeper，但也存在很多差异。Chubby对外公开的资料，主要是一篇论文，叫做“The Chubby lock service for loosely-coupled distributed systems”，下载地址如下：

另外，YouTube上有一个的讲Chubby的talk，也很不错，播放地址：

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保护的情况下进行操作，带来数据不一致的潜在风险。）

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

  • 锁的名字。
  • 锁的获取模式（排他锁还是共享锁）。
  • lock generation number（一个64bit的单调递增数字）。作用相当于fencing token或epoch number。

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

  • 调用Chubby提供的API，CheckSequencer()，将整个sequencer传进去进行检查。这个检查是为了保证客户端持有的锁在进行资源访问的时候仍然有效。
  • 将客户端传来的sequencer与资源服务器当前观察到的最新的sequencer进行对比检查。可以理解为与Martin描述的对于fencing token的检查类似。

当然，如果由于兼容的原因，资源服务本身不容易修改，那么Chubby还提供了一种机制：

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

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

关于时钟

在Martin与antirez的这场争论中，冲突最为严重的就是对于系统时钟的假设是不是合理的问题。Martin认为系统时钟难免会发生跳跃（这与分布式算法的异步模型相符），而antirez认为在实际中系统时钟可以保证不发生大的跳跃。
Martin对于这一分歧发表了如下看法（原话）：

So, fundamentally, this discussion boils down to whether it is reasonable to make timing assumptions for ensuring safety properties. I say no, Salvatore says yes — but that’s ok. Engineering discussions rarely have one right answer. （译文： 从根本上来说，这场讨论最后归结到了一个问题上：为了确保安全性而做出的记时假设到底是否合理。我认为不合理，而antirez认为合理 —— 但是这也没关系。工程问题的讨论很少只有一个正确答案。）

那么，在实际系统中，时钟到底是否可信呢？对此，Julia Evans专门写了一篇文章，“TIL: clock skew exists”，总结了很多跟时钟偏移有关的实际资料，并进行了分析。这篇文章地址：

Julia Evans在文章最后得出的结论是：

clock skew is real （时钟偏移在现实中是存在的）

Martin的事后总结

我们前面提到过，当各方的争论在激烈进行的时候，Martin几乎始终置身事外。但是Martin在这件事过去之后，把这个事件的前后经过总结成了一个很长的故事线。如果你想最全面地了解这个事件发生的前后经过，那么建议去读读Martin的这个总结：

在这个故事总结的最后，Martin写下了很多感性的评论：

For me, this is the most important point: I don’t care who is right or wrong in this debate — I care about learning from others’ work, so that we can avoid repeating old mistakes, and make things better in future. So much great work has already been done for us: by standing on the shoulders of giants, we can build better software. …… By all means, test ideas by arguing them and checking whether they stand up to scrutiny by others. That’s part of the learning process. But the goal should be to learn, not to convince others that you are right. Sometimes that just means to stop and think for a while. （译文： 对我来说最重要的一点在于：我并不在乎在这场辩论中谁对谁错 —— 我只关心从其他人的工作中学到的东西，以便我们能够避免重蹈覆辙，并让未来更加美好。前人已经为我们创造出了许多伟大的成果：站在巨人的肩膀上，我们得以构建更棒的软件。 …… 对于任何想法，务必要详加检验，通过论证以及检查它们是否经得住别人的详细审查。那是学习过程的一部分。但目标应该是为了获得知识，而不应该是为了说服别人相信你自己是对的。有时候，那只不过意味着停下来，好好地想一想。）

关于分布式锁的这场争论，我们已经完整地做了回顾和分析。
按照锁的两种用途，如果仅是为了效率(efficiency)，那么你可以自己选择你喜欢的一种分布式锁的实现。当然，你需要清楚地知道它在安全性上有哪些不足，以及它会带来什么后果。而如果你是为了正确性(correctness)，那么请慎之又慎。在本文的讨论中，我们在分布式锁的正确性上走得最远的地方，要数对于ZooKeeper分布式锁、单调递增的epoch number以及对分布式资源进行标记的分析了。请仔细审查相关的论证。
Martin为我们留下了不少疑问，尤其是他提出的fencing token机制。他在blog中提到，会在他的新书《Designing Data-Intensive Applications》的第8章和第9章再详加论述。目前，这本书尚在预售当中。我感觉，这会是一本值得一读的书，它不同于为了出名或赚钱而出版的那种短平快的书籍。可以看出作者在这本书上投入了巨大的精力。
最后，我相信，这个讨论还远没有结束。分布式锁(Distributed Locks)和相应的fencing方案，可以作为一个长期的课题，随着我们对分布式系统的认识逐渐增加，可以再来慢慢地思考它。思考它更深层的本质，以及它在理论上的证明。
（完）
感谢：
由衷地感谢几位朋友花了宝贵的时间对本文草稿所做的review：CacheCloud的作者付磊，快手的李伟博，阿里的李波。当然，文中如果还有错漏，由我本人负责^-^。
原创文章，转载请注明出处，并包含下面的二维码！否则拒绝转载！
本文链接：http://zhangtielei.com/posts/blog-redlock-reasoning-part2.html
欢迎关注我的个人微博：微博上搜索我的名字「张铁蕾」。
Redis 基础知识 - 图87

Redis6.0多线程重磅来袭

多线程实现

目前对于单线程 Redis 来说，性能瓶颈主要在于网络的 IO 消耗, 优化主要有两个方向:

  • 提高网络 IO 性能，典型的实现像使用 DPDK 来替代内核网络栈的方式
  • 使用多线程充分利用多核，典型的实现像 Memcached

多线程特性在社区也被反复提了很久后，Redis作者antirez终于在 Redis 6 加入多线程。
因为读写网络的read/write系统调用在Redis执行期间占用了大部分CPU时间，如果把网络读写做成多线程的方式对性能会有很大提升。现在已经实现了第一版，write side即回复客户端这部分已经完成了，并且去掉了主线程和IO线程之间的互斥锁，采用busy loop的形式来等待io线程工作结束，这部分能够有50%的性能提升，架构图如下：
Redis 基础知识 - 图88
Redis 的多线程部分只是用来处理网络数据的读写和协议解析，执行命令仍然是单线程。之所以这么设计是不想 Redis 因为多线程而变得复杂，需要去控制 key、lua、事务，LPUSH/LPOP 等等的并发问题。
多线程 IO 的读(请求)和写(响应)在实现流程是一样的，只是执行读还是写操作的差异。同时这些 IO 线程在同一时刻全部是读或者写，不会部分读或部分写的情况，所以下面以读流程作为例子。分析过程中只会覆盖核心逻辑而不是全部细节。如果想完全理解细节，建议看完之后再次看一次源码实现。
加入多线程 IO 之后，整体的读流程如下:

  • 主线程负责接收建连请求，读事件到来(收到请求)则放到一个全局等待读处理队列
  • 主线程处理完读事件之后，通过 RR(Round Robin) 将这些连接分配给这些 IO 线程，然后主线程忙等待(spinlock 的效果)状态
  • IO 线程将请求数据读取并解析完成(这里只是读数据和解析并不执行)
  • 主线程执行所有命令并清空整个请求等待读处理队列(执行部分串行)

上面的这个过程是完全无锁的，因为在 IO 线程处理的时主线程会等待全部的 IO 线程完成，所以不会出现data race的场景。