timeout

Tickless Hierarchical Timing Wheel.

Description

timeout implements hierarchical timing wheels as described in "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility" by George Varghese and Tony Lauck, ACM 089791-242-X/87/0011/0025, pp. 25-38. This data structure implements timers in O(1) worst-case time for all operations including insertion, deletion, and expiration.

timeout is tickless. Traditional implementations utilize an external periodic timer which interrupts at intervals equal to the granularity of the clock to progress the timing wheel by one tick. timeout uses bitmaps and bitfield manipulation to optimize aperiodic wheel progression, and in particular reduces calculation of the next minimum update interval to a small O(1) in the worst case. This makes timing wheels practicable.

Why a timing wheel? The critical feature of timing wheels is O(1) insertion and deletion. Timeouts rarely expire in network server software; they are hedges by software for when other expected events fail to occur. Timeouts are often installed and cancelled repeatedly for even the simplest of actions. But the typical timeout implementation uses a red-black tree or priority queue, where insertion and deletion are O(log N) operations. Timing wheels are considerably more efficient algorithmically, while this implementation in particular tries to address potential fixed cost and latency issues, particularly for sparsely populated wheels.

Build

Build this project from source:

$ make

Run the test suite:

$ make check

Benchmarking

The benchmark depends on Lua version 5.3, and there are a few prerequisites which must be installed on your machine before you will be able to build and run the benchmark suite.

The following command will install all required and optional dependencies on Ubuntu Linux 18.04 or later:

$ sudo apt install lua5.3 liblua5.3-dev ghostscript gnuplot

macOS:

$ brew install lua@5.3 gnuplot ghostscript

Build and execute the benchmark:

$ make bench

Then, you will get the generated report in file out/bench.pdf which compares several algorithms.

Clean up the files generated by benchmark:

$ make clean

License

timeout is released under the MIT License. Use of this source code is governed by a MIT-style license that can be found in the LICENSE file.

External source code used for benchmarking:

• bench/bench-heap.c: written by Maxim Yegorushki. 3-Clause BSD License.
• bench/bench-ebtree.c: written by Willy Tarreau. GNU GPL v2.