Parallelism, Synchronization, and Contention

Relay Rooms adds workers to its presence-update path. Modeled throughput rises from 45,000 updates/s with one worker to 169,811/s at sixteen, then falls to 134,933/s at thirty-two. CPU is busy. The lock profile’s largest wait share belongs to metrics-label-map, at 42%. Removing that lock from the benchmark would be satisfying and would not meet the 300,000/s objective.

The metrics lock affects only 6% of successful update paths. The session-registry lock has 27% of recorded lock wait and affects 71% of those paths; its hold interval includes sequence validation, mutation, and preparation of a reader-visible snapshot. A third snapshot-publish lock contributes only 14% of wait yet sits on 84% of completions. Ranking locks by wait share ranks where sampled threads waited. It does not rank the change that releases the system constraint.

The design question is not “Which lock is hottest?” It is: which state truly requires common ordering, how much independent useful work remains after that ordering, and can ownership remove coordination from the critical path?

Parallel work needs an independence proof

Concurrency means work can be in progress during overlapping intervals. Parallelism means useful work executes simultaneously on different resources. More runnable workers can increase concurrency while reducing useful parallelism through scheduling, queues, cache displacement, synchronization, and retries.

Three decompositions expose different constraints:

• Task parallelism runs independent operations at the same stage, such as validating unrelated session updates. It scales only while tasks do not contend on a hidden allocator, registry, queue, or downstream dependency.
• Data parallelism applies a similar operation across partitions or elements. It benefits from balanced partitions, regular memory access, and a reduction whose coordination is small relative to local work.
• Pipeline parallelism overlaps distinct stages, such as decode, validate, own, publish, and transmit. Its steady throughput is bounded by the slowest stage; buffers add residence time and failure state between stages.

A workload canvas must name the unit of useful completion. Relay’s unit is one accepted presence update that passes sequence validation and becomes visible in a versioned session snapshot. Duplicate, stale, rejected, or not-yet-published updates are not goodput. The peak population has a p99 objective of 18 ms, at least 300,000 correct updates/s, and a bounded delay for high-priority leave and control operations. Eighteen percent of arrivals target the hottest ownership key.

Before adding executors, draw dependencies among units. Two updates to different sessions may be independent. Two updates for the same session require the product’s sequence rule. Publishing a global snapshot may serialize otherwise independent mutations. Recovery may require fencing an old owner before a new owner replays acknowledged commands. The independence proof is therefore conditional on key, version, stage, and operating state.

The scalability curve is a resource profile

The fixture uses a universal-scalability-form teaching model:

[ X(N) = X_1 \frac{N}{1 + \alpha(N-1) + \beta N(N-1)} ]

where (N) is workers, (X_1) is single-worker goodput, (\alpha) is a fitted serialization/contention coefficient, and (\beta) is a fitted coherency or coordination-growth coefficient. The equation describes the simulated curve. It does not infer that a measured system’s coefficients each map to one physical mechanism.

For the global design, (X_1=45{,}000/s), (\alpha=0.12), and (\beta=0.006). For the ownership design, the teaching coefficients are 0.025 and 0.0006. The latter also has a skew ceiling: one hot owner can process 70,000/s and receives 18% of arrivals, so total goodput cannot exceed approximately:

[ X_{hot} = \frac{70{,}000}{0.18} = 388{,}889/s ]

The global curve has four regions. At low (N), extra workers convert idle resources into completions. Next, common ordering limits gains. Then ownership transfer and coordination grow with participants. Finally, adding workers lowers goodput. The owned design crosses the 300,000/s objective but becomes skew-bound; it has not created unlimited scale.

Do not fit the curve from one run and treat smoothness as causality. Record offered load, goodput, correctness, latency distribution, worker utilization, runnable time, CPU placement, frequency, memory traffic, lock events, queue age, and downstream demand across independent runs. Hold the workload population constant. If larger worker counts change batching, connection count, allocation, or data placement, document the changed experiment.

Critical sections charge hold time and arrival shape

A critical section protects an invariant while common state changes. Its scope is the state and transitions that must be mutually ordered; its duration is the executed path between acquisition and release. Broad scope is easier to reason about and serializes unrelated work. Fine granularity can expose parallelism and add lock acquisition, ordering rules, memory footprint, and deadlock edges.

Contention depends on more than mean hold time. A rare 2 ms hold can delay a burst of short holders. Preemption or a page fault inside a critical section extends wall-clock ownership without adding useful protected work. A waiter awakened after release may not run immediately. A newly arriving thread may acquire first if the implementation makes no fairness promise. The relevant evidence is the distribution of hold, wait, owner-off-CPU, waiter count, and request effect by lock and call path.

A convoy forms when multiple workers queue behind a holder and then proceed in a constrained sequence. One teaching timeline is:

time →        t0         t1          t2          t3          t4
worker A      [ lock: validate + mutate ] unlock
worker B         wait ───────────────────▶[short hold] unlock
worker C           wait ─────────────────────────────▶[hold]
worker D              preempted while waiting ───────────▶ runnable
useful work     one owner       wake/schedule gaps       serialized drain

The timeline must distinguish blocked, runnable, preempted, spinning, and running. A trace that only shows pthread_mutex_lock time cannot decide whether the owner was computing, off CPU, faulting, or waiting while holding the lock. Align lock events with scheduler traces and request spans. Move I/O, logging, allocation, callbacks, and unbounded parsing out of a protected interval unless the invariant truly requires them. Never call unknown code while holding a foundational lock without documenting reentrancy and blocking behavior.

Lock granularity is a topology decision. Per-session locks reduce unrelated interference but increase object count and lifecycle work. Striped locks bound metadata while allowing false contention among keys mapped to the same stripe. Hierarchical locks can match state containment and need a global acquisition order. Optimistic reads move work to validation and retry; under write bursts they can waste more CPU and extend tails.

Synchronization primitives express different waiting contracts

A mutex grants exclusive ownership around a transition. POSIX specifies that a caller blocks when a mutex is already locked, subject to mutex type and protocol rules; it does not make every implementation fair or make a critical section short. A simple mutex is often the correct baseline because its invariant is legible and its uncontended path may already be efficient.

A reader-writer lock allows concurrent readers and an exclusive writer under its API’s policy. It helps when read-side overlap is valuable, holds are long enough to amortize additional machinery, and writer latency remains bounded. It can lose when read sections are tiny, cache-line ownership for reader bookkeeping is expensive, or the workload continuously admits readers while a writer waits. POSIX leaves scheduling-dependent selection details to the specified policy; measure the deployed implementation and declare the fairness objective.

A semaphore represents permits for a bounded resource or concurrency limit. It is not ownership of arbitrary state: a permit says capacity is available, not that a compound mutation is safe. A condition variable lets waiters sleep until a predicate may have changed. The predicate belongs under a mutex and must be checked in a loop because wake-up does not itself prove the condition. A barrier waits for a cohort to reach a phase boundary; one slow or failed participant delays the cohort, so timeouts, cancellation, and membership changes require an explicit protocol.

Use the primitive that matches the state transition:

Primitive substitution does not change required serialization. Replacing one mutex with a spin lock can turn sleeping wait into CPU consumption. Replacing it with a reader-writer lock can move contention to reader counters. Replacing it with atomics can distribute retries across callers. First reduce the protected work or shared state; then choose the simplest mechanism that enforces the remaining contract.

Atomics order memory as well as values

An atomic operation prevents a data race for that atomic object under the language’s rules and may establish ordering relationships for other memory. It does not make a multi-object invariant atomic, preserve object lifetime, or make a compound read-modify-write sequence correct by default.

A release operation can publish prior writes; an acquire operation that observes the corresponding release can make those writes visible under the language memory model. Sequential consistency adds a stronger single-order constraint for qualifying atomic operations. Relaxed operations preserve atomicity and modification order for the atomic object without establishing the acquire/release synchronization needed to publish unrelated state. The exact rules belong to the implementation language, not to intuition from one processor.

Start with the strongest simple ordering that is correct. Weaken it only with a written proof of the synchronization relation, object lifetime, and allowed outcomes, plus stress and model-oriented tests. A faster benchmark on one architecture does not prove correctness on another. volatile in C and C++ is not a replacement for atomics or locks.

Atomic read-modify-write operations can still serialize at the coherence boundary. If every worker increments one shared counter, the cache line must move among writers or be serviced by an implementation-specific coherence path. The instruction is “lock-free” in a language or library sense only under its declared property; the data path can remain a single contested resource.

Batch local counters and reduce periodically when exact instantaneous totals are unnecessary. Shard by owner when exact per-key state is required. Align or separate independently written counters only after a cache-line profile shows destructive sharing, and do not bake a universal line size into portable correctness.

Progress words are scoped guarantees, not performance grades

Blocking algorithms allow a stalled thread holding a required resource to delay others. A lock-free algorithm provides system-wide progress under its stated execution assumptions: some operation completes, not necessarily a particular caller. A wait-free algorithm bounds each operation’s own steps under its model. Obstruction-free algorithms progress when executing in isolation. These terms do not rank latency, fairness, memory use, or maintainability.

A lock-free stack can repeatedly fail compare-and-swap under contention, so one thread starves while others complete. Reclamation may use epochs, hazards, reference counts, or a runtime collector; each adds memory, scanning, quiescence, or pause behavior. Tagged pointers or versioning may address one ABA pattern while wraparound and object reuse still need proof. A complex nonblocking structure can be slower than a mutex at the real contention level and harder to recover after partial operations.

State the guarantee at the correct boundary: operation, data structure, library call, allocator, runtime, and scheduler. If the “lock-free” operation allocates from a blocking allocator, waits on page faults, or invokes a callback, the end-to-end path is not nonblocking. The WG21 progress papers and working drafts define terms for C++ atomics and execution; they do not promise a service p99.

False sharing turns independent fields into one ownership fight

True sharing occurs when workers access the same logical data and at least one writes. False sharing occurs when independently used data occupies the same coherence unit, so writes invalidate or transfer a line even though the fields do not share an application invariant.

Common patterns include per-worker counters packed together, a hot mutable flag beside read-mostly metadata, allocator metadata adjacent to payload, and two owners updating neighboring shard slots. Symptoms can include increased cache-to-cache transfers, remote modified-line hits, stalls, and throughput loss as writers spread across cores or sockets. CPU utilization can remain high because coherence work consumes cycles.

Confirm addresses, offsets, readers/writers, CPU placement, and the deployed machine’s events. Linux’s false-sharing guide describes using perf c2c, profiles, and layout tools to identify contended cache lines. Padding every object is not a general solution: it increases footprint, harms locality for read-together data, and can shift pressure to caches or translation. Separate only independently written hot fields, and measure the full workload.

False sharing also interacts with Chapter 17’s layout decision. SoA can isolate a frequently written field from cold record data, yet a dense per-owner array can place several owners’ counters together. AoS can keep one owner’s fields local, yet unrelated readers fetch a mutated flag. Layout and ownership must be designed together.

Deadlock, livelock, starvation, inversion, and fairness leave different evidence

Deadlock is a cycle or unsatisfied wait in which required progress cannot occur. Prevent it with ownership design, global acquisition order, try-and-rollback protocols where justified, bounded waits, and diagnostics that retain the wait-for graph. Timeouts surface a problem but do not make a partially applied transition safe.

Livelock keeps participants active while their retries or conflict-avoidance prevent completion. Compare-and-swap retry storms and two agents repeatedly yielding to one another are examples. Measure attempts per success, retry age, and useful goodput—not CPU alone. Randomized or bounded backoff can help, but admission and ownership reduction are often stronger.

Starvation denies a particular participant progress while the system as a whole advances. Reader preference, unfair mutex acquisition, hot-key competition, or repeated optimistic conflicts can create it. Report per-key, tenant, priority, and age distributions rather than aggregate throughput.

Priority inversion occurs when high-priority work depends on lower-priority work that cannot run promptly, potentially while medium-priority work consumes the resource. Some mutex protocols can provide inheritance or ceilings under specific operating-system policies. The service design must still avoid low-priority callbacks, I/O, or unbounded work while holding state required by control traffic.

Fairness needs a definition: FIFO acquisition, bounded wait, proportional share, deadline order, tenant share, or no starvation. These are not equivalent. Strict FIFO can worsen head-of-line blocking when task duration varies. Work-conserving scheduling can let large low-value tasks occupy every worker. Specify the product objective and measure it at the request population, not only inside the primitive.

Ownership redesign removes the shared mutation

Relay’s global registry combines three jobs: validate a session sequence, mutate current presence, and publish a reader-visible view. The redesign assigns each of 64 shards one command stream that owns mutation. A request routes by session key. The owner validates and applies updates serially for that shard, batches an immutable versioned snapshot, and publishes it for readers. Cross-shard operations use messages with idempotency keys and a bounded reduction rather than acquiring several shard locks.

This design does not abolish queues or serialization. It makes their scope observable and proportional to owned demand. It creates new contracts:

• route each key to one active owner epoch;
• bound queue count, bytes, age, and in-flight work per owner;
• keep high-priority leave/control work from waiting behind optional refresh;
• define snapshot staleness and reader fallback;
• detect duplicate, stale, and out-of-order commands;
• fence an old owner before a replacement accepts writes;
• restore the last durable sequence state and replay acknowledged commands once; and
• rebalance gradually so recovery does not create another hot owner.

The 18% hot key caps the teaching design near 388,889/s even when the unskewed curve predicts more. Possible responses depend on semantics. If sessions inside the hot key are independent, refine the partition key. If one room needs total order, keep one owner and reduce per-update work, batch compatible changes, or admit less. If reads dominate, publish a snapshot without making readers acquire mutation ownership. Do not shard an invariant that cannot be merged.

The globally locked structure can sometimes be repaired more simply: move metrics registration out of the request path, shorten the registry hold, split unrelated state, and publish snapshots less often. The ownership design earns its operational complexity only if simpler changes cannot meet the objective under skew, failure, and recovery.

The hottest lock may not be the highest-value fix

The fixture ranks locks two ways:

Wait share is affected by sample population, call frequency, waiter count, and whether spinning is attributed as lock wait. Multiplying wait share by path share is also not a causal estimator; the fixture uses it only to show why rankings can change. The decision needs a counterfactual: if this state transition were removed, shortened, partitioned, or moved, which resource and path would bind next?

Trace from objective to path, then to wait. Separate critical and background populations. Measure hold and wait distributions, not just totals. Identify owner CPU and off-CPU intervals. Compare goodput and correctness with the change under the same offered load. A low-wait lock may guard a rare control path whose delay is operationally catastrophic; a high-wait metrics lock may not affect customer completion.

Overload and recovery are concurrency states

At saturation, retrying acquisition or adding workers increases demand on the constrained state. Bound work before it reaches the contested region. Relay’s normal state admits under per-owner queue-age and in-flight limits. Its guarded state disables optional refresh and reduces snapshot frequency within the declared staleness budget. Its reject state sheds new optional presence updates before high-priority leave and control operations. Rejections are explicit outcomes, not requests left spinning.

Recovery changes ownership. After an owner failure, fence the old epoch, restore sequence and acknowledged-command state, replay idempotently, validate a new snapshot, then reopen admission gradually. A lock protected process memory before failure; it does not coordinate two owner incarnations after failure. Durable identity and fencing extend the invariant across time.

Cancellation must know whether a transition linearized. If the caller times out after enqueue but before acknowledgement, blind retry can duplicate an effect. Return or recover an operation identity and status. Chapter 19 will put explicit queues and backpressure around these stages; the ownership model here defines what each queued command means.

Choose by the remaining invariant

Keep one simple mutex when the state is small, measured contention is low, and the clarity of one transition is worth explicit serialization. Hold and wait tails, aligned with owner scheduling and the objective curve, reveal when that simplicity no longer fits. Process failure still needs recovery state; a legible in-process invariant does not survive a lost process by itself.

If keys are independent, finer or striped locks can expose overlap. Demand by stripe and the frequency of multi-key operations decide whether the gain survives skew. Once operations cross stripes, acquisition order, object lifecycle, and partial transitions become part of the design; a hot stripe can leave the original constraint largely intact.

Use a reader-writer lock only when stable reads are substantial enough to make their overlap valuable and writes remain bounded. Tiny reads, continuous readers, or a strict writer-tail objective favor a simpler design or immutable snapshots. Read and write section distributions plus a starvation test matter more than the primitive’s name, because bookkeeping and fairness policy vary by implementation.

Atomics and nonblocking structures earn their complexity when the transition and object lifetime admit a reviewed linearization and progress proof. They avoid a blocking owner but may replace waiting with retries and cache-line transfer. If the invariant spans several objects or reclamation dominates, allowed-outcome tests, retries per success, and address-level coherence evidence usually expose the mismatch.

When mutation partitions cleanly, a shard or owner removes common mutation at the cost of routing and queues. Per-owner demand, service, and age show whether skew is operable; sequence and duplicate checks test the correctness boundary. Global order or an unsplittable hot key defeats the design, while failover adds fencing, replay, epochs, and snapshot-freshness obligations.

When reads dominate and bounded staleness is acceptable, immutable snapshots plus a reduction can make reads cheap and move coordination to publication. Snapshot age, retained bytes, and build and publish tails define the envelope. The design fails when every reader needs the latest global state or old versions cannot be retained within a firm bound.

Across these choices, reduce sharing and coordination before replacing a simple lock with a more intricate primitive. Complexity is justified only by an invariant and measured operating envelope the simpler design cannot satisfy.

Field checklist

• What exact correct completion, population, latency objective, and fairness objective define scale?
• Which work units are independent by key, version, stage, and failure state?
• Does added concurrency increase goodput, or only runnable work, queues, retries, and downstream demand?
• What are lock hold, wait, owner-off-CPU, waiter-count, and request-impact distributions?
• Are critical sections free of I/O, callbacks, allocation surprises, page faults, and unbounded work?
• Which state truly requires common ordering, and can an owner or shard contain it?
• What memory-order, linearization, lifetime, reclamation, and progress guarantees are actually proven?
• Are independently written fields sharing a coherence unit, and is that confirmed by address-level evidence?
• How do skew and variable task duration change per-owner service and queue age?
• What prevents deadlock, livelock, starvation, and priority inversion, and how is fairness measured?
• What admission, cancellation, fencing, replay, snapshot, and recovery rules apply in degraded states?
• Does the simplest correct design meet the curve before a more complex primitive is introduced?

Applied diagnosis: read the profile as a path

Reproduce examples/performance-engineering-system-design-handbook/part-03/parallel-contention/ and plot both curves. Identify the point where the global model’s marginal worker reduces goodput. Then explain why fitted (\alpha) and (\beta) do not prove a mutex or coherence cause without lock, scheduler, and cache-line evidence.

Use the lock profile to propose an experiment sequence. Move label registration out of the measured interval, but predict why the objective still fails. Shorten session-registry to exact mutation only and decouple snapshot publication. Finally compare global and owned designs at equal offered load, checking output sequences, p99, rejected work, queue age, and CPU/resource evidence. State the next constraint at 32 workers: the hot owner, not the previous global lock.

A strong diagnosis treats the recovery ledger differently from a request-path lock. Its mean hold is longest, but its rarity and correctness role make a complex replacement low value until recovery evidence says otherwise.

Principal drill: design parallelism under skew

Relay must handle 300,000 correct updates/s at p99 below 18 ms. Eighteen percent target one key, 2% of updates take ten times normal validation work, leave operations outrank cosmetic refresh, and an owner can fail after applying a command but before acknowledging it. Readers accept snapshots up to 250 ms old during normal load and 2 s during guarded operation.

Produce a concurrency design that includes:

1. task, data, and pipeline boundaries with the dependency proof for each;
2. a partition or owner key and the handling of the hot key;
3. the exact role of every mutex, semaphore, condition variable, barrier, or atomic retained;
4. queue count, bytes, age, priority, cancellation, and admission bounds;
5. snapshot publication, staleness, retention, and reader fallback;
6. sequence, idempotency, fencing, ambiguous-completion, replay, and owner-recovery rules;
7. fairness metrics by tenant, priority, and oldest age;
8. lock/scheduler/cache-line traces and a scalability experiment with independent runs; and
9. rollback thresholds for correctness, p99, hot-owner age, retry attempts, and recovery time.

Reject a design that promises fairness from a primitive name, splits the hot key without preserving its ordering invariant, or calls a shared atomic counter “parallel.” The best answer may reserve one serialized owner for a truly ordered room while partitioning every independent session around it.

Evidence and transfer limits

• The Open Group POSIX pthread_mutex_lock contract defines current mutex ownership, blocking, type, and protocol behavior. Scheduling and performance depend on the deployed system and attributes.
• The Open Group POSIX pthread_rwlock_rdlock contract defines reader-writer acquisition semantics and scheduling interactions. It does not establish that reader-writer locking outperforms a mutex.
• WG21 N3927, “Definition of Lock-Free” clarifies the scope of lock-free executions and scheduling assumptions in C++. Progress terminology is not a latency result.
• WG21 N2176, “Memory Model Rationales” explains design choices behind atomics and ordering. Consult the actual language version and implementation for normative behavior.
• Linux kernel false-sharing documentation describes address-level diagnosis with profiles, perf c2c, and layout inspection. Exact events and interpretation vary by processor and kernel.
• Linux lock statistics documentation describes hold/wait collection and caller/contender reporting for kernel locks. User-space runtimes need their own equivalent evidence.
• Intel 64 and IA-32 Architectures Optimization Reference Manual, Volume 1 documents current processor-specific considerations for memory sharing and optimization. Validate on the deployed architecture.
• Every Relay value is deterministic simulated teaching evidence reproduced by examples/performance-engineering-system-design-handbook/part-03/parallel-contention/. The coefficients describe the fixture; they are not observations from a language, lock, CPU, operating system, or production service.

Parallel ownership solves only one boundary. Once owners communicate through mailboxes, channels, durable logs, or work queues, waiting has moved into explicit state with capacity, age, cancellation, and failure semantics. Chapter 19 follows that boundary and asks when asynchronous execution decouples work—and when it merely hides an unbounded queue.