Live data from Hacker News

Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

fauna.com

71–80 of 105 posts

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

#71
post #67
post #64

Earlier quoted context omitted.

This is such a niche subcategory of distributed databases [1], that it's a miracle even a few of them exist and you want more implementations. Intuitively distributed systems try to avoid consensus/coordination, as doing those things over public internet is not that useful. [1] https://trends.google.com/trends/explore?date=2016-09-20%202... compare that to some other distributed database https://trends.google.com/tre…

The property that attracts the most mission critical use cases is the ability to keep transactions rolling without loss of guarantees, even while hitting the typical cloud failure modes. Some applications can't make tradeoffs between correctness and global availability, for them FaunaDB's mainframe-like capabilities are key. For the average application, the benefit is that you don't need to write code to address data…

Well, I don't expect distributed ACID transactions to ever become a thing developers expect. I see people try them, but leave unhappy because of the unexpectedly bad latency and performance. Hence the lack of growth in trends.

Furthermore, eventual consistency was never problematic, it was just a myth. It was never hard, certainly not harder than ACID transactions in all those MVCC systems. So not much to benefit from for an average application. And today with all the research in strong eventual consistency applications can have all that correctness without coordination and without sacrificing performance, latency and availability. This is where the opportunity for distributed databases still exists, performance and latency are sellable.

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

#72

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

optimistic concurrency control https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung...

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

#73
post #68

Earlier quoted context omitted.

Read-only transactions are serializable by default but can be upgraded to strict serializability, either from the perspective of a single client by passing a transaction timestamp that serves as a causal token, which is free and happens by default with our drivers, or globally, by opting in to the log at the price of additional latency.

But opting into the log for read-only txns would destroy performance for many apps, both in terms of latency and throughput. This is rarely practical since so many apps are read-heavy. I assume you don't recommend that to your customers, especially in global deployments. Causal tokens are practical from a performance point of view, but do require application awareness and changes, which presents a different set of is…

Really putting me on the spot when our CTO is out of town. My initial reply was ambiguous and appears to suggest that the transaction highwater mark/causal token preserves strict serializability. It preserves serializability. Strict serializability requires the log.

Let me try to explain more clearly and you tell me what you would call it. It is subtle because there are three coordination points, the log, the replica, and the client.

The log is marching along, moving time itself forward. Every node within a replica is following the log monotonically for a disjoint set of partitions. Every client process is querying an arbitrary and changing set of nodes within a replica, which is normally a datacenter.

Every node in every replica maintains a highwater mark (the causal token) of the last transaction time it has applied. Every client does the same, and keeps a highwater mark of the last transaction time (read or write) it has seen. If it was a write, the highwater mark came from first replica to apply the transaction from the log. If it was a read, it came from the local replica based on the last applied transaction time that node has personally applied.

These transaction times are passed back and forth with every request, from client to replica and back, automatically by the Fauna drivers. Thus, a replica node will block if a client performs a read-only transaction presenting a transaction time which it has not yet replicated from the log. And if a client receives a later time from a replica or from the log, it will update its local highwater mark so that its view of time (and thus its key set) can never backtrack.

1a. If the client process is long-lived and maintains the highwater mark, then it is guaranteed to read its own writes and maintains serializability (but not strict serializability) for all keys on all partitions that own any keys it has queried via log write or local read. Even if the write acknowledgement comes from another replica, the highwater mark is still advanced and any local read partitions will block until they have replicated beyond that point. A stateful webserver would maintain the highwater mark internally across requests.

1b. If the client process is not long-lived (a Javascript call directly from a browser, for example, which is possible with FaunaDB's security model), then you will still read your own writes as long as you do not accidentally switch replicas e.g. datacenters because there is only one node per replica that owns any specific key. In practice, switching datacenters during a client session is a pathological edge case. The most likely scenario would be that the client performs a write, receives a commit acknowledgement from a remote datacenter, discards the transaction time, queries the locally partitioned node for the key it just wrote, and does not see the update. This could be eliminated by threading replica affinity through the entire write/read cycle.

2. Stale reads from partitioned nodes are no different than increased client-server latency, because if the client can write, it will receive a higher transaction time, and its subsequent reads will block and timeout, preserving the serial order of operations. If it doesn't write, as far as it is aware, time is just running a little slow, and the data will be stale from an external consistency perspective, but order will be preserved. This is a violation of strict serializability but not of serializability. In this case if the client switches datacenters, it will read or write and get an updated transaction highwater mark, and will no longer be able to successfully read from the partitioned node because it knows about the future now.

I should note that Spanner-derived systems typically offer some variant of serializability or worse for read-only transactions since nobody wants to wait around for the clock ambiguity window to expire. Spanner itself can wait, but it still comes at a cost, and Spanner goes out of its way to offer bounded staleness reads that are low latency but do not meet any serializability guarantee at all, as far as I can tell.

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

#74

This is a weakness imo: `client.query( q.get( q.match( q.index("posts_by_title"), "My cat and other marvels" ) ))` That you have to specify the index in a query is a regression imo at least I've been spoiled by not having to have to do so in when using Mongo or SQL databases since the query engine will more often than not find the right index.

This a design choice to guarantee predictable performance at scale, not an architectural limitation, and subject to revision. You don't want your service to collapse when the query optimizer suddenly doesn't choose the right index anymore. That was a hard lesson learned for us at Twitter.

Another interesting approach is the way Google Cloud Datastore/Firestore works. The query engine will only allow queries that scale and can happen in a single contiguous scan of an index range. The database can then stream results back and the work done is proportional to the size of the result set.

This way you can't do queries that don't scale in production, but still don't have to increase the cognitive load on the developer. If a query is rejected by the planner that (for the most part - it's not perfect) means the query won't scale.

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

#75
"unlike Google Percolator, FoundationDB, or similar systems, FaunaDB places no constraints on replica distance and is practical to deploy at global internet latencies"

"For each batch of parallel transactions, they are inserted into a distributed, write-ahead transaction log"

"Replicas must achieve consensus for how to insert new transactions into the log. FaunaDB uses an optimized Raft implementation to achieve consensus."

There are constrains on running consensus across the world (Raft), it adds at least 200 ms to serialize txs. Also higher latency means longer interval between hearbeats and hence longer downtime if leader is isolated - known issue of leader based consensus protocols (see "There Is More Consensus in Egalitarian Parliaments" paper[1] or "In search of a simple consensus algorithm" post[2])

Google's Percolator doesn't depend on global consensus but just on global TSO (timestamp oracle) which is possible to implement in a way:

- it doesn't suffer from leader isolation (no leader)

- doesn't have bottleneck (each node handles requests)

- doesn't touch disk on each request

details in the "Quorum clock: leaderless distributed clock" post[3].

[1] https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf

[2] http://rystsov.info/2017/02/15/simple-consensus.html

[3] http://rystsov.info/2018/10/01/tso.html

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

#76
post #15

Earlier quoted context omitted.

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?

lol

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

#77
post #62

Earlier quoted context omitted.

Is not possible to make the query optimizer deterministic? I think is better that every time I see a query it do exactly the same steps. Only when testing/monitoring say so, I hint it.

Perhaps. What if you add a new index and it changes the optimization plan of existing queries that you didn’t anticipate? There are a lot of edge cases, but we are not religiously opposed to making the optimizer smarter.

Oh, I see. That make sense.

In fact I like the idea of a RDBMS to be less of a black box.

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

#78
post #59

The paper contains this claim: > FaunaDB is an elegant, software-only solution for achieving global ACID transactions, with complete guarantees of serializability and consistency. The paper makes it sound like FaunaDB claims strict serializability for all transactions (like Spanner). This means that if Txn(A) ends before Txn(B) begins, then Txn(B) must be guaranteed to see all data written by Txn(A). However, what if…

>It reads the value of X on replica R2, which does not yet reflect W(X).

Why does someone want this functionality? Do you expect, say, Oracle to work this way? I honestly don't see this as a useful feature in a database that's operating at scale, but I'm open to hearing reasons for needing this.

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

#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, otherwise you risk giving out not just stale answers, but completely wrong answers. This is fine for a site like FB but is not OK if it's attached to military equipment.

CRDTs don't help in the case that you don't want to deliver wrong answers, they only help making sure merges (during synch time) are resolvable without conflicts. Lamport clocks only give you a partial order, and you need something else (physical clocks) for total order, which is what you get from raft (because you only let one node manage the log in the first place).

What I haven't seen yet/want to try is to see if sharded + replicated raft could introduce some interesting performance benefits. It's basically max complexity (the complexity plus sharding, plus multiple instances of raft at the same time), but it could be only way to distribute write load (smart routing/forwarding of requests) and increase availability (eventually consistent replication for every node of every shard) at the same time. This is basically what Faunda does but I'm not 100% sure about splitting a single table across replicas...

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

#80

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.
Post reply on HN