Distributed Job Scheduling And Exactly-Once Workflows

What's being tested

This topic tests whether you can design a distributed scheduler that remains correct when workers crash, messages duplicate, machines partition, and requests are retried. The interviewer is probing your understanding of durable state, leases, idempotency, retry semantics, and the limits of “exactly once” execution. Stripe cares because payment and financial workflows must avoid both duplicate side effects and silently lost work while operating at high availability and scale.

Core knowledge

Exactly-once processing is not generally achievable across independent systems without coordination: a worker can commit an external charge and crash before recording completion. Prefer effectively-once side effects through durable idempotency keys and downstream deduplication.
Separate job state from execution attempts: PENDING, CLAIMED, RUNNING, SUCCEEDED, RETRYABLE_FAILURE, and DEAD_LETTER. Store attempt number, lease expiry, next-run time, error details, and a stable workflow or task identifier.
Use leases rather than permanent ownership. A worker atomically claims eligible work with a compare-and-swap or transaction, renews periodically, and loses ownership when lease_until < now; stale workers must be rejected by a fencing token.
A fencing token is a monotonically increasing claim version attached to every write. Downstream storage accepts updates only from the newest token, preventing a paused worker from committing after another worker has taken over.
Use a durable database such as `Postgres` for authoritative state, with an index like (status, next_run_at) and SELECT ... FOR UPDATE SKIP LOCKED for moderate-scale polling. At very high throughput, partition queues by shard, tenant, or time bucket.
Treat queue delivery as at-least-once: acknowledgments can be lost, consumers can crash after processing, and brokers can redeliver. A queue such as `Kafka` or `SQS` improves dispatch, but it does not itself provide exactly-once business effects.
Make every handler idempotent using a deterministic key such as (workflow_id, step_id, attempt-independent operation). Record the key and result atomically in an inbox or side-effect table; repeated requests return the original result rather than repeating the operation.
Implement retries with exponential backoff and jitter, for example $d_n=\min(d_{\max},d_0 2^n)+U(0,j)$ . Classify errors as transient, permanent, or unknown; cap attempts, use a dead-letter path, and avoid retry storms during dependencies’ outages.
Workflow progression needs a durable state machine. A step completion should transactionally record its output and make dependent steps runnable; use an outbox pattern when publishing a dispatch event must be atomic with the database transition.
Scheduling requires explicit time semantics: define UTC or a canonical clock, handle daylight-saving changes, and decide whether cron means wall-clock time or fixed intervals. Avoid relying on local machine time for correctness; monitor clock skew and use server-side timestamps.
Design for backpressure and fairness. Bound per-tenant concurrency, reserve capacity for high-priority work, enforce workflow timeouts, and use weighted fair queuing so one customer or runaway workflow cannot exhaust all workers.
Failure recovery must be observable and repairable: expose queue depth, oldest runnable age, claim latency, execution latency, retry counts, lease expirations, stuck workflows, and dead-letter volume. Preserve correlation IDs and provide safe replay or operator cancellation.

Worked example — Design a distributed job scheduler with exactly-once workflow execution

A strong candidate first clarifies whether “exactly once” means one worker attempt or one externally visible business effect, what latency and throughput are required, and whether downstream APIs support idempotency keys. They would state an assumption such as: the scheduler may deliver a task multiple times, but each payment-related side effect must be effectively once. The answer can be organized around four pillars: durable workflow state, lease-based claiming with fencing, idempotent handlers, and recovery/observability. They might store workflow and task rows in `Postgres`, atomically claim runnable tasks, publish work through an outbox, and let workers renew short leases while executing. The central tradeoff is between synchronous transactional coordination, which improves correctness but increases coupling and latency, and asynchronous at-least-once delivery, which scales better but requires idempotent consumers. They should explicitly explain the crash window after an external API call and before local acknowledgment, then show how a stable idempotency key makes the retry safe. They close by noting that, with more time, they would quantify shard capacity, model multi-region failover, and design replay and reconciliation tooling.

A second angle — Recovering a workflow after worker and region failure

The same principles apply to a workflow engine that executes several dependent steps, but the emphasis shifts from dispatch throughput to recovery and consistency. The candidate should explain how a coordinator reconstructs runnable work from durable task state rather than trusting in-memory queues. They should address split-brain coordinators with leader epochs or fencing tokens, and define whether failover can duplicate attempts. A strong design includes reconciliation that scans for expired leases, verifies downstream idempotency records, and advances or retries tasks safely. The key framing difference is recovery correctness: availability matters, but a failover must not cause a financial step to execute twice.

Common pitfalls

Pitfall: Claiming that a transactional queue or `Kafka` “guarantees exactly once” end to end. Broker-level exactly-once semantics do not cover an external payment API, email provider, or database unless the side effect participates in the same coordination protocol.

Pitfall: Saying “the worker marks the job complete after processing” without defining the crash window, ownership rule, or duplicate behavior. Explain the atomic state transition, lease expiry, fencing, and idempotency key explicitly.

Pitfall: Focusing only on the happy path and naming technologies without failure reasoning. Walk through worker crash before acknowledgment, worker pause past lease expiry, duplicate delivery, database outage, poison messages, and downstream timeout; these cases reveal whether the design is actually robust.

Connections

An interviewer may pivot to leader election, transactional outbox/inbox patterns, consistent hashing, backpressure, or multi-region consistency. They may also ask how to test failure windows using fault injection, deterministic clocks, and property-based tests.

Visa Tools

Visa Sponsors

H-1B Odds Calculator

Visa Bulletin