Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

fauna.com

Post reply on HN
Print view View original

31–40 of 105 posts

Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

#31

Post by jamesblonde »

jchanimal wrote: post #22
jamesblonde wrote: post #20

Earlier 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 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 Transaction Protocol

#32

Post by evanweaver »

jamesblonde wrote: post #20
fernly wrote: post #16

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,…

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…

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 Transaction Protocol

#33

Post by evanweaver »

fernly wrote: post #16

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,…

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 Transaction Protocol

#34

Post by evanweaver »

jamesblonde wrote: post #24
jchanimal wrote: post #22

Earlier quoted context omitted.

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 a…

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 Transaction Protocol

#35

Post by wmf »

EGreg wrote: post #27

This 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.

A BFT database is called a blockchain.

Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

#36

Post by evanweaver »

ummonk wrote: post #19
evanweaver wrote: post #2

We're here, ready for your questions to be consistently replicated across the WAN at the lowest latency information science allows ;-)

Not a database person, so I might be missing context, but why is FaunaDB the only implementation of this? Intuitively, it seems to be exactly the way I would do a distributed database - distributed transactional storage with a global ordering of transactions that are based on ids rather than timestamps. The only thing that I wouldn't intuitively come up with is the actual consensus algorithm, but that already existed…

Everybody wants to copy Google apparently; there are a variety of Spanner or Percolator clones although some of them do not meet the original guarantees of their reference systems.

FoundationDB also forged its own path and is worth studying.

Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

#37

Post by evanweaver »

voidmain wrote: post #26
evanweaver wrote: post #7

Earlier quoted context omitted.

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 reg…

Very interesting. People really care about latency so we are also look at more datacenter-local journaling schemes that maintain consistency at the expense of a theoretically unlikely hit to durability.

What do you mean, "active datacenter"? Can all datacenters accept transactions concurrently?

Re: Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

#38

Post by jamesblonde »

evanweaver wrote: post #32
jamesblonde wrote: post #20

Earlier 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…

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 bett…

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 Transaction Protocol

#39

Post by evanweaver »

jamesblonde wrote: post #38
evanweaver wrote: post #32

Earlier quoted context omitted.

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 bett…

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 s…

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 Transaction Protocol

#40

Post by kerneltime »

Apologies, I quickly skimmed the blog but in the summary did not see clear answers for: When is the transaction acked? What is the reader-writer consistency? If the transaction is acknowledged only after speculative work is validated after ordering, what is the value add for doing the speculative work? Would you achieve similar benefits from just batching commits?
Post reply on HN