RFC 002: Execution Leases

Start by reading VISIBILITY_WINDOW and the claim logic in packages/sqlite-runtime/src/sqlite-task-queue.ts, then insertStepResponse in packages/sqlite-runtime/src/dao/step-response-dao.ts and the loop in sqlite-event-loop.ts. This is an open design RFC, not a ready task: the first step is discussing the fencing and lease semantics with the maintainers. Done means an agreed design, not a patch.

Abstract

Nothing prevents two workers from replaying the same execution at once. A delivery that runs longer than the queue's visibility window is handed out a second time, and both replays then race to write the same steps and to acknowledge the same outcome.

We will solve this by giving each delivery a lease with a fencing token that increases on every claim, and by making every write that could conflict check that token atomically. A stale worker will be harmless however long it pauses, so the dispatcher can safely run many executions at once, even across several runtime processes.

https://github.com/user-attachments/assets/7b95c395-56d7-4fa8-8838-136e7477a9a2

Video transcript

Take a shop that uses Yieldstar to charge for orders. When order 42 comes in, Yieldstar starts a workflow run, called order-42. The workflow loads the order, then charges the card. After each step, Yieldstar saves the result. If the run is interrupted and starts again from the top, any step with a saved result is skipped. That is how a restart avoids charging the card twice. Keep this rule in mind, because everything that follows hangs on it: a step with a saved result is skipped, and a step without one runs again.

The shop runs several workers, so it can charge many orders at once. To keep two workers off the same order, the first worker to take order-42 claims it, and the claim hides order-42 from the others. But a worker can crash while it holds a claim, and order-42 would be stuck forever. So the claim runs out after five minutes, and then another worker can take order-42 and finish it. So the claim has two jobs, and they pull against each other. It has to keep other workers out while worker A is working, and let them in if worker A dies.

Problem 1: the customer pays twice. Say the payment provider is having a bad day, and worker A's charge takes six minutes. At minute five, the claim runs out. This is the heart of it: from the outside, a worker that is still busy looks exactly like a worker that has crashed. Neither has finished. So worker B takes order-42 and starts from the top. The load has a saved result, so it is skipped. The charge has no saved result, because worker A is still waiting on it, so, by the rule, it runs again. Worker B charges the card again, and the customer pays twice.

Problem 2: the wrong worker can win. Now both workers try to save a receipt for the charge. The database already refuses a second save for the same step, so you might think that settles it. But the database keeps whichever save arrives first, not the save from the worker that holds the claim. If worker A's receipt lands first, worker B, the worker that now holds order-42, hits a database error and fails. Meanwhile worker A, whose claim ran out, carries on and reports that order-42 is done. Hold on to this, because the fix turns on it: being first is not the same as being current.

Could the claim just last longer? Make it an hour. Now a worker that crashes leaves order-42 stuck for an hour, and the customer waits an hour for their order. And a charge that takes sixty-one minutes still gets charged twice. Remember the claim's two jobs. A short claim does the second job, letting workers in fast after a crash, but fails the first, because it cuts off slow workers. A long claim does the first job and fails the second. No single number does both, because the claim is asking the wrong question. It doesn't need to know how long worker A has had order-42. It needs to know whether worker A is still alive.

RFC 002's fix has two parts. Part 1 decides when another worker may take over. RFC 002 will replace the fixed claim with a lease: a short claim, say thirty seconds, that worker A will renew every ten seconds for as long as it is alive. A slow worker keeps renewing, so it will keep its lease for as long as the charge takes. A crashed worker stops renewing, so within thirty seconds worker B can take over. The claim will do both of its jobs.

But here is the catch, and it is why part 1 is not enough. A renewal only proves that worker A was alive when it renewed. It says nothing about the seconds after. Say worker A has just charged the card when its server freezes for two minutes. Worker A isn't dead, but nothing on that server runs, so nothing renews the lease. The lease runs out, and worker B takes over. The charge has no saved result, so by the rule, worker B charges the card, and saves its receipt. Then worker A's server wakes up. Worker A has no idea that any time has passed, so it carries on, and tries to save its own receipt.

Couldn't worker A check its lease before it saves? It could, but its clock might be wrong. And even with a perfect clock, the lease could run out in the moment between the check and the save. Whatever worker A checks, it checks too early. So the decision cannot belong to the worker. The only place that sees the save at the moment it happens is the database, so the database has to make the call.

Part 2 decides whose saves count. To make that call, the database needs to know which claim is the current one. So every claim of order-42 will get a number, called a fencing token, one higher than the last. Worker A took order-42 with token 2. Worker B takes it with token 3, and the database notes 3 as current. Every save will carry its worker's token, and the database will check the token and make the save in one step, so nothing can slip in between. When worker A wakes up and tries to save with token 2, the database will refuse, and worker A will stop. Remember problem 2, where the first save won, even from a worker whose claim had run out. Now the current claim will win. So the two parts split the work: the lease will decide when worker B may take over, and the token will decide whose saves count.

One limit remains. The token can't undo the first charge. Worker A charged the card before it froze, so the customer still paid twice. But leases make this rare, because it now takes a frozen server, not just a slow one. And when it does happen, Yieldstar's records stay consistent. Stopping the charge itself from repeating is the job of RFC 004.

Before, several workers could share orders safely only as long as no step outlasted the claim. With the lease deciding when, and the token deciding whose, a worker that falls behind can no longer do any harm. A slow worker will keep its lease. A crashed worker will lose it in seconds. And a frozen worker that wakes up late will find its saves refused. So the shop will be able to add workers, even on several servers sharing one database, without them racing each other.

Problem

SqliteTaskQueue hides a claimed task for a fixed five minutes (VISIBILITY_WINDOW = 300000 in sqlite-task-queue.ts). After that, the task is visible again, whether or not its first delivery has finished.

Step records are written with a plain INSERT keyed by (execution_id, step_key, step_attempt) (insertStepResponse in step-response-dao.ts). A second worker that writes the same step fails at the database.

yield* step.run("generate-report", async () => {
  // This step takes longer than the visibility window.
  // A second worker receives the same execution and replays it,
  // so two workers now run this step and both try to record it.
  return await generateReport(reportId)
})

RFC 001 and RFC 003 make this sharper:

• RFC 003 keeps a delivery claimed until the workflow reaches a durable outcome. Any step that outlives RFC 001's redelivery timeout will now produce two live replays and possibly two acknowledgements.
• SqliteEventLoop.loop awaits each delivery before claiming the next. Once a delivery lasts until the workflow's outcome, the runtime runs one execution at a time.

Proposed solution

claimDue will grant a lease on each execution it returns. A lease will carry an expiry time and a fencing token. The token will increase every time the execution is claimed.

The lease holder will renew the lease while it works. If the holder stops renewing, the lease will expire and another dispatcher can claim the execution with a higher token. Every write that could conflict with the current holder's writes will be accepted only with the current token.

yield* step.run("generate-report", async () => {
  // If this worker pauses and its lease is claimed by another worker,
  // its step write carries a stale token and is rejected.
  return await generateReport(reportId)
})

Clocks will decide only when an execution becomes claimable again. Two holders may briefly both believe they hold the lease. Tokens, not clocks, will decide which of their writes are accepted.

Proposed API

This RFC will add the running status that RFC 001 reserved:

type ExecutionStatus =
  | "admitted"
  | "running"
  | "suspended"
  | "completed"
  | "failed"

running will mean that the execution has a live lease. When the lease ends without a terminal acknowledgement, the status will return to suspended if any earlier delivery was acknowledged as suspended, and to admitted otherwise.

The execution record will gain one field:

interface ExecutionRecord {
  // Consecutive deliveries that ended without an acknowledgement.
  unacknowledgedDeliveries: number
}

The dispatcher will accept a concurrency limit:

interface DispatcherOptions {
  // The maximum number of deliveries this dispatcher runs at once.
  concurrency: number
}

Runtime API

ExecutionLease will replace RFC 001's ExecutionDelivery. The fencing token will take over the role of its opaque token: it will identify the wakes that the delivery covers.

type ExecutionLease = {
  executionId: string
  token: number
  expiresAt: number
}

type LeaseLost = { status: "lost" }

interface ExecutionClient {
  claimDue(request: {
    now: number
    limit: number
    duration: number
  }): Promise<ExecutionLease[]>

  renew(request: {
    lease: ExecutionLease
    duration: number
  }): Promise<{ status: "renewed"; lease: ExecutionLease } | LeaseLost>

  release(request: {
    lease: ExecutionLease
  }): Promise<{ status: "released" } | LeaseLost>

  acknowledge(request: {
    lease: ExecutionLease
    outcome: WorkflowRunOutcome
  }): Promise<{ status: "suspended" } | ExecutionOutcome | LeaseLost>
}

abstract class HeapClient {
  abstract writeStep(params: {
    lease: ExecutionLease
    stepKey: string
    stepAttempt: number
    done: boolean
    stepResponseJson: string
  }): Promise<HeapRecord | LeaseLost>
}

admit, get and requestWake will keep their RFC 001 signatures.

Required Semantics

Leases

• claimDue will return at most limit leases. Each will be for a due execution with no live lease.
• An execution will have at most one live lease at any time, across every dispatcher sharing the backend.
• Each claim will give the execution a token greater than every earlier token for that execution.
• renew with the current token will extend expiresAt. renew with a stale token, or after the lease has expired and been claimed again, will return lost.
• A holder whose lease is lost will stop. It will not acknowledge, and it will make no further fenced writes.
• An expired lease will make the execution claimable again, if it is due. This replaces RFC 001's redelivery timeout.
• release with the current token will end the lease without waiting for expiry. It will not acknowledge an outcome.
• acknowledge with the current token will end the lease. After a suspended acknowledgement, the execution's due time will follow RFC 001: the earliest wake requested after the claim, or none.
• A holder will renew its lease while its worker is alive. If the runtime process holding the lease goes away, its worker will stop making fenced writes.
• A worker crash will leave the lease to expire. The execution will then be delivered again.

Redelivery delay

• A delivery that ends by release or lease expiry will be unacknowledged. Each will increase unacknowledgedDeliveries by one.
• Any acknowledgement will reset unacknowledgedDeliveries to zero.
• While unacknowledgedDeliveries is greater than zero, the execution will not be claimable until a non-zero redelivery delay has passed since the delivery ended.
• The delay will never decrease while unacknowledgedDeliveries grows.
• Operators will be able to read unacknowledgedDeliveries to find executions that keep failing.

Fencing

• A fenced write will be accepted only if its token is current. The check and the write will be atomic.
• A rejected fenced write will change nothing and will return lost.
• Safety will not depend on clocks. A holder that pauses past expiry, or whose clock runs slow, will have its fenced writes rejected once another claim has issued a higher token.
• HeapClient.writeStep will be idempotent for the current holder. Rewriting an existing step record will succeed without changing it, and the driver will continue with the recorded value.

Each durable write made during a delivery will be fenced, idempotent by receipt, idempotent by identity, or unfenced:

Write	Protection	Why a stale holder is harmless
Heap step write (writeStep)	Fenced	Rejected once a higher token exists.
acknowledge	Fenced	Rejected once a higher token exists; the status and outcome are unchanged.
renew, release	Fenced	A stale call returns lost and changes nothing.
Store update, updateFrom, deleteFrom, matched take	Idempotent (receipt)	The step receipt, keyed by store, execution and step key, commits atomically with the mutation. Whichever holder commits first applies the step once; the other receives the recorded result.
Store getOrCreate (RFC 005)	Idempotent (identity)	Store identity admits one initial state. A later call finds the store and records the snapshot it observed in a fenced heap step.
WorkflowStartClient.start (RFC 003)	Idempotent (receipt)	The start-request ID returns the first target; a repeat starts nothing.
EffectClient.begin (RFC 004)	Idempotent (receipt)	The effect ID identifies one effect; a repeat returns its current state.
EffectClient.settle	Idempotent (receipt)	The first result is kept. The external system contract makes every holder's result equal; a conflict is reported, not applied.
requestWake, store waiter registration, EffectClient.wait, timed-wait timers (RFC 006)	Unfenced	A stale wake causes at most one extra delivery, and replay absorbs it.

Idempotent writes will not be fenced. A receipt or an identity already makes each one take effect once, whichever holder commits it. The recorded step that returns the receipt's result to workflow code is a fenced heap write.

Fencing will not make step.run exactly-once. A stale holder may still run a function's external side effects before its step write is rejected. RFC 004 covers operations that must not repeat.

Delivery concurrency

• A dispatcher will run up to concurrency deliveries at once.
• A dispatcher will claim new executions without waiting for earlier deliveries to reach an outcome.
• Several runtime processes sharing one backend will follow these semantics, as in the store connector spec's createPeer model (store-connector-spec.md).

Relationship to RFC 001

• The lease expiry replaces RFC 001's redelivery timeout.
• This RFC adds the running status and defines how it returns to admitted or suspended.
• claimDue will return ExecutionLease values. The fencing token will identify the wakes a delivery covers, as RFC 001's opaque token did.
• acknowledge will be fenced, will end the lease, and will return lost for a stale token.
• The record will gain unacknowledgedDeliveries.

Relationship to RFC 003

RFC 003's delivery acknowledgement happens under a lease, and its retry reply releases the lease. WorkflowStartClient.start is idempotent by receipt.

Relationship to RFC 004

RFC 004's client calls follow the fencing table above.

Conformance tests

Runtime-adapter tests will exercise leases:

Case	Observable outcome
Two dispatchers call claimDue concurrently for one due execution	Exactly one receives a lease.
claimDue claims a due execution	The status is running.
A lease expires without renewal	The execution is claimable with a higher token.
A lease expires after an earlier suspended delivery	The status returns to suspended.
A lease expires before any acknowledgement	The status returns to admitted.
Renewal keeps the lease past its original expiry	A delivery longer than one lease period completes with one claim.
Renewal uses a stale token	It returns lost.
A lease is released	The execution is claimable after the redelivery delay, with a higher token.
A delivery acknowledges suspended, with a future wake requested during it	The lease ends; the execution is due at that wake's time.
A delivery acknowledges suspended, with no wake requested during it	The lease ends; the execution is not due.
A worker crashes	The execution is delivered again after the lease expires.
The runtime process holding a lease dies	Its worker makes no further fenced writes.

Fencing tests will interleave a stale holder with the current one:

Case	Observable outcome
A stale holder writes a heap step after a reclaim	The write returns lost; the current holder's records are unchanged.
A stale holder acknowledges after a reclaim	It returns lost; the status and outcome are unchanged.
A holder pauses past expiry, another claims, and the first resumes	Every fenced write from the first returns lost.
The current holder rewrites an existing step record	It succeeds, and the recorded value is unchanged.
A stale holder commits an idempotent store update	The store reflects the step exactly once, and the current holder receives the recorded result.
A stale holder calls WorkflowStartClient.start	The current holder receives the same target; exactly one target exists.
A stale holder requests a wake	At most one extra delivery occurs; the outcome is unchanged.

Dispatcher tests will cover concurrency:

Case	Observable outcome
N executions are due and concurrency is N	All are delivered without waiting for each other.
More executions are due than concurrency	No more than concurrency deliveries run at once.
Several dispatchers share one backend	No execution ever has two live leases.
A delivery replies retry	Its lease is released, and unacknowledgedDeliveries increases by one.
A delivery replies retry several times in a row	Each redelivery waits a non-zero delay, no shorter than the one before.
A lease expires after a retry reply	Both count; unacknowledgedDeliveries is two.
A delivery is acknowledged after several retry replies	unacknowledgedDeliveries returns to zero, and the next wake is not delayed.

Scope

This RFC will not specify:

• deployment of several runtime processes or a networked connector; or
• fairness, priorities or rate limits between executions.

Not Specified

This RFC will not choose:

• how leases and tokens are stored;
• lease duration or renewal interval;
• how the token reaches the worker that makes fenced writes, or how the worker learns that its runtime process has gone (for example, a heartbeat over IPC or polling from the child);
• the redelivery delay's amounts, growth or cap; or
• how the dispatcher chooses among due executions.