Traditional operas

I was once asked to talk about my understanding of CAP in an interview. At that time, I was able to squeeze out a few words based on the materials I had googled during the interview, just like a pupil’s recitation. The interviewer smiled helplessly and succinct summarized the key points he wanted to hear, which made me feel ashamed. Naturally, I failed in the interview. Later, I came into contact with this word occasionally at work. At the beginning, I did not get to the point.

The interviewer roughly summed it up like this: In distributed systems, failure is inevitable, partition fault tolerance (P) is necessary, and therefore the system needs to be designed with tradeoffs between availability (A) and consistency (C). At that time was very impressed by the education, now it seems that this sentence is the point out the small lotus just showed the sharp horn of that Angle.

Author: Greenwood Birdwww.qtmuniao.com/2020/02/08/…Please indicate the source

history

Eric Brewer (hence the name Of the CAP theorem, Brewer’s Theorem) had the idea around 1998, published it as a principle in 1999, and finally formally presented it as a conjecture at the 1999 PODC. In 2002, Seth Gilbert and Nancy Lynch at MIT made a proof under very bunched conditions that made it a theorem.

The point to make here is that when it comes to THE CAP principles (something like that, I’m throwing this one up), they can be vaguely defined, broad principles that inspire distributed system design. However, CAP theorem belongs to the concept of theoretical computational science in which every property has a strict mathematical definition and the conclusion has a complete derivation. Most people want to mean the former, but use the latter’s terms. Martin Kleppmann, the author of DDIA, even joked about it.

concept

The CAP principle states that a distributed storage system cannot provide services that meet the following three requirements:

  1. consistency(Consistency) : For requests from different nodes, either a response containing the latest modification or an error response is given.
  2. availability(Available) : A non-error response is given for each request, but the timeliness of the response data is not guaranteed.
  3. Partition fault tolerance(Partition tolerance) : occurs between nodes in the systemNetwork partition, the system can still respond to requests normally.

consistency

A distributed system usually contains multiple Data servers. There are three commonly used methods for distributing a Dataset to multiple nodes:

  1. Redundancy (Replication): Stores an identical full data set on each of the nodes, each of which is calledA copy of the(Replica).
  2. Partition: The data set is divided into several pieces of appropriate size and stored on different nodes.
  3. Redundancy and sharding: A data set is cut into multiple slices, each of which is redundant and stored on different nodes.

It is the redundancy and fragmentation of data that lead to consistency problems in distributed systems. Here’s a quick example:

Take the policy with only data redundancy as an example. Suppose there is a data system consisting of three nodes S0, S1 and S2, respectively storing three copies D0, D1 and D2 of a certain data set D, which is a simple set of key-value pairs. Initially, the set “A” = 0; At some time t, client C0 sends a write request set(” A “, 1) to S0 and receives a successful response. Following t, another client, C1, sends a read request to S1 to get(” A “),

If the system is designed as follows:

  1. S0Changed the value of “A” and synchronized itS1.C1Get withThe global latestdata"a" = 1The response of the
  2. The system has detectedS1The latest data has not been synchronized and is returned toC1aError response“, prompting it to retry

Then the system satisfies the consistency.

availability

It is easy to understand that the system must give a non-fault response in a finite amount of time. If the response time exceeds the tolerable time by several orders of magnitude, the service is essentially unavailable. The system responds quickly, but gives an error response, such as bad file, data stale, etc., and the service is still unavailable.

Partition fault tolerance

This property used to bother me (and still does), and I can’t give an accurate description, only from several sides.

The difficulty lies in how to understand network partitioning.

First of all, a simple understanding is that a part of the system and other parts of the network isolated, unable to communicate with each other, and thus unable to complete data synchronization in a timely manner, can be considered to have occurred network partition. For example, {S0} and {S1, S2} have network isolation, so the updated data in {S0} cannot be synchronized to {S1, S2} in time, and partitions are generated between {S0} and {S1, S2}.

Then, the restriction is further relaxed, if there are two parts in the system, the communication delay between them is very large, can not reach an agreement within the time limit, then the network partition can still be considered to have occurred. For example, after {S0} updates the data, before it is synchronized to {S1, S2}, C1 request comes, users will still access the old data, it can also be considered that {S0} and {S1, S2} generate partitions.

If the system can still provide services after network partitions occur, the system has fault tolerance of partitions.

Abstractly, network partitioning occurs when the communication delay between system components is greater than the interval between system events (such as system requests), which is also normal for distributed systems. In extreme cases, if a system is running on a single machine, but the communication latency between components such as memory and CPU within the machine is high, the single machine can be considered a distributed system and network partitioning occurs.

The above is some understanding from the practical point of view. Theoretically, the strictly defined conditions for the occurrence of network partitioning are more stringent, which will be explained in detail later.

explain

In a distributed system, network failures and node outages are the norm, so network partitions are bound to occur. When network partitioning occurs, the system needs to choose between availability and consistency based on business requirements:

  1. Ensure availability first. Some nodes are unreachable due to network partition, and the system cannot synchronize data in a timely manner. Although the requested node attempts to return the most recent data within its visibility, there is no guarantee that the data is globally up to date, sacrificing consistency to ensure availability.
  2. Make consistency a priority. Network partitioning causes the requested node to return an error message to the user if the data cannot be kept up to date globally. Or return nothing until the client times out.

But this principle does not mean that a system must abandon one of the Caps at any time. For example, when the system network is in good condition, there is no need to choose between the three. In this case, fault tolerance of partitions is not required, and consistency and availability can be taken into account.

To fully understand this principle, you need to grasp two key factors in the design of distributed systems: network environment and business requirements. In particular, it is important to note that principles are assertions in ideal situations, while practices are trade-offs in real situations, and CAP principles only point to three important trade-offs in system design.

Network environment, the network environment that different systems have to face varies greatly.

If the network condition is good and partitions are rare, then the system design should not be overly concerned with fault tolerance of partitions. For example, it can simply be designed to stop service when partitions occur, or better yet, to allow clients to retry, and so on. This may seem like a sacrifice of usability, but note that this rarely happens, so the system may still be able to serve N nines.

If the network condition is bad, the cluster size is large, and network failure and node downtime are the norm, the system design should carefully consider the trade-off between availability and consistency when network partitions occur. Here it is emphasized that the partition fault tolerance of the CAP theorem is very ideal:

The network will be allowed to arbitrarily lose many messages sent from one node to another – Gilbert, Lynch

If the network loses any messages between nodes, classical distributed consensus protocols such as Paxos and Raft will not be able to reliably select the master node and provide services properly. Industrial-level distributed database systems (such as HBase and Dynamo) cannot synchronize data between multiple machines to provide storage services. However, the network environment of the general system is not so bad, so we can balance some degree of availability and consistency through consensus algorithm, redundancy and so on.

And that, to some extent, is the business requirement that comes next.

Business requirements, according to the preferences of different business scenarios design, resulting in a variety of distributed system middleware in the market. Here, we only consider the two requirements of availability and consistency. Again, in practice, most systems do not require atomic consistency or perfect availability.

For consistency, there are strong consistency, weak consistency, final consistency and other options according to the requirements. Industrial-level systems, to provide high availability, often opt for weak consistency or final consistency where the business can tolerate it, such as Amazon’s key-value pair storage Dynamo.

For availability, it is necessary to consider the number of requests from system users, the level of concurrency, the size of data and so on to define the availability of the system. It is impossible for any system to cover all scenarios. As long as the system design can meet the business scenarios for which it is oriented, the system can be said to meet the availability requirements. For example, for a private cloud object storage service, the traffic may be only dozens of QPS per day, read far more than write, and the concurrency is very low. In this case, it is possible to design the system in a way that is not too complex but that is consistent and usable. But if the service is used as a Taobao Double 11 scene, the system usability is basically gone.

conclusion

CAP generalizes the important tradeoffs in distributed system design when distributed systems are not popular. With cloud computing and big data in full swing today, a large number of excellent distributed systems have emerged, giving us more consideration directions and practical details for system design. Nowadays, when designing systems, we don’t have to stick to CAP principles. We can make bold choices according to the business scenarios we face.

Recommended reading

  1. Wikipedia, CAP, unseen: en.wikipedia.org/wiki/CAP_th…
  2. Distributed pamphlets, Distributed Systems, for Fun and Profit: book.mixu.net/distsys/abs…
  3. Jeff Hodges, beginners to distributed system notes: www.somethingsimilar.com/2013/01/14/…
  4. Codahale.com/you-cant-sa…
  5. Left ear Mouse recommended, distributed system architecture classic information: www.infoq.cn/article/201…

Welcome to pay attention to the public number distributed drip, get more distributed system articles.

Chat 🏆 technology project stage v | distributed those things…