8 ms·

PigPaxos: Removing the Scalability Bottlenecks in Paxos

103 points by mad44 7y ago

excerionsforte 7y ago
Interesting idea moving the reception of messages to other nodes and getting back smaller set of messages. Not only that but distributing the reception responsibility into relay groups where it can be load balanced among peers. The leader using relay nodes reminds me of how humans organize into boss and worker groups and the boss shouts out orders to group leaders. I would like to see how dynamic relay groups will perform under stress and I wonder who would communicate new relay groups. Choice of leader imposing relay group structure or groups self organizing.
- hinkley 7y ago
  I use Raft for the same reason I use Ethernet. As my distributed computing teacher said, it’s a terrible protocol but the best one we have. Raft, and I believe Panos, contain some of the 8 Fallacies of Distributed Computing. The most unavoidable being assuming the network is heterogenous. I won’t say this keeps me up at night, but it distracts me when I’m eating lunch. Mere mortals don’t have all identical hardware or all equidistant network ping times. And even if you start that way, upgrades will at least temporarily change that dynamic. Geographical redundancy will really change that dynamic. And often it’s when we are changing things that they break. So it’s all fine until you get new customers and have to upgrade and then all of your new customers get to watch you crash and burn during an upgrade. Rabbit and Consul reduce this surface area by having two classes of users. I’ve heard of Raft variants with three (pure consumers, full voting members, and new or returning members who are still catching up) so that you can use machines unprepared for leadership and they will never try to elect themselves leader. Right now we are still in a weird era where networking is so stupid fast that it’s faster to get data from another machine than from your own storage, but that can’t last forever. Berkeley did some really crazy things when this inversion of costs happened in the 80’s, but by the time I learned about it less than 10 years later, we were already tut tutting about how foolish that was. I think the big thing I’ve been waiting for from a relay group type solution is for the participants to discover the network topology and elect a local representative to receive and rebroadcast the inbound stream of updates. I don’t know that you have to funnel all traffic through that intermediary, the way statsd does. Just the cumulative event stream could represent an order of magnitude decrease in packets with only a slight increase in latency.
  - excerionsforte 7y ago
    I was thinking about datacenter/network topology aware dynamic groups as one of the ideas for how a leader would impose structure or how a group would self organize. All nodes could keep statistics, as well as use user defined metadata, and when they are chosen as leader or group leader to figure out group structure to minimize latency considering latency time is based on slowest path to leader.
  - dnautics 7y ago
    > Raft, and I believe Panos, contain some of the 8 Fallacies of Distributed Computing. The most unavoidable being assuming the network is heterogenous. Did you mean homogeneous? Also, Raft doesn't assume the network is homogeneous. > I’ve heard of Raft variants with three (pure consumers, full voting members, and new or returning members who are still catching up) so that you can use machines unprepared for leadership and they will never try to elect themselves leader. What's the purpose of these non-leader-competent nodes? Is it merely to increase the quorum membership and make consistency more difficult? Why wouldn't you architect this as a client/server relationship?
    - hinkley 7y ago
      > Did you mean homogeneous? Yes > Also, Raft doesn't assume the network is homogeneous. Raft assumes that if the leader dies, that quick and orderly election relies on all members doing their 'duty' and putting themselves forward as the new leader if some counter says they are next. That means it assumes that any server can be leader. What is implicit in this state of affairs is that all cluster members are equipped to perform the duties of the leader, which includes rebroadcasting all state changes - directly - to all other members. So every single machine has to have enough bandwidth to every other machine to comfortably ferry all of that data across. That is a huge assumption, both historically speaking, and with geographical distribution of servers.
      - dnautics 7y ago
        ah ok, so you mean the "node membership is homogenous". i thought you were talking about the transport layer.
eternalban 7y ago
[edit: comparative performance to epaxos is noted in OP - a x10 improvement is claimed.] Egalitarian Paxos (2013): https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf code: https://github.com/efficient/epaxos https://github.com/efficient/epaxos
zinclozenge 7y ago
Interesting that there is another Paxos variant that was published to arxiv around february called BipartisanPaxos https://mwhittaker.github.io/publications/bipartisan_paxos.pdf https://mwhittaker.github.io/publications/bipartisan_paxos.p.... It too aims at removing bottlenecks.
- mad44 7y ago
  The compartmentalized consensus separates follower as acceptor and replica, and divorces command-log replication from data replication. It also seems to use two acceptors group as in horizontal scaling. The compartmentalized consensus does not have relay nodes that do relay/aggregation. The idea in PigPaxos is simply that using randomized relay/aggregators have surprising power for vertically scaling Paxos. The bipartisan Paxos, seems to apply the compartmentalized consensus idea to EPaxos.
hadronzoo 7y ago
Is this a similar concept to compartmentalized consensus? https://mwhittaker.github.io/publications/compartmentalized_consensus.pdf https://mwhittaker.github.io/publications/compartmentalized_...
- mad44 7y ago
  The compartmentalized consensus separates follower as acceptor and replica, and divorces command-log replication from data replication. It also seems to use two acceptors group as in horizontal scaling. The compartmentalized consensus does not have relay nodes that do relay/aggregation. The idea in PigPaxos is simply that using randomized relay/aggregators have surprising power for vertically scaling Paxos. The bipartisan Paxos, seems to apply the compartmentalized consensus idea to EPaxos.
nano_o 7y ago
Great idea and great work! A couple nitpicks: it would be nice to see what happens when the leader fails. Optimizing for the case of a stable leader might have impact on recovery time. Another important aspect for fault-tolerance is whether you can really survive any minority crashing. For example, if only the strictly necessary number of nodes keep up with the leader, then if most of those crash the system will have a really hard time recovering due to the backlog accumulated at slow nodes which now need to catch up for the system to continue operating. A performance number that does not take those things into account may not be very realistic. Nevertheless the idea is pretty good.
- tptacek 7y ago
  Doesn't Multi-Paxos already have stable leaders? My understanding was that the innovation here was to relay prepare/promise/accept/accepted across a random relay network.
  - nano_o 7y ago
    Yes, it's a nitpick. The comparison to Multi-Paxos seems fair because it makes similar assumptions (unless re-configuring the relay network after a leader failure is somehow difficult, but I wouldn't expect that). My point is that it would be nice to benchmark protocols that take into account the issues I brought up, and measure what happens in the worst failure scenarios they are supposed to tolerate. Otherwise we get a false sense of what performance can be achieved if one really cares about fault-tolerance. This small issue does not diminish the main contribution of the paper in any way.
senderista 7y ago
You can achieve constant write throughput and read latency and linearly scalable read throughput (at the cost of write latency) with LCR, a criminally unknown uniform total order broadcast protocol.

103 points by mad44 7y ago

Interesting idea moving the reception of messages to other nodes and getting back smaller set of messages. Not only that but distributing the reception responsibility into relay groups where it can be load balanced among peers. The leader using relay nodes reminds me of how humans organize into boss and worker groups and the boss shouts out orders to group leaders. I would like to see how dynamic relay groups will perform under stress and I wonder who would communicate new relay groups. Choice of leader imposing relay group structure or groups self organizing.

hinkley 7y ago
I use Raft for the same reason I use Ethernet. As my distributed computing teacher said, it’s a terrible protocol but the best one we have. Raft, and I believe Panos, contain some of the 8 Fallacies of Distributed Computing. The most unavoidable being assuming the network is heterogenous. I won’t say this keeps me up at night, but it distracts me when I’m eating lunch. Mere mortals don’t have all identical hardware or all equidistant network ping times. And even if you start that way, upgrades will at least temporarily change that dynamic. Geographical redundancy will really change that dynamic. And often it’s when we are changing things that they break. So it’s all fine until you get new customers and have to upgrade and then all of your new customers get to watch you crash and burn during an upgrade. Rabbit and Consul reduce this surface area by having two classes of users. I’ve heard of Raft variants with three (pure consumers, full voting members, and new or returning members who are still catching up) so that you can use machines unprepared for leadership and they will never try to elect themselves leader. Right now we are still in a weird era where networking is so stupid fast that it’s faster to get data from another machine than from your own storage, but that can’t last forever. Berkeley did some really crazy things when this inversion of costs happened in the 80’s, but by the time I learned about it less than 10 years later, we were already tut tutting about how foolish that was. I think the big thing I’ve been waiting for from a relay group type solution is for the participants to discover the network topology and elect a local representative to receive and rebroadcast the inbound stream of updates. I don’t know that you have to funnel all traffic through that intermediary, the way statsd does. Just the cumulative event stream could represent an order of magnitude decrease in packets with only a slight increase in latency.
- excerionsforte 7y ago
  I was thinking about datacenter/network topology aware dynamic groups as one of the ideas for how a leader would impose structure or how a group would self organize. All nodes could keep statistics, as well as use user defined metadata, and when they are chosen as leader or group leader to figure out group structure to minimize latency considering latency time is based on slowest path to leader.
- dnautics 7y ago
  > Raft, and I believe Panos, contain some of the 8 Fallacies of Distributed Computing. The most unavoidable being assuming the network is heterogenous. Did you mean homogeneous? Also, Raft doesn't assume the network is homogeneous. > I’ve heard of Raft variants with three (pure consumers, full voting members, and new or returning members who are still catching up) so that you can use machines unprepared for leadership and they will never try to elect themselves leader. What's the purpose of these non-leader-competent nodes? Is it merely to increase the quorum membership and make consistency more difficult? Why wouldn't you architect this as a client/server relationship?
  - hinkley 7y ago
    > Did you mean homogeneous? Yes > Also, Raft doesn't assume the network is homogeneous. Raft assumes that if the leader dies, that quick and orderly election relies on all members doing their 'duty' and putting themselves forward as the new leader if some counter says they are next. That means it assumes that any server can be leader. What is implicit in this state of affairs is that all cluster members are equipped to perform the duties of the leader, which includes rebroadcasting all state changes - directly - to all other members. So every single machine has to have enough bandwidth to every other machine to comfortably ferry all of that data across. That is a huge assumption, both historically speaking, and with geographical distribution of servers.
    - dnautics 7y ago
      ah ok, so you mean the "node membership is homogenous". i thought you were talking about the transport layer.

eternalban 7y ago

[edit: comparative performance to epaxos is noted in OP - a x10 improvement is claimed.] Egalitarian Paxos (2013): https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf code: https://github.com/efficient/epaxos https://github.com/efficient/epaxos

zinclozenge 7y ago

Interesting that there is another Paxos variant that was published to arxiv around february called BipartisanPaxos https://mwhittaker.github.io/publications/bipartisan_paxos.pdf https://mwhittaker.github.io/publications/bipartisan_paxos.p.... It too aims at removing bottlenecks.

mad44 7y ago
The compartmentalized consensus separates follower as acceptor and replica, and divorces command-log replication from data replication. It also seems to use two acceptors group as in horizontal scaling. The compartmentalized consensus does not have relay nodes that do relay/aggregation. The idea in PigPaxos is simply that using randomized relay/aggregators have surprising power for vertically scaling Paxos. The bipartisan Paxos, seems to apply the compartmentalized consensus idea to EPaxos.

hadronzoo 7y ago

Is this a similar concept to compartmentalized consensus? https://mwhittaker.github.io/publications/compartmentalized_consensus.pdf https://mwhittaker.github.io/publications/compartmentalized_...

mad44 7y ago
The compartmentalized consensus separates follower as acceptor and replica, and divorces command-log replication from data replication. It also seems to use two acceptors group as in horizontal scaling. The compartmentalized consensus does not have relay nodes that do relay/aggregation. The idea in PigPaxos is simply that using randomized relay/aggregators have surprising power for vertically scaling Paxos. The bipartisan Paxos, seems to apply the compartmentalized consensus idea to EPaxos.

nano_o 7y ago

Great idea and great work! A couple nitpicks: it would be nice to see what happens when the leader fails. Optimizing for the case of a stable leader might have impact on recovery time. Another important aspect for fault-tolerance is whether you can really survive any minority crashing. For example, if only the strictly necessary number of nodes keep up with the leader, then if most of those crash the system will have a really hard time recovering due to the backlog accumulated at slow nodes which now need to catch up for the system to continue operating. A performance number that does not take those things into account may not be very realistic. Nevertheless the idea is pretty good.

tptacek 7y ago
Doesn't Multi-Paxos already have stable leaders? My understanding was that the innovation here was to relay prepare/promise/accept/accepted across a random relay network.
- nano_o 7y ago
  Yes, it's a nitpick. The comparison to Multi-Paxos seems fair because it makes similar assumptions (unless re-configuring the relay network after a leader failure is somehow difficult, but I wouldn't expect that). My point is that it would be nice to benchmark protocols that take into account the issues I brought up, and measure what happens in the worst failure scenarios they are supposed to tolerate. Otherwise we get a false sense of what performance can be achieved if one really cares about fault-tolerance. This small issue does not diminish the main contribution of the paper in any way.

senderista 7y ago

You can achieve constant write throughput and read latency and linearly scalable read throughput (at the cost of write latency) with LCR, a criminally unknown uniform total order broadcast protocol.