9 ms·

Say No to Paxos Overhead: Replacing Consensus with Network Ordering

199 points by kushti 10y ago

socmag 10y ago
This gets a huge thumbs up from me. I've worked through a lot of the same reasoning as these people, and as technically correct as PAXOS might be, in the real world, causality at high frequency is a blur at best, and there is absolutely no need to impose the hard constraints that PAXOS and others imply. The only cases where guaranteed constraint systems are needed are when you don't have traffic and at each time step all parties are capable of asking each other to confirm that from all frames of reference they all agree who and why someone committed first. Which is great, but makes zero sense in the real world. At scale transactions are and should be committed on a best effort basis. You don't look at your bank account and wonder why the T-Mobile payment went out slightly after your ATM withdrawal. Why? Because... shrug. God said so. He works in mysterious ways. This is awesome. Sign me up.
- MrBuddyCasino 10y ago
  Maybe I didn't get it, but ordering is still guaranteed, it has just moved to the network layer and is kind of "hardware accelerared" by a smart switch or SDN node, or am I wrong?
  - hardwaresofton 10y ago
    Ordering is definitely guaranteed -- it's the only thing that is, by this scheme (delivery is not, latency is unbounded). They provide 3 approaches in the paper: SDN node, programmed hardware, and software-only. Software-only approach lost some of the latency-gains, as might be expected.
    - MrBuddyCasino 10y ago
      Thanks, thats how I understood it. The tradeoffs are quite seductive, in my experience most companies do not operate their software on a scale where they really have to scale out, but they run multiple instances simply to increase availability. But then those are probably the same kind of companies that will probably not have the required network hardware, and won't for many years to come. I'm thinking about stuff like Redis or distributed caches like Hazelcast, maybe even Zookeeper and friends. Any ideas where this could shine? Cloud vendors could manage the hardware part, but is this model attractive to them, essentially being constrained to single-node performance?
      - hardwaresofton 10y ago
        I thought of mostly the same things (redis/some other database), maybe also IoT? This, in combination with the ultra low power wifi post that recently went up (https://news.ycombinator.com/item?id=13135607 https://news.ycombinator.com/item?id=13135607) seem like they would go together. I think cloud vendors would definitely charge a pretty high premium for this, since it requires more than zero work on their part. Also, aren't most simply-distributed databases constrained to single node performance (for writes, assuming one master)? I feel like you could work in fast reads to this scheme too, if you required replicas to have a complete log in order to respond to a read, since it's all or nothing. The possibility of a slightly (1 op) stale read is possible though.
- lepacheco 10y ago
  That's not what the paper is about. They still provide Consensus (i.e., total ordering).
- jon-wood 10y ago
  > You don't look at your bank account and wonder why the T-Mobile payment went out slightly after your ATM withdrawal. Your bank account isn't being used for even nearly the same things distributed data stores like this are being used for. And even then they have to make workarounds to ordering issues, otherwise if there were a day when my salary comes in and my rent went out I'd be hit with overdraft charges if they happened in the wrong order.
  - ansible 10y ago
    For a while, banks were maliciously ordering such transactions, to create such scenarios. That's why I'm real cautious about debit cards.
    - function_seven 10y ago
      Yup. I don’t think they ever processed debits before credits in any given day. (The standard AFAIK has always been to process all credits first, then do the debits. This might be an antiquated understanding, though). But what they did do was to process the largest debit first, then the next largest, and so on. You have $100 in the account, and completed four transactions at $4, $8, $15, and $90? In that order? Too bad, 90 goes first, followed by three overdrafts.
    - tinco 10y ago
      You're cautious about debit cards? The only alternative being credit cards, where each transaction by definition is an overdraft? Maybe I'm getting this wrong, I'm from Europe where we don't really use credit cards. What fee are you talking about? If you use a debit card, and you don't have the money it will simply refuse the transaction right?
      - deleted 10y ago
        [deleted]
      - computerphage 10y ago
        No, they will charge you a fee called an overdraft fee for the "service" of allowing you to purchase the item. They basically extend you a small line of credit (there's some upper limit before they will deny the purchase) and then charge you, say, $35. Credit cards are always overdrawn in the sense that the bank has extended you a line of credit, but they don't have a fee associated with typical use.
- pron 10y ago
  You have misunderstood (as the title is a pun). It is "Say NO to Paxos Overhead", and is about a new Paxos invariant called NOPaxos (Network Ordering Paxos), that relies on code running in network switches to provide ordering. The same consensus guarantees apply -- in fact, it is still Paxos -- but the latency is significantly improved (and is within 4% of no replication at all). So it's Paxos with (almost) no overhead thanks to NO. You are also very mistaken about there being "no need" for consistency guarantees. Even systems that don't provide consistency for every data update, do enjoy consistency for some more rare events (like cluster membership). Without strong consistency at all, the range of distributed programs we can build is much reduced. The need for a greater range of distributed programs arises not from geographically separated applications (like ATMs), but from the mere fact that distributed computing is currently our only way to scale computational power (within that data center). If we cannot have consistent distributed computations, our computational power and the range of applications we can build in general would be greatly reduced.
  - socmag 10y ago
    I was definitely NOt saying there is no need for consistency guarantees at all. I was saying that this is a much better way to do it.
otoburb 10y ago
Using the correct capitalization makes more sense for the HN title because "NO" in this instance and context means "network ordering", which the article then discusses (even though the expansion is at the end of the article title).
- IshKebab 10y ago
  It's a pun. Although you are right, they have kind of ruined it by using No instead of NO.
hardwaresofton 10y ago
"NOPaxos" might me a catchy name but is probably not good in the long term as it might make people think it's NOT paxos. Maybe "NeOPaxos" is better? Also If my understanding is anywhere near correct, it's a mix of Paxos and a bit of a proxying sequencer (which may be implemented in a physical switch) and all replicas & master need to be on the same switch/subnet... Going to read the paper now -- anyone have a better understanding of the tech they could share? Excited but still a bit skeptical
- meta_AU 10y ago
  Use a single node to provide all-or-nothing and ordering, then simplify Paxos based on those assumptions.
  - hardwaresofton 10y ago
    Thanks -- After reading the paper I think I have a better understanding, and it is pretty exciting, this does seem to be a pretty good throughput improvement, especially if things are mostly happy-path. The paper seemed to be missing an exploration of worst-case scenarios and equivalencies though, but I guess I guess worst case is paxos speed (consistently failing sequencer, or a leading replica that receives one messages then is unreachable, bad quorums, etc)
- lepacheco 10y ago
  Yep, I also think it's kind of a misleading name. It's still Consensus but with stronger assumptions on the network (kind of, it depends on an external master for correctness, which could itself use something like classic Paxos). Simplifying it a bit, they use a single sequencer that every packet must go through to get "ordered". As the authors suggest, that could be implemented in a programmable switch. Given that abstraction, they can simplify the consensus protocol itself.
- qznc 10y ago
  "NoPaxos" is not "Not Paxos" like "NoSQL" is "Not SQL" ;) If you use a NoSQL database, the relations do not disappear. You just have to implement your joins in a higher layer. NoPaxos pushes some parts of Paxos into lower levels, namely the OUM primitive of the network.
siscia 10y ago
In the Second to the last figure (fig 5) you can see a behaviour that is extremely weird in my opinion, the latency is almost in O(1) and then hit a wall and goes up as exponential (I guess). It this common? What cause this behavior?
- qaq 10y ago
  https://www.youtube.com/watch?v=gas2v1emubU https://www.youtube.com/watch?v=gas2v1emubU
- mritun 10y ago
  That's multicast for you. Once you congestion and/or group size increase beyond a certain value or group size, things go /really/ bad; as in you may need to "shutdown, wait and reboot" your network to recover.
  - deleted 10y ago
    [deleted]
  - tssva 10y ago
    All of the tested protocols including unreplicated flows follow the same pattern with the proposed multicast protocol most closely following the same pattern of behavior as the unreplicated data; therefore some intrinsic property of multicast is not responsible.
- considrdharmful 10y ago
  Yes, this is common. That's a throughput-latency graph. What isn't being plotted in that graph is that there's actually an underlying controlled variable which both throughput and latency are responding to---the number of clients/outstanding requests at any given time. The reason you're seeing a "wall" is that the system has some peak throughput, and once you reach full saturation, the average latency for requests is going to go up to infinity. (So, it's actually not exponential growth, it's approaching an asymptote.)
mritun 10y ago
Interesting research paper but multicast is a non-starter for non-trivial production systems. 1. As implemented by most (read: all) network hw, it works fine when congestion is low. As soon as congestion starts increasing, the packet loss amplifies. 2. If you have large multicast groups, the bloom filters used for membership test become very full, hence false positive rate rapidly increases. This leads to multicast storms. In my experience, anything which is not TCP (or, to lesser degree UDP) is a non-starter for building reliable distributed systems. Despite the claims of "lower overhead" the TCP protocol stack gets most love and hence has been optimized heavily on every significant operating system.
- hardwaresofton 10y ago
  Would you mind expanding a little more? If I'm understanding your point correctly -- you're saying that the sequencer failure case (whether it's modified switches or programmable switches, or software-based) is more common as congestion increases, and that's what makes this unusable in practice? Wouldn't traditional Paxos already be dead in the water at that point? Also regarding the point about multicast storms -- I was imagining something like <100 nodes in a multicast group -- is that naive? What obvious use case am I missing? I was basically thinking of this scheme in front of a database layer
- polskibus 10y ago
  Multicast has been used TIBCO Rendezvous to deliver high performance, high volume messaging in financial sector for ages. Can you elaborate on your claims?
  - revertts 10y ago
    Messaging in the financial sector has very different requirements from messaging for a general service backend, which I assume is what the OP is referencing. As an example, a certain ecommerce site back in the day was heavily tibco based and migrated off due to inefficiencies at scale, multicast storms, debugability, and the general nature of multicast failures (for the most part you get no graceful degradation - which is fine when you have tight control of the network and do careful capacity planning, but isn't the mode that most tech companies live in). Anecdotally, non-multicast setups are easier to scale in hardware (because you can push commodity farther) and most critically are easier for the normal type of engineer you'd find in the tech sector to reason about (because many aren't comfortable with networking equipment, so it's much easier moving that state out of the network and into layers they can easily debug).
toast0 10y ago
I haven't done much with Paxos and friends and I only read the blog, not the paper, but this seems like elect a coordinator, send all changes through the coordinator which creates an ordering and sends out the ordered changes to the group. And by the way, hide the coordinator in your switch. This seems pretty straightforward -- running MySQL replication in a sane way is essentially appoint a master server, send all writes through that, and hope you don't need to have a new election.
- altendo 10y ago
  This is characteristic of all distributed systems, so in that sense it isn't a unique concept to NOPaxos. The emphasis here is minimizing the traffic that a typical Paxos implementation incurs while changing the constraints of the distributed system.
matthewaveryusa 10y ago
I'm actually really curious about this. If you are geo-diverse and need to go over the internet, will this work?
- hardwaresofton 10y ago
  It It depends on what your definition of "work" is. if you're geo-diverse, and you want writes to happen are more than one place (as in the top nodes at each geographic location can all process requests), then you have to go the traditional consensus route. One server in one region makes a write, and the other servers in the region need to acknowledge the write before they move on, lest state become inconsistent. Pretty sure there's no way around it. if you're geo-diverse, but are OK with possibly stale reads from time to time, and only writing to one geographic area (server), then it seems possible -- you'd just apply these same principles across a bigger scale rather than same-datacenter. You'd probably also lose a lot of the latency gains though.
- zb 10y ago
  Probably not. It depends on guaranteed in-order packet arrival. In general the Internet very much does not guarantee that, so you would need control over all of the networks involved. Of course you can always tunnel over TCP (you need to tunnel over something, because you can't route multicast over the Internet either), but that would almost certainly eliminate the performance benefits.
- altendo 10y ago
  I'm in agreement with the other replies here - this seems more useful within a datacenter (and any unit smaller than that, such as an AWS Availability Zone) and not so much useful over the general internet. Too much unpredictability in how things get routed, what types of routers are hit, etc.
toolslive 10y ago
There are other consensus algorithms that start with a monotonous channel (ie a channel that might drop messages, but does not reorder them). Mencius fe does this and also avoids most of the overhead http://www.sysnet.ucsd.edu/sysnet/miscpapers/mencius-osdi.pdf http://www.sysnet.ucsd.edu/sysnet/miscpapers/mencius-osdi.pd...

199 points by kushti 10y ago

This gets a huge thumbs up from me. I've worked through a lot of the same reasoning as these people, and as technically correct as PAXOS might be, in the real world, causality at high frequency is a blur at best, and there is absolutely no need to impose the hard constraints that PAXOS and others imply. The only cases where guaranteed constraint systems are needed are when you don't have traffic and at each time step all parties are capable of asking each other to confirm that from all frames of reference they all agree who and why someone committed first. Which is great, but makes zero sense in the real world. At scale transactions are and should be committed on a best effort basis. You don't look at your bank account and wonder why the T-Mobile payment went out slightly after your ATM withdrawal. Why? Because... shrug. God said so. He works in mysterious ways. This is awesome. Sign me up.

MrBuddyCasino 10y ago
Maybe I didn't get it, but ordering is still guaranteed, it has just moved to the network layer and is kind of "hardware accelerared" by a smart switch or SDN node, or am I wrong?
- hardwaresofton 10y ago
  Ordering is definitely guaranteed -- it's the only thing that is, by this scheme (delivery is not, latency is unbounded). They provide 3 approaches in the paper: SDN node, programmed hardware, and software-only. Software-only approach lost some of the latency-gains, as might be expected.
  - MrBuddyCasino 10y ago
    Thanks, thats how I understood it. The tradeoffs are quite seductive, in my experience most companies do not operate their software on a scale where they really have to scale out, but they run multiple instances simply to increase availability. But then those are probably the same kind of companies that will probably not have the required network hardware, and won't for many years to come. I'm thinking about stuff like Redis or distributed caches like Hazelcast, maybe even Zookeeper and friends. Any ideas where this could shine? Cloud vendors could manage the hardware part, but is this model attractive to them, essentially being constrained to single-node performance?
    - hardwaresofton 10y ago
      I thought of mostly the same things (redis/some other database), maybe also IoT? This, in combination with the ultra low power wifi post that recently went up (https://news.ycombinator.com/item?id=13135607 https://news.ycombinator.com/item?id=13135607) seem like they would go together. I think cloud vendors would definitely charge a pretty high premium for this, since it requires more than zero work on their part. Also, aren't most simply-distributed databases constrained to single node performance (for writes, assuming one master)? I feel like you could work in fast reads to this scheme too, if you required replicas to have a complete log in order to respond to a read, since it's all or nothing. The possibility of a slightly (1 op) stale read is possible though.
lepacheco 10y ago
That's not what the paper is about. They still provide Consensus (i.e., total ordering).
jon-wood 10y ago
> You don't look at your bank account and wonder why the T-Mobile payment went out slightly after your ATM withdrawal. Your bank account isn't being used for even nearly the same things distributed data stores like this are being used for. And even then they have to make workarounds to ordering issues, otherwise if there were a day when my salary comes in and my rent went out I'd be hit with overdraft charges if they happened in the wrong order.
- ansible 10y ago
  For a while, banks were maliciously ordering such transactions, to create such scenarios. That's why I'm real cautious about debit cards.
  - function_seven 10y ago
    Yup. I don’t think they ever processed debits before credits in any given day. (The standard AFAIK has always been to process all credits first, then do the debits. This might be an antiquated understanding, though). But what they did do was to process the largest debit first, then the next largest, and so on. You have $100 in the account, and completed four transactions at $4, $8, $15, and $90? In that order? Too bad, 90 goes first, followed by three overdrafts.
  - tinco 10y ago
    You're cautious about debit cards? The only alternative being credit cards, where each transaction by definition is an overdraft? Maybe I'm getting this wrong, I'm from Europe where we don't really use credit cards. What fee are you talking about? If you use a debit card, and you don't have the money it will simply refuse the transaction right?
    - deleted 10y ago
      [deleted]
    - computerphage 10y ago
      No, they will charge you a fee called an overdraft fee for the "service" of allowing you to purchase the item. They basically extend you a small line of credit (there's some upper limit before they will deny the purchase) and then charge you, say, $35. Credit cards are always overdrawn in the sense that the bank has extended you a line of credit, but they don't have a fee associated with typical use.
pron 10y ago
You have misunderstood (as the title is a pun). It is "Say NO to Paxos Overhead", and is about a new Paxos invariant called NOPaxos (Network Ordering Paxos), that relies on code running in network switches to provide ordering. The same consensus guarantees apply -- in fact, it is still Paxos -- but the latency is significantly improved (and is within 4% of no replication at all). So it's Paxos with (almost) no overhead thanks to NO. You are also very mistaken about there being "no need" for consistency guarantees. Even systems that don't provide consistency for every data update, do enjoy consistency for some more rare events (like cluster membership). Without strong consistency at all, the range of distributed programs we can build is much reduced. The need for a greater range of distributed programs arises not from geographically separated applications (like ATMs), but from the mere fact that distributed computing is currently our only way to scale computational power (within that data center). If we cannot have consistent distributed computations, our computational power and the range of applications we can build in general would be greatly reduced.
- socmag 10y ago
  I was definitely NOt saying there is no need for consistency guarantees at all. I was saying that this is a much better way to do it.

otoburb 10y ago

Using the correct capitalization makes more sense for the HN title because "NO" in this instance and context means "network ordering", which the article then discusses (even though the expansion is at the end of the article title).

IshKebab 10y ago
It's a pun. Although you are right, they have kind of ruined it by using No instead of NO.

hardwaresofton 10y ago

"NOPaxos" might me a catchy name but is probably not good in the long term as it might make people think it's NOT paxos. Maybe "NeOPaxos" is better? Also If my understanding is anywhere near correct, it's a mix of Paxos and a bit of a proxying sequencer (which may be implemented in a physical switch) and all replicas & master need to be on the same switch/subnet... Going to read the paper now -- anyone have a better understanding of the tech they could share? Excited but still a bit skeptical

meta_AU 10y ago
Use a single node to provide all-or-nothing and ordering, then simplify Paxos based on those assumptions.
- hardwaresofton 10y ago
  Thanks -- After reading the paper I think I have a better understanding, and it is pretty exciting, this does seem to be a pretty good throughput improvement, especially if things are mostly happy-path. The paper seemed to be missing an exploration of worst-case scenarios and equivalencies though, but I guess I guess worst case is paxos speed (consistently failing sequencer, or a leading replica that receives one messages then is unreachable, bad quorums, etc)
lepacheco 10y ago
Yep, I also think it's kind of a misleading name. It's still Consensus but with stronger assumptions on the network (kind of, it depends on an external master for correctness, which could itself use something like classic Paxos). Simplifying it a bit, they use a single sequencer that every packet must go through to get "ordered". As the authors suggest, that could be implemented in a programmable switch. Given that abstraction, they can simplify the consensus protocol itself.
qznc 10y ago
"NoPaxos" is not "Not Paxos" like "NoSQL" is "Not SQL" ;) If you use a NoSQL database, the relations do not disappear. You just have to implement your joins in a higher layer. NoPaxos pushes some parts of Paxos into lower levels, namely the OUM primitive of the network.

siscia 10y ago

In the Second to the last figure (fig 5) you can see a behaviour that is extremely weird in my opinion, the latency is almost in O(1) and then hit a wall and goes up as exponential (I guess). It this common? What cause this behavior?

qaq 10y ago
https://www.youtube.com/watch?v=gas2v1emubU https://www.youtube.com/watch?v=gas2v1emubU
mritun 10y ago
That's multicast for you. Once you congestion and/or group size increase beyond a certain value or group size, things go /really/ bad; as in you may need to "shutdown, wait and reboot" your network to recover.
- deleted 10y ago
  [deleted]
- tssva 10y ago
  All of the tested protocols including unreplicated flows follow the same pattern with the proposed multicast protocol most closely following the same pattern of behavior as the unreplicated data; therefore some intrinsic property of multicast is not responsible.
considrdharmful 10y ago
Yes, this is common. That's a throughput-latency graph. What isn't being plotted in that graph is that there's actually an underlying controlled variable which both throughput and latency are responding to---the number of clients/outstanding requests at any given time. The reason you're seeing a "wall" is that the system has some peak throughput, and once you reach full saturation, the average latency for requests is going to go up to infinity. (So, it's actually not exponential growth, it's approaching an asymptote.)

mritun 10y ago

Interesting research paper but multicast is a non-starter for non-trivial production systems. 1. As implemented by most (read: all) network hw, it works fine when congestion is low. As soon as congestion starts increasing, the packet loss amplifies. 2. If you have large multicast groups, the bloom filters used for membership test become very full, hence false positive rate rapidly increases. This leads to multicast storms. In my experience, anything which is not TCP (or, to lesser degree UDP) is a non-starter for building reliable distributed systems. Despite the claims of "lower overhead" the TCP protocol stack gets most love and hence has been optimized heavily on every significant operating system.

hardwaresofton 10y ago
Would you mind expanding a little more? If I'm understanding your point correctly -- you're saying that the sequencer failure case (whether it's modified switches or programmable switches, or software-based) is more common as congestion increases, and that's what makes this unusable in practice? Wouldn't traditional Paxos already be dead in the water at that point? Also regarding the point about multicast storms -- I was imagining something like <100 nodes in a multicast group -- is that naive? What obvious use case am I missing? I was basically thinking of this scheme in front of a database layer
polskibus 10y ago
Multicast has been used TIBCO Rendezvous to deliver high performance, high volume messaging in financial sector for ages. Can you elaborate on your claims?
- revertts 10y ago
  Messaging in the financial sector has very different requirements from messaging for a general service backend, which I assume is what the OP is referencing. As an example, a certain ecommerce site back in the day was heavily tibco based and migrated off due to inefficiencies at scale, multicast storms, debugability, and the general nature of multicast failures (for the most part you get no graceful degradation - which is fine when you have tight control of the network and do careful capacity planning, but isn't the mode that most tech companies live in). Anecdotally, non-multicast setups are easier to scale in hardware (because you can push commodity farther) and most critically are easier for the normal type of engineer you'd find in the tech sector to reason about (because many aren't comfortable with networking equipment, so it's much easier moving that state out of the network and into layers they can easily debug).

toast0 10y ago

I haven't done much with Paxos and friends and I only read the blog, not the paper, but this seems like elect a coordinator, send all changes through the coordinator which creates an ordering and sends out the ordered changes to the group. And by the way, hide the coordinator in your switch. This seems pretty straightforward -- running MySQL replication in a sane way is essentially appoint a master server, send all writes through that, and hope you don't need to have a new election.

altendo 10y ago
This is characteristic of all distributed systems, so in that sense it isn't a unique concept to NOPaxos. The emphasis here is minimizing the traffic that a typical Paxos implementation incurs while changing the constraints of the distributed system.

matthewaveryusa 10y ago

I'm actually really curious about this. If you are geo-diverse and need to go over the internet, will this work?

hardwaresofton 10y ago
It It depends on what your definition of "work" is. if you're geo-diverse, and you want writes to happen are more than one place (as in the top nodes at each geographic location can all process requests), then you have to go the traditional consensus route. One server in one region makes a write, and the other servers in the region need to acknowledge the write before they move on, lest state become inconsistent. Pretty sure there's no way around it. if you're geo-diverse, but are OK with possibly stale reads from time to time, and only writing to one geographic area (server), then it seems possible -- you'd just apply these same principles across a bigger scale rather than same-datacenter. You'd probably also lose a lot of the latency gains though.
zb 10y ago
Probably not. It depends on guaranteed in-order packet arrival. In general the Internet very much does not guarantee that, so you would need control over all of the networks involved. Of course you can always tunnel over TCP (you need to tunnel over something, because you can't route multicast over the Internet either), but that would almost certainly eliminate the performance benefits.
altendo 10y ago
I'm in agreement with the other replies here - this seems more useful within a datacenter (and any unit smaller than that, such as an AWS Availability Zone) and not so much useful over the general internet. Too much unpredictability in how things get routed, what types of routers are hit, etc.

toolslive 10y ago

There are other consensus algorithms that start with a monotonous channel (ie a channel that might drop messages, but does not reorder them). Mencius fe does this and also avoids most of the overhead http://www.sysnet.ucsd.edu/sysnet/miscpapers/mencius-osdi.pdf http://www.sysnet.ucsd.edu/sysnet/miscpapers/mencius-osdi.pd...