Package org.agrona

Class 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.

    • 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 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​(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 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 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 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:
        java.lang.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, 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 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)