Class DeadlineTimerWheel
- java.lang.Object
-
- org.agrona.DeadlineTimerWheel
-
public class DeadlineTimerWheel extends java.lang.Object
Timer Wheel for timers scheduled to expire on a deadline, (NOT thread safe).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 Classes Modifier and Type Class Description static interface
DeadlineTimerWheel.TimerConsumer
Consumer of timer entries as deadline to timerId.static interface
DeadlineTimerWheel.TimerHandler
Handler for processing expired timers.
-
Field Summary
Fields Modifier and Type Field Description private int
allocationBitsToShift
private long
currentTick
private static int
INITIAL_TICK_ALLOCATION
static long
NULL_DEADLINE
Represents a deadline not set in the wheel.private int
pollIndex
private int
resolutionBitsToShift
private long
startTime
private int
tickAllocation
private int
tickMask
private long
tickResolution
private int
ticksPerWheel
private long
timerCount
private java.util.concurrent.TimeUnit
timeUnit
private long[]
wheel
-
Constructor Summary
Constructors Constructor Description DeadlineTimerWheel(java.util.concurrent.TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel)
Construct timer wheel and configure timing with default initial allocation.DeadlineTimerWheel(java.util.concurrent.TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel, int initialTickAllocation)
Construct timer wheel and configure timing with provided initial allocation.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
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
currentTickTime()
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
currentTickTime0()
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
startTime()
The start time tick for the wheel from which it advances.private static int
tickForTimerId(long timerId)
long
tickResolution()
Resolution of a tick of the wheel intimeUnit()
s.int
ticksPerWheel()
The number of ticks, or spokes, per wheel.long
timerCount()
Number of active timers.private static long
timerIdForSlot(int tickOnWheel, int tickArrayIndex)
java.util.concurrent.TimeUnit
timeUnit()
Time unit for the time ticks.
-
-
-
Field Detail
-
NULL_DEADLINE
public static final long NULL_DEADLINE
Represents a deadline not set in the wheel.- See Also:
- Constant Field Values
-
INITIAL_TICK_ALLOCATION
private static final int INITIAL_TICK_ALLOCATION
- See Also:
- Constant Field Values
-
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
private final java.util.concurrent.TimeUnit timeUnit
-
wheel
private long[] wheel
-
-
Constructor Detail
-
DeadlineTimerWheel
public DeadlineTimerWheel(java.util.concurrent.TimeUnit timeUnit, long startTime, long tickResolution, int ticksPerWheel)
Construct timer wheel and configure timing with default 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).
-
DeadlineTimerWheel
public DeadlineTimerWheel(java.util.concurrent.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 Detail
-
timeUnit
public java.util.concurrent.TimeUnit 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:
java.lang.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
public int poll(long now, DeadlineTimerWheel.TimerHandler handler, int expiryLimit)
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
public void forEach(DeadlineTimerWheel.TimerConsumer consumer)
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)
-
-