Class DeadlineTimerWheel

java.lang.Object
org.agrona.DeadlineTimerWheel
public class DeadlineTimerWheel extends 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.

  • Field Details

    • NULL_DEADLINE

      public static final long NULL_DEADLINE
      Represents 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

      private final TimeUnit 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.
      Parameters:
      timeUnit - for the values used to express the time.
      startTime - for the wheel (in given TimeUnit).
      tickResolution - for the wheel, i.e. how many TimeUnits per tick.
      ticksPerWheel - or spokes, for the wheel (must be power of 2).

    • 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 given TimeUnit).
      tickResolution - for the wheel, i.e. how many TimeUnits 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

      public 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 in timeUnit()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 in timeUnit()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 next poll(long, 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, 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 in timeUnit()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)