System Design Fundamentals

0% completed

Concurrency and Coordination

atomicdefinition · 2023-08-02T22:44:21.830Z

I'm a bit confused about the differences between them. It seems like "concurrency control" is all about synchronizing multiple processes or threads, which is basically the same as "synchronization."

On This Page

What Concurrency Means

Race Conditions

Concurrency Control

Locking

Optimistic Concurrency Control

Transactional Memory

Synchronization

Concurrency Control vs. Synchronization

Coordination Services

Consistency Models

What One Reader Is Promised

What Everyone Agrees On

Key Takeaways

Practice Questions

Two people want the last seat on a flight. They both tap "Book" at the same moment, on different phones. Both screens say "Booked!" The airline now has two passengers and one seat.

Nothing crashed, and both requests ran correct code. The problem is that they ran at the same time, on the same data.

This lesson answers three questions. How do we stop work that runs at the same time from damaging shared data? How do many machines agree on things, like which one is in charge? And when data has copies in many places, what can a reader expect to see?

What Concurrency Means

Concurrency means many tasks are in progress at the same time. A web server handles thousands of requests at once. A database serves many users at once. In a distributed system, many machines also work on the same data.

A running program is called a process. A process can run several threads, which are smaller units of work that share the same memory. Everything in this lesson applies to both.

Concurrency is useful because it lets one system serve many users. It also creates a new kind of bug.

Race Conditions

A race condition is a bug where the result depends on the exact timing of tasks that run at the same time.

Here is a simple example. A post has 100 likes. Two users like it at the same moment, and two servers handle the requests.

Server A reads the like count: 100.
Server B reads the like count: 100.
Server A adds 1 and writes 101.
Server B adds 1 and writes 101.

Two likes were added, but the count only went up by one. Server B wrote over Server A's change. This is called a lost update.

Two servers read the same count, both add one, and the second write erases the first

This bug is hard to find because it does not happen every time. If Server B had read the count after Server A wrote 101, the result would be correct. Race conditions often appear only under heavy traffic.

Concurrency Control

Concurrency control manages access to shared resources or data when many processes run at the same time. Its goal is to let them work together without conflicts or inconsistent data.

There are three main techniques: locking, optimistic concurrency control, and transactional memory.

Locking

A lock restricts access to a shared resource, so that only one process can use it at a time. A process takes the lock, does its work, and releases the lock. Any other process that wants the resource must wait.

In the like-count example, Server A takes a lock on the post, reads 100, and writes 101. Server B waits. Then Server B takes the lock, reads 101, and writes 102. The result is correct.

Locking is simple and safe, but it has two costs.

Waiting. While one process holds a lock, the other processes that need it must wait. A lock held for a long time slows the whole system.
Deadlock. A deadlock happens when two processes each wait for a lock that the other one holds. Process 1 holds lock X and waits for lock Y. Process 2 holds lock Y and waits for lock X. Neither can continue.

A common way to prevent deadlock is to always take locks in the same order. Another way is to stop waiting and retry if a lock is not free after a short time.

Optimistic Concurrency Control

Optimistic concurrency control assumes that conflicts are rare. Processes run freely, without locks. Before saving, each process checks whether someone else changed the data. If there was a conflict, the process detects it and tries again.

A common way to check is a version number stored with the data. Here is how it works.

Server A and Server B both read the post. Its like count is 100, and its version is 7.
Server A writes 101, but only if the version is still 7. It is, so the write succeeds, and the version becomes 8.
Server B tries to write 101, but only if the version is still 7. The version is now 8, so the write fails.
Server B reads the post again, sees 101 and version 8, and writes 102.

Locking makes the second process wait, while optimistic control lets both run and makes the second one retry

When conflicts really are rare, nobody waits, and the system is fast. When conflicts are common, processes keep failing and retrying, which wastes work. In that case, locking is often the better choice.

	Locking	Optimistic concurrency control
Assumption	Conflicts are likely	Conflicts are rare
When two processes conflict	The second one waits	The second one retries
Main cost	Waiting, and possible deadlock	Repeated work after a conflict
Good fit	Booking the last seats on a flight	Editing a user profile

Transactional Memory

Transactional memory groups several operations into one transaction that runs atomically. Atomic means that all the operations happen, or none of them do. No other process can see the work half done.

For example, moving money between two accounts takes two steps. The app subtracts the money from one account and adds it to the other. When they run as one transaction, the two steps cannot be split. No other process ever sees the money missing from both accounts.

Database transactions use the same idea. The ACID vs. BASE lesson explains them.

Synchronization

Synchronization coordinates the execution of processes or threads, so that the system works correctly. It controls the order and timing of their work.

There are four common tools.

Mutexes. A mutex (mutual exclusion lock) lets exactly one thread at a time use a resource. A thread locks the mutex, does its work, and unlocks it. Every other thread that wants the resource waits until then. This is the most common form of the lock described above.

Semaphores. A semaphore limits how many threads can use a pool of resources at the same time. It keeps a counter of free slots. Each thread that enters takes one slot. When no slots are free, the next thread waits until one is released.

A database connection pool is the standard example. Suppose an app has 20 database connections, guarded by a semaphore with 20 slots. The first 20 requests get a connection at once. The 21st request waits until one of them finishes. A semaphore with only one slot works like a mutex.

A semaphore with three slots lets three requests use the database while the fourth waits for a free slot

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?"

	Concurrency control	Synchronization
Main question	Who may change the data?	In what order does work run?
Tools	Locking, optimistic control, transactional memory	Mutexes, semaphores, condition variables, barriers
Problem it prevents	Conflicting changes to data	Work running in the wrong order

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.

A coordination service is a small cluster that gives other servers configuration, service discovery, leader election, and locks

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.

Seven consistency models in two groups: what one reader is promised, and what every reader agrees on

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?