Implement a fault-tolerant work queue that never loses tasks when workers fail
Company: OpenAI
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
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.
```hint 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 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 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.
```
### 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?
### What a Strong Answer Covers
- Explicit task states and the transitions between them, with no path that drops a task
- A failure-detection rule for silent workers, with an injectable clock so tests are deterministic
- Rejection of late or duplicate reports from a worker that no longer owns the task
- A bounded retry policy with a terminal state for tasks that always fail
- Thread safety and the cost of each operation, including how abandoned tasks are found without scanning every task
- Tests that cover a crash, a slow worker, a late report and a task that always fails
### 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?
Overview: 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.
Read the full OpenAI Software Engineer interview experience this question came from
Community answers
Answer by tmmwangioo3
Questions:
Is the queue bounded or can tasks be added without checking for queue capacity?
Do we care about tasks that are partially complete? eg. crashed or hanged
Can we assume a reasonable expiry time?
Does a worker reporting an error mean the task should be retried? Should it go to the front of the queue or the back?
Assume multiple threads?
How will the workers report back? Do they wait on Consume or are they asynchronous? Do we just read the Status from the Task
For bounded queues should the capacity count the sizes of both queues? i.e running + main queues
In golang we have channels that can be used to detect when the task is completed and also put a timer for when a task does not complete in time.
type Status int
var Completed Status = 0
var Error Status = 1
var Running Status = 2
var Expired Status = 3
type Task interface {
Run() Status
GetStatus() Status
GetStartTime() time.Time
GetEndTime() time.Time
}
type Queue interface {
Produce(Task)
Consume(Task) (Status, error)
}
Queue:
Multiple Queues: main, running
Running queue to track tasks that are currently running. Can we use a map? If so we need to be able to have a unique hash for a task. Use uuids to have a task id? Will make it easier to have Consume just take the head of the queue.
Mutex to synchronize workers adding into and reading from the queues.
Produce:
Add to the back of the main queue
If we the queue is bounded, reject the task if we are at capacity.
Consume:
Get the head of queue and pass it onto the wo
Answer by Coco_yao
1、define Queue= LinkedBlockQueue, and set the capacity according to business, assume capability = 100. it will reject the producers request when queue is full. It will assign nothing to consumer when queue is empty.
2、Task status: initial/running/failed/finish
2、producers interface, queue.submitTask(task, expired time, start_time), task status = initial, producers can consider this task failed if it can get task result before expired time.
3、consumers interface, queue.takeTask(), task status = running when the task is assigned to worker. if worker report exception, task status turn out to failed. this task will be assigned to other work. if it go through, task status= finish. if it didn't receivie any response from worker before task expired, task staus = failed.
4、all status data have to be set out of in-process, so other worker process also can get the status data to continue
Answer by ThePassionateEngineer
import java.time.Duration;
import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.function.LongSupplier;
/**
Thread-safe, in-process, at-least-once work queue. Java 17+, no dependencies.
A task remains tracked until COMPLETED or DEAD_LETTER; no user code runs locked.
Queue/JVM failure is outside the contract. Payloads should be immutable.
*/
public final class FaultTolerantWorkQueue {
public enum State { READY, IN_FLIGHT, COMPLETED, DEAD_LETTER }
/ Only taskId and token authorize ack/fail; token changes on every delivery. /
public record Lease(UUID taskId, UUID token, T payload, int attempt) {}
public record DeadLetter(UUID taskId, T payload, int attempts, String reason) {}
public record Counts(int ready, int inFlight, int completed, int deadLetters) {}
private static final class Task {
final UUID id = UUID.randomUUID();
final T payload;
State state = State.READY;
int attempts;
UUID token;
long deadline;
String reason;
Task(T payload) { this.payload = payload; }
}
private final long leaseNanos;
private final int maxAttempts;
private final LongSupplier clock;
private final Map> tasks = new LinkedHashMap<>();
private final Deque> ready = new ArrayDeque<>();
// Deadline keys change only AFTER the task has been removed from this set.
private final NavigableSet> deadlines = new TreeSet<>(
Comparator.>comparingLong(t -> t.deadline).thenComparing(t -> t.id));
public FaultTolerantWorkQueue(Duration leaseDuration, int maxAttempts) {
this(leaseDuration, maxAttempts,
Answer by chethan
The queue must be bounded, whenever the queue is full a message should be sent to the producer to slow down.
As multiple producers and workers can conccurently access the same queue, 2 synchronization primitives (mutex) are required each one at the producer and worker end.
A dedicated thread for queue management and monitoring of all worker threads.
The task goes through 4 different states:
S_QUEUE (fresh, not picked by any of the worker threads)
S_WAIT_FOR_ACK (picked by a worker, waiting for the task to be complete)
S_REMOVE (can succesfully remove the task or destroy the memory)
S_REJECT (the task failed for 'n' times configurable, discard the task)
Answer by kganesk
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.LongSupplier;
public class FaultTolerantWorkQueue {
public record Lease(String taskId, String token, T payload) {}
private static class Task {
final String id = UUID.randomUUID().toString();
final T payload;
int attempts = 0;
Task(T payload) {
this.payload = payload;
}
}
private record DeadlineEntry(String taskId, String token, long deadline) {}
private final long timeoutMillis;
private final int maxAttempts;
private final LongSupplier clock; // Injectable for deterministic testing
private final Queue> ready = new LinkedList<>();
private final Map> inFlight = new HashMap<>();
private final PriorityQueue deadlines =
new PriorityQueue<>(Comparator.comparingLong(e -> e.deadline));
private final List> deadLetters = new ArrayList<>();
private final ReentrantLock lock = new ReentrantLock();
public FaultTolerantWorkQueue(long timeoutMillis, int maxAttempts, LongSupplier clock) {
this.timeoutMillis = timeoutMillis;
this.maxAttempts = maxAttempts;
this.clock = clock;
}
public String submit(T payload) {
lock.lock();
try {
Task task = new Task<>(payload);
ready.offer(task);
return task.id;
} finally {
lock.unlock();
}
}
public Lease take() {
lock.lock();
try {
reclaimExpiredTasks();
Task task = ready.poll();
if (task == null) {
return null;
}
task.attempts++;
String token = UUID.randomUUID().toString();
long deadline = clock.getAsLong() + timeoutMillis;
inFlight.put(task.id, task);
deadlines.o