News for hackers. Stuff that matters.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by fernly on Friday October 19, 2018 @01:46PM (#18258506)
The concept of the "global log" is mentioned many times in the article, but not much detail on this critical piece:

> ... the consensus protocol is only being used for inserting transactions into a global log. For every other part of the protocol, replicas can proceed completely independently from each other.

Clearly this central resource can't be distributed or replicated. Right? So it, and the hardware it runs on, and the communications links to it, are a single point of failure. True?

If the global log goes down, or can't be reached at all, or perhaps only from some region of the regionized application, what happens?

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @01:58PM (#18258611)
You are correct that they serialize cross-partition transactions. So if your workload has a reasonable percentage of write/update/delete operations it is possible that you will bottleneck on the global coordinator. From this blog https://fauna.com/blog/distributed-acid-transaction-performa..., you can get 3300 transactions/second. Daniel Abadi claims you can get to 500,000 trans/sec - http://dbmsmusings.blogspot.com/2018/09/newsql-database-syst....

In any case, there is an open-source in-memory database called NDB (MySQL Cluster) that can get to 100 million write transactions per second. The echo chamber of SV has ignored it, but it's real: http://mikaelronstrom.blogspot.com/2015/03/200m-reads-per-se...

NDB has what i call lock-aware programming. When you read a row, you take either a read_lock or a write_lock, as it only supports READ_COMMITTED isolation level. But, it does not serialize cross-partition transactions. Transaction coordinators run independently, and it is up to the developer to ensure consistency by taking either read or write locks on rows.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by evanweaver on Friday October 19, 2018 @03:20PM (#18259228)
Serializing cross-partition transactions is known as "external consistency" or "strict serializability"; that's what this game is about. The illusion of total order. :-)

There is no single node that serves as a global coordinator. The "coordinator" as referred here is a stateless logical role for each transaction and every node in the cluster can do it on an ad-hoc basis.

Our current performance numbers are much better but we don't have anything published quite yet. The bottleneck, so to speak, is the distributed, partitioned write-ahead log which is implemented in a pipelined version of Raft. It is not materially different than the Paxos or Raft-based rings that support replicas in aa Spanner-style leader-per-tablet two phase system. However it has better long-tail latency because a fixed subset of nodes resolves transactions instead of every leader regardless of location, and it is not subject to write skew across disjoint transactions.

We are well aware of NBD. NBD is not designed for WAN latencies, and like you say, it pushes consensus complexity onto the developer. Certainly it is easier to reach higher theoretical throughput numbers when you do less work on faster hardware. I admire NBD but it doesn't make sense to compare a WAN system with a higher consistency guarantee to a LAN system with a lower guarantee.

Fauna will support multiple consensus regions in the future to uncork aggregate throughput, at the cost of some explicit optimistic consensus across region boundaries. This is still a better story than explicitly locking on a read-committed isolation level which is subject to read and write skew in a way that cannot be architecturally overcome, even with locks.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by tongcx on Sunday October 21, 2018 @11:51PM (#18272058)
I'd like more detail on the "coordinator". Seems all cross-partition transactions need to be serialized into a global ordering (via consensus algorithm?). So why this isn't a bottleneck?
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @03:51PM (#18259487)
But spanner uses 2pc for cross partition transactions and paxos within a partition. There's no global coordinator service there.

Dont get me wrong. I think Calvin/FaunaDb is great as an alternative to Spanner for multi region Dbs. But strict serializability is not a goal for all systems and certainly not for high performance distributed systems that can provide their own concurrency models. Not just HopsFs, but any system layered on top.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by evanweaver on Friday October 19, 2018 @03:55PM (#18259529)
There is no global coordinator "service" in FaunaDB either. The "coordinator" is a stateless function on available on every node. The log is a stateful, logical function implemented in Raft, so no different than a Paxos ring in terms of failure modes and high availability.

Think of it as a way to scale a single Spanner tablet to support the entire dataset and eliminate the 2-phase commit, as well as the associated write skew or clock ambiguity window.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @04:09PM (#18259629)
Paxos/raft is an agreement service where nodes agree on entries in a single log. I have no problem calling it a distributed/global coordination service for agreeing on entries in a log.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jchanimal on Friday October 19, 2018 @02:10PM (#18258704)
The log segments committed by FaunaDB contain batches of transactions, which means our throughput is constrained not by our consensus protocol, but rather by conflicts as transactions are resolved. The benchmarked 3300 transactions/second mentioned is for complex transactions with dozens of reads and writes. Additionally, read-only transactions are not run through the transaction pipeline, since they can be served consistently with low latency from replicas using FaunaDB's snapshot storage.

More important for most applications than theoretical benchmarks is taking a sound approach and using a database you can depend on. Asking your development team to manage isolation is going to introduce more costs than benefits, except in the most specialized of circumstances.

FaunaDB's model is always ACID, so you never have to guess what's in the database, even in the presence of region failures or other anomalies.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @02:19PM (#18258776)
We built HopsFS on NDB, not CalvinDB, because we needed performance for cross-partition transactions. Some workloads need it. In the filesystem workload, when FS path components are normalized and stored on different partitions, practically all transactions cross partitions. So if you serialize them, then writing a file in /home/jchan will block writing a file in /home/jim. This is what most distributed filesystems already do - have a global write lock on the filesystem metadata. I like having the freedom to build my the concurrency model on top of READ_COMMITTED, as i can squeeze out 16X performance improvemnts by doing so (ref: https://www.usenix.org/conference/fast17/technical-sessions/... )
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by evanweaver on Friday October 19, 2018 @03:26PM (#18259287)
Sure, if you don't care about serializability, you don't need to pay consensus costs to enforce it, but you will be subject to read and write skew.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by notacoward on Saturday October 20, 2018 @11:54PM (#18266659)
> This is what most distributed filesystems already do - have a global write lock on the filesystem metadata

Absolutely untrue. Stop lying about other systems.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @02:29PM (#18258854)
I should add that when you don't serialize cross-partition transactions, you have the hard problem of system recovery - transaction coordinators need to reach consensus on a consistent set of transactions to recover. Here's NDB's protocol for doing so: NDB’s solution to this problem was only published this year in Mikael Ronstrom's book on MySQL Cluster : https://drive.google.com/file/d/1gAYQPrWCTEhgxP8dQ8XLwMrwZPc...
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jamesblonde on Friday October 19, 2018 @02:46PM (#18258979)
I should add that it is not correct to say 'our throughput is constrained not by our consensus protocol'. A trivial example would be a workload of transactions, where each transaction has at least two non-conflicting writes on different partitions. FaunaDB will serialize those transactions, and you will bottleneck on the consensus protocol - compared to NDB.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by ummonk on Sunday October 21, 2018 @12:51PM (#18268849)
What he's saying is that the throughput number they mention is constrained by transaction conflicts. The limit for non-conflicting transactions allowed by the consensus protocol is no doubt much higher.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by mcguire on Friday October 19, 2018 @05:24PM (#18260172)
Can you partition your batch transactions, so that all up to the conflict succeed?
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jchanimal on Friday October 19, 2018 @06:15PM (#18260494)
My understanding is yes, we commit to the log in batches, but abort conflicts at the transaction level. So only the conflicts have to suffer the retry loop, everything else is durably committed.
Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by evanweaver on Friday October 19, 2018 @03:21PM (#18259231)
The "global log" is a logical component. It is a distributed, partitioned write-ahead log which is implemented in a pipelined version of Raft.

It is both distributed and replicated, even across datacenters, depending on topological configuration.

We will update the post to make this more clear.

Re:Consistency Without Clocks: FaunaDB's Distributed Transac... by jchrisa on Friday October 19, 2018 @01:55PM (#18258583)
The global log is replicated using a Raft-like consensus mechanism, so that all replicas have a copy of the log, and agree on its order. So even if one replica site is lost, the others have a full copy of the log, and can continue.

You can learn more about Raft from this excellent visualization: http://thesecretlivesofdata.com/raft/