Redis设计与实现

本文主要是介绍Redis设计与实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

简单动态字符串

2.1　SDS的定义

struct sdshdr {

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

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

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

};

2.2 SDS 与 C 字符串的区别

• 常数复杂度获取字符串长度
• 杜绝缓冲区溢出
• 减少修改字符串时带来的内存重分配次数
  空间预分配： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。
  惰性空间释放：当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。
• 二进制安全
  通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据。
• 兼容部分 C 字符串函数
  它们一样遵循 C 字符串以空字符结尾的惯例，可以重用一部分 <string.h> 库定义的函数。
  
• 优化追加操作
  除了可以用 θ(1) 复杂度获取字符串的长度之外，还可以减少追加（append）操作所需的内存重分配次数，以下就来详细解释这个优化的原理。
  当大小小于 1MB 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间； 当字符串的大小大于 1MB ， 那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。

这里是引用

链表

• 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
• 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis的链表实现是双端链表。
• 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

字典

字典（dictionary）， 又名映射（map）或关联数组（associative array）， 是一种抽象数据结构， 由一集键值对（key-value pairs）组成， 各个键值对的键各不相同， 程序可以添加新的键值对到字典中， 或者基于键进行查找、更新或删除等操作。

4.1字典的实现

哈希表

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

哈希表节点
哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

typedef struct dictEntry {

    // 键
    void *key;

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

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

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

4.4渐进式 rehash

以下是哈希表渐进式 rehash 的详细步骤：

1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将rehashidx 属性的值增一。
4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

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

另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。

跳跃表

1. 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
2. Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点。 每个跳跃表节点的层高都是1 至 32 之间的随机数。
3. 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。 跳跃表中的节点按照分值大小进行排序，当分值相同时， 节点按照成员对象的大小进行排序。

整数集合

1. 整数集合是集合键的底层实现之一。
2. 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型。
3. 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
4. 整数集合只支持升级操作， 不支持降级操作。

压缩列表

1. 压缩列表是一种为节约内存而开发的顺序型数据结构。
2. 压缩列表被用作列表键和哈希键的底层实现之一。
3. 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
4. 添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高。

对象

8.1对象的类型与编码

Redis 中的每个对象都由一个 redisObject 结构表示， 该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性：

typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...

} robj;

类型

下图展示了 redisObject 、Redis 所有数据类型、以及 Redis 所有编码方式（底层实现）三者之间的关系：

字符串

字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码：

REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。
REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds （也即是 char* )、 long long 、 double 和 long double 类型值。

需要注意的是 字符串最大长度为 512M。

• 键值对：set name codehole
• 批量键值对：mset name1 boy name2 girl name3 unknown
• 过期和 set 命令扩展：
  setex name 5 codehole # 5s 后过期，等价于 set+expire
  setnx name codehole # 如果 name 不存在就执行 set 创建
• 计数
  incr age

哈希表

REDIS_HASH （哈希表）是 HSET 、 HLEN 等命令的操作对象， 它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_HT 两种编码方式：

Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞 时，就会将碰撞的元素使用链表串接起来。

列表

REDIS_LIST （列表）是 LPUSH 、 LRANGE 等命令的操作对象， 它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_LINKEDLIST 这两种方式编码：

Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)。

Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符 串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理。

集合

REDIS_SET （集合）是 SADD 、 SRANDMEMBER 等命令的操作对象， 它使用 REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 两种方式编码：

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的 内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL。

有序集

REDIS_ZSET （有序集）是 ZADD 、 ZCOUNT 等命令的操作对象， 它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_SKIPLIST 两种方式编码：

zset 可能是 Redis 提供的最为特色的数据结构，它也是在面试中面试官最爱问的数据结 构。它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权 重。它的内部实现用的是一种叫着「跳跃列表」的数据结构。
zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们 可以对成绩按分数进行排序就可以得到他的名次。

zadd books 9.0 "java"
zadd books 8.9 "python"
zrange books 0 -1 # 按 score 排序列出，参数区间为排名范围
zrevrange books 0 -1 # 按 score 逆序列出，参数区间为排名范围
zscore books "python" # 获取指定 value 的 score
zrangebyscore books 0 8.91 # 根据分值区间遍历 zset

数据库

数据库的键空间

redis将所有key进行统一管理，按照所属的库划分，放在redisDb的字典中（按照上面画的数据结构，redis每一个库都对应一个redisDb）。redisDb结构的dict字典保存了该数据库中的所有键值对，也称为键空间。键空间的数据结构如下：

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

键空间的存储

举个例子， 如果我们在空白的数据库中执行以下命令：

redis> SET message "hello world"
OK

redis> RPUSH alphabet "a" "b" "c"
(integer) 3

redis> HSET book name "Redis in Action"
(integer) 1

redis> HSET book author "Josiah L. Carlson"
(integer) 1

redis> HSET book publisher "Manning"
(integer) 1

那么在这些命令执行之后， 数据库的键空间将会是图 IMAGE_DB_EXAMPLE 所展示的样子：

• alphabet 是一个列表键， 键的名字是一个包含字符串 “alphabet” 的字符串对象， 键的值则是一个包含三个元素的列表对象。
• book 是一个哈希表键， 键的名字是一个包含字符串 “book” 的字符串对象， 键的值则是一个包含三个键值对的哈希表对象。
• message 是一个字符串键， 键的名字是一个包含字符串 “message” 的字符串对象， 键的值则是一个包含字符串 “hello
  world” 的字符串对象。

因为数据库的键空间是一个字典， 所以所有针对数据库的操作 —— 比如添加一个键值对到数据库， 或者从数据库中删除一个键值对， 又或者在数据库中获取某个键值对， 等等， 实际上都是通过对键空间字典进行操作来实现的， 以下几个小节将分别介绍数据库的添加、删除、更新、取值等操作的实现原理。

添加新键

添加一个新键值对到数据库， 实际上就是将一个新键值对添加到键空间字典里面， 其中键为字符串对象， 而值则为任意一种类型的 Redis 对象。
举个例子， 如果键空间当前的状态如图 IMAGE_DB_EXAMPLE 所示， 那么在执行以下命令之后：

redis> SET date "2013.12.1"
OK

删除键

删除数据库中的一个键， 实际上就是在键空间里面删除键所对应的键值对对象。

举个例子， 如果键空间当前的状态如图 IMAGE_DB_EXAMPLE 所示， 那么在执行以下命令之后：

redis> DEL book
(integer) 1

更新键

对一个数据库键进行更新， 实际上就是对键空间里面键所对应的值对象进行更新， 根据值对象的类型不同， 更新的具体方法也会有所不同。

举个例子， 如果键空间当前的状态如图 IMAGE_DB_EXAMPLE 所示， 那么在执行以下命令之后：

redis> SET message "blah blah"
OK

对键取值

对一个数据库键进行取值， 实际上就是在键空间中取出键所对应的值对象， 根据值对象的类型不同， 具体的取值方法也会有所不同。

举个例子， 如果键空间当前的状态如图 IMAGE_DB_EXAMPLE 所示， 那么当执行以下命令时：

redis> GET message
"hello world"

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

通过EXPIRE或PEXPIRE，客户端可以以秒或毫秒为精度设置过期时间（Time To Live，TTL）。通过EXPIREAT或PEXPIREAT，客户端可以设置时间戳作为过期时间。
使用TTL或PTTL也可查看某个键的剩余生存时间，还有多久过期：

redis> SET key value
OK
 
redis> EXPIRE key 500
(integer) 1
 
redis> TTL key
(integer) 498

设置过期时间

Redis提供了4个命令设置过期时间：

EXPIRE ：将key的生存时间设为ttl秒。
PEXPIRE ：将key的生存时间设为ttl毫秒。
EXPIREAT ：将key的过期时间设置为timestamp秒数时间戳。
PEXPIREAT ：将key的过期时间设置为timestamp毫秒数时间戳。

过期键删除策略

如果一个键过期了，那么在什么时候被删除？列举几个常见淘汰策略：
定时删除：设置键的过期时间时，创建定时器，过期时，以定时器立刻执行键的删除。
惰性删除：不着急删除过期键，每次获取时都会进行过期校验。
定期删除：隔一段时间，程序就对数据库检查，删除过期键。
定时删除

定时删除策略对内存友好，但对CPU不友好。过期键比较多时，删除会占用资源，特别是和删除当前任务无关的过期键，影响性能。Redis定时器需要创建时间事件，时间事件底层由无需链表实现，查找复杂度为O(N)，如果需要高效处理必然要创建大量的定时器，并不现实。

惰性删除

惰性删除对CPU友好，但对内存不友好。不需要把时间浪费在非相关键的删除上。当键非常多时，会导致内存泄漏，因为只有用到时才会判断，删除。

定期删除

定期删除是一种折衷的方式，隔一段时间执行一次，并限制删除操作执行的时长和频率减少对CPU的占用；定期删除还能减少庞大的过期键对内存的占用。如何确定时长和频率是难点，过长或过少，会退变为定时删除和惰性删除。

Redis的过期键删除策略

Redis使用了惰性删除和定期删除两种策略配合，服务器可以合理地在使用CPU时间和避免内存浪费之间权衡。

数据库通知

Redis发布订阅功能可以让客户端获取数据库中键的变化及命令的执行情况。关注某个键执行了什么命令的通知称为键空间通知。关注某个命令被什么键执行的通知称为事件通知。

RDB持久化

由于Redis是内存数据库，数据状态都存储于内存，如果不想办法将存储在内存中的数据库状态保存到磁盘里，那么一旦服务器进程退出，服务器中的数据库状态也会消失。

为解决这个问题，Redis提供了持久化的功能，可将内存中的数据库保存到磁盘，防止意外丢失。RDS持久化（默认持久化策略）就是将某一时间点上的状态保存到一个RDB文件里。RDB文件是经过压缩的二进制文件，可通过该文件还原成数据库状态。

RDB文件的创建与载入

有两个命令可用于生成RDB文件（SAVE和BGSAVE）。他们之间的区别是：SAVE会阻塞Redis服务器进程，直到RDB文件创建完毕为止，阻塞期间，服务器不能处理任何命令请求。而BGSAVE会fork出一个子进程，由子进程负责创建RDB文件，父进程继续处理命令请求。当子进程完成之后，向父进程发送信号。

• 适用场景
  适合大规模的数据恢复
  对数据完整性和一致性要求不高
• 缺陷
  在一定间隔时间做一次备份，所以如果redis挂了，就会丢失最后一次快照后的所有修改。
  fork的时候，内存中的数据被克隆一份，大致2倍的膨胀性需要考虑内存空间。

自动间隔保存

服务器允许用户通过配置文件设置隔一定时间自动执行BGSAVE。可通过save选项设多个保存条件，默认的配置如下：

save 300 10 // 300 秒内对数据库进行了至少10次修改

RDB文件结构

AOF持久化

AOF 持久化功能的实现可以分为命令追加（append）、文件写入、文件同步（sync）三个步骤。

命令追加

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

举个例子， 如果客户端向服务器发送以下命令：

redis> SET KEY VALUE
OK

那么服务器在执行这个 SET 命令之后， 会将以下协议内容追加到 aof_buf 缓冲区的末尾：

*3\r\n$3\r\nSET\r\n$3\r\nKEY\r\n$5\r\nVALUE\r\n

以上就是 AOF 持久化的命令追加步骤的实现原理。

AOF 文件的写入与同步

Redis 的服务器进程就是一个事件循环（loop）， 这个循环中的文件事件负责接收客户端的命令请求， 以及向客户端发送命令回复， 而时间事件则负责执行像 serverCron 函数这样需要定时运行的函数。

事件

Redis服务器是一个事件驱动程序，主要有两种：

• 文件事件：Redis服务器通过套接字与客户端连接，文件事件就是服务器对套接字操作的抽象。服务器与客户端通信会产生相应文件事件，服务器通过监听这些事件来完成一系列网络通信操作。
• 时间事件：Redis服务器有一些需要在给定时间内执行的操作，而时间事件就是对这类定时操作的抽象。

简单来说，文件事件就是套接字操作相关的事件；时间事件就是定时操作相关事件。

文件事件

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

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

虽然文件事件处理器以单线程方式运行， 但通过使用 I/O 多路复用程序来监听多个套接字， 文件事件处理器既实现了高性能的网络通信模型， 又可以很好地与 Redis 服务器中其他同样以单线程方式运行的模块进行对接， 这保持了 Redis 内部单线程设计的简单性。

文件事件处理器的构成

图 IMAGE_CONSTRUCT_OF_FILE_EVENT_HANDLER 展示了文件事件处理器的四个组成部分， 它们分别是套接字、 I/O 多路复用程序、 文件事件分派器（dispatcher）、 以及事件处理器。

I/O多路复用的实现

Redis 的 I/O 多路复用程序的所有功能都是通过包装常见的 select 、 epoll 、 evport 和 kqueue 这些 I/O 多路复用函数库来实现的， 每个 I/O 多路复用函数库在 Redis 源码中都对应一个单独的文件， 比如 ae_select.c 、 ae_epoll.c 、 ae_kqueue.c ， 诸如此类。

时间事件

时间事件可分为定时事件和周期性事件：

定时事件:只在指定事件到达一次。如xx时间后执行一次。
周期性事件:每隔一段时间执行一次。如每隔xx秒执行一次。

注：Redis一般只用周期性事件。

时间事件的组成

一个时间事件主要由以下三个属性组成：

• id：服务器为时间事件创建的全局唯一ID (标识号)。 ID号按从小到大的顺序递增，新事件的ID号比旧事件大。
• when：毫秒精度的UNIX时间戳，时间事件的到达(arrive)时间。
• timeProc：时间事件处理器函数。当时间事件到达时，服务器就会调用相应的处理器来处理事件。

实现
服务器将所有时间事件都放在一个无序链表中，每当时间事件执行器运行时，遍历整个链表，找到已到达的时间事件，调用相应的事件处理器。新的事件总是插入到链表的表头。

复制

在Redis中，用户可以通过执行SLAVEOF命令或设置slaveof选项，让一个服务器去复制另外一个服务器，被复制的服务器称为主服务器，进行复制的服务器被称为从服务器。

旧版复制功能的实现

Redis的复制功能分为同步和命令传播两个操作：

• 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态；
• 命令传播操作则用于在主服务器的数据库状态被修改，导致从服务器的数据库状态不一致时，让主服务器的数据库重新回到一致

同步
从服务器对主服务器的同步操作需要通过向主服务器发送 SYNC 命令来完成， 以下是 SYNC 命令的执行步骤：

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

命令传播
当同步操作执行完毕之后，主从服务器的数据库达到一致的状态，但当主服务器执行写操作后，主从服务器状态将不再一致；为了确保状态的一致，主服务器会将接受到的写命令发送给从服务器，执行完成后状态再次回到一致

旧版复制功能的缺陷

Redis2.8版本之前，从服务器的复制分为两种情况：

• 初次复制：之前没有复制过主服务器，或者复制的主服务器与上一次主服务器不同；
• 断线后重新复制：处于命令传播的主从服务器因网路原因中断了复制，但从服务器重新连上了主服务器，并继续复制后一种情况虽然在功能上没有问题，但是效率却非常低，因为它会在重新连接后重新发送SYNC命令接受RDB文件，但此时的RDB文件已经包含了部分之前复制过的数据，因而服务器做了部分重复的操作

新版复制功能的实现

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

• 完整重同步用于处理初次复制的情况，其执行步骤与SYNC命令的执行步骤基本一致；
• 部分重同步用于处理断线后重复制情况，从服务器断线后，如果条件允许，主服务器可以将从断线开始执行的写命令发送给从服务器，从服务器接受并执行这些命令后，就可以将数据库更新至主服务器当前所处的状态

Sentinel（哨兵）

上文介绍的复制功能可以把Master的读压力分散到其它Slave上，但是当Master发生故障后，需要手动把一台Slave提升为Master，客户端也很有可能需要修改连接地址如果你没有服务发现这样的基础设施的话，因为你不知道是哪一台Slave被提升为Master。
Redis提供了Sentinel来解决以上问题。它会监控所有的Redis节点，并提供故障转移机智，是一种高可用解决方案。其大致结构如图所示：

集群

相比上文提到的哨兵模式，集群模式主要提供了数据分片的功能，因为一台服务器总有物理容量的限制。分片功能支持把数据分散的存储在多台实例上，突破了单个节点的物理限制。

节点

一个Redis集群通常由多个节点组成，刚开始的时候每个节点都是相互独立的，它们处于一个只包含自己的集群当中，要组建一个真正可用的工作集群，我们必须将各个独立的节点连接起来，构成一个包含多个节点的集群。

连接各个节点的工作可以使用 CLUSTER MEET 命令来完成， 该命令的格式如下：

CLUSTER MEET <ip> <port>

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

槽指派

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

在集群中执行命令

在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态。当客户端向节点发送与数据库键有关的命令时，接受命令的节点会计算出处理命令的数据库键属于哪个槽，并检查这个槽是否指派给了自己。如果键所在的槽指派给了当前节点，那么节点将直接执行这个命令；如果键所在的槽没有指派当前节点，当前节点会向客户端返回一个MOVED错误，指引客户端转向至正确的节点，并再次发送之前要执行的命令。

重新分片

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

数据库

集群模式和单机模式下的数据库一个重要的区别是：集群模式只能使用0号数据库

复制和故障转移

集群模式下节点也分为主节点和从节点，从节点复制主节点并在主节点下线时接替它继续处理请求。
节点之间会定期向集群中其它节点发送PING消息检测在线状态，如果对方在一定时间内没有回复PONG消息，那么节点就会把对方标为疑似下线REDIS_NODE_PFAIL状态。各个节点之间会通过消息交换节点状态，当某个主节点收到其它主节点发来的下线报告时，会把该报告存在目标下线节点对应的clusterNode结构体的fail_reposts链表中。

发布与订阅

Redis的发布与订阅功能由PUBLISH、SUBSCRIBE、PSUBSCRIBE等命令组成。

SUBSCRIBE “news.it” // 订阅频道news.it
PUBLISH “news.it” “hello” // 频道news.it 发布通知

PSUBSCRIBE命令订阅一个或多个模式，从 而成为这些模式的订阅者：每当有其他客户端向某个频道发送消息时，消息不仅会被发送给 这个频道的所有订阅者，它还会被发送给所有与这个频道相匹配的模式的订阅者。

频道的订阅与退订

当一个客户端执行 SUBSCRIBE 命令， 订阅某个或某些频道的时候， 这个客户端与被订阅频道之间就建立起了一种订阅关系。

Redis 将所有频道的订阅关系都保存在服务器状态的 pubsub_channels 字典里面， 这个字典的键是某个被订阅的频道， 而键的值则是一个链表， 链表里面记录了所有订阅这个频道的客户端：

struct redisServer {

    // ...

    // 保存所有频道的订阅关系
    dict *pubsub_channels;

    // ...

};

比如说， 图 IMAGE_PUBSUB_CHANNELS 就展示了一个 pubsub_channels 字典示例， 这个字典记录了以下信息：

• client-1 、 client-2 、 client-3 三个客户端正在订阅 “news.it” 频道。
• 客户端 client-4 正在订阅 “news.sport” 频道。
• client-5 和 client-6 两个客户端正在订阅 “news.business” 频道。

事务

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

事务的实现

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

事务开始
MULTI 命令的执行标志着事务的开始：

redis> MULTI
OK

命令入队
当一个客户端处于非事务状态时，这个客户端发送的命令会立即被服务器执行。
与此不同的是，当一个客户端切换到事务状态之后，服务器会根据这个客户端发来的不同命令执行不同的操作：

• 如果客户端发送的命令为 EXEC 、 DISCARD 、 WATCH 、 MULTI 四个命令的其中一个，那么服务器立即执行这个命令。
• 与此相反，如果客户端发送的命令是 EXEC 、 DISCARD 、 WATCH 、 MULTI
  四个命令以外的其他命令，那么服务器并不立即执行这个命令，而是将这个命令放入一个事务队列里面，然后向客户端返回 QUEUED 回复。

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

Redis应用

分布式锁

分布式应用进行逻辑处理时经常会遇到并发问题。
比如一个操作要修改用户的状态，修改状态需要先读出用户的状态，在内存里进行修 改，改完了再存回去。如果这样的操作同时进行了，就会出现并发问题，因为读取和保存状 态这两个操作不是原子的。

1. 分布式锁本质上要实现的目标就是在 Redis 里面占一个“坑”，当别的进程也要来占
   时，发现已经有人蹲在那里了，就只好放弃或者稍后再试。一般是使用 setnx(set if not exists)指令，只允许被一个客户端占坑。先来先占， 用 完了，再调用 del 指令释放坑。
2. 如果逻辑执行到中间出现异常了，可能会导致 del 指令没有被调用，这样 就会陷入死锁，锁永远得不到释放。
3. 于是我们在拿到锁之后，再给锁加上一个过期时间，比如 5s，这样即使中间出现异常也 可以保证 5 秒之后锁会自动释放。
4. 但是以上逻辑还有问题。如果在 setnx 和 expire 之间服务器进程突然挂掉了，可能是因 为机器掉电或者是被人为杀掉的，就会导致expire 得不到执行，也会造成死锁。 这种问题的根源就在于 setnx 和 expire 是两条指令而不是原子指令。 Redis2.8 版本中作者加入了 set 指令的扩展参数，使得 setnx 和 expire 指令可以一起执行。

超时问题

Redis 的分布式锁不能解决超时问题，如果在加锁和释放锁之间的逻辑执行的太长，以至 于超出了锁的超时限制，就会出现问题。因为这时候锁过期了，第二个线程重新持有了这把锁， 但是紧接着第一个线程执行完了业务逻辑，就把锁给释放了，第三个线程就会在第二个线程逻 辑执行完之间拿到了锁。

有一个更加安全的方案是为 set 指令的 value 参数设置为一个随机数，释放锁时先匹配 随机数是否一致，然后再删除 key。但是匹配 value 和删除 key 不是一个原子操作，Redis 也 没有提供类似于 delifequals 这样的指令，这就需要使用 Lua 脚本来处理了，因为 Lua 脚本可 以保证连续多个指令的原子性执行。

可重入性

可重入性是指线程在持有锁的情况下再次请求加锁，如果一个锁支持同一个线程的多次加 锁，那么这个锁就是可重入的。比如 Java 语言里有个 ReentrantLock 就是可重入锁。Redis 分 布式锁如果要支持可重入，需要对客户端的 set 方法进行包装，使用线程的 Threadlocal 变量 存储当前持有锁的计数。

集群安全性

比如在 Sentinel 集群中，主节点挂掉时，从节点会取而代之，客户端上却并没有明显感 知。原先第一个客户端在主节点中申请成功了一把锁，但是这把锁还没有来得及同步到从节 点，主节点突然挂掉了。然后从节点变成了主节点，这个新的节点内部没有这个锁，所以当 另一个客户端过来请求加锁时，立即就批准了。这样就会导致系统中同样一把锁被两个客户 端同时持有，不安全性由此产生。

Redlock 算法

因为在Redis的主从架构下，主从同步是异步的，如果在Master节点加锁成功后，指令还没有同步到Slave节点，此时Master挂掉，Slave被提升为Master，新的Master上并没有锁的数据，其他的客户端仍然可以加锁成功。

对于这种问题，Redis作者提出了RedLock红锁的概念。

RedLock的理念下需要至少2个Master节点，多个Master节点之间完全互相独立，彼此之间不存在主从同步和数据复制。

加锁时，它会向过半节点发送 set(key, value, nx=True, ex=xxx) 指令，只要过半节点 set 成功，那就认为加锁成功。释放锁时，需要向所有节点发送 del 指令。不过 Redlock 算法还 需要考虑出错重试、时钟漂移等很多细节问题，同时因为 Redlock 需要向多个节点进行读 写，意味着相比单实例 Redis 性能会下降一些。

RedLock问题：

• 性能、资源
  因为需要对多个节点分别加锁和解锁，而一般分布式锁的应用场景都是在高并发的情况下，所以耗时较长，对性能有一定的影响。此外因为需要多个节点，使用的资源也比较多，简单来说就是费钱。
• 节点崩溃重启
  比如有1~5号五个节点，并且没有开启持久化，客户端A在1，2，3号节点加锁成功，此时3号节点崩溃宕机后发生重启，就丢失了加锁信息，客户端B在3，4，5号节点加锁成功。
• GC、网络延迟
• 时钟跳跃
  同样的例子，假设发生网络分区，4、5号节点变为一个独立的子网，3号节点发生始终跳跃（不管人为操作还是同步导致）导致锁过期，这时候另外的客户端就可以从3、4、5号节点加锁成功，问题又发生了。

Redission

加锁、可重入

首先，加锁和解锁都是通过lua脚本去实现的，这样做的好处是为了兼容老版本的redis同时保证原子性。

解锁

如果key都不存在了，那么就直接返回
如果key、field不匹配，那么说明不是自己的锁，不能释放，返回空
释放锁，重入次数-1，如果还大于0那么久刷新过期时间，反之那么久删除锁

watchdog

也叫做看门狗，也就是解决了锁超时导致的问题，实际上就是一个后台线程，默认每隔10秒自动延长锁的过期时间。

延时队列

异步消息队列
Redis 的 list(列表) 数据结构常用来作为异步消息队列使用，使用rpush/lpush操作入队列， 使用 lpop 和 rpop 来出队列。

队列延迟
阻塞读在队列没有数据的时候，会立即进入休眠状态，一旦数据到来，则立刻醒过来。消 息的延迟几乎为零。用 blpop/brpop 替代前面的 lpop/rpop。
如果线程一直阻塞在哪里，Redis 的客户端连接就成了闲置连接，闲置过久，服务器一般
会主动断开连接，减少闲置资源占用。这个时候 blpop/brpop 会抛出异常来。

延时队列的实现
延时队列可以通过 Redis 的 zset(有序列表) 来实现。我们将消息序列化成一个字符串作 为 zset 的 value，这个消息的到期处理时间作为 score，然后用多个线程轮询 zset 获取到期 的任务进行处理，多个线程是为了保障可用性，万一挂了一个线程还有其它线程可以继续处 理。因为有多个线程，所以需要考虑并发争抢任务，确保任务不能被多次执行。

可以考虑使用 lua scripting 来优化一下这个逻辑，将 zrangebyscore 和 zrem 一同挪到服务器端进行原子化操作，这样多个进程之间争抢任务时就不 会出现这种浪费了。

位图

BitMap算法的核心思想是用bit数组来记录0-1两种状态，然后再将具体数据映射到这个比特数组的具体位置，这个比特位设置成0表示数据不存在，设置成1表示数据存在。

BitMap算在在大量数据查询、去重等应用场景中使用的比较多，这个算法具有比较高的空间利用率。

使用案列
给定10亿个不重复的正int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那10亿个数当中。
解法：遍历10个亿数字，映射到BitMap中，然后对于给出的数，直接判断指定的位上存在不存在即可。

BitMap的一些缺点

（1）数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
（2）数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。

HyperLogLog

HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不 精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。

实现原理
HyperLogLog 的使用非常简单，但是实现原理比较复杂，如果读者没有特别的兴趣，下 面的内容暂时可以跳过不看。

布隆过滤器

布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某 个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合 理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在;当它说不存在时，那就肯定不存 在。

布隆过滤器原理
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k

添加元素

• 将要添加的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 将这k个位置设为1

查询元素

• 将要查询的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 如果k个位置有一个为0，则肯定不在集合中
• 如果k个位置全部为1，则可能在集合中

简单限流

滑动时间窗口
zset 数据结构的 score 值，是不是可以 通过 score 来圈出这个时间窗口来。而且我们只需要保留这个时间窗口，窗口之外的数据都 可以砍掉。

漏斗限流
漏斗的剩余空间就代表着当前行为可以持续进行的数量，漏嘴的流水速率代表着 系统允许该行为的最大频率。

GeoHash

Redis 在 3.2 版本以后增加了地理位置 GEO 模块，意味着我们可以使用 Redis 来实现
摩拜单车「附近的 Mobike」、美团和饿了么「附近的餐馆」这样的功能了。

Scan

在平时线上 Redis 维护工作中，有时候需要从 Redis 实例成千上万的 key 中找出特定 前缀的 key 列表来手动处理数据，可能是修改它的值，也可能是删除 key。这里就有一个问 题，如何从海量的 key 中找出满足特定前缀的 key 列表来?
Redis 提供了一个简单暴力的指令 keys 用来列出所有满足特定正则字符串规则的 key。

key命令缺陷
1、没有 offset、limit 参数，一次性吐出所有满足条件的 key，万一实例中有几百 w 个
key 满足条件
2、keys 算法是遍历算法，复杂度是 O(n)，如果实例中有千万级以上的 key，这个指令
就会导致 Redis 服务卡顿

scan提供 limit 参数，可以控制每次返回结果的最大条数。复杂度虽然也是 O(n)，但是它是通过游标分步进行的，不会阻塞线程。
大 key
1.内存空间不均匀
这样会不利于集群对内存的统一管理，存在丢失数据的隐患。

2.超时阻塞
由于Redis单线程的特性，操作bigkey的通常比较耗时，也就意味着阻塞Redis可能性越大，这样会造成客户端阻塞或者引起故障切换，它们通常出现在慢查询中。

3.网络拥塞
bigkey也就意味着每次获取要产生的网络流量较大。
4.过期删除
有个bigkey，它安分守己（只执行简单的命令，例如hget、lpop、zscore等），但它设置了过期时间，当它过期后，会被删除，如果没有使用Redis 4.0的过期异步删除(lazyfree-lazy-expire yes)，就会存在阻塞Redis的可能性，而且这个过期删除不会从主节点的慢查询发现（因为这个删除不是客户端产生的，是内部循环事件，可以从latency命令中获取或者从slave节点慢查询发现）。
5.迁移困难
当需要对bigkey进行迁移（例如Redis cluster的迁移slot），实际上是通过migrate命令来完成的，migrate实际上是通过dump + restore + del三个命令组合成原子命令完成，如果是bigkey，可能会使迁移失败，而且较慢的migrate会阻塞Redis。

这篇关于Redis设计与实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！