Katkat
Back

Implement a fault-tolerant work queue that never loses tasks when workers fail

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement an in-process work queue that never loses a task when the worker holding it crashes, stalls or reports an error. It tests task state tracking, detecting silent workers, rejecting late reports from workers that lost a task, bounded retries for tasks that always fail, thread safety, and deterministic tests built on an injected clock.

Implement a fault-tolerant work queue. Producers submit tasks to the queue, and workers take tasks from it and process them. A worker can crash, hang, or report an error at any point while it holds a task. The queue must guarantee that no task is lost because the worker holding it failed: every submitted task must eventually be completed by some worker, or deliberately set aside as one that cannot be completed.

Propose the queue's interface, implement it as a class with runnable code, and show tests that simulate worker failures.

Constraints and Clarifications

  • In the reported interview this was a two-part coding exercise, checked by running the code against tests. The two parts were not described, so this version states the core task, and likely extensions appear as follow-up questions.
  • Assume the queue is an in-process data structure, and that a worker failure shows up either as an explicit failure report or as silence.

Clarifying Questions

  • How should the queue detect a failed worker: an explicit failure call, a time limit on each task, periodic heartbeats from the worker, or a combination?
  • Is at-least-once processing acceptable, meaning a task may be processed twice if a slow worker is wrongly presumed dead, or must each task's effect happen exactly once?
  • Should a task that keeps failing be retried forever, or given up on after a limit, and where should it go then?
  • Do workers run concurrently on several threads, so that the queue must be thread-safe?
  • Must tasks be handed out in submission order, and where does a retried task go in that order?
  • Does the queue itself need to survive a process restart, or is in-memory state enough?

Hints

Hint 1

Taken is not finished: When a worker takes a task, the task leaves the line of waiting work, but the queue still owes it to someone. Decide what record the queue keeps between "handed out" and "done".

Hint 2

A crashed worker sends nothing: A worker that crashes never reports back, so the queue needs its own rule for deciding that a task has been abandoned. Make time something your tests can control.

Hint 3

The worker that comes back: Consider a worker that was presumed dead but finishes after its task was handed to someone else. Decide how the queue tells its report apart from the current holder's.

Follow-up questions

  • How would you make the queue survive a restart of its own process without losing tasks that were in progress?
  • Processing a task sends an email. How do you keep a redelivered task from sending it twice?
  • How would you support a task that legitimately runs longer than the failure-detection time limit?
  • What changes when workers are separate processes on other machines that talk to the queue over a network?