浅谈Timewheel的实现、原理以及典型场景

义杰

浅谈 Time wheel 的实现、原理以及典型场景 glmapper 磊叔的技术博客 磊叔的技术博客 聊一聊技术、聊一聊生活 69篇内容 2024年09月09日 18:30 安徽 时间轮 (Time Wheel) 是一种高效的定时器数据结构，广泛应用于需要管理大量定时任务的系统中。它通过将时间划分为多个时间槽，并使用环形数组来表示时间轮盘，从而在常数时间复杂度内执行插入、删除和查找操作。时间轮结构不仅提高了定时任务的管理效率，还显著减少了系统资源消耗。笔者期望通过本篇文章，能够向各位读者详细介绍时间轮的实现方法、工作原理以及典型应用场景，期望可以为读者提供一个比较全面的技术参考。时间轮Time wheel 的实现对比下面是几种 Time Wheel 的实现类型对比实现方式描述实现方法优点缺点简单时间轮（Simple Time Wheel）最基本的时间轮实现，使用单层环形数组来管理定时任务。1、环形数组：使用一个固定大小的数组表示时间轮，每个数组元素表示一个时间槽，存储定时任务的列表。2、时间槽：每个时间槽表示一个固定的时间间隔（如1秒）。3、指针移动：一个指针每隔一个时间间隔移动一次，指向下一个时间槽，并执行该槽中的所有任务。1、实现简单，适用于短时间跨度的定时任务。2、插入、删除和查找任务的时间复杂度为 O(1)。1、时间轮大小固定，难以处理超出时间轮范围的长时间定时任务。2、适用于任务间隔较短的场景，无法精确到毫秒级。层级时间轮（Hierarchical Time Wheels）层级时间轮通过使用多个层级的时间轮来管理不同时间跨度的定时任务。1、多层时间轮：使用多个时间轮，每个时间轮负责一个特定的时间跨度（如毫秒、秒、分钟）。2、任务转移：当一个时间轮的时间槽满时，将任务移到下一个层级的时间轮中。3、指针移动：每个时间轮都有自己的指针，按照不同的时间间隔移动。1、能够处理长时间跨度的定时任务，适用于需要管理不同时间级别的任务。2、插入、删除和查找任务的时间复杂度仍为 O(1)。1、实现复杂，需要处理跨层级任务的移动和管理。2、存储开销较大，每个层级的时间轮都需要分配内存。Hashed Time Wheel使用哈希函数将任务分配到不同的时间槽中1、哈希函数：使用哈希函数计算任务的到期时间，将任务分配到相应的时间槽中。2、时间槽：每个时间槽存储一个任务列表，任务按到期时间排序。3、指针移动：指针按照固定时间间隔移动，执行指针指向槽中的任务。1、任务插入和查找的时间复杂度为 O(1)。2、适用于高并发场景，能够高效管理大量定时任务。1、实现复杂度较高，需要处理哈希冲突和时间槽的扩展。2、需要额外的内存来存储哈希表和任务列表。Distributed Time Wheel用于分布式系统的时间轮实现，能够在多个节点之间协调定时任务的管理1、分布式协调：使用分布式协调服务（如Zookeeper、Consul）来管理时间轮状态和任务分配。2、任务分片：将任务分片分配到不同的节点，每个节点负责管理一部分定时任务。3、指针同步：各节点的时间轮指针需要定期同步，确保任务按时执行。1、适用于大规模分布式系统，具有高可用性和扩展性。2、能够处理跨节点的定时任务，提供可靠的任务调度机制。1、实现复杂度较高，需要处理分布式协调和故障恢复。2、网络通信和协调开销较大，可能影响性能。简单时间轮（Simple Time Wheel） 的代码实现和测试这里笔者提供一个基于 java LinkedList 一个简单实现，来帮助理解 Time Wheel 的基本思路，完整代码如下：packagecom.glmapper.wheeltimer;importjava.util.LinkedList;importjava.util.List;/***@authorglmapper*@date2024/7/10*@description时间轮*@classSimpleTimeWheel*/publicclassSimpleTimeWheel{//时间轮大小privatefinalintwheelSize;//时间轮privatefinalList[]wheel;//当前指针privateintcurrentIndex;publicSimpleTimeWheel(intwheelSize){this.wheelSize=wheelSize;this.wheel=newLinkedList[wheelSize];for(inti=0;i();}this.currentIndex=0;}/***添加任务**@paramtask任务*@paramdelay延迟时间*/publicvoidaddTask(SimpleTimeWheel.Tasktask,intdelay){//计算任务应该放到哪个槽intindex=(currentIndex+delay)%wheelSize;wheel[index].add(task);}/***时间轮转动*/publicvoidtick(){Listtasks=wheel[currentIndex];for(Tasktask:tasks){task.execute();}tasks.clear();currentIndex=(currentIndex+1)%wheelSize;}publicstaticclassTask{privatefinalStringname;publicTask(Stringname){this.name=name;}publicvoidexecute(){System.out.println("Executing:"+name);}}}测试代码：publicstaticvoidmain(String[]args)throwsInterruptedException{SimpleTimeWheeltimeWheel=newSimpleTimeWheel(60);timeWheel.addTask(newTask("Task1"),5);timeWheel.addTask(newTask("Task2"),10);//这里通过一个loop来不断的从timeWheel中捞取待执行的任务，这里的精度是1swhile(true){timeWheel.tick();//fortestThread.sleep(1000);}}简单时间轮的实现比较简单，因此它能支撑的场景也就比较局限；首先是精度问题，如果我们使用毫秒级的精度，则可能轮的划分太细，导致任务列表离散程度较大；如果；轮的范围较小，则单个索引节点上的任务数也可能会非常多。因此为了能够实现对更加精细的控制，就衍生出了使用多个层级的时间轮来管理不同时间跨度的定时任务。层级时间轮（Hierarchical Time Wheels）的代码实现和测试下面是一个 层次时间轮的实现，按照小时、分钟以及秒三个精度进行分层。packagecom.glmapper.wheeltimer;importjava.util.LinkedList;importjava.util.List;/***@ClassnameHierarchicalTimeWheel*@Description层次时间轮*@Date2024/7/1217:47*@Createdbyglmapper*/publicclassHierarchicalTimeWheel{//秒级时间轮privatefinalTimeWheelsecondsWheel;//分钟级时间轮privatefinalTimeWheelminutesWheel;//小时级时间轮privatefinalTimeWheelhoursWheel;publicHierarchicalTimeWheel(){secondsWheel=newTimeWheel(60,1);minutesWheel=newTimeWheel(60,60);hoursWheel=newTimeWheel(24,3600);}publicvoidaddTask(Tasktask,intdelay){if(!secondsWheel.addTask(task,delay)){if(!minutesWheel.addTask(task,delay)){hoursWheel.addTask(task,delay);}}}publicvoidtick(){ListsecondsTasks=secondsWheel.tick();executeTasks(secondsTasks);if(secondsWheel.currentIndex==0){ListminutesTasks=minutesWheel.tick();executeTasks(minutesTasks);if(minutesWheel.currentIndex==0){ListhoursTasks=hoursWheel.tick();executeTasks(hoursTasks);}}}privatevoidexecuteTasks(Listtasks){for(Tasktask:tasks){task.execute();}tasks.clear();}publicbooleanhasTasks(){returnsecondsWheel.hasTasks()||minutesWheel.hasTasks()||hoursWheel.hasTasks();}publicstaticclassTask{privateStringname;publicTask(Stringname){this.name=name;}publicvoidexecute(){System.out.println(newSimpleDateFormat("yyyy.MM.ddHH:mm:ss").format(newDate())+"Executing:"+name);}@OverridepublicStringtoString(){returnname;}}publicstaticclassTimeWheel{privatefinalintwheelSize;privatefinalList[]wheel;privateintcurrentIndex;privatefinalintinterval;publicTimeWheel(intwheelSize,intinterval){this.wheelSize=wheelSize;this.interval=interval;this.wheel=newLinkedList[wheelSize];for(inti=0;i();}this.currentIndex=0;}publicbooleanaddTask(Tasktask,intdelay){intindex=(currentIndex+delay/interval)%wheelSize;if(delaytick(){Listtasks=wheel[currentIndex];currentIndex=(currentIndex+1)%wheelSize;returntasks;}publicbooleanhasTasks(){for(Listtasks:wheel){if(!tasks.isEmpty()){returntrue;}}returnfalse;}}}测试代码：publicstaticvoidmain(String[]args)throwsInterruptedException{HierarchicalTimeWheeltimeWheel=newHierarchicalTimeWheel();timeWheel.addTask(newTask("Task1"),5);timeWheel.addTask(newTask("Task2"),65);timeWheel.addTask(newTask("Task3"),3605);while(timeWheel.hasTasks()){timeWheel.tick();Thread.sleep(1000);}}执行日志：2024.07.1814:25:47Executing:Task12024.07.1814:28:40Executing:Task2#因为debug原因，时间有一些误差...层次时间轮的实现主要包括几个核心类：Task 类：表示需要执行的任务，包含任务名称和执行方法。TimeWheel 类：表示一个时间轮，包含时间槽数组、当前指针位置和时间间隔。主要方法包括添加任务（addTask）、时间的一次跳动最小单位（tick）和检查是否有任务（hasTasks）。HierarchicalTimeWheel 类：表示层级时间轮，包含秒轮、分轮和小时轮。主要方法包括添加任务（addTask）、时间的一次跳动最小单位（tick）和检查是否有任务（hasTasks）。在每个时间轮的 tick 方法中，检查是否需要向上级时间轮传递任务。执行逻辑如下： 1、添加任务时，首先尝试添加到秒轮，如果秒轮满了，尝试添加到分轮，如果分轮也满了，最后添加到小时轮。 2、每秒钟调用一次 tick 方法，首先执行秒轮中的任务，如果秒轮指针转到 0，说明一分钟过去了，执行分轮中的任务；如果分轮指针转到 0，说明一小时过去了，执行小时轮中的任务。 3、任务到期时，调用任务的 execute 方法执行任务。多层级的时间轮实现在精度控制上会更加合理，但相对应的是它需要额外的内存空间来支撑每个层的任务存储。在具体的工程化实践中，笔者上述提供的代码还需要很多的优化，比如处理跨层级任务的移动和管理等。upload successful目前很多时间轮的使用都是基于 netty 中提供的 Hashed Time Wheel。Hashed Time Wheel - netty 提供的实现HashedWheelTimer 本质是一种类似延迟任务队列的实现，适用于对时效性不高的，可快速执行的，大量这样的“小”任务，能够做到高性能，低消耗。在众多时间轮的实现中，目前 netty 中提供的 Hashed Time Wheel 是应用较多的。Netty 中提供 Time Wheel 的主要背景是 Netty 需要管理大量的连接，包括发送超时、心跳检测等等；试想一下，如果为每个链接维护一个 Timer 定时器的话，这将耗费多大大量的资源？upload successful下面是 HashedWheelTimer 的测试：publicstaticvoidmain(String[]args)throwsInterruptedException{HashedWheelTimerwheelTimer=newHashedWheelTimer();wheelTimer.newTimeout(timeout->System.out.println(newSimpleDateFormat("yyyy-MM-ddHH:mm:ss").format(newDate())+"1sdelay"),1,TimeUnit.SECONDS);wheelTimer.newTimeout(timeout->System.out.println(newSimpleDateFormat("yyyy-MM-ddHH:mm:ss").format(newDate())+"10sdelay"),10,TimeUnit.SECONDS);wheelTimer.newTimeout(timeout->System.out.println(newSimpleDateFormat("yyyy-MM-ddHH:mm:ss").format(newDate())+"15sdelay"),15,TimeUnit.SECONDS);TimeUnit.SECONDS.sleep(20);}输出结果2024-07-1815:40:331sdelay2024-07-1815:40:4210sdelay2024-07-1815:40:4715sdelay理解 Timer、TimerTask 和 Timeout1、Timer是一个定时器的接口，定义了管理定时任务的基本方法。Netty 中HashedWheelTimer是Timer接口的具体实现。Timer接口主要有以下方法：newTimeout(TimerTask task, long delay, TimeUnit unit)：创建一个新的定时任务。stop()：停止定时器，并返回所有未到期的任务。2、TimerTask表示一个定时任务。主要包括一个 run 方法，用来接受一个 Timeout 任务。run(Timeout timeout)：当任务到期时执行的逻辑。Timeout参数用于在任务内部获取更多信息和控制。3、Timeout表示一个特定的定时任务，它可以取消任务并查询任务状态。主要方法有：Timer timer()：返回创建此Timeout的Timer。TimerTask task()：返回关联的TimerTask。boolean cancel()：取消此定时任务，如果任务已经执行或取消则返回false。boolean isExpired()：检查任务是否已到期。boolean isCancelled()：检查任务是否已被取消。当调用Timer的newTimeout方法时，会创建一个新的Timeout实例，并将其与一个TimerTask关联。newTimeout方法需要传递一个TimerTask实例、延迟时间和时间单位。当定时器触发时，HashedWheelTimer会调用Timeout对象中关联的TimerTask的run方法，执行定时任务的逻辑。从任务管理的角度，主要是由 Timeout 自己负责，如取消任务（cancel）和检查任务状态（isExpired和isCancelled），Timer对象管理整个时间轮和所有的定时任务。理解 timeouts 队列和 cancelledTimeouts 队列publicclassHashedWheelTimerimplementsTimer{//...privatefinalQueuetimeouts=PlatformDependent.newMpscQueue();privatefinalQueuecancelledTimeouts=PlatformDependent.newMpscQueue();//...}MpscQueue 全称 Multi-Producer Single-Consumer Queue，是一种适合于多个生产者，单个消费者的高并发场景的高性能的，无锁的队列。timeouts 和 cancelledTimeouts 都使用了这个结构。 timeouts： 用于存储所有新提交的定时任务 cancelledTimeouts：用于存储所有被取消的定时任务。当你调用Timeout.cancel()方法取消一个定时任务时，该任务会被加入到cancelledTimeouts队列中从场景来看，MpscQueue 这种结构比较适合时间轮底层任务的存储。首先是多生产者特性，任务的添加在实际的应用中一定是存在多个线程同时提交任务的，前面提到的无锁机制，实际上就是在做入队时使用了 CAS 机制；另一个是单消费者特性，在 netty 的实现中，HashedWheelTimer 内部有一个单一的线程（Worker 线程）负责处理所有定时任务。因此这也限定了 HashedWheelTimer 在一些长任务上的发挥，因为其中的任务是串行执行的。Hashed Time Wheel 分析和应用这里我们以蚂蚁集团开源的 sofabolt 组件中的心跳机制来分析一下 HashedWheelTimer 的应用。sofa bolt 中维护了一个 HashedWheelTimer 实例，代码如下：publicclassTimerHolder{privatefinalstaticlongdefaultTickDuration=10;privatestaticclassDefaultInstance{staticfinalTimerINSTANCE=newHashedWheelTimer(newNamedThreadFactory("DefaultTimer"+defaultTickDuration,true),defaultTickDuration,TimeUnit.MILLISECONDS);}privateTimerHolder(){}/***Getasingletoninstanceof{@linkTimer}. *Thetickdurationis{@link#defaultTickDuration}.**@returnTimer*/publicstaticTimergetTimer(){returnDefaultInstance.INSTANCE;}}SOFABolt心跳相关的处理有两部分：客户端发送心跳，服务端接收心跳处理并返回响应。@OverridepublicvoidheartbeatTriggered(finalChannelHandlerContextctx)throwsException{IntegerheartbeatTimes=ctx.channel().attr(Connection.HEARTBEAT_COUNT).get();finalConnectionconn=ctx.channel().attr(Connection.CONNECTION).get();//如果心跳次数超过最大次数，关闭连接if(heartbeatTimes>=maxCount){//如果心跳次数超过最大次数，关闭连接}else{booleanheartbeatSwitch=ctx.channel().attr(Connection.HEARTBEAT_SWITCH).get();if(!heartbeatSwitch){return;}finalHeartbeatCommandheartbeat=newHeartbeatCommand();//创建本次请求的InvokeFuture对象finalInvokeFuturefuture=newDefaultInvokeFuture(heartbeat.getId(),newInvokeCallbackListener(){//省略},null,heartbeat.getProtocolCode().getFirstByte(),this.commandFactory);finalintheartbeatId=heartbeat.getId();//将InvokeFuture对象加入到当前的Connection中conn.addInvokeFuture(future);//发送心跳，并设置超时时间ctx.writeAndFlush(heartbeat).addListener(newChannelFutureListener(){//...});//设置心跳超时TimerHolder.getTimer().newTimeout(newTimerTask(){@Overridepublicvoidrun(Timeouttimeout)throwsException{InvokeFuturefuture=conn.removeInvokeFuture(heartbeatId);if(future!=null){future.putResponse(commandFactory.createTimeoutResponse(conn.getRemoteAddress()));future.tryAsyncExecuteInvokeCallbackAbnormally();}}},heartbeatTimeoutMillis,TimeUnit.MILLISECONDS);}}当客户端接收到IdleStateEvent时会调用上面的heartbeatTriggered方法。 在Connection对象上会维护心跳失败的次数，当心跳失败的次数超过系统的最大次时，主动关闭Connection。如果心跳成功则清除心跳失败的计数。同样的，在心跳的超时处理中同样使用Netty的Timer实现来管理超时任务（和请求的超时管理使用的是同一个Timer实例）。RpcHeartbeatProcessor是SOFABolt对心跳处理的实现，包含对心跳请求的处理和心跳响应的处理（服务端和客户端复用这个类，通过请求的数据类型来判断是心跳请求还是心跳响应）。如果接收到的是一个心跳请求，则直接写回一个HeartbeatAckCommand（心跳响应）。如果接收到的是来自服务端的心跳响应，则从Connection取出InvokeFuture对象并做对应的状态变更和其他逻辑的处理：取消超时任务、执行Callback。如果无法从Connection获取InvokeFuture对象，则说明客户端已经判定心跳请求超时。总结本篇主要介绍了几种不同时间轮的实现及优缺点对比，并给出了简单时间轮和层级时间轮的简单代码实现，以帮助读者理解相关概念。此外笔者基于 Netty 中的 HashedWheelTimer 实现进行了一些概念的解释，并简单分析了 HashedWheelTimer 在应用场景上的一些局限性；最后基于 sofabolt 的心跳机制介绍了 HashedWheelTimer 的一个具体的应用案例，以期望读者可以加深印象。总的来说，时间轮作为一种处理延迟任务的结构，它可以在较低的内存消耗下，实现准实时的延迟任务管理和执行，从简单时间轮、层次时间轮或者是hash 时间轮的实现机制来看，一般是基于数组+链表的方式实现，因此整体在任务添加和任务调度上的时间复杂度也控制的不错。