Concurrency and Coordination

Distributed components run at the same time and share state, and three concerns get muddled constantly: concurrency control (keeping shared data correct under simultaneous access), synchronization (coordinating ordering and timing), and consistency models (what a reader is promised to see). This lesson separates them where they genuinely differ, shows where they overlap, and pins down the parts people most often get wrong: how coordination services actually serve reads, and how a real rate limiter is built.

Concurrency control: keep shared state correct

Concurrency control is a goal: when many processes touch the same data at once, the result must be as if they had run in some valid order. The common techniques trade off differently:

• Pessimistic locking (2PL): acquire a lock before touching data. Simple and safe under contention, but locks serialize work and can deadlock. Use when conflicts are frequent or correctness is non-negotiable.
• Optimistic concurrency control (OCC): proceed without locking, then validate at commit (via version numbers or timestamps) and abort/retry on conflict. Best when conflicts are rare; wasteful when they are common because of repeated retries.
• Multi-version concurrency control (MVCC): keep multiple versions so readers see a consistent snapshot without blocking writers (Postgres, MySQL/InnoDB). Great read throughput; costs storage and vacuum/GC of old versions.
• Transactional memory: group operations to commit atomically, resolving conflicts underneath. Attractive in-process; harder to make efficient across a network.

Synchronization and concurrency control overlap — they are not disjoint

It is tempting to draw a hard line — "concurrency control is about correctness, synchronization is about timing" — but that split is misleading. A mutex or semaphore is a canonical synchronization primitive and the very mechanism you use to enforce concurrency control. The two words mostly differ in emphasis, not in what they cover:

• Synchronization primitives — locks, semaphores, monitors, barriers, condition variables — are the tools.
• Concurrency control is one thing you build with those tools (alongside MVCC/OCC schemes that are themselves synchronization strategies).

So a semaphore protecting a shared counter is doing concurrency control; a barrier making all workers reach a checkpoint before proceeding is doing pure ordering. Same family of primitives, different intent. The diagram below shows the overlap rather than a false partition.

Coordination services: ZooKeeper, etcd, Consul

These systems provide leader election, service discovery, config, and distributed locks on top of a replicated log kept in sync by a consensus protocol (ZAB for ZooKeeper, Raft for etcd and Consul). Every write goes through the leader and is quorum-committed — acknowledged only after a majority of nodes have durably stored it.

Correction to a common myth: quorum commit makes writes linearizable and durable. It does not, by itself, make reads linearizable. A read is linearizable only if it is additionally routed through the current leader with a leadership check (Raft's ReadIndex or a leader lease) or preceded by a sync. If a read is served locally from a follower's copy, it can be stale even though every write was quorum-committed. The three services differ sharply in their default read behavior:

So the accurate statement is: all three give linearizable writes; only etcd gives linearizable reads out of the box. ZooKeeper reads are sequentially consistent (a client never goes backward in time, but may lag the latest committed write), and Consul's default trades a little freshness for latency.

Where does a gateway fleet actually meet these systems? Route and config propagation: gateway instances watch etcd or Consul for upstream changes — and here a slightly stale (default-mode, non-linearizable) read is the right choice, because a route table lagging by tens of milliseconds is harmless and cheap, while forcing a linearizable read on every config watch buys nothing a health check doesn't already cover. Rate-limit counters: the opposite — a shared counter is only correct under atomic read-modify-write (the Redis INCR in the worked example below), never a stale snapshot. One fleet, two consistency choices, chosen per data: that is the lesson.

Consistency models: the spectrum

A consistency model is the contract between the store and a reader — what a read is allowed to return relative to prior writes. Weaker models buy availability and latency; stronger models buy predictability. From weakest to strongest:

• Eventual consistency: if writes stop, replicas eventually converge; a read may return a stale value in the meantime. Example: Amazon DynamoDB's default reads are eventually consistent — cheaper and faster, but a just-written item may not appear on every replica yet (DynamoDB also offers opt-in strongly consistent reads).
• Causal consistency: operations that are causally related are seen in the same order everywhere; concurrent (unrelated) operations may be seen in different orders on different nodes. Example: on social media, anyone who sees a comment must also see the post it replies to — the post causally precedes the comment.
• Sequential consistency: there is one global total order of operations consistent with each process's program order, but it need not match real (wall-clock) time. Example: merging per-server logs into one agreed sequence that respects each server's own ordering.
• Linearizability (strong consistency): the strongest single-object model — every operation appears to take effect atomically at one instant between its call and return, so a read always sees the most recent committed write in real time. Example: a compare-and-swap on a distributed key-value store that every client observes identically the moment it commits.

Client-centric guarantees layer on top of these and are usually what apps actually need: read-your-writes (you always see your own last write), monotonic reads (you never see time go backwards), and session consistency (both, scoped to a session). ZooKeeper's per-client ordering is exactly this flavor: sequentially consistent and monotonic per client, but not globally linearizable for reads.

Choosing a model is a trade-off, not a ranking: linearizability is easiest to reason about but forces coordination on the write/read path (hurting latency and availability under partition, per CAP), while eventual consistency maximizes availability at the cost of temporary staleness.

Distributed locks: fencing, not just mutual exclusion

The distributed lock is the feature most people reach a coordination service for — "make sure only one worker runs job J" — and it is also where naive use silently corrupts data. A lock taken with a TTL (say Redis SET job:J <token> NX EX 30, or an ephemeral key in ZooKeeper/etcd) can expire while its holder is still alive but paused: a long GC pause, a slow syscall, a VM freeze. The lease lapses, a second worker acquires the lock, and now two workers each believe they hold it. Mutual exclusion has failed without any error being raised, and if the job is not idempotent you get dual execution — a payment charged twice, one file written by two writers.

The fix is a fencing token: the lock service issues a monotonically increasing number with each grant, and every write to the protected resource carries its token. The storage layer remembers the highest token it has accepted and rejects any write bearing a lower one. When the paused worker wakes and tries to write with its now-stale token, the store refuses it — correctness no longer depends on the lease being perfectly timed, only on token ordering. This is precisely the guarantee a bare TTL cannot provide, which is why "we put a TTL on the lock" is not, on its own, a correct distributed lock.

When NOT to use a distributed lock. A lock on the hot request path is a scalability tax: every request now serializes through one coordination round-trip, so at, say, 100k req/s that round-trip becomes both the throughput bottleneck and a shared outage surface. Two alternatives usually win. Ownership partitioning — consistently hash the job/entity ID to a single owning worker — makes exclusivity structural, so no lock is needed at all. Optimistic concurrency control — skip the lock and, on write, execute UPDATE ... SET ..., version = version + 1 WHERE id = ? AND version = ?, retrying whenever it matches zero rows — replaces coordination with a cheap conditional write when conflicts are rare. Reserve coordination services (ZooKeeper/etcd) for coarse, low-frequency decisions — leader election, membership, config — not per-request locking.

Worked example: a correct fixed-window rate limiter

Rate limiting is where an API gateway meets concurrency in practice: many gateway instances share one counter (usually in Redis), so the increment-and-check must be safe under concurrent requests. Consider "100 requests per minute per user."

The naive version is subtly broken

A first attempt reads "increment a counter, reject if it exceeds 100." Two things are missing:

1. No time window. A plain counter never resets, so after a user hits 100 once they are rejected forever. "Per minute" requires an EXPIRE (or a time-bucketed key) that actually bounds the window — nothing in "INCR then reject" provides that.
2. The rejected request still counts. With INCR-then-check, the 101st request executes the increment before it is rejected, so the counter keeps climbing past 100 even while every over-limit request is turned away. Without an expiry to reset it, that inflation is permanent.

The correct mechanics

Use an atomic INCR (it is atomic in Redis, so concurrent gateways can't lose updates), key the counter by a time bucket, and set the TTL exactly once when the window opens:

key = "rl:" + user_id + ":" + current_minute
count = INCR(key)              # atomic; returns the new value
if count == 1:                 # first request of this window...
    EXPIRE(key, 60)            # ...arm the 60s window
if count > 100:
    return 429                 # reject (this request already counted)
allow()

Three details make it correct:

• Atomicity of INCR means two simultaneous requests can never both read "99" and both pass — they get 100 and 101.
• EXPIRE on the first hit is what turns a raw counter into a per-minute limit; when the key expires, the next request re-creates it at 1.
• Crash safety: if the process dies between INCR and EXPIRE, the key has no TTL and the user is locked out until manual cleanup. Bundle both commands in a single Lua script so they apply as one atomic unit. (A plain INCR followed by a separate EXPIRE is not crash-safe, and pre-creating the key to 1 out-of-band before the INCR miscounts the first request as 2 — the atomic script is what avoids both traps.)

The lingering counter inflation is acceptable here: everything above 100 is rejected anyway, and the whole key vanishes at expiry. If you need the counter to reflect only admitted requests, either decrement on rejection or do the limit check inside the Lua script before incrementing. Note the classic fixed-window flaw too — a burst straddling the boundary can allow up to 2x the limit across two adjacent windows; sliding-window counters or a token bucket smooth that out.

Sources and further reading

Adapted and corrected from the original lesson "Concurrency and Coordination" in the System Design / API Gateway track of this guide. The corrected read-consistency and mechanism claims are grounded in primary documentation and standard references:

• Apache ZooKeeper — Consistency Guarantees and the sync() operation (reads are served locally and are sequentially consistent, not linearizable).
• etcd documentation — API guarantees: linearizable reads by default, opt-in serializable reads.
• HashiCorp Consul — Consistency Modes: default (leader-lease, possibly stale), consistent (linearizable), stale.
• Herlihy & Wing (1990), Linearizability: A Correctness Condition for Concurrent Objects.
• Martin Kleppmann, Designing Data-Intensive Applications, ch. 5 and 9 (replication, consistency, and consensus).
• Amazon DynamoDB Developer Guide — Read Consistency (eventually vs. strongly consistent reads).
• Redis documentation — INCR, EXPIRE, and rate-limiting patterns (atomic counters, Lua scripting).