Cache with Version-Checked Sets

In cache-aside, a reader can load version 1 from the database, a writer can commit version 2 and invalidate, and the reader can then cache version 1 — a stale set. Prevent it by attaching the database row version to every write into the cache.

set(key, value, version) — store the value if the key has no entry, or if version is greater than the stored entry's version, or (after a delete) if version is at least the delete's version. Return whether it was stored.
delete(key, version) — invalidate after a writer committed version: remove the value but remember a tombstone with that version.
get(key) — the cached value, or null if missing or deleted.

See The Stale-Set Race.

Example 1

Input: ["VersionedCache","set","get","delete","set","get","set","get","set","set"]
[[],["p","100",1],["p"],["p",2],["p","100",1],["p"],["p","80",2],["p"],["p","80",2],["p","70",3]]
Output: [null,true,"100",null,false,null,true,"80",false,true]
Explanation: The slow reader's version-1 set after the version-2 delete is rejected; a fresh reader's version-2 set is accepted.

Solution and explanation

Show the solution

Time O(1) per operation · Space O(keys)

Versions turn "last write wins" into "newest write wins". A live entry only accepts strictly newer versions, so a slow reader can't replace newer data. A delete leaves a tombstone carrying the version that caused it, so a reader that loaded an older version before the delete is rejected, while a reader that loaded the committed version is accepted. In Redis the comparison and write must be one atomic Lua script; memcache's leases solve the same race.

Reference solution

class VersionedCache {
  constructor() {
    this.entries = new Map(); // key -> { value, version, deleted }
  }

  set(key, value, version) {
    const e = this.entries.get(key);
    const ok = !e || (e.deleted ? version >= e.version : version > e.version);
    if (ok) this.entries.set(key, { value, version, deleted: false });
    return ok;
  }

  delete(key, version) {
    this.entries.set(key, { value: null, version, deleted: true });
  }

  get(key) {
    const e = this.entries.get(key);
    return e && !e.deleted ? e.value : null;
  }
}

class VersionedCache {
  private entries = new Map<string, { value: string | null; version: number; deleted: boolean }>();

  set(key: string, value: string, version: number): boolean {
    const e = this.entries.get(key);
    const ok = !e || (e.deleted ? version >= e.version : version > e.version);
    if (ok) this.entries.set(key, { value, version, deleted: false });
    return ok;
  }

  delete(key: string, version: number): void {
    this.entries.set(key, { value: null, version, deleted: true });
  }

  get(key: string): string | null {
    const e = this.entries.get(key);
    return e && !e.deleted ? e.value : null;
  }
}

class VersionedCache:
    def __init__(self):
        self.entries: dict[str, tuple] = {}   # key -> (value, version, deleted)

    def set(self, key: str, value: str, version: int) -> bool:
        e = self.entries.get(key)
        ok = e is None or (version >= e[1] if e[2] else version > e[1])
        if ok:
            self.entries[key] = (value, version, False)
        return ok

    def delete(self, key: str, version: int) -> None:
        self.entries[key] = (None, version, True)

    def get(self, key: str) -> str | None:
        e = self.entries.get(key)
        return e[0] if e and not e[2] else None

<?php

class VersionedCache
{
    private array $entries = [];

    public function set(string $key, string $value, int $version): bool
    {
        $e = $this->entries[$key] ?? null;
        $ok = $e === null || ($e['deleted'] ? $version >= $e['version'] : $version > $e['version']);
        if ($ok) {
            $this->entries[$key] = ['value' => $value, 'version' => $version, 'deleted' => false];
        }
        return $ok;
    }

    public function delete(string $key, int $version): void
    {
        $this->entries[$key] = ['value' => null, 'version' => $version, 'deleted' => true];
    }

    public function get(string $key): ?string
    {
        $e = $this->entries[$key] ?? null;
        return $e !== null && !$e['deleted'] ? $e['value'] : null;
    }
}

class VersionedCache {
    private static final class Entry {
        final String value; final int version; final boolean deleted;
        Entry(String value, int version, boolean deleted) { this.value = value; this.version = version; this.deleted = deleted; }
    }
    private final Map<String, Entry> entries = new HashMap<>();

    public VersionedCache() {}

    public boolean set(String key, String value, int version) {
        Entry e = entries.get(key);
        boolean ok = e == null || (e.deleted ? version >= e.version : version > e.version);
        if (ok) entries.put(key, new Entry(value, version, false));
        return ok;
    }

    public void delete(String key, int version) {
        entries.put(key, new Entry(null, version, true));
    }

    public String get(String key) {
        Entry e = entries.get(key);
        return e != null && !e.deleted ? e.value : null;
    }
}

Common mistakes

Forgetting the tombstone: after a plain delete any old version could be cached again.
Accepting equal versions on live entries (pointless writes).
Rejecting the committed version after a delete (must use ≥).

Follow-up questions

Expire tombstones after the maximum read duration.
Implement set-if-newer as a Redis Lua script.

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Design & Data Structures problems