# Julian Squires - Implementations of Timing Wheels (Highlights)
## Metadata
**Cover**:: https://i.ytimg.com/vi/AftX7rqx-Uc/hqdefault.jpg
**Source**:: #from/readwise
**Zettel**:: #zettel/fleeting
**Status**:: #x
**Authors**:: [[Julian Squires]]
**Full Title**:: Implementations of Timing Wheels
**Category**:: #podcasts #readwise/podcasts
**Category Icon**:: 🎙
**URL**:: [www.youtube.com](https://www.youtube.com/watch?v=AftX7rqx-Uc)
**Host**:: [[www.youtube.com]]
**Highlighted**:: [[2021-02-14]]
**Created**:: [[2022-09-26]]
## Highlights
- Timing wheels theory ([Time 0:01:23](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#83))
- ## Timing wheels theory
* Varghese and Lauck. “Hashed and hierarchical timing wheels: Data structures for the efficient implementation of a timer facility.” ACM SIGOPS Operating Systems Review 21.5( 1987): 25-38.
* Varghese and Lauck. “Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility.” IEEE/ACM transactions on networking 5.6 (1997): 824-834.
* Varghese. Network Algorithmics: An Interdisciplinary Approach To Designing Fast Networked Devices Morgan Kaufmann, 2004.
* Timing Wheels is a case used in the book. ([Time 0:01:24](https://reclipped.com/a/yU1qFm7kEeu3Dr9v6HRh8A#84))
- Recent activity ([Time 0:01:59](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#119))
- ## Recent activity
* LWN on Gleixner's timing wheels patch: https://lwn.net/Articles/646950/
* Adrian Colyer's Morning Paper blog:
https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/
* Juho Snellman on Ratas: https://www.snellman.net/blog/archive/2016-07-27-ratas-hierarchical-timer-wheel/ ([Time 0:02:00](https://reclipped.com/a/HuXLdm7lEeu3D9tGUB-90Q#120))
- Two kinds of timer cases: Optimistic and Pessimistic ([Time 0:02:14](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#134))
- Guarantees of a timer system ([Time 0:02:47](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#167))
- ## Guarantees of a timer system
A timer scheduled to file after _t_ ticks will have its action executed, some time after _t_ ticks. ([Time 0:02:48](https://reclipped.com/a/S5rAlG7mEeu3EFfbQua2rA#168))
- Unordered list ([Time 0:05:07](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#307))
- Ordered list ([Time 0:05:49](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#349))
- Binary heaps ([Time 0:06:33](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#393))
- Timing wheels ([Time 0:07:29](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#449))
- Hierarchical timing wheels ([Time 0:08:59](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#539))
- ## Hierarchical timing wheels
Implementations:
* Linux `linux/kernel/time/timer.c`
* Ratas https://github.com/jsnell/ratas
* Kafka `core/src/main/scala/kafka/utils/timer/TimingWheel.scala`
* timeout https://github.com/wahern/time ([Time 0:09:00](https://reclipped.com/a/CgsksG7nEeu3EZubwwrBUA#540))
- Hashed timing wheels ([Time 0:12:34](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#754))
- ## Hashed timing wheels
Implementations
* BSD `sys/kern/kern_timeout.c`
* Erlang (port and proc timers) `erts/emulator/beam/time.c`
* Netty `common/src/main/java/io
/netty/util/HashedWheelTimer.java`
Papers
* Costello and Varghese. "Redesigning the Bsd callout and timer facilities. " (1995).
* Italiano and Motin. "Calloutng: a new infrastructure for timer facilities in the FreeBSD kernel. "(2013). ([Time 0:12:35](https://reclipped.com/a/jv5NoG7nEeu3EqvouZH5FA#755))
- Other techniques ([Time 0:14:05](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#845))
- ## Other techniques
* Calendar queues
* Skip lists: DPDK http://dpdk.org `lib/librte.timer/rte.timer.c`
* Red-Black trees:
* Linux `kernel/time/hrtimer.c`
* Erlang `erts/emulator/beam/erl`.
* Hash table
* nodejs `lib/timers.js`
* Softheaps ([Time 0:14:06](https://reclipped.com/a/0MkJqm7nEeu3E5OQLlLnJw#846))
- O(lgN) vs O(1) ([Time 0:18:04](https://reclipped.com/a/aqGoDG7eEeu285-ByYjFmw#1084))
- Jason Evans says:
> In essence, my initial failure was to disregard the difference between O(1) algorithm and a O(n) algorithm. Intuitively, think of logarithmic--time algorithms as fast, but constant factors and large n can conspire to make logarthmic time not nearly good
enough.
http://branchtaken.net/blog/2008/07/24/overzealous-use-of-my-red-black-tree.html ([Time 0:18:05](https://reclipped.com/a/8DIPNG7oEeu3FeeWQhghKQ#1085))