Redis

定制化的数据结构

字符串(SDS)：

字符串保存自身长度，查询长度只需O(1)复杂度；

字符串拼接操作不会带来数组越界异常；

修改字符串不需要重新分配内存空间；

可以保存二进制数据;

SDS结构：

C字符串和SDS之间的区别

SDS特点：

• 常数复杂度获取字符串长度
• 杜绝修改字符串造成的缓冲区溢出
• 减少修改字符串时带来的内存重分配次数
• 二进制安全（可以存储’\0’，而c语言字符串不可以）
• 兼容部分C字符串函数

list

双端链表，一个list可以存储不同类型的值

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：·dup函数用于复制链表节点所保存的值；

·free函数用于释放链表节点所保存的值；

·match函数则用于对比链表节点所保存的值和另一个输入值是否相等。

Redis的链表实现的特性可以总结如下：

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

跳跃表(skip list)：

有序链表。实现简单，查找快速，平均操作复杂度O(logN)。

字典(dict)：

等同于Map。哈希表（dictht）的数据结构为数组链表。

渐进式Rehash：一个dict通常维护了两个哈希表，dictht0作为正常使用的，dictht1作为rehash的临时表。rehash的过程实际上是渐进的，不会一次全部rehash完。比如在增加一个entry时，如果dict在rehash过程中，新增的key会写入到dictht1中，同事dict会将1个entry从dictht0迁移到dictht1，由dict.rehashidx标记rehash的位置。

优雅地实现扩容，减少扩容带来的阻塞。

哈希表结构：

字典结构：

压缩列表(ziplist)：

使用二进制方式保存字符串或整数，节省内存。是列表对象和哈希对象的实现方式之一。

当一个列表键只包含少量列表项， 并且每个列表项要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做列表键的底层实现。

当一个哈希键只包含少量键值对， 并且每个键值对的键和值要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做哈希键的底层实现。

ziplist结构：

总字节数-为节点指针偏移量-节点数-节点…-结束符

ziplist-entry结构：

<encoding&length>

上一个entry大小-数据类型以及长度-数据内容

如果前一个节点长度小于254字节，prev_entry_bytes_length占1字节；否则占5字节，第一个字节用0xFE标记

以上数据结构保证ziplist可以正向遍历，也可以反向遍历。

连锁更新：由于prev_entry_bytes_length特点，插入一个新的节点时，可能导致后面的节点prev_entry_bytes_length值变大，导致后面节点也恰好超过254字节，导致连锁更新，导致插入节点的最差复杂度为O(n^2)。但平均复杂度还是O(N)

整数集合（intset）：

数据结构为有序的int8_t数组,一个或多个int8_t可以组合为int8,int16,int32,int64。所以添加一个元素的时间复杂度是O(N)

升级：如果新的int值超过了最开始定义的元素类型范围，则可以对intset进行数据类型升级

对象

在以上数据结构上，redis基于它们构建了对象系统（字符串对象，列表对象，哈希对象，集合对象，有序集合对象），实现了引用计数器回收机制、访问时间记录等。

对象类型与数据结构对应关系。可以看出每种对象都有多种实现方式。

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象。
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用embstr编码的简单动态字符串实现的字符串对象。
REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串实现的字符串对象。
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的列表对象。
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象。
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象。
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象。
REDIS_SET	REDIS_ENCODING_INTSET	使用整数集合实现的集合对象。
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象。
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象。
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象。

引用计数与内存回收

refcount:

redisobject使用refcount字段来记录引用次数，来判断是否要回收此段内存。

最明显的常见是redis对象共享。redis在初始化服务器时，会创建1万个字符串对象，包括0-9999的所有整数值。当使用这些字符串对象是，服务器就会共享这些对象而不是重新创建。实际上，redis也只会对整数值字符串进行共享，原因是字符串相等的比较非常耗费cpu时间

lru:

lru字段记录key的最后一次访问时间。当服务器打开maxmenmory选项是，使用lru算法回收内存的话需要使用此字段。

Redis数据库

一个redis服务端可以维护多个redis数据库，redis client可以通过SELECT命令选择数据库。每个数据库都为一个redisDb

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

dict：键空间，dictEntry中key为字符串对象指针

expires：键的生存时间。key为指向键空间中对应key的指针（即键空间和过期字典的键都指向同一个键对象），value为一个long long值（毫秒），对应数据库键的过期时间。

过期删除策略

redis使用惰性删除和定期删除两种策略。

• 惰性删除：
  在访问key时判断是否已过期，如果已经过期则删除key
• 定期删除：
  在规定时间内，分多次遍历服务器中各个数据库，从expires中按照redisDb.expires_cursor标记的位置扫描key
  两种模式：
  • ACTIVE_EXPIRE_CYCLE_FAST-快速模式方法执行的时间不会长于EXPIRE_FAST_CYCLE_DURATION毫秒。并且在EXPIRE_FAST_CYCLE_DURATION毫秒内不会再次执行。
  • ACTIVE_EXPIRE_CYCLE_SLOW-慢速模式正常执行方式，方法的执行时限为serverCron每次执行时间的一个百分比，百分比由REDIS_EXPIRELOOKUPS_TIME_PERC定义，默认是25%。
    执行时间：
  • beforesleep
  • serverCron

持久化

RDB

自动保存机制

redisServer.saveparam保存了自动执行BGSAVE的条件。每个配置包含时间和执行次数。redisServer.lastsave记录上次BGSAVE/SAVE时间，redisServer.dirty记录上次保存以来的修改数量，serverCron中会对这些值进行检查，用来判断是否需要执行BGSAVE操作。

BGSAVE会fork一个子进程进行，子进程会带有主进程数据的副本（具体地说其实是写时复制，数据发生修改前为父进程物理地址，某个进程操作某块内存页发生修改时会复制出一块新的内存页存储新数据，旧的内存页留给另一个进程）。相当于fork时刻的数据快照

RDB结构

RDB结构

AOF

步骤

1. 命令追加：redisServer.aof_buf为aof缓冲区，所有写命令都会追加到缓冲区末尾。
2. 文件写入：将缓冲区内容写入AOF文件的操作系统缓存中
3. 文件同步：通过fsync或fdatasync函数将AOF文件保存到磁盘

步骤2和步骤3在flushAppendOnlyFile函数中进行，该函数会在时间事件中和文件事件结束前被调用，通过appendfsync配置来决定是否执行：

• appendfsync always：每次执行完一个命令之后，2 和 3 都会被执行
• appendfsync everysec（默认配置）：3 原则上每隔一秒钟就会执行一次。
• appendfsync no：每次执行完一个命令之后， 2 会执行，3 会被忽略，只会在以下任意一种情况中被执行：
  • Redis 被关闭
  • AOF 功能被关闭
  • 系统的写缓存被刷新（可能是缓存已经被写满，或者定期保存操作被执行。完成依赖 OS 的写入，一般为 30 秒左右一次）

AOF文件重写

避免aof文件无限扩大，redis会通过读取服务器当前数据库，来重写构造aof文件。

aof同样可以在子进程中进行。此时主进程会创建一个AOF重写缓冲区，保存aof异步重写期间的操作，在异步重写完成后会阻塞地将所有内容写入到新aof文件中

事件

文件事件：套接字操作的抽象。可大致理解为每次单独的客户端请求。

时间事件：redis服务器中一些需要在给定时间执行的操作。如serverCron

文件事件

基于Reactor模式

• 使用IO多路复用（select,epoll,evport,kqueue）监听多个套接字
• 根据套接字操作产生相应的文件事件，调用关联的事件处理器处理

高并发

Redis根据操作系统类型的选择合适的IO模型，其中最让人称道的是Epoll支撑下的事件驱动模型(Reactor模型)。Epoll可以支持大量的链接（理论上线是INT类型的最大值），并以O(1)复杂度通知用户进程IO事件。这两点为Redis高并发打下了坚实的基础。

线程安全

Redis的操作都是线程安全的，大部分用户指令都是原子的。原因很简单，Redis是单线程模型。不适合在主进程执行的操作(比如说RDB、AOF重写)，它选择使用子进程进行处理（子进程拷贝父进程数据）。

集群

Redis3.0之后提供Redis Cluster功能，配合redis-trib工具，使用者可以轻松搭建一个Redis集群。Redis集群支持动态扩容缩容，支持主从互备，支持自动地故障转移。

数据一致性分析

数据一致性，Redis要么明确告知客户端请求失败，要么正确响应客户端请求并且持久化结果。

单机持久化

Redis提供两种持久化方式分别是：RDB和AOF。需要说明的一点是写入文件并不代表持久化成功，还需要将文件同步到磁盘。

RDB

RDB指的是Redis将内存中的用户数据持久化到磁盘。这就注定RDB只能在一定时间间隔的情况执行。Redis支持时间间隔和数据修改次数两种维度出发RDB。当然我们也可以通过执行SAVE或者BGSAVE命令显示地持久化数据。显而易见，以上方式总是无法避免部分最新的数据无法持久化到磁盘。

AOF

AOF指的是Redis记录所有的写操作命令，并且持久化。AOF持久化有三个级别

no：AOF文件同步交给操作系统决定;

everysec：每隔一秒执行一次文件同步；

always：写入文件立即同步。

虽然always级别最消耗性能，但是它似乎能够保证数据的一致性。不幸的是，它也不能保证数据绝对的一致性。原因如下：

1.无法以事务的形式写AOF文件和执行写操作。一旦机器在写AOF文件和执行写操作中间的某一时刻崩溃，都会导致数据的不一致性。Mysql使用二阶段提交解决这个问题。

2.文件同步到磁盘过程并非原子操作。mysql同步磁盘使用”double write”解决这个问题。

主从数据一致性

Redis支持主从互备，自动地故障转移。如果主从之间能够保证数据一致性，那我们也不需要担心持久化造成的数据不一致。不幸的是主从互备并不能保证数据一致性。

1. 宕机。虽然多台机器同时宕机的概率极低。但我们不能忽略这种可能(墨菲定律)。
2. 网络故障。主服务器主动将所有写操作发给从服务器。当网络通信不畅时，就会出现主从不同步。即使网络恢复正常，主服务器也不会将从服务器未接收到的命令发给从服务器。Mysql主从解决方案，从服务器以发送确认信号的方式确保主从一致。
3. 过期Key。从服务器不会主动删除过期Key。即使我们访问从服务期的过期Key，从服务器将过期key返回给客户端。
   在单机版Redis中，存在两种删除策略：
   惰性删除：服务器不会主动删除数据，只有当客户端查询某个数据时，服务器判断该数据是否过期，如果过期则删除。
   定期删除：服务器执行定时任务删除过期数据，但是考虑到内存和CPU的折中（删除会释放内存，但是频繁的删除操作对CPU不友好），该删除的频率和执行时间都受到了限制。
   在主从复制场景下，为了主从节点的数据一致性，从节点不会主动删除数据，而是由主节点控制从节点中过期数据的删除。由于主节点的惰性删除和定期删除策略，都不能保证主节点及时对过期数据执行删除操作，因此，当客户端通过Redis从节点读取数据时，很容易读取到已经过期的数据。
   Redis 3.2中，从节点在读取数据时，增加了对数据是否过期的判断：如果该数据已过期，则不返回给客户端；将Redis升级到3.2可以解决数据过期问题。
4. 延迟与不一致问题
   由于主从复制的命令传播是异步的，延迟与数据的不一致不可避免。如果应用对数据不一致的接受程度程度较低，可能的优化措施包括：优化主从节点之间的网络环境（如在同机房部署）；监控主从节点延迟（通过offset）判断，如果从节点延迟过大，通知应用不再通过该从节点读取数据；使用集群同时扩展写负载和读负载等。
   在命令传播阶段以外的其他情况下，从节点的数据不一致可能更加严重，例如连接在数据同步阶段，或从节点失去与主节点的连接时等。从节点的slave-serve-stale-data参数便与此有关：它控制这种情况下从节点的表现；如果为yes（默认值），则从节点仍能够响应客户端的命令，如果为no，则从节点只能响应info、slaveof等少数命令。该参数的设置与应用对数据一致性的要求有关；如果对数据一致性要求很高，则应设置为no。

HA

主从

主从模式就是N个redis实例，可以是1主N从，也可以N主N从（N主N从则不是严格意义上的主从模式了，后续的集群模式会说到，N主N从就是N+N个redis实例。）

主从模式的一个作用是备份数据，这样当一个节点损坏（指不可恢复的硬件损坏）时，数据因为有备份，可以方便恢复。

另一个作用是负载均衡，所有客户端都访问一个节点肯定会影响Redis工作效率，有了主从以后，查询操作就可以通过查询从节点来完成。

1. 一个Master可以有多个Slaves，可以是1主N从。
2. 默认配置下，master节点可以进行读和写，slave节点只能进行读操作，写操作被禁止（readonly）。
3. 不要修改配置让slave节点支持写操作，没有意义，原因一，写入的数据不会被同步到其他节点；原因二，当master节点修改同一条数据后，slave节点的数据会被覆盖掉。
4. slave节点挂了不影响其他slave节点的读和master节点的读和写，重新启动后会将数据从master节点同步过来。
5. master节点挂了以后，不影响slave节点的读，Redis将不再提供写服务，master节点启动后Redis将重新对外提供写服务。
6. 特别说明：该种模式下，master节点挂了以后，slave不会竞选成为master。

主从节点的缺点：

master节点挂了以后，redis就不能对外提供写服务了，因为剩下的slave不能成为master

哨兵Sentinel

一、Sentinel的作用：

1. Master 状态监测
2. 如果Master 异常，则会进行Master-slave 转换，将其中一个Slave作为Master，将之前的Master作为Slave
3. Master-Slave切换后，master_redis.conf、slave_redis.conf和sentinel.conf的内容都会发生改变，即master_redis.conf中会多一行slaveof的配置，sentinel.conf的监控目标会随之调换

二、Sentinel的工作方式:

1. 每个Sentinel以每秒钟一次的频率向它所知的Master，Slave以及其他 Sentinel 实例发送一个 PING 命令
2. 如果一个实例（instance）距离最后一次有效回复 PING 命令的时间超过 down-after-milliseconds 选项所指定的值， 则这个实例会被 Sentinel 标记为主观下线。
3. 如果一个Master被标记为主观下线，则正在监视这个Master的所有 Sentinel 要以每秒一次的频率确认Master的确进入了主观下线状态。
4. 当有足够数量的 Sentinel（大于等于配置文件指定的值）在指定的时间范围内确认Master的确进入了主观下线状态， 则Master会被标记为客观下线
5. 在一般情况下， 每个 Sentinel 会以每 10 秒一次的频率向它已知的所有Master，Slave发送 INFO 命令
6. 当Master被 Sentinel 标记为客观下线时，Sentinel 向下线的 Master 的所有 Slave 发送 INFO 命令的频率会从 10 秒一次改为每秒一次
7. 若没有足够数量的 Sentinel 同意 Master 已经下线， Master 的客观下线状态就会被移除。
   若 Master 重新向 Sentinel 的 PING 命令返回有效回复， Master 的主观下线状态就会被移除。

Redis cluster

基础通信原理

1. redis cluster节点间采取gossip协议进行通信
   跟集中式不同，不是将集群元数据（节点信息，故障，等等）集中存储在某个节点上，而是互相之间不断通信，保持整个集群所有节点的数据是完整的
   维护集群的元数据用得，集中式，一种叫做gossip
   集中式：好处在于，元数据的更新和读取，时效性非常好，一旦元数据出现了变更，立即就更新到集中式的存储中，其他节点读取的时候立即就可以感知到; 不好在于，所有的元数据的跟新压力全部集中在一个地方，可能会导致元数据的存储有压力
   gossip：好处在于，元数据的更新比较分散，不是集中在一个地方，更新请求会陆陆续续，打到所有节点上去更新，有一定的延时，降低了压力; 缺点，元数据更新有延时，可能导致集群的一些操作会有一些滞后
   我们刚才做reshard，去做另外一个操作，会发现说，configuration error，达成一致
2. 10000端口
   每个节点都有一个专门用于节点间通信的端口，就是自己提供服务的端口号+10000，比如7001，那么用于节点间通信的就是17001端口
   每隔节点每隔一段时间都会往另外几个节点发送ping消息，同时其他几点接收到ping之后返回pong
3. 交换的信息
   故障信息，节点的增加和移除，hash slot信息，等等

gossip

gossip协议

gossip协议包含多种消息，包括ping，pong，meet，fail，等等

meet: 某个节点发送meet给新加入的节点，让新节点加入集群中，然后新节点就会开始与其他节点进行通信

redis-trib.rb add-node

其实内部就是发送了一个gossip meet消息，给新加入的节点，通知那个节点去加入我们的集群

ping: 每个节点都会频繁给其他节点发送ping，其中包含自己的状态还有自己维护的集群元数据，互相通过ping交换元数据

每个节点每秒都会频繁发送ping给其他的集群，ping，频繁的互相之间交换数据，互相进行元数据的更新

pong: 返回ping和meet，包含自己的状态和其他信息，也可以用于信息广播和更新

fail: 某个节点判断另一个节点fail之后，就发送fail给其他节点，通知其他节点，指定的节点宕机了

判断节点宕机

如果一个节点认为另外一个节点宕机，那么就是pfail，主观宕机

如果多个节点都认为另外一个节点宕机了，那么就是fail，客观宕机，跟哨兵的原理几乎一样，sdown，odown

在cluster-node-timeout内，某个节点一直没有返回pong，那么就被认为pfail

如果一个节点认为某个节点pfail了，那么会在gossip ping消息中，ping给其他节点，如果超过半数的节点都认为pfail了，那么就会变成fail

从节点过滤

对宕机的master node，从其所有的slave node中，选择一个切换成master node

检查每个slave node与master node断开连接的时间，如果超过了cluster-node-timeout * cluster-slave-validity-factor，那么就没有资格切换成master

这个也是跟哨兵是一样的，从节点超时过滤的步骤

从节点选举

哨兵：对所有从节点进行排序，slave priority，offset，run id

每个从节点，都根据自己对master复制数据的offset，来设置一个选举时间，offset越大（复制数据越多）的从节点，选举时间越靠前，优先进行选举

所有的master node开始slave选举投票，给要进行选举的slave进行投票，如果大部分master node（N/2 + 1）都投票给了某个从节点，那么选举通过，那个从节点可以切换成master

从节点执行主备切换，从节点切换为主节点

与哨兵比较

整个流程跟哨兵相比，非常类似，所以说，redis cluster功能强大，直接集成了replication和sentinal的功能

没有办法去给大家深入讲解redis底层的设计的细节，核心原理和设计的细节，那个除非单独开一门课，redis底层原理深度剖析，redis源码

对于咱们这个架构课来说，主要关注的是架构，不是底层的细节，对于架构来说，核心的原理的基本思路，是要梳理清晰的

总结

Redis一款优秀的缓存中间件。Redis的短板在于它无法保证数据的强一致性。如果您的业务场景对数据一致性要求很高，请不要把Redis当做DB使用。

multi vs pipeline

事务原子性

事务

MULTI, EXEC, DISCARD and WATCH 是Redis事务的基础。用来显式开启并控制一个事务，它们允许在一个步骤中执行一组命令。并提供两个重要的保证：

1. 事务中的所有命令都会被序列化并按顺序执行。在执行Redis事务的过程中，不会出现由另一个客户端发出的请求。这保证 命令队列 作为一个单独的原子操作被执行。
2. 队列中的命令要么全部被处理，要么全部被忽略。EXEC命令触发事务中所有命令的执行，因此，当客户端在事务上下文中失去与服务器的连接，
3. 如果发生在调用MULTI命令之前，则不执行任何commands；
4. 如果在此之前EXEC命令被调用，则所有的commands都被执行。