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

91–100 of 105 posts

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

#91

Post by evanweaver »

evanweaver wrote: post #85
andydb wrote: post #82

Earlier quoted context omitted.

Sorry to put you on the spot. Perhaps your CTO can chime in when he gets back. Serializable tends to sound really good to database people, because it's the "highest" isolation level available in most databases. However, those databases are built for a single machine, and they really offer "strict serializable" without calling it that, because they maintain a single log which serializes all writes, and all reads opera…

Having the read information sent from one location (presumably where the write occurs) and then read from another is a good example of one of the few times this anomaly can occur. I think it's a stretch to say that including a single timestamp in the link is too hard for developers. It happens by default across queries within a process with the Fauna drivers, so the database is preventing it; the only place you have…

Also: please email us! It would be great to talk further.

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

#92

Post by hardwaresofton »

rystsov wrote: post #80
hardwaresofton wrote: post #79

I've come to the realization that sharding might be the only way to actually scale multi-master systems without allowing stale (or potentially outright wrong) reads. Sharding is complex and makes parallel queries a requirement but it really does seem like the only way to distribute a database. In the end, once you have the op log on more than one machine, they're going to have to synchronize with each other, otherwis…

CRDT may help: if you read from quorum, merge(+modify) and write back to quorum for read (write) then you'll always get right answers.

I'm not sure if I'm understanding what you're suggesting right, but it sounds like you're just quorum-ing for everything. You shouldn't need improved merging if you quorum both reads and writes, since it implies the majority agreeing on the contents of the log to begin with.

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

#93

Post by EGreg »

jchrisa wrote: post #30
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.

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

I think BFT can be added as an option to your database and it wouldn’t need refactoring any other part of the database. Just have crypto signatures and the log would need to use BFT consensus with a quorum before committing. May be worth it at least for marketing purposes, but also for multiple mistrusting parties jointly running the database. You’ve done so much already, may as well benefit from this addition!

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

#94

Post by notacoward »

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…

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

#95

Post by ummonk »

jamesblonde wrote: post #31
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…

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.

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

#96

Post by evanweaver »

hardwaresofton wrote: post #92
rystsov wrote: post #80

Earlier quoted context omitted.

CRDT may help: if you read from quorum, merge(+modify) and write back to quorum for read (write) then you'll always get right answers.

I'm not sure if I'm understanding what you're suggesting right, but it sounds like you're just quorum-ing for everything. You shouldn't need improved merging if you quorum both reads and writes, since it implies the majority agreeing on the contents of the log to begin with.

Quorum/quorum does not guarantee agreement or serializability even for a single key.

Imagine a write that commits to one replica but is delayed committing to two others. Some quorum reads will see it (but also see a tie with the old value...what breaks the tie? Certainly not a timestamp) and others will not see it at all, indefinitely.

It’s easy to end up in a state where every replica has a different value because of torn writes.

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

#97

Post by tongcx »

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…

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

#98

Post by hardwaresofton »

evanweaver wrote: post #96
hardwaresofton wrote: post #92

Earlier quoted context omitted.

I'm not sure if I'm understanding what you're suggesting right, but it sounds like you're just quorum-ing for everything. You shouldn't need improved merging if you quorum both reads and writes, since it implies the majority agreeing on the contents of the log to begin with.

Quorum/quorum does not guarantee agreement or serializability even for a single key. Imagine a write that commits to one replica but is delayed committing to two others. Some quorum reads will see it (but also see a tie with the old value...what breaks the tie? Certainly not a timestamp) and others will not see it at all, indefinitely. It’s easy to end up in a state where every replica has a different value because o…

Sorry, I think either my fundamental understanding is off or I wasn't clear enough in how I was imagining this happening...

If you and a majority of nodes agree on a value like an CRDT OpSet (more simplistically, just agreeing on the state of the log), how does that not guarantee agreement and serializability? It is impossible from that point on to have a another majority of nodes have some other view of what happened. Consensus algorithms are

One copy serializability is exactly what would be achieved by having a read and write quorum[0][1]. It intuitively makes sense to me (and maybe my intuition is wrong), but if you talk to a majority of nodes and ask "this is what we all have, right?" before every write and every read, you've got a guaranteed consistent (of course, progress isn't guaranteed if partitions/nodes die, etc) state.

AFAIK Quorums are the state of the art (and arguably the only relatively efficient option) as far as achieving serializability in a distributed system...

[0]: https://en.wikipedia.org/wiki/Quorum_(distributed_computing)...

[1]: https://arxiv.org/pdf/1406.7423.pdf

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

#99

Post by evanweaver »

hardwaresofton wrote: post #98
evanweaver wrote: post #96

Earlier quoted context omitted.

Quorum/quorum does not guarantee agreement or serializability even for a single key. Imagine a write that commits to one replica but is delayed committing to two others. Some quorum reads will see it (but also see a tie with the old value...what breaks the tie? Certainly not a timestamp) and others will not see it at all, indefinitely. It’s easy to end up in a state where every replica has a different value because o…

Sorry, I think either my fundamental understanding is off or I wasn't clear enough in how I was imagining this happening... If you and a majority of nodes agree on a value like an CRDT OpSet (more simplistically, just agreeing on the state of the log), how does that not guarantee agreement and serializability? It is impossible from that point on to have a another majority of nodes have some other view of what happene…

> If you talk to a majority of nodes and ask "this is what we all have, right?"

You cannot know this, because the transaction replication is racy and not atomic--it may have applied to only one node while you are doing your read. Whether you see it or don't is luck. So you can have the following scenario (and in practice you will):

- TX commit begins

- TX replicated to node A

- Read from coordinator A' begins

- Read sees replica A (has tx) and replica B (does not)

- Read assumes A wins because of some kind of vector clock in the data value (choosing the older value doesn't make things better, just in case you are wondering)

- Read from coordinator B' begins

- Read sees B (no TX) and C (no TX)

- Read completes with stale value--serializability violation has occurred

- TX finishes replicating to B and C

This leaves aside write skew, torn transactions due to partitions, and all kinds of other problems.

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

#100

Post by jchrisa »

EGreg wrote: post #93
jchrisa wrote: post #30

Earlier quoted context omitted.

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

I think BFT can be added as an option to your database and it wouldn’t need refactoring any other part of the database. Just have crypto signatures and the log would need to use BFT consensus with a quorum before committing. May be worth it at least for marketing purposes, but also for multiple mistrusting parties jointly running the database. You’ve done so much already, may as well benefit from this addition!

We have a roadmap item to add blockchain style tamper evidence to the storage engine. The crypto we'll use is certainly a step along the path you describe. If you have a use case, we love talking to developers to help make sure we are building features you can use.
Post reply on HN