13 ms·

Consistency Without Clocks: FaunaDB's Distributed Transaction Protocol

171 points by evanweaver 8y ago

evanweaver 8y ago
We're here, ready for your questions to be consistently replicated across the WAN at the lowest latency information science allows ;-)
- ryanworl 8y ago
  Has the lack of interactive transactions and only supporting entirely deterministic transactions been a big issue for your customers? My understanding is you're essentially shipping a "stored procedure" to the database where every input and condition is known up-front. It seems like a reasonable trade-off for lowering the latency of WAN transactions, but it might make application development more complicated.
  - evanweaver 8y ago
    No, it hasn't. It is possible to layer an optimistic concurrency model for session transactions on top of our protocol, but the database standard library is sufficiently full-feature that it's easy to express most application logic as a pure function over the current state of the database. Most read/modify/write cycles end up being essentially that, but with the added confusion of local application threading and standard library. We eliminate that, but preserve the general ability to express a complex query in application code (which also increases application concurrency since the database executes transactions with maximum parallelism.) Transactions do not have to be pre-registered as stored procedures.
  - jchrisa 8y ago
    This FaunaDB ledger tutorial gives a feel for how you'd build out your application logic: https://fauna.com/blog/tutorial-how-to-create-and-query-a-ledger-with-faunadb https://fauna.com/blog/tutorial-how-to-create-and-query-a-le... If you want to see a query with precondition checks etc, the code at the end of this post is another example: https://fauna.com/blog/distributed-ledger-without-the-blockchain https://fauna.com/blog/distributed-ledger-without-the-blockc...
- ummonk 8y ago
  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... Both the tendency to use declarative rather than transactional queries and the tendency to use timestamps with clock skew rather than an id-based ordering always seemed surprising to me.
  - evanweaver 8y ago
    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.
  - zzzcpan 8y ago
    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%202018-10-20&q=FaunaDB,FoundationDB,CockroachDB,TiDB https://trends.google.com/trends/explore?date=2016-09-20%202... compare that to some other distributed database https://trends.google.com/trends/explore?date=2016-09-20%202018-10-20&q=FaunaDB,FoundationDB,CockroachDB,TiDB,DynamoDB https://trends.google.com/trends/explore?date=2016-09-20%202...
    - jchrisa 8y ago
      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 database drift / eventual consistency. I expect Fauna-like systems to gain popularity as more developers come to expect cloud-native solutions to offer global ACID transactions.
- tongcx 8y ago
  have a question about phantom read issue, i.e. two doctors are oncall for the night, but we have the constraint that at least one is needed to be oncall. If we have two transaction checking whether there is at least 2 doctors oncall, then remove one, seems we could end up with no one oncall with FaunaDB? If so, seems this violate serializability?
whargarbl 8y ago
As an aside, can somebody explain the constraints FoundationDB puts on replica distance?
- evanweaver 8y ago
  FoundationDB cannot currently replicate its transaction log across datacenters, either synchronously or asynchronously: https://forums.foundationdb.org/t/multi-dc-replication/499 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.
  - voidmain 8y ago
    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.
donpdonp 8y ago
thanks drift.com (and driftt.com) for driving me to learn how to block specific sites in uBlock. Audio 'pops' for a webpage chatroom is a new level of annoyance.
- jchrisa 8y ago
  Thanks for the bump I needed to go fix that. Sound is off now.
wikibob 8y ago
This looks like a fascinating approach. Unfortunately I’m not well versed enough to intelligently compare it to alternatives. Any plans to have Jepsen / Aphyr conduct a rigorous test and write a report on the results?
- jchrisa 8y ago
  We have a whole suite of internal correctness verification tools, in addition to which we are also using Jepsen. We don't have an official report out yet, but you can get a preview of our progress here: https://fauna.com/blog/verifying-transactional-consistency-with-jepsen-and-faunadb https://fauna.com/blog/verifying-transactional-consistency-w...
  - wikibob 8y ago
    Just my opinion, having Kyle write a formal report would give a huge bump to validating the stated properties :)
    - evanweaver 8y ago
      Stay tuned...
  - nickpsecurity 8y ago
    Might want to look into methods FoundationDB was using: https://abdullin.com/foundationdb-is-back/ https://abdullin.com/foundationdb-is-back/ Might be useful to your team. One of rare times I was surprised and impressed by a new company's verification process. I look forward to reading your tesm's write-up of techniques and lessons learned, too.
agentultra 8y ago
I 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.
- jchrisa 8y ago
  You can read the paper that inspired the FaunaDB transaction protocol here: http://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdf 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-in-database-systems https://www.slideshare.net/abadid/the-power-of-determinism-i...
  - agentultra 8y ago
    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?
    - mmysteryy 8y ago
      lol
fernly 8y ago
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?
- jchrisa 8y ago
  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/ http://thesecretlivesofdata.com/raft/
- jamesblonde 8y ago
  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-performance 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-systems-are-failing-to.html 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-second-in-mysql-cluster.html 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.
deleted 8y ago
[deleted]
EngineerBetter 8y ago
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?
- jchrisa 8y ago
  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.
netgusto 8y ago
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 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.
- convolvatron 8y ago
  optimistic concurrency control https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung-robinson.pdf https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung...
EGreg 8y ago
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.
- jchrisa 8y ago
  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.)
  - EGreg 8y ago
    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!
    - jchrisa 8y ago
      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.
- wmf 8y ago
  A BFT database is called a blockchain.
kerneltime 8y ago
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?
- evanweaver 8y ago
  The transaction is acknowledged after it has been durably replicated to the distributed write-ahead log, and applied by at least one replica. The first replica to apply will ack back to the coordinator and on to the client. This increases partition tolerance and reduces latency. The speculative work ("reconnaissance query") is what enables support for dependent transactions (transactions where the write set depends on the values of the read set rather than just the keys themselves). The transaction will optimistically retry if the speculation turns out to be false.
  - kerneltime 8y ago
    A system like CORFU where the log is serialized upfront (not post speculative commit) will give most of the benefits mentioned?
    - evanweaver 8y ago
      My understanding is that in CORFU the write set is always known, so this kind of transaction cannot be expressed. You could layer it on top with the same strategy.
gigatexal 8y ago
Hmm. I’m intrigued though skeptical. Who’s using this in production that can give an unbiased take?
- evanweaver 8y ago
  Not quite what you are asking, but some customers with case studies on the site: https://fauna.com/customers https://fauna.com/customers
  - gigatexal 8y ago
    Unbiased in that the article we are all referencing is coming from you guys, the creators, you can't help but show it in a positive light and I don't fault you for it. Just I've become so jaded of late that I am looking for people who have used it in the wild. I also signed up for the cloud account -- your pricing terms are some of the best I've ever seen, kudos -- so that I can check out the API some more.
    - evanweaver 8y ago
      Thanks; what do you like about the pricing?
      - gigatexal 8y ago
        The free forever on premise pricing for personal use to the 90-trial in production even in commercial use. And I thought the free threshold for the cloud reasonable as I can forgo all the setup work and just use the cloud isntance for free if my usage falls under the right level. Anything that saves me time but then doesn’t cost me anything while learning it / trying it out is a win in my book.
    - deleted 8y ago
      [deleted]
gigatexal 8y ago
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.
- evanweaver 8y ago
  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.
  - gigatexal 8y ago
    I agree -- it burns us in the SQL world too. I was just seeing it from a developer cognitive load point of view and maybe as a premature optimization, again, though if you guys and gals put this in place because of war stories from twitter then it's not premature by any means. In the rare case when no index or the wrong index is used in a SQL query an index hint is all it takes to fix or updating statistics of a table to help the optimizer. Not having to remember the exact index for a query imo is better, but I could learn to adapt.
    - evanweaver 8y ago
      I should also add that Fauna indexes are more akin to views. They can cover multiple source collections and transform the data as well. So it’s not always possible to detect which index is correct via heuristic.
      - gigatexal 8y ago
        Ahh makes sense. Interesting.
  - 8y ago
andydb 8y ago
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 Txn(B) is a read-only transaction? According to the paper, read-only transactions do not contact the global sequencer. Here is an example where an application would fail to read its own writes: 1. Txn(A) performs a write W(X) of data on replica R1. 2. Txn(A) is assigned a logical timestamp of T1 by the global log. 3. Conflict verification is triggered. Replica R1 plays back the global log and verifies there is no conflict. 4. Txn(A) completes, since one replica has verified there are no conflicts, and passes control back to the application. 5. The application now triggers a read-only Txn(B). 6. The coordinator for Txn(B) decides to read replica R2 rather than R1. However, the coordinator is not yet aware that the global log is now at timestamp T1, and it picks T0 as its snapshot timestamp. 7. It reads the value of X on replica R2, which does not yet reflect W(X). -- From the application's point of view, it did not read its own writes. -- I'm not familiar enough with Fauna DB's subtleties to know if this scenario is possible in practice. Perhaps you could comment? I did notice that at the end of the article, the language is carefully phrased to only make the claim of "serializable" (not "strictly serializable") for read-only transactions. But that would fall short of the guarantees that Spanner and Calvin make, and undermine the "complete guarantees of serializability and consistency".
- evanweaver 8y ago
  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.
  - andydb 8y ago
    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 issues. Most application developers would not appreciate the subtleties and just use the default behavior, which does not guarantee "read your own writes". And causal tokens don't prevent the more general case of stale reads. This would mean that in the default FaunaDB configuration, applications could see anomalies: 1. Inability to read own writes - described above, with the additional clarification that it can't be fully solved at the driver level. For example, say I call a web API that creates a blog post and returns a PostID. I then call another API that edits that post, passing it the PostID I got back from the first. If FaunaDB is in use, the second call could fail to find the PostID, because I happened to hit a different replica that did not yet have it. 2. Stale reads - could be arbitrary levels of staleness if replica/coordinator haven't been able to sync to the global log. If a coordinator node and a replica were stuck in their own little partition, cut off from the rest of the cluster, they'd still happily serve stale reads (until perhaps they detect a partition and shut down?). These read anomalies aren't usually considered compatible with a consistent system, but instead are hallmarks of an eventually consistent system. It seems misleading to make an unqualified 100% consistency claim when it doesn't apply to read-only txns by default, and when the fully consistent mode is not practical to use in global deployments.
PHGamer 8y ago
is the issue not so much other dbs cant provide that global consitency but other dbs just choose not to for the sake of speed. like their are trade offs
rystsov 8y ago
"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 https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf [2] http://rystsov.info/2017/02/15/simple-consensus.html http://rystsov.info/2017/02/15/simple-consensus.html [3] http://rystsov.info/2018/10/01/tso.html http://rystsov.info/2018/10/01/tso.html
hardwaresofton 8y ago
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...
- sporkland 8y ago
  Sounds like foundationdb to some extent. All data is sharded (and replicated) i.e. chunks of the keyspace up to the small blocksize limit are spread across the cluster. With this you can scale read throughput with the size of the cluster through parrallel reads. Though their write performance is bounded by the more limited number of transactors, but they still acheive fairly large write scale.
- rystsov 8y ago
  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.
  - hardwaresofton 8y ago
    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.
kuujo 8y ago
“Consisteny without clocks” seems like a misnomer considering Raft indexes are tantamount to a logical clock. Perhaps it should be “consistency without wall clocks.” But that’s not really novel by itself, except in the context of geo-distributed databases.
andras_gerlits 8y ago
I've published this article 5 months ago. Mine doesn't require global consensus for all commits, just local one and it works from there. What's even more annoying is that I tweeted this article to them and they didn't say anything. https://medium.com/p/optimistic-acid-transactions-4f193844bb5f https://medium.com/p/optimistic-acid-transactions-4f193844bb...
- mirlyn86 8y ago
  Did you implement it?
  - andras_gerlits 8y ago
    I'm planning on releasing a prototype as open source in a few months. I'm also planning on releasing my patent into the public domain.
- andras_gerlits 8y ago
  Sorry, let me clarify. Tweeted to them at the time. So, back in May.
grogers 8y ago
I'm really confused how this scales to high transaction rates. If the replica has to redo all the reads (which means talking to multiple nodes) before it can make a commit/abort decision for the transaction this could take tens of microseconds if all nodes are in the same datacenter (if serving from RAM). Since it also has to process transactions from the log in order, that seems like it would limit the transaction rate to tens of thousands of TPS? Forget about distributing a replica across data centers or having enough data that it may not be RAM resident. Is this actually how it works or am I missing something important?
chappar 8y ago
How does FaunaDB achieves atomicity without some sort of 2 phase commit? What I understood from the article is that each node in a replica commits independently from the distributed transaction log. So, if a transaction updates data in multiple nodes in a replica then it can happen that one of the commit in one of the nodes fails because of some failure. In that case will there be partial commit?

171 points by evanweaver 8y ago

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

ryanworl 8y ago
Has the lack of interactive transactions and only supporting entirely deterministic transactions been a big issue for your customers? My understanding is you're essentially shipping a "stored procedure" to the database where every input and condition is known up-front. It seems like a reasonable trade-off for lowering the latency of WAN transactions, but it might make application development more complicated.
- evanweaver 8y ago
  No, it hasn't. It is possible to layer an optimistic concurrency model for session transactions on top of our protocol, but the database standard library is sufficiently full-feature that it's easy to express most application logic as a pure function over the current state of the database. Most read/modify/write cycles end up being essentially that, but with the added confusion of local application threading and standard library. We eliminate that, but preserve the general ability to express a complex query in application code (which also increases application concurrency since the database executes transactions with maximum parallelism.) Transactions do not have to be pre-registered as stored procedures.
- jchrisa 8y ago
  This FaunaDB ledger tutorial gives a feel for how you'd build out your application logic: https://fauna.com/blog/tutorial-how-to-create-and-query-a-ledger-with-faunadb https://fauna.com/blog/tutorial-how-to-create-and-query-a-le... If you want to see a query with precondition checks etc, the code at the end of this post is another example: https://fauna.com/blog/distributed-ledger-without-the-blockchain https://fauna.com/blog/distributed-ledger-without-the-blockc...
ummonk 8y ago
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... Both the tendency to use declarative rather than transactional queries and the tendency to use timestamps with clock skew rather than an id-based ordering always seemed surprising to me.
- evanweaver 8y ago
  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.
- zzzcpan 8y ago
  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%202018-10-20&q=FaunaDB,FoundationDB,CockroachDB,TiDB https://trends.google.com/trends/explore?date=2016-09-20%202... compare that to some other distributed database https://trends.google.com/trends/explore?date=2016-09-20%202018-10-20&q=FaunaDB,FoundationDB,CockroachDB,TiDB,DynamoDB https://trends.google.com/trends/explore?date=2016-09-20%202...
  - jchrisa 8y ago
    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 database drift / eventual consistency. I expect Fauna-like systems to gain popularity as more developers come to expect cloud-native solutions to offer global ACID transactions.
tongcx 8y ago
have a question about phantom read issue, i.e. two doctors are oncall for the night, but we have the constraint that at least one is needed to be oncall. If we have two transaction checking whether there is at least 2 doctors oncall, then remove one, seems we could end up with no one oncall with FaunaDB? If so, seems this violate serializability?

whargarbl 8y ago

As an aside, can somebody explain the constraints FoundationDB puts on replica distance?

evanweaver 8y ago
FoundationDB cannot currently replicate its transaction log across datacenters, either synchronously or asynchronously: https://forums.foundationdb.org/t/multi-dc-replication/499 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.
- voidmain 8y ago
  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.

donpdonp 8y ago

thanks drift.com (and driftt.com) for driving me to learn how to block specific sites in uBlock. Audio 'pops' for a webpage chatroom is a new level of annoyance.

jchrisa 8y ago
Thanks for the bump I needed to go fix that. Sound is off now.

wikibob 8y ago

This looks like a fascinating approach. Unfortunately I’m not well versed enough to intelligently compare it to alternatives. Any plans to have Jepsen / Aphyr conduct a rigorous test and write a report on the results?

jchrisa 8y ago
We have a whole suite of internal correctness verification tools, in addition to which we are also using Jepsen. We don't have an official report out yet, but you can get a preview of our progress here: https://fauna.com/blog/verifying-transactional-consistency-with-jepsen-and-faunadb https://fauna.com/blog/verifying-transactional-consistency-w...
- wikibob 8y ago
  Just my opinion, having Kyle write a formal report would give a huge bump to validating the stated properties :)
  - evanweaver 8y ago
    Stay tuned...
- nickpsecurity 8y ago
  Might want to look into methods FoundationDB was using: https://abdullin.com/foundationdb-is-back/ https://abdullin.com/foundationdb-is-back/ Might be useful to your team. One of rare times I was surprised and impressed by a new company's verification process. I look forward to reading your tesm's write-up of techniques and lessons learned, too.

agentultra 8y ago

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

jchrisa 8y ago
You can read the paper that inspired the FaunaDB transaction protocol here: http://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdf 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-in-database-systems https://www.slideshare.net/abadid/the-power-of-determinism-i...
- agentultra 8y ago
  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?
  - mmysteryy 8y ago
    lol

fernly 8y ago

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?

jchrisa 8y ago
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/ http://thesecretlivesofdata.com/raft/
jamesblonde 8y ago
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-performance 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-systems-are-failing-to.html 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-second-in-mysql-cluster.html 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.

deleted 8y ago

[deleted]

EngineerBetter 8y ago

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?

jchrisa 8y ago
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.

netgusto 8y ago

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

convolvatron 8y ago
optimistic concurrency control https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung-robinson.pdf https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung...

EGreg 8y ago

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.

jchrisa 8y ago
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.)
- EGreg 8y ago
  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!
  - jchrisa 8y ago
    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.
wmf 8y ago
A BFT database is called a blockchain.

kerneltime 8y ago

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?

evanweaver 8y ago
The transaction is acknowledged after it has been durably replicated to the distributed write-ahead log, and applied by at least one replica. The first replica to apply will ack back to the coordinator and on to the client. This increases partition tolerance and reduces latency. The speculative work ("reconnaissance query") is what enables support for dependent transactions (transactions where the write set depends on the values of the read set rather than just the keys themselves). The transaction will optimistically retry if the speculation turns out to be false.
- kerneltime 8y ago
  A system like CORFU where the log is serialized upfront (not post speculative commit) will give most of the benefits mentioned?
  - evanweaver 8y ago
    My understanding is that in CORFU the write set is always known, so this kind of transaction cannot be expressed. You could layer it on top with the same strategy.

gigatexal 8y ago

Hmm. I’m intrigued though skeptical. Who’s using this in production that can give an unbiased take?

evanweaver 8y ago
Not quite what you are asking, but some customers with case studies on the site: https://fauna.com/customers https://fauna.com/customers
- gigatexal 8y ago
  Unbiased in that the article we are all referencing is coming from you guys, the creators, you can't help but show it in a positive light and I don't fault you for it. Just I've become so jaded of late that I am looking for people who have used it in the wild. I also signed up for the cloud account -- your pricing terms are some of the best I've ever seen, kudos -- so that I can check out the API some more.
  - evanweaver 8y ago
    Thanks; what do you like about the pricing?
    - gigatexal 8y ago
      The free forever on premise pricing for personal use to the 90-trial in production even in commercial use. And I thought the free threshold for the cloud reasonable as I can forgo all the setup work and just use the cloud isntance for free if my usage falls under the right level. Anything that saves me time but then doesn’t cost me anything while learning it / trying it out is a win in my book.
  - deleted 8y ago
    [deleted]

gigatexal 8y ago

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.

evanweaver 8y ago
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.
- gigatexal 8y ago
  I agree -- it burns us in the SQL world too. I was just seeing it from a developer cognitive load point of view and maybe as a premature optimization, again, though if you guys and gals put this in place because of war stories from twitter then it's not premature by any means. In the rare case when no index or the wrong index is used in a SQL query an index hint is all it takes to fix or updating statistics of a table to help the optimizer. Not having to remember the exact index for a query imo is better, but I could learn to adapt.
  - evanweaver 8y ago
    I should also add that Fauna indexes are more akin to views. They can cover multiple source collections and transform the data as well. So it’s not always possible to detect which index is correct via heuristic.
    - gigatexal 8y ago
      Ahh makes sense. Interesting.
- 8y ago

andydb 8y ago

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 Txn(B) is a read-only transaction? According to the paper, read-only transactions do not contact the global sequencer. Here is an example where an application would fail to read its own writes: 1. Txn(A) performs a write W(X) of data on replica R1. 2. Txn(A) is assigned a logical timestamp of T1 by the global log. 3. Conflict verification is triggered. Replica R1 plays back the global log and verifies there is no conflict. 4. Txn(A) completes, since one replica has verified there are no conflicts, and passes control back to the application. 5. The application now triggers a read-only Txn(B). 6. The coordinator for Txn(B) decides to read replica R2 rather than R1. However, the coordinator is not yet aware that the global log is now at timestamp T1, and it picks T0 as its snapshot timestamp. 7. It reads the value of X on replica R2, which does not yet reflect W(X). -- From the application's point of view, it did not read its own writes. -- I'm not familiar enough with Fauna DB's subtleties to know if this scenario is possible in practice. Perhaps you could comment? I did notice that at the end of the article, the language is carefully phrased to only make the claim of "serializable" (not "strictly serializable") for read-only transactions. But that would fall short of the guarantees that Spanner and Calvin make, and undermine the "complete guarantees of serializability and consistency".

evanweaver 8y ago
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.
- andydb 8y ago
  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 issues. Most application developers would not appreciate the subtleties and just use the default behavior, which does not guarantee "read your own writes". And causal tokens don't prevent the more general case of stale reads. This would mean that in the default FaunaDB configuration, applications could see anomalies: 1. Inability to read own writes - described above, with the additional clarification that it can't be fully solved at the driver level. For example, say I call a web API that creates a blog post and returns a PostID. I then call another API that edits that post, passing it the PostID I got back from the first. If FaunaDB is in use, the second call could fail to find the PostID, because I happened to hit a different replica that did not yet have it. 2. Stale reads - could be arbitrary levels of staleness if replica/coordinator haven't been able to sync to the global log. If a coordinator node and a replica were stuck in their own little partition, cut off from the rest of the cluster, they'd still happily serve stale reads (until perhaps they detect a partition and shut down?). These read anomalies aren't usually considered compatible with a consistent system, but instead are hallmarks of an eventually consistent system. It seems misleading to make an unqualified 100% consistency claim when it doesn't apply to read-only txns by default, and when the fully consistent mode is not practical to use in global deployments.

PHGamer 8y ago

is the issue not so much other dbs cant provide that global consitency but other dbs just choose not to for the sake of speed. like their are trade offs

rystsov 8y ago

"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 https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf [2] http://rystsov.info/2017/02/15/simple-consensus.html http://rystsov.info/2017/02/15/simple-consensus.html [3] http://rystsov.info/2018/10/01/tso.html http://rystsov.info/2018/10/01/tso.html

hardwaresofton 8y ago

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

sporkland 8y ago
Sounds like foundationdb to some extent. All data is sharded (and replicated) i.e. chunks of the keyspace up to the small blocksize limit are spread across the cluster. With this you can scale read throughput with the size of the cluster through parrallel reads. Though their write performance is bounded by the more limited number of transactors, but they still acheive fairly large write scale.
rystsov 8y ago
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.
- hardwaresofton 8y ago
  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.

kuujo 8y ago

“Consisteny without clocks” seems like a misnomer considering Raft indexes are tantamount to a logical clock. Perhaps it should be “consistency without wall clocks.” But that’s not really novel by itself, except in the context of geo-distributed databases.

andras_gerlits 8y ago

I've published this article 5 months ago. Mine doesn't require global consensus for all commits, just local one and it works from there. What's even more annoying is that I tweeted this article to them and they didn't say anything. https://medium.com/p/optimistic-acid-transactions-4f193844bb5f https://medium.com/p/optimistic-acid-transactions-4f193844bb...

mirlyn86 8y ago
Did you implement it?
- andras_gerlits 8y ago
  I'm planning on releasing a prototype as open source in a few months. I'm also planning on releasing my patent into the public domain.
andras_gerlits 8y ago
Sorry, let me clarify. Tweeted to them at the time. So, back in May.

grogers 8y ago

I'm really confused how this scales to high transaction rates. If the replica has to redo all the reads (which means talking to multiple nodes) before it can make a commit/abort decision for the transaction this could take tens of microseconds if all nodes are in the same datacenter (if serving from RAM). Since it also has to process transactions from the log in order, that seems like it would limit the transaction rate to tens of thousands of TPS? Forget about distributing a replica across data centers or having enough data that it may not be RAM resident. Is this actually how it works or am I missing something important?

chappar 8y ago

How does FaunaDB achieves atomicity without some sort of 2 phase commit? What I understood from the article is that each node in a replica commits independently from the distributed transaction log. So, if a transaction updates data in multiple nodes in a replica then it can happen that one of the commit in one of the nodes fails because of some failure. In that case will there be partial commit?