Redis

《Redis设计与实现》

版本: 2.9

简单动态字符串(SDS)

SDS与C的字符串区别:

长度提前计算
杜绝缓冲区溢出 + 提前分配空间策略 + 惰性空间释放
二进制安全. C中的字符串以空字符结尾,所以不能存带有空字符的二进制数据

链表

双端链表

字典

Value可以存任何类型的值(指针、uint64、int64)
可以为不同的字典设置不同的类型特定函数
支持rehash操作. 它里面有两个table,rehash时换着用

MurmurHash算法优点在于: 即使输入的键是有规律的,算法仍能给出一个很好的随机分布性

扩展和缩小哈希表的工作通过rehash完成

伸缩时机:

申: 1.1: 服务器目前没有在执行BGSAVE或BGREWRITEAOF,并且当前负载因子大于等于1 1.2: 服务器目前在执行BGSAVE或BGREWRITEAOF,并且当前负载因子大于等于5
缩: 当前负载因子小于0.1

渐进式rehash: 在字典非常大时用的上,思路是等到真正对键开始处理的时候才会进行rehash这个键. 查询的时候如果在ht[0]里没找到后还会去ht[1]里找. 久而久之,ht[0]最终会变成空表

跳跃表

有序数据结构,通过在每个节点中维持多个指向其它节点的指针从而达到快速访问节点的目的

Redis将其用在: 有序集合键、集群节点中作为内部数据结构

整数集合

使用时机: 当一个集合值包含整数元素,并且这个集合的元素数量不多时就会用到

存储: 统一用int8来存,但可以指定encoding_type,如果是INTSET_ENC_INT16的话,用两个int8来存,以此类推...

整数集合会在当前INTSET_ENC_INTXXX不够用时进行动态升级,但不会降级

压缩列表

使用时机: 当一个列表键值包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串

使用了很精细的压缩算法,将多个元素共同存到同一个Entry里

不过,我本机用的redis-6.x已经不用它来存了,用的是"quicklist". 【猜测】或许是因为"连锁更新"等原因觉得这么省划不来所以换掉的

对象

Redis基于底层数据结构包装出来了对象系统,Redis可以在执行命令之前,根据对象系统来判断一个对象是否可以执行给定的执行命令.

引用计数技术: 内存回收、多个数据库键共享一个对象

对象带有访问时间记录信息,用于判断空转

编码和底层实现: 每个对象只能使用特定的编码(不是所有编码),不同的编码对应不同的底层实现.

编码表

常量说明 REDIS_ENCODING_INT long类型的整数 REDIS_ENCODING_EMBTR embstr编码的简单动态字符串 REDIS_ENCODING_RAW 简单动态字符串 REDIS_ENCODING_HT 字典 REDIS_ENCODING_LINKEDLIST 双端列表 REDIS_ENCODING_ZIPLIST 压缩列表 REDIS_ENCODING_INTSET 整数集合 REDIS_ENCODING_SKIPLIST 跳跃表和字典

对象类型对应编码

类型编码对象 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 使用跳跃表和字典实现的有序集合对象

ZSET

用了"跳跃表"和"字典"两个数据结构来满足"找成员分值"、"ZRANGE"的复杂度为O(1)

类型检查实现

类型特定命名所进行的类型检查是通过redisObject结构的type属性来实现的

内存回收

通过对象里的引用计数

对象共享

为什么Redis不共享包含字符串的对象: 当服务器考虑将一个共享对象设置为键的值对象时,程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同,只有两者完全相同,程序才会将共享对象设置为键的值对象.如果一个共享对象保存的值越复杂,那么在验证两者(即共享对象和目标对象)是否完全相同的时候复杂度也会越高,那么消耗CPU的时间也会越多.

如果共享对象是保存整数值的字符串对象,那么验证操作的复杂度为O(1);
如果共享对象是保存字符串值的字符串对象,那么验证操作的复杂度为O(N);
如果共享对象是包含了多个值(或者对象)的对象,比如列表对象或者哈希对象,那么验证操作的复杂度为O(N^2); 因此,尽管共享更复杂的对象可以节约更多的内存,但受到CPU时间的限制,Redis只对包含整数值的字符串对象进行共享.

对象的空转时长

对象里会有个lru属性,该属性记录了对象最后一次被命令程序访问的时间(OBJECT IDLETIME).

如果服务器打开了maxmemory选项,并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru,那么当回收时会优先释放空转比较高的key

数据库

每个Redis客户端都有自己的目标数据库,默认0

数据库对象中有个叫"键空间"的概念,其实就是个大字典,当前数据库的所有数据都是在这个对象里

如果服务器在读取一个键时发现该键已经过期,然后才执行余下的其他操作

如果有客户端使用WATCH命令监视了某个键,那么服务器在对被监视的键进行修改后,会将这个键标记为脏(dirty), 从而让事务程序注意到这个键已经被修改过

服务器每次修改一个键后,都会对脏(dirty)键计数器的值增1,这个计数器会触发服务器的持久化以及复制操作

超时时间

所有的超时命令最终都会转成"PEXPIREAT"命令来执行.

每个数据库都会专门对"键过期时间"进行存储: key->string key value->expireAt

过期键删除策略

有三种可能的答案:

定时删除: 每建一个过期键就加个timer,timer一到就删
惰性删除: 取键的时候处理
定期删除: 定时器定期扫描

定时删除不考虑,像Redis这种可以存大量键的数据库用这种策略会消耗非常多资源; 惰性删除不会占用额外的CPU资源,但会占用内存,因为没被触发处理的键会一直留着; 定期删除难点在于频率和执行时长的控制;

Redis使用的策略: 惰性(expireIfNeeded) + 定期(activeExpireCycle)

Redis定期删除会限制每次检查"键"、"数据库"的数量

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

RDB: 过期的键不会被新的RDB文件造成影响(会被过滤),载入RDB文件时也会过滤;
AOF: 2.1 当服务器以AOF持久化模式运行时,如果数据库中的某个键已经过期,但它还没有被删除,那么AOF文件不会因为这个过期键而产生任何影响 2.2 当过期键被删除后,程序会向AOF文件追加一条DEL命令 2.3 在执行AOF重写的过程中,程序会对数据库中的键进行检查,已过期的键不会被保存到重写后的AOF文件中
复制: 当服务器运行在复制模式下时,从服务器的过期键删除动作由主服务器控制: 3.1 主服务器在删除一个过期键后,会显示地向所有从服务器发送一个DEL命令,告知从服务器删除这个过期键 3.2 从服务器在执行客户端发送的读命令时,即使碰到过期键也不会将过期键删除,而是像未过期的键一样处理. 3.3 从服务器只有在收到主服务器发来的DEL命令后才会删除键其实想表明的是只有收到主服务器的"过期"(DEL)才会认为它应该被"过期"(DEL),从服务器本身不判断这个逻辑

数据库通知

服务器需要设置notify-keyspace-events选项来选择服务器发送通知的类型

"通知"实现: notifyKeyspaceEvent; 参数event、keys、dbid分别是事件名称、产生事件的键 、数据库;

RDB持久化(默认方式)

功能: 将某个时间点上的数据库状态保存到一个RDB文件(压缩过的二进制)中.

触发时机: 配置的定期(BGSABE)或手动执行(SAVE)

适合场景: 冷备份(定期备份)

"定期"的默认配置:

save 900 1		# If at least 1 key is changed within 900 seconds, a snapshot will be taken
save 300 10		# If at least 10 keys are changed within 300 seconds, take a snapshot
save 60 10000	# If at least 10000 keys are changed within 60 seconds, take a snapshot

SAVE(rdbSave): 阻塞进程,直到RDB文件创建完毕为止. BGSAVE(rdbSave): 非阻塞

Q: 如果之前配的是RDB,重启之前改成AOF会怎样? A: RDB文件的载入工作是在服务器启动时自动执行的,所以Rdis没有专门用于载入RDB文件的命令,只要检测到存在就自动载入. 另外,因为AOF文件的更新频率会比RDB高,所以如果服务器开启了AOF,那么会有限使用AOF来还原数据库状态. 只有在AOF关闭时,服务器才会使用RDB文件来还原数据库状态. 结论: 切换到AOF没问题,只要你AOF文件内容没错就行了 PS: 载入RDB文件的实际工作由rdbLoad函数完成

定时RDB

通过dirty字段(不是对象上的,是redisServer的)来计算进行了多少次修改.

Redis服务器周期性操作函数serverCron默认每隔100ms就会执行一次,该函数会对服务器进行维护,其中有一个就是检查save所设条件是否满足,满足的话就执行BGSAVE

RDB文件结构

各版本区别: https://github.com/sripathikrishnan/redis-rdb-tools/blob/master/docs/RDB_Version_History.textile

常量: 全大写变量、数据: 小写

REDIS | db_version | database | EOF | check_sum

database: 包含所有数据库以及各个数据库中的键值对数据

例子:

REDIS | db_version | database0 | database3 | EOF | check_sum

解释: 0号和3号数据库为非空,并且database0表示0号数据库的所有键值对,database3表示3号......

每个非空数据库在RDB文件中都可以保存为SELECTDB、db_number、key_value_pairs三个部分:

SELECTDB | db_number | key_value_pairs

如果键有过期时间的话也会保存.

一份完成的RDB文件:

REDIS | db_version | SELECTDB| 0 | pairs | SELECTDB | 3 | paris | EOF | check_sum

key_value_pairs格式:

TYPE | key | value

有过期时间的键的格式:

EXPIRETIME_MS | ms | TYPE | key | value

# 示例
EXPIRETIME_MS | 1388556000000 | REDIS_RDB_TYPE_SET | key | value

不同TYPE的value存储形式也不一样,因为编码不同.

AOF

服务端执行的每个命令都会发送追加到AOF缓冲区.

同步到系统磁盘的策略: always: 将缓冲区所有内容写入并同步到AOF文件 everysec(默认): 将缓冲区所有内容写入到AOF文件,如果上一次同步AOF文件时间距离现在超过1秒钟,那么再进行对AOF文件同步,并且这个同步是由专门的线程进行的 no: 将缓冲区所有内容写入到AOF文件,什么时候同步由操作系统决定

关于写入和同步: 操作系统提供了fsync和fdatasync两个函数,可以强制让操作系统立即将缓冲区中的数据写入到硬盘; 否则操作系统会在内存缓冲区超过指定的时限或被填满时才真正写入磁盘

AOF重写(rewrite): 最简单的实现是直接从数据库读取键的值,然后用模拟客户端命令写入AOF,这样很多函数都是可以复用的,并且省去了分析老AOF文件的复杂度

子进程带有父进程的数据副本

Redis会在重写后继续读取"AOF重写缓冲区"(和AOF缓冲区数据一样)中的内容以保证重写时的老数据的更新

混合持久化(Redis4.0)

混合持久化同样也是通过bgrewriteaof完成的,不同的是当开启混合持久化时,fork出的子进程先将共享的内存副本全量的以 RDB方式写入aof文件,然后在将重写缓冲区的增量命令以AOF方式写入到文件,写入完成后通知主进程更新统计信息,并将新的含有RDB格式和AOF格式的AOF文件替换旧的的AOF文件. 简单的说: 新的AOF文件前半段是RDB格式的全量数据后半段是AOF格式的增量数据

缺点: 兼容性差(不兼容老版本了); 可读性差;

文件事件

定义: 客户端的命令都是文件事件

单队列、有序、同步处理

如果一个Socket同时可读可写,先处理读

文件事件处理器

连接应答处理器、命令请求处理器、命令回复处理器、复制处理器(主从服务器)

一次完整的应答: 假设一个Redis服务器正在运作,那么这个服务器的监听套接字的AE_READABLE事件应该正处于监听状态之下,而该事件所对应的处理器为连接应答处理器. 如果这时有一个Redis客户端向服务器发起连接,那么监听套接字将产生AE_READABLE事件,触发连接应答处理器执行. 处理器会对客户端的连接请求进行应答,然后创建客户端套接字,以及客户端状态,并将客户端套接字的 AE_READABLE事件与命令请求处理器进行关联,使得客户端可以向服务器发送命令请求. 之后,假设客户端向服务器发送一个命令请求,那么客户端套接字将产生AE_READABLE事件,引发命令请求处理器执行,处理器读取客户端的命令内容,然后传给相关程序去执行. 执行命令将产生相应的命令回复,为了将这些命令回复传送回客户端,服务器会将客户端套接字的AE_WRITABLE 事件与命令回复处理器进行关联. 当客户端尝试读取命令回复的时候,客户端套接字将产生AE_WRITABLE事件,触发命令回复处理器执行,当命令回复处理器将命令回复全部写入到套接字之后,服务器就会解除客户端套接字 AE_WRITABLE事件与命令回复处理器之间的关联

时间事件应用实例: serverCron函数

功能: 定期对自身的资源和状态进行检查和调整,从而确保服务器可以长期、稳定地运行,主要工作有:

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

频率: 每秒运行10次

客户端

Redis存的客户端结构:

客户端的套接字描述符
客户端的名字
客户端的标志值
指向客户端正在使用的数据库的指针,以及该数据库的号码
客户端当前要执行的命令、命令的参数、命令参数的个数,以及指向命令实现的函数的指针
客户端的输入缓冲区和输出缓冲区
客户端的复制状态信息,以及进行复制所需的数据结构
客户端执行BRPOP、BLPOP等列表阻塞命令时使用的数据结构
客户端的事务状态,以及执行WATCH命令时用到的数据结构
客户端执行发布与订阅功能时用到的数据结构
客户端的身份验证标志
客户端的创建时间,客户端和服务器最后一次通信的时间,以及客户端的输出缓冲区大小超出的软性限制(soft limit)的时间

服务端

客户端执行命令到服务端以及响应流程:

客户端解析程序命令并生成协议然后发送到服务端
服务端读取套接字中协议格式的命令请求,并将其保存到客户端状态的输入缓冲区里
对输入缓冲区中的命令进行分析,提取出命令请求中包含的命令参数,以及命令参数的个数,然后分别将参数和参数个数保存到客户端状态的argv属性和argc属性里面
调用命令执行器,执行客户端指定的命令

服务器时间缓存

Redis会缓存unixtime、mstime,精度分别是秒级、毫秒级,每100毫秒会更新一次(serverCron)

初始化服务器

步骤:

创建RedisServer类型实例
载入配置选项
初始化服务器数据结构. 比如: clients、db、lua环境、pubsub_channels等等. PS: 当initServer函数执行完毕之后,服务器将打印Redis的图标到控制台
还原数据库状态 PS: 当服务器完成数据库状态还原工作之后,服务器将打印载入并还原数据库状态耗时
执行事件循环(loop)

旧版本(2.8以前)复制功能的实现

两种方式: 同步(sync)和命令传播(command propagate)

同步:

从向主发送SYNC
主执行BGSAVE生成RDB文件,并用缓冲区记录后续执行命令
BGSAVE完成后将RDB文件给从
将缓冲区里的命令发给从

命令传播: 其实就是增量...

缺点:

主每次都需要BGSAVE
每次断线后都需要重新走RDB全量
从每次都要重新载入RDB

新版(2.8以后)复制功能实现

通过保存主从服务器的复制偏移量(字节)来精确需要同步的数据

通过一个默认为1MB的"复制积压缓冲区"来控制是否执行这个"精确增量同步". 也就是说, 落后了太久的从库走旧版的同步流程

建议的"复制积压缓冲区"最小大小计算公式: second * write_size_per_second. 其中second为从库断线后重连上主所需的平均时间. PS: 为了安全起见,可以将复制积压缓冲区的大小设为2*second*write_size_per_second,这样能保证绝大部分断线情况都能用部分"重(chong)同步"来处理

SALVEOF命令实现

从绑定主实现步骤:

设置从的master_host、master_port
建立Socket
发送PING. 这步用来检查Socket的读写状态是否正常

心跳检测

在命令传播阶段,从默认会以每秒一次的频率向主发送命令: REPLCONF ACK <replication_offset>; 其中replication_offset是从服务器当前的复制偏移量. 发送心跳有三个作用:

检测主从服务器的网络连接状态
辅助实现min-slaves状态. 只是一个配置,如果slaves数量小于min-slaves时,主将拒绝执行写命令
检测命令丢失

Sentinel

介绍: Sentinel收Redis的高可用性解决方案: 由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器,以及这些主属下的所有从,并在被监视的主进入下线状态时自动将它的某个从升级为新的主

启动并初始化Sentinel

启动步骤:

初始化服务器
将普通Redis服务器使用的代码替换成Sentinel专用代码
初始化Sentinel状态
根据给定的配置文件,初始化Sentinel的监视主服务器列表
创建连向主服务器的网络连接

Sentinel本身就是一个运行在特殊模式下的Redis服务器,但很多功能都不用

对于每个被Sentinel监视的主服务器来说,Sentinel会创建两个连向主的异步网络连接:

命令连接,专门用于向服务器发送命令
订阅连接,专门用于订阅主服务器的__sentinel__:hello频道 PS: 在Redis目前的发布与订阅功能中,被发送的信息都不会保存在Redis服务器里,如果在信息发送时,想要接收信息的客户端不在线或者断线,那么这个客户端就会丢失这条信息. 所以为了不丢失__sentinel__:hello频道任何信息,Sentinel必须专门用一个订阅连接来接收该频道的信息另一方面,除了订阅频道之外,Sentinel还必须向主发送命令以此来与主通信,所以还必须向主创建命令连接因为Sentinel需要与多个实例创建多个网络连接,所以Sentinel使用的是异步连接

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

# Server
...
run_id: 76xxxxxxxxxxxxxxxxxxxxxxxx
...

# Replication
role:master

...
slave0:ip=127.0.0.1,port=11111,state=online,offset=43,lag=0
slave0:ip=127.0.0.1,port=22222,state=online,offset=43,lag=0
slave0:ip=127.0.0.1,port=33333,state=online,offset=43,lag=0

...
# Other sections
...

所以从服务器信息是Sentinel和主通信拿到的

Sentinel每十秒向从服务器发送INFO命令:

# Server
...
run_id: 32bexxxxxxxxxxxxxxxxxxx
...
# Replication
role: slave
master_host: 127.0.0.1
master_port: 6379
master_link_status: up
slave_repl_offset: 11887
slave_priority: 100
# Other sections
...

Sentinel每两秒一次通过命令连接向所有被监视的主和从发送命令: PUBLISH__SENTINEL__:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_ip>,<m_port>,<m_epoch>"

s_: Sentinel本身信息 -- s_epoch: Sentinel当前的配置纪元
m_: 如果正在监视的是主,那么这些参数记录的是主的信息；如果正在监视的是从,那么这些参数记录的是从正在复制的主的信息 -- m_epoch: 主当前的配置纪元

Sentinel同样会接收PUBLISH__SENTINEL__:hello频道的信息,用于知道以及被知道监控这个Redis实例的Sentinel PS: 等于这个机制会让Sentinel互相同步监控者的信息,所以配多个Sentinel的时候不需要手动配置对方

当Sentinel通过频道信息发现一个新的Sentinel时,它不仅会为新Sentinel在sentinels字典中创建相应的实例结构,还会创建一个连向新Sentinel的命令连接,而新Sentinel也会同样创建连向这个Sentinel的命令连接,最终所有Sentinel会相互连接使用命令连接相连的各个Sentinel可以通过向其他Sentinel发送命令请求来进行信息交换

Sentinel检测主观下线状态

频率: 一秒一次

每个Sentinel配的主观下线配置(down-after-milliseconds)可能不同

当接收到了足够数量的已下线判断后,Sentinel就会将从服务器判定为客观下线

当主被判断客观下线时,监视这个下线的主的各个Sentinel会进行协商,选举出一个领头Sentinel(Leader),并由它对下线主执行故障转移操作

选领头Sentinel的规则和方法:

每个Sentinel都有资格被选中
每次选举完后,纪元(epoch)会加一
每个人都有投票的机会,并且投了后在这个纪元里就不能改
每个发现主进入客观下线的Sentinel都会要求其他Sentinel将自己设置为局部领头
当一个Sentinel(Source)向另一个Sentinel(Target)发送SENTINEL is-master-down-by-addr命令,并且命令中的runid参数不是*符号而是Source的运行ID时,表示Source要求Target将Source设置为Target的局部Leader
设置局部领头是先到先得
Target在接收到SENTINELis-master-down-by-addr命令后将向Source返回一条命令回复,回复中的 leader_runid参数和leader_epoch参数分别记录了Target的局部Leader的运行ID和配置纪元
Source在接收到Target返回的命令回复之后会检查回复中leader_epoch参数的值和自己的配置纪元是否相同,如果相同那么Source继续取出回复中的leader_runid参数,如果leader_runid值和Source 的运行ID一致,那么表示Target将Source设置成了局部Leader
如果有某个Sentinel被半数以上的Sentinel设置成了局部Leader,那么这个Sentinel就成为了领头 Sentinel
因为Leader产生需要半数以上Sentinel的支持,并且每个Sentinel在每个配置纪元里面只能设置一次局部Sentinel,所以在一个配置纪元里里面出现一个Leader
如果在限定时限内没有一个Sentinel被选举为Leader,那么将在一段时间之后再次进行选举,直到选出Leader

PS: 就是Raft算法的leader election

故障转移

Leader Sentinel将对已下线的主执行故障转移操作:

在已下线主服务器属下的所有从里,挑出一个从并将其转移为主
将已下线主的属下的所有从的主改为这个新的主
将已下线的主设置为新的主的从

新的主怎么挑选出来的:

删除列表中所有处于下线或断线状态的从
删除列表中最近五秒内没有回复过Leader的INFO命令的从
删除所有与已下线主连接断开超过down-after-millseconds*10毫秒内的从. PS: 这步保证列表中剩余的从都没有过早地与主断开. 换句话说,列表中剩余的从保存的数据都是比较新的
根据从的优先级排序
相同最高优先级的从会根据"复制偏移量"再排序
如果"最高优先级"、"复制偏移量"都一样,根据ID顺序排并取最小

集群

集群模式下的函数

集群模式下的serverCron函数还会调用特有的clusterCron函数. 它会负责执行在集群模式下需要执行的常规操作,例如向集群中其他节点发送Gossip消息,检查节点是否断线,检查是否需要对下线节点进行自动故障转移等

集群数据结构

redisClient结构和clusterLink结构的相同之处在于它们都有自己的套接字描述符和输入、输出缓冲区,这两个结构的区别在于redisClient结构中的套接字和缓冲区是用于连接客户端的,而clusterLink结构中的套接字和缓冲区是用于连接节点的

Cluster命令实现

A --> B: 发送MEET消息
B --> A: 返回PONG消息
A --> B: 返回PING消息

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

槽指派

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

每个集群节点负责的槽都会互相转告给其它节点

槽都分配好后集群才会进入上线状态

PS: 16384二级制表示为0100 0000 0000 0000

重新分片

工具: redis-trib

步骤:

redis-trib对目标节点发送CLUSTER SETSLOT <slot> IMPORTING <source_id>命令,让目标节点准备好从源节点导入属于槽slot的键值对
redis-trib对源节点发送CLUSTER SETSLOT <slot> MIGRATING <target_id>命令,让源节点准备好将属于槽slot的键值对迁移至目标节点
redis-trib向源节点发送CLUSTER GETKEYSINSLOT <slot><count>命令,获得最多count个属于槽slot的键值对的键名(key name)
对于步骤3获得的每个键名,redis-trib都向源节点发送一个 MIGRATE <target_ip><target_port><key_name>0<timeout>命令,将被选中的键原子地从源节点迁移至目标节点
重复执行步骤3和步骤4,直到源节点保存的所有属于槽slot的键值对都对被迁移至目标节点为止
redis-trib向集群中的任意一个节点发送CLUSTER SETSLOT <slot>NODE<target_id>命令,将槽slot指派给目标节点,这一指派信息会通过消息发送至整个集群,最终集群中的所有节点都会知道槽slot已经指派给了目标节点 PS: 如果涉及多个槽,那么redis-trib将对每个给定的槽分别执行上面给出的步骤

重新分片期间,源节点接收到客户端请求处理方式:

源节点会先在自己的数据库里面查找指定的键,如果找到的话,就直接执行客户端发送的命令
相反地,如果源节点没能在自己的数据库里面找到指定的键,那么这个键有可能已经被迁移到了目标节点, 源节点将向客户端返回一个ASK错误,指引客户端转向正在导入槽的目标节点,并再次发送之前想要执行的命令

ASK错误和MOVED错误的区别

ASK错误和MOVED错误都会导致客户端转向,它们的区别在于:

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

Redis Cluster中的主从

设置从节点: CLUSTER REPLICATE <node_id>

因为和单机Redis服务器的复制功能使用了相同的代码,所以让从复制主相当于先从发送命令SLAVEOF

一个节点称为从节点,最终集群中的所有节点都会知道某个从节点正在复制某个主节点

故障检测

集群中每个节点都会定期地向集群中的其他节点发送PING,如果接收PING消息的节点没有在规定时间内向发送PING消息的节点返回PONG消息,那么它就会被发送PING消息的节点标记为疑似下线(probable fail)

集群中的各个节点会通过互相发送消息的方式来交换集群中各个节点的状态信息. 当一个主节点A通过消息得知主节点B认为主节点C进入了疑似下线状态时,主节点A会在自己的clusterState.nodes字典中找到主节点C所对应的clusterNode结构,并将主节点B的下线报告添加到clusterNode结构的fail_reports里

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

选举新主节点

和Sentinel中选Leader非常相似,因为两者都是基于Raft算法的领头选举(leader election)方法来实现的

集群节点之间的消息

五种:

MEET: 将MEET的对象接入到当前集群中
PING: 每个一秒钟会从已知节点列表中随机选五个节点,然后对最长时间没有发送过PING消息的节点发PING消息用来检测是否在线; 此外,如果节点A最后一次收到节点B发送的PONG消息的时间,距离当前时间已经超过了节点A的cluster-node-timeout选项设置时长的一半,那么节点A也会向节点B发送PONG消息,这可以防止节点A因为长时间没有随机选中节点B作为PING消息的发送对象而导致对节点B的信息更新滞后
PONG: 收到MEET、PING消息后都会返回PONG; 另外,可以通过向集群广播自己的PONG消息来让集群的节点立即刷新关于这个节点的信息. 比如"故障转移"场景
FAIL: 某个A节点判断B节点已经进入FAIL状态时,会像集群广播一条关于节点B的FAIL消息
PUBLISH: 当节点收到PUBLISH命令时,节点会执行这个命令并向集群广播一条PUBLISH消息,所有接收到这条消息的节点都会执行相同的PUBLISH命令 PS: 这是Redis的一个功能,就是PUB|SUB的作用,具体看文档

一条消息分消息头(header)和消息正文(data)组成

Redis Gossip实现

举个发送PING和返回PONG消息的例子,假设一个包含A、B、C、D、E、F六个节点的集群里:

节点A向节点D发送PING消息,并且消息里面包含了节点B和节点C的信息,当节点D收到这条PING消息时,它将更新自己对节点B和节点C的认识
之后,节点D将向节点A返回PONG消息,并且消息里面包含了节点E和节点F的消息,当节点A收到这条PONG消息时, 它将更新自己对节点E和节点F的认识

FAIL消息的实现

当集群里的主节点A将主节点B标记为下线时会向集群广播一条关于主节点B的FAIL消息,所有接收到这条FAIL消息的节点都会将主节点B标记为已下线

其实通过Gossip也是可以实现所有节点将主节点B标记为已下线的,但在集群的节点数量比较大的情况下,单纯用Gossip 协议来传播节点的已下线信息会给节点的信息更新带来一定的延迟,所以广播FAIL消息是为了加快速度

独立功能的实现

发布订阅

PS: 执行subscribe命令的客户端会在Redis重启服务的时候直接断连,而Publish的那个不会...

普通订阅和模式订阅数据结构不一样: 普通订阅: key->主题 value->客户端列表模式订阅: 对象: 主题,模式

模式订阅实现: 遍历所有....

事务

当一个客户端切换到事务状态之后,服务器会根据这个客户端发来的不同命令执行不同的操作:

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

每个客户端都有自己的事务状态

Watch实现

watched_keys数据结构: key: redisKey value: watch clients

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

事务的ACID性质

Redis的事务总具有"原子性"、"一致性"、"隔离性",并且当Redis运行在某种特定的持久化模式下时,事务也具有"耐久性" PS: 在AOF的"alway sync"模式下,事务的每条命令在执行成功之后,都会立即调用fsync或fdatasync将事务数据写入到 AOF文件.但是,这种保存是由后台线程进行的,主线程不会阻塞直到保存成功,所以从命令执行成功到数据保存到硬盘之间, 还是有一段非常小的间隔,服务器也有可能出现问题,所以这种模式下的事务也是不持久的 PS: 针对Redis保证了"原子性"我保持观点. 因为Redis在一个事务中途失败了不会自动恢复到以前的数据,所以我觉得它没有做到"原子性". 设想下执行一段MySQL事务,中途碰到个主键冲突后MySQL还继续执行,我们会认为这是"原子"的吗? 再多说一句,提出ACID这种事务模型本身就是为了简化编程模型,一个事务里的所有命令本就是一个单位,如果执行完一个事务后数据会有可能为"中间状态",那太可怕了. -- 违反完成性,永无一致性

Redis的事务和传统的关系型数据库事务的最大区别在于它不支持事务的回滚机制(rollback)

PS: Redis的作者在文档中解释说,不支持事务回滚是因为这种复杂的功能和Redis追求简单高效的设计主旨不相符

Redis是这样保证一致性的:

入队错误: 入队命令中出现了命令不存在或者命令的格式不存在等情况,那么Redis将拒绝执行这个事务
执行错误: 2.1: 这些错误都是些不能在入队时被发现的错误,只会在命令实际执行时被触发 2.2: 即使在事务执行的过程中发生了错误,服务器也不会中断事务的执行,它会继续执行余下的其他命令,并且已执行的命令不会被出错的命令影响
服务器停机: 如果在执行事务的过程中停机,那么根据服务器所使用的持久化模式,可能会出现几种情况: 3.1: 如果服务器运行在五持久化的内存模式下,那么重启之后的数据库将是空白的,因此数据总是一致的 3.2: 在执行事务时,Redis不会中断事务去执行保存RDB的工作,只有在事务执行之后,保存RDB的工作才有可能开始. 所以当RDB模式下的Redis服务器进程在事务中途被杀死时,事务内执行的命令,不管成功了多少,都不会被保存到RDB文件里.恢复数据库需要使用现有的RDB文件,而这个RDB文件的数据保存的是最近一次的数据库快照(snapshot), 所以它的数据可能不是最新的,但只要RDB文件本身没有因为其他问题而出错,那么还原后的数据库就是一致的. 3.3: 因为保存AOF文件的工作在后台线程进行,所以即使是在事务执行的中途,保存AOF文件的工作也可以继续进行, 因此,根据事务语句是否被写入并保存到AOF文件,有以下两种情况发生: 3.3.1: 如果事务语句未写入到AOF文件,或AOF未被SYNC调用保存到磁盘,那么当进程被杀死之后,Redis 可以根据最近一次成功保存到磁盘的AOF文件来还原数据库,只要AOF文件本身没有因为其他问题而出错, 那么还原后的数据库总是一致的,但其中的数据不一定是最新的 3.3.2: 如果事务的部分语句被写入到AOF文件,并且AOF文件被成功保存,那么不完整的事务执行信息就会遗留在AOF文件里,当重启Redis时,程序会检测到AOF文件并不完整,Redis会退出,并报告错误.需要使用 redis-check-aof工具将部分成功的事务命令移除之后,才能再次启动服务器.还原之后的数据总是一致的, 而且数据也是最新的(直到事务执行之前为止)

PS: 当当上数和这本书官网的最新版描述完全不一样: https://redisbook.readthedocs.io/en/latest/feature/transaction.html

Redis是这样保证持久性的: 因为事务不过是用队列包裹起了一组Redis命令,并没有提供任何额外的持久性功能,所以事务的持久性由 Redis所使用的持久化模式决定

在单纯的内存模式下,事务肯定是不持久的
在RDB模式下,服务器可能在事务执行之后、RDB文件更新之前的这段时间失败,所以RDB模式下的Redis事务也是不持久的
在AOF的"always"模式下,事务的每条命令在执行成功之后,都会立即调用fsync或fdatasync将事务数据写入到AOF文件. 但是,这种保存是由后台线程进行的,主线程不会阻塞直到保存成功,所以从命令执行成功到数据保存到硬盘之间,还是有一段非常小的间隔,所以这种模式下的事务也是不持久的.
总结: 非阻塞型的异步就别想保证持久性了.

Lua脚本支持

Jedis使用Redis Lua是先用script eval ${script}让Redis保存这个脚本,Redis会返回这个脚本对应生成的函数名称"f_${SHA1}",然后Jedis每次使用这个函数的时候只需要传"函数名称" + "参数". 所以还是很轻便的

如果服务器设置了lua-time-limit配置选项,那么在每次执行Lua脚本之前都会在Lua环境里面设置一个超时处理钩子,超时处理钩子在脚本运行期间,会定期检查脚本已经运行了多长时间,一旦钩子发现脚本的运行时间已经超过了 lua-time-limit选项设置的时长,钩子将定期在脚本运行的间隙中,查看是否有SCRIPT kill命令或者SHUTDOWN 命令到达服务器

Sort

SORT ${key} BY {pattern}命令: 排序指定key,但根据一个模式匹配的"键族"(就是模式匹配到的所有键)的值来排序例子:

# 生成测试数据
LPUSH uid 1
SET user_name_1 admin
SET user_level_1 9999
LPUSH uid 2
SET user_name_2 jack
SET user_level_2 10
LPUSH uid 3
SET user_name_3 peter
SET user_level_3 25
LPUSH uid 4
SET user_name_4 mary
SET user_level_4 70

# 测试数据长这样:
uid	user_name_{uid}	user_level_{uid}
1	admin			9999
2	jack			10
3	peter			25
4	mary			70


# 排序uid,但根据user_level_{uid}的值来排序
`SORT uid BY user_level_*`

# 按上面的排序来,但返回结果是user_name
`SORT uid BY user_level_* GET user_name_*`

# 按上面的返回user_name,但会存到daxigua这个键里
`SORT uid BY user_level_* GET user_name_* store daxigua`

# 排序uid,但根据user_name_{uid}的值来排序
`SORT uid BY user_name_* ALPHA`

参考: http://doc.redisfans.com/key/sort.html

命令执行顺序: SORT <key> ALPHA DESC BY <by-pattern> LIMIT <offset><count> GET ==> ==> <get-pattern> STORE <store_key> 先手顺序:

SORT APLHA DESC BY
LIMIT
GET
STORE<store_key>

Bit

用的SDS来实现,里面的char array每个元素包含8个bit,所以存、取的时候会要多两步计算,但省了7倍空间

关于扩容: 当setbit操作计算后的下标超过当前char array size的时候,会走正常char array buffer resize 流程

BITCOUNT实现算法:

遍历计算法: 遍历数组每个字符然后累加为1的缺点: 数据量大的时候消耗大. PS: 100MB需要8,589,934,592次计算
查表法: N8bit作为一个单位. 缺点: 典型的空间换时间,但随着"表"要提前计算的位数越多,需要的空间呈几何倍数增长(8位需要数百个字节,16需要数百KB,32需要十多个GB),所以优化也是有上限的
二进制位统计算法(variable-precision SWAR算法): BITCOUNT需要解决的问题--统计一个位数想组中非0二进制位的数量,在数学上称为"计算汉明重量(Hamming Weight)". 该算法通过一系列位移和位运算操作,可以在常数时间内计算多个字节的汉明重量,并不需要使用任何额外的内存算法代码:
```
uint32_t swar(uint32_t i){
    i = (i & 0x55555555) + ((i>>1) & 0x55555555);  // 步骤1
    i = (i & 0x33333333) + ((i>>2) & 0x33333333);  // 步骤2
    i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);  // 步骤3
    i = (i * 0x01010101) >> 24;                    // 步骤4
    return i;
}
```
思路: 我们可以把i的二进制位理解成：长度为32的数组,每个元素取值区间[0,1],每个元素正好能代表这个位是不是1. 所以,问题就可以转化为,求这个数组的和。根据分治法的思想,我们可以把相邻的两个数字相加,得到长度为16的数组, 每个元素取值区间[0,2]。并以此类推,最终求出总和步骤:
1. (i & 0x55555555) + ((i>>1) & 0x55555555): 0x55555555的二进制表示01010101010101010101010101010101. 此时i可理解为长度为32的数组,每个元素取值区间[0,1],元素宽度1bit. 通过与运算,可以求出奇数位元素,i>>1后可以求出偶数位元素. 两者相加,相当于16组2bit整数按位相加,问题就转化成了2bit的二进制加法
2. (i & 0x33333333) + ((i>>2) & 0x33333333): 0x33333333的二进制表示00110011001100110011001100110011. 此时i可理解表示为长度为16的数组,每个元素取值区间[0,2],元素宽度2bit. 通过与运算,可以求出奇数位元素,i>>2后可以求出偶数位元素. 两者相加,相当于8组4bit整数按位相加,问题就转化成了4bit的二进制加法
3. (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F): 0x0F0F0F0F的二进制表示00001111000011110000111100001111. 此时i可理解表示为长度为8的数组,每个元素取值区间[0,4],元素宽度4bit. 通过与运算,可以求出奇数位元素,i>>4后可以求出偶数位元素. 两者相加,相当于4组8bit整数按位相加,问题就转化成了8bit的二进制加法
4. (i * 0x01010101) >> 24: 本来可以继续按16位来分的,但这里的4个8bit相加存在简便运算,所以就停止继续分治了. (i * 0x01010101) >> 24 ==> (i & 0xFF) + ((i>>8) & 0xFF) + ((i>>16) & 0xFF) + ((i>>24) & 0xFF). 算法推导:
```
 # 将0x01010101转化成多项式表达
 0x01010101 == 2^24 + 2^16 + 2^8 + 2^0 
 # 两边同乘以i
 i * 0x01010101 == i * 2^24 + i * 2^16 + i * 2^8 + i * 2^0
 # 2的乘方运算转化为位移运算
 i * 0x01010101 == (i<<24) + (i<<16) + (i<<8) + (i<<0)
 # 两边同时右移24位
 (i * 0x01010101)>>24 == ((i<<24)>>24) + ((i<<16)>>24) + ((i<<8)>>24) + ((i<<0)>>24)
 # 将左移和右移合并,并考虑溢出(总共32位),最终结果一致
 (i * 0x01010101)>>24 == (i & 0xFF) + ((i>>8) & 0xFF) + ((i>>16) & 0xFF) + ((i>>24) & 0xFF)
```
二进制位统计算法: Redis的实现
1. 查表算法使用键长为8位的表,表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量
2. 至于variable-precision SWAR算法方面,BITCOUNT命令在每次循环中载入128个二进制位,然后调用四次32位variable-precision SWAR算法来计算这个128二进制位的汉明重量在执行命令时会根据二进制位的数量来决定用哪个算法性能: 以100MB=800000000bit来计算,BITCOUNT需要执行六百二十五万次

参考: How to count the number of set bits in a 32-bit integer、variable-precision SWAR 算法详解

监视器

命令: MONITOR

说明: 每当一个客户端向服务器发送一条命令请求时,服务器除了会处理这条命令请求之外,还会将关于这条命令请求的信息发送给所有监视器

服务器在每次处理命令请求之前,都会调用replicationFeedMonitors函数,这个函数将被处理的命令请求的相关信息发送给各个监视器

其它

Redis最多存放2^32次方个Key,Key的内存限制为512MB

SkipList

SkipList介绍以及使用Redis范围搜索等功能

ZipList

ZipList介绍

缓存雪崩

介绍: 由于原有缓存失效,新缓存未到期间(例如: 我们设置缓存时采用了相同的过期时间,在同一时刻出现大面积的缓存过期),所有原本应该访问缓存的请求都去查询数据库了,而对数据库CPU和内存造成巨大压力,严重的会造成数据库宕机.从而形成一系列连锁反应,造成整个系统崩溃.

解决:

具有相同过期时间的Key在过期时间上加点随机数;

如果是缓存服务器宕机了,考虑主备;

查库时限流

特殊情况考虑本地缓存

缓存穿透

介绍: 缓存穿透是指用户查询数据,在数据库没有,自然在缓存中也不会有.这样就导致用户查询的时候,在缓存中找不到,每次都要去数据库再查询一遍,然后返回空(相当于进行了两次无用的查询).这样请求就绕过缓存直接查数据库,这也是经常提的缓存命中率问题

解决:

如果查询也为空,直接设置一个默认值存放到缓存

根据缓存数据Key的规则.例如我们公司是做机顶盒的,缓存数据以Mac为Key,Mac是有规则,如果不符合规则就过滤掉,这样可以过滤一部分查询.在做缓存规划的时候,Key有一定规则的话,可以采取这种办法.这种办法只能缓解一部分的压力,过滤和系统无关的查询,但是无法根治

采用布隆过滤器将所有可能存在的数据哈希到一个足够大的BitSet中,不存在的数据将会被拦截掉,从而避免了对存储系统的查询压力.

如果是需要登录的接口的话,网关可以给用户做限流

Redis缓存击穿

介绍: 某个热点的key失效,大并发集中对其进行请求,就会造成大量请求读缓存没读到数据,从而导致高并发访问数据库。

解决: 不要失效

缓存预热

解决: 写程序跑预热

一致性Hash算法

介绍(CSDN)(暂时没找到更好的博客)

Redis回收算法

LRU(Least Recently Used,最近最久未使用算法)
- 源码介绍(博客园)
- 缺点: 新加入的节点有可能会立马被删掉
LFU(Least Frequently Used,最不经常使用算法)
- 缺点: 需要额外的数据结构,开销有点大
FIFO(First in First out,先进先出)

我的设计: 新加入的节点score为1,每次执行LRU之后会将所有活下来的key的score按照一定比例降低(向下取整). 每次淘汰时直接按score顺序淘汰

LRU和LFU的区别: LFU算法是根据在一段时间里数据项被使用的次数选择出最少使用的数据项,即根据使用次数的差异来决定。而LRU是根据单纯使用时间的差异来决定的

Redis内存淘汰策略

noeviction(默认): 当内存不足以容纳新写入数据时,新写入操作会报错
allkeys-lru(常用)：当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的 key
allkeys-random：当内存不足以容纳新写入数据时,在键空间中,随机移除某个 key
volatile-lru：当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,移除最近最少使用的 key
volatile-random：当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,随机移除某个 key
volatile-ttl：当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,有更早过期时间的 key 优先移除

Redis主从数据同步相关

Redis主从复制原理学习总结 - 运维笔记(博客园)

分布式锁

SET EX PX NX + 校验唯一随机值

例子: SET product:10001 true ex 10 nx # 当产品10001不存在时,设置10s的锁

EX seconds: 将键的过期时间设置为 seconds
PX millisecounds: 将键的过期时间设置为 milliseconds
NX: 只在键不存在的时候,才对键进行设置操作
XX: 只在键已经存在的时候,才对键进行设置操作

PS: 主从情况下,就算主挂了,只要数据复制到了从就能保证安全性

RedLock: 容错

参考: https://mp.weixin.qq.com/s?__biz=MzIyMjIxMjM3MQ==&mid=2247484112&idx=1&sn=8b1088ac8596fedca19afe9b66093fdc&chksm=e831baacdf4633baf1b286887fa1bdec232300ea733ee6c198815d5ae354941379aa3d04cc7d#rd

客户端先获取「当前时间戳T1」
客户端依次向这5个Redis实例发起加锁请求(用SET命令),且每个请求会设置超时时间(毫秒级,要远小于锁的有效时间), 如果某一个实例加锁失败(包括网络超时、锁被其它人持有等各种异常情况),就立即向下一个Redis实例申请加锁
如果客户端从>=3个(大多数)以上Redis实例加锁成功,则再次获取「当前时间戳T2」,如果 T2 - T1 <锁的过期时间(这步很重要). 此时,认为客户端加锁成功,否则认为加锁失败
加锁成功,去操作共享资源(例如修改MySQL某一行,或发起一个API请求)
加锁失败,向「全部节点」发起释放锁请求(前面讲到的 Lua 脚本释放锁)

"限流"实现代码

Redis官方文档

需求: 限制用户在x秒内请求y次

now = int(time.time())
x = 60
y = 10

redis_key = str(now - (now % x)) // 主要代码

count = client.incr(redis_key)

if count >= y:

缺点: 没有考虑到滑动窗口

Files

Redis设计与实现.md

Latest commit

History