- 掌握 Redis 数据类型的底层数据结构
- 理解 IO 模型和 IO 多路复用及 Redis 的实现
- 理解 LRU
- 能够编写 Redis 事务处理,理解弱事务
- 理解 RedisRDB 和 AOF 持久化原理
Redis 数据类型的底层数据结构
简单动态字符串(SDS)
simple dynamic string,默认字符串表示,结构
1 | struct sdshdr { |
好处:
- 长度直接取出,常数复杂度获取字符串长度
- 杜绝缓冲区溢出 free 的作用
链表
list 的底层实现之一就是双向链表,发布、订阅、慢查询、监视器等功能也用到了链表
1 | typedef struct listNode { |
- 链表节点使用 void *指针保存节点值,可以保存各种不同类型的值
字典
字典又称为符号表,关联数组、或映射(map),是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的,通过 key 可以对值进行查找或修改。
哈希表作为底层实现
1 | typedef struct dictht { |
跳跃表
普通单链表查询一个元素的时间复杂度为 O(n),即使该单链表是有序的。
如果你构建一个数据结构,比链表查找还快,就用跳跃表。下面的链表是由上面的链表构建出的跳跃表
查找 46:55 -> 21 -> 55 -> 37 -> 55 -> 46
大数从右找到头,小数从左往右找 和 21 比大小。
插入
初始状态
插入元素2
决定2 是否到L2层,采用百分之50的随机算法,如果中了,则2插入到 L2 层
继续执行随机算法,如果没中则停止插入。插入后表结构为上图,接下来插入33
插入后执行随机算法,33 没有能进入 L2 层,插入结束,接下来插入元素55.
55 中了2次 所以,L2 层 L3 层都需要插入 55 如下图
以此类推,如果规模较小,结果可能不是一个理想的跳跃表,如果元素n的规模很大,就会非常接近于理想的跳跃表。
1 | typedef struct zskiplistNode { |
整数集合
当一个集合 set 只包含整数元素,并且这个集合的元素不多,Redis 就会使用整数聚合 intset 作为该集合的底层实现。整数集合 intset 是 Redis 用于保存整数值的集合抽象数据类型,它可以保存类型为 int_t、int32_t 或者 int64_t 的整数值,并保证集合中不会出现重复元素。
1 | typedef struct intset { |
压缩列表
ziplist 是列表键和哈希键的底层实现之一,当一个列表值包含少量列表项时,并且每个列表项为小整数值或短字符串,那么 Redis 会使用压缩列表做该列表的底层实现。
压缩列表 ziplist 是 Redis 为了节省内存开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点 (entry),每个节点可以保存一个字节数组或者一个整数值。
IO 多路复用
Redis 单线程 性能高 使用 IO 多路复用处理并发。
同步IO 和 异步IO
同步IO: 应用程序要的数据,需要等到操作系统给了才做其他事情。
异步IO: 应用程序要的数据,不需要等到内核控件给它就做别的事情,内核控件会异步通知应用程序,把数据直接给到应用程序。
阻塞 IO 和 非阻塞 IO
阻塞方式下读取或者写入函数将一直等待,而非阻塞方式下,函数会立即返回状态值。等数据准备就绪后,可以采用回调函数(call back) 的方式获得数据。
1 | { |
同步非阻塞 IO
1 | { |
IO多路复用 (IO Multiplexing)
多路分离函数 select (操作系统)
用户首先将需要进行IO操作的 socket 添加到 select 中,然后阻塞等待 select 系统调用返回。当数据到达时,socket 被激活,select 函数返回。用户线程正式发起 read 请求,读取数据并继续执行。
1 | { |
Reactor 设计模式 (反应器)
IO 多路复用,也叫异步阻塞IO模型,通过 Reactor 的方式,可以将用户线程轮询IO操作工作统一交给 handle_events 事件循环进行处理。用户线程注册事件处理器之后可以继续执行做其他工作,而 Reactor 线程负责调用内核的 select 函数,检查 socket 状态。
当 socket 被激活时,通知相应的用户线程,执行 handle_event 函数进行数据读取、处理工作。由于 select 函数是阻塞的,多路 IO 复用模型也被称为异步阻塞 IO 模型。
1 | void UserEventHandler::handle_event() { |
异步 IO (Asynchronous IO)
Redis IO 多路复用技术以及 epoll 实现原理
Redis 是跑在单线程中的,所有的操作都是按照顺序线性执行的,但是读写操作等待用户输入和输出都是阻塞的,所以I/O操作一般不会直接返回,会导致某一文件的 I/O阻塞,导致整个进程无法对其它用户提供服务。所以需要用 I/O 多路复用解决这个问题。
实现机制
select / poll / epoll 都是 IO 多路复用的实现机制。
在 select/poll 时代,服务器进程会每次把所有的连接告诉操作系统(从用户态复制句柄数据到内核态),让操作系统内核去查询这些套接字(socket) 上是否有事件发生,轮询完后,再将句柄数据复制到用户态,让服务器应用程序轮询处理已发生的网络事件,由于资源消耗较大,因此,select/poll 只能处理几千的并发连接。
epoll 是 poll 的一种优化,返回后不需要对所有的连接(fd) 进行遍历,在内核中维持了 连接(fd)的列表。
- 调用 epoll_create() 建立一个 epoll 对象。在epoll 文件系统中为这个句柄对象分配资源
- 调用 epoll_ctl 向 epoll 对象中添加所有的连接的套接字
- 调用 epoll_wait 收集发生的事件的连接
redis epoll 底层实现
当进程调用 epoll_create 方法时,Linux 内核会创建一个 eventpoll 结构体,这个结构体中有两个成员与 epoll 的使用方式密切相关。
1 | struct eventpoll{ |
每一个 epoll 对象都有一个独立的 eventpoll 结构体,用于存放通过 epoll_ctl 方法向 epoll 对象中添加进来的事件。
这些事件都会挂载在红黑树中,如此,重复添加的事件就可以通过红黑树而高效的识别出来,红黑树插入的时间效率是 logn,n 为树的高度。
所有添加到 epoll 中的事件都会与设备网卡建立回调关系,当相应的事件发生时会调用回调方法 ep_poll_callback。
epoll_wait->ep_poll->ep_poll_callback 在 epoll 中,每一个事件都会建立一个 epitem 结构体,然后将 epitem 放到 rdlist中,说白了是将 socket 放到 event 中再将持有 event 的 epitem 放到 rdlist 中,此过程 epoll_wait 阻塞,插入后,所有添加到 epoll 的事件都会与网卡驱动程序建立回调关系,当事件发生时会调用这个回调方法,这个回调方法在内核中叫 ep_poll_callback。
1 | struct epitem{ |
epoll 初始化时,会开辟出 epoll 自己的内核高速 cache 服务于 epoll,安置每一个需要监控的 socket,这些 socket 会以红黑树的形式保存在内核的 cache 里,支持快速查找、插入、删除。这个内核高速 cache 区,就是建立连续的物理内存页,然后在之上建立 slab 层。在初始化时已经分配好了 size 内存对象,每次使用时都是使用空闲的已经分配好的对象。
在内核中,一切皆文件。epoll 向内核注册了一个文件系统,用于存储上述被监控的 socket。当调用 epoll_create 时,就会在 epoll 文件系统里创建一个 file 节点,它只服务于 epoll。
epoll_create 除了建立节点和红黑树存储 socket 外,还会建立一个 list 链表,存储准备就绪的事件,当 epoll_wait 调用时,仅仅观察这个 list 链表里有没有数据即可。有数据就返回,没有数据就 sleep。等到 timeout 时,如果链表没有数据也返回。所以 epoll_wait 非常高效。
相较于 select/poll,epoll 的优势就是不用重复传递 socket 句柄给内核。因为内核在 epoll_ctl 方法中就已经获取了要监控的 socket 句柄列表。
Redis 的缓存淘汰策略
redis 中,允许用户设置最大使用的内存大小 maxmemory,默认为0,即没有指定最大缓存。如果有新数据添加,超过最大内存,则 redis 会崩溃。redis 内存数据集大小上升到一定大小的时候,会执行数据淘汰策略。
淘汰策略 maxmemory-policy
六种数据淘汰策略:
- voltile-lru: 从已设置过期时间的数据集(server.db[i].expires) 中挑选最近最少使用的数据淘汰
- volatile-ttl: 从已设置过期时间的数据集(server.db[i].expires) 中挑选将要过期的数据淘汰
- volatile-random: 从已设置过期时间的数据集(server.db[i].expires) 中任意选择数据淘汰
- allkeys-lru: 从数据集(server.db[i].dict) 中挑选最近最少使用的数据淘汰(默认,一般使用此策略)
- allkeys-random: 从数据集(server.db[i].dict) 中任意选择数据淘汰
- no-enviction(驱逐) : 禁止驱逐数据
LRU 实现原理
LRU 最近最少使用,算法根据数据的历史访问记录来进行淘汰数据,其核心思想是,如果数据最近被访问过,将来被访问的记录也更高。
Java 中可以使用 LinkHashMap 去实现 LRU
算法:利用哈希链表实现
假设,我们使用哈希链表缓存用户信息,目前缓存了5个用户,这5个用户按时间顺序依次从链表右端插入。
此时如果业务访问了用户2,哈希链表中存在用户2的数据,则把它从前去节点和后继节点之间移除,重新插入到链表最右端。最左端还是1.
接下来,业务修改了用户4的信息,则将用户4移到了最右端。最左端仍然是访问最少的用户1
后来业务访问了新的用户6,6在缓存中没有,需要插入到哈希链表,假设此时缓存容量已达上限。必须先删除访问最少的数据,那么位于哈希链表最左端用户1就会被删除。然后把6插入到最右端。
Redis 事务
- Redis 的事务通过 MULTI、EXEC、DISCARD 和 WATCH 这四个命令完成的
- Redis 的单个命令都是原子性的,所以这里需要确保事务性的对象是命令集合
- Redis 将命令集合序列化并确保处于同一事务的命令集合连续且不被打断的执行
- Redis 不支持回滚操作
MULTI: 标记事务块开始
EXEC: 执行所有先前放入队列的命令,事务结束
DISCARD: 清除队列
WATCH: 监控某个 key 的 value,当值变化则队列被清除,可以实现 Redis 的乐观锁
1 | > set s1 11 |
WATCH 演示:
1 | > get s1 |
事务失败处理
语法错误
1 | > multi |
语法错误命令队列都不执行
运行错误
1 | > multi |
a1 是个字符串了,不能被当成数组使用,第一个执行成功了。语法错误和运行错误不同。
Redis 持久化(RDB、AOF)
Redis 是一个内存数据库,为了保证数据的持久性,提供了2个持久化方案
RDB(默认): 通过 snapshotting 完成,快照。当符合一定条件时,Redis 会自动将内存中的数据进行快照并持久化到硬盘中。
触发快照的时机: 符合自定义配置的快照规则,执行save或者bgsave 命令,执行 flushall 命令,执行主从复制操作(第一次)
RDB 规则: save <seconds> <changes>
多少秒内,数据变了多少。
- save “” 表示不使用 RDB
- save 900 1: 表示 15 分钟(900s) 内至少1个键被更改则进行快照。
- save 300 10: 表示 5 分钟内至少有10个键被更改则进行快照
- save 60 10000: 表示 1 分钟内至少有10000个键被更改则进行快照
使用 RDB 方式实现持久化,一旦 Redis 异常退出,就会丢失最后一次快照以后更改的所有数据。如果数据比较重要,可以使用 AOF 方式进行持久化。
RDB 可以最大化 Redis 性能,父进程在保存 RDB 文件时唯一要做的就是 fork 出一个子进程,然后这个子进程就会处理接下来所有的保存工作。但如果数据集较大,fork 会比较耗时,造成服务器在一段时间内停止处理客户端请求。
AOF: append only file,基于 RESP 实现。
默认不开启 AOF
开启 AOF 持久化后,每执行一条会更改 Redis 中的数据的命令,Redis 就会将该命令写入硬盘中的 AOF 文件,这一过程显然会降低 Redis 的性能,但大部分情况下这个影响是可以接受的,使用较快的硬盘可以提高 AOF 性能。
1 | # 通过修改 redis.conf 配置文件中的 appendonly 参数开启 |
RESP Redis 的序列化协议,
AOF 文件中存储的是 redis 的指令。
重写 AOF 优化指令:
Redis 在创建新的 AOF 文件的过程中,会继续将命令追加到现有的 AOF 文件里,保证安全性。一旦新的 AOF 文件创建文笔,Redis 就会从旧 AOF 文件切换到新的 AOF 文件,并开始对新的 AOF 文件进行追加操作。
优化触发条件: 表示当前 aof 文件大小超过上一次 aof 文件大小的百分之多少时进行重写。如果之前没有重写过,启动的时候已 aof 文件大小为准
1 | auto-aof-rewrite-percentage 100 |
限制允许重写最小 aof 文件大小,也就是文件大小小于64mb 时,不需要进行优化
1 | auto-aof-rewrite-min-size 64mb |
Redis 的应用场景
内存数据库 不需要存在 DB 中的数据,登录信息、浏览记录、购物车
缓存服务器 缓存 DB 信息 减少 DB 压力,商品数据信息
session 存储 多个应用服务器
任务队列 list 秒杀系统 请求限流
分布式锁 set nx
应用排行 zset
数据过期 冷热数据
如何选择存储策略 RDB AOF
内存数据库 rdb + aof 数据不丢失
缓存服务器 rdb
不建议只使用 aof ,因为性能差
Redis 的主从复制
配置
主 Redis 数据库不需要额外配置。从 Redis 修改 redis.conf 文件:
1 | # slaveof <masterip> <masterport> |
原理
Redis 的主从同步,分为全量同步和增量同步,只有第一次连接上主机是全量同步,断线重连有可能触发全量同步也有可能是增量同步,master 判断 runid 是否一致。除此之外均是增量同步
全量同步
- 同步快照阶段:Master 创建并发送快照给 slave,slave 载入并解析快照。Master 同时将此阶段产生的新的写命令存储到缓冲区。
- 同步写缓冲阶段:Master 向 slave 同步存储在缓冲区的写操作命令。
- 同步增量阶段:Master 向 Slave 同步写操作指令。
增量同步
- Redis 增量同步指 Slave 完成初始化后开始正常工作时,Master 发生的写操作同步到 Slave 的过程。
- 通常情况下,Master 每执行一个写命令就会向 Slave 发送相同的写命令,然后 Slave 接受并执行。
Redis 哨兵机制
Redis 的哨兵模式是从 2.8 版本后才有。
Sentinel 进程用于监控 Redis 集群中 Master 主服务器工作的状态
在 Master 主服务器发生故障的时候,可以实现 Master 和 Slave 服务器切换,保证系统的高可用。HA
- 监控(Monitoring),哨兵会不断的检查 Master 和 Slave 是否运转正常
- 提醒(Notification) 当被监控的某个 Redis 节点出现问题,哨兵可以通过 API 向管理员或者其他应用程序发送通知。
- 自动故障迁移(Automatic failover) 当一个 Master 不能正常工作时,哨兵会开始一次自动故障迁移操作。
判断故障原理分析
- 每个 Sentinel 进程以每秒一次的频率向整个集群中的 Master 主服务器,Slave 从服务器以及其他 Sentinel 进程发送一个 PING 命令。
- 如果一个实例距离最后一次有效回复 PING 命令的时间超过
down-after-milliseconds
选项指定的值,则这个实例会被 Sentinel 进程标记为主观下线 SDown - 如果一个 Master 主服务器被标记为主观下线 SDown,则正在件事这个 Master 主服务器的所有 Sentinel 进程要以每秒一次的频率确认 Master 主服务器的确进入了主观下线状态
- 在足够多的 Sentinel 进程(大于等于配置文件指定的值) 在指定的时间范围内确认主服务器进入了主观下线状态,则 Master 主服务器会被标记为客观下线状态,ODown。
- 当 Master 主服务器被 Sentinel 进程标记为 客观下线状态 ODown时,Sentinel 进程向下线的 Master 主服务器所有的 Slave 从服务器发送
INFO
指令的频率从10秒一次改为1秒一次。一般情况下,每个 Sentinel 进程会以 10 秒一次的频率向集群中所有 Master主服务器、Slave 从服务器发送INFO
命令。 - 如果没有足够数量的 Sentinel 进程同意 Master 主服务器下线,Master 主服务器的客观下线状态就会被移除。如果 Master 主服务器重新向 Sentinel 进程发送的 PING 命令返回有效回复,Master 主服务器的主观下线状态就会被移除。
自动故障迁移
它会将失效的 Master 其中一个 Slave 升级为新 Master 并让失效 Master 的其他 Slave 改为复制新的 Master,客户端视图连接失效的 Master 时,集群会向客户端返回新 Master 的地址,使得集群可以使用现在的 Master 替换失效 Master。
服务器切换后,Master 的 redis.conf Slave 的 redis.conf 和 Sentinel.conf 的配置文件的内容都会发生相应的改变。
Master 主服务器的 redis.conf 配置文件中会多一行 slaveof 的配置,Sentinel.conf 的监控目标会随之调换。
案例演示
sentinel.conf
1 | # 哨兵 Sentinel 监控的 redis 主节点的 ip port |
启动哨兵服务
1 | ./redis-sentinel sentinel.conf |