Single-Flight Cache Loader

The home page's "deals" block takes loadMs to build and is cached for ttlMs. When it expires, thousands of concurrent requests would all rebuild it. Implement a cache that coalesces loads (like Go's singleflight or a rebuild lock). Time is passed in explicitly.

SingleFlightCache(loadMs, ttlMs):

get(key, nowMs):
1. If a load for key started at time s and nowMs ≥ s + loadMs, it has completed: the value is cached until s + loadMs + ttlMs.
2. If the key is cached and nowMs < expiresAt, return "hit".
3. Else if a load for the key is in flight, return "wait" (the caller joins it).
4. Else start a load now and return "load".
loads(key) — how many loads were started for the key.

Calls arrive with non-decreasing nowMs. See Cache Stampedes.

Example 1

Input: ["SingleFlightCache","get","get","get","get","get","get","loads"]
[[100,1000],["k",0],["k",10],["k",50],["k",100],["k",1099],["k",1100],["k"]]
Output: [null,"load","wait","wait","hit","hit","load",2]
Explanation: Requests during the first load wait for it; the value is fresh from 100 to 1100, then one request reloads.

Solution and explanation

Show the solution

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

The key idea is a per-key in-flight marker: the first miss starts the load and records it; later misses see the marker and join instead of starting their own. When the load finishes, the value is cached and the marker cleared. In a real service the marker is a promise/future in memory (singleflight, Caffeine loaders) or a short-lived Redis lock (SET lock NX PX) shared by all instances, and joiners either wait for the result or serve a stale copy.

Reference solution

class SingleFlightCache {
  constructor(loadMs, ttlMs) {
    this.loadMs = loadMs;
    this.ttlMs = ttlMs;
    this.inflight = new Map(); // key -> load start
    this.expires = new Map();  // key -> expiresAt
    this.count = new Map();    // key -> loads started
  }

  get(key, nowMs) {
    const start = this.inflight.get(key);
    if (start !== undefined && nowMs >= start + this.loadMs) {
      this.expires.set(key, start + this.loadMs + this.ttlMs);
      this.inflight.delete(key);
    }
    if (this.expires.has(key) && nowMs < this.expires.get(key)) return "hit";
    if (this.inflight.has(key)) return "wait";
    this.inflight.set(key, nowMs);
    this.count.set(key, (this.count.get(key) ?? 0) + 1);
    return "load";
  }

  loads(key) {
    return this.count.get(key) ?? 0;
  }
}

class SingleFlightCache {
  private inflight = new Map<string, number>();
  private expires = new Map<string, number>();
  private count = new Map<string, number>();

  constructor(private loadMs: number, private ttlMs: number) {}

  get(key: string, nowMs: number): string {
    const start = this.inflight.get(key);
    if (start !== undefined && nowMs >= start + this.loadMs) {
      this.expires.set(key, start + this.loadMs + this.ttlMs);
      this.inflight.delete(key);
    }
    const exp = this.expires.get(key);
    if (exp !== undefined && nowMs < exp) return "hit";
    if (this.inflight.has(key)) return "wait";
    this.inflight.set(key, nowMs);
    this.count.set(key, (this.count.get(key) ?? 0) + 1);
    return "load";
  }

  loads(key: string): number {
    return this.count.get(key) ?? 0;
  }
}

class SingleFlightCache:
    def __init__(self, load_ms: int, ttl_ms: int):
        self.load_ms = load_ms
        self.ttl_ms = ttl_ms
        self.inflight: dict[str, int] = {}
        self.expires: dict[str, int] = {}
        self.count: dict[str, int] = {}

    def get(self, key: str, now_ms: int) -> str:
        start = self.inflight.get(key)
        if start is not None and now_ms >= start + self.load_ms:
            self.expires[key] = start + self.load_ms + self.ttl_ms
            del self.inflight[key]
        if key in self.expires and now_ms < self.expires[key]:
            return "hit"
        if key in self.inflight:
            return "wait"
        self.inflight[key] = now_ms
        self.count[key] = self.count.get(key, 0) + 1
        return "load"

    def loads(self, key: str) -> int:
        return self.count.get(key, 0)

<?php

class SingleFlightCache
{
    private array $inflight = [];
    private array $expires = [];
    private array $count = [];

    public function __construct(private int $loadMs, private int $ttlMs)
    {
    }

    public function get(string $key, int $nowMs): string
    {
        if (isset($this->inflight[$key]) && $nowMs >= $this->inflight[$key] + $this->loadMs) {
            $this->expires[$key] = $this->inflight[$key] + $this->loadMs + $this->ttlMs;
            unset($this->inflight[$key]);
        }
        if (isset($this->expires[$key]) && $nowMs < $this->expires[$key]) {
            return 'hit';
        }
        if (isset($this->inflight[$key])) {
            return 'wait';
        }
        $this->inflight[$key] = $nowMs;
        $this->count[$key] = ($this->count[$key] ?? 0) + 1;
        return 'load';
    }

    public function loads(string $key): int
    {
        return $this->count[$key] ?? 0;
    }
}

class SingleFlightCache {
    private final int loadMs, ttlMs;
    private final Map<String, Integer> inflight = new HashMap<>();
    private final Map<String, Integer> expires = new HashMap<>();
    private final Map<String, Integer> count = new HashMap<>();

    public SingleFlightCache(int loadMs, int ttlMs) {
        this.loadMs = loadMs;
        this.ttlMs = ttlMs;
    }

    public String get(String key, int nowMs) {
        Integer start = inflight.get(key);
        if (start != null && nowMs >= start + loadMs) {
            expires.put(key, start + loadMs + ttlMs);
            inflight.remove(key);
        }
        Integer exp = expires.get(key);
        if (exp != null && nowMs < exp) return "hit";
        if (inflight.containsKey(key)) return "wait";
        inflight.put(key, nowMs);
        count.merge(key, 1, Integer::sum);
        return "load";
    }

    public int loads(String key) {
        return count.getOrDefault(key, 0);
    }
}

Common mistakes

Forgetting to complete a finished load before checking freshness.
Starting a second load while one is in flight.
Off-by-one on expiry (now < expiresAt is fresh).

Follow-up questions

Serve the stale value to joiners instead of making them wait.
Refresh slightly before expiry (probabilistic early expiration).

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