时间轮(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 - 2024 chengxuzhixin.com All Rights Reserved.

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