Gryadka is not Paxos, so it's probably wrong
tschottdorf.github.io
tschottdorf.github.io
Thank you for the analysis of my post but it seems that you didn't get it correctly. Even to read a value you have to execute the full cycle (prepare, accept) of consensus (in the case of the stable leader we can skip prepare), so when you read the nil value the state of the system will be:
A: (value=foo ballot=1 promised=2) B: (value=nil ballot=2 promised=2) C: (value=nil ballot=2 promised=2)
Not the one you mentioned in the post:
A: (value=foo ballot=1 promised=2) B: (value=nil ballot=0 promised=2) C: (value=nil ballot=0 promised=2)
So the counter example is incorrect.
I proved the algorithm mathematically by hand and used very aggressive property based testing with fault injections so I'm pretty confident in its correctness.
I think it makes a slightly stronger argument about MultiPaxos than it needs to. There are other correct ways to use single-decree Paxos, as long as you recognize it's limitations. The true limitation is "use every register once", and a log is the gold standard way to do that. Another correct pattern could be a set-only K/V store, or a store for monotonic finite state machine states (at the cost of O(N) rounds for every contender). One real-world example is 2PC coordination, where the state machine is very simple, and can be modeled as an ordered pair of three registers.
Also from the "variants of Paxos" department is Flexible Paxos (https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...) which changes the rules about how to select a quorum.
The repo includes a TLA+ model too, which will hopefully become a trend in newly proposed distributed systems in the future!
Cassandra looked into implementing it, and reached a prototype implementation with ~60% better performance, but it looks like the contributor didn't continue driving it: https://issues.apache.org/jira/browse/CASSANDRA-6246
"every consensus protocol out there or every fully distributed consensus protocol is either Paxos or Paxos with cruft or broken" - Mike Burrows
Is it possible to get compare-and-swap without the log?
TL;DR: I don’t think so.
Riak Ensemble is such a system that utilizes single-decree Paxos in order to try to achieve CAS: https://github.com/basho/riak_ensemble
If the only the distinguished leader is allowed to publish a proposal for value change, then this allows you to preserve the CAS invariant. Unfortunately, this comes at the sacrifice of liveness. If you then have a second Paxos group to elect the leader, then this removes the liveness issue. On view change, you have to contact a quorum of nodes, and re-propose a new epoch in order to avoid issues.
I'm curious if someone can poke a hole in riak_ensemble's algorithm.
Always running an ensemble of three or five nodes for each shard seems to be pretty overkill (and expensive, both in terms of money and latency), especially if it's mostly just a way to do automated failovers. I sometimes wonder if there's a good-enough cheaper semisync alternative.
It doesn't need to be incredibly performant. Its role is merely to unify the topology. Various services can use whatever strategy best fits the problem. But you have to be able to register and find those services first.
Of course, there are dozens of projects that attempt to provide this functionality, but none are plug-and-play AFAIIK, not yet. I shouldn't need a config file, or any kind of configuration except maybe a couple of DNS records to bootstrap discovery and a path to a certificate authority. There shouldn't be _anything_ that a sysadmin could fiddle with.
A long time ago (almost 10 years) I wrote something like this using BerkeleyDB replication. (I think it was basically Raft long before Raft was written down and formalized.) It was a replicated backing store for BIND. All you provided the daemon was the name of a SRV record, a certificate authority, and signed public key credentials.
It wasn't complete. BerkeleyDB left initial replication of bulk data up the user, and I never completely finished that work before the startup ended. And there were some other problems left unsolved and unexplored. Plus BerkeleyDB wasn't completely multi-master like EPaxos. But the basic system worked: firing up and shutting down nodes was trivial and seamless.
The database was itself the backing store for an authoritative DNS zone which registered the distributed nodes used for a tunneling/proxy network. (Not a botnet ;) (Think Cloudflare + Sling + ...) To access a slave node you just queried it's SRV record, which gave you the location of the gateway. If the slave node disappeared and reappeared at another gateway address (because of a network hiccup), that was fine: logical streams were multiplexed over the transport channel(s).
And there was also a separate service that gateway'd external HTTP requests, so external software didn't have to understand the internal protocols. Using A records and HTTP redirects clients were usually directed to the node terminator node for the tunnel, to reduce internal network traffic, but that was just a small optimization--everything looked the same no matter your ingress or egress points.
The thing was, this was a _completely_ flat architecture. Every node provided each and every service, backend and frontend. Growing and shrinking the network was trivial, as was building the machine images. Testing and development was easy, too, because absolutely _everything_ hung off a DNS zone. The only necessary bit of configuration was providing the signed X.509 certificate for a node with an embedded ID and hostname. Because I was using SRV records which provided port numbers, you could run multiple nodes on a single machine during development.
It wasn't a perfect system, and it was incomplete. But I did this in just a couple of months, from scratch, alone, and while writing other components, long before all these other projects came out. And my solution was much easier to manage. I'm nowhere near as smart, experienced, or capable as many of the engineers on these modern projects. I don't understand why all the solutions suck.
CockroachDB seems like the best candidate, but of course they're providing much more capability than is necessary for a naming service and are still immature. etcd seems like one of the most mature, but it fails in being zero maintenance, which is like the most important part. The others are generally much too complex in almost every respect. Though I have to admit I haven't been following the space very closely.
Reality is that if you need to hit 5+ nines and require strong consistency guarantees (like "we never lose our customer's data") at data center scale, you'll probably need something similar. Most people probably don't need those guarantees, however.
I see why Google built Megastore, Spanner, etc. And sure, ZooKeeper or etcd makes sense for putting small amounts of configuration data.
But most of us aren't Google, and synchronously replicating the entire OLTP database, 3 or 5 nodes times the number of shards, seems kind of absurdly expensive for most people.
tl;dr2 when you read "Paxos" or "distributed"-anything just assume it's a bunch of nerds arguing about theoretical problems inside a box
Recap of those wiki pages:
- Consensus is many different ways to solve similar problems, all of which involve agreeing on a solution, to different degrees.
- The two-generals' problem is a proved unsolvable problem that says you can't know what two generals are going to do if you have no way to prove communication between them is valid (or happens at all).
- Byzantine faults are basically the same thing, but 10 people instead of 2.
- Paxos is a bunch of ways of proving various degrees of different kinds of consensus with different uses that works most of the time. (also known as "the algorithm family that comp sci majors keep trying to improve on, but then a genius points out that any changes make it work differently, and therefore must suck")
Why do we care? So you can use 5 servers all around the world, store random messages on them, and be sure that a bunch of them have the information you want, that it is correct, that it will still be available somewhere if one of them goes down, and that if one comes back up with shitty data, it will get corrected and become good data again.
The reason why this is hard is we assume that the messages:
1. have no CRC (integrity, "this data is not corrupt")
2. or digital signature (integrity+authenticity, "this message is not corrupt and definitely came from Bob")
3. and that even if they did, it could have been 3a. "wrong" before it was signed, or 3b. "faked" so that we can't tell when a CRC or sign is correct,
4. or the message never arrived,
5. or that random valid messages have been saved on one server and that when it rejoins the group it now has data that, regardless of it being good or bad, we don't want in the rest of the pool of servers because now the rest have to incorporate it, and what if there are conflicts
The Paxos algorithm family seeks to solve most of this in one go, with exceptions.
Do you need Paxos to solve all those problems? No. Do you need it to solve those problems in the theoretical boundaries of comp sci nerds? Yes. Do you need to know how it works? No. Are there situations where a Paxos network can simply stop working? Yes. Do you need to use Paxos for something you're working on? Probably not. Is it possible Paxos will not solve your problem? Yes. And do you still need plans to back up and restore your data in the event of catastrophic failure? Definitely.
The only paper that I know of currently that I would recommend anyone to read on byzantine failures and their solutions is this one: https://www.cs.indiana.edu/classes/p545/post/lec/fault-toler...
(Granted, I don't know what I am talking about, so take all that with a grain of salt)
I suppose "It's not Paxos, so it's probably wrong" is beyond discussion (not that I disagree, of course).
Is Bitcoin Paxos?
Consider the simplest case: 1/2 of bitcoin users/miners are temporarily split off from the other half, for say a week (all atlantic/pacific fibers are broken at once, all satellites fall out of the sky, other huge catastrophes occur all simultaneously). Each half would append their own blocks to the blockchain happily, and depending on the chain lengths added, once the partition went away there would be no good way to reconcile. Thus: not consistent in the face of partitions.
Why do you say that? The chain with the greatest total difficulty wins.