/home/zhuang

zhuang@linux:~/notes/dsa/timing-wheel/$ cat

Timing Wheel

$ stat timing-wheel.md

words 102
reading 1 min
views ...

$ grep tags timing-wheel.md

@programming #dsa

This post overviews an efficient data structure called timing wheel for implementing timer facility.

Model

The model of a timer module has the following four component routines:

  • STARTTIMER (Interval, RequestId, ExpiryAction)
  • STOPTIMER (RequestId)
  • PERTICKBOOKKEEPING
  • EXPIRYPROCESSING

Timer Schemes

Scheme 1 – Straightforward

Scheme 2 – Ordered List

Scheme 3 – Tree-Based Algorithms

SCHEME 4 – BASIC SCHEME

Scheme 5 – Hash Table With Sorted Lists

Scheme 6 – Hash Table with Unsorted Lists

Scheme 7 – Exploiting Hierarchy

References

  1. Varghese G, Lauck A. Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility[J]. IEEE/ACM transactions on networking, 1997, 5(6): 824-834.

zhuang@linux:~/notes/dsa/timing-wheel/$ comments