The challenges of distributed systems

In the previous article, we analyzed the business consistency technique of distributed systems, i.e., distributed transactions, whose result orientation is user-oriented. However, in our system, sometimes we also need to face the consistency requirements from higher levels such as software architecture, such as Redis sentinel mode and Zookeeper election process. The consistency they consider is more about reaching a consensus among service nodes. When a consensus is reached, it can be used as a guiding principle to carry out more collaborative operations.

Before we explore how to reach consensus, let’s examine the characteristics of distributed systems:

  • concurrent: Processes on different nodes can be executed at the same time, we need a coordination mechanism to complete the tasks of each stage.
  • Global clockIn a distributed system, it is difficult to maintain a global clock. There is no absolute time order between servers.
  • Fault impact: There is no system without faults. You need to consider the overall impact on the system and the fault tolerance capability provided by the system.
  • The messaging: Due to the complex environment of the network, the communication between nodes may arrive or partially arrive, may be transmitted within a known time range, or may be delayed indefinitely, which is not certain.

Thus, the challenges in reaching consensus in a distributed system lie in coordination, fault tolerance, and uncertain communication.

State replication

If we wanted to introduce a coordinator into a system, it would be very simple to introduce a stateful component to determine which business phase the system should be in. A stateful component is easy to implement, as long as it has persistence, like Mysql or MongoDB. However, given the importance of the coordinator, we often need to ensure that it is highly available, and to achieve this, we add a replication process to the state update process. For example, synchronizing updated values to other machines.

But do all machines need to be copied in place to complete this update process? Not necessarily. For example, Mysql synchronous replication, asynchronous replication, and semi-synchronous replication provide us with a variety of choices in terms of performance and data consistency. However, the higher the replication efficiency, the lower the data consistency.

Coordinators like us, with low update frequency and small data volume, tend to adopt the minority follows the majority strategy. As long as more than half of the synchronization nodes are synchronized, the write can be considered as successful. Log synchronization for Raft, this is how Message broadcast for Zookeeper is handled. In addition, in order to ensure the correctness of synchronization, an election mechanism will be introduced to allow the elected Leader node to process the synchronization results uniformly. When the Leader node fails or goes offline, the Leader node is re-elected based on certain rules (such as the latest submission level of logs) to ensure the normal operation of the system.

Fault handling

In the method reached consensus above, it is inevitable to consider the impact of the failure, and the corresponding failure types mainly have two kinds:

  • crashes: A node suddenly crashes and stops responding to other nodes
  • Byzantium lost: Nodes are untrusted and will respond to error messages to other nodes

For this type of failure, like Raft, Paxos, we can resolve it through elections. But problems like Byzantium’s defeat are more difficult to solve, because there are possible mutinous nodes that can push the system in the wrong direction to reach consensus, which is obviously not what we want. So we’ll see the following solution in blockchain:

  • PBFT (Practical Byzantine Fault Tolerance): Byzantine fault tolerance algorithm(Alliance/private chain uses this algorithm)
  • PoW (Proof of Work): Proof of work algorithm(Bitcoin and Ethereum use this algorithm.)

FLP is impossible

As for communication models between distributed systems, they can be generally divided into the following two types:

  • Synchronization: The time for the system to process messages is within the specified range. Once the time is exceeded, it is considered as failure.
  • Asynchrony: The system takes a variable amount of time to process a message and may or may not get a result.

Among them, under the asynchronous communication model, there is a famous FLP impossibility principle, namely:

There is no deterministic consensus algorithm that can solve the consistency problem in the minimal asynchronous model system with reliable network but allowing node failure (even if only one)

The PRINCIPLE of FLP impossibility tells us not to waste time designing consensus algorithms for arbitrary scenarios for asynchronous distributed systems. We should focus on a distributed system with constraints and termination conditions. If the algorithm we design meets the following two conditions as much as possible, our system will have a consensus output:

  • Activity: Each non-failure node will eventually decide to output a value, and if the node does not decide, the system will stop.
  • Security: All non-failing nodes will eventually output the same value, and if this is not achieved, consistency is not guaranteed.

Consensus building

Different algorithms describe the above conditions differently. Broadly speaking, consensus algorithms usually divide the following three roles:

  • Proposal is: Often referred to as a leader or coordinator
  • The recipient: Respond to the proposer’s proposal
  • Learners': Does not participate in the decision and learns the final value of the decision

After the role responsibilities are divided, we define a consensus algorithm through the following three steps:

Step 1 Election: When triggered by an external event, the leader proposes the next valid output value. Step 2 Vote: after receiving the leader’s proposed value, the non-failure node verifies it and proposes it as the next valid value. Step 3 Decision: According to the proposed results of valid values in each non-failure node, decide whether to adopt this value; Otherwise, restart Step 1

For the above steps, different consensus algorithms will have some differences, such as the definition of terms, the voting process, the determination criteria of valid values, etc.

application

Consensus in distributed systems needs to be achieved in an unreliable, untrusted network. Without Byzantine fault tolerance, our raft and ZooKeeper protocols are sufficient, and their applications are often on the Intranet, so internal nodes are trusted by default. If we are to reach a consensus among open online communities that contain malicious behavior, such as blockchains, then we have to address the improvement of three scenarios:

  • Rationalization: Participants choose the implementation of the agreement according to the strategy of maximizing benefits.
  • Altruistic: In the process of implementation, can consider the interests of the whole.
  • Byzantine fault tolerance: it can resist the malicious behavior of some nodes and ensure the normal operation of the system.

conclusion

The consensus-building process of distributed systems needs to be robust and secure, and its consensus-building mechanisms need to take into account Byzantine errors. The solution of the consensus problem makes our distributed system run more robust, and it is precisely because of the importance of consensus that today’s blockchain technology appears to be extra important!

reference

  • [1]consensus in distributed systems
  • [2] Let’s take a crack at understanding distributed consensus

Interested friends can search the public account “Read new technology”, pay attention to more pushed articles.

Thank you for your support!

Read new technology, read more new knowledge.