Synchronization Patterns and Concurrent Design

Most concurrency problems have been solved before.

Learning Objectives

Apply the single-writer principle, immutability, thread confinement, message passing and the actor model.

Implement producer-consumer, reader-writer, dining philosophers, barrier synchronization, rendezvous, pipelines, fan-out/fan-in, work stealing, futures dependency graphs, map-reduce and leader-worker designs.

Recognise RCU, double-checked initialization caveats, lazy initialization, concurrent memoization, in-flight request deduplication, rate limiters (token and leaky bucket), circuit breakers, bulkheads, backpressure, batching, coalescing and shutdown coordination.

Select the simplest correct pattern.

Plain-Language Explanation

Most concurrency problems have been solved before. Patterns are those solutions, named: give each piece of data a single writer; never change shared data, replace it; let one thread own a resource and everyone else send it messages; merge duplicate requests; batch small requests into big ones. Knowing the catalogue lets you pick a well-understood design instead of inventing a fragile one.

Precise Technical Explanation

Each piece of mutable data has exactly one writer thread; others only read (with proper publication). Removes write contention and most locking (used in LMAX Disruptor, logging, metrics).

Immutable objects can be shared freely after safe publication. Updates create new versions (persistent data structures, records, frozen dataclasses, ImmutableArray).

Data is accessed only by one thread: UI toolkits (main thread), thread-local buffers, per-connection state in an event loop, actors.

Communicate by sending owned or immutable messages through queues/channels (Module 8).

Actors (Hewitt, 1973) own private state, process one message at a time from a mailbox, and interact only by sending messages; they can create actors and change behavior. Erlang/Elixir processes, Akka, Orleans, Swift actors (implemented below with asyncio).

Bounded queue between producers and consumers (Module 8).

Many readers or one writer — read/write locks, RCU, or copy-on-write snapshots (Module 4).

Five philosophers, five forks, each needing two: the classic illustration of deadlock (all take left fork) and its fixes — resource ordering, a waiter/semaphore, or Chandy-Misra (implemented below with ordering).

All threads finish phase k before any starts phase k+1 (Module 4).

Two parties wait for each other to exchange data — unbuffered channels, Exchanger (Java), SynchronousQueue.

Stages connected by bounded queues (Module 8).

Scatter work to N workers, gather results (Module 8).

Per-worker deques with stealing (Module 15).

Futures and dependency graphs Express tasks as nodes whose inputs are other tasks' futures; a scheduler runs each when its inputs complete (build systems, CompletableFuture graphs, Dask, TBB flow graphs).

Parallel map, then reduce partial results (Module 16).

A leader receives requests and assigns them to workers (or, in leader/followers, one thread at a time waits for events and promotes a follower when it starts processing).

Read-copy-update (RCU) overview Readers access a shared pointer without locks; a writer copies the data, modifies the copy, atomically swaps the pointer, and frees the old version only after all readers that might see it have finished (a grace period). Extremely cheap reads; used in the Linux kernel. A garbage-collected language gets the "free later" part for free (implemented below as a config swap).

Double-checked initialization (language-specific caveats) Correct only with proper atomics/volatile (Module 7); in most languages use the built-in lazy facilities instead.

Create on first use: functools.cache (not exactly-once under concurrency), Lazy<T>, std::call_once, holder idiom, sync.OnceValue.

Memoization with concurrent caches Cache results of a pure function; under concurrency, ensure the expensive computation runs once per key (store futures, not values — next pattern).

Deduplicating in-flight requests "Single-flight": the first caller for a key starts the request and stores its future; concurrent callers await the same future (Go singleflight, demonstrated below). Prevents cache stampedes.

Limit how often an action can occur (per client, per API).

Token bucket and leaky bucket Token bucket: tokens accrue at rate r up to capacity b; each request spends one — allows bursts up to b, average rate r.

Leaky bucket: requests queue and leave at a constant rate r — smooths bursts into a steady stream (implemented below).

Separate pools/semaphores per dependency (Module 14).

Slow producers down when consumers lag (Module 8).

Collect several requests and process them with one operation (one database round-trip, one disk write) — trade latency for throughput.

Merge redundant or overlapping operations into one (many "refresh" signals within 50 ms → one refresh; duplicate keys → one fetch). Implemented below with a time window.

Stop intake → drain or cancel in-flight work → stop workers in dependency order → close resources → exit, all with deadlines (Modules 13–15).

Selecting the simplest correct pattern Prefer, in order: no sharing (confinement, immutability) → message passing → a single coarse lock → finer locking → lock-free algorithms from proven libraries. Complexity must be justified by measurements.

Why It Matters in Real Systems

Production systems are compositions of these patterns: a web service is an event loop (confinement) + bounded pools (bulkheads) + caches with single-flight + rate limiters + circuit breakers + graceful shutdown.

Key Terms

Only one thread writes a given datum Data used by only one thread

Mailbox + private state + one message at a time Lock-free reads, copy-and-swap writes, deferred reclamation

Share one in-flight call among concurrent callers Token / leaky bucket

Burst-allowing / smoothing rate limiters Merging redundant operations

Syntax and API Overview

This is a concurrency concept, not a language construct; patterns are built from the primitives of Modules 4–15.

Complete Code Example

An actor, single-flight deduplication, coalescing/batching, a token bucket and RCU-style config swaps (CPython 3.13.1 asyncio — deterministic):

Dining philosophers with threads — the ordered-forks fix (CPython 3.13.1; the naïve version deadlocks, so only the fixed version is run):

import asyncio


class AccountActor:
    """Private state, a mailbox, one message at a time: no locks needed."""
    def __init__(self, balance):
        self.balance = balance
        self.mailbox = asyncio.Queue()

    async def run(self):
        while True:
            msg, reply = await self.mailbox.get()
            if msg[0] == "withdraw":
                ok = self.balance >= msg[1]
                if ok:
                    await asyncio.sleep(0)               # even with a suspension, the next message waits
                    self.balance -= msg[1]
                reply.set_result(ok)
            elif msg[0] == "stop":
                reply.set_result(self.balance)
                return

    async def ask(self, *msg):
        reply = asyncio.get_running_loop().create_future()
        await self.mailbox.put((msg, reply))
        return await reply


class SingleFlight:
    def __init__(self):
        self.inflight = {}
        self.backend_calls = 0

    async def get(self, key):
        if key in self.inflight:                         # no await between check and insert: atomic on the loop
            return await self.inflight[key]
        fut = asyncio.ensure_future(se
…

actor: approvals [True, False] final balance 20
single-flight: 10 concurrent callers -> 1 backend call, all got 'value-of-user:42'
coalescing: results ['A', 'B', 'A', 'C'] | batches sent: [['a', 'b', 'c']]
token bucket: t=0:ok t=0:ok t=0:ok t=0:deny t=0.25:deny t=0.5:ok t=1.0:ok t=1.0:deny t=1.0:deny
RCU-style swap: readers saw consistent snapshots [(1, 5), (1, 5), (1, 5), (2, 10)]

import threading

N, MEALS = 5, 200
forks = [threading.Lock() for _ in range(N)]
meals = [0] * N

def philosopher(i):
    left, right = i, (i + 1) % N
    first, second = sorted((left, right))         # global order: lower-numbered fork first
    for _ in range(MEALS):
        with forks[first]:
            with forks[second]:
                meals[i] += 1                       # eating

threads = [threading.Thread(target=philosopher, args=(i,)) for i in range(N)]
for t in threads: t.start()
for t in threads: t.join()
print("all philosophers finished; meals eaten:", meals)

all philosophers finished; meals eaten: [200, 200, 200, 200, 200]

Line-by-Line Explanation

Actor: both withdrawals become messages; the actor processes them one at a time, so even with an await inside the handler the second withdrawal sees the updated balance — one approval, balance 20 (compare Module 3).

Single-flight: the first caller inserts a future; the next nine find it and await the same future — one backend call.

Coalescer: the first request schedules a flush 20 ms later; requests in that window (including the duplicate "a") join one batch.

Token bucket: three requests pass at t = 0 (burst capacity), the fourth is denied; tokens refill at 2/s.

RCU-style: readers take one reference to an immutable dict; the writer publishes a modified copy by rebinding; readers see either the whole old or the whole new version, never a mix.

Philosophers: philosopher 4 takes fork 0 before fork 4, breaking the circular wait.

Interleaving or State Trace

Actor mailbox: [withdraw 80 (A), withdraw 80 (B)] → A: 100 ≥ 80, sleep(0) (B is still queued, not running), balance 20, reply true → B: 20 < 80, reply false → stop: reply 20.

Correctness and Safety Analysis

Each pattern removes a class of hazards: actors and confinement remove shared mutation; single-flight removes duplicate work; immutability + reference swap removes torn reads; lock ordering removes circular wait. They still need bounded mailboxes, timeouts and error handling in production.

Common Mistakes and Misconceptions

Unbounded actor mailboxes (memory growth under load).

An await between check and insert in single-flight (two flights start).

Mutating a "published" immutable config in place.

Treating functools.cache as exactly-once under concurrency.

Coalescing without a maximum batch size or deadline.

Failure Modes and Debugging Steps

Actor stuck: a handler awaiting a reply from itself (actor deadlock) — use timeouts on asks. Stampede after cache expiry: add single-flight or early refresh. Rate limiter bypass: per-instance buckets in a cluster need a shared store or per-instance shares.

Performance and Scalability Implications

Actors serialise per actor — shard state across many actors; batching raises throughput and per-request latency; RCU makes reads almost free and writes expensive.

Security Considerations

Rate limiting and bulkheads are DoS defences; single-flight can propagate one failure (or one poisoned result) to many callers — validate results and avoid caching errors.

Platform and Runtime Caveats

The Python actor relies on asyncio's single-threaded loop for mailbox safety; with threads use queue.Queue. RCU in C requires a reclamation scheme (liburcu); in GC languages, the collector reclaims old versions.

Real-World Applications

Erlang/Akka/Orleans actor systems, Go's singleflight in caches and DNS resolvers, DataLoader batching in GraphQL, API gateways' token buckets, Linux kernel RCU, configuration hot reloading.

Best Practices

Start from confinement and immutability.

Use message passing for ownership transfer, actors for stateful entities.

Deduplicate in-flight work; batch and coalesce with bounds.

Choose the simplest pattern that meets measured needs.

Exercises

E1 · Beginner. Why does the actor need no lock?

Answer: Only the actor's own task touches balance, and it handles one message at a time; other tasks communicate only through the mailbox.

E2 · Intermediate. What goes wrong if SingleFlight.get awaited something between checking inflight and inserting the future?

Answer: Another caller could run during the await, find no entry, and start a second backend call — the check-then-act race returns.

E3 · Advanced challenge. Implement a leaky-bucket limiter that delays requests instead of rejecting them.

Answer: Keep next_free_time; for each request set start = max(now, next_free_time), next_free_time = start + 1/rate, and await asyncio.sleep(start - now) before proceeding (with a maximum queue delay after which the request is rejected).

Quiz

? What makes an actor safe without locks?
+ It processes its mailbox one message at a time and owns its state privately. :: No shared mutation.
- It runs on a dedicated CPU core. :: Not required.
- Its messages are encrypted. :: Unrelated.
- It never awaits. :: It may await; messages still queue.

? What does single-flight prevent?
+ Many concurrent callers triggering duplicate expensive loads for the same key. :: They share one in-flight future.
- Rate-limit violations. :: That is a rate limiter's job.
- Deadlocks. :: Unrelated.
- Data races on the cache. :: It addresses duplicate work.

? Which break the dining philosophers' deadlock? (select all that apply)
+ Acquiring forks in a global order :: Removes circular wait.
+ Letting at most four philosophers try to eat at once :: Removes the full cycle.
- Making forks recursive locks :: Different threads still wait for each other.
+ Picking up both forks atomically or not at all :: Removes hold-and-wait.

Summary

Concurrency patterns package proven solutions: single writer, immutability, confinement, message passing and actors avoid sharing; producer-consumer, pipelines, fan-out/fan-in, barriers, work stealing and map-reduce structure work; RCU, lazy initialisation, single-flight, batching and coalescing optimise shared access; rate limiters, breakers, bulkheads and backpressure protect systems; shutdown coordination ends them cleanly. Pick the simplest correct one.