timeout.c: Tickless Hierarchical Timing Wheel

description

timeout.c 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.c 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.c 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 in pure software.

Why a timing wheel? The critical feature of timing wheels is O(1) insertion and deletion. Timeouts rarely expire in network server software; they're 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.

news

2014-01-15

Renamed project page to timeout.c.html and Git repositories to timeout.git.

2014-01-10

Fixed bug by adding a bit fill operation which had been removed earlier.

Preliminary benchmarking against libevent's binary heap-based timer implementation is proving very promising, both algorithmically and in absolute terms.

2013-12-14

Extensive refactoring. Renamed the API to use the prefix timeouts_ and timeout_, because POSIX protects timer_. Removed some unused code, added some comments (I forgot how most of it worked over the past several months), and fleshed out the API.

2013-05-28

Public release.

usage

The timing wheels are fundamentally dimensionless. Neither the algorithm nor the implementation necessarily conceives of seconds, milliseconds, microseconds, etc, per se. It is the application's responsibility to use consistent units. Whatever the units, the clock source should be monotonic, though successive timestamps do not need to increase.

An opaque 64-bit integer type is used for relative and absolute time values, and expiration times are segmented bit-wise and mapped to wheels according to the compile-time parameters WHEEL_NUM and WHEEL_BIT (see source for more details).

[more to come]

license

Copyright (c) 2013, 2014 William Ahern

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

source

git clone http://25thandClement.com/~william/projects/timeout.git

Or browse the source code from the Github mirror at https://github.com/wahern/timeout.

other projects

airctl | bsdauth | cnippets | libmime | libarena | libevnet | authldap | streamlocal | libnostd | zoned | dns.c | delegate.c | llrb.h | lpegk | json.c | cqueues | siphash.h | hexdump.c | timeout.c | luapath | luaossl | AnonNet