Design a Rate-Based Alerting System for API Requests

Problem Design a rate-based alerting system for an API. Given a sorted stream of request timestamps in seconds, emit a notification after a request if either more than 3 requests occurred in the last 1 second, or more than 25 requests occurred in the last 10 seconds. Report the total number of notifications sent.

Example [1,1,1,1,1,2,2,2,3,3,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,15] → 4 notifications.

Functional requirements

• Evaluate both window conditions after every incoming request.
• Support multiple independent rules (window length + threshold) evaluated concurrently.
• Emit at most the alerts the rules define; count them.
• Extend to per-API-key / per-endpoint rate tracking rather than one global counter.
• Support adding or changing a rule without a redeploy.

Non-functional requirements

• ~200k requests/sec across the fleet; ~1M distinct API keys tracked independently.
• Per-request evaluation must be O(1) amortized and add < 1 ms to the request path.
• Memory bounded: storing raw timestamps at 200k/sec over a 10 s window is 2M timestamps per rule per key — infeasible at 1M keys, so bucketed counters are required.
• Alert delivery latency < 5 s from the triggering request.
• Counter state must survive a single node loss without producing a storm of false alerts.

Key components

• Per-rule sliding window: one 1-second window and one 10-second window, evaluated independently so each check is O(1) rather than rescanning a shared queue.
• Bucketed counters: fixed-size ring buffer of per-second buckets (10 slots for the 10 s rule). On each request, advance/zero expired buckets, increment the current bucket, and compare the running sum to the threshold. Memory is O(buckets), independent of request volume.
• Rule engine holding the (window, threshold) configs, hot-reloadable.
• Aggregation tier: counters sharded by key so a single hot key doesn't serialize the fleet; a distributed store (Redis) or local counters with periodic rollup.
• Alert dispatcher with deduplication and cooldown, feeding the notification channel.

Deep dives / trade-offs

• Queue of raw timestamps vs bucketed counters: a deque of timestamps is exact and trivially correct, and is the right first answer — but it is O(window x rate) memory and the eviction scan is unbounded on a burst. Bucketed counters are O(1) memory and O(1) per request, at the cost of boundary precision.
• Exactness vs bounded memory: a 1-second bucket granularity means the "last 1 second" is really "the current bucket", which can miss a burst straddling a boundary. Finer buckets (100 ms) reduce the error linearly at 10x the memory. A sliding-window-counter approximation (weighted blend of the current and previous bucket) is the standard middle ground — quantify the error.
• Two windows, one pass: keep them as separate counters rather than deriving the 1 s count from the 10 s structure. Independence is what keeps each check O(1) and lets rules be added freely.
• Distributed counting: at 200k/sec across many nodes, a shared Redis counter per key becomes the bottleneck and adds a network hop to the hot path. Local counting with periodic rollup is fast but each node only sees its slice, so thresholds fire late or not at all. Discuss consistent hashing requests by key so one node owns one key's counters.
• Alert storms: once over threshold, every subsequent request re-triggers. Cooldown/hysteresis and dedup on (key, rule) are what make this usable in production.