文章目录
- redis的过期策略如何实现
- 关于定时器的补充
- 基于优先级队列/堆实现的定时器
- 基于时间轮实现的定时器
redis的过期策略如何实现
注意:不能直接遍历所有的key来判断当前key是否过期,这样子效率非常低,redis整体策略是:定期删除和惰性删除
- 定期删除:每次抽取一部分进行验证过期时间。保证抽取检查过程足够快。为了避免一次性删除大量过期键导致服务器阻塞,Redis将每次执行的删除数量限制在一个较小的范围内。
- 对于定期删除的时间有明确的要求,因为redis是单线程程序,如果扫描过期key消耗的时间太多,就可能导致正常处理请求的命令被阻塞
- 惰性删除:假设这个key已经到了过期时间了,但是暂时还没有删除它,这个key还存在,当客户端尝试访问一个键时,Redis会检查该键是否已过期。如果键已过期,则会立即删除该键并返回空结果(nil)。
通过惰性过期和定期过期策略的结合,Redis可以高效地管理键的过期,并保持内存的合理使用,并且还提供了一系列的内存淘汰策略
注意:redis当中并没有采用定时器的方式来实现过期key的删除,因为如果基于定时器来实现,可能要引入多线程,不符合redis单线程执行流的初衷
关于定时器的补充
redis并没有采取下述的两种定时器方案,但是下述两种都是属于高效的定时器的实现方式
定时器:在某个时间到达之后,执行某些特定的任务
基于优先级队列/堆实现的定时器
优先级队列:按照指定的优先级先进先出,在redis过期key的场景中,可以通过 “过期时间越早,优先级越高”
例子:假设有很多key设置了过期时间,就可以把这些key加入到一个优先级队列当中,指定优先级规则是过期时间早的先出队列,此时队头元素就是最早的要过期的key,此时定时器当中只要分配一个线程,让这个线程去检查队首元素,查看是否过期即可,如果队头元素都没有过期,那么后续元素一定没有过期
注意:
1.扫描线程不需要遍历所有的key,只需要盯住队头元素即可,如果队头元素没有过期,那么后续元素一定没有过期
2.扫描线程检查元素过期时间也不能太频繁,可以根据当前时刻和队头元素的过期时间的差值设置一个等待时间,当时间差不多到了的时候,系统再去唤醒这个扫描线程。此时扫描线程不需要高频扫描队头元素,把CPU的开销也节省下来了
3.但是如果在线程休眠的时候来了一个新任务,该新任务可能过期时间比较早,此时可以在新任务添加的时候,唤醒一下扫描线程,重新检查队头元素,再根据时间差距重新调整阻塞时间
基于时间轮实现的定时器
时间轮算法是通过一个时间轮去维护定时任务,按照一定的时间单位对时间轮进行划分刻度。然后根据任务延时计算任务落在该时间轮的第几个刻度上,如果任务时长超出了刻度数量,则需要增加一个参数记录时间轮需要转动的圈数
优点:实现相对简单
缺点:是无法精确、准时地执行定时任务,只能是近似执行`
时间轮结构
时间轮类似于一个时钟,它和时钟一样是有刻度的,每个刻度大小可以是100ms也可以是1ms,上图的时间轮有6个刻度,每个刻度大小是100ms,也就是每过100ms会顺时针移动一个刻度,走完一圈需要600ms
工作原理:每往时间轮提交一个延时任务,会判断该任务的执行时间要放在哪个刻度上
,比如在时间轮启动后的第100ms,提交了一个延时400ms执行的任务,那么该任务应该放在刻度5上,如果提交了一个延迟700ms执行的任务,那么该任务会放在刻度2上,并且会记录该任务还需要走一圈时间轮才能执行。时间轮每移动一个刻度,就会执行当前刻度上的任务,一个刻度上的任务可能会有多个