The Effects Algebra: Five Primitives That Generate All of Concurrent and Distributed Systems #

How five operations on four layers of data, composed by seven rules, unify Herlihy, Kleppmann, Evans, Hellerstein, and Petrov into one framework.

The Five Sacred Primitives #

Every concurrent and distributed system — every database, every message broker, every operating system, every consensus protocol — is built from five state effects:

That’s it. Five operations. Everything else is composition.

A database read is an observe. A blind write is a mutate. A compare-and-swap is a conditional_mutate. Dequeuing a message is a consume. Creating a primary key is a generate.

These aren’t arbitrary categories. They’re ordered by information content — how much coordination they inherently require. This maps directly to Herlihy’s consensus hierarchy: registers (observe + mutate) have consensus number 1. Queues (consume) have consensus number 2. CAS objects (conditional_mutate) have consensus number infinity. The effects algebra formalizes what Herlihy proved: the coordination cost is a property of the operation itself, not of the implementation.

What About Concurrency Control? #

When I first developed this, I thought concurrency control (locks, scheduling, thread coordination) needed its own set of primitives — spawn, suspend, resume. Three “control effects” alongside the five “state effects.”

But that’s wrong. Control effects are derived from state effects applied to scheduling data structures:

acquire(lock) = conditional_mutate(lock.state, FREE → HELD)
                if success → continue (the "resume")
                if failure → save continuation to wait queue (the "suspend")

release(lock) = mutate(lock.state, HELD → FREE)
                + consume(wait_queue, take first waiter)
                + hand waiter its continuation back (the "resume")

Every control mechanism — locks, semaphores, condition variables, schedulers — is implemented by the same five state effects operating on scheduling data structures (queues, counters, flags) instead of application data.

This leads to the deepest insight of the framework.

Four Layers of the Same Five Effects #

The five effects are applied recursively at four layers. The only thing that changes is what data they operate on:

And below all four: Layer 4: Trust — hardware correctness, cryptographic assumptions, failure models. These aren’t effects. They’re axioms. The ground the effects stand on.

The same conditional_mutate appears at every layer:

• Layer 0: conditional_mutate(row, SET balance=100 WHERE version=7) — a database write
• Layer 1: conditional_mutate(lock, SET holder=thread_A WHERE state=FREE) — acquiring a lock
• Layer 2: conditional_mutate(term, SET leader=node_B WHERE term=current) — winning an election

Same operation. Different data. Different textbook. Three “fields” that are actually one field studied at different layers.

Each layer’s data is metadata about the layer below. Layer 0 is your state. Layer 1 is data about who’s currently changing the state. Layer 2 is data about who’s authorized to make Layer 1 decisions. Layer 3 is data about who can change the Layer 2 rules.

The recursion terminates at Layer 4 because trust isn’t data you can conditional_mutate. It’s the assumption that makes conditional_mutate meaningful. If the hardware CAS instruction is buggy, no amount of correct Layer 0–3 reasoning saves you.

Seven Composition Rules #

Effects don’t combine arbitrarily. There are seven rules that constrain legal compositions. Every distributed systems bug I’ve examined traces to a violation of one of these rules.

Rule 1: Fused effects cannot split across boundaries. A consume is really an observe + conditional_mutate fused atomically. Split them and you get TOCTOU bugs: two workers observe the same task, both claim it. This is the atomicity property. Every “exactly-once” guarantee is Rule 1 enforcement.

Rule 2: Generate must be singular per namespace. Two generate sites for the same namespace produce conflicting identities. Multi-master replication violates this — two leaders both generate sequence numbers for the same log. The result is divergence. Consensus protocols exist to enforce Rule 2.

Rule 3: Observations expire. An observe is valid only at the instant it’s made. Acting on stale observations causes cache inconsistency, split-brain, and stale reads. Every TTL, lease, and fencing token is a Rule 3 fix.

Rule 4: Effects escalate along causal chains. If you conditional_mutate at the leader but mutate (blind apply) at followers, the weakest link determines the actual guarantee. MongoDB’s w:1 is this: the leader validates, but async replication can lose the write.

Rule 5: Cross-scope composition requires coordination. Effects within one reactor are cheap (implicit coordination). Effects across reactor boundaries are expensive (explicit coordination proportional to the strongest effect). This is why distributed transactions are hard — they force cross-scope conditional_mutate.

Rule 6: Effect scope must match invariant scope. If your data is naturally per-user, but your generate is global (single sequence for all users), you’ve created an artificial bottleneck. This is why Kafka uses per-partition offsets, not a global offset. Overscoping is the most common performance antipattern.

Rule 7: Recovery needs its own effects. Without checkpoints (generate checkpoint IDs) and change tracking (observe deltas), recovery requires observing the entire state. Kafka’s tiered storage recovery vs. full broker resync is the difference between Rule 7 compliance and Rule 7 violation.

Effect Amplification: The Hidden Cost Model #

One logical effect becomes many physical effects inside the reactor. This amplification is where performance lives and dies.

Generate amplification is the most consequential. Consider a PostgreSQL UPDATE of one column in a row with five indexes:

1. Generate a new tuple version (MVCC copies the entire row)
2. Generate WAL record for the new tuple
3. Generate new index entries in all five indexes (even for unchanged columns)
4. Generate WAL records for each index entry
5. Later: VACUUM must consume the old tuple and old index entries

One logical conditional_mutate → 15+ physical generates. This is why “remove unused indexes” was a key optimization for OpenAI’s PostgreSQL serving 800M users. Each index multiplies the generate amplification on every write.

Consume amplification appears in garbage collection and rebalancing. One Kafka consumer joining a group triggers revocation of all partition assignments across all consumers, offset commits for each, and reassignment. One join → O(consumers × partitions) effects. This is why Kafka evolved from eager to cooperative rebalancing to share groups — each reducing consume amplification scope.

Observe amplification is the N+1 query problem, scatter-gather reads, and LSM merge across levels.

The RUM conjecture (Read, Update, Memory amplification — you can optimize at most two of three) is a statement about effect amplification tradeoffs. B-Trees minimize observe amplification. LSM trees minimize mutate amplification. You cannot minimize both. The algebra is the same. The amplification profile is the design choice.

The Reactor: Effects Meet Interpretation #

A reactor is the runtime that gives effects meaning. It’s an interpreter in the programming language sense — specifically, a handler for algebraic effects (à la Plotkin and Pretnar).

Reactor = (Algebra, Strategy, Scheduling)

Algebra:     which of the five effects are available at this boundary
Strategy:    which composition rules are enforced (ACID, BASE, etc.)
Scheduling:  when effects execute, who goes next (derived from state effects
             on Layer 1 data structures)

PostgreSQL is a reactor that interprets observe as a B-tree traversal with MVCC visibility checks, and conditional_mutate as a row-level lock + write + WAL generate. Redis is a reactor that interprets observe as a hash table lookup and conditional_mutate as WATCH/MULTI/EXEC. Same effects. Different interpreters. Different amplification profiles.

This is the free monad / interpreter pattern:

• The program is a tree of effects (what you want to happen)
• The reactor is the interpreter (how effects become physical operations)
• Nested reactors are monad transformer stacks (each layer interprets one concern)

Application Reactor          → interprets business effects
  └─ Transaction Reactor     → interprets ACID fusion (Rule 1)
       └─ Storage Reactor    → interprets effects as disk I/O
            └─ OS Reactor    → interprets I/O as syscalls

Each layer wraps the one below, adding a new interpretation. The lift operation in monad transformers — “pass this effect down to a lower layer” — is exactly what happens when an effect crosses a reactor boundary.

Data Is Not Effects #

This distinction sounds obvious but is routinely confused in system design:

• Data is what effects operate on. Inert. Can be copied, serialized, stored.
• Effects are what happens to the data at a boundary. Active. Cannot be copied (an effect happens once).

A Kafka message sitting in a partition is data. Reading it is an effect (observe). Appending it is an effect (generate + mutate). The message doesn’t care whether it’s observed. The effect is what creates the relationship between agent and data.

When systems break, the data is usually fine. The effect was wrong: duplicate processing (observe instead of consume), stale read (observe from wrong replica), lost write (mutate instead of conditional_mutate).

A domain event in DDD is a past-tense record of an effect — a serialized effect stored as data. OrderPlaced is data that records the fact that a conditional_mutate(order.status, DRAFT → SUBMITTED) succeeded. Event sourcing is the pattern of generating these serialized effects and deriving state by replaying them. The event store is a WAL. The aggregate is a leader. The read model is a follower. The projection is the replication apply function.

The Continuation: What Happens Next #

A continuation is the rest of the computation after the current step, bundled up as a value that can be stored, passed around, or handed to someone else to execute. It’s simpler and more fundamental than a process or thread.

When an agent invokes an effect at a reactor boundary, the agent’s continuation is suspended — saved somewhere — until the reactor completes the effect and resumes it with the result. suspend = save the continuation and stop running it. resume = give the continuation a value and start running it again.

Every time we say “the producer waits for ack” — that’s a continuation suspended. “The follower catches up and rejoins” — that’s a continuation resumed. “Deadlock” — that’s two continuations each waiting for the other to produce a value, neither able to proceed.

The scheduling question at every boundary is: which of the five state effects did you choose? That choice determines the suspension behavior:

• mutate at a boundary → fire and forget → producer’s continuation never suspends
• conditional_mutate at a boundary → must check precondition → continuation may suspend if precondition fails
• consume at a boundary → exclusive claim → losers’ continuations must suspend or retry

You don’t design the control layer separately. You choose the state effects, and the suspend/resume points fall out.

Mapping the Canon #

The framework maps cleanly onto four major systems textbooks:

DDIA (Kleppmann): Effects at Boundaries #

Each chapter is about effects at progressively wider boundaries:

Control effects are latent in chapters 1–4 (single agent, nothing to schedule) and manifest from chapter 5 onward (multiple agents, multiple reactors). They don’t “appear” — they were always implied by the state effects. They become visible when multiple continuations coexist.

OSTEP (Arpaci-Dusseau): Three Pieces Are Three Perspectives #

OSTEP’s “three easy pieces” are three challenges of running multiple continuations on shared hardware:

• Virtualization: how to share Layer 4 hardware across continuations. CPU virtualization = scheduling continuations on a shared generate site. Memory virtualization = mapping Layer 0 addresses through Layer 1 page tables.
• Concurrency: Layer 1 data structures (locks, condition variables, semaphores) coordinating which continuation accesses Layer 0 data when. Every concurrency primitive is conditional_mutate on Layer 1 data.
• Persistence: Layer 0 effects must survive reactor failure. Journaling is Rule 7 (recovery infrastructure). The WAL commit marker is the same 2PC commit decision. Copy-on-write (ZFS/Btrfs) is the Git model — generate new objects, atomic pointer swing.

Database Internals (Petrov): The Reactor’s Internals #

Where DDIA describes what effects happen at boundaries, Petrov describes how the reactor implements them:

• B-Tree: conditional_mutate via page locks (blocking scheduling), splits are generate chains
• LSM: mutate via append to memtable (never blocks), compaction is deferred consume + generate
• The RUM conjecture: which effect amplification you choose to minimize
• Calvin: solves distributed transactions by making generate(order) singular — once order is decided, execution is deterministic mutate (no conditional_mutate needed)
• Spanner: TrueTime is a Layer 4 upgrade that reduces commit-wait suspend duration
• Percolator: stores Layer 2 coordination data in Layer 0 structures (Bigtable columns) — the cleanest proof that Layer 2 effects are just Layer 0 effects on Layer 2 data

DDD (Evans): Aggregates Are Reactors #

• Aggregate = reactor with singular generate (aggregate root controls all mutations)
• Command = effect invocation
• Domain Event = serialized effect (effect recorded as data)
• Repository = Rule 7 checkpoint mechanism (load/save reactor state)
• Application Service = Layer 1 scheduler (orchestrate effects across reactors)
• Saga = distributed scheduling protocol across reactor boundaries
• Bounded Context = Layer 2 coordination boundary (different algebras meet)
• Anti-Corruption Layer = interpreter that translates between effect algebras
• Ubiquitous Language = Layer 4 trust (shared axioms about domain meaning)

The aggregate boundary IS the thin crossing point. Within the aggregate, effects are local and cheap. Across aggregates, effects require coordination — domain events, sagas, eventual consistency. DDD’s most important structural rule maps directly to Rule 5.

The Design Method #

This isn’t just theory. It’s a design procedure:

1. What data do you have? (domain model)
2. What effects at each boundary? (observe, mutate, conditional_mutate, consume, generate)
3. What data structures implement those effects? (reactor internals)
4. What amplification profile results? (observe/mutate/conditional_mutate/consume/generate amplification)
5. Where do continuations suspend and resume? (falls out from steps 2–4)
6. Check composition rules at every boundary. (Rule 1–7 violation scan)
7. Identify which axis to improve. (strength, generate quality, scope, recovery, completeness, progress, fairness, backpressure)

Steps 1–4 determine step 5. You don’t design the control layer separately. Design the data structures and their effects, and the suspend/resume points emerge from the choices.

Example: Choosing Between Redis and Postgres for a Task Queue #

The canonical question “should I use Redis or Postgres?” is actually three questions:

What effect at the consumer boundary? For exclusive task claiming, you need either consume (atomic dequeue) or conditional_mutate (CAS on status).

Redis BRPOPLPUSH: consume amplification is 2–3 physical effects. Workers suspend cleanly when queue is empty — Redis resumes exactly one worker when an item arrives (no thundering herd). But: weak Rule 7 compliance (in-flight tasks lost on crash) and single-reactor scope ceiling.

Postgres SELECT FOR UPDATE SKIP LOCKED: conditional_mutate amplification is 8–12 physical effects (B-tree traversal + lock + update + WAL + MVCC + index updates). Workers never suspend on contention (SKIP LOCKED converts lock waits into skips). Strong Rule 7 (WAL recovery). But: index contention under high worker counts.

Same logical operation. Different amplification profiles. Different suspend/resume semantics. The choice is derived, not recalled.

Translating Effects to System Design Vocabulary #

The algebra is the reasoning engine. Canonical vocabulary is the communication layer. You need both:

You reason in effects. You speak in canonical terms. The internal monologue and the external communication are different languages for the same structure.

Every named pattern in system design is a specific effect composition: CQRS separates reactors for conditional_mutate (writes) and observe (reads). Event sourcing makes generate(event) the primary effect, with state derived by replay. Circuit breaker is conditional_mutate(call downstream iff circuit CLOSED). Backpressure is downstream suspend propagating upstream.