Concurrency and Coordination

Condition variables. A condition variable lets a thread sleep until a condition becomes true. The classic example is a worker waiting for a queue to have items. The worker does not check the queue again and again. It sleeps, and the thread that adds work to the queue wakes the worker up.

Barriers. A barrier holds threads at a point until all of them arrive, and then lets them all continue. A job that runs in phases uses one. Every worker must finish phase one before any worker starts phase two.

Concurrency Control vs. Synchronization

The two ideas are easy to mix up because both deal with work that runs at the same time.

Concurrency control is about access. It manages who can use a shared resource, and it prevents conflicts when two processes want to change the same data.

Synchronization is about timing and order. It makes sure certain work happens before other work, and that processes do not interfere with each other.

One asks, "May you use this data now?" The other asks, "Is it your turn yet?"

Coordination Services

Locks and semaphores are easy to use when all threads share one machine's memory. Across many machines, it is much harder. The machines share no memory. Messages over the network can be slow or lost. And any machine can crash in the middle of its work.

Coordination services are specialized tools that handle these hard problems for a distributed system. They provide ready-made solutions for four common tasks.

• Configuration management. All servers read the same settings from one place. When a setting changes, every server learns about it.
• Service discovery. A server finds the addresses of healthy instances of another service. For example, the order service asks where the payment service is running right now.
• Leader election. A group of servers picks exactly one of them as the leader, which is the server that makes decisions for the group. If the leader crashes, the group picks a new one.
• Distributed locking. Processes on different machines share one lock. The lock usually has an expiry time, so it is released if the holder crashes.

The best-known coordination services are Apache ZooKeeper, etcd, and Consul.

A coordination service is itself a small cluster, usually of three or five nodes. A change is accepted only when a majority of the nodes agree. That majority is called a quorum. So the service keeps working even if one node fails. The quorum and leader and follower chapters explain how this works.

Why not build these features yourself? Each one is hard to get right. Small mistakes often cause failures that appear only under heavy load or during a network problem. So teams use a tested service instead.

Consistency Models

Many distributed systems keep copies of the same data on several servers. Each copy is called a replica. When data changes on one replica, the other replicas do not change at the same instant.

A consistency model is the promise a system makes about when a change made in one place becomes visible in another. Every model answers one question: after someone writes something, who may still see the old version, and for how long?

One example, used throughout. Sarah posts "Got the job!" on a social app. The app keeps replicas in several regions. Her friends Raj and Mia read the post from different regions. Each model below says something different about what Raj and Mia may see.

What One Reader Is Promised

These models make a promise to one person. They say nothing about what anyone else sees.

Eventual consistency. Raj sees the post after two seconds, and Mia sees it after ten. Both see it in the end, but there is no promise about when. This is the weakest common model. It also keeps a system fast and available because a replica can answer at once with the data it already has.

Monotonic read consistency. Once Raj has seen the post, it never disappears for him. Without this promise, his next refresh might reach a replica that does not have the post yet. The post would vanish and then come back.

Read-your-writes consistency. Sarah always sees her own post at once, even while Raj and Mia still cannot. The promise is made only to the person who wrote the data. This is why your own profile change looks instant to you, but takes a moment to reach others.

Session consistency. This is read-your-writes for a whole visit, called a session. Sarah keeps seeing her own post even if the app moves her to a different replica during her visit. A shopping cart that keeps showing its items for one user's whole visit is another example.

What Everyone Agrees On

These models describe the order that all readers see, not the experience of one person.

Causal consistency. Raj replies "Congratulations!" to Sarah's post. Anyone who can see Raj's reply must also be able to see the post it answers. A cause is always visible wherever its effect is visible. Operations that are not related may still appear in different orders in different regions.

Sequential consistency. Sarah posts, and then Mia posts. Every reader sees those two posts in the same order. But the shared order does not have to match the clock. Every reader could see Mia's post first, as long as all readers agree.

Linearizability. This is sequential consistency plus the clock. Every operation is atomic, and it is visible to all nodes the instant it completes. The moment Sarah's post is confirmed, a read from any region returns it. The shared order must match the order in which things really happened.

The difference between the last two models needs a precise example. Sarah's write finishes at 10:00:00. Raj starts a read at 10:00:05 and gets the old version, without the post.

• Sequential consistency allows this, as long as all readers agree on one order in which Raj's read came before Sarah's write.
• Linearizability does not allow this, because Sarah's write had already finished in real time before Raj's read began.

A note on names. You will often see strong consistency listed as its own model. In practice, it means linearizability, and this course treats the two as the same guarantee.

These models do not form one simple ranking from weakest to strongest. The first group makes promises to one reader. The second group sets rules for all readers. But every promise has a cost. A stronger guarantee needs more coordination between replicas. That means slower writes, less availability when the network between replicas fails, or both.

So the right model depends on the operation, not on the whole system. A bank balance may need linearizability, while a news feed can be eventually consistent. One system often uses different models for different data. The CAP theorem chapter explains this trade-off.

Key Takeaways

• A race condition is a bug where the result depends on the timing of tasks that run at the same time. A lost update is a common example.
• Concurrency control manages access to shared data. Its techniques are locking, optimistic concurrency control, and transactional memory.
• A lock lets only one process use a resource at a time. It is safe, but others must wait, and deadlocks are possible.
• Optimistic concurrency control assumes conflicts are rare. Processes run freely, and a conflict is detected and fixed with a retry.
• Synchronization coordinates the timing and order of work, using mutexes, semaphores, condition variables, and barriers.
• Coordination services like ZooKeeper, etcd, and Consul provide configuration management, service discovery, leader election, and distributed locking.
• Consistency models range from eventual consistency to linearizability. Stronger promises need more coordination, so choose a model for each operation.

Work that runs at the same time is what lets a system serve many users. Controlling that work is what keeps the data correct. The next lesson, Monitoring and Observability, covers how to find out what such a system is actually doing.

Practice Questions

Try each question first, then open the answer.

1. A product has 10 items in stock. Two servers sell one item each at the same moment. Each server reads the count, subtracts 1, and writes the result, with no lock. What final counts are possible, and which one is correct?

<details> <summary>Show answer</summary>

8 is correct, but 9 is also possible. If one server finishes before the other one reads, the second server reads 9 and writes 8. If both servers read 10 before either one writes, both write 9. One sale is then lost. This is a race condition, and a lock or a version check prevents it.

</details>

2. Many people edit pages on a wiki, but two people rarely edit the same page at the same time. Should the system use locking or optimistic concurrency control?

<details> <summary>Show answer</summary>

Optimistic concurrency control. Conflicts are rare, so most edits succeed on the first try and nobody waits. When a conflict does happen, the second editor reloads the page and makes the change again. With locking, editors would wait for each other, even though conflicts almost never happen.

</details>

3. An app has a pool of 10 database connections, and 14 requests arrive at the same time. Which synchronization tool fits, and what happens to the requests?

<details> <summary>Show answer</summary>

A semaphore with 10 slots. The first 10 requests each take a slot and a connection. The other 4 requests wait. Each time a request finishes and releases its slot, one waiting request takes it.

</details>

4. Three servers run the same code, but only one of them should send the daily report email. If that server crashes, another server should take over. What does the team need, and which tools provide it?

<details> <summary>Show answer</summary>

Leader election. The servers use a coordination service like ZooKeeper, etcd, or Consul to pick one leader. Only the leader sends the email. If the leader crashes, the service notices, and the remaining servers pick a new leader.

</details>

5. A user changes their profile photo, refreshes the page, and still sees the old photo. It is fine if other users see the old photo for a few seconds. Which consistency model fixes this user's problem at the lowest cost?

<details> <summary>Show answer</summary>

Read-your-writes consistency. It promises that the person who made a change sees it at once. Other users may still see the old photo for a short time, under eventual consistency. Linearizability would also fix the problem, but it needs much more coordination between replicas for every user.

</details>