Class DeadlineTimerWheel
Based on netty's HashedTimerWheel, which is based on George Varghese and Tony Lauck's paper, 'Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility'. More comprehensive slides are located here.
Wheel is backed by arrays. Timer cancellation is O(1). Timer scheduling might be slightly longer if a lot of timers are in the same tick or spoke. The underlying tick is contained in an array. That array grows when needed, but does not shrink.
Caveats
Timers that expire in the same tick are not ordered with one another. As ticks are fairly coarse resolution normally, this means that some timers may expire out of order.
Note: Not threadsafe.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic interface
Consumer of timer entries as deadline to timerId.static interface
Handler for processing expired timers. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
private long
private static final int
static final long
Represents a deadline not set in the wheel.private int
private final int
private long
private int
private final int
private final long
private final int
private long
private final TimeUnit
private long[]
-
Constructor Summary
ConstructorsConstructorDescriptionDeadlineTimerWheel
(TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel) Construct timer wheel and configure timing with default initial allocation.DeadlineTimerWheel
(TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel, int initialTickAllocation) Construct timer wheel and configure timing with provided initial allocation. -
Method Summary
Modifier and TypeMethodDescriptionboolean
cancelTimer
(long timerId) Cancel a previously scheduled timer.private static void
checkInitialTickAllocation
(int tickAllocation) private static void
checkResolution
(long tickResolution) private static void
checkTicksPerWheel
(int ticksPerWheel) void
clear()
Clear out all scheduled timers in the wheel.long
Time of current tick of the wheel intimeUnit()
s.void
currentTickTime
(long now) Set the current tick of the wheel to examine on the nextpoll(long, org.agrona.DeadlineTimerWheel.TimerHandler, int)
.private long
long
deadline
(long timerId) Get the deadline for the given timerId.void
forEach
(DeadlineTimerWheel.TimerConsumer consumer) Iterate over wheel so all active timers can be consumed without expiring them.private long
increaseCapacity
(long deadline, int spokeIndex) private static int
indexInTickArray
(long timerId) int
poll
(long now, DeadlineTimerWheel.TimerHandler handler, int expiryLimit) Poll for timers expired by the deadline passing.void
resetStartTime
(long startTime) Reset the start time of the wheel.long
scheduleTimer
(long deadline) Schedule a timer for a given absolute time as a deadline intimeUnit()
s.long
The start time tick for the wheel from which it advances.private static int
tickForTimerId
(long timerId) long
Resolution of a tick of the wheel intimeUnit()
s.int
The number of ticks, or spokes, per wheel.long
Number of active timers.private static long
timerIdForSlot
(int tickOnWheel, int tickArrayIndex) timeUnit()
Time unit for the time ticks.
-
Field Details
-
NULL_DEADLINE
public static final long NULL_DEADLINERepresents a deadline not set in the wheel.- See Also:
-
INITIAL_TICK_ALLOCATION
private static final int INITIAL_TICK_ALLOCATION- See Also:
-
tickResolution
private final long tickResolution -
startTime
private long startTime -
currentTick
private long currentTick -
timerCount
private long timerCount -
ticksPerWheel
private final int ticksPerWheel -
tickMask
private final int tickMask -
resolutionBitsToShift
private final int resolutionBitsToShift -
tickAllocation
private int tickAllocation -
allocationBitsToShift
private int allocationBitsToShift -
pollIndex
private int pollIndex -
timeUnit
-
wheel
private long[] wheel
-
-
Constructor Details
-
DeadlineTimerWheel
public DeadlineTimerWheel(TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel) Construct timer wheel and configure timing with default initial allocation. -
DeadlineTimerWheel
public DeadlineTimerWheel(TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel, int initialTickAllocation) Construct timer wheel and configure timing with provided initial allocation.- Parameters:
timeUnit
- for the values used to express the time.startTime
- for the wheel (in givenTimeUnit
).tickResolution
- for the wheel, i.e. how manyTimeUnit
s per tick.ticksPerWheel
- or spokes, for the wheel (must be power of 2).initialTickAllocation
- space allocated per tick of the wheel (must be power of 2).
-
-
Method Details
-
timeUnit
Time unit for the time ticks.- Returns:
- time unit for the ticks.
-
tickResolution
public long tickResolution()Resolution of a tick of the wheel intimeUnit()
s.- Returns:
- resolution of a tick of the wheel in
timeUnit()
s.
-
ticksPerWheel
public int ticksPerWheel()The number of ticks, or spokes, per wheel.- Returns:
- number of ticks, or spokes, per wheel.
-
startTime
public long startTime()The start time tick for the wheel from which it advances.- Returns:
- start time tick for the wheel from which it advances.
-
timerCount
public long timerCount()Number of active timers.- Returns:
- number of currently scheduled timers.
-
resetStartTime
public void resetStartTime(long startTime) Reset the start time of the wheel.- Parameters:
startTime
- to set the wheel to.- Throws:
IllegalStateException
- if wheel has any scheduled timers.
-
currentTickTime
public long currentTickTime()Time of current tick of the wheel intimeUnit()
s.- Returns:
- time of the current tick of the wheel in
timeUnit()
s.
-
currentTickTime
public void currentTickTime(long now) Set the current tick of the wheel to examine on the nextpoll(long, org.agrona.DeadlineTimerWheel.TimerHandler, int)
.If the time passed in is less than the current time, nothing is changed. No timers will be expired when winding forward and thus are still in the wheel and will be expired as encountered in the wheel during
poll(long, org.agrona.DeadlineTimerWheel.TimerHandler, int)
operations. No guarantee of order for expired timers is assumed when later polled.- Parameters:
now
- current time to advance to or stay at current time.
-
clear
public void clear()Clear out all scheduled timers in the wheel. -
scheduleTimer
public long scheduleTimer(long deadline) Schedule a timer for a given absolute time as a deadline intimeUnit()
s. A timerId will be assigned and returned for future reference.- Parameters:
deadline
- after which the timer should expire.- Returns:
- timerId assigned for the scheduled timer.
-
cancelTimer
public boolean cancelTimer(long timerId) Cancel a previously scheduled timer.- Parameters:
timerId
- of the timer to cancel.- Returns:
- true if successful otherwise false if the timerId did not exist.
-
poll
Poll for timers expired by the deadline passing.- Parameters:
now
- current time to compare deadlines against.handler
- to call for each expired timer.expiryLimit
- to process in one poll operation.- Returns:
- count of expired timers as a result of this poll operation.
-
forEach
Iterate over wheel so all active timers can be consumed without expiring them.- Parameters:
consumer
- to call for each active timer.
-
deadline
public long deadline(long timerId) Get the deadline for the given timerId.- Parameters:
timerId
- of the timer to return the deadline of.- Returns:
- deadline for the given timerId or
NULL_DEADLINE
if timerId is not scheduled.
-
currentTickTime0
private long currentTickTime0() -
increaseCapacity
private long increaseCapacity(long deadline, int spokeIndex) -
timerIdForSlot
private static long timerIdForSlot(int tickOnWheel, int tickArrayIndex) -
tickForTimerId
private static int tickForTimerId(long timerId) -
indexInTickArray
private static int indexInTickArray(long timerId) -
checkTicksPerWheel
private static void checkTicksPerWheel(int ticksPerWheel) -
checkResolution
private static void checkResolution(long tickResolution) -
checkInitialTickAllocation
private static void checkInitialTickAllocation(int tickAllocation)
-