Data Consistency and Availability in distributed systems

A. What is Consistency?

When we have multiple copies of data, those data pieces must match each other. This is a core concept of computer science, appearing in the CAP theorem and in the ACID acronym.

Propogating updates is HARD

The easiest way to ensure consistency is having a single server. However, there are some practical problems with this approach 😓

1. Single Point of Failure: In case of network outage, power loss, goofy admins (like me), our system goes DOWN.

2. Scaling: As we get more clients, we must vertically scale our (only) server. But, even a supercomputer can't handle all of Google's load. You just HAVE to add more servers after a point.

3. Latency: Clients located far away from our server will have very high latency. Increased response time directly correlates to customer dropoff. Having multiple servers located close to the geographical location of our users is a saving in cost and improves our product offering (Think of a collection of corner shops vs. a big mall).

There is no free lunch though. Using a distributed system makes our system less consistent. Let's take an example:

Two servers A and B, each have copies of X.

1. User 1 sends a request to A to update x -> y.
2. Server A updates the value and sends the update request to Server B.
3. While Server A is sending the update request, User 2 sends a read request to server B.
4. User 2 will get the value X from server B.

Our system data is inconsistent.

Inconsistency in distributed systems example

B. Methods to update values in different servers

1. Using manual updates

If we have very infrequent updates and the users don't need to see the updates in real-time we can manually send the update messages to different servers.

Manually updating multiple databases is tedious

2. TCP with acknowledgments

For real-time updates, we send update messages over TCP, and wait on acknowledgments from update receivers.

On successful acknowledgement, we know that message propagation was successful, and the system is consistent upto this TCP update.

On failure to recieve acknowledgement, the updater can retry till it succeeds. We can retry at regular intervals with a maximum retry limit.

However, this method brings us to a fundamental problem with distributed system: The Two Generals Problem. It states that we can never be sure if we are making a commit that is based on the hope that the acknowledgment goes through.

Data consistency using acknowledgements video

3. Leader-Follower Architecture

One for all and all for one? Not really. Here, we have one leader and the rest are followers.

1. If there is an update request, it must be routed to the leader.
2. Follower servers get regular updates from the leader.
3. Both leaders and followers get read requests.

What happens if an update does not go through to the followers?

1. This leads to data inconsistency. But the system is still responding to requests. So it is up and available.
2. If you force the system to wait for the update propogate across the system, the system is unavailable.

We note that Data Consistency and Data Availability are tradeoffs in a distributed system.

4. Two-Phase Commit Protocol

This requires a distributed system with one leader and multiple followers.

1. Leader gets an update.
2. It sends a "prepare" request to the followers. It is the first phase of the process. In this phase, all the statements in the transactions are executed but not committed.
3. Followers send the leaders an acknowledgment, notifying the leader that they got the request. Acknowledgment here means that the server has executed all the statements in the transaction successfully and is ready to commit.
4. If the leader does not get acknowledgment from all the followers, it assumes that some of the servers have failed. In such cases, the leader fails the transaction and executes a rollback.
5. If the leader gets positive acknowledgment from all followers it then asks all the followers to commit (like committing a transaction).
6. If the leader does not send a commit message then the followers rollback. (This is an edge case)
7. After the data is committed, followers send an acknowledgment to the leader.

Two phase commit protocol explanation video

C. Conclusion

Consistency is a crucial property of a distributed system. Although maintaining consistency can be challenging, there are approaches that can be used to ensure it. The two-phase commit protocol and the leader-follower architecture are two common approaches.

Thank you for reading! You can check out more system design concepts with us here: System Design Fundamentals.