Back to Miscellaneous Coding
Q3Question 3 of 52

Cache with TTL and Versioned Expiry

Key Concepts
  • Each entry stores a value, an absolute expiry timestamp (now + ttl), and a version number incremented on every write.
  • get(key, now) returns the value only if now < expires_at; otherwise reports a miss (lazy expiry).
  • put(key, value, ttl, now) replaces both the value and the expiry, and bumps the version.
  • Proactive cleanup uses a min-heap of expiry records, each stamped with the version they were created with.
  • A cleanup event deletes the entry only if its version matches the record's version; otherwise the record is stale and discarded.
  • Lazy expiry gives O(1) per get and put; the heap adds O(log n) per put and pop for proactive cleanup.

Definition

Validate on read against the expiry, and stamp every expiry record with a version so a late cleanup never deletes a newer rewrite.
  • TTL cache – stores each key with an expiry timestamp computed as now + ttl; a read is valid only while now < expires_at.
  • Versioned expiry – each write increments a version; cleanup records carry the version they were created with.
  • Lazy expiry – on get, check the timestamp and treat expired entries as misses. O(1) per operation.
  • Proactive cleanup – a min-heap keyed on expiry time pops expired records; only delete if version matches. O(log n) per push/pop.
  • Stale-record safety – a late cleanup event with a mismatched version is discarded, protecting freshly rewritten entries.

At the National Bank of India, Rajesh's OTP is cached with a two-minute validity. If he requests a new OTP before the old one expires, the new one replaces the old value and its expiry. A background cleanup robot holding a note that says 'delete Rajesh's OTP at 10:02' must check the version number: by then Rajesh has a fresh OTP valid until 10:05, so the robot discards the stale note.

Understanding the Concepts

What is a Cache with TTL?

A cache with time-to-live stores each key alongside an absolute expiry timestamp computed as the write time plus a TTL duration. A read is valid only while the current time is strictly before the expiry. This is the foundation for session caches, OTP stores, and rate limiters.

JAVA
package com.bank.service;

import java.util.HashMap;
import java.util.Map;

public class TTLCache<V> {
    private final Map<String, CacheEntry<V>> store = new HashMap<>();

    public void put(String key, V value, long ttl, long now) {
        CacheEntry<V> existing = store.get(key);
        long version = (existing != null) ? existing.version + 1 : 1;
        store.put(key, new CacheEntry<>(value, now + ttl, version));
    }

    public V get(String key, long now) {
        CacheEntry<V> entry = store.get(key);
        if (entry == null || now >= entry.expiresAt) {
            store.remove(key); // lazy cleanup
            return null;
        }
        return entry.value;
    }
}

class CacheEntry<V> {
    V value;
    long expiresAt;
    long version;

    CacheEntry(V value, long expiresAt, long version) {
        this.value = value;
        this.expiresAt = expiresAt;
        this.version = version;
    }
}

Why do we need versioned expiry?

When a key is rewritten, the old expiry is no longer valid. If proactive cleanup fires a stale expiry event, it could delete the freshly rewritten entry. Versioning prevents this: each write bumps a version, and cleanup records carry the version they were created with. A cleanup event only deletes if the versions match.

JAVA
package com.bank.service;

public class VersioningDemo {
    public static void main(String[] args) {
        TTLCache<String> cache = new TTLCache<>();
        // Write OTP with 2-minute TTL at time 100
        cache.put("rajesh-otp", "1234", 120, 100);
        // Entry: value="1234", expires=220, version=1

        // Rajesh requests new OTP at time 150
        cache.put("rajesh-otp", "5678", 120, 150);
        // Entry: value="5678", expires=270, version=2

        // Stale cleanup event fires at time 220 with version=1
        // Current entry has version=2 -> versions differ -> skip deletion
        System.out.println(cache.get("rajesh-otp", 220)); // "5678" (still valid)
    }
}
TEXT
5678

How does lazy expiry work?

Lazy expiry checks validity on every get call. If now >= expiresAt, the entry is treated as a miss and optionally removed. This adds zero overhead to writes and keeps each operation O(1). The downside is that expired entries linger in memory until accessed.

JAVA
// Lazy expiry in get:
public V get(String key, long now) {
    CacheEntry<V> entry = store.get(key);
    if (entry == null || now >= entry.expiresAt) {
        store.remove(key); // optional cleanup on access
        return null;       // expired -> miss
    }
    return entry.value;
}
// O(1) per get, O(1) per put

How does proactive cleanup with a heap work?

A min-heap ordered by expiry time enables proactive cleanup. Each put pushes an expiry record with the key and the current version. A background thread pops records whose expiry has passed and checks whether the entry's version still matches. If it does, the entry is deleted. If not, the record is stale and discarded.

JAVA
package com.bank.service;

import java.util.PriorityQueue;

public class ProactiveCleanup<V> {
    private final Map<String, CacheEntry<V>> store = new HashMap<>();
    private final PriorityQueue<ExpiryRecord> heap = new PriorityQueue<>();

    public void put(String key, V value, long ttl, long now) {
        CacheEntry<V> existing = store.get(key);
        long version = (existing != null) ? existing.version + 1 : 1;
        long expiresAt = now + ttl;
        store.put(key, new CacheEntry<>(value, expiresAt, version));
        heap.offer(new ExpiryRecord(key, expiresAt, version));
    }

    public void cleanup(long now) {
        while (!heap.isEmpty() && heap.peek().expiresAt <= now) {
            ExpiryRecord record = heap.poll();
            CacheEntry<V> entry = store.get(record.key);
            if (entry != null && entry.version == record.version) {
                store.remove(record.key); // version matches -> delete
            }
            // else: stale record, discard silently
        }
    }
}

class ExpiryRecord implements Comparable<ExpiryRecord> {
    String key;
    long expiresAt;
    long version;

    ExpiryRecord(String key, long expiresAt, long version) {
        this.key = key; this.expiresAt = expiresAt; this.version = version;
    }

    public int compareTo(ExpiryRecord other) {
        return Long.compare(this.expiresAt, other.expiresAt);
    }
}

What is the complexity of each approach?

Lazy expiry keeps everything O(1) but expired entries linger. Proactive cleanup adds logarithmic cost per put and pop but frees memory promptly.

| Operation | Lazy Only | With Heap Cleanup |
|---|---|---|
| put | O(1) | O(log n) |
| get | O(1) | O(1) |
| cleanup | N/A | O(k log n) per sweep |
| Memory | Stale entries linger | Freed promptly |

JAVA
// Lazy: O(1) get, O(1) put, stale entries stay in memory
// Heap: O(log n) put (heap push), O(1) get, O(k log n) cleanup

What are the edge cases?

Edge cases include getting a key that was never put, getting a key exactly at its expiry time (should be a miss with strict less-than), putting the same key multiple times, and cleanup running when no entries have expired.

JAVA
package com.bank.service;

public class TTLEdgeCases {
    public static void main(String[] args) {
        TTLCache<String> cache = new TTLCache<>();

        // Never put
        System.out.println(cache.get("unknown", 100)); // null

        // Exactly at expiry (now == expiresAt -> miss)
        cache.put("key", "val", 10, 100);
        System.out.println(cache.get("key", 110)); // null (110 >= 110)
        System.out.println(cache.get("key", 109)); // "val" (109 < 110)
    }
}
TEXT
null
null
val

What are common mistakes?

The most common mistake is not attaching a version to expiry records, allowing stale cleanup events to delete freshly rewritten entries. Another mistake is using less-than-or-equal instead of strictly-less-than for the validity check, causing off-by-one behavior at the expiry boundary.

JAVA
// WRONG: no version check in cleanup
if (entry != null) {
    store.remove(record.key); // may delete a freshly rewritten entry!
}

// CORRECT: version check
if (entry != null && entry.version == record.version) {
    store.remove(record.key); // only delete if versions match
}

How would you apply this in a banking system?

At the National Bank of India, the system caches transfer authorization codes with short TTLs. Customers frequently refresh a code before the old one expires. The versioned expiry records ensure background cleanup never deletes a refreshed code.

JAVA
package com.bank.service;

public class AuthCodeCacheService {
    private final TTLCache<String> cache = new TTLCache<>();

    public void issueCode(String customerId, String code, long ttlSeconds, long now) {
        cache.put(customerId, code, ttlSeconds, now);
    }

    public String validateCode(String customerId, long now) {
        return cache.get(customerId, now);
    }
}

What should a senior engineer know?

A senior engineer should know the trade-off between lazy and proactive expiry. Lazy is simpler but lets expired entries consume memory. Proactive with a heap adds complexity but keeps memory bounded. They should also ensure the strictly-less-than comparison is consistent in both the get path and the cleanup path.

JAVA
// Consistency: both paths must use the same comparison
// get: now >= expiresAt -> expired (strictly less-than validity)
// cleanup: record.expiresAt <= now -> expired (same logic)
// Mismatch between these causes the entry to be alive in get
// but dead in cleanup, or vice versa.

Visual Overview

DIAGRAM
Timeline for key "rajesh-otp":

  Time 100: put("rajesh-otp", "1234", ttl=120)
    Entry: value="1234", expires=220, version=1
    Heap record: (key="rajesh-otp", expires=220, version=1)

  Time 150: put("rajesh-otp", "5678", ttl=120)
    Entry: value="5678", expires=270, version=2
    Heap record: (key="rajesh-otp", expires=270, version=2)

  Time 220: cleanup fires
    Pop record: (expires=220, version=1)
    Current entry version=2 ≠ 1 → STALE → discard
    Entry "5678" survives!

  Time 270: cleanup fires
    Pop record: (expires=270, version=2)
    Current entry version=2 == 2 → DELETE

┌──────────────┬────────┬──────────┬─────────┐
│ Time         │ Action │ Version  │ Entry   │
├──────────────┼────────┼──────────┼─────────┤
│ 100          │ put    │ v1       │ "1234"  │
│ 150          │ put    │ v2       │ "5678"  │
│ 220 (stale)  │ skip   │ v1 ≠ v2 │ "5678"  │
│ 270          │ delete │ v2 == v2 │ removed │
└──────────────┴────────┴──────────┴─────────┘

Key Takeaway

A cache with time-to-live stores each key alongside an absolute expiry timestamp, and a read is valid only while the current time is strictly before that expiry. Lazy expiry checks validity on every get in O(1), treating expired entries as misses. This is simple but lets expired entries linger in memory.

The subtle correctness problem appears with proactive cleanup. When a key is rewritten with a new value and expiry, a pending cleanup event for the old expiry could fire and delete the fresh entry. The solution is versioning: each write bumps a version number, and each heap record carries the version it was created with. Cleanup only deletes when versions match; otherwise the record is stale and discarded.

The heap adds O(log n) per put and per pop. The lazy get path stays O(1). The strictly-less-than validity comparison must be consistent in both the get and cleanup paths to avoid edge-case inconsistencies.

At the National Bank of India, we cached short-lived transfer authorization codes. Customers frequently refreshed a code before the old one expired. The versioned expiry records ensured background cleanup never deleted a freshly renewed code.

Remember one sentence: stamp every expiry record with a version, and only delete on cleanup if the version still matches the live entry.

---

Share
Use ← → arrow keys to navigate