note-book-the-design-and-implementation-of-redis

本文不适合学习，偏向复习用

相关文章：Redis笔记——Redis设计与实现

数据结构与对象

看前须知

对象章节的有些内容最好提前了解下，比如以下内容：

在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）

对于 Redis 数据库保存的键值对来说， 键总是一个字符串对象， 而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种

当我们称呼一个数据库键为“字符串键”时， 我们指的是“这个数据库键所对应的值为字符串对象”

当我们称呼一个键为“列表键”时， 我们指的是“这个数据库键所对应的值为列表对象”

简单动态字符串（Simple Dynamic String，SDS）

在Redis中，有两种字符串，一种是传统的C字符串，通常仅用于无需修改的地方（例如日志中）。
而如果Redis需要一个可以修改的字符串，就会使用SDS（键值对的字符串都是使用SDS）

SDS定义

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

常数时间复杂度获取字符串长度

SDS 遵循 C 字符串以空字符(‘\0’)结尾的惯例，空字符占用1的空间，但不会计算在len属性中

SDS获取字符串的时间复杂度是O(1)，而C字符串则需要O(n)遍历

杜绝缓冲区溢出

缓冲区溢出：<string.h>/strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾。C 字符串不记录自身的长度，假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2，执行strcat(s1, s3)时，s1 的数据将溢出到 s2 所在的空间中

SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性，SDS修改前会检查空间是否满足需要，如果不满足会先进行空间拓展，然后进行修改操作

内存预分配

对于C字符串来说，每次修改都会导致内存重分配（因为每次都是占用固定空间，没有冗余空间）

而SDS的内存空间可以由未分配的字节，由free属性记录。每次SDS进行空间拓展时，不仅会给分配修改所需要的空间，还会给分配额外的未使用空间（free）。

• 如果len小于1MB，那么free和len的值相同，即已使用空间等于未使用空间
• 如果大于等于1MB，那么free的值等于1MB

SDS 的 len 将变成 13 字节， 那么程序也会分配13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。

惰性空间释放策略（或者叫不释放策略？）

sdstrim 函数接受一个 SDS 和一个 C 字符串作为参数， 从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。

SDS通过sdstrim函数释放出来的空间会被保留在free中，供以后使用。如果想要释放未使用空间，SDS也提供了相应的API。

保存二进制数据

C字符串在字符串的结尾由空字符，而在中间不能包含空字符。

而SDS可以在字符串中间包含空字符，所以SDS可以用于保存二进制数据，SDS的API都是二进制安全的，这也是SDS的buf被称为字节数组的原因

在处理二进制数据时，特别是在存储图像、音频文件或其他二进制格式的数据时，'\0’的存在是很常见的。

兼容部分C字符串函数

SDS遵循C字符串以空字符串结尾的惯例，所以可以重用部分<string.h>库函数，比如strcasecmp、strcat等

链表

用处

链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器

实现

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

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

字典

用于保存键值对

Redis 的数据库就是使用字典来作为底层实现的

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

实现

typedef struct dict {
    // 类型特定函数，保存了一簇用于操作特定类型键值对的函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表，ht[0]哈希表用于保存数据，ht[1]哈希表用于rehash
    dictht ht[2];
    // rehash 索引，当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表（哈希冲突时将添加到链表表尾）
    struct dictEntry *next;
} dictEntry;

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;

哈希算法

计算索引

hash = dict->type->hashFunction(key);
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
MurmurHash 算法最初由 Austin Appleby 于 2008 年发明， 这种算法的优点在于， 即使输入的键是有规律的， 算法仍能给出一个很好的随机分布性， 并且算法的计算速度也非常快。
MurmurHash 算法目前的最新版本为 MurmurHash3 ， 而 Redis 使用的是 MurmurHash2

rehash （重新散列）

随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。

负载因子 load_factor = ht[0].used / ht[0].size

1. 为字典的 ht[1] 哈希表分配空间
   • 拓展操作时，空间大小等于第一个大于等于$ht[0].used * 2 * 2^n$的空间
   • 收缩操作时，空间大小等于第一个大于等于$ht[0].used * 2^n$的空间
2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面
3. 释放 ht[0] ， 将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表

• 扩展操作（以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行）：
  • 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
  • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；
• 收缩操作：当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。

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

渐进式rehash

为了避免当数据量大时一次性rehash导致停止服务的情况，rehash需要分多次，渐进式。

1. 为字典的 ht[1] 哈希表分配空间
2. 维持一个索引计数器变量rehashidx（初始值为0）
3. rehash过程中，将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，完成映射rehashidx值加一
4. 最后，所有键值对被映射到ht[1]，这是rehashidx的值设为-1，完成rehash操作

在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。

新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作

跳跃表

有序的链式结构，在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的

跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序

在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。

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

实现

表头节点header类似于dummy的性质，没有具体的成员对象和分值

表头节点和其他节点的构造是一样的： 表头节点也有后退指针、分值和成员对象， 不过表头节点的这些属性都不会被用到

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量（表头节点不计算在内）
    unsigned long length;
    // 表中层数最大的节点的层数（表头节点的层数不计算在内）
    int level;
} zskiplist;
typedef struct zskiplistNode {
    // 后退指针（只能按照顺序后退）
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层（根据幂次定律随机生成一个介于1和32之间的值作为level数组的大小）
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

幂次定律（power law）：越大的数出现的概率越小

整数集合

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

实现

可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现重复元素

typedef struct intset {
    // 编码方式，决定了contents数组的类型
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组，从小到大保存
    int8_t[int16_t/int32_t/int64_t] contents[];
} intset;

升级策略：每当我们要将一个新元素添加到整数集合里面， 并且新元素的类型比整数集合现有所有元素的类型都要长时， 整数集合需要先进行升级（upgrade），将底层数组现有的所有元素都转换成与新元素相同的类型，对底层数组进行空间重分配， 然后才能将新元素添加到整数集合里面。

因为每次向整数集合添加新元素都可能会引起升级， 而每次升级都需要对底层数组中已有的所有元素进行类型转换， 所以向整数集合添加新元素的时间复杂度为 O(N)

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大， 所以这个新元素的值要么就大于所有现有元素， 要么就小于所有现有元素（负数）

整数集合的升级策略有两个好处， 一个是提升整数集合的灵活性， 另一个是尽可能地节约内存。

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

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

zlbytes	zltail	zllen	entry1	entry2	…	entryN	zlend

• zlbytes：记录整个压缩列表占用的字节数
• zltail：记录压缩俩表尾节点（entryN）的距离（通过zltail就可以直接得到表尾节点的地址）
• zzlen：记录节点数量
• entryX：列表节点
• zlend：压缩列表的末端标记，是特殊值0xFF

节点

每个压缩列表节点可以保存一个字节数组或者一个整数值

• 字节数组
  • 长度小于等于 63 （2^6-1）
  • 长度小于等于 16383 （2^14-1）
  • 长度小于等于 4294967295 （2^32-1）
• 整数值
  • 4bit（0-12的无符号整数）
  • 1byte的有符号整数
  • 3byte的有符号整数
  • int16_t
  • int32_t
  • int64_t

previous_entry_length	encoding	content

• previous_entry_length：记录上一个节点的长度（通过它就可以获得上一个节点的地址，从而实现从尾到头的遍历）
  • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面
  • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE（十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。
• encoding：记录了节点的 content 属性所保存数据的类型以及长度，按照前两个bit进行划分
  • 00bbbbbb（1byte）：长度小于等于 63 字节的字节数组（长度就是bbbbbb，下面两个数组同理）
  • 01bbb…b（2byte）：长度小于等于 16383 字节的字节数组
  • 10bbb…b（5byte）： 长度小于等于 4294967295 的字节数组
  • 11bbbbbb（1byte）：各种类型的整数（具体类型还要按照接下来的bit继续划分）
• content：content就是上面的字节数组或者整数值

连锁更新： 每个节点的 previous_entry_length 属性都记录了前一个节点的长度。previous_entry_length用1byte或者5byte记录，如果在上一个节点插入一个大于254byte的节点，那么当前节点的previous_entry_length就可能从1byte变成5byte。导致当前节点也扩张，有可能进一步导致下一个节点也要扩张。

实际上连锁更新的情况并不多见

对象

在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）

对于 Redis 数据库保存的键值对来说， 键总是一个字符串对象， 而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种

当我们称呼一个数据库键为“字符串键”时， 我们指的是“这个数据库键所对应的值为字符串对象”

当我们称呼一个键为“列表键”时， 我们指的是“这个数据库键所对应的值为列表对象”

TYPE 命令的实现方式也与此类似， 当我们对一个数据库键执行 TYPE 命令时， 命令返回的结果为数据库键对应的值对象的类型， 而不是键对象的类型

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // 引用计数，过跟踪对象的引用计数信息，值为0的时候自动释放对象并进行内存回收
    int refcount;
    // 空转时长就是通过将当前时间减去键的值对象的lru时间， 空转时长较高的那部分键会优先被服务器释放， 从而回收内存
    unsigned lru:22;
} robj;

• type：对象的类型
  • REDIS_STRING，字符串对象
  • REDIS_LIST，列表对象
  • REDIS_HASH，哈希对象
  • REDIS_SET，集合对象
  • REDIS_ZSET，有序集合对象

汇总一个类型对应的多种编码

• REDIS_STRING，字符串对象
  • REDIS_ENCODING_INT
    • 要求字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示
    • ptr属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int
    • 通过 APPEND 命令， 向一个保存整数值的字符串对象追加了一个字符串值，对象的编码就会从int变成raw
  • REDIS_ENCODING_RAW
    • 字符串对象保存的是一个字符串值，且长度大于 39 字节
    • ptr指针指向一个SDS对象（sdshdr）
  • REDIS_ENCODING_EMBSTR
    • 字符串对象保存的是一个字符串值，且长度小于等于 39 字节
    • 和raw一样，ptr指针指向一个SDS对象，但它的redisObject和sdshdr在空间上是连续的，所以内存分配和释放都只需要一次就可以完成（raw因为两者空间不连续，所以需要分别分配）
    • Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序，所以对embstr的任意修改，都会导致对象的编码从embstr转为raw

  long double类型的浮点数也是作为字符串值来保存的，按长度分为raw和embstr保存

• REDIS_LIST，列表对象
  • REDIS_ENCODING_ZIPLIST
    • 使用压缩列表作为底层实现， 每个压缩列表节点（entry）保存了一个列表元素（可以是字符数组或者int）
    • 需要满足列表对象保存的所有字符串元素的长度都小于 64 字节，并且列表对象保存的元素数量小于 512 个；否则转换为linkedlist
  • REDIS_ENCODING_LINKEDLIST
    • 使用双端链表作为底层实现， 每个双端链表节点（node）都保存了一个字符串对象， 而每个字符串对象都保存了一个列表元素。
• REDIS_HASH，哈希对象
  • REDIS_ENCODING_ZIPLIST
    • 使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾
      • 保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；
      • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
    • 需要满足哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节，并且哈希对象保存的键值对数量小于 512 个；否则转换为hashtable来实现
  • REDIS_ENCODING_HT
    • 使用字典作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存
• REDIS_SET，集合对象
  • REDIS_ENCODING_INTSET
    • 使用整数集合作为底层实现， 集合对象包含的所有元素都被保存在整数集合里面
    • 需要满足集合对象保存的所有元素都是整数值，并且集合对象保存的元素数量不超过 512 个；否则转换为hashtable实现
  • REDIS_ENCODING_HT
    • 使用字典作为底层实现， 字典的每个键都是一个字符串对象， 每个字符串对象包含了一个集合元素， 而字典的值则全部被设置为 NULL
• REDIS_ZSET，有序集合对象（每个节点有成员member和分值score）
  • REDIS_ENCODING_ZIPLIST
    • 使用压缩列表作为底层实现， 每个集合元素使用两个紧挨在一起的压缩列表节点来保存， 第一个节点保存元素的成员（member）， 而第二个元素则保存元素的分值（score），压缩列表的集合元素按照分值从小到大排序

    文中似乎没有说这里的排序方式，如何保持有序性呢？压缩列表中的元素是按照插入顺序存储的，所以新添加的元素会按照其分数值的大小插入到合适的位置，以保持有序性。这样，即使有新元素的加入，Redis 仍然能够在压缩列表中维护有序集合的顺序。

    • 需要满足有序集合保存的元素数量小于 128 个，并且有序集合保存的所有元素成员的长度都小于 64 字节；否则转换为skiplist实现
  • REDIS_ENCODING_SKIPLIST
    • 使用 zset 结构作为底层实现， 一个 zset 结构同时包含一个字典dict和一个跳跃表zskiplist
      • 跳跃表按分值从小到大保存了所有集合元素， 每个跳跃表节点都保存了一个集合元素。通过这个跳跃表， 程序可以对有序集合进行范围型操作， 比如 ZRANK 、ZRANGE 等命令就是基于跳跃表 API 来实现的。
      • 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素： 字典的键保存了元素的成员， 而字典的值则保存了元素的分值。 通过这个字典， 程序可以用 O(1) 复杂度查找给定成员的分值

类型检查

• SET 、 GET 、 APPEND 、 STRLEN 等命令只能对字符串键执行；
• HDEL 、 HSET 、 HGET 、 HLEN 等命令只能对哈希键执行；
• RPUSH 、 LPOP 、 LINSERT 、 LLEN 等命令只能对列表键执行；
• SADD 、 SPOP 、 SINTER 、 SCARD 等命令只能对集合键执行；
• ZADD 、 ZCARD 、 ZRANK 、 ZSCORE 等命令只能对有序集合键执行；

命令的多态性质

可以认为 LLEN 命令是多态（polymorphism）的： 只要执行 LLEN 命令的是列表键， 那么无论值对象使用的是 ziplist 编码还是 linkedlist 编码， 命令都可以正常执行。

对象共享

对象的引用计数属性还带有对象共享的作用，共享对象机制对于节约内存非常有帮助

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

只有在共享对象和目标对象完全相同的情况下， 程序才会将共享对象用作键的值对象， 而一个共享对象保存的值越复杂， 验证共享对象和目标对象是否相同所需的复杂度就会越高， 消耗的 CPU 时间也会越多

所以Redis只共享int字符串对象，并且共享值为 0 到 9999

单机数据库的实现

struct redisDb {
  // 数据库键空间，保存数据库中所有的键值对
  dict *dcit;
  // 过期字典，保存所有键的过期时间
  dict *expires;
}
struct saveparam {
  // 在seconds秒内执行changes次，则满足RDB备份条件
  time_t seconds;
  int changes;
}
struct redisServer {
  // 一个数组，保存着服务器中所有的数据库
  redisDb *db;
  // 服务器的数据库数量
  int dbnum;

  // 数组，保存多个RDB备份的条件
  struct saveparm *saveparms;
  // 距离上一次RDB备份后，服务器进行了多少次修改次数和总时长
  long long dirty;
  time_t lastsave;

  // AOF缓冲区
  sds aof_buf;
}
struct redisClient {
  // 客户端当前正在使用的数据库，使用select命令切换数据库
  redisDb *db;
}

数据库

过期键删除策略

一个键过期了，什么时候会被删除呢？

1. 定时删除：为每个键创建一个定时器，在键过期时立即执行删除操作。缺点：开销大
2. 惰性删除：不主动检查，而是每次从键空间获取键时，检查键是否过期，过期则删除该键。缺点：如果一个键过期，并且一直没有访问到，那么将不会被删除
3. 定期删除：每个一段时间，对数据库进行检查，删除过期键

实际上，Redis服务器使用惰性删除和定期删除两种策略结合

数据库通知

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

比如，通过SUBSCRIBE _ _keyspace@0_ _message命令，可以获取到0号数据库中的message键的所有执行命令

又如，通过SUBSCRIBE _ _keyevent@0_ _:del命令，可以获取0号数据库所有执行del命令的键

RDB持久化

用于备份数据

RDB文件的创建和载入

• 创建
  • SAVE命令会阻塞Redis服务器进程，执行过程中，所有其它命令被阻塞
  • BGSAVE命令会派生一个子进程，由子进程进行文件创建
    • 执行期间，其它命令不会被阻塞，但是相关备份命令执行会有所不同
    • SAVE命令和BGSAVE命令会被拒绝
    • BGSAVE命令执行时，发送的BGREWRITEAOF命令会被阻塞
    • BGREWRITEAOF命令执行时，发送的BGSAVE命令会被拒绝
• 载入
  • 载入期间，服务器处于阻塞状态

AOF持久化的优先级比RDB高，服务器优先使用AOF

RDB文件结构

REDIS	db_version	databases	EOF	check_sum

• REDIS：RDB文件标志位，保存这5个字符，用于快速检查文件类型是否为RDB
• db_version：RDB版本号
• databases：各个数据库的键值对数据
• EOF：结束标志
• check_sum：8字节的校验和

databases保存多个数据库的数据，每个数据库的内容如下所示：

SELECTDB	db_number	key_value_pairs
数据库标志位	数据库号码	键值对数据

其中，key_value_paris由键值对组成，结构如下所示：

EXPIRETIME_MS	ms	TYPE	key	value
过期键标志位（如果有）	过期时间戳（如果有）	value的类型	键（字符串）	值数据

每种value的保存方式和RDB二进制文件的分析方法，这里不展开说了

AOF持久化

通过保存服务器执行的写命令来记录数据库状态

AOF持久化的实现

• 命令追加（append）
  • AOF持久化打开时，服务器执行完一个写命令后，会将写命令追加到aof_buf缓冲区的末尾
• 写入（write）
  • 将aof缓冲区的内容写入程序缓冲区
• 同步（fsync）
  • 将程序缓冲区的内容写入aof文件，根据appendfsync选项的值决定同步方式
    • always：将aof缓冲区所有内容写入并同步到aof文件
    • everysec：将aof缓冲区所有内容写入到aof文件，如果上次aof同步时间超过1秒钟，那么将对AOF文件进行同步，这个同步由一个单独的线程负责
    • no：将aof缓冲区所有内容写入到aof文件，但并不对aof文件执行同步，何时同步由操作系统决定。

AOF文件的载入与数据还原

1. 创建一个不带网络连接的伪客户端
2. 对AOF文件进行分析，并读取一条写命令
3. 通过伪客户端执行被读出的写命令
4. 一直重复步骤2和3直至所有写命令都被处理完

AOF重写

从数据库中读取键当前的值，然后用一条命令去记录键值对，代替之前记录这个键值对的多条命令，这就是AOF重写的实现原理

AOF后台重写

通过一个子进程进行AOF重写，这样重写期间，服务器就可以继续处理请求

这样有个问题，继续处理请求会有新的数据写入，导致AOF重写的数据库状态不一致

为了解决这个问题，Redis设置了一个AOF重写缓冲区，将写命令同时发送给AOF缓冲区和AOF重写缓冲区，保证了：

1. AOF缓冲区的内容会定期被写入和同步到AOF文件，对现有AOF文件的处理工作会如常进行
2. 从创建子进程开始，服务器执行的所有写命令也都会被记录到AOF重写缓冲区里面

当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接到该信号之后，会调用一个信号处理函数，并执行以下工作：

1. 将AOF重写缓冲区中的所有内容写入到新AOF文件中，这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致
2. 对新的AOF文件进行改名，原子地（atomic）覆盖现有的AOF文件，完成新旧两 个AOF文件的替换。

Redis服务重启的数据恢复流程优先考虑AOF，如果没有AOF才会使用RDB持久化文件恢复数据。如果都没有，那么直接启动Reids。

RDB恢复数据功能优于AOF，但如果数据集很大，RDB持久化就会很耗时

AOF文件以文本格式保存所有写操作命令，所以同一数据下，AOF文件通常大于RDB文件

方式	RDB	AOF
启动优先级	低	高
文件体积	小	大
恢复速度	快	慢
数据安全性	丢失（断电）	根据策略配置

事件

Redis服务器需要处理以下两种事件：

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

文件事件

Redis基于Reactor模式开发了自己的网络事件处理器：文件事件处理器，使用IO多路复用来同时监听多个套接字

• 文件事件处理器的构成
  • 套接字
    • 客户端对套接字执行write或close操作，套接字变得可读，产生AE_READABLE事件
    • 客户端对套接字执行read操作，套接字变得可写，产生AE_WRITEABLE事件
  • IO多路复用程序
    • 服务器通过IO多路复用程序监听客户端的套接字，允许同时监听AE_READABLE和AE_WRITEABLE事件，优先处理AE_READABLE事件
  • 文件事件分派器
    • 根据IO多路复用程序传来的套接字，调用相应的事件处理器
  • 事件处理器
    • 连接应答处理器：对连接服务器监听套接字的客户端进行应答
    • 命令请求处理器：从套接字中读入客户端发送的命令请求内容
    • 命令回复处理器：将服务器执行命令后得到的回复通过套接字返回给客户端

时间事件

时间事件分为两类：

1. 定时事件：让程序在指定的时间之后执行一次。事件处理器返回ae.h/AE_NOMORE，该事件到达一次后就会被删除，不会再到达
2. 周期性时间：让程序每隔一段时间就执行一次。事件处理器返回整数值，服务器根据这个值，对时间事件的when属性更新，让事件在一段时间后再次到达

正常模式下，Redis服务器只是用serverCron这一个时间事件，serverCron函数主要工作内容包括：

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

这里顺带总结了服务器的运行主函数：

def main():
    # 初始化服务器
    init_server()
    # 一直处理事件，直至服务器关闭
    while sever_is_not_shutdown():
        aeProcessEvents()
    # 服务器关闭，清空一些数据
    clean_server()

def aeProcessEvents ():
    #获取到达时间离当前时间最接近的时间事件
    time_event = aeSeachNearestTimer()
    #计算最接近的时间事件距离到达还有多少毫秒
    remaind_ms = time_event.when - unix_ts_now()
    #如果事件巳到达，那么remaind_ms的值可能为负数，将它设定为0
    if remaind_ms < 0: remaind_ms = 0
    #根据remaind_ms的值，创建timeval结构
    timeval = create_timeval_with_ms(remaind_ms)
    #阻塞并等待文件事件产生，最大阻塞时间由传入的timeval结构决定
    #如果remaind_ms的值为0,那么aeApiPoll调用之后马上返回，不阻塞
    aeApiPoll(timeval) 
    #处理所有巳产生的文件事件
    processFileEvents()
    #处理所有已到达的时间事件 
    processTimeEvents()

ae.c/aeApiPll函数接受一个sys/time.h/struct timeval结构为参数，并在指定的时间内，阻塞并等待所有被aeCreateFileEvent函数设置为监听状态的套接字产生文件事件，当有至少一个事件发生，或者等待超时后，函数返回

客户端

Reids服务器时典型的一对多服务器程序，使用单线程单进程处理命令请求，并与多个客户端进行网络通信

redisClient对象和redisServer对象都保存在redis服务器中

struct redisClient {
  // 正在使用的套接字描述符
  int fd;
  // 客户端的名字
  robj *name;
  // 客户端的角色，以及目前所处的状态
  int flags;

  // 输入缓冲区，用于保存客户端发送的命令
  sds querybuf;
  // 服务器对命令解析，将命令参数以及个数保存在客户端的argv和argc中
  robj **argv;
  int argc;
  // 服务器在命令表中查找对应的命令实现函数，让客户端的cmd指向这个函数
  struct redisCommand *cmd;

  // 固定大小输出缓冲区，保存服务器的命令回复，默认大小是16*1024
  char buf[REDIS_REPLY_CHUNK_BYTES];
  // 记录buf数组目前已使用的字节数量
  int bufpos;
  // 可变大小输出缓冲区，由reply链表和一个或多个字符串对象组成
  // 当buf数组的空间已经用完，或者回复因为太大无法放入buf数组中，服务器开始使用可变大小输出缓冲区
  list *reply;

  // 记录客户端是否通过了验证
  int authenticated;

  // 创建客户端的时间
  time_t ctime;
  // 客户端与服务器最后一次进行互动的时间
  time_t lastinteraction;
  // 客户端的空转时间，即距离客户端与服务器最后一次互动以来过去的时间
  time_t obuf_soft_limit_reached_time;
}；
struct redisServer {
  // 一个链表，保存了所有客户端状态
  list * clients;
  redisClient *lua_client;
}

服务器使用两种模式来限制客户端输出缓冲区的大小：

1. 硬性限制（hard limit）：输出缓冲区超过硬性限制的大小，立即关闭客户端
2. 软性限制（soft limit）：输出缓冲区超过软性限制的大小，服务器根据客户端的obuf_soft_limit_reached_time属性记录的客户端到达软性限制的时间，如果时间超过了client-output-buffer-limit选项规定的时间，才关闭客户端

服务器

命令请求的执行过程

当我们发送一条指令时，对于服务端其大体执行了如下流程：

1. 客户端将命令转换成协议格式（二进制），并将其发送给服务端
2. 服务端调用命令请求处理器对输入缓冲区中的命令进行解析，得到命令与参数等信息
3. 调用命令对应的命令执行器执行命令
   1. 通过redisCommand结构查找命令
   2. 执行预备操作，检查cmd指针，服务器状态，客户端是否通过验证等，确保命令可以正确顺利执行
   3. 调用命令的实现函数
   4. 执行后续工作，记录慢日志，更新服务器状态，持久化，同步从服务器等操作
4. 将协议格式的执行结果返回给客户端
5. 客户端接受并打印命令回复给我们

struct redisCommand {
  // 命令的名字，比如set
  char* name;
  // 函数指针，指向命令的实现函数，比如setCommand。
  redisCommandProc* proc;
  // 命令参数的个数，用于检查命令请求的格式是否正确。如果这个值为负数-N,那么表示参数的数量大于等于N。注意 命令的名字本身也是一个参数，比如说SET msg hello world命令的参数是"SET", "msg". hello world", 而不仅仅是"msg"和"hello world"
  int arity;
  // 字符串形式的标识值，这个值记录了命令的属性，比如这个 命令是写命令还是读命令，这个命令是否允许在载人数据时使 用，这个命令是否允许在Lua脚本中使用等等
  char* sflags;
  // 对sflags标识进行分析得出的二进制标识，由程序自动生 成。服务器对命令标识进行检查时使用的都是flags属性而不 是sflags属性，因为对二进制标识的检查可以方便地通过位操作来完成
  int flags;
  // 服务器总共执行了多少次这个命令
  long long calls;
  // 服务器执行这个命令所耗费的总时长
  long long milliseconds;
}

serverCron

serverCron函数在redisServer结构中相关属性：

struct redisServer {
  // serverCron函数每100ms执行一次

  // 每100ms更新一下unixtime和mstime，对于精度要求不高的操作会直接使用这两个值，例如：获取缓存内的时间，如日志打印、更新服务器的LRU时钟、决定是否执行持久化任务、计算服务器上线时间等操作
  // 一些都时间精度要求比较高的指令，如设置键过期还是会进行系统调用，获取最准确的系统当前时间
  // 保存了秒级精度的系统当前UNIX时间戳
  time_t unixtime;
  // 保存了毫秒级精度的系统当前UNIX时间戳
  long long mstime;

  // 每10s更新一次，用于计算数据库键的空转时间
  unsigned lruclock:22;

  // 更新服务器每秒执行命令次数，通过ops_sec_last_sample_time和ops_sec_last_sample_ops进行估算
  // 上一次进行抽样的时间
  long long ops_sec_last_sample_time;
  // 闪一次抽样时，服务器已执行的命令数量
  long long ops_sec_last_sample_ops;
  // 大小默认为16的环形数组，数组中每个项都记录了一次抽样结果
  long long ops_sec_samples[REDIS_OPS_SEC_SAMPLES];
  // 环形数组索引值
  int ops_sec_idx;

  //已使用内存峰值
  size_t stat_peak_memory;

  // serverCron运行时，如果这个属性的值为1时，则关闭服务器（服务器接受到SIGTERM信号时，会打开这个标识）
  int shutdown_asap;

  // 如果值为1，那么表示有 BGREWRITEOF 命令被 BGSAVE 延迟了
  int aof_rewirete_scheduled;

  // 记录执行 BGSVAE 命令的子进程（没有则是-1）
  pid_t rdb_child_pid;
  // 记录执行 BGREWRITEOF 命令的子进程（没有则是-1）
  pid_t aof_child_pid;

  // serverCron函数运行次数计数器
  int cronloops;
}

除此之外，serverCron还有以下功能：

• 管理客户端资源
  • 释放超时的客户端
  • 重新分配超过一定长度的客户端缓冲区
• 管理数据库资源
  • 删除过期键
  • 字典rehash
• 将AOF缓冲区中的内容写入AOF文件
• 关闭输出缓冲区大小限制的客户端

初始化服务器

1. 初始化服务器状态结构：设置服务器运行id， Redis 服务器的运行架构等
2. 载入配置选项：Redis服务器加载用户定义的配置选项
3. 初始化服务器数据结构
4. 还原数据库状态：RDB和AOF的初始化
5. 执行事件循环：Redis服务器的事件循环初始化，等待客户端发送命令请求

多机数据库的实现

复制

主服务器和从服务器互相建立关系后，互为对方的客户端，以此来发送消息

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

旧版复制：SYNC

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

在主服务器执行客户端发送的写命令时，主服务器的数据库就有可能会被修改。主服务器需要对从服务器执行命令传播操作：主服务器会将自己执行的写命令，也即是造成主从服务器不一致的那条写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态

旧版复制的缺陷：如果从服务器断线，那么需要与主从服务器重连成功后，主服务器都需要再次执行BGSAVE，并将RDB文件发给从服务器，如果主服务器当前数据库保存数据量比较大，则需要频繁的IO操作（磁盘IO和网络IO）

新版复制：PSYNC

分为两种同步：

1. 完全重同步：与我们刚才介绍的SYNC相同，主服务器向从服务器发送BGSAVE后的RDB文件，并将缓冲区的内容也发给从服务器
2. 部分重同步：对于一些短时间的断线重连情况，从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令，就可以将数据库更新至主服务器当前所处的状态。

• 部分重同步的实现
  • 复制偏移量
    • 在主从服务器复制初始时，主服务器会向从服务器发送一个复制偏移量，这个偏移量由主从服务器分别维护。在命令传播阶段，每次主服务器向从服务器传播N个字节数据时，就会将自己的复制偏移量+N，同时从服务器接收到主服务器传播来的N个字节时，从服务器也会将自己的复制偏移量+N。因此我们可以通过对比主从服务器的复制偏移量，程序可以很容易的知道主从服务器是否处于一致状态。
  • 复制积压缓冲区
    • 复制积压缓冲区是由主服务器维护的一个固定长度(fixed-size)先进先出(FIFO)队列，默认大小为1MB。当主服务器进行命令传播时，它不仅会将写命令发送给所有从服务器，还会将写命令入队到复制积压缓冲区里面，也即主服务器的复制积压缓冲区里面会保存着一部分最近传播的写命令，并且复制积压缓冲区会为队列中的每个字节记录相应的复制偏移量
    • 当从服务器重新连上主服务器时，从服务器会通过PSYNC命令将自己的复制偏移量(offset)发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作。如果offset偏移量之后的数据（也即是偏移量offset+1开始的数据）仍然存在于复制积压缓冲区里面，那么主服务器将对从服务器执行部分重同步操作。相反，如果offset偏移量之后的数据已经不存在于复制积压缓冲区，那么主服务器将对从服务器执行完整重同步操作。
  • 服务器ID
    • 每个Redis服务器，不论主服务器还是从服务器，都会有自己的运行ID，这个ID由服务器在启动时自动生成，由40个随机16进制字符组成
    • 当从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传送给从服务器，而从服务器则会将这个运行ID保存起来。
    • 当从服务器断线并重新连上一个主服务器时，从服务器将向当前连接的主服务器发送之前保存的运行ID
      • 如果从服务器保存的运行ID和当前连接的主服务器的运行ID相同，那么说明从服务器断线之前复制的就是当前连接的这个主服务器，主服务器可以继续尝试执行部分重同步操作。
      • 相反地，如果从服务器保存的运行ID和当前连接的主服务器的运行ID并不相同， 那么说明从服务器断线之前复制的主服务器并不是当前连接的这个主服务器，主服务器将对从服务器执行完整重同步操作。

复制的实现

struct redisServer {
  // 主服务器的地址
  char* masterhost;
  // 主服务器的端口
  int masterport;
}

复制的过程：

1. 从服务器发送SLAVEOF命令给主服务器端后，从服务器会在自己的结构上记录主服务器的地址
2. 建立套接字：根据IP和PORT建立双方的套接字
3. 发送PING命令：检查通信状态
4. 身份验证：主服务器验证从服务器的密码（如果配置了
5. 同步：通过PSYNC进行数据同步
6. 命令传播：主服务器执行了写命令，将命令传播给从服务器

心跳机制

从服务器每秒向主服务器发送：REPLCONF ACK <replication_offset>

1. 检测主从服务器的网络连接状态
2. 辅助实现min-slaves选项
   1. min-slaves-to-write 3：从服务器数量小于3，主服务器就拒绝执行写操作
   2. min-slaves-max-lag 10：超过3个从服务器的延迟大于3秒，主服务器就拒绝执行写操作
3. 检测命令丢失：在保持连接（未断开）的情况下，从服务器也可能出现命令丢失的情况，所以通过心跳检测复制偏移量。如果不同，则主服务器发送缺失的命令给从服务器

Sentinel

Sentinel用于管理主服务器和从服务器，本质上是一个运行在特殊模式下的Redis服务器

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

当server1（主节点）的下线时长超过用户设定的下线时长上限时，Sentinel系统就会对 server1执行故障转移操作：

1. 首先，Sentinel系统会挑选server1属下的其中一个从服务器，并将这个被选中的从服务器升级为新的主服务器。
2. 之后，Sentinel系统会向server1属下的所有其他从服务器发送新的复制指令，让它们成为新的主服务器的从服务器，当所有从服务器都复制新的主服务器时，故障转移操作执行完毕。
3. 另外，Sentinel还会继续监视已下线的server1，并在它重新上线时，将它设置为新的主服务器的从服务器。

启动并初始化Sentinel

启动Sentinel命令：redis-server sentinel.conf --sentinel 或 $ redis-sentinel sentinel.conf

启动过程：

1. 初始化服务器：和正常Reids服务器一样需要初始化，不过不需要加载数据库文件和数据库相关命令
2. 将普通Redis代码换为Sentinel专用代码
3. 状态初始化：sentinelstate结构
4. 初始化sentinel的监视主服务器列表：初始化sentinel结构中的masters
5. 创建向主服务器的连接：Sentinel服务器作为客户端向主服务器建立连接

struct sentinelstate {
  //当前纪元，用于实现故障转移
  uint64_t current_epoch;
  //保存了所有被这个sentinel监视的主服务器
  //字典的键是主服务器的名字
  //字典的值则是一个指向sentinelRedisInstance结构的指针 
  dict *masters;
  //是否进入了TILT模式？
  int tilt;
  //目前正在执行的脚本的数量
  int running_scripts;
  //进入TILT模式的时间 
  mstime_t tilt_start_time;
  //最后一次执行时间处理器的时间 
  mstime_t previous_time;
  // 一个FIFO队列，包含了所有需要执行的用户脚本 
  list *scripts_queue;
} sentinel;
typedef struct sentinelRedisInstance{
  //标识值，记录了实例的类型，以及该实例的当前状态
  int flags;
  //实例的名字
  //主服务器的名字由用户在配置文件中设置
  //从服务器以及Sentinel的名字由Sentinel自动设置
  //格式为 ip:port,例如 ”127.0.0.1:26379”
  char *name;
  //实例的运行id
  char *runid;
  //配置纪元，用于实现故障转移
  uint64_t config_epoch;
  //实例的地址
  sentinelAddr *addr;
  //sentinel down-after-milliseconds 选项设定的值
  //实例无响应多少毫秒之后才会被判断为主观下线(subjectively down) 
  mstime_t down_after_period;
  //sentinel monitor <master-name> <IP> <port> <quorum> 选项中的quorum参数 
  //判断这个实例为客观下线(objectively down)所需的支持投票数量 
  int quorum;
  //sentinel parallel-syncs <master-name> <number> 选项的值
  //在执行故障转移操作时，可以同时对新的主服务器进行同步的从服务器数量
  int parallel_syncs;
  //sentinel failover-timeout <master-name> <ms> 选项的值
  //刷新故障迁移状态的最大时限
  mstime_t failover_timeout;
  
  //主服务器下的从服务器实例
  //字典的键是从服务器的IP加端口，值也是一个指向sentinelRedisInstance结构的指针 
  dict *slaves;
  //监测主服务器的sentinel实例（包含自己本身）
  //字典的键是sentinel的IP加端口，值也是一个指向sentinelRedisInstance结构的指针 
  dict *sentinels;
} sentinelRedisInstance;
typedef struct sentinelAddr {
  char *ip;
  int port;
} sentinelAddr;

获取主服务器信息

Sentinel服务器通过发送INFO命令获取主服务器的当前信息，包括连接这个主服务器的所有从服务器信息

获取从服务器信息后，Sentinel服务器还会建立向从所有服务器的连接

默认情况下，Sentinel会以两秒一次的频率向所有被监视的主服务器和从服务器发送以下信息：（其中s代表sentinel，m代表master）

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

每个sentinel还会通过_sentinel_:hello频道发送自己的信息，其次每个sentinel又会订阅_sentinel_:hello频道，因此一个sentinel通过_sentinel_:hello频道发送的信息会被其他sentinel收到（包括它自己也会收到），这样一来，sentinel就能获得其他sentinel的信息

获得的信息会被用于更新主服务器中sentinels字典，字典的键为ip:port，值为一个指向sentinelRedisInstance结构的指针 ，sentinel会判断当前实例是否存在，如果存在就更新对应的sentinel实例的信息，否则就创建一个新的sentinel实例并加入到字典中

获取到其它sentinel服务器后，当前setntinel服务器会创建向其它sentinel服务器的连接，用于sentinel服务器之间的信息交换（比如用于判断主服务器下线状态）

主观下线

默认情况下sentinel会以每秒1次的频率向所有建立的网络连接发送PING命令（包括主从服务器和其他sentinel），通过实例的PING命令回复来判断实例是否在线，主观下线是一个sentinel单独的判断结果

通过配置down-after-milliseconds参数设置服务器响应超时时间，每个sentinel的这个参数配置可能不同，所以每个sentinel服务器对同个主服务器的主观下线状态判定可能不一样

客观下线

在得出主观下线后，会询问其他sentinel是否也认为实例已经下线，当超过半数的sentinel服务器认为主服务器下线后，则可以认为是客观下线

sentinel服务器通过发送SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid>指令询问其它sentinel服务器

选举领头Sentinel进行故障转移

1. 配置纪元就是代表着一次执行，如果本次选举不成功，那么就将配置纪元+1，进行下一次的选举。
2. 每个sentinel如果监测到了主观下线都可以通过SENTINEL is-master-down-by-addr要求其他sentinel给自己投票。
3. 投票规则是先到先得，且每人只有一票，只有票数过半的sentinel才会被选举为领头。
4. 通过SENTINEL is-master-down-by-addr的返回结果中的leader_epoch和leader_runid是否和自己相同，可以知道返回的sentinel有没有为自己投票。

故障转移

1. 在从服务器中选出一个服务器作为新的主服务器（选取条件：在线，五秒内有回复，优先级高，复制偏移量最新，ID最小）
2. 将其他从服务器改为复制新的主服务器
3. 将已下线的旧主服务器设为新主服务器的从服务器，当旧主服务器重新上线后，会成为新主服务器的从服务器。

集群

Redis集群允许多个 Redis 服务器通过分布式的方式存储数据，通过数据分片（sharding）和节点复制来实现高可用性和可扩展性。

typedef struct clusterState {
  // 指向当前节点的指针
  clusterNode *myself;
  // 集群当前的配置纪元，用于实现故障转移
  uint64_t currentEpoch;
  // 集群当前的状态：是在线还是下线
  int state;
  // 集群中至少处理着一个槽的节点的数量
  int size;
  // 集群节点名单（包括 myself 节点）
  // 字典的键为节点的名字，字典的值为节点对应的 clusterNode 结构
  dict *nodes;

  // 记录每个槽对应的指派节点
  clusterNode *slots[16384];

  // 由键和这个键所在的槽组成的跳跃表
  zskiplist *slots_to_keys;

  // 记录当前节点正在从其它节点导入的槽，默认为null。如果指向一个clusterNode节点，则表示当前节点正在从clusterNode节点导入槽i
  clusterNode *importing_slots_from[16384];
  // 记录当前节点正在迁移至其他节点的槽。如果指向一个clusterNode节点，则表示当前节点正在将槽迁移至clusterNode节点
  clusterNode *migrating_slots_to[16384];
} clusterState;
struct clusterNode {
  // 创建节点的时间
  mstime_t ctime;
  // 节点的名字，由 40 个十六进制字符组成
  // 例如 68eef66df23420a5862208ef5b1a7005b806f2ff
  char name[REDIS_CLUSTER_NAMELEN];
  // 节点标识
  // 使用各种不同的标识值记录节点的角色（比如主节点或者从节点），
  // 以及节点目前所处的状态（比如在线或者下线）。
  int flags;
  // 节点当前的配置纪元，用于实现故障转移
  uint64_t configEpoch;
  // 节点的 IP 地址
  char ip[REDIS_IP_STR_LEN];
  // 节点的端口号
  int port;
  // 保存连接节点所需的有关信息
  clusterLink *link;

  // 槽指派，索引i上的二进制数为1，那么表示该节点负责处理槽i
  unsigned char slots[16384/8];
  // 该节点处理槽的总数
  int numslots;
  
  // 如果该节点是个从节点，那么将指向主节点（记录这个节点正在复制的主节点）
  struct clusterNode *slaveof;
  // 如果该节点是个主节点，记录正在复制这个主节点的从节点数量
  int numslaves;
  // 数组每一项代表正在复制这个主节点的从节点的clusterNode结构
  struct clusterNode **slaves;
  // 链表，记录了所有其他节点对该节点的下线报告，由clusterNodeFailReport结构标识
  list *fail_reports;
};
typedef struct clusterLink {
  // 连接的创建时间
  mstime_t ctime;
  // TCP 套接字描述符
  int fd;
  // 输出缓冲区，保存着等待发送给其他节点的消息（message）。
  sds sndbuf;
  // 输入缓冲区，保存着从其他节点接收到的消息。
  sds rcvbuf;
  // 与这个连接相关联的节点，如果没有的话就为 NULL
  struct clusterNode *node;
} clusterLink;
struct clusterNodeFailReport {
  // 报告目标节点已经下线的节点
  struct clusterNode *node;
  // 最后一次从node节点收到下线报告的时间
  mstime_t time;
}

redisClient 结构和 clusterLink 结构都有自己的套接字描述符和输入、输出缓冲区， 这两个结构的区别在于， redisClient 结构中的套接字和缓冲区是用于连接客户端的， 而 clusterLink 结构中的套接字和缓冲区则是用于连接节点的。

通过向节点 A 发送 CLUSTER MEET 命令，并指定节点 B 的 IP 地址和端口时， 客户端可以让接收命令的节点 A 将另一个节点 B 添加到节点 A 当前所在的集群里面

槽指派

集群的整个数据库被分为16384个槽（slot），集群中的每个节点都可以处理0个或16384个槽；数据库中的每个键都属于这16384个槽的其中一个

节点可以使用 CLUSTER ADDSLOTS <slot> [slot ...] 命令将指定的槽指派给自己

当集群的所有槽都有节点指派后，集群就会进入上线状态

MOVED 错误

当节点发现键所在的槽并非由自己负责时，节点会向客户端返回一个MOVED错误，指引客户端转向负责这个槽的节点

集群节点也是通过保存键值对过期时间的方式实现过期键

集群节点只能使用0号数据库，而单机数据库则没有这个限制

重新分片

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

1. 让目标节点准备好接收
2. 让源节点准备好键值对迁移
3. 向源节点发送最多count个属于槽slot的键值对（分批发送）
4. 对于上个步骤的每个键值对，让源节点迁移键值对到目标节点
5. 重复3和4步骤，直到发送完毕
6. 广播消息给所有节点

ASK 错误

通过migrating_slots_to属性可以知道正在进行迁移操作的槽，如果当前节点收到一个键key的请求，它首先会尝试在自己的数据中找这个key，如果找到则直接返回。
如果没找到，那么检查自己的migrating_slots_to属性，查看键key所在的槽是否正在进行迁移，如果是，那么返回ASK错误，指引客户端前往迁移的目标节点。
于是客户端前往目标节点请求这个key，但是要注意，这个key所在的槽并没有完全迁移完成，还属于源节点。所以，客户端向目标节点请求这个key时，默认情况下不会被正常处理，而是返回MOVED 错误。
所以在这里，Redis让客户端先发送一个ASKING命令给目标节点，开启目标节点的REDIS_ASKING标识，带有这个标识的客户端将破例执行这个槽的命令一次。

MOVED 错误代表槽的负责权已经从一个节点转移到了另一个节点

ASK错误只是两个节点在迁移槽的过程中的一种临时措施

复制与故障转移

集群中每个主节点定期向集群的其他主节点发送PING消息，如果其它主节点没有在规定时间内返回PONG消息，那么主节点会在自己的clusterState.nodes字典标志目标主节点的clusterNode结构进入疑似下线状态

同样是超过半数标记疑似下线状态，则会认为目标主节点下线，并向集群广播目标主节点下线的FAIL消息，之后便开始对目标主节点进行故障转移

1. 目标主节点（下线）的所有从节点执行SLAVEOF no one命令，称为新的主节点，最终一个从节点得到一半以上投票，胜出选举
2. 将目标主节点的所有槽指派转移给新的主节点
3. 新的主节点广播PONG消息，宣告自己称为新的主节点

消息

typedef struct {
  //消息的长度（包括这个消息头的长度和消息正文的长度）
  uint32_t totlen;
  //消息的类型
  uint16_t type;
  //消息正文包含的节点信息数量
  //只在发送MEET 、PING 、PONG 这三种Gossip 协议消息时使用
  uint16_t count;
  //发送者所处的配置纪元
  uint64_t currentEpoch;
  //如果发送者是一个主节点，那么这里记录的是发送者的配置纪元
  //如果发送者是一个从节点，那么这里记录的是发送者正在复制的主节点的配置纪元
  uint64_t configEpoch;
  //发送者的名字（ID ）
  char sender[REDIS_CLUSTER_NAMELEN];
  //发送者目前的槽指派信息
  unsigned char myslots[REDIS_CLUSTER_SLOTS/8];
  //如果发送者是一个从节点，那么这里记录的是发送者正在复制的主节点的名字
  //如果发送者是一个主节点，那么这里记录的是REDIS_NODE_NULL_NAME
  //（一个40 字节长，值全为0 的字节数组）
  char slaveof[REDIS_CLUSTER_NAMELEN];
  //发送者的端口号
  uint16_t port;
  //发送者的标识值
  uint16_t flags;
  //发送者所处集群的状态
  unsigned char state;
  //消息的正文（或者说，内容）
  union clusterMsgData data; 
} clusterMsg;
struct clusterMsgData {
  // MEET 、PING 、PONG 消息的正文
  struct {
    //每条MEET 、PING 、PONG 消息都包含两个
    //clusterMsgDataGossip 结构
    clusterMsgDataGossip gossip[1];
  } ping;
  // FAIL 消息的正文
  struct {
    clusterMsgDataFail about;
  } fail;
  // PUBLISH 消息的正文
  struct {
    clusterMsgDataPublish msg;
  } publish;
}

• MEET 消息：当一个节点需要加入集群时，它会通过 MEET 消息告诉集群中的其他节点自己的地址
• PING 消息：集群节点会周期性地向其他节点发送 PING 消息，以检查它们是否仍然处于活动状态
• PONG 消息：节点在接收到 PING 消息后，会回复一个 PONG 消息，表示它仍然是活动的
• FAIL消息：当节点检测到其他节点失效时，会发送 FAIL 消息通知集群，触发集群对失效节点的处理
• PUBLISH 消息： 当一个节点需要向整个集群广播某个消息时，它会通过 PUBLISH 消息将消息发送给其他节点，所有接收到PUBLISH消息的节点都会执行相同的PUBLISH命令

独立功能的实现

发布与订阅

struct redisServer {
  // 保存所有频道的订阅关系，key为频道名，Value是一个链表，链表上的每一个节点都是一个Redis客户端
  dict *pubsub_channels;
  //保存所有模式订阅关系，用一个pubsubPattern的链表进行保存
  list *pubsub_patterns;
}
typedef struct pubsubPattern{
  //订阅模式的客户端
  redisClient *client;
  //被订阅的模式
  robj *pattern;
} pubsubPattern;

• 订阅
  • SUBSCRIBE命令：订阅一个或多个频道
  • PSUBSCRIBE命令：订阅一个或多个模式（一个模式通过正则匹配多个频道）
• 发布消息
  • PUBLISH命令：向频道发送消息
• 查看订阅消息
  • PUBSUB CHANNELS [pattern]
    • 返回所有或者符合pattern模式的频道
  • PUBSUB NUMSUB [channel-1 channel-2…]
    • 从pubsub_channels字典中找到频道对应的订阅者链表，返回这些链表的长度
  • PUBSUB NUMPAT
    • 返回服务器当前被订阅模式的数量，及pubsub_patterns链表的长度

事务

事务提供一种将多个命令请求打包，然后一次性、按顺序地执行多个命令的机制，并且在事务执行期间，服务器不会中断事务而该去执行其他客户端的命令请求

typedef struct redisClient{
  //事务队列
  multiState mstate;
}
typedef struct multiState{
  //事务队列，FIFO顺序 
  multiCmd *commands;
  //已入队命令计数
  int count;
}
typedef struct multiCmd{
  //参数
  robj **argv;
  //参数数量
  int argc;
  //命令指针
  struct redisCommand *cmd;
} multiCmd;

• 事务的实现
  • 事务开始
    • 一个事务首先以一个 MULTI 命令开始
    • MULTI命令会打开客户端flags属性的REDIS_MULTI标识
  • 命令入队
    • 接着将多个命令放入事务中
  • 事务执行
    • 最后又 EXEC 命令将这个事务提交给服务器执行

typedef struct redisDb{
  //正在被WATCH命令监视的键，key值是键名，value是一个链表，链表中的每个节点都是一个客户端
  dict *watched_keys;
} redisDb;

• WATCH 命令是一个乐观锁（optimistic locking）

  • WATCH可以在事务执行前监视Redis中任意数量的数据库键，如果在EXEC命令执行时，被监视的键改动了，那么事务就拒绝执行，否则就正常执行
  • Redis客户端通过打开flags属性的 REDIS_DIRTY_CAS 标识 实现，如果客户端监视的键被修改了，那么这个标识就会被打开

• Reids的ACID

  • 原子性
    • 要求：数据库将事务中的多个操作当作一个整体来执行，服务器要么执行事务中的所有操作，要么就一个操作也不执行
    • Redis事务的执行是原子执行的，由于Redis是单线程的，因此某个事务执行的时候，不会执行其他客户端的指令，直到事务执行完。
    • Redis事务不支持回滚。也即如果事务队列中任何一条指令失败，Redis会不会回滚这条事务之前的操作。Redis的作者在事务功能的文档中解释说，不支持事务回滚是因为这种复杂的功能和 Redis追求简单高效的设计主旨不相符，并且他认为，Redis事务的执行时错误通常都是编程错误产生的，这种错误通常只会出现在开发环境中，而很少会在实际的生产环境中出现， 所以他认为没有必要为Redis开发事务回滚功能。

    • 当事务中有语法错误时，Redis会检测出，并且不会执行事务中的任何命令；如果事务出现执行错误时，比如incr一个字符串，则会顺序执行所有命令并且这个incr命令报错

  • 一致性
    • 要求：数据库在执行事务之前是一致的，那么在事务执行之后，无论事务是否执行成功，数据库也应该仍然是一致的
    • Redis对于错误命令和命令执行错误的情况，会拒绝执行；对于停机的情况，通过持久化来进行恢复
  • 隔离性
    • 要求：数据库中有多个事务并发地执行，各个事务之间也不会互相影响，并且在并发状态下执行的事务和串行执行的事务产生的结果完全相同
    • Redis使用单线程的方式执行事务，总是以串行的方式运行事务，所以事务总是具有隔离性的
  • 持久性
    • 要求：一个事务执行完毕时，执行这个事务所得到的结果已经被保存到永久性存储介质（比如硬盘）中了，即使服务器在事务执行完毕后停机，执行事务所得到的结果也不会丢失
    • Redis通过AOF和RDB进行持久化，但只有AOF模式处于appendfsync为always时，保证每个命令执行完数据被持久化到硬盘，Redis才具有持久性

Lua脚本

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

• 创建Lua环境
  • 载入函数库：基础库、表格库、字符串库等
  • 创建redis全局表格，包含一些函数：Redis命令执行函数、Redis日志函数等
  • 使用Redis自制的随机函数来替换Lua原有的随机函数：对于相同的sedd，产生相同的结果（避免了原有的副作用）
  • 创建排序辅助函数
  • 创建redis.pcall错误报告辅助函数
  • 保护Lua环境，保护Lua全局变量
  • 将Lua环境保存到服务器状态的lua属性中
• Lua环境协作组件
  • 伪客户端：Redis服务器为Lua环境创建了一个伪客户端，执行Lua脚本中的Redis命令
  • lua_script字典：key是Lua脚本的SHA1校验和，value是Lua脚本
  • EVAL命令
    • 定义脚本函数：在Lua环境中创建这个脚本对应的Lua函数
    • 将脚本保存到lua_scripts字典
    • 执行脚本函数
  • EVALSHA命令：执行SHA1校验和对应的Lua脚本
  • 脚本管理命令
    • SCRIPT FLUSH：清除所有和Lua脚本有关的信息
    • SCRIPT EXISTS：检验SHA1校验和对应的Lua脚本是否存在于服务器之中
    • SCRIPT LOAD：和EVAL命令的前两个步骤一样，但是不执行
    • SCRIPT KILL：停止Lua脚本运行
• 脚本复制
  • 在服务器运行在复制模式下时，具有写性质的脚本命令也会被复制到从服务器中，包括：EVAL、SCRIPT FLUSH、SCRIPT LOAD
  • EVALSHA命令比较特殊，主服务器执行EVALSHA命令，可以找到对应的Lua脚本，而在从服务器中可能找不到
    • 主服务器使用repl_scriptcache_dict字典记录已经将哪些Lua脚本传播给了所有服务器，以此来判断此次EVALSHA命令是否安全
      • 如果执行的EVALSHA命令的校验和在字典中，那么直接将EVALSHA复制到从服务器中即可
      • 否则，需要将EVALSHA命令替换成对应的EVAL命令，再复制到给从服务器中

排序

typedef struct _redisSortObject {
  // 被排序键的值
  robj *obj;
  // 权重
  union {
    // 排序数字值时使用
    double score;
    // 排序带有 BY 选项的字符串值时使用
    robj *cmpobj;
  } u;
} redisSortObject;

• SORT命令
  • 默认对数字值的键key进行排序
  • ALPHA选项：对包含字符串值的键进行排序
  • ASC和DESC选项：升序和降序
  • BY选项：使用被排序键包含的元素作为排序的权重，可用于使用value排序字典的key
  • LIMIT选项：返回限制数量的元素个数
  • GET选项：对返回结果的二次“加工”
  • STORE选项：保存排序结果

二进制位数组

• 位数组的表示
  • 使用字符串对象表示位数组，
    • 使用SDS结构保存位数组
    • 每个字符是一个字节，包含8个位
    • 末尾是一个空字符
  • SETBIT：设置指定偏移量上的一个或多个二进制位的值
  • GETBIT：获取指定偏移量上的一个或多个二进制位的值
  • BITCOUNT：统计值为1的二进制位的数量
  • BITOP：执行AND、OR、XOR等操作

慢查询日志

struct redisServer {
  // 下一条慢查询日志的 ID
  long long slowlog_entry_id;
  // 保存了所有慢查询日志的链表，保存slowlogEntry对象
  list *slowlog;
  // 服务器配置 slowlog-log-slower-than 选项的值
  long long slowlog_log_slower_than;
  // 服务器配置 slowlog-max-len 选项的值
  unsigned long slowlog_max_len;
};
typedef struct slowlogEntry {
  // 唯一标识符
  long long id;
  // 命令执行时的时间，格式为 UNIX 时间戳
  time_t time;
  // 执行命令消耗的时间，以微秒为单位
  long long duration;
  // 命令与命令参数
  robj **argv;
  // 命令与命令参数的数量
  int argc;
} slowlogEntry;

• 配置
  • slowlog-log-slower-than选项指定执行时间超过多少微秒的命令会被记录到日志上
  • slowlog-max-len选项指定服务器最多保存多少条慢查询日志
• 命令
  • SLOWLOG GET：打印指定数量或者所有的慢日志
  • SLOWLOG LEN：获取慢日志的数量
  • SLOWLOG RESET：删除所有慢日志

监视器

通过MONITOR命令，客户端可以将自己变成一个监视器，实时地接收并打印服务器当前处理请求的相关信息（会开启flags属性的REDIS_MONITOR标志）

当一个客户端发送命令给服务器时，服务器处理命令后，将这条命令请求的信息发送给所有监视器