Design an Order Processing API with Time-Window Queries

Problem Design an API that processes incoming order batches, where each batch contains multiple orders with different timestamps, and supports querying the number of orders placed in the last X minutes (X up to 30).

Functional requirements

• Ingest batches of orders, each carrying its own timestamp.
• Answer "how many orders in the last X minutes" for any X from 1 to 30.
• Handle concurrent batch submissions from multiple threads/clients.
• Correctly age out data older than 30 minutes.
• Reject or handle orders with timestamps outside the tracked window.

Non-functional requirements

• ~50k orders/sec at peak arriving in batches of ~1,000.
• Query p99 < 5 ms — the answer is a sum of at most 30 integers, so anything slower means a design mistake.
• Memory strictly bounded: 30 counters regardless of order volume, versus ~90M raw timestamps if every order were retained for the window.
• Ingest must not block queries; both run concurrently across many threads.
• Counts may be approximate at the current-minute boundary; older buckets must be exact.

Key components

• A fixed circular array of 30 buckets, each representing one minute.
• Bucket index: order_timestamp_minute mod 30, giving O(1) placement with no allocation and no growth.
• Per-bucket last-written-minute stamp, so a bucket that has aged out (its stamp is more than 30 minutes stale) is lazily reset to zero before being read or incremented, rather than swept by a background thread.
• Query: sum the X buckets covering the requested window.
• Concurrency control: a ReentrantLock, per-bucket locks, or atomic counters guarding concurrent increments and the reset-on-access path.

Deep dives / trade-offs

• Circular buffer vs storing raw orders: retaining timestamps is exact and supports arbitrary later queries, but is O(orders) memory — at 50k/sec that's 90M timestamps in the window for a question answerable with 30 integers. The ring buffer is O(1) memory and O(1) ingest; the cost is that you can only answer the queries you bucketed for.
• Lazy reset vs a sweeper thread: lazy reset (check the bucket's stamp on access, zero it if stale) needs no background thread and no timer, but the staleness check must happen on both read and write, and it is easy to write a version that under-counts a bucket read twice in the same minute. A sweeper is simpler to reason about but adds a thread and a drift/pause risk. Walk through the bug where a query at minute 40 reads a bucket last written at minute 5 — without the stamp check it returns 35-minute-old data as if it were current.
• Lock granularity: one global ReentrantLock is trivially correct and serializes all ingest — at 50k/sec that lock is the bottleneck. Per-bucket locks give near-full parallelism since concurrent orders usually target the current bucket... which means they contend on exactly one lock anyway. Atomic counters (LongAdder-style striping) sidestep the contention; discuss why the read path then can't get a consistent snapshot across buckets, and whether that matters here (it usually doesn't — the window is approximate at the edge by nature).
• Read/write consistency: a query summing 30 buckets while writers increment them is not atomic. You get a slightly-off count, not a corrupt one. Say explicitly that this is acceptable and why locking the whole ring for a read would be the worse choice.
• Out-of-window timestamps: a batch containing an order from 45 minutes ago maps via mod 30 onto a live bucket and silently corrupts it. The modulo must be paired with an absolute-minute check, not trusted alone — this is the single most common bug in this design.
• Extending beyond one process: the ring lives in one JVM's memory. Across N API instances each holds a partial count, so the true answer needs a shared store or a rollup — state the limitation.