Sharded Counter for a Hot Row

A viral post's like_count row is updated thousands of times per second; every update holds the row lock for a while, so requests queue. Model a sharded counter: each key has slots counter rows, and an increment uses whichever slot becomes free earliest (the lowest slot index on ties).

ShardedCounter(slots, holdMs):

increment(key, nowMs) — choose the slot as above; the update starts at max(nowMs, slotFreeAt), holds that slot for holdMs, and adds 1 to the key's count. Return the wait in ms (start − nowMs). Calls arrive with non-decreasing nowMs.
get(key) — the total count for the key (sum of all slots); 0 for unknown keys.

Each key has its own slots. See Hot Rows and High-Traffic Counters.

Example 1

Input: ["ShardedCounter","increment","increment","increment","increment","get","increment"]
[[2,10],["p",0],["p",0],["p",0],["p",5],["p"],["q",0]]
Output: [null,0,0,10,5,4,0]
Explanation: Two slots absorb the first two likes immediately; the third waits for slot 0 (free at 10); the fourth gets slot 1 (free at 10) after waiting 5 ms.

Solution and explanation

Show the solution

Time O(slots) per increment, O(1) per get · Space O(keys × slots)

A single row can only absorb about 1 / holdMs updates per unit of time; anything faster queues. With slots rows, increments run in parallel on different rows, multiplying capacity by roughly the number of slots. Reads pay by summing the slots. In SQL: INSERT … ON CONFLICT (post_id, slot) DO UPDATE SET n = n + 1 with a random slot, and SELECT sum(n) … WHERE post_id = ? to read.

Reference solution

class ShardedCounter {
  constructor(slots, holdMs) {
    this.slots = slots;
    this.holdMs = holdMs;
    this.state = new Map(); // key -> { freeAt: number[], count }
  }

  increment(key, nowMs) {
    if (!this.state.has(key)) this.state.set(key, { freeAt: new Array(this.slots).fill(0), count: 0 });
    const s = this.state.get(key);
    let best = 0;
    for (let i = 1; i < this.slots; i++) if (s.freeAt[i] < s.freeAt[best]) best = i;
    const start = Math.max(nowMs, s.freeAt[best]);
    s.freeAt[best] = start + this.holdMs;
    s.count += 1;
    return start - nowMs;
  }

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

class ShardedCounter {
  private state = new Map<string, { freeAt: number[]; count: number }>();

  constructor(private slots: number, private holdMs: number) {}

  increment(key: string, nowMs: number): number {
    let s = this.state.get(key);
    if (!s) {
      s = { freeAt: new Array(this.slots).fill(0), count: 0 };
      this.state.set(key, s);
    }
    let best = 0;
    for (let i = 1; i < this.slots; i++) if (s.freeAt[i] < s.freeAt[best]) best = i;
    const start = Math.max(nowMs, s.freeAt[best]);
    s.freeAt[best] = start + this.holdMs;
    s.count += 1;
    return start - nowMs;
  }

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

class ShardedCounter:
    def __init__(self, slots: int, hold_ms: int):
        self.slots = slots
        self.hold_ms = hold_ms
        self.free_at: dict[str, list[int]] = {}
        self.counts: dict[str, int] = {}

    def increment(self, key: str, now_ms: int) -> int:
        free = self.free_at.setdefault(key, [0] * self.slots)
        best = min(range(self.slots), key=lambda i: free[i])   # first slot on ties
        start = max(now_ms, free[best])
        free[best] = start + self.hold_ms
        self.counts[key] = self.counts.get(key, 0) + 1
        return start - now_ms

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

<?php

class ShardedCounter
{
    private array $freeAt = [];
    private array $counts = [];

    public function __construct(private int $slots, private int $holdMs)
    {
    }

    public function increment(string $key, int $nowMs): int
    {
        if (!isset($this->freeAt[$key])) {
            $this->freeAt[$key] = array_fill(0, $this->slots, 0);
            $this->counts[$key] = 0;
        }
        $best = 0;
        for ($i = 1; $i < $this->slots; $i++) {
            if ($this->freeAt[$key][$i] < $this->freeAt[$key][$best]) {
                $best = $i;
            }
        }
        $start = max($nowMs, $this->freeAt[$key][$best]);
        $this->freeAt[$key][$best] = $start + $this->holdMs;
        $this->counts[$key]++;
        return $start - $nowMs;
    }

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

class ShardedCounter {
    private final int slots;
    private final int holdMs;
    private final Map<String, int[]> freeAt = new HashMap<>();
    private final Map<String, Integer> counts = new HashMap<>();

    public ShardedCounter(int slots, int holdMs) {
        this.slots = slots;
        this.holdMs = holdMs;
    }

    public int increment(String key, int nowMs) {
        int[] free = freeAt.computeIfAbsent(key, k -> new int[slots]);
        int best = 0;
        for (int i = 1; i < slots; i++) if (free[i] < free[best]) best = i;
        int start = Math.max(nowMs, free[best]);
        free[best] = start + holdMs;
        counts.merge(key, 1, Integer::sum);
        return start - nowMs;
    }

    public int get(String key) {
        return counts.getOrDefault(key, 0);
    }
}

Common mistakes

Sharing slots between keys.
Not starting at max(now, freeAt) — negative waits.
Choosing the last instead of the first slot on ties.

Follow-up questions

Adapt the number of slots to how hot a key is.
Replace the sum on read with a periodically refreshed cached total.

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