Source-linked AI summary
Paxos Made Switch-y
Huynh Tu Dang, Marco Canini, Fernando Pedone, Robert Soulé
TL;DR
Because data-center services depend on Paxos-based replication, Paxos performance matters, while implementing consensus inside forwarding devices has presented practical challenges. The paper implements Paxos in P4 and presents the implementation as a first step toward data-plane language evolution and further consensus-design research.
Problem
Paxos performance affects data-center infrastructure, but implementing Paxos inside forwarding devices has been challenging.
Source: §1 · p. 1Method
The paper implements Paxos in P4, a language for programming network data planes.
Source: §1 · p. 1Results
The implementation is a first step toward data-plane language evolution and new research challenges in consensus-protocol design.
Source: §7 · p. 9Takeaways & Limitations
Implementing Paxos exposes requirements for data-plane languages and research opportunities for consensus designers.
Source: §1 · p. 2, §5 · p. 7The implementation has not been evaluated on actual hardware, so efficient support for P4 programs on new hardware remains uncertain.
Source: §5.1 · p. 8
Abstract
from arXiv · showhide
This paper describes an implementation of the well-known consensus protocol, Paxos, in the P4 programming language. P4 is a language for programming the behavior of network forwarding devices (i.e., the network data plane). Moving consensus logic into network devices could significantly improve the performance of the core infrastructure and services in data centers. Moreover, implementing Paxos in P4 provides a critical use case and set of requirements for data plane language designers. In the long term, we imagine that consensus could someday be offered as a network service, just as point-to-point communication is provided today.
1 Introduction
Paxos performance matters to data-center services, and flexible forwarding hardware opens a path to implementing consensus in switches. The paper implements Paxos in P4, highlighting new practical concerns and requirements for data-plane languages and consensus design.
1 Introduction
- Paxos performance affects data-center services that depend on state-machine replication for fault tolerance.The paper notes that many core infrastructure systems use state-machine replication.Source: §1 · p. 1
- Moving Paxos logic into forwarding devices could reduce message hops and server message-processing bottlenecks.The authors describe consensus as a possible network service.Source: §1 · p. 1
- Flexible packet-processing hardware is emerging, while data-plane languages still need practical applications and use cases.The paper cites customizable pipelines and proposals including POF, PX, and P4.Source: §1 · p. 1
- The paper implements Paxos in P4, addressing practical concerns introduced by implementing consensus on packet-forwarding devices.The authors choose P4 because it is open and relatively mature compared with alternatives.Source: §1 · pp. 1–2
- The implementation exposes constraints for consensus designers, exercises P4 beyond published examples, and offers techniques for other data-plane applications.The cited constraints include field size and persistent-storage history.Source: §1 · p. 2
2 Paxos Background
Paxos coordinates participants through rounds and two phases, using acceptor quorums to preserve a chosen value and reach decisions. Its liveness depends on a nonfaulty coordinator, a majority quorum of nonfaulty acceptors, and at least one nonfaulty proposer.
2 Paxos Background
- Paxos participants act as proposers, coordinators, acceptors, and learners, and instances proceed through rounds with two phases.Leader election selects the coordinator and is external to Paxos.Source: §2 · p. 2
- In Phase 1, a coordinator requests promises from acceptors; a majority quorum completes the phase and reports any previously accepted value.The coordinator must use the previously accepted value with the highest associated round number in Phase 2.Source: §2 · pp. 2–3
- Consensus terminates when a quorum accepts the same round, permanently binding the instance's value for learners to deliver.Learners can monitor acceptors or receive a decision message from the coordinator.Source: §2 · p. 3
- Every instance eventually decides if a nonfaulty coordinator is eventually selected, a majority quorum of acceptors is nonfaulty, and at least one proposer is nonfaulty.A coordinator can retry with a larger round number; Phase 2 at a higher round requires completing Phase 1 at that round.Source: §2 · p. 3
- Throughout the paper, Paxos refers to multiple instances chained together as Multi-Paxos.Source: §2 · p. 3
3 P4 Background
P4 programs describe packet-processing pipelines through tables and actions, with developers specifying packet fields, parsing, and control composition. Registers and metadata provide persistent and per-packet state for the Paxos implementation.
3 P4 Background
- A P4 program describes a sequence of tables that match packet-header fields and forward, drop, or modify packets.Source: §3 · p. 3
- P4's core abstractions specify header fields, parsing, table matching, actions, and the composition of tables.Developers set field widths; actions can modify fields, add or remove headers, forward or drop packets, and perform stateful operations.Source: §3 · p. 3
- Registers store persistent state in arrays of specified-size cells, while metadata stores volatile per-packet state not derivable from headers.The Paxos implementation uses both constructs.Source: §3 · p. 3
4 P4 Paxos
Switch Paxos places coordinator and acceptor functionality on forwarding devices. Its P4 implementation carries Paxos state and messages through switches, while learners gather acceptor votes to decide values.
Architecture
- Switch Paxos executes coordinator and acceptor functionality on forwarding devices, while learners receive acceptor votes to learn the consensus result.The prototype connects each learner to every acceptor on a separate network interface.Source: §4 · pp. 3, 6
Paxos Header
- Phase 1 can be pre-computed for a bounded number of instances, so this implementation commonly runs Phase 2 only.Pre-computation must be repeated when the bound is approached or the coordinator changes.Source: §4 · pp. 3–4
- The packet header carries message type, instance, round, prior-vote round, and value; fixed-width fields require reserving space for the largest value.The bounded instance field limits how many instances can be pre-computed, while oversized fields can affect performance and values may contain unused bytes.Source: §4 · p. 4
Coordinator
- The coordinator assigns each Phase 2A message the next instance number, incrementing and persisting that sequence in a register.The P4 table invokes this action for valid Paxos messages before forwarding them.Source: §4 · p. 5, Figure 4
Learner
- Learners decide a value after receiving identical Phase 2B messages from a majority quorum of acceptors for an instance.In the prototype, each acceptor connects through a separate learner interface; a majority is f + 1 when f acceptor failures are tolerated.Source: §4 · p. 6
Optimizations
- Cheap Paxos can place f + 1 first-class acceptors in switches and f second-class acceptors on servers; with f = 1, coordinator co-location needs two switches.The server acceptors may lag but can help if a first-class acceptor fails.Source: §4 · p. 6
Acceptor
- Acceptors compare each packet’s round with stored state, then return prior vote information for Phase 1A or update proposal state for Phase 2A.The implementation drops packets whose round is not greater than the stored round; it does not include periodic cleanup of accepted-proposal history.Source: §4 · p. 6, Figure 5
5 Discussion
The discussion uses the Paxos-in-P4 implementation to identify language-design challenges and future directions for consensus protocols. It considers both practical constraints in P4 and ways network properties could inform protocol design.
5.1 Impact on P4 Language
- P4’s table-based programming can make state-dependent logic awkward because control blocks cannot directly read stored values.The acceptor must access the round number through an action resulting from a table application.Source: §5.1 · p. 8
- Without a module system, separating and composing functionality is difficult, and the authors expect mistakes to become more likely as tables or applications grow.They give importing a Paxos module into an L2 learning switch as an example of desired composition.Source: §5.1 · p. 8
- Out-of-range register access causes a segmentation fault, while checking every memory access would add packet-processing overhead.The authors suggest a safe mode with runtime boundary checks and a way to catch and recover from faults.Source: §5.1 · p. 8
- Target-dependent memory layout could place tables and shared registers in areas that cannot communicate, making the implementation unsupported on some targets.The authors suggest annotations to indicate tables and registers that should be co-located.Source: §5.1 · p. 8
- P4 is expressive enough to describe Paxos, but the implementation has not been evaluated on hardware, leaving efficient hardware support uncertain.The authors identify balancing expressivity and performance as an open design challenge.Source: §5.1 · p. 8
5.2 Impact on Paxos Protocol
- Consensus protocols often compensate for possible message loss or reordering, while programmable network hardware may let future protocols use network behavior to optimize performance.The authors present this as a direction for protocol design, not a result demonstrated by their implementation.Source: §5.2 · p. 8
- Fast Paxos and Speculative Paxos use spontaneous message ordering for low-latency consensus; it can arise from careful network configuration or IP multicast in local-area networks.Spontaneous message ordering means that messages sent to several destinations are likely to arrive in the same order.Source: §5.2 · p. 8
- Switches could increase spontaneous ordering and help Fast Paxos reach consensus in fewer communication steps; stateful switches could also support a redesigned Disk Paxos.Such a Disk Paxos design would need to account for switches having much less storage than traditional storage devices.Source: §5.2 · p. 8
6 Related Work
The related-work discussion situates the paper among data-plane languages and replication protocols. It connects replication to message ordering and notes that few ordering protocols exploit network-specific behavior.
Related work
- Prior work proposed switch-based Paxos and NetPaxos, which solves consensus without switch computation by assuming packet ordering; this paper makes switch-based Paxos concrete.The authors chose P4 for its active user community and relative maturity, while suggesting their switch-based ideas may generalize to other languages.Source: §6 · p. 9
- State-machine replication [12, 26], deferred-update replication [7], and primary-backup replication [19] all rely on message ordering.The required ordering concerns commands or updates among replicas, including updates in transit when a primary fails.Source: §6 · p. 9
- Few protocols exploit network-specific behavior; those that use spontaneous message ordering can avoid constructing order through additional protocol steps.The authors argue that programmable network hardware makes closer integration between ordering protocols and the network layer realizable.Source: §6 · p. 9
7 Conclusion
The paper presents Paxos in P4 as a first step toward developing data-plane languages and exploring consensus-protocol design. It suggests that moving application-layer logic into flexible network hardware could improve data-center infrastructure performance.
Conclusion
- The paper describes an implementation of Paxos in P4 as a first step toward continued development of data-plane languages.The implementation also opens research challenges in consensus-protocol design.Source: §7 · p. 9
- Moving application-layer logic into flexible network hardware could dramatically improve data-center infrastructure performance.The conclusion frames this as a possible impact of emerging hardware and expressive data-plane programming languages.Source: §7 · p. 9
- The implementation opens new research challenges in the design of consensus protocols.Source: §7 · p. 9