An implementation of the Speculative Paxos protocol | Hacker News Reader

An implementation of the Speculative Paxos protocol

github.com

57 pointsdrkp15 comments

Le sigh, multicast. A great example where software engineering crosses over to the physical realms.

When a router receives a packet destined for a multicast group and that router has multiple destinations for that pocket, it must store that packet in memory until the last interface associated with that group can be written to. On networks which aren't heavily used that's not problem. Once you start utiziling your network however, the routers will be busy storing packets and their sensible-for-simple-cases buffers will become overwhelmed and you've got a multicast storm on your hands.

Great on paper, even works in test setups. Call me when you're running your kit to the limits, and I'll let you know you have a multicast problem.

Wasn't the multicast storm issue related to the fact that most hardware implementations have limited-size Bloom filters that are used to manage subscriptions, and once they're full, they deliver every packet to everybody? Or is that an additional issue?

Why is it worse than sending a separate packet to each of the participants? If we're using multicast router can send packets to all participants in any order (when links become available) while storing one copy of it. If we're sending separate packets, either router has to store multiple copies of it in memory or it sends the packet to different participants in a constrained order.

Interesting concept but relies on multicast. SDN might help solve the inherent multicast drawbacks by creating topologies, distribution trees, etc.. ahead of time. But practically, how often do you see multicast deployed and enabled in modern datacenters ?

This would go very nicely with Aeron.

https://github.com/real-logic/Aeron

I like this as a niche (sub 100 node) solution to an interesting problem. I wonder how well this works over a MAN.

Use Raft. Rather than speculating, learn, do, and guarantee you're doing the correct thing by electing once, distributing, achieving quorum and continuing. This is spitshine on a turd - PAXOS is a great protocol, but not a speedy one. It's an important building block, not something to be running constantly.

This implementation is an optimization of leader-based protocols like Raft. It removes the leader from the critical path using SDN.

Raft is more-or-less equivalent to Paxos. Its protocol is more detailed but no more efficient than the core, original Paxos protocol.

More appropriately, don't implement these incredibly difficult protocols yourself - unless it's an exercise. Use one of the well maintained, widely used implementations.

If you took edX's Reliable Distributed Algorithms 1, you'd have implemented it in a few lines in Scala.

Well, in a few lines built atop kompics which is a simulation framework. (Multi) Paxos in particular is considered so hard to get right that no organization actually implements it to my understanding. They instead have their own flavor based on paxos. See zookeeper.

That's not really true at all. Basho (makers of Riak) have a multi-paxos implementation that is used in Riak. Riak_Ensemble:(https://github.com/basho/riak_ensemble)

Yes, that's the beauty of it - it deflects all the noise from you and you can focus on the essence of Paxos itself.

Instead of thinking how to write all the underlying abstractions yourself and likely drowning in them before you can understand what Paxos is about.

Surely, for production you have to deal with a different set of issues, like how many nodes can you handle at once before you need to send way too many messages, what happens if your socket gets full or unresponsive, what if you get into a distributed deadlock in some rare case (which always happens in production), how to recover from out of order messages, what if ACKs are missing but operation went through etc.

raft, view stamp replication, full active - active many writable nodes all have different tradeoffs in terms of the overhead. Basically it comes down to what is being replicated.

Reply on news.ycombinator.com