TTL and expiry

coreCommon atAnthropicStripeOpenAIAmazonRead firstHeapsTime handlingPractise in the Sandbox →

A TTL (time to live) turns into an absolute deadline expires_at = now + ttl, and the entry is live while now < expires_at. You can check deadlines lazily (on every read, O(1), but unread garbage piles up) or actively (a min-heap of deadlines pops only what is due, O(log n) each). Either way, time comes from an injected clock or a ts argument, never from the system clock inside your class.

The idea in plain words

A parking ticket says “valid until 14:30”. It doesn’t say “valid for 2 hours”, because then every warden would need to know when you arrived. Storing the absolute deadline makes the check a single comparison.

Now, who removes expired tickets? Two options:

• Lazy expiry. Nobody goes looking. When someone presents a ticket, you check the time. Expired? Throw it away right then. Zero background work, but tickets nobody presents stay in the drawer forever.
• Active expiry. Someone walks the drawer and throws out expired ones. Doing that by checking every ticket is wasteful. Keeping tickets sorted by deadline means you only ever look at the front of the pile.

Real systems combine both. Redis, for example, checks a key’s expiry whenever the key is accessed, and also periodically samples keys that have a TTL and deletes the expired ones it finds.

See it

Set a few keys with different TTLs, then move the clock. Try the same actions in each strategy. In lazy mode, watch dashed red bars pile up: expired data still taking memory. In sweep mode, watch the work counter climb even when nothing expires. In heap mode, re-set a key and look for the stale entry the heap skips later.

Expire keys lazily, by sweeping, or with a deadline heap

sandbox

strategylazy (on read)sweep alldeadline heapkeyABCDEttl

set A (ttl 5)get Aclock +1clock +5↺ reset

memory

live entries

0

expired, still held

0

expiry work so far

0

how this strategy finds expired keys

It doesn't. A read checks now < exp and deletes on the spot. Cheap, but keys nobody reads stay in memory forever.

now0

stored0

live0

live: now < expexpired but still storedstale heap entry

Set a few keys with different TTLs, then move the clock. Compare the three strategies.

When to reach for it

The problem says…	What to build
“the entry is visible while now < t + ttl”	Store expires_at. Check it on every read (lazy).
“expired entries don’t count toward capacity / size / totals”	You must purge before counting, or count only live entries. Lazy alone is not enough for size().
“return the keys that expired” / “fire a callback at expiry”	Active expiry with a deadline heap.
“every call receives ts”	The caller is your clock. Never read the system time.
“writing the key again replaces its expiry”	Re-arming. The old heap entry becomes stale; skip it on pop.
“a session / lease / lock / code expires”	Same pattern with a different name.

How it works

1. Convert TTL to a deadline at write time: expires_at = now + ttl. Store that, not the TTL. A missing deadline means “never expires”.
2. Pick one interval convention and say it. The common one is half-open [set_at, expires_at): live while now < expires_at, expired at exactly expires_at.
3. Inject time. Take a Clock in the constructor (or a ts per call). Tests drive a fake clock; production uses a monotonic one.
4. Lazy check on every read path: get, contains, update, and anything that iterates. Delete on the spot if expired.
5. Active purge when needed: push (expires_at, key) onto a min-heap. Before answering a query that depends on “everything live”, pop while the top is due.
6. Handle re-arming with lazy deletion: don’t search the heap for the old entry. When you pop, compare against the key’s current deadline and skip the entry if it doesn’t match.

Steps 1 to 4, with a fake clock driving the test:

Python

one_time_codes.py

import secrets
import time
from typing import Protocol


class Clock(Protocol):
    def now(self) -> float: ...


class SystemClock:
    def now(self) -> float:
        return time.monotonic()  # 1. monotonic: never jumps back when NTP adjusts the wall clock


class FakeClock:
    def __init__(self, t: float = 0.0) -> None:
        self.t = t

    def now(self) -> float:
        return self.t

    def advance(self, dt: float) -> None:
        self.t += dt


class OneTimeCodes:
    """Login codes valid for `ttl` seconds. Time comes from the injected clock."""

    def __init__(self, clock: Clock, ttl: float) -> None:
        self.clock, self.ttl = clock, ttl  # 2. never call time.* in here directly
        self.codes: dict[str, tuple[str, float]] = {}  # user -> (code, expires_at)

    def issue(self, user: str) -> str:
        code = f"{secrets.randbelow(10**6):06d}"
        self.codes[user] = (code, self.clock.now() + self.ttl)  # 3. store an absolute deadline
        return code

    def verify(self, user: str, code: str) -> bool:
        entry = self.codes.get(user)
        if entry is None:
            return False
        if self.clock.now() >= entry[1]:  # 4. half-open [issued, expires): expired at exactly ttl
            del self.codes[user]  # lazy expiry: clean up when touched
            return False
        return entry[0] == code


if __name__ == "__main__":
    clock = FakeClock()
    otp = OneTimeCodes(clock, ttl=30)
    c = otp.issue("ana")
    clock.advance(29.5)
    assert otp.verify("ana", c)
    clock.advance(0.5)  # exactly 30s: expired
    assert not otp.verify("ana", c) and "ana" not in otp.codes
    print("ok")

TypeScript

one_time_codes.ts

import assert from "node:assert/strict";
import { randomInt } from "node:crypto";

interface Clock { now(): number }

// 1. performance.now() is monotonic: it never jumps back when the wall clock is adjusted.
const systemClock: Clock = { now: () => performance.now() / 1000 };

class FakeClock implements Clock {
  constructor(private t = 0) {}
  now(): number { return this.t; }
  advance(dt: number): void { this.t += dt; }
}

/** Login codes valid for `ttl` seconds. Time comes from the injected clock. */
class OneTimeCodes {
  readonly codes = new Map<string, { code: string; expiresAt: number }>();
  constructor(private readonly clock: Clock, private readonly ttl: number) {} // 2. no Date.now() inside

  issue(user: string): string {
    const code = String(randomInt(1_000_000)).padStart(6, "0");
    this.codes.set(user, { code, expiresAt: this.clock.now() + this.ttl }); // 3. absolute deadline
    return code;
  }

  verify(user: string, code: string): boolean {
    const entry = this.codes.get(user);
    if (!entry) return false;
    if (this.clock.now() >= entry.expiresAt) { // 4. half-open [issued, expires)
      this.codes.delete(user); // lazy expiry: clean up when touched
      return false;
    }
    return entry.code === code;
  }
}

const clock = new FakeClock();
const otp = new OneTimeCodes(clock, 30);
const c = otp.issue("ana");
clock.advance(29.5);
assert.ok(otp.verify("ana", c));
clock.advance(0.5); // exactly 30s: expired
assert.ok(!otp.verify("ana", c));
assert.ok(!otp.codes.has("ana"));
assert.ok(systemClock.now() >= 0);
console.log("ok");

C#

one_time_codes.cs

var clock = new FakeClock();
var otp = new OneTimeCodes(clock, TimeSpan.FromSeconds(30));
var c = otp.Issue("ana");
clock.Advance(TimeSpan.FromSeconds(29.5));
if (!otp.Verify("ana", c)) throw new Exception("should be valid at 29.5s");
clock.Advance(TimeSpan.FromSeconds(0.5)); // exactly 30s: expired
if (otp.Verify("ana", c) || otp.Count != 0) throw new Exception("should be expired and removed");
Console.WriteLine("ok");

// .NET 8+ ships an abstraction for this: System.TimeProvider (FakeTimeProvider for tests).
// A one-method interface keeps the idea visible.
interface IClock { DateTimeOffset Now { get; } }

class FakeClock : IClock
{
    public DateTimeOffset Now { get; private set; } = DateTimeOffset.UnixEpoch;
    public void Advance(TimeSpan dt) => Now += dt;
}

// Login codes valid for `ttl`. Time comes from the injected clock.
class OneTimeCodes(IClock clock, TimeSpan ttl) // 2. never read DateTime.Now in here
{
    readonly Dictionary<string, (string Code, DateTimeOffset ExpiresAt)> codes = [];
    public int Count => codes.Count;

    public string Issue(string user)
    {
        var code = Random.Shared.Next(1_000_000).ToString("D6");
        codes[user] = (code, clock.Now + ttl); // 3. store an absolute deadline
        return code;
    }

    public bool Verify(string user, string code)
    {
        if (!codes.TryGetValue(user, out var entry)) return false;
        if (clock.Now >= entry.ExpiresAt) // 4. half-open [issued, expires)
        {
            codes.Remove(user); // lazy expiry: clean up when touched
            return false;
        }
        return entry.Code == code;
    }
}

Steps 5 and 6 as a reusable piece:

Python

deadline_heap.py

import heapq


class DeadlineHeap:
    """Min-heap of (deadline, key). Re-arming a key leaves the old entry behind; pops skip it."""

    def __init__(self) -> None:
        self.heap: list[tuple[int, str]] = []
        self.deadline: dict[str, int] = {}  # 1. source of truth: each key's current deadline

    def arm(self, key: str, at: int) -> None:
        self.deadline[key] = at
        heapq.heappush(self.heap, (at, key))  # 2. O(log n); no search for the old entry

    def disarm(self, key: str) -> None:
        self.deadline.pop(key, None)  # the heap entry becomes stale; that's fine

    def pop_due(self, now: int) -> list[str]:
        due: list[str] = []
        while self.heap and self.heap[0][0] <= now:  # 3. only touch what is due
            at, key = heapq.heappop(self.heap)
            if self.deadline.get(key) == at:  # 4. lazy deletion: skip stale entries
                del self.deadline[key]
                due.append(key)
        return due


if __name__ == "__main__":
    h = DeadlineHeap()
    h.arm("a", 5)
    h.arm("b", 3)
    h.arm("a", 9)  # re-armed: the (5, "a") entry is now stale
    h.arm("c", 4)
    h.disarm("c")
    assert h.pop_due(4) == ["b"]
    assert h.pop_due(8) == []  # (5, "a") popped and skipped
    assert h.pop_due(9) == ["a"] and h.heap == []
    print("ok")

TypeScript

deadline_heap.ts

import assert from "node:assert/strict";

type Item = [at: number, key: string];

/** Min-heap of [deadline, key]. JS has no built-in heap, so here is the minimal one. */
class DeadlineHeap {
  readonly heap: Item[] = [];
  private readonly deadline = new Map<string, number>(); // 1. each key's current deadline

  arm(key: string, at: number): void {
    this.deadline.set(key, at);
    const h = this.heap; // 2. push + sift up: O(log n), no search for the old entry
    h.push([at, key]);
    for (let i = h.length - 1, p = (i - 1) >> 1; i > 0 && h[p][0] > h[i][0]; i = p, p = (i - 1) >> 1) [h[p], h[i]] = [h[i], h[p]];
  }

  disarm(key: string): void { this.deadline.delete(key); } // heap entry goes stale

  private popMin(): Item {
    const h = this.heap, top = h[0], last = h.pop()!;
    if (h.length) {
      h[0] = last; // sift down
      for (let i = 0; ;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < h.length && h[l][0] < h[m][0]) m = l;
        if (r < h.length && h[r][0] < h[m][0]) m = r;
        if (m === i) break;
        [h[m], h[i]] = [h[i], h[m]]; i = m;
      }
    }
    return top;
  }

  popDue(now: number): string[] {
    const due: string[] = [];
    while (this.heap.length && this.heap[0][0] <= now) { // 3. only touch what is due
      const [at, key] = this.popMin();
      if (this.deadline.get(key) === at) { this.deadline.delete(key); due.push(key); } // 4. skip stale
    }
    return due;
  }
}

const h = new DeadlineHeap();
h.arm("a", 5); h.arm("b", 3);
h.arm("a", 9); // re-armed: [5, "a"] is now stale
h.arm("c", 4); h.disarm("c");
assert.deepEqual(h.popDue(4), ["b"]);
assert.deepEqual(h.popDue(8), []); // [5, "a"] popped and skipped
assert.deepEqual(h.popDue(9), ["a"]);
assert.equal(h.heap.length, 0);
console.log("ok");

C#

deadline_heap.cs

var h = new DeadlineHeap();
h.Arm("a", 5); h.Arm("b", 3);
h.Arm("a", 9); // re-armed: (a, 5) is now stale
h.Arm("c", 4); h.Disarm("c");
if (!h.PopDue(4).SequenceEqual(["b"])) throw new Exception("expected [b]");
if (h.PopDue(8).Count != 0) throw new Exception("(a,5) should be skipped as stale");
if (!h.PopDue(9).SequenceEqual(["a"]) || h.Count != 0) throw new Exception("expected [a], empty");
Console.WriteLine("ok");

// PriorityQueue<TElement, TPriority> is a min-heap with no "update priority" operation,
// which is exactly why the lazy-deletion trick is standard.
class DeadlineHeap
{
    readonly PriorityQueue<(string Key, long At), long> heap = new();
    readonly Dictionary<string, long> deadline = []; // 1. each key's current deadline
    public int Count => heap.Count;

    public void Arm(string key, long at)
    {
        deadline[key] = at;
        heap.Enqueue((key, at), at); // 2. O(log n); no search for the old entry
    }

    public void Disarm(string key) => deadline.Remove(key); // heap entry goes stale

    public List<string> PopDue(long now)
    {
        var due = new List<string>();
        while (heap.TryPeek(out _, out var at) && at <= now) // 3. only touch what is due
        {
            var (key, itemAt) = heap.Dequeue();
            if (deadline.TryGetValue(key, out var cur) && cur == itemAt) // 4. skip stale entries
            {
                deadline.Remove(key);
                due.Add(key);
            }
        }
        return due;
    }
}

Wall clock vs monotonic clock

The wall clock (time.time(), Date.now(), DateTime.UtcNow) can jump backwards when it is synced or adjusted. Durations measured with it can come out negative. For “how long until this expires inside one process”, use a monotonic clock: Python time.monotonic(), JS performance.now(), .NET Stopwatch or TimeProvider.GetTimestamp(). Use wall time only for deadlines that must mean something outside the process.

What it costs

Strategy	Read	Write	Background work	Memory
Lazy only	O(1) check	O(1)	none	expired keys stay until read
Sweep everything per tick	O(1)	O(1)	O(n) per tick, even if nothing expires	prompt
Deadline heap	O(1) check	O(log n) push	O(log n) per expired (or stale) entry	heap holds stale entries until popped
Sorted map by deadline	O(1) check	O(log n), can remove old entry	O(log n) per expired entry	no stale entries
Timer wheel (bucketed by tick)	O(1)	O(1)	O(1) per tick + per expiry	coarse resolution

The heap’s bill is proportional to how much actually expires, not to how much is stored. That’s the right shape when most entries live a long time.

Stale entries cost memory. If keys are re-armed constantly (a session refreshed on every request), the heap can grow far larger than the store. Two fixes: rebuild the heap when stale entries outnumber live ones, or use a sorted map where the old entry can be removed directly (.NET SortedSet, Python sortedcontainers, a balanced tree in TS).

Variations you’ll meet

• Sliding expiration. Every access pushes the deadline out again (“idle timeout”). It’s a re-arm on read.
• Absolute + sliding. A session that expires after 30 idle minutes or 12 hours total, whichever comes first. Store both deadlines; live while now < min(both).
• Remaining TTL on restore. Restoring from a backup should usually keep the remaining time, not the original TTL. Store or compute expires_at - backup_time and add it to the restore time.
• Probabilistic active expiry. Redis samples 20 keys that have a TTL, deletes the expired ones, and repeats if more than a quarter were expired. Bounded work per cycle without a heap.
• Timer wheels. Kernels and network stacks bucket deadlines into slots of a circular array, advancing one slot per tick. O(1) operations at the price of resolution.
• Expiry as a state transition. “A pending request expires after 48 hours” is a state machine transition that nobody fires. Compute it lazily when the object is next touched.

Pitfalls

• < vs <=. “Valid for 5 seconds” set at t=10: is it live at t=15? Under half-open intervals, no. Ask, then be consistent in every method.
• Forgetting a read path. get checks expiry, but size(), keys(), scan or a counter doesn’t. One unchecked path leaks expired data.
• Counting expired entries toward capacity. If the spec says expired entries don’t occupy space, purge before deciding to evict.
• Reading the real clock in a class that receives ts. Tests become flaky and replays non-deterministic.
• Updating the value but keeping (or losing) the old TTL by accident. Decide whether a plain write clears the expiry. Specs often say it does.
• Assuming time only moves forward. If timestamps can arrive out of order, “expired” is no longer permanent: a late event can be in the past relative to the current clock.

In the interview

• Ask: “Is the boundary inclusive? Does a plain write clear an existing TTL? Do expired entries count toward size or capacity? Is time passed in, or should I read a clock?”
• Say: “I’ll store absolute deadlines and check them lazily on every read. If we need expired keys reported or purged proactively, I’ll add a min-heap of deadlines with lazy deletion.”
• Make the clock a dependency so you can test boundaries exactly: set at 10 with ttl 5, check at 14 and at 15.
• Expect follow-ups: “what if millions of keys expire at once?” (bounded work per call, amortize), “what if the process restarts?” (persist absolute wall-clock deadlines), “how do you test this?” (fake clock).

Check yourself

Check yourself

pick one

A key is set at t=100 with ttl=20 under half-open intervals. Which reads see it?

At=100 through t=120 inclusiveBt=100 through t=119Ct=101 through t=120DOnly t=100

Check yourself

pick one

With a deadline heap, a key is re-armed 1,000 times before it finally expires. What does the heap contain?

AOne entry: re-arming replaces it in placeBUp to 1,000 entries for that key; all but the newest are stale and skipped when poppedCZero entries: re-arming removes the key from the heap

Check yourself

pick one

Your cache uses only lazy expiry. size() returns the length of the map. What's wrong?

ANothing, lazy expiry is completeBsize() counts expired entries that nobody has read yetCsize() is O(n)

Practice on your own

These are classic exercises, not gym questions:

• A “last seen” presence tracker: users are online for 60 seconds after their last heartbeat. Report who is online at time t.
• A countdown timer service: start, cancel and list timers that fired between two calls to tick(now).
• A distributed-lock lease with renewal: the holder must renew before the deadline or lose the lock. What happens if the holder’s clock is slow?
• Implement a simple timer wheel with 60 slots and compare its operation counts with a heap for 10,000 timers.

Go deeper

• Redis docs, EXPIRE: “How Redis expires keys” covers passive plus sampled active expiry.
• G. Varghese and T. Lauck, “Hashed and Hierarchical Timing Wheels” (SOSP 1987): the timer-wheel data structure.
• .NET TimeProvider (.NET 8+): the built-in injectable clock. Python time.monotonic.
• Python heapq docs, “Priority Queue Implementation Notes”: the mark-as-removed lazy deletion trick.

Related

Heaps and priority queuesThe structure behind active expiry.

Time handlingClocks, timestamps and boundaries.

Caching and evictionExpiry plus capacity limits.

Event-driven simulationDeadlines as events on a timeline.