时间轮(TimeWheel)的设计与实现

2021-11-20 From 博客园 By luceion

一、前言

由于工作的需要,得实现一个用于控制事件超时抛弃的时间轮,由于这是一个相对独立的接口,就总结分享一下。

首先看下需求,此时间轮需要具备下面几个功能:

1)能添加事件,同时附上其超时时间;

2)如果事件正常执行结束,可以显示将其从时间轮上剔除掉,而不需要等时间轮自动移除;

3)如果事件到了设定的超时时间还没执行完,则时间轮需将其剔除掉,并发送一个超时的消息给系统。

基于这样的需求,下面就进行相应的设计和实现。

二、时间轮的设计

基于前面的需求,可以抽象出两个实体来:时钟和槽,其中时钟去负责指针的走动、获取等,而槽用来存储落在各个时间点的事件。同时还需要有三个行为:添加,正常执行的删除,超时的删除和发送消息。有了这样的抽象,首先设计了两个类Clocker和Slot,分别代表时钟和槽;对于几种行为,则需要放到一个主控制类中,设计为TimeWheel,将接口暴露给外部调用。这样系统的静态结构就出来了。

注意到,当事件超时后,需要发送消息出去,以供事件执行相关的处理,这里采用一种面向接口的编程方式。我们先定义一个接口Expiration,里面只有一个方法expired方法。具体的事件需要实现这个接口,这样在我们的时间轮中,只要超时,直接以传入的事件来调用expired方法即能起到发送消息的目的!

对着几部门进行组合,就有了主体框架类图。

对于Clocker类,由于它要控制着时间的不停走动,得是一个单独的线程去完成。其中时间的走动,最好不用Thread.sleep去模拟;可以用一个空的阻塞队列,然后每次调用poll方法,设置间隔时间为超时时间,这样的效果会更好。对于一个新事件,带着超时时间来,需要找到其应在的指针位置,通常的做法就是按超时时间除以预定义好的间隔时间,获取一个偏移量,加上当前位置即可。

对于主类TimeWheel,由于在事件正常结束的时候,可以让事件主动从时间轮中将自己删除掉,因此其add方法就需要返回一个事件所在slot的位置;这样在remove的时候,连带位置信息,就可以方便找到坐在的slot,从中删除该事件。

当超时时间到时,需要将对应的slot中所有元素清除掉,这个工作可以在Slot类中完成,即将对应槽中所有元素取出来放到临时变量中,将当前槽清空,这样就能保证槽中不会有事件积压。对于取出的元素,调用对应的expired方法即可。

基于这样的设计,已经能够满足系统的需要了,并且运行的较为良好。

三、优化

对于上面的设计,细想会有一个可改造的点,就是对于超时元素执行expired方法是在TimeWheel线程里执行的,这样会有问题:

1)不确定expired方法执行所需要花费的时间,这样就有可能影响主线程;

2)如果expired方法出现异常,主线程可能会受到影响。

基于这样的考虑,我们可以把这些事件放到一个阻塞队列里,然后另起一个线程,专门去队列中取元素,执行expired方法。这样就很好的将expired操作和主线程隔离了开来。对于这样的设计,也就是典型的生产者-消费者模型,主线程TimeWheel负责生产数据,设计一个Release线程负责消费数据,仓库用阻塞队列承担,这样就较好的解决了这个问题,起到了优化的作用。

本文来源:博客园,转载请注明出处!

来源地址:https://www.cnblogs.com/luceion/p/5499138.html

君子曰:学不可以已。
《黑匣子思维》
“黑匣子思维”是一种记录和审视失败并从中吸取经验的积极态度。不惧怕面对失败,反而视失败为学习的途径。不会否认过失、推诿责任和想方设法脱身,而会把失败作为样本深入研究。 缺乏从失败中学习的态度、勇气和能力,会对个体或行业带来严重危害。千方百计避免犯错并不是我们的目标,学习如何聪明而有意义地犯错,将每一次失败作为测试我们成绩的机会。
发表感想

© 2016 - 2022 chengxuzhixin.com All Rights Reserved.

浙ICP备2021034854号-1    浙公网安备 33011002016107号