Design a logger rate limiter

01The design, in the six-step framework

1. Requirements and use cases

Often given open-ended: the candidate must define the methods, the assumptions and the tests. The base problem is easy. The reported follow-ups are not: timestamps out of order, top-K messages, and memory that must not grow forever.

• A logger asks whether to print a message at timestamp t; the answer is yes if the same message was not printed in the last 10 seconds.
• Each message has an independent window.
• A rejected message does not restart its window; only accepted prints count.
• Follow-up: timestamps arrive out of order.
• Follow-up: a caller asks for the top K messages by accepted count.
• Follow-up: evict state for messages that have gone quiet.

Out of scope: distributed limits, per-severity rules, and text normalisation (messages are compared exactly). Non-functional constraints: the decision is O(1) in the in-order case; memory is bounded by messages active in the last window once eviction is on; and the boundary is stated: at exactly t + 10 a message may print again.

2. Core entities and relationships

• LoggerLimiter: in-order version; maps each message to its next allowed time.
• Expiry queue: a deque of (time, message) in acceptance order, used to drop quiet messages.
• OutOfOrderLimiter: keeps a sorted list of accepted times per message and answers by neighbours.
• TopMessages: accepted counts per message, with a top-K query.

The limiter composes its map and queue. TopMessages is a separate collaborator told about each accepted message, so the decision logic and the statistics change independently. The in-order and out-of-order classes share a method name, so a caller swaps one for the other at construction, and the out-of-order version carries a real cost that only some callers should pay.

3. Interfaces and key methods

from typing import List, Protocol


class Limiter(Protocol):
    def should_print(self, t: int, message: str) -> bool:
        """True and recorded if allowed; False leaves all state unchanged."""


class TopMessages:
    def record(self, message: str) -> None:
        """Count one accepted print."""

    def top(self, k: int) -> List[str]:
        """Up to k messages by count descending; ties alphabetical, so results are stable."""

Invariants: a rejected call changes nothing; in the in-order class, next_ok[m] equals the last accepted time for m plus the window; in the out-of-order class, any two accepted times for a message are at least the window apart, in any arrival order.

4. Design patterns and the choices behind them

Store the next allowed time

The force is simplicity. A dictionary from message to next allowed time decides in O(1). The alternative, one queue per message, is more memory for no benefit here. The subtle rule is that a rejection must not update the map; otherwise a noisy message is silenced forever, because each attempt pushes its window out. Treat this as an API contract, and write it in the docstring.

Bounded memory by evicting quiet messages

The force is an unbounded set of messages, since real logs contain ids. A message whose window has passed needs no state: forgetting it gives the same answer as remembering it. Accepted times are in order, so a deque of (next allowed time, message) lets each call pop expired entries in amortised O(1). The check that the stored time still matches keeps a re-accepted message from being dropped by its old queue entry. This is lazy expiry with no sweeper.

Out of order changes the question

The force is a late arrival. Suppose times 20 then 12 arrive for one message. With only "next allowed", 12 is rejected, yet 12 is 8 seconds before 20, and rejecting is right only because of 20. Now try 5 after 20: it is 15 away from 20 and should pass, but the map says no, and if it passes it may conflict with an earlier neighbour. The correct check compares against both neighbours among accepted times, with a sorted list per message and binary search: reject if the predecessor is within the window or the successor is. Rejected events do not join the history, as the report says. Using bisect.insort costs O(a) for a accepted times, which is fine if history is trimmed by a watermark.

Top-K with a heap at query time

The force is that counts change on each accept while top-K queries are rare. Keeping a counter and running heapq.nsmallest at query time costs O(m log k). If queries are frequent, keep a bucket structure instead, as in the frequency container. See heaps in design.

5. Core flow and code

Flow for an in-order sequence: "a" at 1, "a" at 5, "a" at 11:

1. At 1 there is no entry, so it prints; next_ok["a"] = 11, and (11, "a") joins the queue.
2. At 5, 5 is less than 11, so it returns false and changes nothing.
3. At 11 the queue front (11, "a") has expired, so the entry is dropped; no record remains, it prints, and next_ok["a"] = 21.

import bisect
import heapq
from collections import Counter, deque
from typing import Deque, Dict, List, Optional, Tuple


class TopMessages:
    def __init__(self) -> None:
        self.counts: Counter = Counter()

    def record(self, message: str) -> None:
        self.counts[message] += 1

    def top(self, k: int) -> List[str]:
        best = heapq.nsmallest(k, self.counts.items(), key=lambda kv: (-kv[1], kv[0]))
        return [m for m, _ in best]


class LoggerLimiter:
    """Timestamps are non-decreasing. Memory holds only messages inside their window."""

    def __init__(self, window: int = 10, stats: Optional[TopMessages] = None) -> None:
        self.window = window
        self.next_ok: Dict[str, int] = {}
        self.recent: Deque[Tuple[int, str]] = deque()
        self.stats = stats

    def should_print(self, t: int, message: str) -> bool:
        self._evict(t)
        if t < self.next_ok.get(message, t):
            return False
        allowed_again = t + self.window
        self.next_ok[message] = allowed_again
        self.recent.append((allowed_again, message))
        if self.stats:
            self.stats.record(message)
        return True

    def _evict(self, t: int) -> None:
        while self.recent and self.recent[0][0] <= t:
            when, message = self.recent.popleft()
            if self.next_ok.get(message) == when:
                del self.next_ok[message]


class OutOfOrderLimiter:
    """Any arrival order. Accepted times per message are kept at least `window` apart."""

    def __init__(self, window: int = 10, stats: Optional[TopMessages] = None) -> None:
        self.window = window
        self.accepted: Dict[str, List[int]] = {}
        self.stats = stats

    def should_print(self, t: int, message: str) -> bool:
        times = self.accepted.setdefault(message, [])
        i = bisect.bisect_left(times, t)
        if i > 0 and t - times[i - 1] < self.window:
            return False
        if i < len(times) and times[i] - t < self.window:
            return False
        times.insert(i, t)
        if self.stats:
            self.stats.record(message)
        return True

    def trim(self, watermark: int) -> None:
        """Forget accepted times older than watermark - window; no event can conflict with them."""
        for message, times in list(self.accepted.items()):
            del times[:bisect.bisect_left(times, watermark - self.window)]
            if not times:
                del self.accepted[message]


if __name__ == "__main__":
    stats = TopMessages()
    lim = LoggerLimiter(stats=stats)
    assert lim.should_print(1, "a") and not lim.should_print(5, "a")
    assert lim.should_print(11, "a")               # exactly at the boundary
    assert lim.should_print(11, "b") and lim.should_print(100, "c")
    assert list(lim.next_ok) == ["c"]              # quiet messages forgotten
    assert stats.top(2) == ["a", "b"]

    o = OutOfOrderLimiter()
    assert o.should_print(20, "m")
    assert not o.should_print(12, "m")             # within 10 of 20
    assert o.should_print(5, "m")                  # 15 before 20: allowed
    assert not o.should_print(14, "m")             # within 10 of 20; rejected, not recorded
    assert o.should_print(30, "m") and o.accepted["m"] == [5, 20, 30]
    o.trim(100)
    assert not o.accepted

6. Extensions, concurrency and what interviewers probe

• Rejected events. They enter no history. This is the first assumption to state, and the report's follow-up depends on it.
• The boundary. Exactly 10 seconds later is allowed; the usual slip is > against >=. Test at t + 9 and t + 10.
• Duplicates within the window, both dropped. One reported variant drops every message seen twice in a window, including the first. That needs a held-back buffer until the window closes, so output is delayed by 10 seconds. Ask which behaviour is wanted.
• Evicting the least important logs. With a fixed memory budget, a heap keyed by importance then time discards the least valuable first; this is a separate class from the limiter.
• Thread safety. The check and the update must be one atomic step, or two threads both print. A lock per message hash keeps writers of different messages apart, using the same striping as the hit counter.
• Common mistake. Updating the timestamp on a rejection, which silences a chatty message forever.

02Where this question was reported

• LeetCode Discuss · LeetCode 359 (Easy), Google-tagged, freq 51.1; also named in Hello Interview's Google L5 guide and TechPrep's Google LLD list
• Hello Interview · Hello Interview Google L5 guide lists 'Leetcode 359. Logger Rate Limiter' among senior coding questions
• techprep.app · TechPrep Google LLD: https://www.techprep.app/problems/logger-rate-limiter?topic=low-level-design
• FastPrep · Follow-up: timestamps arrive out of order; rejected events don't enter accepted history; per-message independent windows
• LeetCode Discuss · Open-ended: candidate had to define methods, assumptions and tests; follow-up variant drops messages duplicated within the window
• Land the Lab · 'Logger that reports its top K messages'; also 'Log manager that evicts the least important logs'
• techprep.app · Named as a typical Google LLD prompt alongside parking lot and in-memory file system
• vikyding.gitbooks.io · LC 359 in a Google-tagged collection
• Taro · Taro problem page; boundary (>= vs >) is the usual mistake