时间轮定时器的原理和实现

.,HashedandHierarchicalTimingWheels,ApaperbyGeorgeVargheseandTonyLauck,.,Motivation,TimersareimportantforFailurerecovery,ratebasedflowcontrol,schedulingalgorithms,controllingpacketlifetimeinnetworksTimermaintenancehighifProcessorinterruptedeveryclocktickFinegranularitytimersareused#outstandingtimersishighEfficienttimeralgorithmsarerequiredtoreducetheoverallinterruptoverhead,.,Model&PerformanceMeasure,RoutinesinthemodelClientInvoked:START_TIMER(Interval,Request_ID,Expiry_Action)STOP_TIMER(Request_ID)Timertickinvoked:PER_TICK_BOOKKEEPINGEXPIRY_PROCESSINGPerformanceMeasureSpace:MemoryusedbythedatastructuresLatency:Timerequiredtobeginandendanyoftheroutinesmentionedabove,.,CurrentlyUsedTimerSchemes,a,b,c,d,e,CanmaintainabsoluteexpirytimeorthetimerintervalSTART_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(n),a,b,c,d,e,f,maintainabsoluteexpirytimeSTART_TIMER=O(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1),.,Treebasedtimers,a,b,c,d,a,b,c,d,maintainabsoluteexpirytimeSTART_TIMER=O(log(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1),CandegeneratetoalinearlistincaseofequalIntervaltimersSTART_TIMER=O(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1),.,SimpleTimingWheel,KeepalargetimingwheelAcurserinthetimingwheelmovesonelocationeverytimeunit(justlikeasecondshandintheclock)IfthetimerintervaliswithinarotationfromthecurrentcurserpositionthenputthetimerinthecorrespondinglocationRequiresexponentialamountofmemory,START_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1),1,2,3,4,5,6,7,0,.,HashedTimingWheel,1,2,3,4,5,6,7,0,2,4,1,2,2,1,1,2,#ofroundsremaining,Saywheelhas8ticksTimervalue=17Make2roundsofwheel+1moretickSchedulethetimerinthebucket“1”Keepthe#roundswiththetimerAttheexpiryprocessingifthe#rounds0thenreinsertthetimer,.,HashedTimingWheel,SortedListsineachbucketThelistineachbucketcanbeinsertionsortedHenceSTART_TIMERtakesO(n)timeintheworstcaseIfnWheelSizethenaverageO(1)UnsortedlistineachbucketListcanbekeptunsortedtoavoidworstcaseO(n)latencyforSTART_TIMERHoweverworstcasePER_TICK_BOOKKEEPING=O(n)Again,ifnWheelSizethenaverageO(1),.,HierarchicalTimingWheel,1,2,3,4,5,6,7,0,3,5,7,5,2,1,1,Hourswheel,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,Minuteswheel,Secondswheel,.,HierarchicalTimingWheels,START_TIMER=O(m)wheremisthenumberofwheelsThebucketvalueoneachwheelneedstobecalculatedSTOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1)onavg.,.,Comparison,START_TIMER,STOP_TIMER,PER_TICK,O(1),StraightFwd,O(1),O(n),SequentialList,O(n),O(1),O(1),TreeBased,O(log(n),O(1),O(1),SimpleWheel,O(1),O(1),O(1),Highmemoryrequirement,HashedW