Lawn: an Unbound Low Latency Timer Data Structure for Large Scale, High Throughput Systems

Adam Lev-Libfeld

arxiv: 1906.10860 · v2 · pith:BFPOLCIPnew · submitted 2019-06-26 · 💻 cs.DS · cs.DC· cs.NI· cs.OS

Lawn: an Unbound Low Latency Timer Data Structure for Large Scale, High Throughput Systems

Adam Lev-Libfeld This is my paper

Pith reviewed 2026-05-25 15:27 UTC · model grok-4.3

classification 💻 cs.DS cs.DCcs.NIcs.OS

keywords timer data structuretiming wheellow latencyunbounded rangehashed queuesreal-time systemshigh throughput

0 comments

The pith

Lawn timer structure achieves low-latency unbounded range using hashed queues on timing wheels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Lawn algorithm as a timer data structure for large-scale systems. It builds on the timing wheel by organizing timers into queues hashed by their time-to-live values. This design aims to support arbitrary time ranges without overflow or added latency. The approach claims simpler implementation and maintained performance compared to existing methods under typical conditions. Such a structure matters because timers underpin many real-time applications in operating systems and networks.

Core claim

The Lawn algorithm uses a timing wheel augmented with queues hashed according to TTL values to manage timers over an unbounded range. This organization delivers O(1) operations, avoids overflow, requires minimal overhead, and maintains performance parity with bounded alternatives in standard use cases.

What carries the argument

The hashed-queue organization layered on a timing wheel, where each queue holds timers sharing the same TTL hash.

If this is right

Timers can have arbitrarily large expiration times without causing overflow in the data structure.
Insert and deletion operations remain near-constant time regardless of the timer range.
Implementation complexity decreases relative to hierarchical or multi-level timing wheel designs.
High-throughput systems can handle more concurrent timers without performance degradation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Integrating Lawn into existing timer libraries could simplify codebases that currently manage range limits separately.
Testing under skewed TTL distributions might reveal whether hash collisions affect real-world latency.
Extensions to support timer cancellation or updates could follow from the queue structure.

Load-bearing premise

That the hashing of TTLs into queues does not introduce variable costs from collisions or queue traversals that would violate the constant-time guarantee.

What would settle it

Running the Lawn algorithm on a workload where many timers share TTLs that hash to the same bucket and measuring if operation times exceed those of standard timing wheels.

Figures

Figures reproduced from arXiv: 1906.10860 by Adam Lev-Libfeld.

read the original abstract

As demand for Real-Time applications rises among the general public, the importance of enabling large-scale, unbound algorithms to solve conventional problems with low to no latency is critical for product viability. Timer algorithms are prevalent in the core mechanisms behind operating systems, network protocol implementation, stream processing, and several database capabilities. This paper presents a field-tested algorithm for low latency, unbound range timer structure, based upon the well excepted Timing Wheel algorithm. Using a set of queues hashed by TTL, the algorithm allows for a simpler implementation, minimal overhead no overflow and no performance degradation in comparison to the current state of the algorithms under typical use cases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Lawn layers TTL-hashed queues onto a timing wheel but offers no analysis or data to back its performance claims.

read the letter

The main thing to know is that Lawn is a timing-wheel variant that hashes timers into queues by TTL and claims this gives low latency, unbounded range, simpler code, minimal overhead, no overflow, and no degradation versus prior algorithms under typical use. That specific organization is the concrete new piece relative to the cited wheel work. The motivation from real-time apps, OS kernels, and network stacks is straightforward and the high-level sketch is easy to follow. It does identify a real systems need for timers that span wide TTL ranges without the usual bucket-size limits. The soft spots are the lack of any supporting detail. The description gives no hash function, no collision handling, no expiration scan procedure, no pseudocode, and no amortized-cost argument. There are also no benchmarks or error analysis, so the claim that hashing adds no hidden costs or slowdowns for wide TTL distributions or high timer counts rests on an untested assumption. Without those elements it is impossible to verify that the structure stays near-constant time or avoids degradation. This is aimed at practitioners who already know timing wheels and want a practical tweak for high-throughput code. A reader looking for a verified algorithm or reproducible results will not get enough here. I would not bring it to a reading group and would not cite it. It does not deserve peer review until the authors supply the missing implementation details and some measurements or analysis.

Referee Report

2 major / 1 minor

Summary. The manuscript presents the Lawn algorithm, an extension of the standard Timing Wheel timer data structure. It uses a set of queues hashed by TTL to support an unbounded range while claiming low latency, simpler implementation, minimal overhead, no overflow, and no performance degradation relative to prior algorithms under typical use cases. The claims rest on field testing.

Significance. If the performance and correctness properties can be substantiated with benchmarks or analysis, the algorithm would offer a practical, low-overhead unbounded timer structure useful for high-throughput real-time systems in networking, OS kernels, and databases. The field-tested aspect is a potential strength, but the current lack of quantitative evidence or formal argument limits its assessed significance.

major comments (2)

[Abstract] Abstract: the central claims of 'no performance degradation', 'no overflow', and 'field-tested' behavior with low latency for unbound ranges are asserted without any quantitative benchmarks, comparison tables, error analysis, or proof sketch, so the performance assertions cannot be evaluated from the provided text.
[Abstract] Abstract / overall description: the hashed-queue organization is described only at high level ('a set of queues hashed by TTL') with no definition of the hash function, collision handling, expiration-scan procedure, or amortized-cost analysis; this leaves the key assumption that O(1) or near-constant behavior is preserved for wide TTL distributions unverified and load-bearing for the main claim.

minor comments (1)

[Abstract] Abstract: 'well excepted' is a typo and should read 'well accepted'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We agree that the current manuscript is high-level and lacks supporting data, which limits evaluation of the claims. We will revise to address both points by expanding the description and adding empirical evidence.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims of 'no performance degradation', 'no overflow', and 'field-tested' behavior with low latency for unbound ranges are asserted without any quantitative benchmarks, comparison tables, error analysis, or proof sketch, so the performance assertions cannot be evaluated from the provided text.

Authors: We acknowledge that the abstract makes performance claims without quantitative support in the text. 'Field-tested' refers to production deployment in high-throughput systems where no degradation or overflow was observed, but we agree this is insufficient for evaluation. In revision we will add a dedicated evaluation section with latency benchmarks, comparisons to standard timing wheels under varying loads and TTL ranges, and basic error/overflow analysis. revision: yes
Referee: [Abstract] Abstract / overall description: the hashed-queue organization is described only at high level ('a set of queues hashed by TTL') with no definition of the hash function, collision handling, expiration-scan procedure, or amortized-cost analysis; this leaves the key assumption that O(1) or near-constant behavior is preserved for wide TTL distributions unverified and load-bearing for the main claim.

Authors: The manuscript intentionally presents a high-level overview. We will expand the algorithm description in the revised version to define the hash function (TTL modulo wheel size), collision handling (chained per-bucket lists), the expiration scan (linear scan of the current hashed queue), and an amortized-cost argument showing expected O(1) per insertion/expiration under typical uniform TTL distributions, with discussion of degradation cases. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic construction with no equations or self-referential reductions

full rationale

The manuscript describes a data-structure construction (hashed queues layered on a timing-wheel base) without any equations, fitted parameters, or derivation steps. The central claims rest on the properties of this construction rather than on any mathematical reduction that loops back to its own inputs or to a self-citation chain. No load-bearing uniqueness theorems, ansatzes, or renamings appear. The description is therefore self-contained as an engineering proposal; any performance assertions would require separate empirical or analytic verification but do not constitute circularity within the given text.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The contribution is an algorithmic description with no mathematical axioms, free parameters, or invented physical entities; the only new named object is the Lawn structure itself, which is an implementation artifact rather than a postulated entity requiring independent evidence.

pith-pipeline@v0.9.0 · 5636 in / 1167 out tokens · 19478 ms · 2026-05-25T15:27:49.741149+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

B. P. Douglass, Real-Time Design Patterns . Addison-Wesley, 2003. chapter 5: Concurrency Patterns (Rendezvous)

work page 2003
[2]

Uncertainty, waiting time, and capacity utilization: A stochastic theory of product quality,

A. D. Vany, “Uncertainty, waiting time, and capacity utilization: A stochastic theory of product quality,” Journal of Political Economy , vol. 84, no. 3, pp. 523–541, 1976

work page 1976
[3]

Redesigning the bsd callout and timer facilities,

A. Costello, A. M. Costello, G. Varghese, and G. Varghese, “Redesigning the bsd callout and timer facilities,” tech. rep., Washington University in St Louis, 1995

work page 1995
[4]

Hashed and hierarchical timing wheels: efﬁcient data structures for implementing a timer facility,

G. Varghese and A. Lauck, “Hashed and hierarchical timing wheels: efﬁcient data structures for implementing a timer facility,” IEEE/ACM transactions on networking , vol. 5, pp. 824–834, December 1997

work page 1997
[5]

Calendar queues: A fast o(1) priority queue implementation for the simulation event set problem,

D. Sleator and R. Brown, “Calendar queues: A fast o(1) priority queue implementation for the simulation event set problem,” Comunications of the ACM, vol. 31, Oct. 1988

work page 1988
[6]

An empirical comparison of priority-queue and event-set implementations,

D. W. Jones, “An empirical comparison of priority-queue and event-set implementations,” Commun. ACM, vol. 29, pp. 300–311, Apr. 1986

work page 1986
[7]

Hashed and hierarchical timing wheels: Data structures for the efﬁcient implementation of a timer facility,

G. Varghese and T. Lauck, “Hashed and hierarchical timing wheels: Data structures for the efﬁcient implementation of a timer facility,” SIGOPS Oper. Syst. Rev., vol. 21, pp. 25–38, Nov. 1987

work page 1987
[8]

timeout.c: Tickless hierarchical timing wheel implementa- tion

N. Welch, “timeout.c: Tickless hierarchical timing wheel implementa- tion.” http://25thandclement.com/∼william/projects/timeout.c.html

work page
[9]

Large-scale timer management

H. Hu, “Large-scale timer management.” US Patent no. US8307030B1

work page
[10]

On-demand scalable timer wheel

Z. ZhouIvan, “On-demand scalable timer wheel.” US Patent no. US20140298073A1

work page
[11]

Vioozer geo-tagging system

A. M. Adam Matan, Adam Lev-Libfeld, “Vioozer geo-tagging system.” http://www.vioozer.com/, 2017

work page 2017
[12]

Fast data - moving beyond from big datas map-reduce,

A. Lev-Libfeld and A. Margolin, “Fast data - moving beyond from big datas map-reduce,” GeoPython, vol. 1, pp. 3–6, June 2016

work page 2016
[13]

Iberra, “Redis.” https://redis.io/, 2009

S. Iberra, “Redis.” https://redis.io/, 2009

work page 2009
[14]

A redis element dehydration module

A. Lev-Libfeld, “A redis element dehydration module.” www.tamarlabs. com/ReDe/, 2017

work page 2017

[1] [1]

B. P. Douglass, Real-Time Design Patterns . Addison-Wesley, 2003. chapter 5: Concurrency Patterns (Rendezvous)

work page 2003

[2] [2]

Uncertainty, waiting time, and capacity utilization: A stochastic theory of product quality,

A. D. Vany, “Uncertainty, waiting time, and capacity utilization: A stochastic theory of product quality,” Journal of Political Economy , vol. 84, no. 3, pp. 523–541, 1976

work page 1976

[3] [3]

Redesigning the bsd callout and timer facilities,

A. Costello, A. M. Costello, G. Varghese, and G. Varghese, “Redesigning the bsd callout and timer facilities,” tech. rep., Washington University in St Louis, 1995

work page 1995

[4] [4]

Hashed and hierarchical timing wheels: efﬁcient data structures for implementing a timer facility,

G. Varghese and A. Lauck, “Hashed and hierarchical timing wheels: efﬁcient data structures for implementing a timer facility,” IEEE/ACM transactions on networking , vol. 5, pp. 824–834, December 1997

work page 1997

[5] [5]

Calendar queues: A fast o(1) priority queue implementation for the simulation event set problem,

D. Sleator and R. Brown, “Calendar queues: A fast o(1) priority queue implementation for the simulation event set problem,” Comunications of the ACM, vol. 31, Oct. 1988

work page 1988

[6] [6]

An empirical comparison of priority-queue and event-set implementations,

D. W. Jones, “An empirical comparison of priority-queue and event-set implementations,” Commun. ACM, vol. 29, pp. 300–311, Apr. 1986

work page 1986

[7] [7]

Hashed and hierarchical timing wheels: Data structures for the efﬁcient implementation of a timer facility,

G. Varghese and T. Lauck, “Hashed and hierarchical timing wheels: Data structures for the efﬁcient implementation of a timer facility,” SIGOPS Oper. Syst. Rev., vol. 21, pp. 25–38, Nov. 1987

work page 1987

[8] [8]

timeout.c: Tickless hierarchical timing wheel implementa- tion

N. Welch, “timeout.c: Tickless hierarchical timing wheel implementa- tion.” http://25thandclement.com/∼william/projects/timeout.c.html

work page

[9] [9]

Large-scale timer management

H. Hu, “Large-scale timer management.” US Patent no. US8307030B1

work page

[10] [10]

On-demand scalable timer wheel

Z. ZhouIvan, “On-demand scalable timer wheel.” US Patent no. US20140298073A1

work page

[11] [11]

Vioozer geo-tagging system

A. M. Adam Matan, Adam Lev-Libfeld, “Vioozer geo-tagging system.” http://www.vioozer.com/, 2017

work page 2017

[12] [12]

Fast data - moving beyond from big datas map-reduce,

A. Lev-Libfeld and A. Margolin, “Fast data - moving beyond from big datas map-reduce,” GeoPython, vol. 1, pp. 3–6, June 2016

work page 2016

[13] [13]

Iberra, “Redis.” https://redis.io/, 2009

S. Iberra, “Redis.” https://redis.io/, 2009

work page 2009

[14] [14]

A redis element dehydration module

A. Lev-Libfeld, “A redis element dehydration module.” www.tamarlabs. com/ReDe/, 2017

work page 2017