Hashed and Hierarchical Timing Wheels

Papers We Love, Montreal
Papers We Love, Montreal
Public group
Location image of event venue


I will present Hashed and Hierarchical Timing Wheels (http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf) by Varghese and Lauck. This is the basis for pretty much every operating system's timer facility, and has an important role in distributed systems. (As usual, Adrian Colyer's writeup of this paper (https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/) is great; see also the subsequent discussion of GD-Wheels (https://blog.acolyer.org/2015/11/24/gd-wheel/).)

I'll talk about some specific implementations of this idea, in Erlang's runtime system (https://github.com/erlang/otp/blob/maint/erts/emulator/beam/time.c), in Linux (https://github.com/torvalds/linux/blob/master/kernel/time/timer.c) (see also this lwn article (https://lwn.net/Articles/646950/)), as well as Juho Snellman's Ratas (https://www.snellman.net/blog/archive/2016-07-27-ratas-hierarchical-timer-wheel/) and possibly some others. (The article on Kafka's use of timing wheels is easy to understand.)

The front door for AdGear's new office is not finished, so please enter via the alleyway behind the building (rue de Longueuil between Notre-Dame and Saint-Maurice), per the map. There will be a sign on the door.