Windowed Aggregation over Event Streams

Learning outcomes

Trade Republic’s documented coding prompt asks you to compute the net portfolio value per user over the last thirty days from a stream of user transactions, each carrying an id, a timestamp, an amount, and a buy or sell side. On the surface this is a sum with a group-by, which is trivial. The interest is everything the stream adds: the window slides with wall-clock time, events arrive out of order, the same event may arrive more than once, and the aggregation must stay correct across all of it. This concept derives the windowed aggregate from a naive recomputation up to the per-key stateful pattern that Kafka Streams implements, teaching why each complication forces a design change.

After studying this page, you can:

• Derive the per-key running sum with time-based eviction and justify its amortized constant per-event cost.
• Distinguish event-time windows from processing-time windows and explain why each breaks differently.
• Explain why monotonic-clock assumptions fail and how watermarks bound out-of-order events.
• Implement idempotent aggregation keyed by transaction id so duplicates and retries are safe.
• Map the design onto a Kafka Streams windowed aggregate topology and name each piece.

The prompt and streaming mental model

The exact prompt is: given user transactions (id, ts, amount, buy or sell), compute net portfolio value per user over the last 30 days. Restate it as four simultaneous requirements. The aggregation is a per-user sum of signed amounts, where a buy contributes plus amount and a sell contributes minus amount. The window is the last thirty days, which slides with time, so the live set per user changes continuously. The grouping is by user, so there is one independent aggregate per user. The input is a stream, so the answer must update incrementally rather than by recomputation.

Net value per user u at time t is the signed sum over transactions in the 30-day window ending at t, signed positive for buys and negative for sells.

Four complications stack on top of the formula. Events arrive out of order, so a transaction with an older timestamp can land after a younger one. Events duplicate under retry, so the same transaction id can arrive twice. Events arrive late relative to the wall clock, so a window that has already emitted may need a correction. And the aggregation state lives across many instances, so per-user state must be partitionable. Each complication is solved by a different mechanism, and the design is the composition of all of them.

A customer opens the app and sees their net portfolio value. That number is the running result of every transaction they have ever made, restricted to a relevant time horizon. The prompt isolates one slice of that: the net of buy and sell amounts per user over the last thirty days. Buy a stock and the net goes up by the amount, sell and it goes down. Summed per user, over the rolling window, that is the answer.

What looks like a database query becomes an event-streaming problem the moment the data arrives as a continuous feed and the answer must be current at any instant. The thirty-day window is not a fixed range, it slides forward every second, so yesterday’s transactions age out while today’s arrive. The aggregation is not a one-shot computation, it is a stateful transform that updates incrementally as events flow. And the events themselves are unreliable in three specific ways: they arrive out of timestamp order when they come from multiple venues, they arrive more than once when delivery retries, and they arrive late relative to a window that may already have emitted its result. A design that ignores any of these produces a number that is occasionally, silently wrong.

The naive recomputation and why it fails

The baseline is to store every transaction and, whenever the net is asked for a user, recompute the sum over the window. It is correct and obvious, and its cost is what disqualifies it.

Per-query cost of recomputation, linear in the user's transaction count, with unbounded total storage.

Every query walks every transaction the user made in the window. At the arrival rates of a retail brokerage that is expensive on every read, and the storage holds every transaction ever, not just the live window. Worse, the recomputation does not help the continuous case, where the answer must be current without an explicit query. The structure throws away the information it had: between two events for the same user, almost all the contributions to the net are unchanged. The optimal design keeps the running net per user and adjusts it by what entered and what left, exactly the running-sums trick from the sliding window concept, now keyed by user and with time-based eviction.

Per-key running sums with expiry

The incremental design holds one running sum per user, plus a per-user queue of the transactions currently in the window, ordered by timestamp. On every new transaction for a user, the design adds the signed amount to that user’s sum, appends the transaction to the user’s queue, then evicts from the front of the queue every transaction whose timestamp fell behind the window cutoff, subtracting each as it leaves. The net for a user is then just its running sum, read in constant time.

The amortized argument is the same as for any sliding window: each transaction is inserted once and evicted at most once, so across N events the total eviction work is O(N), and each event is amortized constant per user.

Each transaction is inserted once and evicted at most once, so per-event work is amortized constant, and the net reads in constant time per user.

The memory bound is per-user and proportional to the live window, not to all history, because expired transactions leave the queue. Across all users the bound is the total live transaction volume, which is the right operational target.

Event time versus processing time

The first design decision that changes correctness is which clock defines the window. Event time is the timestamp carried by the transaction itself, when the trade actually happened. Processing time is when the stream processor observes the event, which may be much later due to ingestion lag. A window defined on processing time closes when the processor’s clock crosses the boundary. A window defined on event time closes when the processor has seen every event whose timestamp falls in the window, which is a stronger and harder claim.

The two produce different answers whenever ingestion lags. A trade that happened at 11:59 but is ingested at 12:01 lands in the 11:00 to 12:00 event-time window, but in the 12:00 to 13:00 processing-time window. For a net-portfolio number the customer sees, event time is correct: the customer cares when the trade happened, not when the system learned about it. The prompt’s last thirty days is an event-time window, which commits the design to handling event time, and that commitment is what makes out-of-order events a problem.

Processing-time windows are cheaper and wrong for money

A processing-time window needs no watermark and no buffering, because the processor’s clock is monotonic and locally observable. It is the easy choice. It is also wrong for any money-facing number, because a lagged trade lands in the wrong window and the net is off by the trade’s amount. Event time is harder and correct; choose it whenever the timestamp on the event is the truth.

The distinction extends to the physical storage layout. A processing-time window can be implemented as a simple TTL on the per-user queue, because the expiry deadline is known at insert time (insert-time plus window). An event-time window cannot, because the expiry deadline depends on the event’s timestamp, which may be far in the past or the future relative to the insert time. The per-user queue must keep events in event-time order, not arrival order, which means the insert of a late event may need to sort into the queue rather than simply append. This is the implementation cost of event-time correctness, and it is worth naming in the interview.

Out-of-order events and watermarks

Event-time windows commit the design to handling out-of-order arrival. Two venues reporting the same user’s trades arrive on different schedules, a retry resends an old transaction after newer ones, a batch load injects a backfill of historical events. In all these cases a transaction with an older timestamp lands after transactions with younger timestamps, and the naive head-eviction loop, which assumes arrival order matches timestamp order, misplaces it.

The mechanism that bounds this disorder is a watermark. A watermark is the processor’s assertion that it has probably seen every event with a timestamp older than some bound, so any window older than the watermark is closed and its result can be emitted. Events that arrive after the watermark has passed their timestamp are late events, and the system must decide whether to drop them, route them to a side output, or recompute and emit a correction.

A bounded-out-of-orderness watermark is the common policy. The processor assumes events arrive at most, say, five minutes out of order, so it advances the watermark to the largest seen timestamp minus five minutes. Events older than that are treated as late. The bound is a latency-versus-completeness trade: a larger bound waits longer to close windows and captures more late events but increases latency, a smaller bound emits faster but drops more late events. For a thirty-day net-portfolio window the bound can be generous, because the window is long and a few minutes of lag is negligible; for a one-minute alerting window the bound must be tight or the alert fires on incomplete data.

Watermark code sketch

A simple watermark tracker keeps the largest observed timestamp and a configurable slack. It reports whether a given timestamp is late relative to the current watermark.

In a production stream processor, the watermark is more sophisticated: it tracks the progress of every input partition, not just the max across all events, and it pauses a partition’s watermark advancement when that partition is silent. The simple tracker above is what the candidate can sketch in an interview to show they understand the mechanism, before extending it to the multi-partition case the interviewer may ask about.

Idempotent aggregation and deduplication

The second design decision that changes correctness is duplication. A delivery retry sends the same transaction twice. A failover resends a batch that the primary already applied. Without protection the aggregation counts the transaction’s amount twice, and the net is off by exactly that amount, which for a money-facing number is unacceptable.

The fix is idempotent aggregation keyed by transaction id. The processor records every transaction id it has applied, and before adding an event’s amount to the running sum it checks whether that id was already applied. If it was, the event is a duplicate and is skipped. If it was not, the processor applies the amount and records the id. The same logic that protects a retried trade execution protects a retried aggregation.

The seen set is the same idempotency-key idea from the money-safety concept, applied here to a stream aggregation rather than a trade execution. Its growth is the operational cost: the set holds every id ever seen, and over a long run it must be partitionable, time-bounded, or approximated by a bounded dedup structure. The honest operational answer is that the seen set is itself a stateful store, usually sharded by the same key as the aggregation so that dedup and aggregation live on the same instance and never miss.

Idempotent aggregation sums over distinct transaction ids, so a retried event with the same id contributes once, never twice.

Partitioning and state locality

The per-user state (the running sum, the queue of live transactions, and the dedup seen set) must live on one instance per user for the aggregate to be correct. If two instances hold parts of the same user’s state, they race on the user’s net value, and the result is the same kind of lost update as the concurrency bug-hunting concept describes, now across processes instead of threads.

The design partitions the input by user id so that all events for a given user route to the same instance. The partition key is the user id derived from the transaction id prefix. Within an instance, the per-user state is a local hash map, and because all events for that user arrive on the same thread (or are serialized through the partition processing), the per-user updates are naturally single-threaded with no cross-thread race. This is the co-partitioning pattern: the input topic and the state store are partitioned on the same key, so one Kafka Streams task owns a complete subset of users.

Partition by the aggregation key, always

If the input is not partitioned by user id, two instances can receive events for the same user and the per-user state becomes inconsistent. The design must either repartition the input (add a keyBy step in the stream processor) or route events to the correct instance through a consistent hash ring. Co-partitioning is the simpler and more common choice in Kafka Streams.

How this maps to Kafka Streams

The design above is, almost component for component, what a Kafka Streams windowed aggregate implements. Kafka Streams is the stream-processing library Trade Republic uses for its real-time pipelines, and the abstractions it exposes are the abstractions the hand-derived design needed.

The per-user state is a state store, an embedded key-value store partitioned by user id, co-partitioned with the input topic so that all events for a user route to the same instance. The grouping by user is a keyBy on the user id. The running sum is an aggregator that the framework calls on every event, passing the current aggregate and the new event and receiving the new aggregate. The window is a time-window specification with an inactivity gap that plays the role of the watermark: a window closes when no new events arrive for it within the gap, after which its result is emitted and its state can be discarded. The idempotency is achieved by the framework’s exactly-once processing, which uses transactional offsets and state-store updates so that a retried event re-applies the aggregate only if its prior application did not commit.

The mapping clarifies which pieces are the application’s responsibility and which the framework provides. The application owns the aggregator (the signed-sum logic), the window definition (thirty days, event time, with an inactivity gap), and the keying (by user). The framework owns the state-store partitioning, the watermarking, the exactly-once delivery, and the failover that restores state from the changelog. A senior candidate names this split, because it shows they know where the hard distributed-systems work lives and why a framework provides it rather than reimplementing it by hand.

The changelog topic is a critical detail a senior candidate names. Every state store in Kafka Streams is backed by a compacted changelog topic. When a task fails over to another instance, the new instance replays the changelog to reconstruct the state store. The changelog is partitioned identically to the input topic, so the failover is local to one partition and does not require a full rebuild. This is the durability-and-recovery mechanism that makes the per-user state robust to instance failure, and any design that omits it has a gap the interviewer will probe.

Common mistakes candidates make

The first mistake is treating the prompt as a database query rather than a stream. A query recomputes on demand, a stream maintains continuously, and the design must reflect that the answer updates on every event without being asked.

The second mistake is choosing processing time for the window because it is easier. For a money-facing net value the window must be event time, because a lagged trade belongs to the window when it happened, not when the system saw it. Choosing processing time silently misattributes trades across window boundaries.

The third mistake is assuming events arrive in timestamp order. They do not, once multiple venues or retries are involved, and a head-eviction loop that assumes monotonic timestamps misplaces late events. The fix is a watermark with a bounded out-of-orderness policy.

The fourth mistake is forgetting duplication. A retried event with the same id contributes its amount twice without idempotent aggregation, and the net drifts by exactly the duplicated amounts. The fix is dedup by transaction id, with the seen set partitioned alongside the aggregation.

The fifth mistake is reimplementing the distributed machinery by hand. State partitioning, watermarking, exactly-once delivery, and failover restore are exactly what a framework like Kafka Streams provides, and a senior answer names the framework and the split of responsibilities rather than hand-rolling each piece.

The sixth mistake is ignoring state recovery. A per-user state store that lives only in process memory is lost on a crash or redeploy, and recovering it from the input stream costs an unbounded replay. The answer must mention a durable state store or a changelog topic that reconstructs the state on failover, which is what Kafka Streams provides natively.

What the interviewer asks next

The first follow-up asks how the design handles an event that arrives after its window would have closed. The expected answer names event time, the watermark, and the late-event policy (drop, side output, or correction), and justifies the out-of-orderness bound against the window length.

The second follow-up asks what happens when the same transaction arrives twice. The expected answer is idempotent aggregation keyed by transaction id, with the dedup state partitioned by the same key as the aggregation so the check and the update live on the same instance.

The third follow-up probes the difference between event time and processing time for this specific number. The expected answer is that event time is correct for a money-facing net because the trade’s timestamp is the truth, and processing time would misattribute lagged trades across window boundaries.

The fourth follow-up asks how the design behaves across many instances. The expected answer is that the per-user state must be partitionable by user id, co-partitioned with the input, so that all events for a user land on one instance, and the framework handles failover by restoring state from a changelog.

The final probe asks the candidate to map the design onto a real system. The expected answer is Kafka Streams: a partitioned input topic, a groupByKey, a windowedBy with an inactivity gap, an aggregate backed by a partitioned state store, and exactly-once delivery that subsumes the idempotency layer.

Mastery Questions

Question

Why does the net-portfolio prompt resist a one-shot query and demand a streaming design?

Question

Derive the per-key running-sum design and its amortized cost.

Question

Why must the net-portfolio window be event time, and what does that commit the design to?

Question

What is a watermark, and how does it bound out-of-order events?

Question

How does idempotent aggregation defeat duplicate events, and where does the dedup state live?

Question

Map the hand-derived design onto a Kafka Streams windowed aggregate.

Question

What is the single most common correctness bug in a hand-rolled windowed aggregate, and how is it prevented?

Answer

The thirty-day window slides continuously with wall-clock time, so the live set per user changes every second, and the answer must be current without an explicit query. A recomputation on demand walks the user's transactions every time, $O(\text{txns}(u))$ per query, and stores all history. The streaming design keeps a per-user running sum, adjusts it by what enters and leaves the window, and answers in $O(1)$, with memory bounded by the live window rather than all history.

Answer

Hold one running sum per user and one arrival-ordered queue per user. On an event, add the signed amount (positive for buy, negative for sell) to the user's sum, append the event to its queue, then evict from the head every event older than the cutoff, subtracting each. The net for a user is its running sum, read in $O(1)$. Each event is inserted once and evicted at most once, so across $N$ events the total eviction work is $O(N)$, and per-event work is amortized constant per user.

Answer

Event time uses the timestamp on the trade, which is when the trade actually happened and is the truth for a money-facing number. Processing time uses when the processor saw the event, which misattributes lagged trades across window boundaries. Committing to event time commits the design to handling out-of-order arrival, because events from multiple venues or retries do not arrive in timestamp order, which requires a watermark and a late-event policy.

Answer

A watermark is the processor's assertion that it has probably seen every event older than some bound, so windows older than the watermark are closed and can emit. A bounded-out-of-orderness policy sets the watermark to the largest seen timestamp minus a slack (say, five minutes), assuming events arrive at most that far out of order. Events older than the watermark are late and are dropped, routed to a side output, or used to emit a correction. The slack is a latency-versus-completeness trade: larger waits longer and captures more late events, smaller emits faster but drops more.

Answer

Each event carries a unique transaction id. Before adding an event's amount to the sum, the processor checks a seen set of ids; an id already present means a retry and the event is skipped, an absent id means a new event and its amount is applied with the id recorded. The dedup state must be partitioned by the same key as the aggregation (the user id) so the check and the update live on the same instance and never miss, and over a long run it must be time-bounded or approximated to bound its growth.

Answer

The per-user state is a partitioned state store co-partitioned with the input topic; the grouping is a groupByKey on user id; the window is a windowedBy specification with an inactivity gap that plays the watermark; the running sum is an aggregate function the framework calls per event; and idempotency is the framework's exactly-once processing, which uses transactional offsets and state-store updates so a retried event re-applies only if its prior application did not commit. The application owns the aggregator, the window definition, and the keying; the framework owns partitioning, watermarking, exactly-once, and failover restore from the changelog.

Answer

Double-counting a retried event, because delivery is at-least-once and a retry resends the same transaction. The net drifts by exactly the duplicated amounts, which for a money-facing number is unacceptable. Prevent it with idempotent aggregation keyed by transaction id: record every applied id in a partitioned dedup store, and skip any event whose id is already present before its amount reaches the sum. Exactly-once stream processing subsumes this by making the aggregate update and the offset commit atomic.

Question

Why does the net-portfolio prompt resist a one-shot query and demand a streaming design?

Answer

The thirty-day window slides continuously with wall-clock time, so the live set per user changes every second, and the answer must be current without an explicit query. A recomputation on demand walks the user's transactions every time, $O(\text{txns}(u))$ per query, and stores all history. The streaming design keeps a per-user running sum, adjusts it by what enters and leaves the window, and answers in $O(1)$, with memory bounded by the live window rather than all history.

Prev1 / 7Next