skip to content

In a reminder service where several pollers read the same due-time index, how do you claim a due job so two pollers never both take it?

level: middleimportance: must knowfreq 62%

answer

  1. read-then-write gap
  2. expected state in the WHERE
  3. count the affected rows
  4. skip rows already locked
  5. version-based compare-and-set

basics

~20 s

Make the claim one conditional write: move a job from pending to claimed only if it is still pending, and treat zero rows changed as losing. Reading first and updating afterwards lets both pollers see the same pending row.

solid answer

~50 s

The bug is read-then-write: two pollers both read the same pending row, both decide it is theirs, both dispatch it. The fix is to let the state change itself decide — `UPDATE jobs SET status = 'claimed', claimed_by = :me WHERE job_id = :id AND status = 'pending'` — and check the affected-row count; only one writer can get `1`. For batches, databases that support it offer a row-locking read that skips rows another transaction holds (`FOR UPDATE SKIP LOCKED`), so pollers take disjoint batches without queueing. In stores without transactions, use a compare-and-set on a version number. Assigning each poller its own shard reduces contention, but keep the conditional claim for moments when ownership changes. A claim stops two pollers taking a job at the same time; on its own it does not make execution exactly-once.

code

pseudocode · 8 lines
pseudocode
claim(job_id, poller_id):
  rows = execute("UPDATE jobs SET status = 'claimed', claimed_by = ?
                  WHERE job_id = ? AND status = 'pending'",
                 poller_id, job_id)
  if rows == 1:
    dispatch(job_id)
  else:
    skip(job_id)   # another poller won the claim

go deeper

for a junior

Remember the race: two workers can read the same row before either writes. The fix is a write that checks the row is still pending.

for a middle

Explain the conditional update and the affected-row check, the skip-locked batch claim, and compare-and-set for stores without transactions.

for a senior

Show you know where claims still collide — shard ownership moving, slow pollers — and that claims pair with leases and idempotent handlers.

for a principal

Weigh contention against complexity: when sharded ownership is worth it, how batch size affects fairness, and which store features the design needs.

## The race One poller is a single point of failure and a throughput ceiling, so reminder services run several. They all read the same **due-time index** — a structure listing pending jobs ordered by due time. The natural first implementation is **read-then-write**, and it has a race: 1. Poller A reads the due jobs and gets job 42. 2. Poller B, a few milliseconds later, reads the due jobs and also gets job 42, because A has not written anything yet. 3. A updates job 42 to `claimed` and dispatches it. 4. B updates job 42 to `claimed` too — its update did not check the current status — and dispatches it again. The user gets two reminders. The gap between reading and writing is small, but at thousands of jobs per second it is hit constantly. ## Let the write decide The fix is to make the **state transition** the arbiter. A **conditional update** includes the expected current state in its `WHERE` clause: ```sql UPDATE jobs SET status = 'claimed', claimed_by = :poller_id, claimed_at = :now WHERE job_id = :job_id AND status = 'pending'; ``` The database applies the check and the change atomically. If A and B both run it, one sees `status = 'pending'` and changes the row (**affected rows = 1**); the other finds the row already claimed and changes nothing (**affected rows = 0**). The poller that gets zero simply skips the job. No separate lock is needed. ## Claiming batches without blocking Claiming one job per statement is slow. To claim a batch, a poller can lock rows while selecting them. A plain `SELECT ... FOR UPDATE` makes every other poller **wait** on the same locked rows, so pollers queue behind each other and add nothing. Databases that support it offer a variant that **skips rows another transaction has locked**: ```sql UPDATE jobs SET status = 'claimed', claimed_by = :poller_id, claimed_at = :now WHERE job_id IN ( SELECT job_id FROM jobs WHERE status = 'pending' AND due_at <= :now ORDER BY due_at LIMIT 100 FOR UPDATE SKIP LOCKED ); ``` Each poller then walks away with a **disjoint** batch. Syntax and support differ between databases, and some cannot combine these clauses in one statement, so check yours. ## Stores without transactions Key-value and wide-column stores often lack multi-row transactions but offer a **conditional write** or **compare-and-set (CAS)**: 'write this only if the stored version is still 7'. Give each job a `version` field, read the job, and write `status = claimed, version = 8` only if the version is still 7. The loser's write is rejected, which plays the same role as zero affected rows. | Technique | Where it fits | Behaviour under contention | |---|---|---| | Read, then unconditional update | nowhere | double dispatch | | Conditional update on status | any transactional store | loser sees 0 rows | | Locking read that waits | small, low-concurrency setups | pollers queue up | | Locking read that skips locked rows | relational stores that support it | disjoint batches | | Compare-and-set on a version | stores with conditional writes | loser's write rejected | ## Reducing contention - **Shard the work.** Give each poller its own set of partitions so, most of the time, no two pollers look at the same rows. - **Keep the claim anyway.** When ownership of a shard moves — a deploy, a scale-out, a slow poller — two pollers can briefly both believe they own it; the conditional claim makes that harmless. - **Randomise or offset batch starts** so pollers do not all fight over the very oldest rows. - **Keep claim transactions short**: claim, commit, then dispatch outside the transaction. ## What a claim does not solve - **A claimer that dies.** If a poller claims a job and crashes before dispatching it, the job sits in `claimed` forever unless something reclaims it. Time-limited leases and orphan recovery handle that; the `claimed_at` column is what they build on. - **Duplicate execution after a crash.** A job dispatched just before a crash may be re-dispatched after recovery, so the side effect still needs an idempotent handler. - **Order across pollers.** Separate batches finish in any order; the claim guarantees single ownership, not ordering.

  • Why not batch-claim with a plain locking read that waits on locked rows?
    Every poller asks for the oldest due jobs, so they all try to lock the same rows. With a waiting lock, the second poller blocks until the first commits and then finds those rows already claimed. Pollers end up running one after another, so adding pollers adds no throughput. Skipping locked rows lets each poller take a different batch at the same time.
  • If each poller owns a disjoint shard, is the conditional claim still needed?
    Yes. Shard ownership changes during deploys, scale-outs and failures, and for a short window two pollers can both believe they own the same shard. The conditional claim costs almost nothing and turns that window from double dispatch into a harmless lost race.
  • What should happen to a job whose claimer crashes before dispatching it?
    It must not stay claimed forever. Recording who claimed it and when makes it possible to detect stale claims and return the job to pending. That is the job of time-limited worker leases and orphan reclaim. Because the job may then run twice, its handler should be idempotent.

saying these in an interview costs you the question

  • Read the due jobs, then update them; the gap is too small to matter.
  • A global lock around the whole poll loop is the only safe design.
  • Sharding pollers by partition removes the need for an atomic claim.
  • A successful claim guarantees the job's side effect happens exactly once.
  • A locking read that waits on locked rows lets batch claims scale with pollers.