Shulou(Shulou.com)06/02 Report--

This time I'm ready to start a new series to talk about concerns in distributed systems. The rhythm will not be too tight, so plan a biweekly shift.

This is the third article in this series. With the first two articles "do not know whether it is the most easy to understand" data consistency analysis "," how to solve the annoying data inconsistency? -- achieving data consistency through "consensus" to form a complete collection of "data consistency".

First, why do you need transactions

If the "consensus" solves the "horizontal" problem, then the "transaction" solves the "vertical" problem. How to make grasshoppers dance together on a rope?

Transaction is just a computer term, and the form of transaction is everywhere in our lives. Whatever we think it should be, the process of ensuring that it achieves expectations is a "transaction". To say the least, when we walk, we usually swing our left hand forward and lift our right leg at the same time. If not, it is inconsistent. Others will say that you walk incongruously. So when we were young, our parents would teach us this in a variety of ways, just like we implement "affairs" in software development.

II. The source of the transaction

When it comes to transactions, we have to mention the "XA specification" [1]. This is a period when distribution is not very popular, and it is used by most databases as the interface standard for its internal distributed transaction implementation.

The ▲ picture comes from the paper, and the copyright belongs to the original author.

The "XA specification" is the interaction specification and interface definition of "RM" and "TM" in the figure above. It only defines the function prototypes of xa_ and ax_ series, as well as functional descriptions, constraints and implementation specifications, and does not include the proposed implementation. The two-phase commit (2PC) mentioned later is the way that "TM" coordinates "RM" to complete transactions.

So in fact, it can be said that the transaction originated from the database, brilliant in the distributed system. When Moore's Law was still applicable, software systems began to use the idea of "divide and conquer" in order to carry more traffic or the number of users. Then, with the vigorous development of the Internet and the popularity of Bhand S applications, distributed systems are becoming more and more common. And with the emergence of giant Internet companies, it is more and more advocated and praised.

Behind a bright moon is a dark side, never seen.

What can be touted is always the beneficial side, coupled with dazzling data: how many TPS, how much QPS, more eye-catching. But behind this, in order to make the system after "partition" operate like a single individual as much as possible, all kinds of experts and scholars have all kinds of famous theories and solutions after years of research.

III. Transaction problems in distributed systems

As mentioned earlier, transaction problems actually exist all the time, but are magnified in distributed systems. And with the finer the granularity of the system split, the complexity of the problem increases exponentially.

For transactions in distributed systems, we have to mention two widely spread theories: "CAP" and "BASE".

The "CAP" theory was put forward by Eric Brewer at the PODC conference in 2000 [2], so it is also called Brewer theorem. It is a conjecture made by Eric Brewer when he developed search engine and distributed web cache during Inktomi:

It is impossible for a web service to provide the three following guarantees: Consistency, Availability and Partition-tolerance.

Later, Seth Gilbert and Nancy Lynch proved it [3] and became known as the "CAP" theorem (thanks to the gardener @ bangerlee for his information collection).

Yes, this is the classic picture below.

▲ pictures come from the Internet, and the copyright belongs to the original author.

Consistency (consistency): consistency here means "linear consistency". (I can read the explanation of linear consistency.)

Availability (availability): each request is answered within a certain time frame.

Partition tolerance (partition-tolerance): this should be the most obscure of the three. Allows the loss of any number of messages sent by one node to another. As long as it is a distributed system, this is inevitable, because the network and hardware will go wrong at any time.

To take a less rigorous example, this is like implementing a system that cannot generate BUG (C), has been launched within 10 days (A), and requires multiple teams to work together (P). We developers also know very well that we can't have both of them. Moreover, as long as it is an organization, teamwork is inevitable, just like the partition tolerance here, such as considering the issue of people asking for leave. The remaining two items, if there is no BUG, it is an infinite extension of time, but only infinitely close to 0, and can not reach the real 0, because no one can guarantee that all the BUG has been found.

The "BASE" theory was put forward by Dan Pritchett, the then ebay architect [4], which is essentially the weakening of "linear consistency". The ways of weakening are as mentioned in the first article in this collection, "sequential consistency" and "ultimate consistency". (I can read the explanation of these two kinds of consistency.)

The "BASE" theory is explained as follows:

Basically available (Basically Available). When a failure occurs in a distributed system, it is allowed to lose some of the available functions to ensure the availability of the core functions.

Soft state (Soft State). The state can be out of sync for a period of time, and this state does not affect system availability.

Final agreement (Eventually Consistent). Ensure that the final data are consistent, not strongly consistent all the time.

The "BASE" theory is not proposed to replace the "CAP" theory, so that we can completely put aside the "linear consistency" in the actual work. This is not the case, but leads us to distinguish between core and non-core, and then treat them separately, and the core still needs to use CAP theory to ensure "linear consistency". Why should they be treated differently? The huge performance loss caused by "linear consistency" cannot be tolerated at all, because it is anti-scalable. However, when it comes to the operation of highly sensitive data such as Money, "linear consistency" must be ensured.

Again in the above example, we focus on reducing the BUG of core functions and don't spend too much effort on non-core functions (BA). We allow the generation of BUG (S) that does not affect core functionality, but we must eventually fix (E).

Fourth, the solution of distributed transaction

If "CAP" theory and "BASE" theory are "Tao", then the solution around the evolution of these two theories is "skill". For us, it is the most important thing for us to find the most suitable one according to the scene in the practical application.

Strong consistency solutions based on "CAP" introduce something like a "coordinator" as the controller of global transactions, which you can take a look at.

01 two-phase submission (2PC) [5]

▲ pictures come from the Internet, and the copyright belongs to the original author.

In my impression, the left ear Mouse (Chen Hao) has made a vivid analogy to the wedding ceremony in the West. It's roughly like a priest asking both men and women, "would you like it?" It is equivalent to "request to submit" here, and the "yes" is equivalent to the "yes" answer. Then ask the other party to wear a ring, this request is equivalent to the "submission" here, and the feedback after wearing the ring is "ACK".

It is also worth noting that participants put their internal resources into a blocking state before answering "yes". So if something goes wrong with the coordinator after the blockage occurs, these blocked resources may not be released all the time, requiring additional intervention.

2PC is relatively the simplest transaction model, but it also has more disadvantages. Other disadvantages include inconsistent data in some scenarios (participants and coordinators fail with the "submit" link), excessive blocking scope, and so on.

02 three-phase submission (3PC) [6]

▲ pictures come from the Internet, and the copyright belongs to the original author.

The emergence of 3PC is to solve or optimize some of the problems in 2PC by increasing complexity (and therefore reduced performance). The essential change is to add a "prepare to submit" link after 2PC's "request submission" to increase that each participant needs to wait for other participants to confirm before taking specific actions.

The action of "blocking" is postponed to the "ready to submit" link, so that the blocking scope is reduced to 2 2PC 3 (background × × and green part in the figure). As in the example above, the act of giving the ring to the priest is added before exchanging the ring.

At the same time, the single point problem of the coordinator is solved. The coordinator of fault recovery or new replacement can use the status results produced by "ready to submit" as the basis for defining participants and coordinators after "submission" failure recovery. Or the previous example, exaggeration, I lost my memory when I exchanged rings, and when I regained consciousness, as long as I saw the ring in the palm of the priest's hand or my finger had been worn, I knew that my wife had said yes. I just have to keep giving her the ring.

A new timeout mechanism is introduced, which implements the default convention in the event of a timeout, avoids permanent blocking, and thus compromises 100% data consistency across multiple participants. For example, when the coordinator timeout when sending "doCommit" to participant A, it will trigger the broadcast "abort", but the "abort" cannot be delivered to participant B, causing participant B to execute the timeout default convention "commit" after "ACK".

03 TCC

In China, due to Ali's halo blessing, TCC seems to be more popular, the limelight has overshadowed 2PC and 3PC. Its essence is to find another way to achieve a similar effect as 3PC.

▲ pictures come from the Internet, and the copyright belongs to the original author.

By using the local transaction instead of the global transaction, the existence of the coordinator can be avoided and the single point problem of the coordinator can be avoided.

Another role of coordinator in 3PC: data consistency after failure recovery. Ensure through transaction logs in TTC.

This concept was first put forward by Pat Helland in 2007, when it was also called "Tentative-Confirmation-Cancellation". It was popularized by Alipay CTO (Cheng Li) at the software development 2.0 technology conference in 2008.

The above three are the mainstream DTS (Distributed Transaction Service) frameworks. It is worth mentioning that whether it is 3PC or TCC, the "idempotency" issue must be raised when it comes to fault recovery or retry mechanisms. For example, in the "submit" phase of 3PC, a participant and the coordinator hang up at the same time, but the participant has already done the commit operation before hanging up. After the fault is restored, no one knows whether it has executed the commit. The coordinator will only initiate another commit notification in order to ensure that the commit instruction is delivered 100%. At this time, if the "idempotency" is not done well, the problem of repeated commit will occur.

Let's talk about solutions based on the "BASE" theory.

01 Asynchronous messages-Local message table

▲ Click on the picture to see a larger picture

The idea of this way of implementation, originated from ebay, is in the same paper as the theory of BASE [4]. The design idea is to split the remote distributed transaction into a series of local transactions, which can be realized with the help of tables in the relational database.

02 Asynchronous messages-MQ that does not support transactions

▲ Click on the picture to see a larger picture

In fact, most MQ do not support transactions, so we need to find ways to solve the problem that MQ messages may not be delivered successfully. One cheap thing to pick up is that if the number of MQ messages to be delivered is only 1, you can put the commit of the local transaction after the message is delivered to avoid this problem. The pseudo code is as follows:

Try {beginTrans (); modifyLocalData1 (); modifyLocalData2 (); deliverMessageToMQ (); commitTrans ();} catch (Exception ex) {rollbackTrans ();}

03 Asynchronous message-MQ that supports transactions

▲ Click on the picture to see a larger picture

As far as I know, the only MQ framework that supports transactions is RockerMQ, and only recently opened up the transaction part of the implementation, "RocketMQ 4.3 officially released to support distributed transactions" (http://www.infoq.com/cn/news/2018/08/rocketmq-4.3-release). This can really save a lot of trouble. Just put a picture given by Ali to feel the details of the implementation.

▲ images come from the Internet, and the copyright belongs to the original author (click on the picture to see a larger picture)

However, there is actually one doubt that I have not verified. Friends who know can leave a message on whether RocketMQ has a mechanism to prevent the loss of ACK sent by consumer (the subscriber in the image above) after consumption is completed. If this can be achieved, the requirement for idempotency of methods within consumer is much lower.

04 Saga

▲ Click on the picture to see a larger picture

Saga is a concept put forward in 1987 [8]. The core is:

Split a distributed transaction into multiple local transactions and beat the drum to pass on to the next without blocking the local transaction waiting for a response. And allows nesting of up to one layer of subtransactions.

Except for the last participant, a "rollback" interface needs to be defined to undo previous changes to the upstream system in the event that it cannot proceed. Of course, the undo here can also be an offset class operation in addition to Update.

Saga is in principle a chained "long-lived transaction", and the whole process can take a long time. So you can add save point (SavePoint, similar to in-game archives) to facilitate fault recovery and speed up, such as forward recovery (retry) and backward recovery (rollback). However, it is also possible to have multiple sub-transactions in parallel, but generally in the Saga mode that uses the central node, as shown in the figure.

▲ Click on the picture to see a larger picture

It's just that after we break the chain rule, we have to make sure that we receive a "forward request" after performing a "rollback", which is equal to the effect of "invalid request". Another big advantage of the central node model is that it can better avoid circular dependencies between transactions.

05 Gossip protocol

By the way, this is actually a specific agreement implemented using BASE theory, which is known to more people through the heat of Cassandra. This protocol is generally used for data replication, P2P topology construction, fault detection and so on.

Looking at these cases, we can find that solutions based on "CAP" are online, while "Base" allows offline. For example, the former is, when you are tired, you must get up immediately and continue with practical information, or else you will fail. The latter is, take your time, as long as you can finally get it done.

In any case, the addition of "retry" and "rollback" to each solution will greatly improve the program's self-correcting ability to reduce the need for human intervention. The way to identify the need for human intervention is similar to the "reconciliation" mechanism, which is backtracking. Finally, you need to do a multiple choice question to prevent confusion: make sure the participant's interface is "idempotent" or "Exactly-once" in the middleware.

These "BASE"-based solutions can be used as PlanB when there is a problem with the "CAP" solution and play a complementary role. Of course, if not necessary, priority can be given to "BASE"-based solutions. After all, this is naturally scalable and will naturally lead to better performance.

5. Conclusion

There are so many solutions that whether we are architects, on our way to becoming architects, or even in our daily lives, we need to get into the habit of Balance and find the one that works best.

Finally, there is a great way to reduce redundancy.

Yes is also that, that is also, that is also right and wrong, and this is also right and wrong. -- Zhuangzi

"everything has two sides", so before choosing to be distributed, carefully consider whether it is necessary to avoid adding trouble to yourself.

Papers can be directly replied to the keyword "consistency" in the background, packaged and downloaded. The next article will open the theme of "High availability". Please look forward to it.

The ▶ background replies with the keyword "consistency" You can download Distributed TP: The XA Specification, X/Open Company Ltd., 1991 Link: https://publications.opengroup.org/c193 [2] Harvest, Yield, and Scalable Tolerant Systems, Armando Fox, Eric Brewer, 1999 Link: https://cs.uwaterloo.ca/~brecht/servers/readings-new2/harvest-yield.pdf [3] Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web, Seth Gilbert, Nancy Lynch 2002 links: https://pdfs.semanticscholar.org/24ce/ce61e2128780072bc58f90b8ba47f624bc27.pdf [4] Base: An Acid Alternative, Dan Pritchett, 2008 links: http://delivery.acm.org/10.1145/1400000/1394128/p48-pritchett.pdf [5] Consensus Protocols: Two-Phase Commit, Henry Robinson, 2008 links: http://the-paper-trail.org/blog/consensus-protocols-two-phase-commit/ [6] Consensus Protocols: Three-phase Commit, Henry Robinson 2008 links: http://the-paper-trail.org/blog/consensus-protocols-three-phase-commit/ [7] Life beyond Distributed Transactions:an Apostate's Opinion, 2007 links: https://cs.brown.edu/courses/cs227/archives/2012/papers/weaker/cidr07p15.pdf [8] Sagas, Hector Garcaa-Molrna & Kenneth Salem, 1987 links: https://www.cs.cornell.edu/andru/cs711/2002fa/reading/sagas.pdf

Author: Zachary (personal × × number: Zachary-ZF)

Official account (launch): cross-border architect.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.