Design AWS Step Functions

A managed workflow engine that runs 200 M state-machine executions a day, some lasting a year, applying every transition exactly once.

Last updated 2026-10-12. Difficulty: hard. Patterns: workflow-orchestration, event-sourcing, durable-timers, sharding, leases. Reported at Amazon, Uber, Netflix, Stripe, Datadog.

Functional requirements

• Define a state machine. A JSON definition of states (Task, Choice, Wait, Parallel, Map, Pass, Succeed, Fail) and their transitions. Publishing creates an immutable version; an alias can split new starts between two versions, and a running execution keeps the version it started on.
• Start an execution, idempotently. StartExecution with a caller-chosen name, unique per state machine. The same name and input while that execution is running returns it; after it closes, or with different input, the call fails with ExecutionAlreadyExists. A name is reusable 90 days after close.
• Run task states. Call a function, any cloud API or an HTTPS endpoint directly; start a job and wait for it to finish; or offer work to the customer’s own activity workers, which long-poll for it.
• Retry, catch and time out. Declarative per-state retry rules (errors matched, interval, backoff rate, max attempts, jitter) and catch clauses, plus a timeout and an optional heartbeat on every task. Failure handling is configuration, not customer code.
• Wait: for a time, or for a callback. A Wait state that sleeps for seconds or months, and a task that pauses until someone calls back with its token: a human approval, a payment webhook, a job on another platform.
• Fan out. Parallel branches that join, and a Map over a list or over a million objects in a bucket, with a concurrency limit and a tolerated failure rate.
• Stop, inspect and redrive. Stop any execution. Read its full event history (every state, input, output, error and duration) for 90 days after it closes. Redrive a failed execution from the state that failed, within 14 days, without rerunning the steps that succeeded.
• Out of scope. The visual designer, IAM policy evaluation, billing, the JSONPath / JSONata data-transformation language, and the customers’ own function runtimes: we call them, we do not run them.

Non-functional requirements

• Exactly-once state transitions (never forked, skipped or applied twice). The engine’s whole promise, and the requirement that drives the hardest trade-off: every transition must be durable before anything acts on it, which puts a replicated commit on every step and makes the steps of one execution strictly serial. Side effects inside customer code get a separate, weaker guarantee, and the design must say precisely which.
• Scale (2 B transitions/day · ~100 k/s peak). Across all customers in a region, about 200 M executions a day. Throughput must grow by adding hosts and partitions, never by making one execution or one partition faster.
• Long-lived executions (up to 1 year · ~50 M open). Most executions are asleep at any instant: waiting on a timer, an approval or a worker. They must live in storage and wake on an event; holding them in memory is not an option.
• Transition overhead (p99 < 100 ms per state). For short workflows the engine’s overhead per step is the customer’s latency. A ten-state checkout flow at 500 ms per transition would be unusable on a request path.
• Timer accuracy (fire within 1 s at p99). Waits, timeouts, retry backoffs and heartbeat deadlines must fire on time even when a million are due in the same second, and must never be lost: a lost timeout leaves an execution asleep forever.
• Availability and durability (99.99 % · nothing lost after a 200). Once StartExecution or SendTaskSuccess returns, the event is replicated across availability zones. Losing a host, or a whole zone, delays executions by seconds and loses nothing. Other services build on this one, so it must be more available than they are.
• Tenant isolation (per-account token buckets · 1 M open cap). Default quotas such as 300 starts/s (burst 1 300) and 5 000 transitions/s per account, enforced at the front door before work enters a shard, so one account’s runaway loop is throttled instead of slowing its neighbours.

Back-of-envelope estimates

• State transitions per second: ~23 k avg · ~100 k peak. 2 B transitions a day ÷ 86 400 s ≈ 23 k/s on average. Business hours, month-end batches and retry storms push peaks to about 4× ≈ 100 k/s. Design for the peak.
• Execution starts per second: ~2.3 k/s. An average execution makes ~10 transitions, so 2 B ÷ 10 = 200 M starts a day ≈ 2.3 k/s, around 10 k/s at peak.
• Executions open at once: ~50 M. Little’s law: 2.3 k starts/s × an average lifetime of ~6 hours (21 600 s) ≈ 50 M open. Most executions finish in seconds; a tail waiting days for approvals or timers dominates the average. Nearly all are idle at any instant, so this is a storage problem, not a compute problem.
• History written per day: ~2 TB · ~180 TB retained. A transition appends ~3 events (state entered, task scheduled, task succeeded, …) of ~300 B: about 1 KB. 2 B × 1 KB = 2 TB/day. At 90 days’ retention after close that is ~180 TB, ~540 TB with three replicas, which is why closed histories leave the hot store within days.
• Database row writes at peak: ~500 k rows/s. Each transition writes ~3 history events, the mutable-state row and ~1 task or timer row: about 5 rows, ~1.5 KB. 100 k transitions/s × 5 = 500 k row writes/s, ~150 MB/s before replication. Spread over thousands of partitions that is ordinary; what limits one execution is commit latency (~5 ms), not bandwidth.
• Shards needed at peak: ~2 000 busy, 16 k fixed. Commits within one shard partition are serialised; at ~5 ms each a shard tops out near 200 transitions/s, and we run it at a quarter of that: 100 k/s ÷ 50/s = 2 000 busy shards. A fixed 16 384 gives 8× headroom and small units to move between hosts.
• Timers: ~12 k created/s · ~50 M pending. Every task gets a timeout timer, nearly always cancelled within seconds when the task finishes: ~1 B task states a day ≈ 12 k timer creations/s, plus Wait states and retry backoffs. Pending timers track open executions, since nearly every sleeping execution is waiting on a deadline: ~50 M, about 3 000 per shard, of which only the next few minutes’ worth is in memory.
• Hosts to own the shards: ~160. 16 384 shards ÷ ~100 per host = ~164 engine hosts, each committing ~600 transitions/s at peak. Shards are the unit of failover: a dead host’s 100 small shards move to many different hosts and each recovers in seconds, rather than one giant partition failing over.

Components

• Customer app: Starts and stops executions, sends task callbacks and reads history through the signed public API. It chooses the execution name, which makes starting idempotent, and it holds the task tokens it is handed until the person or system it waits on replies.
• Activity workers: The customer’s own processes for work the engine cannot call: on-premises jobs, GPU boxes, legacy systems. They long-poll for tasks by activity name, heartbeat while they work and report with the task token. They never know or care which shard a task came from.
• Frontend API (stateless · per-account quotas): Authenticates, enforces per-account token buckets and payload limits, then routes: execution calls to the shard owner (by hashing the execution, or by the shard inside a task token), activity polls to task matching. It holds no execution state, so any instance serves any call and the fleet scales by adding boxes.
• Definitions (versioned · immutable): State machine definitions with their published versions and aliases. A version is immutable and an execution records the version it started on, so editing a definition never changes the path of a running execution. Read on every transition and written rarely, so every engine host caches it.
• Shard membership (leases + range ids): Maps each of 16 384 shards to the engine host that owns it, through leases of about 10 s held in a small consensus-backed store. Taking a shard bumps its range id, which the history store checks on every write, so a former owner that missed its lease expiry is fenced out.
• Execution engine (owns shards): The heart of the system. For every shard it owns, it applies events to executions one at a time, evaluates the state machine and commits the result: new history events, the updated mutable state and any task and timer rows, made visible by one conditional write. Hot executions stay cached so a short workflow never rereads its state, and nothing acts on a transition until the write lands.
• History store (partitioned · conditional writes): Per execution, an append-only event history and a small mutable-state row: current state, definition version, pending tasks with their attempts, timers, next event id. Mutable state, outbox and timer rows share the shard’s partition, so the commit is one single-partition write conditional on the range id. History events are far too big for that partition, so they go to their own table just before the commit and only count once it lands.
• Task outbox (per shard · same commit): Work the engine has committed to: call this function, offer this activity, start this map run, publish this status event. Written in the same commit as the transition (a transactional outbox) and dispatched from memory straight after it; the rows exist so a new owner can replay them after a crash. Acknowledged in bulk by advancing an ack level rather than deleting row by row.
• Task matching (partitioned by activity): Activity task queues, partitioned by activity name, because a worker asks for “resize-image” work, not for a shard. A task that arrives while a worker is polling is handed straight to it without being stored (sync match); otherwise it waits in a durable backlog. Before handing a task out, matching asks the owning shard to record the attempt as started, which drops duplicates and tasks the execution no longer wants.
• Timer queue (per shard · by fire time): Durable timers (Wait states, task timeouts, retry backoffs, heartbeat deadlines) stored per shard, ordered by fire time and written in the transition’s commit. The owner keeps the next few minutes in an in-memory timing wheel and loads more as time advances, so fifty million sleeping executions cost disk, not memory. A fired timer is just another event, applied only if the execution still expects it.
• Service integrations: Makes the call for each started attempt: a function, any cloud API, an HTTPS endpoint, or a job it then watches to completion. Calls run with the execution’s role, never the engine’s, and carry the execution and state names that customers use as an idempotency key. Results, and errors classified as retryable or not, go back to the owner as events.
• Functions & services: What a workflow actually does: functions, queues, databases, containers, third-party APIs. A response can be lost after the work happened, so a retried attempt can repeat a side effect; customers make side effects idempotent with a key that does not change across retries.
• Map run coordinator: Runs a distributed Map: reads the item source in pages, batches items and starts child executions with deterministic names, at most MaxConcurrency (up to 10 000) at a time. It counts outcomes against the tolerated failure rate, checkpoints its progress and writes results to object storage, so the parent’s history records one map run, never a million iterations.
• Payload store (object storage): Item lists and results for distributed maps, payloads too large for the 256 KB limit, and the compacted histories of closed executions. Keeps the history store small and hot: it holds open executions and the last few days of closed ones, not 180 TB.
• Status events: Execution started, succeeded, failed, timed out or aborted, published for customers’ alarms, other workflows and the map run coordinator. Emitted from committed transitions through the outbox, so an event is never sent for a transition that did not happen and never missed for one that did.

User flows

1. Start an execution and run a task. The core path: a start that is idempotent, a transition that is durable before anything acts on it, an attempt handed out exactly once, and a result that advances the machine exactly once.
   1. The customer starts an execution with a name and an input. The frontend authenticates, checks the account’s start bucket (300/s, burst 1 300 by default) and its 1 M open-execution cap, and checks the input is under 256 KB, all before anything is written. The name is the idempotency key, so a client that times out can simply retry.
   2. The frontend hashes the execution to a shard and finds the host that owns it. shard = hash(account, state machine, name) mod 16 384, so a retry with the same name always reaches the same shard, where the uniqueness check is a local read. Every frontend caches the shard map and refreshes it when an owner answers “not my shard”, so the lookup is almost never on the request path.
   3. The owner resolves the definition version and commits the start. If an execution with this id exists, the owner compares inputs and returns it or rejects the call. Otherwise it appends ExecutionStarted, TaskStateEntered and TaskScheduled, then makes them count with one write in the shard partition: the mutable state (definition version 12, task pending at attempt 1) plus an outbox row, conditional on the range id. Only then does the frontend return 200.
   4. The owner records the attempt as started and hands it to the integration that calls the customer’s function. The dispatcher is notified in memory the moment the commit lands, so there is no polling delay. Recording TaskStarted before the call leaves means a replayed outbox row or a duplicate dispatch can never hand the same attempt out twice. The function receives the execution id and state name, which stay the same if a Retry rule runs it again: that pair is the idempotency key for its side effects.
   5. The result comes back as an event; the owner records it and decides the next state. TaskSucceeded is applied only if the mutable state still shows that task pending at that attempt; a duplicate or late result is a no-op. The engine evaluates the next state against the pinned definition version (here a Choice on charged) and schedules it in the same commit. Pass and Choice states are pure computation, so a run of them can be evaluated and committed together.
   6. At a terminal state the execution closes and a status event is published. ExecutionSucceeded is the last history event, and the same commit writes the status event to the outbox, so alarms and downstream workflows hear about every closed execution exactly as the history records it. The 90-day retention clock starts now.
2. Pause for an approval, then a worker. A task that waits days for a callback: the execution sleeps in storage, wakes on a token or a deadline, rejects stale replies, then hands the next step to a polling worker without the worker knowing about shards.
   1. The workflow reaches an approval task, and the integration sends a message carrying a task token. The token encodes the shard, execution, scheduled event id and attempt, with a key id, signed by the service. Nothing else needs to remember it: the token is its own routing address and its own proof of validity.
   2. The engine writes a timeout timer, and the execution leaves memory. The waiting execution is now a mutable-state row and a timer row, a few hundred bytes. Fifty million open executions cost storage, not hosts; memory caches only recently active ones.
   3. Two days later the approver clicks, and the customer’s app sends the token back. The frontend checks the token’s signature and the caller’s credentials for the account, then reads the shard straight out of the token. No index from token to execution exists or is needed.
   4. The owner checks the token still matches the pending task and records the result. If the task already timed out, or this is the second click, the event id or attempt no longer matches and the caller gets TaskTimedOut or an invalid-token error. The approval cannot advance the machine twice.
   5. The timeout is cancelled, and the next state, an activity, is offered to workers. Cancelling is a delete in the same commit; if the timer was already loaded into memory it fires anyway, finds nothing pending and does nothing. The activity task goes to the matching partition for its activity name, because the workers that run it poll by name, not by shard.
   6. A worker’s long poll picks the task up, and the owner records the attempt as started. If a worker is already waiting, the task is handed over in memory (sync match) and never touches the backlog. Before returning it, matching asks the owner to record the start; a duplicate copy, or a task whose execution was stopped meanwhile, is refused there, so one attempt reaches one worker.
   7. The worker heartbeats while it works, then reports success with the token. A heartbeat updates the last-heartbeat time in the mutable state; the single heartbeat timer, when it fires, re-arms itself if a heartbeat arrived since, so heartbeats never rewrite timer rows. A worker that dies is noticed after one heartbeat interval of silence, not at the task’s full timeout. Success cancels both timers and moves the execution on.
3. A Map over a million objects. The scale case: one execution fans out to thousands of child executions without exploding its own history, flattening a downstream database or starving other customers.
   1. The workflow reaches a distributed Map state pointing at a bucket prefix. The parent records one MapRunStarted event and waits as if on a callback. A million iteration events in one history would blow past the 25 000-event limit many times over and make that one shard the hottest in the fleet. The map run is created from an outbox row, so a crash can neither lose it nor create it twice.
   2. The coordinator reads the object list in pages and batches items. Items are grouped, for example 100 objects per child, so a million objects is 10 000 children rather than a million. Batching cuts per-execution overhead by two orders of magnitude for small items.
   3. It starts child executions through the normal start path, up to the concurrency limit. Each child is an ordinary execution hashed to its own shard, so the work spreads across the fleet and passes the same per-account quotas as any start. Names derived from the map run and batch index make starts idempotent across coordinator restarts. Children start at a bounded rate (AWS documents about 100/s for Standard children and 1 000/s for Express), so ramping up is gradual, not a thundering herd.
   4. Children run on their own shards, and their status events drive the coordinator’s counters. The coordinator counts succeeded and failed items and starts a new child as each one finishes. If failures pass the tolerated rate (5 % here), it stops starting children and fails the map run rather than burning through a million broken items.
   5. Results go to the payload store, and the coordinator completes the parent’s Map state like a callback. The parent’s Map state was a callback task all along: the coordinator holds its token and completes it as any external system would, so no new completion path is needed. The next state receives a manifest location, not a million results inlined into a payload capped at 256 KB.
4. An engine host dies mid-transition. The failure case: shards move in seconds, a paused owner is fenced, no transition is lost or applied twice, and a call whose outcome is unknown becomes an explicit, retryable error instead of a silent duplicate.
   1. An engine host stops renewing its shard leases. Leases last about 10 s and are renewed every few seconds. The host may be dead, or just frozen in a long garbage-collection pause and about to wake believing it still owns its shards: the design must be correct in both cases.
   2. Other hosts acquire its 100 shards, each bumping the shard’s range id. Acquiring a shard is a conditional write that increments its range id in the history store. From that moment every write from the old owner, conditional on the old range id, fails. The 100 shards land on many different hosts, so no single host absorbs the load.
   3. The old host wakes up and tries to commit; the store rejects it. This is fencing. The lease alone cannot stop a paused host from writing; the range-id condition on every write can. The old host drops its cached executions and timers for the shard.
   4. The new owner reloads outbox rows and due timers and dispatches what was never started. Everything committed is in the store, so no transition is lost. Executions load lazily on their next event, so taking a shard costs reading two small queues, not fifty thousand executions. Replayed tasks that the mutable state shows as already started are skipped; overdue timers fire at once.
   5. A result for a call the old host dispatched is delivered to the new owner. The integration routes results by shard. It gets a timeout or “not my shard” from the dead host, refreshes the shard map and retries. The function ran once and its result is applied once: an engine crash alone never causes a repeat.
   6. If the integration host itself died mid-call, the attempt’s deadline settles it. Now nobody knows whether the function ran. The deadline fires and records States.Timeout. If the state retries on it, attempt 2 runs with the same execution id and state name, so a function that uses them as its idempotency key does not charge twice. With no Retry rule the error goes to Catch: a non-idempotent call is never repeated behind the customer’s back.
5. A task fails, retries, is caught, is redriven. Retries are timers, not sleeping threads; the catch path is just another transition; and because the history keeps every result, a failed execution can resume from the failed step.
   1. The function returns a throttling error. The integration classifies the error: Lambda.TooManyRequestsException is the service’s own retryable error, while an error the function throws carries whatever name the customer gave it. The engine matches it against the state’s Retry rules in order, here interval 2 s, backoff rate 2, max attempts 5, full jitter.
   2. The engine records the failure and writes a backoff timer instead of retrying at once. The third retry waits up to 2 × 2² = 8 s, with jitter, so ten thousand executions throttled by the same function do not all retry in the same second and throttle it again. Nothing occupies a thread while it waits: the execution is a row and a timer.
   3. The timer fires and the task is dispatched again as the next attempt. The attempt number is part of the task’s identity, so a late result from attempt 1 cannot complete attempt 2. What the function sees as its idempotency key (execution and state) does not change: a retry is the same logical call.
   4. Attempts run out, and the Catch clause routes the execution to a fallback state. The error and its cause are written into the state’s output at the Catch’s result path, so the fallback (refund, notify, park for manual review) knows what failed. It is scheduled in the same commit as the failure.
   5. If nothing catches the error, the execution fails and alarms fire. ExecutionFailed closes the execution and publishes a status event that alarms and dashboards subscribe to. The history keeps every completed step’s output, which is exactly what the next step needs.
   6. The customer raises the downstream limit and redrives the execution from the failed state. Redrive reopens the same execution at the state that failed, with fresh attempt counts, and keeps every earlier result, so steps that succeeded are not run again. It is only possible because the history recorded them, and only for 14 days, after which the execution stays closed.
   7. A few days after it finally closes, the history is compacted into the payload store. One compressed object per execution replaces thousands of rows, and reads for the rest of the 90-day retention are served from it. The hot store keeps open executions and recent closes, tens of terabytes instead of 180.

Deep dives

The theory behind it

• Saga pattern: an interactive playground. Book a trip across four services with a saga, then fail a step, crash the orchestrator or break a compensation, and see whether the services end up consistent.
• Serverless cold starts: an interactive playground. Send quiet, steady and spiky traffic to a serverless function on demand, with a keep-warm ping or with provisioned concurrency, and compare cold starts, peak instances and monthly cost.
• Workflow orchestration and durable execution: Running multi-step processes reliably: choreography versus orchestration, durable execution engines like Temporal, state machines, retries and timeouts per step, compensation, long waits and human steps, data pipeline schedulers like Airflow, and versioning running workflows.
• Event sourcing, CQRS and change data capture: Storing events instead of state, separating write and read models (CQRS), keeping read models in sync with change data capture and the transactional outbox, and when these patterns are worth their complexity.
• Distributed locks, leases and fencing tokens: When you need mutual exclusion across machines and how to get it safely: lock services, leases with expiry, why Redis locks can fail, fencing tokens, leader election, optimistic alternatives, and avoiding locks altogether.

Related

• Design a Distributed Job Scheduler
• Design a Stock Exchange
• Design a Real-Time Leaderboard
• Design a Unique ID Generator
• All 83 system design interview questions
• Run this question for a friend: the interviewer kit