Say No to Paxos Overhead: Replacing Consensus with Network Ordering
blog.acolyer.org
blog.acolyer.org
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.
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
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).
At any rate, most cloud SDNs don't support IP multicast (unless you use an overlay like Weave), so it's sort of a nonstarter for them.
These days I might use Redis pub/sub along with a multi-level cache (e.g. LMDB + local Redis + remote Redis) if I need to distribute data to a large number of clients efficiently.
You can, of course, use Rendezvous without multicast.
And: does anyone still use it? The last exchange I worked with that did was migrating from it to JMS (which sort of gives lie to the idea that Rendezvous's multicast performance was that big a deal).
Now that 10Gb+ is commonplace and modern servers can service hundreds or thousands of message bus consumers with efficient kernel-managed event loops, yes, it's arguably less needed now. But nobody will claim it's efficient from a network perspective. :)
Is well regarded & open source
https://www.nasdaqtrader.com/content/technicalsupport/specif...
It is actually quite good.
FWIW when you talk about different requirements, I'm not sure you're correct. For traders, sure, oftentimes they can just dump old data if they fall behind because it's mostly irrelevant. However, stock exchanges have performance and reliability/availability as top requirements. They must record all transactions and can't crash or lock-up. Most use multicast internally and externally. They would never be able to scale and maintain a low response time with TCP.
In a dynamic environment where you'd be scaling continuously and adding components and servers and building new services, this becomes a non-starter. Multicast implementations doesn't fail gracefully -- there's very little warning before things come to a complete halt and need complete shutdown and reboot of entire network.
(Honest question; I have no direct experience with multicast.)
Most TCP implementations handles it well and Linux has well written guides on how to tune parameters when the defaults don't match well to your specific situation well. Multicast just fails catastrophically in arcane ways that depend upon your specific hardware, network topology and mix of your firmware version on your switch/routers. It makes it very hard to "design" a product around that kind of fragile system.
When IGMP Snooping is enabled, the switches themselves will limit multicast messages only to ports that have actually joined a group, which prevents multicast storms (if I'm understanding you correctly) in the first place.
In the kind of environments I worked in, this was a non-starter.
edit: also "limit multicast messages only to ports that have actually joined a group" part is usually implemented by bloom-filters that I talked about above. They work well as long as there are not many groups and not many members.
I would be curious in your experiences if you're able to share it, but do very much believe there are options other than software for implementing multicast filtering on switches. What type of environments that you worked in made IGMP Snooping a non-starter?
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
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)
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.
Relations ~= Consensus (traditional full-featured Paxos)
To use your sentence
If you use NOPaxos, the consensus doesn't disappear. You just have to perform it whenever your sequencer, or replica-leader becomes unreachable/fails.
The "OUM primitive" addition isn't much more than two monotonically increasing integers (session and order-number) which depend on a central (bottleneck) sequencer... NoSQL moved the responsibility for relation-management up, NoPaxos is moving the responsibility for consensus down/to the worst case... My point was that neither are fundamentally different from the "X" after the "NO"...
SQL as language can have it issues but the relational model is far easier and more flexible than people assume.
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.
It this common? What cause this behavior?
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.
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.
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.
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.
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?
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.
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.
That's why I'm real cautious about debit cards.
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.
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?
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.
American perspective here—I feel safer using a credit card because it's not my money. If someone fraudulently bills my credit card, it's the bank that they're stealing from, not me. There are legal protections in place which limit my personal liability.
With a debit card, if someone fraudulently uses it, the money is gone and you have to fight to get it back. There are legal protections which limit my liability here too, but when I invoke those protections I'm starting from an inferior position (the money is already missing from my account), and those protections are a little better for credit cards.
Our accounts are also often reconciled with ACH, which is not as fast as it could be. So it's not always true that the transaction will be refused if you don't have the money. It's often true, but credit cards are safer because there's not really a penalty for going over your line of credit.
At the very least, I'd recommend that you have a separate debit card account that is used for store purchases and such. This gets filled (manually!) from another account which you also use only for really important stuff like utility payments, housing, car payments, etc.
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.