Bizur: A Key-Value Consensus Algorithm for Scalable File-Systems
arxiv.org
arxiv.org
It's half true. Paxos is an ambiguous term. It includes Multi-Paxos and Single-Decree Paxos (aka Synod). The first one is a log based algorithm, while the second is a just a register. So your critic is valid only for the first part of the Paxos family.
Actually, Bizur is very similar (almost indistinguishable) to Single Decree Paxos - just compare it with the algorithm described in the video [1] by Heidi Howard or in my post "In search of a simple consensus algorithm" [2]
So just replacing bizur' should "register" implementation with a single decree paxos won't be sufficient. You'll need to do something more elaborate (creating more instances as you go along).
This kind of instance management isn't required in bizur.
I'm not sure what's the overhead off all that, w.r.t. memory foot print. Since this overhead is paid for each bucket, it might accumulate to quite a bit.
Proof of the algorithm: http://rystsov.info/2015/09/16/how-paxos-works.html
Moreover, I built a system on top of it and extensively tested it with fault injections: https://github.com/gryadka/js.
It seems that GoshawkDB[1] uses the similar idea, Treode[2] used it too.
It's wrong. Etcd provides "?quorum=true" option which makes reads go through the Raft consensus algorithm archiving linearizability see https://github.com/coreos/etcd/issues/741
Also I believe the authors of the paper tested against the old etcd v2 API/backend although they use etcd3.
The new API/backend has significant high performance.
I work on etcd.
For etcd benchmarking we used the 'benchmark' tool from etcd's source (commit d62ce55, ~3.1.0-rc1). AFAIK that tool does use the v3 api.
The paper was completed before etcd 3.1 was released. etcd's docs stated (at that time) that the client is not linearizable. We only tested writes.
As for performance, it's hard to say if our results pair up with the official etcd results (we were not aware of them - were they published at the time?). The hardware & software setup used for benchmarking is different.
But that might impact performance quite bit depending on your workload.
Suppose a server X was the leader, and subsequently a new leader was elected without X's knowledge. X does not learn of the new election unless it attempts a write. Until then, the read side may not detect the situation either since EnsureRecovery may return true (the bucket being read has the same elect_id as X.elect_id. Thus reads may return stale value. What we have here is "sequential consistency at the bucket level". which technically is cache consistency.
Separately, because the consistency claims are at a key/bucket level, and since there is no claim to global ordering (between different keys), a comparison to Zookeeper is not quite fair. Bizur cannot be used as a coordination service because it isn't sequentially consistent overall.
[1]: Ezra N. Hoch, Yaniv Ben-Yehuda, Noam Lewis, Avi Vigder
If it's true then it looks very suspicious that avg. latency decreases as the number of concurrent clients goes up. How do you measure avg. latency?
Let me illustrate what the avg. latency usually means.
Imagine that we have two concurrent users: Alice and Bob. During the testing lasting one second, Alice managed to send 3 requests per second, the first request took 0.5 seconds while the rest were executed in a quarter of a second each. In the same time, Bob did only 2 requests, each of them took 0.5 seconds.
So the average latency is the sum of execution time taken by each request divided by the number of all requests, in our case it's (0.5+0.25+0.25+0.5+0.5) / 5 = 0.4
Did you use the same definition?
1. Add a system model description under which your protocol is expected to operate.
2. Add description of fault-tolerant properties of the protocol.
3. Do you plan to prove correctness of the algorithm more formally? Maybe you could model the algorithm before publishing. If you prove a safety property using model checking it could considerably reduce doubt about an algorithm correctness.
As for #3, unfortunately we don't currently have plans to publish a formal proof (we're building a product). Some of our internal documentation is more formal, but we decided on a more readable presentation for this paper.
Unless you already have it but don't plan to publish, which seems a little odd to me. I get that you want readable documentation, but at least you could link to it somewhere for people who go digging.
On the other hand a logical model can be encoded in a rather short amount of time by someone who is doing it periodically.
This hypothetical guy could benefit from this activity by co-authoring the paper. Original authors would benefit from it by reinforcing both the protocol and the paper.
Please correct me if read it wrongly.
If you can sacrifice consistency (causal instead of external), you can get EPaxos. If you can sacrifice more, you can get Single Paxos. Both of them can increase concurrency to some degree, and can improve availability over a leader based RSM system like Muti-paxos or Raft.
I believe there are other ways to make the trade-off, even making the trade-off dynamically. Hopefully, I can talk about it more soon.
I work on etcd/raft, which is a shared Raft implementation by TiDB(TiKV), Cockroachdb, etcd and many more.
What do you mean? Single Decree Paxos is linearizable so it's consistent. When the multi-key updates are necessary - they can be implemented with client-side transactions such as 2PC, RAMP or Percolator.
Even with Raft we in the same situation. Once the data overgrows the size of one machine we need to shard them. As a result some keys can live on different shards and we need cross shards transactions to do multi-key updates :)
If you choose things like Raft (or other RSM), you can get a consistent key space to do txn over keys.
For a metadata store like etcd, one RSM group is OK. Performance/availability is better than something requires 2PC.
For database systems, there are quite a few txns that can actually fall into one shard and can bypass 2PC.
Of course, it is highly depend on the workload and use cases.
1) The atomicity usually isn't a problem, it can be added on top of the sharded storage with 2PC, RAMP or Percolator transactions, or with Sagas.
2) With Raft you have to implement log compaction and snapshotting, with Bizur and Single-Decree Paxos it isn't the case
Bizur buckets can be very small (10s of kb), and the overhead for them is minimal (10s of bytes).
What would be the overhead of having a raft group for every 32KB? Would it be practical / a good use of the machine's resources?
Also with most system like Raft a failed machine trying to rejoin the cluster does not need to download the complete transaction log but can instead download a snapshot of the state machines then load log entry created after this snapshot.
Another aspect is that if the bucket contain a large number of key. From the Bizure paper it seem that the complete set of "key->value" need to be sent to replica each time the bucket is updated instead of only the entry that changed. This would produce much larger network traffic compared to Raft or Zab when all replica are mostly in sync
2) In Bizur, rejoining the cluster includes the equivalent of copying the snapshot. However, that node can start participating in the Bizur even before it finished reading the entire snapshot, because of the key-value data model. Once a bucket has been copied, it can start serving it, which is much faster than log-based algorithms.
3) You are correct about the size of a bucket. In our implementation we aim to have up to 8-10 keys in a bucket, to avoid the overhead you mentioned. That's why it's especially important to be very efficient pet-bucket (see point #1).
In most file systems, you can't even update a file atomically, actually -- what you can update atomically is a disk page, 4-16k. Database servers might then maintain a separate, small file that contains only a transaction token, which is atomically updated to contain the last transaction written to disk in full.
More generally, any solution that doesn't require transactions across multiple keys, can use Bizur instead of classical Paxos, and achieve the same benefits (faster recovery from failures, higher concurrency, etc.)