Interview conceptSoftware Engineering Fundamentals

Concurrent Backend Systems: Schedulers And Event Streams

Asked of: Software Engineer

Last updated

Editorial architecture diagram showing a delayed-job scheduler with a min-heap and condition variable alongside Kafka partitions, consumer-group ownership, ordering keys, rebalancing, and at-least-once handling.

What's being tested

These problems test concurrency, coordination, and time- or order-sensitive distributed-system design. You must reason about ownership, synchronization, backpressure, failure, shutdown, and observable guarantees—not merely name a data structure or thread primitive. Walmart Labs operates high-throughput services where delayed work, event ordering, and graceful degradation affect inventory, checkout, fulfillment, and customer-facing reliability.

Core knowledge

  • Kafka-style partitioning distributes a topic across independent logs. Within one consumer group, each partition is assigned to at most one consumer, so maximum active consumption parallelism is min(partitions, consumers).

  • Choose partition count from peak throughput and future growth: approximately P≥⌈peak write throughputper-partition throughput⌉P \ge \lceil \frac{\text{peak write throughput}}{\text{per-partition throughput}} \rceil, then validate broker CPU, disk, network, and consumer processing limits.

  • A consumer group provides horizontal scaling and failover. More consumers than partitions leave workers idle; fewer consumers increase per-worker ownership, potentially creating lag and reducing parallelism.

  • Preserve ordering only within a partition. Use a stable partition key such as order_id when all events for an entity must remain ordered; random or round-robin keys improve distribution but sacrifice entity-local ordering.

  • Rebalancing transfers partitions when consumers join, leave, or fail. Prefer cooperative or incremental assignment when available, and make handlers resilient to revoked ownership, duplicate delivery, and paused processing.

  • At-least-once delivery means a crash after processing but before offset commit can replay an event. Use idempotent handlers, deduplication keys, transactional state changes, or an outbox-style boundary where correctness requires it.

  • A delayed-job scheduler should maintain jobs in a min-heap ordered by due time, giving insertion and removal cost O(log⁡n)O(\log n) and earliest-job lookup cost O(1)O(1). A sorted list is simpler but usually makes insertion O(n)O(n).

  • Coordinate scheduler threads with a condition variable, not periodic polling. The worker waits until either a job is due, a newly inserted job becomes earlier, cancellation changes the head, or shutdown is requested.

  • Cancellation needs an explicit state model: PENDING, RUNNING, CANCELLED, and COMPLETED. Lazy deletion avoids expensive heap removal; the worker skips cancelled entries when they reach the top.

  • Separate scheduling from execution using a bounded worker pool. A scheduler thread should enqueue due work quickly; otherwise one long-running job blocks unrelated deadlines and causes unbounded lateness.

  • Backpressure is essential when jobs become due faster than workers can execute them. Bound the ready queue, define rejection or retry behavior, and expose queue depth, execution latency, failures, and dropped-work counters.

  • Shutdown should distinguish graceful and immediate modes. Graceful shutdown stops accepting jobs and drains accepted work; immediate shutdown signals workers, cancels pending jobs where permitted, and documents that already-running code may not stop safely.

  • Time handling should use a monotonic clock for delays because wall-clock adjustments from NTP or daylight-saving changes can move deadlines backward or forward. Persisted schedules may still require wall-clock timestamps plus explicit timezone rules.

  • Kafka throughput is constrained by the slowest stage: producer, broker, network, consumer fetch, or handler. Monitor consumer lag and p99 processing latency; increasing partitions will not fix a slow downstream dependency or serialized handler.

  • A robust design states its guarantees precisely: per-key ordering versus global ordering, at-most-once versus at-least-once execution, cancellation before start versus cancellation during execution, and whether delayed jobs survive process failure.

Worked example: Design and Implement an In-Memory Job Scheduler for Delayed Jobs

A strong candidate first asks whether jobs must survive process failure, whether delays are relative or absolute, what cancellation guarantees mean, and whether submitted jobs may run concurrently. They then declare an in-memory, single-process assumption and organize the answer around a min-heap, condition-variable coordination, worker execution, and lifecycle state transitions. submit(delay, task) creates a unique job record, inserts it under a lock, and signals the scheduler if the new deadline becomes the heap head. The scheduler waits indefinitely when empty, otherwise waits only until the earliest deadline and rechecks state after every wake-up to handle spurious notifications. Due jobs move to a bounded executor queue, while cancellation marks records rather than relying on unsafe arbitrary heap deletion. A key tradeoff is lazy cancellation: it keeps operations simple and efficient, but cancelled records can temporarily consume heap memory and require periodic compaction. The answer should explicitly state that cancellation cannot guarantee stopping a task already running unless the task cooperatively observes a cancellation token. To close, the candidate would add deterministic tests using an injected clock, metrics for scheduling lateness, and fault behavior for rejected or failed tasks.

A second angle

For Allocating Partitions and Consumers for a Kafka-Style Event Topic, the same concurrency reasoning shifts from local thread coordination to distributed ownership. Clarify required ordering, peak throughput, acceptable lag, consumer processing time, and failure-recovery expectations before choosing partition count. Organize the response around partition-key selection, consumer-group assignment, rebalancing, and offset or duplicate semantics. The central tradeoff is that more partitions increase parallelism and future capacity but also add broker metadata, rebalance overhead, and operational cost.

Common pitfalls

Pitfall: Saying “Kafka guarantees ordering” without qualification is analytically wrong; ordering is guaranteed only within a partition, so explain how the key maps related events to the same partition.

A tempting scheduler answer uses sleep(100ms) in a loop to check deadlines. That introduces unnecessary wakeups and scheduling jitter, and it may miss an earlier newly submitted job; a condition variable with timed waits demonstrates correct coordination.

Many candidates describe a heap and worker threads but omit ownership and lifecycle races. Explicitly discuss shutdown while a worker is dequeuing, cancellation concurrent with execution, spurious wakeups, duplicate event delivery, and what happens when the executor queue is full.

Connections

The interviewer may pivot to backpressure, idempotency, leader election, retry policies, or dead-letter queues. They may also ask how to replace the in-memory scheduler with a durable design using Redis, Postgres, or a managed queue while preserving visibility and delivery guarantees.

Further reading

  • Kafka Documentation: Consumer Groups — authoritative explanation of partitions, group membership, and assignment.

  • The Little Book of Semaphores — practical treatment of locks, condition coordination, and concurrency patterns.

  • Designing Data-Intensive Applications by Martin Kleppmann — strong coverage of logs, ordering, delivery semantics, and distributed-system tradeoffs.

Practice questions

Related concepts