freels

Yes, it potentially is, but it entirely depends on the implementation details of the system. It's certainly allowed behavior by the definition of serializability.

Yes, I believe so. Since in Postgres, snapshot isolation (on top of which its serializable implementation is built) provides a stable view of the system at a point in time, and also doesn't allow stale reads, transactions _can be_ strictly serializable.

However, if multiple synchronous standby replicas are configured, then this means that stale reads are possible, since Postgres by default does not necessarily wait for all replicas to ack the write. It depends on the replication configuration and where reads are directed.

There is some overhead, but it is minimal. For example in Fauna only the modified timestamps of read data are re-checked in transaction processing (which can be stored separately from the data itself), rather than entire records.

The big difference is that it's a much easier problem to solve in the context of a log (see Paxos, Raft, ZAB, et al), where the consensus membership is more or less fixed, as opposed to having to manage it among an adhoc membership set.

FaunaDB already does this. It provides distributed transactions based on Calvin, which does not rely on classic 2PC. See https://fauna.com/blog/acid-transactions-in-a-globally-distr... and http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1...

Yes, I meant regions as well. Speed-of-light bounded latency certainly means that serializable ACID transactions are not workable in some situations, but I disagree with OP that this proves them not viable period, at least at planet-scale as you say.

We're indeed pretty lucky as far as transactions are concerned...

TiDB uses the Percolator protocol

I don't think it's correct to pit ACID against AP systems this way. Consistency is orthogonal. ACID is model for reasoning about transaction guarantees in terms of allowed anomalies at each isolation level. Serializability in ACID implies CP over AP, but weaker levels don't have the same requirement. It still comes down to tradeoffs for a specific use-case of a database system.

Not sure what you're getting at when you say ACID transactions don't work in a multi-DC context. FaunaDB aside, there are many production systems (commercial or internal) that provide them that I am aware of.

You're welcome! I've enjoyed following TiKV/TiDB's development as well. It is an interesting time for databases. :-)

Support for dependent reads is a subject that the Calvin paper only touches on briefly, describing one strategy of using "reconnaissance reads" to determine the key set.

In FaunaDB, this is formalized as an optimistic concurrency control mechanism that combines snapshot reads at the coordinator and read-write conflict detection within the transaction engine. By the time a transaction is ready to commit the entire key set is known. I wrote a blog post that goes into more detail here: https://fauna.com/blog/acid-transactions-in-a-globally-distr...

Better analytics support, including ad-hoc queries is on our roadmap. That being said, requiring indexes was a design choice: First and foremost, we want FaunaDB to be the best operational database. It is a lot easier to write fast, predictable queries if they cannot fall back to a table scan!

While FaunaDB requires you to create indexes to support the views your workload requires, the reward is a clearer understanding of how queries perform. We've built indexes to be pretty low commitment, however. You can add or drop them on the fly based on how your workload evolves over time.

Another point that often gets lost when talking about ACID guarantees is the maximum scope of a transaction that a system supports. There are many systems which support ACID guarantees for a single record or shard, but fewer that can support fully distributed transactions across a sharded dataset in a scalable manner.

That's a great resource. We've tried to be consistent in using these terms. I think a lot of the confusion and lack of standardization over terminology came from the fact that database and distributed systems research had less overlap in the past...

Consistency in the ACID sense meaning something different from CAP Consistency is another good example.

I believe what we spanner calls 'external consistency' we call strict serializability. Read-write transactions in FaunaDB are strictly serializable, whereas reads default to serializable. This allows us to serve reads independently from the closest region to the client, cutting down on latency in geo-distributed clusters.

This is a bit weaker than external consistency or strict serializability; Peter Bailis has a good writeup on the meaning of serializability vs strict serializability here: http://www.bailis.org/blog/linearizability-versus-serializab...

We run FaunaDB as a service, or you can license it for on-prem use. Drivers and tooling are all open however, and we plan to release the source for correctness testing as well.

Our property tests are written in Scala as a Monad for controlling execution and random sample generation, and our internal distributed test harness uses Akka. This worked out nicely because we were able to make the relevant integration and fault tests scale from local runs via SBT to full geo-distributed clusters and OS-level fault injection.

You make a valid point. We fixed the link.

Here is a direct link to the report: https://www2.fauna.com/l/517431/2018-06-25/6c9gwb/517431/114...

That’s right. Along with the load and fault generators, it includes some other useful tools such as a linearizability checker, as well as quite a few existing tests for other systems. From this we built out tests for Fauna’s stronger ACID guarantees.

Admittedly, the specific mechanics of how the log interacts with data partitions was glossed over a bit in that post.

However, to answer your question, the input log is partitioned: Transactions for each epoch are striped across the log partitions. A data partition will need to read a batch from each log partition in order to be able to process the transactions for any given epoch.

In FaunaDB all transaction resolution is deterministic. Once global log order is determined, partitions will wait for the transaction inputs at the correct version and will each independently come up with an identical result.

It is true that Spanner and FaunaDB partition a cluster's dataset across multiple nodes but it's handled transparently by the database. Whenever I've heard the term "sharding" it's usually in reference to the application-level sharding described in the article.

Partitioning the dataset isn't really novel these days (Cassandra, Riak, Mongo et al do the same of course), but what is a significant difference is that both Spanner and FaunaDB implement ACID transactions distributed across partitions. It no longer matters for application correctness what partition key you choose if you can involve any arbitrary set of records in an single transaction.

Snapshot reads require just as many network communications as Cassandra does at consistency ONE, and provide a better correctness guarantee because effect order has already been determined. Data replicas can the single valid state at the requested snapshot time, or delay or reject the read if they are not caught up yet.

IME, while Google's network is really good (based on my experience w/ GCP at least), AWS cross-region traffic, for example, is still pretty reliable.

Reliable enough, at least, that trading off perfect resiliency in the face of partitions is worth it to gain strong consistency semantics.

IMO behavior in the face of partitions is a bit of a red herring. The latency tradeoffs required in a geo-replicated CP vs AP system is much more relevant.

Calvin is still a CP system, so nodes outside of the quorum cannot proceed. The point however is that partitions are rare enough that a CP system can still provide a high level of availability, despite the theoretical limitation. Eric Brewer, who came up with the CAP theorem explicitly makes this point here: https://static.googleusercontent.com/media/research.google.c...

Yes. For log data, it's simply a matter of reading from a replica peer of the down node.

For transaction resolution it's a bit easier if you are able to assume more about the storage layer's semantics.

For example, if you store versioned values for some bounded period of time (ala MVCC), you can go to other replicas for the version required to resolve a transaction, removing the restriction that transaction resolution must proceed in lock-step across all nodes, and allows transaction reads to route to live peers assuming they have the required version of each read dependency.

A better way to think about how Calvin fits into our stack is as a building block similar to two-phase-commit, on which we've built the higher level transaction semantics. And while we do not have any plans on supporting session transactions, this is more of a design constraint to support the best possible OLTP experience rather than a hard technical limitation.

Since our focus has been getting OLTP right, ETLs are currently handled by chunking record imports across multiple transactions. (We have internal tooling for this that we've used to help customers move their data into FaunaDB; we are planning on open-sourcing it soon.)

However, first-class support for OLAP use-cases is on our roadmap and something we are excited about providing, so expect more from us about this in the coming months.

I agree with you that it's not an original analogy, in fact I think you can safely say that most larger, performance-oriented systems end up looking more like an OS than not. There's a large overlap in the problems that need to be solved and the resources available to distributed systems, that I'd be more skeptical of an implementation that didn't lean heavily on the OS, or at least borrow the general patterns.

To answer your question about consistency, we have implemented a transaction resolution mechanism inspired by Calvin. The whitepaper contains a lot more detail, but the short answer is that we use a consistent, distributed transaction log to provide a global order of all read-write transactions, which are executed deterministically on the responsible data partitions. This allows FaunaDB to provide a guarantee of strict-serializability for read-write transactions. Read-only transactions are by default a bit more relaxed and provide a hard guarantee of serializability in order to avoid global coordination overhead.

Fair enough, though at that point, you're layering on additional complexity and getting further away from the goal of simplicity. (And to point 3, while this is true, using a log means this problem can be dealt with a lot later, and there are solutions that don't involve giving up linearizability, such as a dedicated set of log replicas apart from data partitions, or implementing something like Calvin.)

My main point was that the deficiencies of strong-leader-based consensus protocols are overstated, and despite a (minor IMO) level of additional starting complexity, a raft-like protocol is going to be quite a bit simpler than a paxos-based protocol of equivalent capability.

This is true, but comes at the cost of not being able to preserve linearity across arbitrary keys, and you are still limited by the throughput on updates to a single key.

I think this overstates the instability of strong leader-based consensus algorithms, or at least over-generalizes Raft's instability to apply to all consensus algorithms with a stronger leader.

In Raft, it's possible for multiple nodes to prevent leader election progress by being overly aggressive when requesting votes. It is also possible for a follower to knock out a perfectly healthy leader by being too quick time out the leader and start a new term.

Both of these limitations stem from the simplicity of Raft's leader election algorithm. To compensate, most Raft implementations I've seen have more conservative follower timeouts that extend the time to detect leader failure and elect a new one.

It's possible for a more optimized algorithm to get sub-second latencies for detecting and re-electing a leader, even in a latent (e.g. geo-distributed) environment. In other words, well within the commit window for the replica set based on network hop latencies.

Also, while the latency for individual writes in single-decree paxos can be closer to strong leader protocols, it is non-trivial to achieve the same level of throughput that is possible in Raft et al when writing to an ordered log, as you cannot start a paxos instance for a new log entry until all prior instances have been resolved. Raft can just add new values in the next append call (or just spam out appends for new messages w/o waiting for the replies for previous ones).

IME, I'd say both single-decree paxos and raft are probably equivalent in terms of understandability, but raft is a better base on which to build a fast high-throughput consensus protocol.

One thing that makes this easier is that FaunaDB does not support session transactions, rather you must express your transaction logic as a single Fauna query, which is executed atomically. Transactions can still involve arbitrary keys, however.

And yes, for reads, by default the coordinating node chooses a timestamp and uses that to query all involved data partitions. Each partition will respond with the requested data as of at that timestamp, or will delay responding until it has caught up.

One nice thing about this approach is that any chosen timestamp is enough to provide a consistent snapshot view of the dataset at that time. This ends up being useful for bulk or incremental reads, where a longer running process needs a stable view of the dataset.