前言
文章部分内容来自对 《Redis核心技术与实现》的学习
整体架构
基本设计
- 对于键值数据库而言,基本的数据模型是 key-value 模型。key 一般是 String 类型,而 value 类型则比较多样。在对键值数据库进行选型时,一个重要的考虑因素是它支持的 value 类型。例如,Memcached 支持的 value 类型仅为 String 类型,而 Redis 支持的 value 类型包括了 String、哈希表、列表、集合等。Redis 能够在实际业务场景中得到广泛的应用,就是得益于支持多样化类型的 value。从使用的角度来说,不同 value 类型的实现,不仅可以支撑不同业务的数据需求,而且也隐含着不同数据结构在性能、空间效率等方面的差异,从而导致不同的 value 操作之间存在着差异。
- 对数据做什么操作?PUT/GET/DELETE/SCAN 是一个键值数据库的基本操作集合,此外还有EXISTS 等。当一个键值数据库的 value 类型多样化时,也需要包含相应的操作接口。例如,Redis 的 value 有列表类型,因此它的接口就要包括对列表 的操作。
- 键值对保存在内存还是外存?
- 采用什么访问模式?通过函数库调用的方式供外部应用使用,比如RocksDB;通过网络框架以 Socket 通信的形式对外提供键值对操作,通过网络框架提供键值存储服务,一方面扩大了键值数据库的受用面,但另一方面,也给键值数据库的性能、运行模型提供了不同的设计选择,带来了一些潜在的问题。
- 如何定位键值对的位置?这依赖于键值数据库的索引模块。索引的作用是让键值数据库根据 key 找到相应 value 的存储位置,进而执行操作。一般而言,内存键值数据库(例如 Redis)采用哈希表作为索引,而 RocksDB 则采用跳表作为内存中 key-value 的索引(估计是减少索引占用的磁盘空间,减少索引带来的磁盘io)。
- 内存分配,键值对的增删改往往伴随着内存的分配和回收,Redis 的内存分配器提供了多种选择,分配效率也不一样
- 持久化
键和值用什么结构组织?
哈希表。因为这个哈希表保存了所有的键值对,所以,我也把它称为全局哈希表。
查找过程主要依赖于哈希计算(O(1) 复杂度),和数据量的多少并没有直接关系。但是,当你往 Redis 中写入大量数据后,还是会发现操作有时候会突然变慢了,因为哈希表的冲突问题和 rehash 可能带来的操作阻塞。为了使 rehash 操作更高效,Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2。一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。随着数据逐步增多,Redis 开始执行 rehash,这个过程分为三步:
- 给哈希表 2 分配更大的空间,例如是当前哈希表 1 大小的两倍;
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中; 为了避免copy 过程阻塞用户请求,Redis 采用了渐进式 rehash,每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中。PS:跟redis 通过用户请求顺带清理 过期数据是一样的。
- 释放哈希表 1 的空间。
因为 Redis 的数据类型有很多,而且,不同数据类型都有些相同的元数据要记录(比如最后一次访问的时间、被引用的次数等),所以,Redis 会用一个 RedisObject 结构体来统一记录这些元数据,同时指向实际数据。一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针,这个指针再进一步指向具体数据类型的实际数据所在,当然也有例外,为了节省内存空间,Redis 还对 Long 类型整数和 SDS 的内存布局做了专门的设计。
- 当保存的是 Long 类型整数时,RedisObject 中的指针就直接赋值为整数数据了,这样就不用额外的指针再指向整数了,节省了指针的空间开销。
- 当保存的是字符串数据,并且字符串小于等于 44 字节时,RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域,这样就可以避免内存碎片。
#define REDIS_LRU_BITS 24
typedef struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4; // 编码
unsigned lru:REDIS_LRU_BITS; // 对象最后一次被访问的时间
int refcount; // 引用计数
void *ptr; // 指向实际值的指针,可以指向不同的数据类型
} robj;
底层数据结构
Redis 为什么性能突出呢?一方面因为它是内存数据库,另一方面要归功于它的数据结构。这是因为,键值对是按一定的数据结构来组织的,操作键值对最终就是对数据结构进行增删改查操作,所以高效的数据结构是 Redis 快速处理数据的基础。String/List/Hash/Set/SortedSet 是Redis 中value的数据类型,这里说的数据结构 是底层实现,底层数据结构一共有 6 种。可以看到,String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。
持久化/单机高可用
- AOF:记录操作,对命令执行影响小, 但恢复时间较长。
- RDB:记录的是某一时刻的数据,
可以与 mysql 的redo/undo log 对比找找感觉。
AOF
Redis 的持久化主要有两大机制,即 AOF 日志和 RDB 快照
AOF: 我们比较熟悉的是数据库的写前日志(Write Ahead Log, WAL),也就是说,在实际写数据前,先把修改的数据记到日志文件中,以便故障时进行恢复。不过,AOF 日志正好相反,它是写后日志,“写后”的意思是 Redis 是先执行命令,把数据写入内存,然后才记录日志。
- AOF 里记录的是 Redis 收到的每一条命令,这些命令是以文本形式保存的。Redis 在向 AOF 里面记录日志的时候,并不会先去对这些命令进行语法检查。所以,如果先记日志再执行命令的话,日志中就有可能记录了错误的命令。而写后日志这种方式,就是先让系统执行命令,只有命令能执行成功,才会被记录到日志中,否则,系统就会直接向客户端报错。
- 在命令执行后才记录日志,所以不会阻塞当前的写操作。
AOF 也有两个潜在的风险,都是和 AOF 写回磁盘的时机相关
- 如果刚执行完一个命令,还没有来得及记日志就宕机了,那么这个命令和相应的数据就有丢失的风险。
- AOF 虽然避免了对当前命令的阻塞,但可能会给下一个操作带来阻塞风险。因为AOF 日志也是在主线程中执行的,如果在把日志文件写入磁盘时,磁盘写压力大,就会导致写盘很慢,进而导致后续的操作也无法执行了。
对于这个问题,AOF 机制给我们提供了三个选择控制写入磁盘的时机,对应appendfsync配置 (mysql redolog/binlog都有类似的配置)
- Always,同步写回:每个写命令执行完,立马同步地将日志写回磁盘;
- Everysec,每秒写回:每个写命令执行完,只是先把日志写到 AOF 文件的内存缓冲区,每隔一秒把缓冲区中的内容写入磁盘;
- No,操作系统控制的写回:每个写命令执行完,只是先把日志写到 AOF 文件的内存缓冲区,由操作系统决定何时将缓冲区内容写回磁盘。
AOF日志文件太大了怎么办?AOF 重写机制就登场了。
- AOF 重写机制就是在重写时,Redis 根据数据库的现状创建一个新的 AOF 文件。也就是说,读取数据库中的所有键值对,然后对每一个键值对用一条命令记录它的写入。PS:存在一个键值对被多条写命令反复修改的情况,这样一来,一个键值对在重写日志中只用一条命令就行了
- 每次执行重写时,主线程 fork 出后台的 bgrewriteaof 子进程。此时,fork 会把主线程的内存拷贝一份给 bgrewriteaof 子进程,这里面就包含了数据库的最新数据。然后,bgrewriteaof 子进程就可以在不影响主线程的情况下,逐一把拷贝的数据写成操作,记入重写日志。
- 主线程未阻塞,仍然可以处理新来的操作。如果有写操作,除了正在写的AOF 日志,还会再写一份AOF 重写日志。等到bgrewriteaof 拷贝数据的所有操作记录重写完成后,重写日志记录的这些最新操作也会写入新的 AOF 文件,此时,就可以用新的 AOF 文件替代旧文件了。
RDB(Redis DataBase)
把某一时刻的状态以文件的形式写到磁盘上,也就是快照。在做数据恢复时,可以直接把 RDB 文件读入内存,很快地完成恢复。Redis 提供了两个命令来生成 RDB 文件,分别是 save 和 bgsave。
- save:在主线程中执行,会导致阻塞;
- bgsave:创建一个子进程,专门用于写入 RDB 文件,避免了主线程的阻塞,这也是 Redis RDB 文件生成的默认配置。
- 此时,主线程的确没有阻塞,可以正常接收请求,但是,为了保证快照完整性,它只能处理读操作,不能修改正在执行快照的数据。
- Copy-On-Write, COW:为了快照而暂停写操作,肯定是不能接受的。bgsave 子进程是由主线程 fork 生成的,可以共享主线程的所有内存数据。bgsave 子进程运行后,开始读取主线程的内存数据,并把它们写入 RDB 文件。如果主线程要修改一块数据,这块数据就会被复制一份,生成该数据的副本。然后,bgsave 子进程会把这个副本数据写入 RDB 文件。PS:有点 主线程既写AOF 又写AOF 重写日志的感觉。
快照的频率不好把握,如果频率太低,两次快照间一旦宕机,就可能有比较多的数据丢失。如果频繁地执行全量快照,也会带来两方面的开销。一方面,频繁将全量数据写入磁盘,会给磁盘带来很大压力,多个快照竞争有限的磁盘带宽,前一个快照还没有做完,后一个又开始做了,容易造成恶性循环。bgsave 子进程需要通过 fork 操作从主线程创建出来。虽然,子进程在创建后不会再阻塞主线程,但是fork 这个创建过程本身会阻塞主线程,而且主线程的内存越大,阻塞时间越长(所以使用RDB时,单个实例的redis 内存不宜过大)。有什么两全其美的招么?Redis 4.0 中提出了一个混合使用 AOF 日志和内存快照的方法。简单来说,内存快照以一定的频率执行,在两次快照之间,使用 AOF 日志记录这期间的所有命令操作。
虽然 fsync 是由后台子线程负责执行的,但是,主线程会监控 fsync 的执行进度。当主线程使用后台子线程执行了一次 fsync,需要再次把新接收的操作记录写回磁盘时,如果主线程发现上一次的 fsync 还没有执行完,那么它就会阻塞。所以,如果后台子线程执行的 fsync 频繁阻塞的话(比如 AOF 重写占用了大量的磁盘 IO 带宽),主线程也会阻塞,导致 Redis 性能变慢。
Redis 是内存数据库,内存使用量大,如果没有控制好内存的使用量,或者和其他内存需求大的应用一起运行了,就可能受到 swap 的影响,而导致性能变慢。一旦 swap 被触发了,Redis 的请求操作需要等到磁盘数据读写完成才行。
Linux 内核从 2.6.38 开始支持内存大页机制,该机制支持 2MB 大小的内存页分配,而常规的内存页分配是按 4KB 的粒度来执行的。如果采用了内存大页,Redis写时复制时,即使客户端请求只修改 100B 的数据,Redis 也需要拷贝 2MB 的大页。那该怎么办呢?关闭内存大页
主从同步/多机高可用
Redis 提供了主从库模式(副本一致采用强leader模型),主从库同步是如何完成的呢?主库数据是一次性传给从库,还是分批同步?主从间网络中断怎么办?
-
主从库间如何进行第一次同步?当我们启动多个 Redis 实例的时候,它们相互之间就可以通过 replicaof(Redis 5.0 之前使用 slaveof)命令形成主库和从库的关系
- 主从级联模式分担全量复制时的主库压力。一次全量复制中,对于主库来说,需要完成两个耗时的操作:生成 RDB 文件和传输 RDB 文件。如果从库数量很多,而且都要和主库进行全量复制的话,就会导致主库忙于 fork 子进程生成 RDB 文件,进行数据全量同步。fork 这个操作会阻塞主线程处理正常请求,从而导致主库响应应用程序的请求速度变慢。此外,传输 RDB 文件也会占用主库的网络带宽,同样会给主库的资源使用带来压力。那么,有没有好的解决方法可以分担主库压力呢?其实是有的,这就是“主 - 从 - 从”模式。
- 主从库断连怎么办? replication buffer 和 repl_backlog_buffer。repl_backlog_buffer 是一个环形缓冲区,主库会记录自己写到的位置master_repl_offset,从库则会记录自己已经读到的位置slave_repl_offset。主从库的连接恢复之后,从库首先会给主库发送 psync 命令,并把自己当前的 slave_repl_offset 发给主库,主库会判断自己的 master_repl_offset 和 slave_repl_offset 之间的差距。增量复制
主库挂了怎么办? 哨兵其实就是一个运行在特殊模式下的 Redis 进程,三个任务:监控、选主(选择主库)和通知。
- 监控。周期性地给所有的主从库发送 PING 命令,检测它们是否仍然在线运行。如果从库没有在规定时间内响应哨兵的 PING 命令,哨兵就会把它标记为“下线状态”;同样,如果主库也没有在规定时间内响应哨兵的 PING 命令,哨兵就会判定主库下线,然后开始自动切换主库的流程。
- 选主。筛选+打分,在多个从库中,先按照一定的筛选条件,把不符合条件的从库去掉(在线状态、断连次数)。然后,我们再按照一定的规则,给剩下的从库逐个打分(从库优先级、从库复制进度= master_repl_offset-slave_repl_offset 以及从库 ID 号),将得分最高的从库选为新主库。PS:有点k8s 调度的感觉
- 通知。哨兵会把新主库的连接信息发给其他从库,让它们执行 replicaof 命令,和新主库建立连接,并进行数据复制。同时,哨兵会把新主库的连接信息通知给客户端,让它们把请求操作发到新主库上。
切片集群
Redis Cluster 方案采用哈希槽(Hash Slot,接下来我会直接称之为 Slot),来处理数据和实例之间的映射关系。一个切片集群共有 16384 个哈希槽,键值对的 key,按照CRC16 算法计算一个 16 bit 的值;然后,再用这个 16bit 值对 16384 取模。在部署 Redis Cluster 方案时,可以使用 cluster create 命令创建集群,此时,Redis 会自动把这些槽平均分布在集群实例上(当然也可以手动配置)。通过哈希槽,切片集群就实现了数据到哈希槽、哈希槽再到实例的分配。
如何知道哈希槽分布在哪个实例上?Redis 实例会把自己的哈希槽信息发给和它相连接的其它实例,来完成哈希槽分配信息的扩散。当实例之间相互连接后,每个实例就有所有哈希槽的映射关系了。客户端收到哈希槽信息后,会把哈希槽信息缓存在本地。当客户端请求键值对时,会先计算键所对应的哈希槽,然后就可以给相应的实例发送请求了。
在集群中,实例和哈希槽的对应关系并不是一成不变的,会有增删节点、负载均衡等情况, 此时,实例之间还可以通过相互传递消息,获得最新的哈希槽分配信息,但是,客户端是无法主动感知这些变化的。Redis Cluster 方案提供了一种重定向机制,当客户端把一个键值对的操作请求发给一个实例时,如果这个实例上并没有这个键值对映射的哈希槽,那么,这个实例就会给客户端返回下面的 MOVED 命令响应结果,这个结果中就包含了新实例的访问地址。客户端更新本地缓存的哈希槽信息,并向新实例发送操作请求。如果哈希槽对应的数据正在迁移,客户端就会收到一条 ASK 报错信息,于是客户端向新实例发送操作请求,但不会更新本地缓存。
GET hello:key
(error) MOVED 13320 172.16.19.5:6379
GET hello:key
(error) ASK 13320 172.16.19.5:6379
缓冲区
缓冲区在 Redis 中的一个主要应用场景,就是在客户端和服务器端之间进行通信时,用来暂存客户端发送的命令数据,或者是服务器端返回给客户端的数据结果。此外,缓冲区的另一个主要应用场景,是在主从节点间进行数据同步时,用来暂存主节点接收的写命令和数据。缓冲区溢出导致网络连接关闭 和数据丢失。缓冲区溢出,无非就是三个原因:命令数据发送过快过大;命令数据处理较慢;缓冲区空间过小。
淘汰策略
- 不进行数据淘汰 noeviction,一旦缓存被写满了,再有写请求来时,Redis 不再提供服务,而是直接返回错误。
- 在设置了过期时间的数据中进行淘汰 包括 volatile-random、volatile-ttl、volatile-lru、volatile-lfu(Redis 4.0 后新增)。即使缓存没有写满,这些数据如果过期了,也会被删除。
- 在所有数据范围内进行淘汰,包括 allkeys-lru、allkeys-random、allkeys-lfu(Redis 4.0 后新增)。如果一个键值对被删除策略选中了,即使它的过期时间还没到,也需要被删除。当然,如果它的过期时间到了但未被策略选中,同样也会被删除。
为了避免操作链表的开销,Redis 在实现 LRU 策略时使用了两个近似方法:Redis 是用 RedisObject 结构来保存数据的,RedisObject 结构中设置了一个 lru 字段,用来记录数据的访问时间戳;Redis 并没有为所有的数据维护一个全局的链表,而是通过随机采样方式,选取一定数量(例如 10 个)的数据放入候选集合,后续在候选集合中根据 lru 字段值的大小进行筛选。
LFU 缓存策略是在 LRU 策略基础上,为每个数据增加了一个计数器,来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时,首先会根据数据的访问次数进行筛选,把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同,LFU 策略再比较这两个数据的访问时效性,把距离上一次访问时间更久的数据淘汰出缓存。
Redis 在实现 LFU 策略的时候,只是把原来 24bit 大小的 lru 字段,又进一步拆分成了两部分。
- ldt 值:lru 字段的前 16bit,表示数据的访问时间戳;
- counter 值:lru 字段的后 8bit,表示数据的访问次数。8bit 记录的最大值是 255,这样可以吗?Redis 并没有采用数据每被访问一次,就给对应的 counter 值加 1 的计数规则,用计数器当前的值乘以配置项 lfu_log_factor 再加 1,再取其倒数,得到一个 p 值;然后,把这个 p 值和一个取值范围在(0,1)间的随机数 r 值比大小,只有 p 值大于 r 值时,计数器才加 1。PS:总之就是加1kw次才到 255
事务
事务使用场景之一:redis的数据结构各有特点,在某种场景下,一个数据可能要存储多个数据结构,以同时满足对读写性能及特殊的操作命令(比如范围查询、计数等)需求。
127.0.0.1:6379> MULTI # 开启事务
OK
127.0.0.1:6379> DECR a:stock # 将a:stock减1
QUEUED # client 发送命令到服务端 先暂存到一个命令队列中,所以是QUEUED
127.0.0.1:6379> DECR b:stock # 将b:stock减1
QUEUED
127.0.0.1:6379> EXEC # 提交事务并执行
1) (integer) 4
2) (integer) 9
Redis 通过 MULTI、EXEC、DISCARD 和 WATCH 四个命令来支持事务机制,对ACID 的保证情况
- 原子性
- 命令入队时就报错,会放弃事务执行,保证原子性;
- 命令入队时没报错,实际执行时报错,不保证原子性;
- EXEC 命令执行时实例故障,如果开启了 AOF 日志,可以保证原子性。
- 一致性,总结来说,Redis 事务机制对一致性属性是有保证的
- 命令入队时就报错
- 命令入队时没报错,实际执行时报错
- EXEC 命令执行时实例故障,没有开启 RDB 或 AOF,例故障重启后,数据都没有了,数据库是一致的。使用了 RDB 快照,事务命令操作的结果不会被保存到 RDB 快照中,使用 RDB 快照进行恢复时,数据库里的数据也是一致的。使用了 AOF 日志,而事务操作还没有被记录到 AOF 日志时,实例就发生了故障,那么,使用 AOF 日志恢复的数据库数据是一致的。如果只有部分操作被记录到了 AOF 日志,我们可以使用 redis-check-aof 清除事务中已经完成的操作,数据库恢复后也是一致的。
- 不管 Redis 采用什么持久化模式,事务的持久性属性是得不到保证的。
- 隔离性
-
(客户端Y)并发操作在 (客户端X)EXEC 命令前执行,此时,隔离性的保证要使用 WATCH 机制来实现,WATCH 机制的作用是,在事务执行前,监控一个或多个键的值变化情况,当事务调用 EXEC 命令执行时,WATCH 机制会先检查监控的键是否被其它客户端修改了。如果修改了,就放弃事务执行,避免事务的隔离性被破坏。否则隔离性无法保证;
-
(客户端Y)并发操作在 (客户端X)EXEC 命令后执行,此时,隔离性可以保证。因为 Redis 是用单线程执行命令,EXEC 命令执行后,Redis 会保证先把命令队列中的所有命令执行完。
-
影响redis 性能的几大因素
Redis 的网络 IO 和键值对读写是由主线程完成的,网络 IO 有时候会比较慢,但是 Redis 使用了 IO 多路复用机制,避免了主线程一直处在等待网络连接或请求到来的状态,所以,网络 IO 不是导致 Redis 阻塞的因素。键值对的增删改查操作是 Redis 和客户端交互的主要部分,复杂度高的增删改查操作肯定会阻塞 Redis。怎么判断操作复杂度是不是高呢?就是看操作的复杂度是否为 O(N)。
- Redis 中涉及集合的操作复杂度通常为 O(N);
- 集合自身的删除操作同样也有潜在的阻塞风险;释放内存只是第一步,为了更加高效地管理内存空间,在应用程序释放内存时,操作系统需要把释放掉的内存块插入一个空闲内存块的链表,以便后续进行管理和再分配,这个过程本身需要一定时间。在删除大量键值对数据、清空数据库的时候类似。
- 和磁盘交互时的阻塞点:AOF 日志同步写。Redis 采用子进程的方式生成 RDB 快照文件,以及执行 AOF 日志重写操作。但是,Redis 直接记录 AOF 日志时,会根据不同的写回策略对数据做落盘保存。一个同步写磁盘的操作的耗时大约是 1~2ms,如果有大量的写操作需要记录在 AOF 日志中,并同步写回的话,就会阻塞主线程了。
- 从库加载 RDB 文件
Redis 主线程启动后,会使用操作系统提供的 pthread_create 函数创建 3 个子线程,分别由它们负责 AOF 日志写操作、键值对删除以及文件关闭的异步执行。主线程通过一个链表形式的任务队列和子线程进行交互。当收到键值对删除和清空数据库的操作时,主线程会把这个操作封装成一个任务,放入到任务队列中,然后给客户端返回一个完成信息,表明删除已经完成。但实际上,这个时候删除还没有执行,等到后台子线程从任务队列中读取任务后,才开始实际删除键值对,并释放相应的内存空间。因此,我们把这种异步删除也称为惰性删除(lazy free)。和惰性删除类似,当 AOF 日志配置成 everysec 选项后,主线程会把 AOF 写日志操作封装成一个任务,也放到任务队列中。后台子线程读取任务后,开始自行写入 AOF 日志,这样主线程就不用一直等待 AOF 日志写完了。
其它
- 我们在构建计算机硬件系统时,已经把 LLC 和 page cache 放在了应用程序的数据访问路径上,应用程序访问数据时直接就能用上缓存。如果应用程序想要使用 Redis 缓存,我们就要在程序中增加相应的缓存操作代码。所以,我们也把 Redis 称为旁路缓存。
- 全量复制虽然耗时,但是对于从库来说,如果是第一次同步,全量复制是无法避免的,所以一个小建议:一个 Redis 实例的数据库不要太大,一个实例大小在几 GB 级别比较合适,这样可以减少 RDB 文件生成、传输和重新加载的开销。
- 虽然 Redis 的单个命令操作可以原子性地执行,但是在实际应用中,数据修改时可能包含多个操作,至少包括读数据、数据增减、写回数据三个操作,这显然就不是单个命令操作了,那该怎么办呢?Redis 提供了 INCR/DECR 命令,把这三个操作转变为一个原子操作了。如果有更加复杂的判断逻辑或者是其他操作,可以使用Lua 脚本(客户端eval 提交一个lua.script),Redis 会把整个 Lua 脚本作为一个整体执行,在执行的过程中不会被其他命令打断,从而保证了 Lua 脚本中操作的原子性。