Discussion for: Tushar Chandra, Robert Griesemer, and Joshua Redstone, “Paxos Made Live: An Engineering Perspective” (invited talk, PODC 2007)

Paper overview

This paper addresses the challenges and lessons learned from implementing Paxos in a real-world system, specifically for a fault-tolerant database at Google. While Paxos is theoretically robust, its practical implementation proved far more complex than anticipated. The key insight is that adapting Paxos to production requires addressing numerous engineering challenges, such as disk corruption, master leases, efficient group membership changes, and fault recovery, exposing gaps between theoretical descriptions and practical realities. The paper contributes by detailing key modifications, including using non-voting replicas to handle disk corruption, optimizing performance through master leases, and ensuring liveness under challenging conditions. It also introduces approaches like log snapshots for state management and MultiOp for transaction-style operations. Additionally, the authors address practical issues often overlooked in the literature, such as group membership management and performance optimization for real-world environments. Despite its robustness, the system faces challenges in testing fault-tolerant systems and avoiding rare but critical operator errors.

Discussion questions

Q1

(question contributed by former CSE232 student Sherry Lin)

In section 4, the authors use slightly different terminology from "Paxos Made Simple" to overview the Paxos algorithm. How can we map these concepts to the terminology in "Paxos Made Simple"?

Discussion summary for Q1

The terminology in the paper differs slightly but maps directly to concepts in “Paxos Made Simple”: Coordinator = Proposer. While “Paxos Made Simple” uses “proposer,” this paper refers to it as the “coordinator.” The coordinator initiates proposal rounds. Sequence Number = Proposal Number. The “sequence number” mentioned in the paper aligns with the “proposal number” in “Paxos Made Simple.” Replicas = Paxos Nodes (including Proposers, Acceptors, Learners). In the paper, replicas take on multiple roles, with one elected as the coordinator. Propose Message = Prepare Message. This terminology shift reflects a similar operation in phase one of Paxos. Commit Message = Learn Message. The commit message in the paper signals the conclusion of consensus and is equivalent to the learn message in Paxos. Explicit Reject. The paper introduces a “reject” message that is more explicit than Paxos’ “ignore” behavior for invalid proposals. This helps proposers recover faster by avoiding timeouts.

Q2

Section 6.2 of the paper describes a "database consistency check" and various "inconsistency incidents" that have occurred. But using Paxos for state machine replication ought to provide strong consistency. So, why was a "consistency check" necessary, and why did "inconsistency incidents" occur?

Discussion summary for Q2

A "consistency check" was necessary due to factors beyond its crash/omission fault model. These include Byzantine faults, such as hardware corruption, memory errors, or illegal memory access, which can arise from random hardware failures or errant code in the codebase. Additionally, human errors, like unresolved dependencies, and implementation bugs can lead to inconsistency incidents. Practical adaptations, such as interactions with external code or shared memory, may also introduce errors. In one incident, an operator error caused an issue, while in another, replaying the faulty replica’s log showed consistency, suggesting random hardware memory corruption. To mitigate issues, the system now maintains a database of checksums and verifies each database access against it.

Q3

Section 6.1 of the paper describes how, rather than implementing the Paxos algorithm directly in C++, the authors used their own, homegrown state machine specification language that compiles to C++. What do you think the pros and cons of this approach are? The authors give anecdotal evidence in support of their approach; do you find their evidence convincing?

Discussion summary for Q3

Pros:

• Simplifies Paxos implementation, improving productivity and reducing errors.
• Avoids C++ issues like memory leaks and offers tailored optimizations through a domain-specific approach.
• Compiles to C++, ensuring high performance.

Cons:

• Adds maintenance overhead for the DSL and its compiler.
• Sacrifices generality, making it harder to integrate with other systems or adapt to changes.
• Updates to the DSL and compiler are labor-intensive. No experimental comparison with direct C++ implementation, making the benefits less objectively convincing. While the authors provide anecdotal evidence supporting their approach, the lack of quantitative data limits how compelling their claims are.

Q4 (optional; if you have time)

In section 6.3 of the paper, Chandra et al. write, "By their very nature, fault-tolerant systems try to mask problems. Thus they can mask bugs or configuration problems while insidiously lowering their own fault-tolerance." Give an example of how this might happen in Paxos or in another fault-tolerant system with which you are familiar (e.g., chain replication).

Discussion summary for Q4 (optional; if we get to it)

[to be filled in by scribes, if we get to it]