Spring Festival travel ticket rush, the technology behind the ticketing system is so sophisticated!

In daily life, people have become so accustomed to convenient applications such as online shopping, online payment, and map navigation that we hardly pay attention to the technology behind them. This is naturally inseparable from the leapfrog development of communication networks, and the realization of those functions is due to the progress of distributed systems. This article briefly introduces the concept of distributed systems, including its core Paxos algorithm, and how it copes with the challenge of network disconnection through the example of online ticket purchase.

Written by | Chen Qingyang

The annual Spring Festival travel rush is here again. It is estimated that this year's railway passenger volume may exceed 510 million, with an average of 12.75 million passengers per day. Behind the competition of people's hand speed to grab tickets, how does the computer system of 12306 respond to the massive requests quickly? Due to limited computing power, a single server cannot respond to thousands of requests quickly. Imagine the scene of 10,000 people queuing up at only one ticket window in the offline ticket hall. I'm afraid people will have to bring sleeping bags to queue up.

So how can we speed up the ticketing process to reduce people's waiting time? First, the staff at the window can speed up their hands and operate at a very fast speed, but there is a limit to how fast a single staff member can operate; another way is to open multiple windows in the hall and sell tickets at the same time. The same is true for the online ticketing system. If a single server cannot handle it, multiple servers are used to coordinate the processing, which requires the appearance of a "distributed system"!

What is a distributed system?

In layman's terms, a distributed system refers to a group of computers working together to complete a task. These computers can also be called nodes. They are connected together through the network and work together, but they behave like a whole to users. It's not just the 12306 ticketing system. The recommendations you see when you watch videos, the search results given by search engines, and the order distribution of food delivery platforms are all silently running behind distributed systems. Compared with a single server, the use of a distributed system can not only improve the performance of the system and the speed of responding to requests, but also provide better reliability. If some nodes are down or disconnected from the network, the entire system can still continue to provide services.

Although distributed systems have these benefits, the complexity they bring also poses challenges to computer system design. This involves issues of concurrency and data consistency. Take ticket sales as an example. Imagine the following scenario: Zhang San in Beijing and Li Si in Guangzhou are trying to buy the same ticket. Zhang San's ticket request is distributed to a server in North China, while Li Si's request is distributed to a server in South China. These two servers can now process the ticket requests of two people in parallel. The overall response speed of the system is very fast, but how can the system properly collaborate so that the tickets are not sold twice?

In addition, another major feature of distributed systems is the possibility of partial failure, which means that part of the system fails, but the rest of the system can still operate. Distributed systems are composed of many computers and are connected through a network. Obviously, both the computer and the network itself may fail, such as a power outage somewhere, a broken network cable, or a computer operating system failure. Even if the probability of a machine failing is very low, when the number of computers increases, failures will be very frequent for the entire system.

We can do a simple calculation. Assuming that there are 1,000 computers in the system, and each computer fails only once a year on average (the failure may be caused by any reason), the probability of a failure every day is 1/365; conversely, the probability of no failure every day is 1-1/365, which is approximately equal to 0.99726. This seems to be a high probability, but for the entire system, the probability of no failure on all machines every day is 0.99726 to the 1000th power, which is approximately 0.064. Network issues are not considered here, so it is almost impossible for the system to not fail.

Therefore, in the design of distributed systems, how to provide normal services when some nodes fail or the network is disconnected is an issue that must be considered.

The cornerstone of distributed systems - consensus algorithm

Consensus algorithms play a core role in distributed systems. They enable the entire system to reach a consensus on a certain issue even when there is no shared memory, the system can only communicate by sending messages, and some nodes may fail. For example, whether a particular seat has been sold or not, whether it has been sold to Zhang San or Li Si, etc., the system needs to reach a consensus before it can continue to execute.

Leslie Lamport, a pioneer of distributed systems and a famous Turing Award winner, proposed the foundation of modern consensus algorithms in 1990 - the Paxos algorithm. The reason why Lamport used the name Paxos is very interesting. Paxos was originally a small island with a long history in the Ionian Sea of ​​Greece. Lamport imagined that archaeologists discovered that there was a "part-time parliament" on the island in ancient times. Members of parliament voted on bills through messengers, but the messengers were unreliable, and the messages might not be delivered or delayed. In addition, the members of parliament themselves might not come to the meeting. In this case, how could the members of parliament reach a consensus on a bill? In the paper, Lamport used this fictional parliament on the island of Paxos as a framework, proposed an algorithm for achieving consensus under unreliable communication, and gave a rigorous mathematical proof. In 1990, Lamport submitted the paper to ACM Transactions on Computer Systems. The reviewer said that the paper was interesting, but it did not seem very important, and suggested removing the part about the Paxos story. Lamport said that the reviewer had no sense of humor at all and refused to make any changes to the paper. Later, Butler Lampson, another pioneer of distributed systems, read the paper and published their own proofs together with Nancy Lynch and other field leaders. At this time, Lamport considered publishing the paper again. Finally, with the promotion of a group of peers, the paper was published in 1998 and has now become the cornerstone of distributed systems.

Distributed systems pioneer Leslie Lamport 丨 Image source: wiki

Let's take the ticket selling system as an example to briefly describe the idea of ​​the Paxos algorithm and how it can reach consensus even when a node fails. For simplicity, assume that there are only three servers (nodes; three nodes are the minimum number required to demonstrate the Paxos algorithm) in the system and only one ticket is sold (selling multiple tickets can also be understood as the process of repeatedly selling a ticket). In addition, we also need to briefly describe the assumptions of the algorithm.

First, the Paxos algorithm assumes that if a node fails, it will completely stop responding, and will not continue to send erroneous messages on the network to interfere with the system. After it is repaired, it will return to the system and continue to respond. This type of failure is called fail-stop, which means that it stops after failure. Secondly, Paxos is an algorithm based on majority voting, which means that it is considered a consensus only if the majority of nodes vote in favor. Paxos requires 2m+1 nodes to accommodate the failure of m nodes. In other words, to be able to accommodate the failure of 1 node, the system needs to have at least 3 nodes (the other two are running normally). If more than half of the nodes fail, the Paxos algorithm will not function properly.

Now we assign a global serial number to these three servers to distinguish them: node 1, node 2, and node 3. The Paxos algorithm assigns a role to each node. Here, we assume that node 1 is both a proposer and an acceptor; nodes 2 and 3 are acceptors, which only accept but do not propose. Now node 1 has received a ticket purchase request from Zhang San, and it starts the first step of the algorithm: PREPARE-PROMISE.

Proposer Node 1 will first assign a unique serial number (proposal number) to its proposal (i.e., selling tickets to Zhang San). All proposals in the system will have their own unique serial numbers. A simple implementation method is as follows: each node maintains a counter with an initial value of 0. Each time it proposes a new proposal, the counter is incremented by 1. The serial number of the new proposal is set to a decimal consisting of the counter value and the global ID of the node, with a decimal point between the two, i.e., {counter}.{ID}. For example, the serial number of the first proposal of Node 1 is 1.1, and the serial number of the second proposal is 2.1. Similarly, the serial number of the first proposal of Node 2 is 1.2, and the serial number of its second proposal is 2.2, and so on. According to this serial number design, when Proposer Node 1 receives Zhang San's request, it will first send a PREAPRE message to all other nodes and attach the serial number 1.1 of the proposal, which is written as PREPARE(1.1) here.

The recipients of the proposal respond according to the following logic:

1. Check the proposal sequence number attached to the received PREPARE message.

2. Compare the received proposal number with the local max_id. If it is larger, update the local max_id to the received proposal number and return a PROMISE message, which is equivalent to telling the proposer: I received your message, your proposal number is currently the largest, prepare to propose, and I promise not to accept proposals with a smaller number than yours.

3. If the received proposal number is smaller than its local max_id, the recipient will not respond, or will respond with a fail message, telling the proposer that your proposal has failed.

If the proposer (node ​​1) receives a PROMISE message from the majority of acceptors (including itself), it knows that everyone is ready to accept its proposal. If it does not receive a majority response, or receives a fail message, the proposer can only give up the proposal in this round. It can increase its local counter by 1, and then propose a new round of proposals again (since the counter is increased by 1, the proposal number will also be increased by 1) and try again. When node 1 receives the PROMISE message from the majority of nodes, it enters the second step: PROPOSE-ACCEPT.

In the second step, node 1 will send a PROPOSE message with the proposal number and the specific value. The value here is what everyone wants to reach a consensus on. In the example of buying a ticket in this article, its content is "Zhang San", which means the ticket is sold to Zhang San. So the message sent by node 1 is as follows:

PROPOSE(1.1, "Zhang San")

The recipients of the message now have to make a decision whether to accept the proposal. Their logic is as follows:

1. If the proposal number in the PROPOSE message is still the largest one I have received so far (i.e. compared with my own max_id), then accept the proposal and return an ACCEPTED message;

2. Otherwise, no message is returned, or a fail message is returned to tell the proposer that the proposal has failed.

If the proposer receives ACCEPTED messages from the majority of nodes, it knows that consensus has been reached. Assuming that both No. 2 and No. 3 have received the PROPOSE message and returned the ACCEPTED message, all nodes have reached a consensus on the state of "the ticket is sold to Zhang San".

In summary, reaching consensus here takes two steps. The goal of the first step is to obtain the consent of the majority, which is equivalent to the proposer shouting to everyone: I am going to modify the data, do you agree or not? Only after obtaining the consent of the majority, will the second step be carried out - the proposer actually sends the value to be proposed.

Imagine if the algorithm skips the first step and directly sends the proposed value, different recipients may receive values ​​from different proposers. At this time, because there is no prior consent from the majority, the recipients do not know whether the value they received represents the majority opinion. There may be multiple subgroups in the system, each with their own value, and there will be no global consensus.

Complete Paxos algorithm logic

So far, the algorithm has been running fine, now let's look at some more complex situations.

Assume that not only node 1 is the proposer, but node 2 also becomes a proposer because it receives Li Si’s request (note that all nodes are acceptors). Now there are two different proposers in the system, and the messages they send may be intertwined in any way.

Assume that node 3 may have received a PREPARE message from node 1 (Zhang San buys tickets), that is, PREPARE (1.1), and returned a PROMISE. At this time, it received a PREPARE message from node 2 (Li Si buys tickets), that is, PREPARE (1.2). Because the proposal number 1.2 is greater than 1.1, it will return PROMISE to node 2 and update its max_id to 1.2. Note that node 1 will continue to send a PROPOSE message in the second step, PROPOSE (1.1, "Zhang San"), but node 3 will no longer accept its proposal at this time, because now for it, 1.2 is an updated proposal. It will only accept the PROPOSE message from node 2.

Consider another situation. Assume that Li Si's operation is a little slower than Zhang San. When node 2 becomes the proposer and sends PREPARE (1.2), node 3 has already accepted node 1's proposal (proposal number is 1.1), that is, the ACCEPTED message has been sent. At this time, node 2 has not received the PREPARE message from node 1 for various reasons, and is completely unaware that node 1 and node 3 have reached a consensus (the ticket is sold to Zhang San). Then according to the Paxos algorithm, when node 3 receives the PREPARE(1.2) message from node 2, since 1.2 is the largest proposal number that node 3 has ever seen, it will indeed return a PROMISE message to node 2. However, since node 3 has already accepted the previous proposal 1.1, the PROMISE message it returns will include the sequence number and value of the previously accepted proposal, i.e. PROMISE(1.1, "Zhang San"), telling node 2: I have received your proposal number, and it is indeed the latest proposal, but I have previously accepted the proposal with sequence number 1.1, and its content is "Zhang San". When node 2 receives the message and learns that the ticket has been sold, according to the Paxos algorithm, node 2 must change the value it wants to propose to "Zhang San" and then continue to send PROPOSE messages, so all nodes still reach a consensus.

Finally, the result seen by Li Si on the client is: the tickets are sold out. In fact, the proposer may receive multiple PROMISE messages with previously accepted values. It will select the value corresponding to the largest proposal number among all PROMISEs as the value to be proposed. If there is no PROMISE message with previously accepted proposal information, the proposer will continue to use the value it originally wanted to propose. The complete logic of the updated acceptor and proposer is shown in the following figure.

PREPARE-PROMISE process.

This is the complete Paxos algorithm. Finally, let's briefly consider the situation of network disconnection or node failure to see how Paxos can still run correctly under failure conditions.

Paxos under network or node failure

Both the proposer and the acceptor have the possibility of downtime. When the acceptor is down, it actually has little impact on the operation of the system, which is the advantage of the distributed system: even if some nodes do not respond to the PREPARE message or PROPOSE message, as long as the majority of nodes are still online, the system can still respond, and the proposer can still get the majority's reply, so the algorithm runs. And when the downed nodes come back to life, they will eventually learn about the consensus they missed through the PROMISE message sent by other nodes with the previously accepted proposal information, and update it locally.

What if the proposer (such as node 1) goes down? There are three situations:

1. If it crashes before sending the PREPARE message, it is equivalent to nothing happening in the system. Other nodes will become new proposers when they receive the user's request;

2. If the proposer crashes after sending the PREPARE message and has not yet sent the PROPOSE, as we just said, its proposal will be replaced by the later updated PREPARE (sent by the new proposer);

3. If the proposer has completed the first step PREPARE-PROMISE and entered the second step, but crashed after sending PROPOSE messages to some nodes, for example, node 1 crashed after sending PROPOSE to node 3 and did not have time to send it to node 2; then its proposal will be accepted by node 3, and node 2 will eventually learn about the consensus reached by nodes 1 and 3. Because node 2 will become the proposer at some point, it will eventually receive the PROMISE message returned by node 3 with the previously accepted proposal information, and update its local information accordingly, thus maintaining consistency with nodes 1 and 3.

So let’s get back to the issue of grabbing tickets. When we send a ticket purchase request from the client, it will interact with the complex distributed system behind it. If you fail to grab a ticket, it is not necessarily because your hands are not fast enough. It may also be due to network delays, server crashes, or the operation of the system algorithm itself.

Conclusion

As the cornerstone of modern computer systems, distributed systems can support high-load and high-concurrency scenarios such as 12306 ticket purchase. This article discusses some basic concepts and technical implementations of consistency and fault tolerance in distributed systems. In fact, the application of distributed systems is not just online shopping. In the field of encryption, distributed systems provide basic support for blockchain technology to ensure data security and consistency; in the field of scientific computing, distributed systems are also used to solve larger-scale problems. These fields all show that distributed systems play an indispensable role in our daily lives and technological development. Finally, the Spring Festival is coming soon, I wish you all: Happy Spring Festival and a happy family!

Note: The cover image of this article comes from the copyright library. Reprinting and using it may cause copyright disputes.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.