Logs & Streaming

Why this module exists

Streaming systems look like "just append and read" until failures happen. Then correctness depends on a few strict invariants:

• commits are contiguous
• assignment is deterministic
• duplicates are filtered
• stale producers are fenced
• watermarks drive late-data and emission behavior
• compaction keeps only latest key state

This module is about implementing those invariants explicitly.

Shared state model

Keep this mental model while solving all 8 problems:

1. Log position state
   • per partition high watermark
   • per consumer committed offset
2. Producer state
   • producer id
   • epoch (fencing generation)
   • per-partition last accepted sequence
3. Group membership state
   • sorted consumers
   • sorted partitions
   • deterministic owner mapping
4. Event-time state
   • max event time seen
   • watermark = maxEventTime - allowedLateness
5. Compaction state
   • last index seen per key

If output is wrong, check which state machine you violated.

Learning goals

By the end, you should be able to:

• compute contiguous commit advancement from unordered acknowledgements
• produce deterministic round-robin assignments and rebalance move sets
• compute lag and global watermark from partition-level stats
• simulate tumbling-window emission with watermark gating
• enforce idempotent producer sequencing
• compact logs while preserving retained-record order
• combine fencing + transactions + idempotence for exactly-once behavior

Invariant 1: commit only contiguous offsets

Why:

• Committing offset 10 implies all offsets <= 10 are durable and processed.
• If offset 9 was not processed, committing 10 creates an unrecoverable gap.

Practical rule:

• from current committed, advance while committed+1 exists in processed set
• stop at first missing offset

Invariant 2: assignment must be deterministic

For consumer groups, deterministic assignment is operationally critical:

• easy diffing
• predictable rebalances
• no accidental thrashing from random order

Round-robin recipe:

• sort consumers
• sort partitions
• partition at index i goes to consumer i % len(consumers)

Rebalance plan is then:

• compare current owner and new owner per partition
• emit moves where owner changed

Invariant 3: watermark semantics are event-time semantics

Definitions:

• maxEventTime: largest event timestamp observed so far
• watermark: maxEventTime - allowedLateness

Use watermark for two decisions:

1. Late-drop policy
   • if eventTime < watermark, drop event
2. Window emission policy
   • emit window when windowEnd <= watermark

This makes behavior deterministic even with out-of-order arrivals.

Invariant 4: idempotence requires per-producer sequence tracking

For each producer (and often producer+partition):

• accept only expected sequence progression
• reject duplicates and gaps

Simple acceptance model in this pack:

• accept when seq == last + 1
• reject when seq <= last (duplicate/retry)
• reject when seq > last + 1 (out of order)

Invariant 5: exactly-once is composition, not one feature

Exactly-once in this module requires all of:

1. Epoch fencing
   • ignore lower-epoch operations
   • reset producer transactional state on higher epoch
2. Transactional buffering
   • begin starts buffer
   • send and offsets mutate buffer only while in transaction
   • commit applies atomically
   • abort drops buffer
3. Idempotent commit apply
   • apply sends only if seq is newer than last committed seq for that producer+partition in current epoch
4. Monotonic offset commits
   • committed offset per partition only moves forward (max(existing, buffered))

If any one of these is wrong, "exactly once" breaks.

Invariant 6: compaction keeps latest-per-key, preserves stream order

Compaction here is logical retention:

• find last index per key
• keep only records at those indices
• output retained records in original order

Important:

• tombstones are regular latest records if they are last for a key

Suggested solving order

Use this progression to reduce context switching:

1. offset-commit (contiguity invariant)
2. consumer-group-assign (deterministic ownership)
3. consumer-rebalance-plan (ownership delta)
4. streaming-metrics (lag + watermark)
5. windowed-aggregation (watermark-driven stateful emission)
6. idempotent-producer (sequence gating)
7. log-compaction (latest-per-key retention)
8. exactly-once-stream (full composition of prior invariants)

Debugging checklist

Offset/assignment issues:

• Are inputs sorted where required?
• Are empty-consumer and empty-partition cases explicit?
• Are move outputs sorted by partition?

Watermark/window issues:

• Is late check strict (< watermark)?
• Are windows emitted only when end <= watermark?
• Are emitted windows removed from active state?

Idempotence/exactly-once issues:

• Is epoch fence applied before processing operation kind?
• Are stale epochs ignored silently?
• Is transaction state cleared on epoch bump?
• Are duplicates filtered at commit time?
• Are output logs and offsets sorted by partition?

What you will build

• contiguous offset advancement
• round-robin assignment
• rebalance move planning
• lag and watermark metrics
• tumbling window sums with watermark emission
• idempotent producer acceptance
• stable log compaction
• transactional exactly-once simulator

Treat each problem as a constrained state machine, not a one-off algorithm.