The foreword 0.

This paper records the author’s learning and understanding of blockchain consensus algorithm Paxos bit by bit, the article is quite long, need patience to carefully consider, the author is also struggling for a weekend to have a little preliminary understanding of this, if there is a question, please feel free to correct!

1. The initial is the basis for reading the follow-up content of this article. There is not much conceptual description. But I think there are excellent posts to provide reference for understanding. The basic understanding of Paxos above is the basis of 2. Code design and 3. Field flow!

1. The first

Relevant concepts

The Paxos problem is a Consensus problem in distributed systems where there are faults but no corrupt nodes (i.e., messages may be lost or repeated, but no error messages).

Paxos was originally named after Leslie Lamport’s story model of Paxon Island. The background of the story is how judges on the ancient Greek island of Paxon voted on a motion in a hall and reached a unified result. Notes are passed between them by attendants, but the judge may leave or enter the hall, and attendants may slacker off to sleep.

Paxos is the first proven consensus algorithm based on two-phase commit and extended. As the originator of modern consensus algorithm design, he is famous for the complexity of the original paper (the algorithm itself is not complex). Nodes are divided into three types in the algorithm:

• (a) a proposer (a proposer) The client usually plays this role;

• Acceptor: Acceptor is responsible for voting proposals. This role is often played by the server; It generally requires at least three with an odd number of nodes, because Paxos ultimately produces a proposal that most decision makers agree on.

• Learner: is informed of the closing result and agrees with it, and does not participate in the voting process. It can be a client or a server.

Two stages of paXOS algorithm

• A Proposer selects a proposal number N and sends a prepare request numbered N to more than half of the acceptor’s children. 2. If an Acceptor receives a prepare message with a proposal number n greater than the number of prepare requests it has responded to, it sends the proposal with the largest number it approved last time to the Proposer. And promise not to respond to proposals less than N;

• 1. When a Proposer receives a prepare response from more than half of the Acceptors, it enters the approval phase. It sends an Accept request to the Acceptors that responded to the PREPARE request, including the number N and the value determined by the prepare phase. The value here is the value of the proposal with the largest number of all responses (it is free to determine the value if no value has been accepted according to the prepare). 2. An Acceptor accepts an accept request once it receives it without breaching its commitments to other proposers. If an acceptor receives an accept request for proposal N, it can accept the proposal as long as the acceptor has not responded to a prepare request with a number greater than N.

His shan zhishi

The Paxos algorithm sounds a little hard to understand for the first time, and here’s a post I think is good. Post it out for reference:

• Describe the Paxos algorithm through the real world
• The paXOS algorithm is understood by examples
• Principle and derivation of Paxos algorithm

In addition, wiki’s description of Paxos is a good and authoritative reference.

With the above understanding of Paxos algorithm, we can proceed to the next step: programming to implement Paxos algorithm by ourselves.

2. Code practice

The process to understand

The two roles at the heart of the Paxos algorithm are Proposer and Acceptor, and the algorithm architecture must be designed around those two.

Proposer behavior analysis

• 1.0 Send a proposal to all acceptors;

• 2.0 If a reject message is received, try to resend the rejected proposal.

• 2.1 If you receive an Agree from an Acceptor, use a agreeCount flag to count the number of acceptors you have accepted. When agreeCount exceeds half the total number of acceptors, a majority of acceptors have committed to accept the proposal and need to change their proposal status to agreed accepted. And notify the other proposers that I have received a majority of acceptors to accept the proposal.

• 3.0 When a proposal is in a promised acceptance state, a Proposer needs to send an additional confirmation request to the Acceptor set to Accept the proposal.

• 3.1 An Acceptor receives an Accept response from an Acceptor after an Accept request is received. If an Accept message is received, an acceptCount is used to count the number of acceptors who have accepted an Accept request. Also, if the acceptCount exceeds 50%, the majority of acceptors have accepted the proposal, and the proposal status needs to be changed from the promised acceptance state to the accepted state. At the same time, I notify the other proposers that I have accepted the proposal with a majority of acceptors.

• 1,2 belong to the Prepare phase of the Paxos algorithm, and 3 belongs to the Accept phase.

Acceptor behavior analysis

• 1.0 After an Acceptor receives an Acceptor proposal, it determines whether the proposed version is larger than the saved proposal version.

• 1.0 if it is less than that, it says it has promised the Proposer another Proposer, and sends a reject message saying it has rejected any promise to the Proposer.

• 1.1 If not, it replaces its saved version number with the Proposer and sends the current Proposer an Agree saying it will accept its proposal. At the same time, set its status to that it has given a Proposer a commitment (agree).

• 2.0 An Acceptor receives an Accept request for a Proposer numbered N, if the Acceptor has not previously committed to any other Proposer numbered M(M>N). At the same time, it sets its status to accept a Proposer, and notifies all proposers of that message.

• 1 is in the Prepare phase and 2 is in the Accept phase of Paxos.

The above behavior analysis for this Paxos algorithm programming actual combat!!

The design of the class

Paxos algorithm is to solve the problem of distributed system consistency, we simulate multiple nodes on a computer through the port number.

Needless to say, we need a Proposer class and an Acceptor class, respectively.

PaxoProposer class

• A Proposer sends an offer to an Acceptor, so it has to know all of its acceptors and sometimes with other proposers, so it needs to know all of its proposers as well.

• Basic start end interface (start, stop)

• A getQuorumCount is required to determine whether the proposal has been accepted by the majority of acceptors.

• Notifyproposers are required when an offer is promised or finally accepted

• Send a message (offer or Accept request) to an Acceptor(sendMsg); Receive a message from an Acceptor (recvMsg)

• For debugging purposes, we might want to know the getHistory of the request proposals throughout the process.

• GetNumAccepted Number of Acceptor acceptances

• If we look at the Paxos algorithm, we find that if there are two proposers with increasing numbers, they end up in an infinite loop where the Paxos algorithm is not active. So, the common practice is to take a master Proposer as the leader, and only the leader can make a proposal (setPrimary).

• A difficulty with the Proposer class is the various state transitions and processing of the corresponding data after a proposal is made. During the whole process from the proposal to the proposal is accepted, the state of the proposal is constantly changing, but eventually it will reach a termination state. For handling this situation, state machine __ is bound to be a good choice. So because it’s a little bit complicated here we’re abstracting the Proposer functionality separately into a Proposer protocol class __PaxoProposerProtocol.

– Since each node sends and receives messages in parallel, thread is required to detect messages. The HeartbeatListener listens for the message, and the HeartbeatSender sends the message.

"""@author: chaors @file: PaxoProposer. Py @time: 2018/04/14 10:50 @desc: proposer"""

class PaxoProposer:

    # Heartbeat monitor class
    class HeartbeatListener(threading.Thread):
        pass
    # Timer send class
    class HeartbeatSender(threading.Thread):
        pass
        

    # initialization
    def __init__(self, port, proposers=None, acceptors=None):
        pass
    # start
    def start(self):
        pass

    # stop
    def stop(self):
        pass

    # Set whether to be a leader
    def setPrimary(self, isPrimary):
        pass

    # Get decision-makers who support all proposers
    def getGroup(self):
        pass

    # Get all proposers
    def getProposers(self):
        pass

    # Get all decision makers
    def getAcceptors(self):
        pass

    The proposal must be accepted or accepted only if it is accepted by at least half of acceptors
    def getQuorumCount(self):
        pass

    Get local record data
    def getInstanceValue(self, instanceID):
        pass

    Get history
    def getHistory(self):
        pass

    # Number of proposed consents obtained
    def getNumAccepted(self):
        pass


    # Notify other proposers
    def notifyProposer(self, protocol, msg):
        pass


    # New proposal
    def newProposal(self, value, instance=None):
        pass

    # send a message
    def sendMsg(self, msg):
        pass

    # Receive message
    def recvMsg(self, msg):
        pass
Copy the code

PaxoProposerProtocol class

It is used to submit a proposal and to handle various states after submitting the proposal.

• States are defined to represent the various states of the current Proposoer proposal

• Make a proposal

• State machine Processing (doTranition)

"""@author: chaors @file: paxoproposerProtocol. py @time: 2018/04/14 10:50 @desc: Proposer's protocol"""

class PaxoProposerProtocol:
    # constants
    STATE_UNDEFIND = -1  The proposed agreement is undefined
    STATE_PROPOSED = 0  # Offer type
    STATE_REJECTED = 1  The proposal was rejected
    STATE_AGREED = 2    Obtain the protocol status after most Acceptor commitments are accepted during the Prepare phase
    STATE_ACCEPTED = 3  # The offer is accepted
    STATE_UNACCEPTED = 4  # The offer was not rejected

    def __init__(self, proposer):
        pass

    # Make a proposal
    def propose(self, value, pID, instanceID):
        pass

    State transitions run according to the state machine
    def doTranition(self, msg):
        pass
Copy the code

PaxoAcceptor class

Proposer, responding to proposals and Accept requests.

• Interfaces similar to Proposer are not described here.

• Request to compare the version of the Proposer that it sent (getHighestProposal)

"""@author: chaors @file: paxoacceptor. py @time: 2018/04/14 10:50 @desc: decision maker"""

class PaxoAcceptor:
    def __init__(self, port, proposers):
        pass

    # start
    def start(self):
        pass

    # stop
    def stop(self):
        pass

    # failure
    def fail(self):
        pass

    # recovery
    def recover(self):
        pass

    # send a message
    def sendMsg(self, msg):
        pass

    # Receive message
    def recvMsg(self, msg):
        pass


    Notify the client
    def notifyClient(self, protocol, msg):
        pass


    Get local record data
    def getInstanceValue(self, instanceID):
        pass

    # Get the highest consent suggestions
    def getHighestProposal(self, instanceID):
        pass
Copy the code

PaxoAcceptorProtocol class

The Proposer protocol, used to process proposals made with a Proposer, also uses a state machine to process its own states.

"""@author: chaors @file: paxoacceptorProtocol. py @time: 2018/04/14 10:50@desc: Decision maker protocol"""

from Message import Message  Protocol depends on messages

class PaxoAcceptorProtocol:
    # constants
    STATE_UNDEFIND = -1  The protocol is not defined
    STATE_PROPOSAL_RECEIVED = 0  # Receive a message
    STATE_PROPOSAL_REJECTED = 1  # Reject the link, the network is not possible
    STATE_PROPOSAL_AGREED = 2  # promise to accept the Proposer's PROPOSED request for Proposer
    STATE_PROPOSAL_ACCEPTED = 3  # Accept the Accept request for Proposer from this agreement
    STATE_PROPOSAL_UNACCEPTED = 4  # reject request

    def __init__(self, client):
        pass

    # Received proposal
    def recvProposal(self, msg):
        pass


    # transition
    def doTranition(self, msg):
        pass

    Notify the client
    def notifyClient(self, msg):
        pass
Copy the code

The Message class

It has roles for Proposer and Acceptor, but it needs a message class to pass between them. The message is as follows:

• A Proposer sends a request for proposals
• A Proposer sends an Accept request
• A rejection of an Acceptor’s request for an offer
• An Acceptor’s commitment to a proposal request
• An Acceptor accepts an Accept request
• An Acceptor rejects an Accept request
• Proposer received from an external Client
• As a reply message to a message
• Timed heartbeat information, used to synchronize proposals

"""@author: chaors @file: message. py @time: 2018/04/14 09:31 @desc: Message passing class"""

class Message:
    # constants
    MSG_ACCEPTOR_AGREE = 0  Acceptor specifies a commitment to a proposal request
    MSG_ACCEPTOR_ACCEPT = 1  Acceptor Accepts an Accept request
    MSG_ACCEPTOR_REJECT = 2  A rejection of a proposal request
    MSG_ACCEPTOR_UNACCEPT = 3  Acceptor Indicates that an Accept request is not accepted
    MSG_ACCEPT = 4  #Proposer sends an Accept request
    MSG_PROPOSE = 5  #Proposer requests for proposals
    MSG_EXT_PROPOSE = 6  # Proposer to which the Client sends a Proposer
    MSG_HEARTBEAT = 7  # Timed heartbeat message, used to synchronize proposals

    def __init__(self, cmd=None):  Message initialization has a state
        pass
    
    # Reply message to a message
    def copyAsReply(self, msg):
        pass
Copy the code

InstanceRecord class

Proposals are abstracted into protocols, and a Proposer may attempt to submit protocol information (including proposals) more than once before the system reaches a consensus. A Proposer and Acceptor both need to keep a record of all proposals between them, so each has an array of InstanceRecord instances.

With a Proposer, an array of InstanceRecord instances holds all the records of proposals submitted and updates the record status (including protocol and record values) as the proposal status changes.

For acceptors, the InstanceRecord instance array holds the Proposer requests received by acceptors, updated as the version of the proposal changes. An Acceptor accepts an agreement only if the proposed version is larger than the version specified in InstanceRecord. An Acceptor accepts a proposal if the version of the current accept request is greater than that of the previously committed proposal.

• Protocols, containing protocols for each request
• Highest version, the highest version of all currently submitted requests (highestID)
• Record value, the value of the request

"""@author: chaors @File: InstanceRecord. Py @time: 2018/04/14 10:31 @desc: Local record class, record agreement between decision maker and proposer"""

import threading, socket, pickle, queue,random
# InstanceRecord Protocol between the local record class, decision maker, and proposer
from PaxoProposerProtocol import PaxoProposerProtocol

class InstanceRecord():
    def __init__(self):
        self.protocols = {}  # Protocol dictionary
        self.highestID = (-1, -1)  # Highest version (proposed version, port number)
        self.value = None  # offer value

    # add protocol
    def addProtocol(self, protocol):
        self.protocols[protocol.proposalID] = protocol
        If a Proposer with a larger port is led, it takes a larger version number with the same port number
        if protocol.proposalID[1] > self.highestID[1] or \
                (protocol.proposalID[1] == self.highestID[1] \
                 and protocol.proposalID[0] > self.highestID[0]):
            self.highestID = protocol.proposalID

    # fetch protocol
    def getProtocol(self, protocolID):

        return self.protocols[protocolID]

    # Cleanup protocol
    def cleanProtocols(self):
        keys = self.protocols.keys()  # get all you can
        # traversal delete protocol
        for key in keys:
            protocol = self.protocols[key]
            if protocol.state == PaxoProposerProtocol.STATE_ACCEPTED:
                print("Deleting protocol")
                del self.protocols[key] # Delete protocol
Copy the code

MessagePump class

The structure of the message is there, but how is it passed between nodes (Proposer and Acceptor)? Here we encapsulate a network class that delivers messages based on sockets. Here we need a thread to receive the message, and we’re building a helper class to receive the message.

This is just not the key point of the Paxos algorithm, so I won’t repeat it. Go straight to the code.

"""@author: chaors @file: messagepump.py @time: 2018/04/14 09:46 @desc: Socket based message delivery, encapsulation network class message delivery"""

import threading  # thread
import pickle  # object serialization
import socket  # Network information transmission
import queue  # queue

class MessagePump(threading.Thread):
    A helper class for passing messages
    class MPHelper(threading.Thread):
        def __init__(self, owner):
            self.owner = owner  Owner of the object passing the message

            threading.Thread.__init__(self)  # Parent class initialization

        def run(self):  # run
            while not self.owner.abort:  As long as the owner thread is not terminated
                try:
                    # return binary data, address
                    (bytes, addr) = self.owner.socket.recvfrom(2048)  # Receive message
                    msg = pickle.loads(bytes)  Read binary into message
                    msg.source = addr[1]  Fetch the returned address
                    self.owner.queue.put(msg)  The message is queued

                except Exception as e:  Abnormal #
                    print(e)

    def __init__(self, owner, port, timeout=2):
        Basic parameter initialization
        self.owner = owner  # owner
        self.timeout = 2  # timeout
        self.port = port  # Network interface

        Initialize network communication
        self.socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)  # UDP communication
        self.socket.setsockopt(socket.SOL_SOCKET, socket.SO_RCVBUF, 200000)  # Communication parameters
        self.socket.bind(("localhost", port))  # socket binding
        self.socket.settimeout(timeout)  # set timeout

        self.queue = queue.Queue()  # queue
        self.helper = MessagePump.MPHelper(self)  The utility class that receives the message

        threading.Thread.__init__(self)  # Parent class initialization
        self.abort = False  The default does not terminate

    Run the main thread
    def run(self):
        self.helper.start()  # start the thread for receiving messages
        while not self.abort:  As long as it is not terminated
            msg = self.waitForMsg()  Block waiting for messages
            self.owner.recvMsg(msg)  # Receive message

    # Waiting for news
    def waitForMsg(self):
        try:
            msg = self.queue.get(True, 3)  Wait at most 3s to fetch messages from the queue

            return msg
        except Exception as e:
            print(e)

            return None

    # send a message
    def sendMsg(self, msg):
        bytes = pickle.dumps(msg)  Convert the message to binary
        addr = ("localhost", msg.to)
        self.socket.sendto(bytes, addr)  Send a message to the address

        return True

    Set the status to give up
    def doAbort(self):
        self.abort = True
Copy the code

Paxos_MainTest Tests the Paxos algorithm

"""@author: chaors @file: paxo_testmain. py @time: 2018/04/14 17:50 @desc: Paxos algorithm test Case"""

import threading, socket, pickle, queue,random
import time

from MessagePump import MessagePump
from Message import Message
from InstanceRecord import InstanceRecord
from PaxoProposer import PaxoProposer
from PaxoProposerProtocol import PaxoProposerProtocol
from PaxoAcceptorProtocol import PaxoAcceptorProtocol
from PaxoAcceptor import PaxoAcceptor

if __name__ == '__main__':
    The number # Acceptor
    numclients = 5
    # instantiate decision maker array, decision maker node port number 65520-65525
    acceptors = [PaxoAcceptor(port, [56321, 56322]) for port in range(65520, 65520 + numclients)]

    Acceptors (port number 56321,56322) are acceptors
    proposer1 = PaxoProposer(56321, [56321, 56322], [acceptor.port for acceptor in acceptors])
    proposer2 = PaxoProposer(56322, [56321, 56322], [acceptor.port for acceptor in acceptors])

    # Initiate the proposer proposal process
    proposer1.start()
    proposer1.setPrimary(True)
    proposer2.setPrimary(True)
    proposer2.start()

    Start the decision making process for decision makers
    for acceptor in acceptors:
        acceptor.start()

    # Simulate the breakdown of two nodes in the network
    acceptors[0].fail()
    acceptors[1].fail()

    Send proposals to decision makers using Socket mechanisms
    s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    start = time.time()
    for i in range(1000):
        m = Message(Message.MSG_EXT_PROPOSE)
        m.value = 0 + i
        m.to = 56322  
        bytes = pickle.dumps(m)
        s.sendto(bytes, ("localhost", m.to))

        # if i == 2 or i == 30:
        # print(leader2.getInstanceValue(1))

    End the proposal process when the proposal is accepted by 999 decision makers
    while proposer1.getNumAccepted() < 999:
        print(u"Sleep for 1 second -- accepted: %d" % proposer1.getNumAccepted())
        time.sleep(1)
    end = time.time()

    print(u"Sleep for 10 seconds.")
    time.sleep(10)
    print(u"End the leader.")
    proposer1.stop()
    proposer2.stop()
    print(u"End client")
    for acceptor in acceptors:
        acceptor.stop()

    print(u"Leader 1 History: %s" % proposer1.getHistory())
    print(u"Leaders 2 History: %s" % proposer2.getHistory())
    print(u"It took %d seconds." % (end - start))
Copy the code

3. Further understand the processing logic of Paox algorithm through the code

The basic code architecture has been completed above, the detailed source code will be uploaded to Github later. Next, we use a simple test case to further understand the processing logic of the Paxos algorithm at the code level.

We ran the paxo_testMain code, and I made breakpoints at key steps beforehand. In this way, the two stages of Paxos algorithm can be seen completely from the point of view of the code, and the code processing logic of each step can be intuitively observed.

!!!!!!!!! Reading Instructions:

#####1.x corresponds to the Prepare phase of the Paxos algorithm #####2.x corresponds to the Commit phase of the Paxos algorithm

Cut to the code

• 1.0 [start-1.0]Proposer receives a message with the type of a proposal. First determine whether you are a leader, if you are creating an agreement

• Proposer initiates a proposal request with its own PaxoProposerProtocol instance

• 1.2 [start-1.2] An Acceptor received a proposal message. The proposal is then processed with an AcceptorProtocol instance.

• An AcceptorProtocol receives a proposal and determines whether the version of the proposal responds to the Proposer with a commitment to accept or reject a message

• A Proposer receives a message with an Acceptor commitment (MSG_ACCEPTOR_AGREE) of type. If it is not a Proposer that ultimately accepts the proposal, it is forwarded to the ProposerPropotocal state machine for processing.

• [start – 1.5] and [2.0] start –

–[start– 1.5] ProPOSERThe proPOtocal state machine function receives an MSG_ACCEPTOR_AGREE message, which indicates that an Acceptor has been added to accept my request.

— [start– 2.0_1] The code is executed until the number of promised proposers exceeds half, indicating that the Prepare phase is basically over. At this point, the protocol status is updated to STATE_AGREED. A Proposer at this time sends an Accept request to the Acceptor collection asking acceptors to confirm their promise.

At the same time, it broadcasts this message to the other proposers so that the other proposers know which proposal in the Prepare phase has received the most commitments. Thus, during the Commit phase, they may change the proposal to make the system more consistent as quickly as possible.

• 2.1[start-2.1] An Acceptor receives a message of the type numbered Proposer Accept. Process the message with AcceptorPropotal.

• 2.2 to 2.2] [start — –

  — [start– 2._1] AcceptorPropotal Receives a Proposer with an Accept request. A Proposer is accepted if and only if the maximum version number promised by an Acceptor is less than the version number of the request. If the protocol status is STATE_PROPOSAL_AGREED, then any Proposer broadcast a message confirming that it has accepted the Proposer.

  — [start-2.2_2] An Acceptor notifies an Acceptor to update the InstanceRecord value so that an Acceptor has finally accepted an offer.

• (a) a Proposer receives a message with the type MSG_ACCEPTOR_ACCEPT and updates its InstanceRecord(a new record, an additional protocol, and so on) with that message. And passes the message to the ProposerProtocol state machine for processing.

• 2.4 to 2.4] [start — –

  [start– 2.4_1] — ProposerProtocol receives a final acceptance message from an Acceptor (MSG_ACCEPTOR_ACCEPT) indicating that a new Acceptor has finally accepted my proposal. However, the protocol state is still STATE_AGREED because a proposal must be accepted by more than half of Acceptor nodes before it is accepted by the system.

  Code under the [start-2.4_2] STATE_AGREED condition is executed until more than half of acceptors accept the proposal. At this point, the protocol state is updated from the STATE_AGREED state to the final system accepted state (STATE_ACCEPTED). Finally, the current Proposer updates its InstanceRecord record. Of course, there is a possibility that it is rejected by more than half of the other Proposer nodes, and then one of the proposals is accepted.

• Proposer updates the InstanceRecord record and attempts to repropose if the protocol is ultimately rejected by a majority of acceptors (step back to 1.1).

# To sum up the above, we have a deeper understanding of PAxos algorithm from the code level. I want to understand PAxos algorithm in reverse according to the code, is bound to have a deeper impression.

At first I heard that Paxos was confused, but it took a weekend of fighting to realize it. I am still in the process of learning blockchain, so I wrote this post to record my learning process. The mian.

Source code point here

Code farmers:

Choice for farmers

Please count your numbers well

One yard is not adjustable

Why the world

The Internet disrupts the world, blockchain disrupts the Internet!

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — 20180416 00:16