Expiry heaps: invalidate stale TTL records on replacement

Operational case

At time 23, write pump-47 with lifetime 19, so its first deadline is 42. At time 29, replace it with a rechecked value lasting 38 units, with deadline 67. A read at time 42 must return rechecked; the first heap record is stale and cannot delete the replacement. A read at time 67 returns no value because the current deadline is due. A clock step back from 67 is rejected. The trace tests the serial identity rule rather than only heap order. A negative lifetime is rejected before any write occurs.

Working Python program

from heapq import heappop, heappush


class IncidentExpiryIndex:
    def __init__(self):
        self.clock = 0
        self.serial = 0
        self.entries = {}
        self.expirations = []

    def advance(self, now):
        if now < self.clock:
            raise ValueError("clock cannot move backward")
        self.clock = now
        while self.expirations and self.expirations[0][0] <= now:
            expires_at, serial, key = heappop(self.expirations)
            current = self.entries.get(key)
            if current is not None and current[1:] == (expires_at, serial):
                del self.entries[key]

    def put(self, key, value, now, lifetime):
        if lifetime < 0:
            raise ValueError("lifetime cannot be negative")
        self.advance(now)
        self.serial += 1
        expires_at = now + lifetime
        self.entries[key] = (value, expires_at, self.serial)
        heappush(self.expirations, (expires_at, self.serial, key))
        self.advance(now)

    def get(self, key, now):
        self.advance(now)
        current = self.entries.get(key)
        return None if current is None else current[0]


if __name__ == "__main__":
    index = IncidentExpiryIndex()
    index.put("pump-47", "open", now=23, lifetime=19)
    index.put("pump-47", "rechecked", now=29, lifetime=38)
    print("at-42=", index.get("pump-47", 42), sep="")
    print("at-67=", index.get("pump-47", 67), sep="")

Output

at-42=rechecked
at-67=None

Time, space, and tradeoff

With W heap records since the last full rebuild, insertion takes O(log W) time and the heap can use O(W) space even if only a few keys remain live. Advancing through E due records takes O(E log W) time; a read may trigger that work, so its worst-case latency is not constant. A sequence of reads with no due records uses expected O(1) dictionary work plus a heap-head check. Lazy stale records need a compaction policy if repeated overwrites would grow memory too far. This index does not promise wall-clock scheduling, durable timers, concurrent mutation safety, or a fixed upper bound on per-request cleanup work.

Common Mistakes

• Do not let an old deadline delete a newer replacement of the same key.
• Do not describe lazy heap storage as O(number of live keys).
• Do not treat expiry at the deadline as still valid.
• Do not assume a background thread removes entries without an advance call.

Connected lessons

• Trees and Heaps
• Data Structures
• Binary heaps: select the next priority with a tie rule
• Shortest routes: skip stale min-heap entries
• LFU caches: evict by frequency, then recency
• Projects
• Quizzes

Compare its invariant with LFU caches: evict by frequency, then recency, Generational slots: reject stale handles after reuse, D-ary heaps: trade shallower ascent for wider extraction, then run the retention and dispatch audit and operation quiz.

Double-ended queues: reconcile min and max heaps adds another queue operation contract.

Hashed timing wheels: bucket incident expiries by tick extends the retention comparison.