面试集中营—Redis架构篇

一、Redis到底是多线程还是单线程

1、redis6.0版本之前的单线程，是指网络请求I/O与数据的读写是由一个线程完成的；

2、redis6.0版本升级成了多线程，指的是在网络请求I/O阶段应用的多线程技术；而键值对的读写还是由单线程完成的。所以redis多线程的模型依然是线程安全的。

二、Redis的数据存储结构

redis 存储结构

redis的存储结构从外层往内层依次是redisDb、dict、dictht、dictEntry。
redis的Db默认情况下有16个，每个redisDb内部包含一个dict的数据结构。
redis的dict内部包含dictht的数组，数组个数为2，主要用于hash扩容使用。
dictht内部包含dictEntry的数组，可以理解就是hash的桶，然后如果冲突通过挂链法解决

下面我们依次来看下每个存储对象的数据结构

redisDb：Redis中存在“数据库”的概念，该结构由redis.h中的redisDb定义。当Redis 服务器初始化时，会预先分配 16 个数据库，所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中；redisClient中存在一个名叫db的指针指向当前使用的数据库。
RedisDB结构体源码如下：

DB

typedef struct redisDb {
	int id; //id是数据库序号，为0-15（默认Redis有16个数据库）
	long avg_ttl; //存储的数据库对象的平均ttl（time to live），用于统计
	dict *dict; //存储数据库所有的key-value
	dict *expires; //存储key的过期时间
	dict *blocking_keys;//blpop 存储阻塞key和客户端对象
	dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
	dict *watched_keys;//存储watch监控的的key和客户端对象
} redisDb;

每个DB维护了多个字典，每个字段存储的内容不同，主要的是存储了value和过期时间。我们看下字典的数据结构

字典

typedef struct dict {
    dictType *type; // 该字典对应的特定操作函数
    void *privdata; // 上述类型函数对应的可选参数
    dictht ht[2]; /* 两张哈希表，存储键值对数据，ht[0]为原生哈希表，ht[1]为 rehash 哈希表 */
    long rehashidx; /*rehash标识 当等于-1时表示没有在rehash，否则表示正在进行rehash操作，存储的值表示hash表 ht[0]的rehash进行到哪个索引值(数组下标)*/
    int iterators; // 当前运行的迭代器数量
} dict;

字典当中主要我们要注意两个字段，一个是dictht这是一个hash数组，但是容量只有2，也就是只有两张hash表，数组下标为0的是数据默认存储的位置，如果没有扩容就不会触发rehash，如果出发了rehash就会在数组下标1的位置记录rehash阶段的数据。第二个就是rehashidx，这里是记录了当前rehash的标识，因为redis是渐进式rehash的，所以要有一个类似游标的字段来记录当前rehash到了哪里。

我们进入dictht来看下hash表的数据结构

hash表

typedef struct dictht {
    dictEntry **table; // 哈希表数组
    unsigned long size; // 哈希表数组的大小
    unsigned long sizemask; // 用于映射位置的掩码，值永远等于(size-1)
    unsigned long used; // 哈希表已有节点的数量,包含next单链表数据
} dictht;

这个结构比较的简单了，主要是维护了一个hash数组，真正存储数据地方；我们要注意这里还维护了一个字段叫size，这个很重要，当我们要统计整个redis中的键的数量时就不需要全部遍历一遍了。

Hash表节点

typedef struct dictEntry {
    void *key; // 键
    union { // 值v的类型可以是以下4种类型
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一个哈希表节点，形成单向链表 解决hash冲突
} dictEntry;

表节点中的可以就是键值的指针，值v的类型可以是四种类型

数据存储过程

以set为例作为说明，过程如下：

1、从redisDb当中找到dict，每个db就一个dict而已。

2、从dict当中选择具体的dictht对象。

3、首先根据key计算hash桶的位置，也就是index。

4、新建一个DictEntry对象用于保存key/value，将新增的entry挂到dictht的table对应的hash桶当中，每次保存到挂链的头部。

5、dictSetKey的宏保存key

6、dictSetVal的宏保存value

三、Redis的底层数据结构

我们都知道Redis提供了多种数据结构，例如string、hash、list、set、zset等，那么这些数据结构是如果在redis中存储的呢？从第二个问题中，我们可以得到如下这张图。

从全局来看，Redis整个数据库是用字典来存储的，就是dict，那么这个字典其实就是一张hash表，那么hash表主要由两个数据结构来组成，一个是桶，也可以理解成是一个数组列表，然后每个桶下面是对应的entry数据，entry数据中有key和value，key默认都是字符串，value就是各种各样的数据类型。

数据类型和底层数据结构

不同的数据类型在redis底层是怎么实现的呢？我们看下这张图。

SDS

C语言中的char类型的问题如下：

1、获取字符串的长度要遍历所有的字符，为O(n)；

2、追加字符串的时候，比如把"hello" 变成 "hello world"，会重新分配内存地址，会造成缓冲区溢出；

3、字符串中不能含有"\0"字符串，不能保存像图像、视频、音频这样的二进制数据；

为此，redis设计了新的数据类型SDS，简单动态字符串，string类型的实现。

// 3.0版本
struct sdshdr {

    int len; // 记录buf数组中已使用字节的数量

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

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

}


// 5.0版本
struct sdshdr {

    int len; // 记录buf数组中已使用字节的数量

    int alloc; // 分配给字节数组的大小

    char *flags; // 类型

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

}

1、len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
2、alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。
3、flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。
4、buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。

List

同样的，redis也自己实现了一套链表数据结构，首先定义了一个listNode

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

好像也没有什么特别，就是前驱节点，后置节点以及节点的值。为了更好的管理和统计，Redis又抽象出来了一个List数据结构

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

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。

压缩列表

list结构有一个最大的问题就是内存是不连续的，无法利用CPU的缓存。所以就出现了压缩列表，它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。

压缩列表由于存储尾节点的偏移量，那么获取头尾节点都很简单，但是还是有几个问题。

1、获取中间节点就需要像数组一样一个个遍历，时间复杂度变成了O(N)。

2、插入数据的时候如果内存分配的不够就要重新分配。

3、由于每个entry中存储了上一个节点的长度，默认是使用一个字节（小于254)，如果上一个节点的长度大于254就要使用5个字节，此时会出现一个问题，如果上一个节点的长度从小于254变成了大于254，那么后续的所有节点就会出现联动效果都要重新分配内存地址，如果列表很长就会极大的影响性能；

此时为此Redis又推出了新的压缩列表，新增设计了两种数据结构：quicklist（Redis 3.2 引入）和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

quicklist

quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

listpack

Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

listpack 还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。

每个 listpack 节点结构主要包含三个方面内容：

1、encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
2、data，实际存放的数据；
3、len，encoding+data的总长度；
listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

实际操作如下：

127.0.0.1:6379> lpush list one
(integer) 1
127.0.0.1:6379> lpush list two
(integer) 2
127.0.0.1:6379> type two
none
127.0.0.1:6379> type list
list
127.0.0.1:6379> OBJECT encoding list
"listpack"

Set

Set的底层使用的是hash和整数集合，如果Set中存储的都是数字，就使用整数集合。hash我们之前已经讲过了，这里只看整数集合

整数集合

当一个 Set 对象只包含整数值元素，且不相同时，就会使用整数集这个数据结构作为底层实现。整数集合是有序的。

struct intset {

    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
}

如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

实际操作如下：

127.0.0.1:6379> sadd myset 1
(integer) 1
127.0.0.1:6379> sadd myset 2
(integer) 1
127.0.0.1:6379> type myset
set
127.0.0.1:6379> OBJECT encoding myset
"intset"

ZSet

Redis 只有在 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。Zset 对象是唯一一个同时使用了两个数据结构来实现的 Redis 对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

跳表

跳表就是增加了一张跳跃表，这个跳跃表将存储的数据分成了很多个段。或者说分成了几个层，这里有点像B+树的结构。层级为3的跳表大致为

我们可以看到一共有三个头指针L0-L2。

L0层一共是5个节点，也是全部的节点，全量链表；

L1层一共有3个节点，分别是2,3,5；

L2层一共有1个节点，是3。

如果我们要找节点3，从L2层就可以直接获得，时间复杂度是O(1)；

如果我们要找节点4，从L2层只有节点3，而4就是3的后置节点，这样查找两次就可以找到；

这种近似二分查找逻辑的存储模式，可以保证跳表的查找复杂度是O(logN)；

那么调表是如何实现多层级的呢？我们来看下调表的数据结构。

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

可以看到，主要就是依靠level数组来保存每层的数据。比如节点3中，level数组就有三个元素，分别是0级，1级，2级的层数据。

Hash

Hash结构就是我们第二个问题说明的，采用是dict、dictht、dictEntry三层，这里就不多说了。注意，当hash对象的所有键值对字符串长度小于64个字节或者键值对的数量小于512个时，hash结构的数据存储类型依然是压缩列表。

127.0.0.1:6379> hset myhash user liubei
(integer) 1
127.0.0.1:6379> hset myhash user guanyu
(integer) 0
127.0.0.1:6379> hget myhash
(error) ERR wrong number of arguments for 'hget' command
127.0.0.1:6379> hget myhash user
"guanyu"
127.0.0.1:6379> hset myhash pass 123
(integer) 1
127.0.0.1:6379> type myhash
hash
127.0.0.1:6379> OBJECT encoding myhash
"listpack"

当我们新增一个字段，值超过了64个字节后

127.0.0.1:6379> hset myhash address Hash结构就是我们第二个问题说明的，采用是dict、dictht、dictEntry三层，这里就不多说了。注意，当hash对象的所有键值对字符串长度小于64个字节或者键值对的数量小于512个时，hash结构的数据存储类型依然是压缩列表C
127.0.0.1:6379> OBJECT encoding myhash
"hashtable"

redis存储对象也一般使用hash

限于篇幅，关于底层数据结构更加详细的内容请阅读这两篇文章：为了拿捏 Redis 数据结构，我画了 40 张图（完整版）-CSDN博客

源码篇--Redis 底层数据结构_redis 字符串存储结构-CSDN博客

四、渐进式扩容

为了实现从键到值的快速访问，前面的章节已经讲到Redis使用了一张Hash表来快速地定位数据。哈希表让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。

key-value 访问过程：

通过 key 计算出对应的哈希值
根据哈希值计算出对应的哈希桶索引
根据索引找到对应 entry，如果是哈希链则挨个查找到对应的 entry
String 类型则 entry 中的 value 就是要查找的值，集合类型则需要在 value 中进一步查找

那么就必定会出现hash冲突的问题，解决问题的方法就是挂链表。同一个hash桶中的元素用一个链表来串起来，这就是为什么dictEntry数据结构中有一个next指针。但是如果链表过长那么查询的效率就会降低，此时就会触发redis的rehash，rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

Rehash

一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
释放哈希表 1 的空间。

到此，我们就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。

渐进式Rehash

rehash有一个问题，就是如果数据量过大，可能rehash的过程很长，那么就会造成一段时间的服务不可用，这是无法承受的。那么渐进式Rehash就出现了，其实也比较容易理解，一次时间太长就分散到多次。简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求。

1、每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到哈希表2中；

2、等处理下一个请求的，再顺带拷贝哈希表1中的下一个索引位置的entries。

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

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

rehash 触发条件

rehash 的触发条件跟负载因子（load factor）有关系，负载因子=哈希表已保存节点的数量/哈希表的大小。触发 rehash 操作的条件，主要有两个：

1、当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作；
2、当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作；

五、架构演进

单机版的Redis

一个应用服务对应单个数据库(mysql)+单机Redis，这种架构比较简单，应对普通的低并发低数据存储要求的应用足够了。

主从模式

一个master+多个slave，一主多从的模式，主从节点直接通过psync命令来完成数据复制，具体过程概括为：

建立连接。从节点启动时，通过配置文件中的信息连接到主节点，并发送SYNC命令请求同步数据。
数据同步。主节点在接收到SYNC命令后，开始进行数据快照的创建（RDB文件）并通过psync命令将快照发送给从节点。从节点接收并加载这个快照，从而获得与主节点的初始数据一致性。
增量同步。初始同步完成后，主节点开始将新的写入操作发送给从节点，以保持从节点数据的实时性。从节点接收并应用这些写入命令。
复制数据。主节点持续将写入命令发送给所有连接的从节点，从节点接收到这些命令后，将它们应用到本地数据集，以维持与主节点的数据一致性。
主从切换。如果主节点发生故障，管理员可以手动或自动将一个从节点提升为新的主节点。其他从节点将连接到新的主节点以获取数据复制。
部分重同步。如果从节点在断线后重新连接主节点，主节点会根据复制偏移量和复制积压缓冲区决定是否执行部分重同步或全量重同步。部分重同步用于补偿从节点在断线期间丢失的数据。

详细可以参考- Redis 主从复制原理分析，这篇就够了_redis主从复制原理-CSDN博客

哨兵模式

主从模式解决了Redis数据安全的问题，一旦主节点挂了，数据不会丢失，启动一个从节点即可（所以如果有两个或两个以上的从节点，可以使用主从从的模式，像链条一样后一个节点复制前一个节点的数据，这样只需要把主节点后面连接的从节点升级为主节点即可）。可以这样的切换还需要人工的干预同时还得时刻关注redis的状态。

哨兵模式就是在主从节点之外又新增加了一个角色，这个哨兵节点顾名思义就是监控主节点的状态，主节点如果挂了，就自动的选择一个从节点，将其升级为主节点；但是哨兵也会有单节点的问题，故而哨兵也做了集群，哨兵之间通过共识算法进行统一操作。