这篇文章主要介绍“Java如何实现时间轮算法”，在日常操作中，相信很多人在Java如何实现时间轮算法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java如何实现时间轮算法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

考虑这样的一个场景，当前你有1000个任务，要让这1000个任务每隔几分钟触发某个操作。要是实现这样的需求，很多人第一想法就是弄一个定时器。但是1000个任务就是1000个定时器，一个定时器是一个线程。为了解决这个问题，就出现了时间轮算法。

时间轮简介：时间轮方案将现实生活中的时钟概念引入到软件设计中，主要思路是定义一个时钟周期（比如时钟的12小时）和步长（比如时钟的一秒走一次），当指针每走一步的时候，会获取当前时钟刻度上挂载的任务并执行。

一个环形数组存储时间轮的所有槽(看你的手表),每个槽对应当前时间轮的最小精度

超过当前时间轮最大表示范围的会被丢到上层时间轮,上层时间轮的最小精度即为下层时间轮能表达的最大时间(时分秒概念)

每个槽对应一个环形链表存储该时间应该被执行的任务

需要一个线程去驱动指针运转,获取到期任务

以下给出java 简单手写版本实现

代码实现

时间轮主数据结构

/***@authorapdoer*@version1.0*@date2021/3/2219:31*/@Slf4jpublicclassTimeWheel{/***一个槽的时间间隔(时间轮最小刻度)*/privatelongtickMs;/***时间轮大小(槽的个数)*/privateintwheelSize;/***一轮的时间跨度*/privatelonginterval;privatelongcurrentTime;/***槽*/privateTimerTaskList[]buckets;/***上层时间轮*/privatevolatileTimeWheeloverflowWheel;/***一个timer只有一个delayqueue*/privateDelayQueue<TimerTaskList>delayQueue;publicTimeWheel(longtickMs,intwheelSize,longcurrentTime,DelayQueue<TimerTaskList>delayQueue){this.currentTime=currentTime;this.tickMs=tickMs;this.wheelSize=wheelSize;this.interval=tickMs*wheelSize;this.buckets=newTimerTaskList[wheelSize];this.currentTime=currentTime-(currentTime%tickMs);this.delayQueue=delayQueue;for(inti=0;i<wheelSize;i++){buckets[i]=newTimerTaskList();}}publicbooleanadd(TimerTaskEntryentry){longexpiration=entry.getExpireMs();if(expiration<tickMs+currentTime){//到期了returnfalse;}elseif(expiration<currentTime+interval){//扔进当前时间轮的某个槽里,只有时间大于某个槽,才会放进去longvirtualId=(expiration/tickMs);intindex=(int)(virtualId%wheelSize);TimerTaskListbucket=buckets[index];bucket.addTask(entry);//设置bucket过期时间if(bucket.setExpiration(virtualId*tickMs)){//设好过期时间的bucket需要入队delayQueue.offer(bucket);returntrue;}}else{//当前轮不能满足,需要扔到上一轮TimeWheeltimeWheel=getOverflowWheel();returntimeWheel.add(entry);}returnfalse;}privateTimeWheelgetOverflowWheel(){if(overflowWheel==null){synchronized(this){if(overflowWheel==null){overflowWheel=newTimeWheel(interval,wheelSize,currentTime,delayQueue);}}}returnoverflowWheel;}/***推进指针**@paramtimestamp*/publicvoidadvanceLock(longtimestamp){if(timestamp>currentTime+tickMs){currentTime=timestamp-(timestamp%tickMs);if(overflowWheel!=null){this.getOverflowWheel().advanceLock(timestamp);}}}}

定时器接口

/***定时器*@authorapdoer*@version1.0*@date2021/3/2220:30*/publicinterfaceTimer{/***添加一个新任务**@paramtimerTask*/voidadd(TimerTasktimerTask);/***推动指针**@paramtimeout*/voidadvanceClock(longtimeout);/***等待执行的任务**@return*/intsize();/***关闭服务,剩下的无法被执行*/voidshutdown();}

定时器实现

/***@authorapdoer*@version1.0*@date2021/3/2220:33*/@Slf4jpublicclassSystemTimerimplementsTimer{/***底层时间轮*/privateTimeWheeltimeWheel;/***一个Timer只有一个延时队列*/privateDelayQueue<TimerTaskList>delayQueue=newDelayQueue<>();/***过期任务执行线程*/privateExecutorServiceworkerThreadPool;/***轮询delayQueue获取过期任务线程*/privateExecutorServicebossThreadPool;publicSystemTimer(){this.timeWheel=newTimeWheel(1,20,System.currentTimeMillis(),delayQueue);this.workerThreadPool=Executors.newFixedThreadPool(100);this.bossThreadPool=Executors.newFixedThreadPool(1);//20ms推动一次时间轮运转this.bossThreadPool.submit(()->{for(;;){this.advanceClock(20);}});}publicvoidaddTimerTaskEntry(TimerTaskEntryentry){if(!timeWheel.add(entry)){//已经过期了TimerTasktimerTask=entry.getTimerTask();log.info("=====任务:{}已到期,准备执行============",timerTask.getDesc());workerThreadPool.submit(timerTask);}}@Overridepublicvoidadd(TimerTasktimerTask){log.info("=======添加任务开始====task:{}",timerTask.getDesc());TimerTaskEntryentry=newTimerTaskEntry(timerTask,timerTask.getDelayMs()+System.currentTimeMillis());timerTask.setTimerTaskEntry(entry);addTimerTaskEntry(entry);}/***推动指针运转获取过期任务**@paramtimeout时间间隔*@return*/@OverridepublicsynchronizedvoidadvanceClock(longtimeout){try{TimerTaskListbucket=delayQueue.poll(timeout,TimeUnit.MILLISECONDS);if(bucket!=null){//推进时间timeWheel.advanceLock(bucket.getExpiration());//执行过期任务(包含降级)bucket.clear(this::addTimerTaskEntry);}}catch(InterruptedExceptione){log.error("advanceClockerror");}}@Overridepublicintsize(){//todoreturn0;}@Overridepublicvoidshutdown(){this.bossThreadPool.shutdown();this.workerThreadPool.shutdown();this.timeWheel=null;}}

存储任务的环形链表

/***@authorapdoer*@version1.0*@date2021/3/2219:26*/@Data@Slf4jclassTimerTaskListimplementsDelayed{/***TimerTaskList环形链表使用一个虚拟根节点root*/privateTimerTaskEntryroot=newTimerTaskEntry(null,-1);{root.next=root;root.prev=root;}/***bucket的过期时间*/privateAtomicLongexpiration=newAtomicLong(-1L);publiclonggetExpiration(){returnexpiration.get();}/***设置bucket的过期时间,设置成功返回true**@paramexpirationMs*@return*/booleansetExpiration(longexpirationMs){returnexpiration.getAndSet(expirationMs)!=expirationMs;}publicbooleanaddTask(TimerTaskEntryentry){booleandone=false;while(!done){//如果TimerTaskEntry已经在别的list中就先移除,同步代码块外面移除,避免死锁,一直到成功为止entry.remove();synchronized(this){if(entry.timedTaskList==null){//加到链表的末尾entry.timedTaskList=this;TimerTaskEntrytail=root.prev;entry.prev=tail;entry.next=root;tail.next=entry;root.prev=entry;done=true;}}}returntrue;}/***从TimedTaskList移除指定的timerTaskEntry**@paramentry*/publicvoidremove(TimerTaskEntryentry){synchronized(this){if(entry.getTimedTaskList().equals(this)){entry.next.prev=entry.prev;entry.prev.next=entry.next;entry.next=null;entry.prev=null;entry.timedTaskList=null;}}}/***移除所有*/publicsynchronizedvoidclear(Consumer<TimerTaskEntry>entry){TimerTaskEntryhead=root.next;while(!head.equals(root)){remove(head);entry.accept(head);head=root.next;}expiration.set(-1L);}@OverridepubliclonggetDelay(TimeUnitunit){returnMath.max(0,unit.convert(expiration.get()-System.currentTimeMillis(),TimeUnit.MILLISECONDS));}@OverridepublicintcompareTo(Delayedo){if(oinstanceofTimerTaskList){returnLong.compare(expiration.get(),((TimerTaskList)o).expiration.get());}return0;}}

存储任务的容器entry

/***@authorapdoer*@version1.0*@date2021/3/2219:26*/@DataclassTimerTaskEntryimplementsComparable<TimerTaskEntry>{privateTimerTasktimerTask;privatelongexpireMs;volatileTimerTaskListtimedTaskList;TimerTaskEntrynext;TimerTaskEntryprev;publicTimerTaskEntry(TimerTasktimedTask,longexpireMs){this.timerTask=timedTask;this.expireMs=expireMs;this.next=null;this.prev=null;}voidremove(){TimerTaskListcurrentList=timedTaskList;while(currentList!=null){currentList.remove(this);currentList=timedTaskList;}}@OverridepublicintcompareTo(TimerTaskEntryo){return((int)(this.expireMs-o.expireMs));}}

任务包装类(这里也可以将工作任务以线程变量的方式去传入)

@Data@Slf4jclassTimerTaskimplementsRunnable{/***延时时间*/privatelongdelayMs;/***任务所在的entry*/privateTimerTaskEntrytimerTaskEntry;privateStringdesc;publicTimerTask(Stringdesc,longdelayMs){this.desc=desc;this.delayMs=delayMs;this.timerTaskEntry=null;}publicsynchronizedvoidsetTimerTaskEntry(TimerTaskEntryentry){//如果这个timetask已经被一个已存在的TimerTaskEntry持有,先移除一个if(timerTaskEntry!=null&&timerTaskEntry!=entry){timerTaskEntry.remove();}timerTaskEntry=entry;}publicTimerTaskEntrygetTimerTaskEntry(){returntimerTaskEntry;}@Overridepublicvoidrun(){log.info("============={}任务执行",desc);}}

到此，关于“Java如何实现时间轮算法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！