Distributed Development (1) ---CAP Theory

Traditional database (relational database) design follows ACID rules, and distributed system design also has a corresponding CAP theory.

1. ACID

ACID refers to the abbreviation of the four basic elements for the correct execution of database transactions. Including: Atomicity, Consistency, Isolation, Durability. A database that supports transactions (Transaction) must have these four characteristics, otherwise the correctness of the data cannot be guaranteed in the transaction processing (Transaction processing).

1. Atomicity

Atomicity means that all operations in a transaction are either completed or not completed at all , and will not end in an intermediate link. If an error occurs during the execution of the transaction, it will be restored (Rollback) to the state before the transaction started, as if the transaction had never been executed.

example

For example, bank transfer, deduct money from account A and add money to account B, these two operations must be performed at the same time. The transfer involves two steps:

A: 1000-200 = 800
B: 300 + 200 = 500

Atomicity means that these two steps succeed together or fail together, and only one of the actions cannot occur. Otherwise, there will be a situation where the accounts are not aligned.


2. Consistency

Consistency means that a transaction can encapsulate state changes (unless it is a read-only). Transactions must always keep the system in a consistent state, no matter how many concurrent transactions are at any given time.

In layman's terms, the transaction must be changed from one consistency state to another consistency state after the transaction is executed . Before the start of the transaction and after the end of the transaction, the integrity of the database has not been destroyed.

Example
Let's take the bank transfer scenario as an example.
Assuming there are five accounts, each account balance is 100 yuan, then the total amount of the five accounts is 500 yuan, if multiple transfers occur simultaneously between these 5 accounts, no matter how many concurrently, such as between A and B accounts Transfer 5 yuan, transfer 10 yuan between C and D accounts, transfer 15 yuan between B and E, and the total amount of the five accounts should still be 500 yuan.


3. Isolation

Isolation refers to the ability of a database to allow multiple concurrent transactions to read, write and modify its data at the same time. Isolation can prevent data inconsistencies caused by cross execution when multiple transactions are executed concurrently.

Isolation means that multiple concurrency is invisible, and mutual isolation is not disturbed. If isolation is not considered, the following problems may occur:

  • Dirty read : Transaction T1 reads the uncommitted data of transaction T2. ​​As a result, transaction T2 is rolled back, and T1 gets a dirty data.
  • Non-repeatable read : After transaction T1 reads the data, the data is updated immediately after transaction T2. ​​When transaction T1 reads again, the data is found to be inconsistent.
  • Phantom read : This kind of generally occurs during mass modification. For example, transaction T1 modifies all data from 1 to 2. As a result, during the modification process, transaction T2 inserts a new piece of data 1. Finally, check the data and find that one piece of data has not been modified.

In response to the above problems, the database provides four transaction isolation levels: Read uncommitted, Read committed, Repeatable read, and Serializable from low to high. These four levels can solve dirty reads, non-repeatable reads, and phantom reads one by one. Class problem.

√ means it will happen, × means it will not happen

 Dirty readNon-repeatablePhantom reading
Read uncommitted
Read committedX
Repeatable readXX
SerializableXXX

Among them, Read uncommitted is the lowest level, which cannot be guaranteed under any circumstances.


4. Durability

Persistence means that after the transaction is completed, the changes made to the database by the transaction are persisted in the database and will not be rolled back.
In layman's terms, after the transaction is submitted, the saved result remains unchanged. Even if the database fails, it should not have any impact on it.

Two, CAP

1. CAP overview

In 1998, Eric Brewer, a computer scientist at the University of California, proposed that distributed systems have three indicators: Consistency, Availability, and Partition tolerance. Their first letters are C, A, and P, respectively.
Eric Brewer said that these three indicators cannot be achieved at the same time. This conclusion is called the CAP theorem.

The CAP principle, also known as the CAP theorem, refers to the consistency (Consistency), availability (Availability), and partition tolerance (Partition tolerance) in a distributed system . The CAP principle means that these three elements can only achieve two points at the same time, and it is impossible to take care of all three.

Consistency

Consistency refers to "all nodes see the same data at the same time", that is, after the update operation is successful and returns to the client, the data of all nodes at the same time is completely consistent, which is distributed consistency.

In distributed consistency, consistency includes strong consistency and weak consistency . Strong consistency means that the data seen by any node at any time is the same; weak consistency generally achieves final consistency, that is, it may exist at the beginning Differences, but over time, the final data remains consistent.

Availability (Availability)

Availability refers to "Reads and writes always succeed", that is, the service is always available, and it is the normal response time.

Partition tolerance

Partition fault tolerance refers to "the system continues to operate despite arbitrary message loss or failure of part of the system", that is, when a distributed system encounters a node or network partition failure, it can still provide external services that meet consistency and availability .

In layman's terms, when the network nodes cannot communicate with each other, the nodes are isolated, resulting in network partitions, and the entire system can still work.

2. CAP's choice strategy

The three characteristics of CAP can only meet two of them, so there are three strategies to choose:

CA without P: If P is not required (partitioning is not allowed), then C (strong consistency) and A (availability) can be guaranteed . But giving up P also means giving up the scalability of the system, that is, the distributed nodes are limited, and there is no way to deploy child nodes, which is contrary to the original intention of the distributed system design. Traditional relational database RDBMS: Oracle and MySQL are CA.

So, for a distributed system. P is a basic requirement. Among the three CAPs, only a trade-off can be made between the two CAs .

CP without A: If A (available) is not required, it is equivalent to maintaining strong consistency between servers for each request, and P (partition) will cause the synchronization time to be extended indefinitely (that is, waiting for data synchronization to be completed before normal access to the service) In the event of a network failure or message loss, the user’s experience must be sacrificed and the user will be allowed to access the system after all the data is consistent. There are actually many systems designed as CP, the most typical ones are distributed databases, such as Redis, HBase, etc. For these distributed databases, data consistency is the most basic requirement, because if even this standard is not met, then it is better to directly use relational databases, and there is no need to waste resources to deploy distributed databases.

AP wihtout C: To be highly available and allow partitioning, you need to give up consistency. Once the partition occurs, the nodes may lose contact. For high availability, each node can only use local data to provide services, and this will lead to inconsistencies in global data. A typical application is like a mobile phone rush scene in a certain meter. The page may indicate that there is inventory in the first few seconds when you browse the product. When you select the product and prepare to place an order, the system prompts you that the order has failed and the product has been sold out. . This is actually to first ensure the normal service of the system in terms of A (availability), and then make some sacrifices in terms of data consistency. Although it will affect some user experience to some extent, it will not cause serious blockage in the user's shopping process.

There is no conclusion about which is the best one, and it can only be determined according to the scene, and the best one is suitable.

Three, BASE theory

Dan Pritchett, the architect of eBay, originated from the summary of the practice of large-scale distributed systems. He published an article on ACM and proposed the BASE theory. The BASE theory is an extension of the CAP theory. The core idea is that even if strong consistency cannot be achieved (Strong Consistency, The consistency of CAP is strong consistency), but the application can use a suitable way to achieve eventual consistency (Eventual Consitency).

BASE refers to Basically Available, Soft State, Eventual Consistency.