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

关系数据库并不直接支持交集计算操作，要计算两个集合的交集，除了需要对两个数据表执行合并（join）操作之外，还需要对合并的结果执行去重复（distinct）操作，最终导致交集操作的实现变得异常复杂。

第1章　引言

略。

第2章　简单动态字符串

SDS，simple dynamic string，简单动态字符串。

在Redis的数据库里面，包含字符串值的键值对（注意，键也是）在底层都是由SDS实现的。（在Redis源码里，C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，比如打印日志）

如：

redis> SET msg "hello world"
OK

Redis将在数据库中创建一个新的键值对，其中键是一个字符串对象，对象的底层实现是一个保存着字符串“msg”的SDS。值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS。

再如：

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

键是一个字符串对象，对象的底层实现是一个保存了字符串“fruits”的SDS。值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别由三个SDS实现：第一个SDS保存着字符串“apple”，第二个SDS保存着字符串“ba-nana”，第三个SDS保存着字符串“cherry”。

除了用来保存数据库中的字符串值之外，SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的。

SDS的定义

struct sdshdr {    
  int len;     // 记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
  int free;    // 记录buf数组中未使用字节的数量
  char buf[];  // 字节数组，用于保存字符串(最后一个字节为`\0`，是额外分配的，不算在len中，即当len为5、free为5时，buf的实际长度为11。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数)
};

SDS相比较C字符串的优势

常数复杂度获取字符串长度； # STRLEN
减少内存分配系统调用，并杜绝缓冲区溢出和内存泄露；通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略；空间预分配策略：
- （1）如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。
- （2）如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

惰性空间释放策略：

（1）当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。（SDS也提供了专门的API用来真正释放空间）

二进制安全；所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样，所以SDS不仅仅可以保存文本数据。（因为SDS使用len属性的值而不是空字符来判断字符串是否结束）
兼容部分C字符串函数；

SDS API

略。

第3章　链表

Redis中除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，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;

Redis链表的特性

双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）。
无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。
多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

链表API

略。

第4章　字典

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

字典的实现

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

// 哈希表
typedef struct dictht {    
  dictEntry **table;    // 哈希表数组，每个dictEntry都保存着一个键值对
  unsigned long size;   // 哈希表大小  
  unsigned long sizemask;  // 哈希表大小掩码，用于和哈希值一起计算哈希索引（总是等于size-1）
  unsigned long used;  // 该哈希表已有节点的数量
} dictht;

// 哈希表节点
typedef struct dictEntry {
  void *key;// 键 

  union{  // 值      
    void *val;        
    uint64_tu64;        
    int64_ts64;    
  } v;      

  struct dictEntry *next; // 指向下个哈希表节点，形成链表（解决键冲突）
} dictEntry;

// 字典
typedef struct dict {    
  dictType *type;   // 类型特定函数
  void *privdata;   // 私有数据
  dictht ht[2];     // 哈希表，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
  in trehashidx;    // rehash索引，当rehash不在进行时，值为-1
} dict;

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。而privdata属性则保存了需要传给那些类型特定函数的可选参数。

typedef struct dictType {    
  unsigned int (*hashFunction)(const void *key);  // 计算哈希值的函数  
  void *(*keyDup)(void *privdata, const void *key);  // 复制键的函数  
  void *(*valDup)(void *privdata, const void *obj);   // 复制值的函数 
  int (*keyCompare)(void *privdata, const void *key1, const void *key2);   // 对比键的函数 
  void (*keyDestructor)(void *privdata, void *key);  // 销毁键的函数  
  void (*valDestructor)(void *privdata, void *obj);  // 销毁值的函数
} dictType;

哈希算法

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

Redis使用MurmurHash算法来计算键的哈希值，这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，称这些键发生了冲突。Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，以此解决键冲突的问题。

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

rehash

当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。这可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）。
将保存在ht[0]中的所有键值对rehash到ht[1]上面：re-hash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

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

服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。负载因子= 哈希表已保存节点数量/ 哈希表大小另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]。在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。（例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找。在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作）

字典API

略。

第5章　跳跃表

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

Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

跳跃表节点

typedef struct zskiplistNode {  

  struct zskiplistLevel {           // 层      
    struct zskiplistNode *forward;  // 前进指针    
    unsigned int span;              // 跨度 (记录两个节点之间的距离)
  } level[];    

  struct zskiplistNode *backward;  // 后退指针(每次只能后退至前一个节点)
  double score;                    // 分值(double类型的浮点数,排序的依据)
  robj *obj;                       // 成员对象（唯一性）
} zskiplistNode;

跳跃表

typedef struct zskiplist {    
  structz skiplistNode *header, *tail;  // 表头节点和表尾节点
  unsigned long length;   // 表中节点的数量
  int level;              // 表中层数最大的节点的层数（1至32之间的随机数）
} zskiplist;

跳跃表API

略。

第6章　整数集合

当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为底层实现。

redis> SADD numbers 1 3 5 7 9
(integer) 5
redis> OBJECT ENCODING numbers
"intset"

整数集合的实现

typedef struct intset {    
  uint32_t encoding;  // 编码方式  
  uint32_t length;    // 集合包含的元素数量 
  int8_t contents[];  // 保存元素的数组，按值大小有序排列且不重复
} intset;

升级

虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值。每当要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。

升级过程（主要就是内存的重新分配），详略。

升级的好处：

提升整数集合的灵活性：可以随意地将int16_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误；
尽可能地节约内存：升级操作只会在有需要的时候进行；

降级

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

整数集合API

略。

第7章　压缩列表

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

压缩列表的构成

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

压缩列表节点的构成

略。

压缩列表API

添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作。连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O（N），所以连锁更新的最坏复杂度为O（N2）。但这种操作出现的几率并不高，需要当前的内存分布情况恰好满足一定的条件时才可能触发。

第8章　对象

Redis并没有直接使用简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种如上的数据结构。

对象的类型与编码

Redis使用对象来表示数据库中的键和值，每当在Redis的数据库中新创建一个键值对时，至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

typedef struct redisObject {    
  unsigned type:4;     // 类型(字符串、列表、哈希、集合、有序集合)
  unsigned encoding:4; // 编码(即底层数据结构的实际类型)
  void *ptr;           // 指向底层实现数据结构的指针
  // ...
} robj;

键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种。

字符串对象

字符串对象的编码可以是int、raw或者embstr，取决于实际存储的内容。

SET number 10086  # int
SET story "Long, long ago there lived a king ..."  # raw
SET msg "hello"   # embstr

注意：可以用long double类型表示的浮点数在Redis中也是作为字符串值来保存的。

redis> SET pi 3.14
OK

redis> OBJECT ENCODING pi
"embstr"

redis> INCRBYFLOAT pi 2.0
"5.14"

redis> OBJECT ENCODING pi
"embstr"

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象。

redis> SET number 10086  # int
redis> APPEND number " is a good number!"  # raw

embstr编码的字符串对象实际上是只读的。当对embstr编码的字符串对象执行任何修改命令时（比如APPEND），程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。

列表对象

列表对象的编码可以是ziplist或者linkedlist。

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

列表对象保存的所有字符串元素的长度都小于64字节；
列表对象保存的元素数量小于512个；不能满足这两个条件的列表对象需要使用linkedlist编码。当然，这两个限制在Redis配置文件中是可以修改的list-max-ziplist-value，list-max-ziplist-entries。

当条件不满足时，ziplist编码的对象会自动转换为linkedlist编码。

哈希对象

哈希对象的编码可以是ziplist或者hashtable。

ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾，因此保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。

hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存。

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

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
哈希对象保存的键值对数量小于512个；不能满足这两个条件的哈希对象需要使用hashtable编码。限制条件可以在配置文件中修改（hash-max-ziplist-value，hash-max-ziplist-entries）。当条件不满足时，ziplist编码的对象会自动转换为hashtable编码。

集合对象

集合对象的编码可以是intset或者hashtable。 intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。，hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。

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

集合对象保存的所有元素都是整数值；
集合对象保存的元素数量不超过512个。（可以配置set-max-intset-entries）当条件不满足时，intset编码的对象会自动转换为hashtable编码。

有序集合对象

有序集合的编码可以是ziplist或者skiplist。

ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。压缩列表内的集合元素按分值从小到大进行排序。

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

有序集合保存的元素数量小于128个； # zset-max-ziplist-entries
有序集合保存的所有元素成员的长度都小于64字节； # zset-max-ziplist-value 当条件不满足时，ziplist编码的对象会自动转换为skiplist编码。

类型检查与命令多态

为了确保只有指定类型的键可以执行某些特定的命令，在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令。（redisObject结构的type属性）

Redis除了会根据值对象的类型来判断键是否能够执行指定命令之外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。

内存回收

Redis在自己的对象系统中构建了一个引用计数（redisObject结构的refcount属性）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

对象共享

对象的引用计数属性还带有对象共享的作用。在Redis中，让多个键共享同一个值对象需要执行以下两个步骤：

将数据库键的值指针指向一个现有的值对象；
将被共享的值对象的引用计数增一。

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

查看引用计数：

redis> SET A 100
OK

redis> OBJECT REFCOUNT A
(integer) 2

redis> SET B 100
OK

redis> OBJECT REFCOUNT A
(integer) 3

redis> OBJECT REFCOUNT B
(integer) 3

尽管共享更复杂的对象可以节约更多的内存，但受到CPU时间的限制，Redis只对包含整数值的字符串对象进行共享。

对象的空转时长

redisObject结构的lru属性记录了对象最后一次被命令程序访问的时间。

OBJECT IDLETIME命令可以打印出给定键的空转时长，这个命令在访问键的值对象时，不会修改值对象的lru属性。

如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。

第9章　数据库

服务器中的数据库

所有数据库都保存在服务器状态redisServer结构的db数组中：

struct redisServer {      // ...      redisDb *db;  // 一个数组，保存着服务器中的所有数据库   // ...};

可以通过配置指定需要创建的数据库的数量。

切换数据库

客户端状态redisClient结构的db属性记录了客户端当前的目标数据库：

typedef struct redisClient {
  // ...
  redisDb *db;  // 记录客户端当前正在使用的数据库（指向服务器中的数据库）
  // ...
} redisClient;

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

数据库键空间

Redis是一个键值对（key-value pair）数据库服务器，redisDb结构的dict字典保存了数据库中的所有键值对，这个字典也称为键空间（key space）：

typedef struct redisDb {    
  // ...    
  dict *dict;  // 数据库键空间，保存着数据库中的所有键值对   
  // ...
} redisDb;

键空间的键也就是数据库的键，每个键都是一个字符串对象。键空间的值也就是数据库的值，每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种Redis对象。

所有针对数据库的操作实际上都是通过对键空间字典进行操作来实现的：

添加新键：实际上就是将一个新键值对添加到键空间字典里面，其中键为字符串对象，而值则为任意一种类型的Redis对象。
删除键：在键空间里面删除键所对应的键值对对象。
更新键：对键空间里面键所对应的值对象进行更新，根据值对象的类型不同，更新的具体方法也会有所不同。
对键取值：在键空间中取出键所对应的值对象，根据值对象的类型不同，具体的取值方法也会有所不同。
FLUSHDB：删除键空间中的所有键值对。
RANDOMKEY：在键空间中随机返回一个键。 DBSIZE、EXISTS、RENAME、KEYS等等，略。

读写键空间时的维护操作

当使用Redis命令对数据库进行读写时，服务器不仅会对键空间执行指定的读写操作，还会执行一些额外的维护操作，其中包括：

在读取一个键之后，服务器会根据键是否存在来更新服务器的键空间命中（hit）次数或键空间不命中（miss）次数。
在读取一个键之后，服务器会更新键的LRU（最后一次使用）时间，这个值可以用于计算键的闲置时间。
如果服务器在读取一个键时发现该键已经过期，那么服务器会先删除这个过期键，然后才执行余下的其他操作。
如果有客户端使用WATCH命令监视了某个键，那么服务器在对被监视的键进行修改之后，会将这个键标记为脏（dirty），从而让事务程序注意到这个键已经被修改过。
服务器每次修改一个键之后，都会对脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作。
如果服务器开启了数据库通知功能，那么在对键进行修改之后，服务器将按配置发送相应的数据库通知。

设置键的生存时间或过期时间

Redis有四个不同的命令可以用于设置键的生存时间（键可以存在多久）或过期时间（键什么时候会被删除）：

EXPIRE [key] [ttl]命令用于将键key的生存时间设置为ttl秒。
PEXPIRE [key] [ttl]命令用于将键key的生存时间设置为ttl毫秒。
EXPIREAT [key] [timestamp]命令用于将键key的过期时间设置为timestamp所指定的秒数时间戳。
PEXPIREAT [key] [timestamp]命令用于将键key的过期时间设置为timestamp所指定的毫秒数时间戳。实际上EXPIRE、PEXPIRE、EXPIREAT三个命令都是使用PEXPIREAT命令来实现的：无论客户端执行的是以上四个命令中的哪一个，经过转换之后，最终的执行效果都和执行PEXPIREAT命令一样。

redisDb结构的expires字典保存了数据库中所有键的过期时间（一个毫秒精度的UNIX时间戳），这个字典也称为过期字典。通过过期字典，程序可以用以下步骤检查一个给定键是否过期：

检查给定键是否存在于过期字典：如果存在，那么取得键的过期时间。
检查当前UNIX时间戳是否大于键的过期时间：如果是的话，那么键已经过期；否则的话，键未过期。

PERSIST命令可以移除一个键的过期时间。TTL命令以秒为单位返回键的剩余生存时间，而PTTL命令则以毫秒为单位返回键的剩余生存时间

过期键删除策略

三种不同的删除策略：

定时删除：在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键的过期时间来临时，立即执行对键的删除操作。定时删除占用太多CPU时间，影响服务器的响应时间和吞吐量。
惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。惰性删除浪费太多内存，有内存泄漏的危险。
定期删除：每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。至于要删除多少过期键，以及要检查多少个数据库，则由算法决定。服务器必须根据情况，合理地设置删除操作的执行时长和执行频率。

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

所有读写数据库的Redis命令在执行之前都会调用expireIfNeeded函数对输入键进行检查，它可以在命令真正执行之前，过滤掉过期的输入键，从而避免命令接触到过期键。

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

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

在执行SAVE命令或者BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，已过期的键不会被保存到新创建的RDB文件中。在启动Redis服务器时，如果服务器开启了RDB功能，那么服务器将对RDB文件进行载入：

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

当服务器以AOF持久化模式运行时，如果数据库中的某个键已经过期，但它还没有被惰性删除或者定期删除，那么AOF文件不会因为这个过期键而产生任何影响。当过期键被惰性删除或者定期删除之后，程序会向AOF文件追加（append）一条DEL命令，来显式地记录该键已被删除。

在执行AOF重写的过程中，程序会对数据库中的键进行检查，已过期的键不会被保存到重写后的AOF文件中。

复制

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

主服务器在删除一个过期键之后，会显式地向所有从服务器发送一个DEL命令，告知从服务器删除这个过期键。
从服务器在执行客户端发送的读命令时，即使碰到过期键也不会将过期键删除，而是继续像处理未过期的键一样来处理过期键。 3.从服务器只有在接到主服务器发来的DEL命令之后，才会删除过期键。通过由主服务器来控制从服务器统一地删除过期键，有利于保证主从服务器数据的一致性。

1:副本不主动删除，等待主节点del命令同步
2:副本使用逻辑时钟判断key不存在，仅用于不违反一致性的读取操作
3:lua脚本执行时，主节点时间冻结，防止执行中状态改变；并且以需要保证在数据集中具有相同效果的方式将相同的脚本发送给副本。

数据库通知

这个功能可以让客户端通过订阅给定的频道或者模式，来获知数据库中键的变化，以及数据库中命令的执行情况。

关注“某个键执行了什么命令”的通知称为键空间通知（key-space notification），除此之外，还有另一类称为键事件通知（key-event notification）的通知，它们关注的是“某个命令被什么键执行了”。

服务器配置的notify-keyspace-events选项决定了服务器所发送通知的类型。

详略。

第10章　RDB持久化

RDB持久化既可以手动执行，也可以根据服务器配置选项定期执行，该功能可以将某个时间点上的数据库状态保存到一个RDB文件中。Redis服务器就可以用它来还原数据库状态。

SAVE命令会阻塞Redis服务器进程，直到RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何命令请求。客户端发送的所有命令请求都会被拒绝。

BGSAVE命令会派生出一个子进程，然后由子进程负责创建RDB文件，服务器进程（父进程）继续处理命令请求。

RDB文件的载入工作是在服务器启动时自动执行的，所以Redis并没有专门用于载入RDB文件的命令，只要Redis服务器在启动时检测到RDB文件存在，它就会自动载入RDB文件。

因为AOF文件的更新频率通常比RDB文件的更新频率高，所以如果服务器开启了AOF持久化功能，那么服务器会优先使用AOF文件来还原数据库状态。只有在AOF持久化功能处于关闭状态时，服务器才会使用RDB文件来还原数据库状态。

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

在BGSAVE命令执行期间，客户端发送的SAVE命令会被服务器拒绝，服务器禁止SAVE命令和BGSAVE命令同时执行。（防止竞争）
在BGSAVE命令执行期间，客户端发送的BGSAVE命令会被服务器拒绝。（防止竞争）
BGREWRITEAOF和BGSAVE两个命令不能同时执行。（性能原因）

RDB文件载入时的服务器状态

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

自动间隔性保存

Redis允许用户通过设置服务器配置的save选项，让服务器每隔一段时间自动执行一次BGSAVE命令。用户可以通过save选项设置多个保存条件，但只要其中任意一个条件被满足，服务器就会执行BGSAVE命令。默认配置如下：

save 900 1     # 服务器在900秒之内，对数据库进行了至少1次修改
save 300 10    # 服务器在300秒之内，对数据库进行了至少10次修改
save 60 10000  # 服务器在60秒之内，对数据库进行了至少10000次修改

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

RDB文件结构

REDIS db_version database EOF check_sum

详略。

分析RDB文件

打印RDB文件：

redis> FLUSHALLOKredis> SET MSG "HELLO"OKredis> SAVEOK$ od -c dump.rdb0000000   R   E  D  I  S  0   0   0  6 376  \0 \0 003  M   S  G0000020 005   H  E  L  L  O 377 207  z  =  304  f   T  L 3430000037

Redis本身带有RDB文件检查工具redis-check-dump。

详略。

第11章　AOF持久化

与RDB持久化通过保存数据库中的键值对来记录数据库状态不同，AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的。被写入AOF文件的所有命令都是以Redis的命令请求协议格式保存的。

服务器在启动时，可以通过载入和执行AOF文件中保存的命令来还原服务器关闭之前的数据库状态。

AOF持久化的实现

当AOF持久化功能处于打开状态时，服务器在执行完一个写命令之后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
Redis的服务器进程就是一个事件循环（loop），这个循环中的文件事件负责接收客户端的命令请求，以及向客户端发送命令回复，而时间事件则负责执行像serverCron函数这样需要定时运行的函数。在服务器每次结束一个事件循环之前，它都会调用flushAppendOnlyFile函数，考虑是否需要将aof_buf缓冲区中的内容写入和保存到AOF文件里面。

AOF文件的载入与数据还原

Redis读取AOF文件并还原数据库状态的详细步骤如下：

创建一个不带网络连接的伪客户端（fake client）（因为Redis的命令只能在客户端上下文中执行）；
从AOF文件中分析并读取出一条写命令。
从AOF文件中分析并读取出一条写命令。
一直执行步骤2和步骤3，直到AOF文件中的所有写命令都被处理完毕为止。

AOF重写

体积过大的AOF文件很可能对Redis服务器、甚至整个宿主计算机造成影响，并且AOF文件的体积越大，使用AOF文件来进行数据还原所需的时间就越多。

为了解决AOF文件体积膨胀的问题，Redis提供了AOF文件重写（rewrite）功能。通过该功能，Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件，新旧两个AOF文件所保存的数据库状态相同，但新AOF文件不会包含任何浪费空间的冗余命令，所以新AOF文件的体积通常会比旧AOF文件的体积要小得多。

从数据库中读取键现在的值，然后用一条命令去记录键值对，代替之前记录这个键值对的多条命令，这就是AOF重写功能的实现原理。（比如连续6条RPUSH命令会被整合成1条）

在实际中，为了避免在执行命令时造成客户端输入缓冲区溢出，重写程序在处理列表、哈希表、集合、有序集合这四种可能会带有多个元素的键时，会先检查键所包含的元素数量，如果元素的数量超过了redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值，那么重写程序将使用多条命令来记录键的值，而不单单使用一条命令。

BGREWRITEAOF命令的实现原理

使用子进程进行AOF重写，在这同时主进程仍然在接受并处理客户端的请求。为了解决数据不一致问题，Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程之后开始使用，当Redis服务器执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。在子进程执行AOF重写期间，服务器进程需要执行以下三个工作：

执行客户端发来的命令。
将执行后的写命令追加到AOF缓冲区。
将执行后的写命令追加到AOF重写缓冲区。这样一来可以保证： 1.AOF缓冲区的内容会定期被写入和同步到AOF文件，对现有AOF文件的处理工作会如常进行。 2.从创建子进程开始，服务器执行的所有写命令都会被记录到AOF重写缓冲区里面。当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接到该信号之后，会调用一个信号处理函数，并执行以下工作：
将AOF重写缓冲区中的所有内容写入到新AOF文件中，这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致。
对新的AOF文件进行改名，原子地（atomic）覆盖现有的AOF文件，完成新旧两个AOF文件的替换。在整个AOF后台重写过程中，只有信号处理函数执行时会对服务器进程（父进程）造成阻塞，在其他时候，AOF后台重写都不会阻塞父进程，这将AOF重写对服务器性能造成的影响降到了最低。

第12章　事件

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

文件事件（file event）：Redis服务器通过套接字与客户端（或者其他Redis服务器）进行连接，而文件事件就是服务器对套接字操作的抽象。服务器与客户端（或者其他服务器）的通信会产生相应的文件事件，而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
时间事件（time event）：Redis服务器中的一些操作（比如serverCron函数）需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象。

文件事件

文件事件处理器使用I/O多路复用（multiplexing）程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
当被监听的套接字准备好执行连接应答（accept）、读取（read）、写入（write）、关闭（close）等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

API等，详略。

时间事件

Redis的时间事件分为以下两类：

定时事件：让一段程序在指定的时间之后执行一次。比如说，让程序X在当前时间的30毫秒之后执行一次。
周期性事件：让一段程序每隔指定时间就执行一次。比如说，让程序Y每隔30毫秒就执行一次。

服务器将所有时间事件都放在一个无序链表中，每当时间事件执行器运行时，它就遍历整个链表，查找所有已到达的时间事件，并调用相应的事件处理器。

API等，详略。

serverCron函数的主要工作

更新服务器的各类统计信息，比如时间、内存占用、数据库占用情况等。
清理数据库中的过期键值对。
关闭和清理连接失效的客户端。
尝试进行AOF或RDB持久化操作。
如果服务器是主服务器，那么对从服务器进行定期同步。
如果处于集群模式，对集群进行定期同步和连接测试。

用户可以通过修改hz选项来调整server-Cron的每秒执行次数。

事件的调度与执行

略。

第13章　客户端

通过使用由I/O多路复用技术实现的文件事件处理器，Re-dis服务器使用单线程单进程的方式来处理命令请求，并与多个客户端进行网络通信。

struct redisServer {      // ...      list *clients;  // 一个链表，保存了所有客户端状态  // ...};

客户端属性

套接字描述符：客户端状态的fd属性记录了客户端正在使用的套接字描述符；
名字：使用CLIENT setname命令可以为客户端设置一个名字(默认没有名字)；
标志：客户端的标志属性flags记录了客户端的角色（主、从、伪客户端），以及客户端目前所处的状态（阻塞、正在执行事务等）；
输入缓冲区：用于保存客户端发送的命令请求；输入缓冲区的大小会根据输入内容动态地缩小或者扩大，但它的最大大小不能超过1GB，否则服务器将关闭这个客户端。
命令与命令参数；
命令的实现函数：当程序在命令表中成功找到argv[0]所对应的redisCommand结构时，它会将客户端状态的cmd指针指向这个结构；之后，服务器就可以使用cmd属性所指向的redisCom-mand结构，以及argv、argc属性中保存的命令参数信息，调用命令实现函数，执行客户端指定的命令。
输出缓冲区：执行命令所得的命令回复会被保存在客户端状态的输出缓冲区里面，每个客户端都有两个输出缓冲区可用，一个缓冲区的大小是固定的（保存长度比较小的回复），另一个缓冲区的大小是可变的（保存长度比较大的回复）；
身份验证：用于记录客户端是否通过了身份验证；
时间：创建客户端的时间、与服务器最后一次进行互动的时间、输出缓冲区第一次到达软性限制（soft limit）的时间；

客户端的创建与关闭

如果客户端是通过网络连接与服务器进行连接的普通客户端，那么在客户端使用connect函数连接到服务器时，服务器就会调用连接事件处理器，为客户端创建相应的客户端状态，并将这个新的客户端状态添加到服务器状态结构clients链表的末尾。

一个普通客户端可以因为多种原因而被关闭：

客户端进程退出或者被杀死;
向服务器发送了带有不符合协议格式的命令请求;
成为了CLIENT KILL命令的目标;
当客户端的空转时间超过timeout选项设置的值时;(客户端本身是主从服务器、或者正在执行阻塞、订阅命令除外)
客户端发送的命令请求的大小超过了输入缓冲区的限制大小；
如果要发送给客户端的命令回复的大小超过了输出缓冲区的限制大小，那么这个客户端会被服务器关闭。

Lua脚本的伪客户端

服务器会在初始化时创建负责执行Lua脚本中包含的Redis命令的伪客户端，并将这个伪客户端关联在服务器状态结构的lua_client属性中。只有服务器被关闭时，这个客户端才会被关闭。详略。

AOF文件的伪客户端

服务器在载入AOF文件时，会创建用于执行AOF文件包含的Redis命令的伪客户端，并在载入完成之后，关闭这个伪客户端。

第14章　服务器

命令请求的执行过程

当用户在客户端中键入一个命令请求时，客户端会将这个命令请求转换成协议格式，然后通过连接到服务器的套接字，将协议格式的命令请求发送给服务器；
服务器读取套接字中协议格式的命令请求，并将其保存到客户端状态的输入缓冲区里面。
对输入缓冲区中的命令请求进行分析，提取出命令请求中包含的命令参数，以及命令参数的个数，然后分别将参数和参数个数保存到客户端状态的argv属性和argc属性里面。（命令表使用的是大小写无关的查找算法）
调用命令执行器，执行客户端指定的命令。
要执行一些后续工作；（记日志、写AOF缓冲区、传播给从服务器等，取决于具体的配置）
将命令回复发送给客户端，清空客户端状态的输出缓冲区，为处理下一个命令请求做好准备；
当客户端接收到协议格式的命令回复之后，它会将这些回复转换成人类可读的格式，并打印给用户观看；

serverCron函数

serverCron函数默认每隔100毫秒执行一次，这个函数负责管理服务器的资源，并保持服务器自身的良好运转。

更新服务器时间缓存；
更新LRU时钟；
更新服务器每秒执行命令次数；
更新服务器内存峰值记录；
处理SIGTERM信号；
管理客户端资源；
管理数据库资源；
执行被延迟的BGREWRITEAOF；
检查持久化操作的运行状态；
将AOF缓冲区中的内容写入AOF文件；
关闭异步客户端；
增加cronloops计数器的值；（记录了serverCron函数执行的次数）

初始化服务器

一个Redis服务器从启动到能够接受客户端的命令请求，需要经过一系列的初始化和设置过程：

初始化服务器状态结构（initServerConfig）：创建一个struct redisServer类型的实例变量server作为服务器的状态，并为结构中的各个属性设置默认值。
- （1）设置服务器的运行ID。
- （2）设置服务器的默认运行频率。
- （3）设置服务器的默认配置文件路径。
- （4）设置服务器的运行架构。
- （5）设置服务器的默认端口号。
- （6）设置服务器的默认RDB持久化条件和AOF持久化条件。
- （7）初始化服务器的LRU时钟。
- （8）创建命令表。
载入配置选项：在启动服务器时，用户可以通过给定配置参数或者指定配置文件来修改服务器的默认配置。
初始化服务器数据结构（initServer）：
- （1）server.clients链表；
- （2）server.db数组；
- （3）用于保存频道订阅信息的server.pubsub_channels字典，以及用于保存模式订阅信息的server.pubsub_patterns链表。
- （4）用于执行Lua脚本的Lua环境server.lua。
- （5）用于保存慢查询日志的server.slowlog属性。
为服务器设置进程信号处理器。
创建共享对象：这些对象包含Redis服务器经常用到的一些值，比如包含”OK”回复的字符串对象，包含”ERR”回复的字符串对象，包含整数1到10000的字符串对象等等；
打开服务器的监听端口，并为监听套接字关联连接应答事件处理器，等待服务器正式运行时接受客户端的连接。
为serverCron函数创建时间事件，等待服务器正式运行时执行serverCron函数。
如果AOF持久化功能已经打开，那么打开现有的AOF文件，如果AOF文件不存在，那么创建并打开一个新的AOF文件，为AOF写入做好准备。
初始化服务器的后台I/O模块（bio），为将来的I/O操作做好准备。
服务器将用ASCII字符在日志中打印出Redis的图标，以及Redis的版本号信息；

还原数据库状态

在完成了对服务器状态server变量的初始化之后，服务器需要载入RDB文件或者AOF文件，并根据文件记录的内容来还原服务器的数据库状态。如果服务器启用了AOF持久化功能，那么服务器使用AOF文件来还原数据库状态。如果服务器没有启用AOF持久化功能，那么服务器使用RDB文件来还原数据库状态。

[5244] 21 Nov 22:43:49.084 * DB loaded from disk: 0.068 seconds

执行事件循环

[5244] 21 Nov 22:43:49.084 * The server is now ready to accept connections on port 6379

服务器现在开始可以接受客户端的连接请求，并处理客户端发来的命令请求了。

第15章　复制

可以通过执行SLAVEOF命令或者设置slaveof选项，让一个服务器去复制（replicate）另一个服务器。如：

127.0.0.1:12345> SLAVEOF 127.0.0.1 6379OK

进行复制中的主从服务器双方的数据库将保存相同的数据。

旧版复制功能的实现

Redis的复制功能分为同步（sync）和命令传播（commandpropagate）两个操作。

同步：用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。当客户端向从服务器发送SLAVEOF命令，要求从服务器复制主服务器时，从服务器首先需要执行同步操作，将从服务器的数据库状态更新至主服务器当前所处的数据库状态。具体方式是，主服务器执行BGSAVE生成rdb文件，同时启动缓冲区接收命令，然后将rdb文件传给从服务器，从服务器使用rdb进行同步，然后再执行缓冲区中剩余的命令。
命令传播：在执行同步后，当主服务器的数据库状态被修改，导致主从服务器的数据库状态出现不一致时，让主从服务器的数据库重新回到一致状态。主服务器会将自己执行的写命令，也即是造成主从服务器不一致的那条写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态。

旧版复制功能的缺陷

对于断线后重复制来说，旧版复制功能虽然也能让主从服务器重新回到一致状态（重新执行SYNC进行全量复制，而不是差量复制，即使只是瞬间断开），但效率却非常低。

新版复制功能的实现

Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作。PSYNC命令具有完整重同步（full resynchronization）和部分重同步（partial resynchronization）两种模式：

完整重同步用于处理初次复制情况：完整重同步的执行步骤和SYNC命令的执行步骤基本一样，它们都是通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步。
部分重同步用于处理断线后重复制情况：当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令，就可以将数据库更新至主服务器当前所处的状态。

执行SYNC命令需要生成、传送和载入整个RDB文件，而部分重同步只需要将从服务器缺少的写命令发送给从服务器执行就可以了。

部分重同步的实现

部分重同步功能由以下三个部分构成：

主服务器的复制偏移量（replication offset）和从服务器的复制偏移量。主服务器和从服务器会分别维护一个复制偏移量（记录发送、收到的字节数）。通过对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态。
主服务器的复制积压缓冲区（replication backlog）。
由主服务器维护的一个固定长度先进先出（FIFO）队列，默认大小为1MB。当主服务器进行命令传播时，它不仅会将写命令发送给所有从服务器，还会将写命令入队到复制积压缓冲区里面。
服务器的运行ID（run ID）。每个Redis服务器，不论主服务器还是从服务，都会有自己的运行ID。主服务器会在第一次同步时将自己的ID发送给从服务器，而从服务器则会在断线重连时用其进行判断，如果主服务器ID不一致，则进行全量复制。

复制积压缓冲区的最小大小可以根据公式second*write_size_per_second来估算，其中second为从服务器断线后重新连接上主服务器所需的平均时间（以秒计算）。

PSYNC命令的实现

从服务器在开始一次新的复制时将向主服务器发送PSYNC ? -1命令，主动请求主服务器进行完整重同步。

如果从服务器已经复制过某个主服务器，那么从服务器在开始一次新的复制时将向主服务器发送PSYNC [runid] [offset]命令：其中runid是上一次复制的主服务器的运行ID，而offset则是从服务器当前的复制偏移量，接收到这个命令的主服务器会通过这两个参数来判断应该对从服务器执行哪种同步操作。

详略。

复制的实现

具体步骤如下：

设置主服务器的地址和端口；
建立套接字连接；
发送PING命令（检查套接字的读写状态是否正常），主服务器应该返回PONG；
身份验证；
向主服务器发送从服务器的监听端口号；
同步(从服务器将向主服务器发送PSYNC命令)；
命令传播；

心跳检测

从服务器默认会以每秒一次的频率，向主服务器发送命令：

REPLCONF ACK [replication_offset]

主要有三个作用：

检测主从服务器的网络连接状态。
辅助实现min-slaves选项（Redis的min-slaves-to-write和min-slaves-max-lag两个选项可以防止主服务器在不安全的情况下执行写命令）。
检测命令丢失。详略。

第16章　Sentinel

Sentinel（哨岗、哨兵）是Redis的高可用性解决方案：由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器，以及这些主服务器属下的所有从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务器属下的某个从服务器升级为新的主服务器，然后由新的主服务器代替已下线的主服务器继续处理命令请求。

启动并初始化Sentinel

$ redis-sentinel /path/to/your/sentinel.conf

或者：

$ redis-server /path/to/your/sentinel.conf --sentinel

Sentinel本质上只是一个运行在特殊模式下的Redis服务器。（默认26379端口）

普通服务器在初始化时会通过载入RDB文件或者AOF文件来还原数据库状态，但是因为Sentinel并不使用数据库，所以初始化Sentinel时就不会载入RDB文件或者AOF文件。

在Sentinel模式下，Redis服务器不能执行诸如SET、DBSIZE、EVAL等等这些命令，因为服务器根本没有在命令表中载入这些命令。PING、SENTINEL、INFO、SUBSCRIBE、UNSUBSCRIBE、PSUBSCRIBE和PUNSUBSCRIBE这七个命令就是客户端可以对Sentinel执行的全部命令。

获取主服务器信息

Sentinel默认会以每十秒一次的频率，通过命令连接向被监视的主服务器发送INFO命令，并通过分析INFO命令的回复来获取主服务器的当前信息。

获取从服务器信息

当Sentinel发现主服务器有新的从服务器出现时，Sentinel除了会为这个新的从服务器创建相应的实例结构之外，Sentinel还会创建连接到从服务器的命令连接和订阅连接。

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

在默认情况下，Sentinel会以每两秒一次的频率，通过命令连接向所有被监视的主服务器和从服务器发送以下格式的命令：

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

详略。

接收来自主服务器和从服务器的频道信息

对于每个与Sentinel连接的服务器，Sentinel既通过命令连接向服务器的sentinel:hello频道发送信息，又通过订阅连接从服务器的sentinel:hello频道接收信息。详略。

检测主观下线状态

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

Sentinel配置文件中的down-after-milliseconds选项指定了Sentinel判断实例进入主观下线所需的时间长度。

检查客观下线状态

当Sentinel将一个主服务器判断为主观下线之后，为了确认这个主服务器是否真的下线了，它会向同样监视这一主服务器的其他Sentinel进行询问，看它们是否也认为主服务器已经进入了下线状态（可以是主观下线或者客观下线）。当Sentinel从其他Sentinel那里接收到足够数量的已下线判断之后，Sentinel就会将从服务器判定为客观下线，并对主服务器执行故障转移操作。

选举领头Sentinel

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

故障转移

领头Sentinel对已下线的主服务器执行故障转移操作，该操作包含以下三个步骤：

在已下线主服务器属下的所有从服务器里面，挑选出一个从服务器，并将其转换为主服务器。
让已下线主服务器属下的所有从服务器改为复制新的主服务器。
将已下线主服务器设置为新的主服务器的从服务器，当这个旧的主服务器重新上线时，它就会成为新的主服务器的从服务器。详细过程，略。

第17章　集群

集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能。

节点

一个Redis集群通常由多个节点（node）组成，连接各个节点的工作可以使用CLUSTER MEET命令来完成：

CLUSTER MEET [ip] [port]

向一个节点node发送CLUSTER MEET命令，可以让node节点与ip和port所指定的节点进行握手（handshake），当握手成功时，node节点就会将ip和port所指定的节点添加到node节点当前所在的集群中。

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

每个节点都会使用一个clusterNode结构来记录自己的状态，并为集群中的所有其他节点（包括主节点和从节点）都创建一个相应的clusterNode结构，以此来记录其他节点的状态。详细数据结构，略。

CLUSTER MEET命令的实现

通过向节点A发送CLUSTER MEET命令，客户端可以让接收命令的节点A将另一个节点B添加到节点A当前所在的集群里面。

之后，节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点，让其他节点也与节点B进行握手，最终，经过一段时间之后，节点B会被集群中的所有节点认识。详略。

槽指派

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

通过向节点发送CLUSTER ADDSLOTS命令，可以将一个或多个槽指派（assign）给节点负责。将槽0至槽5000指派给节点7000负责：

127.0.0.1:7000> CLUSTER ADDSLOTS 0 1 2 3 4 ... 5000
OK

将槽5001至槽10000指派给节点7001负责：

127.0.0.1:7001> CLUSTER ADDSLOTS 5001 5002 5003 5004 ... 10000
OK

将槽10001至槽16383指派给7002负责：

127.0.0.1:7002> CLUSTER ADDSLOTS 10001 10002 10003 10004 ... 16383
OK

当以上三个CLUSTER ADDSLOTS命令都执行完毕之后，数据库中的16384个槽都已经被指派给了相应的节点，集群进入上线状态：

127.0.0.1:7000> CLUSTER INFOcluster_state:ok...

一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性之外，它还会将自己的slots数组通过消息发送给集群中的其他节点，以此来告知其他节点自己目前负责处理哪些槽。

在集群中执行命令

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

如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令。
如果键所在的槽并没有指派给当前节点，那么节点会向客户端返回一个MOVED错误，指引客户端转向（redirect）至正确的节点，并再次发送之前想要执行的命令。
```
127.0.0.1:7000> SET msg "happy new year!"-> Redirected to slot [6257] located at 127.0.0.1:7001OK127.0.0.1:7001> GET msg"happy new year!"
```

计算键属于哪个槽

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

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

当客户端接收到节点返回的MOVED错误时，客户端会根据MOVED错误中提供的IP地址和端口号，转向至负责处理槽slot的节点，并向该节点重新发送之前想要执行的命令。集群模式的redis-cli客户端在接收到MOVED错误时，并不会打印出MOVED错误，而是根据MOVED错误自动进行节点转向，并打印出转向信息，所以看不见节点返回的MOVED错误。

注意：节点和单机服务器在数据库方面的一个区别是，节点只能使用0号数据库。

重新分片

重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点被移动到目标节点。

重新分片操作可以在线（online）进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求。

的重新分片操作是由Redis的集群管理软件redis-trib负责执行的，Redis提供了进行重新分片所需的所有命令，而redis-trib则通过向源节点和目标节点发送命令来进行重新分片操作。详略。

ASK错误

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

源节点会先在自己的数据库里面查找指定的键，如果找到的话，就直接执行客户端发送的命令。 2.相反地，如果源节点没能在自己的数据库里面找到指定的键，那么这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个ASK错误，指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令。集群模式的redis-cli在接到ASK错误时也不会打印错误，而是自动根据错误提供的IP地址和端口进行转向动作。

ASK错误和MOVED错误的区别

MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点：在客户端收到关于槽i的MOVED错误之后，客户端每次遇到关于槽i的命令请求时，都可以直接将命令请求发送至MOVED错误所指向的节点，因为该节点就是目前负责槽i的节点。
ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施：在客户端收到关于槽i的ASK错误之后，客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK错误所指示的节点，但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响，客户端仍然会将关于槽i的命令请求发送至目前负责处理槽i的节点，除非ASK错误再次出现。

复制与故障转移

Redis集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点继续处理命令请求。

设置从节点

向一个节点发送命令：

CLUSTER REPLICATE <node_id>

可以让接收命令的节点成为node_id所指定节点的从节点，并开始对主节点进行复制。

一个节点成为从节点，并开始复制某个主节点这一信息会通过消息发送给集群中的其他节点，最终集群中的所有节点都会知道某个从节点正在复制某个主节点。

故障检测

集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此来检测对方是否在线，如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线（probable fail，PFAIL）。

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

故障转移

当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移：

复制下线主节点的所有从节点里面，会有一个从节点被选中。
被选中的从节点会执行SLAVEOF no one命令，成为新的主节点。
新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己。
新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽。
新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。

新的主节点是通过选举产生的。选举过程略。

消息

集群中的各个节点通过发送和接收消息（message）来进行通信。节点发送的消息主要有以下五种：

MEET消息：当发送者接到客户端发送的CLUSTER MEET命令时，发送者会向接收者发送MEET消息，请求接收者加入到发送者当前所处的集群里面。
PING消息：集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点，然后对这五个节点中最长时间没有发送过PING消息的节点发送PING消息，以此来检测被选中的节点是否在线。除此之外，如果节点A最后一次收到节点B发送的PONG消息的时间，距离当前时间已经超过了节点A的cluster-node-timeout选项设置时长的一半，那么节点A也会向节点B发送PING消息。
PONG消息：当接收者收到发送者发来的MEET消息或者PING消息时，为了向发送者确认这条MEET消息或者PING消息已到达，接收者会向发送者返回一条PONG消息。另外，一个节点也可以通过向集群广播自己的PONG消息来让集群中的其他节点立即刷新关于这个节点的认识。
FAIL消息：当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A会向集群广播一条关于节点B的FAIL消息，所有收到这条消息的节点都会立即将节点B标记为已下线。
PUBLISH消息：当节点接收到一个PUBLISH命令时，节点会执行这个命令，并向集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUB-LISH命令。

消息头、消息正文的实现，略。

第18章　发布与订阅

通过执行SUBSCRIBE命令，客户端可以订阅一个或多个频道：

SUBSCRIBE "news.it"

另一个客户端执行发布命令：

PUBLISH "news.it" "hello"

还可以通过执行PSUBSCRIBE命令订阅一个或多个模式（一个模式可以匹配多个频道）。

频道的订阅与退订

Redis将所有频道的订阅关系都保存在服务器状态的pubsub_channels字典里面，这个字典的键是某个被订阅的频道，而键的值则是一个链表，链表里面记录了所有订阅这个频道的客户端。 SUBSCRIBE和UNSUBSCRIBE实际就是对这个链表的操作。详略。

模式的订阅与退订

服务器也将所有模式的订阅关系都保存在服务器状态的pubsub_patterns属性里面。pubsub_patterns属性是一个链表，链表中的每个节点都包含着一个pubsub Pattern结构，这个结构的pattern属性记录了被订阅的模式，而client属性则记录了订阅模式的客户端。详略。

发送消息

当一个Redis客户端执行PUBLISH 命令将消息message发送给频道channel的时候，服务器需要执行以下两个动作：

将消息message发送给channel频道的所有订阅者。
如果有一个或多个模式pattern与频道channel相匹配，那么将消息message发送给pattern模式的订阅者。

查看订阅信息

PUBSUB命令是Redis 2.8新增加的命令之一，客户端可以通过这个命令来查看频道或者模式的相关信息，比如某个频道目前有多少订阅者，又或者某个模式目前有多少订阅者，诸如此类。详略。

第19章　事务

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

redis> MULTI
OK

redis> SET "name" "Practical Common Lisp"
QUEUED

redis> GET "name"
QUEUED

redis> SET "author" "Peter Seibel"
QUEUED

redis> GET "author"
QUEUED

redis> EXEC
1) OK
2) "Practical Common Lisp"
3) OK
4) "Peter Seibel"

事务的实现

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

事务开始。 MULTI命令可以将执行该命令的客户端从非事务状态切换至事务状态，这一切换是通过在客户端状态的flags属性中打开REDIS_MULTI标识来完成的。
命令入队。如果客户端发送的命令为EXEC、DISCARD、WATCH、MULTI四个命令的其中一个，那么服务器立即执行这个命令。否则将这个命令放入一个事务队列里面，然后向客户端返回QUEUED回复。
事务执行。当一个处于事务状态的客户端向服务器发送EXEC命令时，这个EXEC命令将立即被服务器执行。服务器会遍历这个客户端的事务队列，执行队列中保存的所有命令，最后将执行命令所得的结果全部返回给客户端。

WATCH命令的实现

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

redis> WATCH "name"
OK

redis> MULTI
OK

redis> SET "name" "peter"
QUEUED

redis> EXEC
(nil)

每个Redis数据库都保存着一个watched_keys字典，这个字典的键是某个被WATCH命令监视的数据库键，而字典的值则是一个链表，链表中记录了所有监视相应数据库键的客户端。

所有对数据库进行修改的命令，比如SET、LPUSH、SADD、ZREM、DEL、FLUSHDB等等，在执行之后都会调用multi.c/touchWatchKey函数对watched_keys字典进行检查，查看是否有客户端正在监视刚刚被命令修改过的数据库键，如果有的话，那么touchWatchKey函数会将监视被修改键的客户端的REDIS_DIRTY_CAS标识打开，表示该客户端的事务安全性已经被破坏。

当服务器接收到一个客户端发来的EXEC命令时，服务器会根据这个客户端是否打开了REDIS_DIRTY_CAS标识来决定是否执行事务。

事务的ACID性质

原子性：事务队列中的命令要么就全部都执行，要么就一个都不执行。 Redis的事务和传统的关系型数据库事务的最大区别在于，Redis不支持事务回滚机制，即使事务队列中的某个命令在执行期间出现了错误，整个事务也会继续执行下去，直到将事务队列中的所有命令都执行完毕为止。
一致性：事务执行前后数据状态一致。“一致”指的是数据符合数据库本身的定义和要求，没有包含非法或者无效的错误数据。
隔离性：因为Redis使用单线程的方式来执行事务（以及事务队列中的命令），并且服务器保证，在执行事务期间不会对事务进行中断，因此，Redis的事务总是以串行的方式运行的，并且事务也总是具有隔离性的。
耐久性：因为Redis的事务不过是简单地用队列包裹起了一组Redis命令，Redis并没有为事务提供任何额外的持久化功能，所以Redis事务的耐久性由Redis所使用的持久化模式决定。不论Redis在什么模式下运作，在一个事务的最后加上SAVE命令总可以保证事务的耐久性，不过因为这种做法的效率太低，所以并不具有实用性。

第20章　Lua脚本

通过在服务器中嵌入Lua环境，Redis客户端可以使用Lua脚本，直接在服务器端原子地执行多个Redis命令。

redis> EVAL "return 'hello world'" 0
"hello world"

redis> EVAL "return 1+1" 0
(integer) 2

详略。

第21章　排序

SORT命令可以对列表、集合或者有序集合的值进行排序。

redis> RPUSH numbers 5 3 1 4 2
(integer) 5#

redis> LRANGE numbers 0 -1
1) "5"
2) "3"
3) "1"
4) "4"
5) "2"

redis> SORT numbers
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"

SORT命令的实现

服务器执行SORT numbers命令的详细步骤如下：

创建一个和numbers列表长度相同的数组，该数组的每个项都是一个redisSortObject结构；
遍历数组，将各个数组项的obj指针分别指向numbers列表的各个项，构成obj指针和列表项之间的一对一关系；
遍历数组，将各个数组项的obj指针分别指向numbers列表的各个项，构成obj指针和列表项之间的一对一关系；
根据数组项u.score属性的值，对数组进行数字值排序，排序后的数组项按u.score属性的值从小到大排列；
遍历数组，将各个数组项的obj指针所指向的列表项作为排序结果返回给客户端，程序首先访问数组的索引0，返回u.score值为1.0的列表项”1”；然后访问数组的索引1，返回u.score值为2.0的列表项”2”；最后访问数组的索引2，返回u.score值为3.0的列表项”3”。

ALPHA选项的实现

通过使用ALPHA选项，SORT命令可以对包含字符串值的键进行排序：

SORT <key> ALPHA

详略。

ASC选项和DESC选项的实现

在默认情况下，SORT命令执行升序排序，排序后的结果按值的大小从小到大排列，以下两个命令是完全等价的：

SORT <key>
SORT <key> ASC

BY选项的实现

在默认情况下，SORT命令使用被排序键包含的元素作为排序的权重，元素本身决定了元素在排序之后所处的位置。通过使用BY选项，SORT命令可以指定某些字符串键，或者某个哈希键所包含的某些域（field）来作为元素的权重，对一个键进行排序。

redis> MSET apple-price 8 banana-price 5.5 cherry-price 7
OK

redis> SORT fruits BY *-price
1) "banana"
2) "cherry"
3) "apple"

带有ALPHA选项的BY选项的实现

略。

LIMIT选项的实现

通过LIMIT选项，可以让SORT命令只返回其中一部分已排序的元素。

redis> SORT alphabet ALPHA LIMIT 0 4

STORE选项的实现

默认情况下，SORT命令只向客户端返回排序结果，而不保存排序结果。通过使用STORE选项，可以将排序结果保存在指定的键里面，并在有需要时重用这个排序结果。

redis> SORT students ALPHA STORE sorted_students
(integer) 3

redis> LRANGE sorted_students 0-1
1) "jack"
2) "peter"
3) "tom"

多个选项的执行顺序

一个SORT命令的执行过程可以分为以下几步：

排序：在这一步，命令会使用ALPHA、ASC或DESC、BY这几个选项，对输入键进行排序，并得到一个排序结果集。
限制排序结果集的长度：在这一步，命令会使用LIMIT选项，对排序结果集的长度进行限制，只有LIMIT选项指定的那部分元素会被保留在排序结果集中。
获取外部键：在这一步，命令会使用GET选项，根据排序结果集中的元素，以及GET选项指定的模式，查找并获取指定键的值，并用这些值来作为新的排序结果集。
保存排序结果集：在这一步，命令会使用STORE选项，将排序结果集保存到指定的键上面去。
向客户端返回排序结果集：在最后这一步，命令遍历排序结果集，并依次向客户端返回排序结果集中的元素。

详略。

第22章　二进制位数组

SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组。详略。

第23章　慢查询日志

服务器配置有两个和慢查询日志相关的选项：

slowlog-log-slower-than选项指定执行时间超过多少微秒（1秒等于1 000 000微秒）的命令请求会被记录到日志上。
slowlog-max-len选项指定服务器最多保存多少条慢查询日志（多余的旧日志会被删除）。

实现，略。

第24章　监视器

通过执行MONITOR命令，客户端可以将自己变为一个监视器，实时地接收并打印出服务器当前处理的命令请求的相关信息。

redis> MONITOR
OK

1378822099.421623 [0 127.0.0.1:56604] "PING"
1378822105.089572 [0 127.0.0.1:56604] "SET" "msg" "hello world"

文章版权归作者所有，未经允许请勿转载。

THE END

redis
# redis

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

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

第1章 引言

第2章 简单动态字符串

SDS，simple dynamic string，简单动态字符串。

SDS的定义

SDS相比较C字符串的优势

SDS API

第3章 链表

Redis链表(双端链表)的定义

Redis链表的特性

链表API

第4章 字典

字典的实现

哈希算法

解决键冲突

rehash

字典API

第5章 跳跃表

跳跃表节点

跳跃表

跳跃表API

第6章 整数集合

整数集合的实现

升级

降级

整数集合API

第7章 压缩列表

压缩列表的构成

压缩列表节点的构成

压缩列表API

第8章 对象

对象的类型与编码

字符串对象

列表对象

哈希对象

集合对象

有序集合对象

类型检查与命令多态

内存回收

对象共享

对象的空转时长

第9章 数据库

服务器中的数据库

切换数据库

数据库键空间

读写键空间时的维护操作

设置键的生存时间或过期时间

过期键删除策略

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

复制

数据库通知

第10章 RDB持久化

RDB文件载入时的服务器状态

自动间隔性保存

RDB文件结构

分析RDB文件

第11章 AOF持久化

AOF持久化的实现

AOF文件的载入与数据还原

AOF重写

BGREWRITEAOF命令的实现原理

第12章 事件

文件事件

时间事件

serverCron函数的主要工作

事件的调度与执行

第13章 客户端

客户端属性

客户端的创建与关闭

Lua脚本的伪客户端

AOF文件的伪客户端

第14章 服务器

命令请求的执行过程

serverCron函数

初始化服务器

还原数据库状态

执行事件循环

第15章 复制

旧版复制功能的实现

第1章　引言

第2章　简单动态字符串

第3章　链表

第4章　字典

第5章　跳跃表

第6章　整数集合

第7章　压缩列表

第8章　对象

第9章　数据库

第10章　RDB持久化

第11章　AOF持久化

第12章　事件

第13章　客户端

第14章　服务器

第15章　复制

第16章　Sentinel

第17章　集群

第18章　发布与订阅

第19章　事务

第20章　Lua脚本

第21章　排序

第22章　二进制位数组

第23章　慢查询日志

第24章　监视器