Tickless Hierarchical Timing Wheel.
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 this project from source:
$ make
Run the test suite:
$ make check
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
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.