# Adrian Colyer - Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility | the Morning Paper (Highlights)
## Metadata
**Cover**:: https://readwise-assets.s3.amazonaws.com/static/images/article3.5c705a01b476.png
**Source**:: #from/readwise
**Zettel**:: #zettel/fleeting
**Status**:: #x
**Authors**:: [[Adrian Colyer]]
**Full Title**:: Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility | the Morning Paper
**Category**:: #articles #readwise/articles
**Category Icon**:: 📰
**URL**:: [blog.acolyer.org](https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/)
**Host**:: [[blog.acolyer.org]]
**Highlighted**:: [[2021-02-21]]
**Created**:: [[2022-09-26]]
## Highlights
- Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility – Varghese & Lauck 1987
#paper #rl
- Yashiro Matsuda recently wrote a blog post describing Apache Kafka’s use of Hierarchical Timing Wheels to keep track of large numbers of outstanding requests.
#rl
- They model timers as composed of two user-facing operations, start and stop, and two internal operations: per-tick bookkeeping and expiry processing.
- “for a general timer module… that is expected to work well in a variety of environments, we recommend scheme 6 or 7.” Scheme 6 is ‘hashed timing wheels’ and scheme 7 is ‘hierarchical timing wheels’.
### 1. Unordered Timer List
- Keep an unordered list of timers and track the remaining time for each.
### 2. Ordered Timer List
- Keep a list of timers as in scheme 1, but record the absolute expiry time (not remaining time) and keep the timer list ordered by this expiry time (with the timers closest to expiry at the head of the list).
### 3. Timer Trees
### 4. Simple Timing Wheels
- when all timers have a maximum period of no more than MaxInterval, and we can construct a circular buffer with MaxInterval slots
### 5. Hashing Wheel with Ordered Timer Lists
- Construct a circular buffer with a fixed number of slots ... Since there may be many timers in any given slot, we maintain an ordered list of timers for each slot.
### 6. Hashing Wheel with Unordered Timer Lists
- To insert a timer that expires j time units in the future, compute a counter value _ c = j / num-buckets_ and a slot delta s = j % num-buckets . Insert the timer s slots around the ring with its counter value c.
### 7. Hierarchical Timing Wheels