WPaxos: A Production‑Grade Java Implementation of the Paxos Consensus Algorithm – Design and Engineering Analysis

WPaxos is an open‑source, production‑grade Java implementation of the Paxos consensus algorithm released by 58.com, designed to solve data inconsistency and distributed consensus problems in high‑concurrency, high‑reliability systems.

Background : The article is the first in a series analyzing WPaxos source code, outlining the core Paxos algorithm and previewing upcoming modules such as storage parsing, fast data alignment, master election, and high‑availability use cases.

What is Paxos? Paxos, proposed by Leslie Lamport in 1990, is a message‑driven, fault‑tolerant consensus algorithm that ensures a distributed system can reach agreement on a proposal even under node crashes or network partitions. Basic Paxos involves three roles—Proposer, Acceptor, and Learner—and proceeds in two phases: Prepare and Accept.

Algorithm Analysis : The article examines several edge cases:

Network partitions (Figures 1‑2) where proposals may fail to obtain a majority and later be reconciled when connectivity is restored.

Proposal number conflicts (Figure 4) where duplicate proposal IDs are resolved by higher IDs winning, and global unique IDs are recommended.

Abnormal proposal conflicts (Figures 5‑7) illustrating why both Prepare and Accept phases are essential to avoid data divergence.

Algorithm liveness (Figure 8) showing how repeated conflicts can be mitigated with random back‑off or a single active proposer.

Engineering Optimizations in WPaxos :

Master election mechanism allowing a designated master to serialize proposals while still permitting other nodes to propose.

Skipping the Prepare phase when the previous proposal succeeded without any rejections, reducing RTT and disk writes from (2,2) to (1,1).

Proposal IDs composed of [ProposeID, NodeID] to guarantee global monotonic ordering.

Instance IDs to uniquely identify each committed value, ensuring strict monotonicity and preventing out‑of‑order execution.

Support for multi‑Paxos groups and batch commits for further performance gains.

Key Code Snippets :

public int newValue(byte[] value) {
    // Initialize new proposal value
    if (this.proposerState.getValue().length == 0) {
        this.proposerState.setValue(value);
    }
    // Determine whether to skip Prepare phase
    if (this.canSkipPrepare && !this.wasRejectBySomeone) {
        accept();
    } else {
        prepare(this.wasRejectBySomeone);
    }
    return 0;
}

public void prepare(boolean needNewBallot) {
    exitAccept();
    this.isPreparing = true;
    this.canSkipPrepare = false;
    this.wasRejectBySomeone = false;
    if (needNewBallot) {
        this.proposerState.newPrepare();
    }
    PaxosMsg paxosMsg = new PaxosMsg();
    paxosMsg.setMsgType(PaxosMsgType.paxosPrepare.getValue());
    // ... broadcast Prepare request ...
}

public void onAccept(PaxosMsg paxosMsg) {
    PaxosMsg reply = new PaxosMsg();
    BallotNumber ballot = new BallotNumber(paxosMsg.getProposalID(), paxosMsg.getNodeID());
    if (ballot.ge(this.acceptorState.getPromiseBallot())) {
        this.acceptorState.setAcceptedBallot(ballot);
        this.acceptorState.setAcceptedValue(paxosMsg.getValue());
        // persist state
    } else {
        reply.setRejectByPromiseID(this.acceptorState.getPromiseBallot().getProposalID());
    }
    sendMessage(paxosMsg.getNodeID(), reply);
}

Conclusion : By combining a clear explanation of Basic Paxos with practical engineering enhancements, WPaxos demonstrates how to build a high‑performance, reliable distributed consensus service. Readers are encouraged to explore the source code for deeper understanding or to adopt WPaxos in their own systems.