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

HashedandHierarchicalTimingWheelsApaperby

GeorgeVargheseand

TonyLauck.MotivationTimersareimportantfor

Failurerecovery,ratebasedflowcontrol,schedulingalgorithms,controllingpacketlifetimeinnetworksTimermaintenancehighifProcessorinterruptedeveryclocktickFinegranularitytimersareused#outstandingtimersishighEfficienttimeralgorithmsarerequiredtoreducetheoverallinterruptoverhead.Model&PerformanceMeasureRoutinesinthemodelClientInvoked:START_TIMER(Interval,Request_ID,Expiry_Action)STOP_TIMER(Request_ID)Timertickinvoked:PER_TICK_BOOKKEEPINGEXPIRY_PROCESSINGPerformanceMeasureSpace:MemoryusedbythedatastructuresLatency:Timerequiredtobeginandendanyoftheroutinesmentionedabove.CurrentlyUsedTimerSchemesabcdeCanmaintainabsoluteexpirytimeorthetimerintervalSTART_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(n)abcdefmaintainabsoluteexpirytimeSTART_TIMER=O(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1).TreebasedtimersabcdabcdmaintainabsoluteexpirytimeSTART_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).SimpleTimingWheelKeepalargetimingwheelAcurserinthetimingwheelmovesonelocationeverytimeunit(justlikeasecondshandintheclock)IfthetimerintervaliswithinarotationfromthecurrentcurserpositionthenputthetimerinthecorrespondinglocationRequiresexponentialamountofmemorySTART_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1)12345670.HashedTimingWheel1234567024122112#ofroundsremainingSaywheelhas8ticksTimervalue=17Make2roundsofwheel+1moretickSchedulethetimerinthebucket“1”Keepthe#roundswiththetimerAttheexpiryprocessingifthe#rounds>0thenreinsertthetimer.HashedTimingWheelSortedListsineachbucketThelistineachbucketcanbeinsertionsortedHenceSTART_TIMERtakesO(n)timeintheworstcaseIfn<WheelSizethenaverageO(1)UnsortedlistineachbucketListcanbekeptunsortedtoavoidworstcaseO(n)latencyforSTART_TIMERHoweverworstcasePER_TICK_BOOKKEEPING=O(n)Again,ifn<WheelSizethenaverageO(1).HierarchicalTimingWheel123456703575211Hourswheel1234567012345670MinuteswheelSecondswheel13353715.HierarchicalTimingWheelsSTART_TIMER=O(m)wheremisthenumberofwheelsThebucketvalueoneachwheelneedstobecalculatedSTOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1)onavg..ComparisonSTART_TIMERSTOP_TIMERPER_TICKO(1)StraightFwdO(1)O(n)SequentialListO(n)O(1)O(1)TreeBasedO(log(n))O(1)O(1)SimpleWheelO(1)O(1)O(1)HighmemoryrequirementH