The global log sounds like a lynchpin but I didn't see a good explanation in the article. It sounds like all synchronization is done at the level of this log? If so, isn't that a bit of a bottleneck?
Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
21–30 of 105 posts
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#22The 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,…
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…
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 Transaction Protocol
#23I wish projects like this would publish their proofs with their protocols. It's interesting to be sure but I find all of the prose and diagrams to be too verbose. I'd much rather read the mathematical model of the transaction protocol.
You can read the paper that inspired the FaunaDB transaction protocol here: http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1... Or if you want a very concise description, see slide 13 from Daniel Abadi's presentation: https://www.slideshare.net/abadid/the-power-of-determinism-i...
Thanks for the links! I meant the actual proof or model they use to verify the protocol. Is the FaunaDB team using TLA+, Coq, Lean?
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#24Earlier quoted context omitted.
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…
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 co…
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 Transaction Protocol
#25Summary, taken from the article:
> To summarize the overall FaunaDB protocol, each transaction proceeds in three phases:
> 1. The first phase is a speculative phase in which reads are performed as of a recent snapshot, and writes are buffered.
> 2. Next, a consensus protocol is used (Raft) to insert the transaction into a global log, which results in the transaction receiving a global transaction identifier that specifies its equivalent serial order relative to all other transactions that are being processed by the system. This is the only point at which global consensus is required.
> 3. Finally, a check begins in each replica which verifies the speculative work. If that speculative work did not result in potential violations of serializability guarantees, then the work becomes permanent and the buffered writes written back to the database. Otherwise, the transaction is aborted and restarted.
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#26As an aside, can somebody explain the constraints FoundationDB puts on replica distance?
FoundationDB cannot currently replicate its transaction log across datacenters, either synchronously or asynchronously: https://forums.foundationdb.org/t/multi-dc-replication/499 In the discussed proposal datacenter failure is considered an extraordinary event with major performance implications, which is different than a global "write anywhere, read anywhere" multi-datacenter partitioned log model like Fauna.
FoundationDB has long supported both synchronous and asynchronous replication across regions, and its major users use multi-regional configurations. In the former mode, you will see 1xRTT latency for commits [1] from the active datacenter and 2xRTT latency for commits from other datacenters. In the latter mode, commits from the active datacenter are fast (0xRTT) but the durability property must be sacrificed if a region fails. I believe almost all users currently use asynchronous replication because the performance is so much better (than any geographically replicated synchronous database).
The new "satellite" replication model in FoundationDB 6.0 allows the best of both worlds: if you have two or more datacenters in each region (each storing transaction logs, but only one storing actual data) then you can do synchronous (0xRTT) commits to the regional datacenters and asynchronous replication to the other region(s). If there are failures in one region, the database can quickly and automatically fail over to the other region, while maintaining durability (by getting the last bits of transaction log from at least one datacenter in the failing region). Even if a whole region fails, as long as the failures of the datacenters and network links in it are spread out over time the database will complete a full ACID recovery. And in the worst case you can fall back to ACI recovery as in asynchronous replication.
The question you are linking to is asking about something different, the ability to have different parts of a single database have subgeographic latencies in different regions.
[1] You will also see 1xRTT latencies when you start transactions, but you can solve this by setting the causal_read_risky transaction option on all read/write transactions. This is not actually risky because if the reads in the transaction turn out not to be externally consistent, the transaction will not commit.
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#27This is very cool
But there is an even harder super boss level for distributed systems: Byzantine Fault Tolerance
Is FaunaDB Byzantine resistant? I have asked many projects, such as Dat, what happens if there are conflicts, and they haven’t built systems that are BFT yet.
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#28Earlier quoted context omitted.
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…
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 co…
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 Transaction Protocol
#29The global log sounds like a lynchpin but I didn't see a good explanation in the article. It sounds like all synchronization is done at the level of this log? If so, isn't that a bit of a bottleneck?
The log is distributed across the cluster, and can be partitioned. The protocol is optimized for long physical distances between replicas. See links elsewhere in the thread to Raft.
Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol
#30This is very cool But there is an even harder super boss level for distributed systems: Byzantine Fault Tolerance Is FaunaDB Byzantine resistant? I have asked many projects, such as Dat, what happens if there are conflicts, and they haven’t built systems that are BFT yet.
Our deployment model assumes a single administrator. With reasonable network operations, Byzantine fault tolerance is largely irrelevant. (Although it's an important problem in other contexts.)