What is a Distributed Algorithm?

A distributed algorithm means that when the multiply-add function is completed, the operation result generated by each corresponding bit of each input data is added in advance to form a corresponding partial product, and then each part is accumulated to form a final result.

In simple terms, distributed computing is to divide a large computing task into multiple small computing tasks and distribute them to several machines for calculation, and then summarize the results. The purpose is to analyze and calculate massive data, analyze abnormal signals (alien civilization) from the massive historical signals monitored by radar, and calculate the consumption habits of various regions in real time on Taobao Double Eleven.

The initial solution for mass computing was to improve the performance of single-machine computing, such as mainframes. Later, due to the explosive growth of data, but single-machine performance could not keep up, there was a compromise solution such as distributed computing. Because once the calculation is split, the problems will become very complicated, and problems such as consistency, data integrity, communication, disaster tolerance, and task scheduling also come.

For example, the product requires 100G users to purchase data from the database, and analyzes the amount of consumption habits in various regions. If there is no time requirement, the programmer Xiaoming writes a corresponding business processing service program, deploys it to the server, and lets it run slowly. Xiaoming expects to finish processing in 10 hours. The latter product was too slow, so Xiaoming tried to speed it up to 3 hours.
There are many similar requirements in ordinary development. To sum up, the amount of data is large, and the single computer calculation is slow. If on

Paxos Distributed algorithm Paxos algorithm

1) Problem description

There is such a difficult problem in the distribution. The client sends a series of data update messages to the server in a distributed cluster. Because the server nodes in the distributed cluster synchronize data with each other, the client is finished running. After a series of message instructions, the data of each server node should be consistent, but due to network or other reasons, the sequence of the messages received by each server node may be inconsistent, resulting in inconsistent data at each node.

2) the algorithm itself

The algorithm itself is not fully described and deduced. There are a lot of materials on the Internet to do this, but I feel Leslie Lamport (the founder of the paxos algorithm) after studying this person. Paxos Made Simple is the best document to learn paxos. It does not scare people with a bunch of formulas and mathematical symbols like most algorithm documents. It uses human language to make you understand what problems Paxos needs to solve. How was it resolved. Here is also an opportunity to attack those academic researchers. If you want others to recognize your results, you must first learn how to make most people happy to read your results. This document describing the Paxos algorithm is an example for us to learn.

Closer to home, through the various steps and constraints of the Paxos algorithm, it is actually a distributed election algorithm, the purpose of which is to pass elections in a bunch of messages, so that the receiver or performer of the message can reach an agreement and follow the same message Sequential execution. In fact, from the simplest point of view, in order to achieve the execution of the same sequence of instructions, it can be done serially, such as adding a FIFO queue in front of a distributed environment to receive all instructions, and then all service nodes follow the queue. The order to execute. This method can certainly solve the consistency problem, but it does not meet the distributed characteristics. What if the queue is down or overwhelmed? The cleverness of Paxos is that it allows each client to send instructions to the server without affecting each other, and everyone agrees on the election method. This method has distributed characteristics and better fault tolerance.

Speaking of this election algorithm itself, you can think of elections in the real world. Generally speaking, those with the most votes win, while Paxos algorithm wins with a higher serial number, and when the person who tries to submit the instruction is rejected The sequence number occupied by the instruction is not the highest), it will participate in the re-election in a better sequence, and through the continuous participation of each submitter, the purpose of selecting a sequence recognized by everyone is achieved. It is precisely because of this process of continuous participation in elections that Paxos provides three roles (proposer, acceptor, and learner) and two phases (accept and learn). The specific responsibilities of the three roles and the specific process of the two phases See Paxos Made Simple, another domestic buddy wrote a good PPT, and also described the running process of paxos through animation. But then again, don't get stuck in the details of the algorithm from the beginning. Think about the original intention of designing these game rules.

The biggest advantage of Paxos algorithm is that it has fewer restrictions. It allows the failure and repeated execution of various roles at various stages. This is also a common thing in a distributed environment. As long as everyone acts according to the rules, the algorithm itself guarantees Consistent results when errors occur.

3) Implementation of the algorithm

There are many versions of Paxos implementation, the most famous one is Google Chubby, but you can't see the source code. Open source implementation can be seen in libpaxos. In addition, ZooKeeper also solves data consistency problems based on paxos. You can also see if it implements paxos ^[1] .

Hash Distributed Algorithm Consistent Hash Algorithm

1) Problem description

Hash algorithm is often used to distribute the data in the distribution. It is very good when the data nodes do not change, but when the data nodes increase or decrease, due to the need to adjust the modules in the hash algorithm, all data must be distributed according to the new modules. Go to each node. If the amount of data is huge, such work is often difficult to complete. Consistent Hash algorithm is based on the optimization of Hash algorithm. The above problems are solved by some mapping rules.

2) the algorithm itself

In fact, in other design and development areas, we can also learn from the idea of consistent hashing. When a mapping or rule causes problems that are difficult to maintain, you can consider further abstracting these mappings or rules, and making the final data constant. Consistent hashing is actually changing the previous point mapping to section mapping so that other data nodes change as little as possible after the data node changes. This idea is reflected in the storage problem of the operating system. For example, in order to use the storage space more optimally, the operating system distinguishes different latitudes such as segments and pages, and adds a lot of mapping rules. The purpose is to avoid the cost of physical changes through flexible rules.

3) Algorithm implementation

The consistent Hash algorithm itself is relatively simple, but there can be many improved versions according to the actual situation, and its purpose is nothing more than two points:

• Other nodes are affected as little as possible after node changes

• Data redistribution is as balanced as possible after node changes ^[2]