pbailis

For non-conflicting operations, I agree entirely that serializable transactions can scale just fine. In fact, just about every serializable concurrency control algorithm (e.g., two-phase locking, partitioned OCC, MVCC with clever timestamp allocation) can scale just fine for non-conflicting operations.

However, for conflicting read-write operations, serializability will incur higher costs than many alternatives (e.g., eventual consistency, weak isolation implemented in a scalable manner). Serializing access to shared data items fundamentally requires some serial execution.

This fundamental overhead is a key reason why almost every commodity RDBMS defaults to one of these weaker isolation levels and why databases like Oracle don't support serializable isolation at all. It's not that their respective database architects don't know how to implement serializability -- it's that weak isolation is faster and, in many cases, reduces deadlocks and system-induced aborts, even if it increases programmer burden.

In the example configuration in the post (i.e., two servers with no replication), during the period between the write start and end of phase two of writes, reads can return either value written (x=y=0 or x=y=1). If we want to enforce the property that once one read returns the second write, all subsequent reads (that begin after this read) will return the second write (or a later write), which is called linearizability (http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf), then whenever servers serve from 'pending', they should move the writes to 'good'. This is safe because, if a client reads from 'pending', it means that the write must be in 'good' elsewhere and therefore is stable.

As for how to order the writes, real-time clocks can provide a fairly useful timestamp mechanism. Databases like Cassandra use this real-time ordering for timestamping, which appears to work well in practice. Alternatively, you could use a distributed sequence number generator to totally order transactions. But real-time should be fine.

As you point out, this atomicity property doesn't address (all) application-level integrity constraints; it doesn't handle isolation between transactions. As I discussed in the post and in another comment (https://news.ycombinator.com/item?id=5784030), if your application-level integrity constraints are such that your updates are not commutative (that is, concurrent updates should not be allowed), then you'll need to block in order to guarantee database integrity is not violated. This is separate from atomicity, but it is important to remember. In your example above, two writers might both simultaneously reserve the last seat on a plane unless they synchronize.

Effectively, with non-commutative updates, you need greater isolation than is provided by the algorithm in the post (which effectively provides Read Committed isolation). Achieving greater isolation is possible but you'll lose the non-blocking property (again, due to the requirement to avoid concurrent updates via higher isolation like serializability rather than due to atomicity). But, for many applications like 2i and the multi-puts I mentioned at Facebook and Twitter, updates are commutative.

In the initial example, I represented 'good' as a set for ease of understanding, but, in practice, unless a client specifically requests an older version of a data item, the system serves the latest value written to 'good'. That is, the system does not expose a read() that returns multiple values. Rather, clients can read_good(key) or read_by_version(key, timestamp), both of which return a single version/write.

This is different from deciding which "transaction you will accept as valid and which you will reject." Many database systems perform in-place updates, but they must either either 1.) choose a winner across multiple writes (as I described below, distributed databases often employ what's called "last writer wins") or 2.) abort multiple writes. However, a large class of database systems (e.g., Oracle, Postgres) employ what's called multi-version concurrency control, whereby the database stores multiple versions of each data item. The system has a total commit order on transactions which determines what version a transaction should read() from the database. But, say, in Oracle, if:

1.) I start a transaction

2.) You start a transaction

3.) You modify variable X

4.) You commit

5.) I read X

Under what's known as Snapshot Isolation, I will read X as of the start of my transaction (i.e., I will not read your write to X even though it's "present" in the database). This is often accomplished via MVCC techniques.

> The paper describes this scheme as READ Committed which doesn't make generally make sense except in the context of a database with secondary indexes.

I tend to disagree. This is probably another conversation, but databases rarely guarantee serializable isolation (see http://www.bailis.org/blog/when-is-acid-acid-rarely/#acidtab...), and Read Committed is a fairly commonly deployed model. It's true that serializability is often required for correct operation. But, perhaps interestingly, many databases like Oracle 11g and SAP HANA do not provide it as an option (largely due to poor performance and deadlock avoidance), and, anecdotally, models like Read Committed are 2-3x faster than serializability.

I'm not entirely sure what you mean by applicability to secondary indexing (rather, I think there are other use cases, though I'm excited about 2i applications). However, I'm genuinely curious if I'm missing something.

> The problem to me seems to be that the interesting problems always come across the case where updates are not commutative.

I agree that many application-level integrity constraints can't be satisfied with commutative updates. However, I've been surprised how frequently they can work for many web applications and how frequently "fuck-it" integrity constraint maintenance is employed given i.) faster database operation and 2.) asynchronous compensation mechanisms (e.g., bank overdraw fees) in the event of constraint violation. But your point is well-taken!

> Here, client B should fail since client A has not committed.

I think I understand your example, though I'm not clear as to whether s and t are stored on both X and Y or separately as s on X and t on Y. But, in general, writes in 'pending' should not block the insertion of other writes into 'pending' (in 2PC parlance, prepared but non-committed transactions should not block other transactions from preparing). This is fundamental to the non-blocking property of the algorithm here (i.e., http://www.bailis.org/blog/non-blocking-transactional-atomic...). So if client A hasn't committed, it shouldn't stop client B from committing. If client A and client B's writes don't commute, then the clients should use a stronger protocol/isolation level than the effective Read Committed that the NBTA algorithm here provides (doable but requires blocking). Does that make sense?

> I guess one of the key insights is that each data has a canonical server owner which enforces the consistency of the writes of the data at a single place.

Well, this is the way I presented it, because it's easiest to understand. But, if you want a replicated system that provides HA, there are alternatives (http://www.bailis.org/blog/non-blocking-transactional-atomic...).

> When a third client3 tries to read the latest value of x or y, what is the latest value of its peer data? It looks like depending which data client3 starts with, it would get a different version of the peer data? ... Am I missing something or this is the semantic in determining the latest values of peer data?

Good question! This ultimately comes down to how you want to handle concurrent writes. Many distributed databases use a "last writer wins" strategy when reconciling concurrent updates (that is, the correct behavior is specified to be that the database serves the highest-timestamped version of a given data item). Now, in your example, the clients both started their writes at the same (real-world) time and used this time as a basis for their timestamp, so the "last" write is undefined. We need a way to break the "last writer wins" tie. In practice, this can be something like the client ID appended to the last few bits of the timestamp or even a hash of the value written--as long as the tie-breaker is deterministic (that is, different replicas don't decide different "winners"), it doesn't really matter which is chosen.

In practice, to avoid storing every value ever written, you'd want to provide some kind of "merge" function for multiple writes, and, in our implementation and in often practice, this is last writer wins (plus some deterministic tie-breaker for identically timestamped but distinct writes).

> Doesn't writes that commute mean that there was no contention to begin with? Ideally, if I have a balance of $100 in my account and try to spend $60 in two different transactions, one should come back as failed before the purchases are complete.

Whether or not conflicting writes are a problem or not depends on the application semantics. For example, if I'm, just adding items to a set, then my updates commute. But if I have a constraint that says that elements in the set need to be unique, then my updates don't (logically) commute any more. Ultimately, this is application-specific. The "CALM Principle" (http://www.bloom-lang.net/calm/, http://vimeo.com/album/2258285/video/53904989) captures this notion of "logical monotonicity" resulting in safe operation despite concurrency. Most of the applications I mentioned, like 2i updates and the social graph example, commute.

For non-commutative operations (and there are plenty), you'll need a stronger model like serializability or sequential consistency that necessarily blocks to prevent concurrent update (or otherwise aborts concurrent updates).

> My ideal database should be read-available at all times, but guarantee that writes are atomic and durable (and give up availability for this guarantee).

This is definitely one point in the spectrum; the question is whether you want to give up availability and write performance. But if you look at workloads like those in the Spanner paper, this is reasonable for many applications.

> What are your thoughts on quorum-based voting in distributed systems? E.g.: your protocol but with the requirement that a write is considered stable if only most (vs all) of the servers involved have it marked as "good".

There's a difference between quorums over replicas over the same data item and quorums over different data items. Using quorums over replicas would help ensure that the replicas provided properties like linearizability or register semantics like Dynamo or other systems that provide an option for "strong consistency." But it's not clear to me that quorums over replicas for different data items would provide the same atomicity property--does that make sense?

I intentionally left many of the issues of replication to the footnotes in the post--mostly for readability and clarity--but I believe the technique is applicable to both linearizable/"CP" and "eventually consistent"/"HA"/"AP" systems.

If you want client writes that reached all servers to become visible, then the servers will have to perform the move from 'pending' to 'good' on their own (by communicating asynchronously). The notification of write stability is idempotent, so it doesn't hurt if both clients and servers perform this notification.

FWIW, in our implementation, servers perform the second step instead of clients (which can be made more efficient via batching).

Yep, I left this out to avoid confusion at first. There are some details in the "What just happened?", but the basic idea is that any aborted write will be stuck in "pending." Same for failed writes; writers won't see these. The algorithm presented actually guarantees "Read Committed" ACID isolation.

> But having a reliable node failure monitor that can react fast enough to ensure availability is really the hard part.

Well, you'll remain available for reads and writes, but the size of "pending" might grow. You essentially need asynchronous distributed garbage collection, which will stall in the presence of partitions and may require the failure detectors I mentioned.

> The paper does talk about how non-overlapping transactions won't block each other (which is nice but not a solution)

I don't see how this isn't a solution for transactions that desire last-writer-wins semantics. If, as in the examples I listed, writes commute, then a blocked write shouldn't stall others. If you want to prevent Lost Update or Write Skew anomalies (i.e., concurrent update), then you'll have to give up availability and/or block.

What you've called 'W=2' in Couchbase is "write to master and at least one slave." Dynamo-style 'W=2' means "write to any two replicas." This can decrease tail latencies since you don't have to wait for the master--any two will do; similarly for 'R=2'. Indeed, Dynamo 'W=2, R=2' will incur more read load than master-based reads (at least double, but not necessarily triple, in your figures). So I think it's more accurately a trade-off between latency and server load.

There can be big benefits to this redundant work. For example: http://www.bailis.org/blog/doing-redundant-work-to-speed-up-...

But don't take it from me: http://cacm.acm.org/magazines/2013/2/160173-the-tail-at-scal...

Anyway, I'm pretty sure CASSANDRA-4705 (https://issues.apache.org/jira/browse/CASSANDRA-4705), which allows for Dean-style redundant requests, both decreases the read load (at least from the factor of N in your post) and should still reduce tail latency without compromising on semantics.

I don't have skin in this game, but I'm pretty sure that the Dynamo engineers had a good idea of what they were doing. (That said, the regular [non-linearizable] semantics for R+W>N are sort of annoying compared to a master-slave system, but can be fixed with write-backs.)

With HATs, you only need to contact one replica for every key. This is to goal behind our definition of "high availability" (http://www.bailis.org/blog/hat-not-cap-introducing-highly-av...).

In general, I haven't seen algorithms guaranteeing serializability or atomicity that complete without a round trip to at least one other replica (or a possibly long trip to the master). Intuitively, the impossibility results dictate that this must be the case, otherwise partitioned replicas could safely serve requests. Daniel Abadi has a great post about this latency-consistency trade-off: http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-an...

As I tried to stress in the post, we aren't claiming to "beat CAP" or provide "100% ACID compliance"; we're attempting to strengthen the semantic limits of highly available systems. I intended "HAT, not CAP" as a play on acronyms, not as a claim to achieve the impossible.

edit: We're also certainly not claiming to have a "CA" solution, whatever that means. There's a lot of confusion between "CAP atomicity"==linearizability and "ACID atomicity"=="transactional atomicity"/"all or nothing"; see http://www.bailis.org/blog/hat-not-cap-introducing-highly-av...

That said, Snapshot Isolation can lead to anomalies like Example 1.2: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142... If you perform additional synchronization (e.g., 2PL, as you describe), then you can get serializability.

What do you mean by consistency? I agree that there are many ways to ensure that application integrity constraints are not violated--without using serializability. My point is that, without ACID serializability, you'll have to do some extra work to ensure them in general [1].

The author of the post basically seems to treat any isolation level below serializability as some sort of sham perpetrated on the development community, and that's not the case

Weak isolation has a long tradition spanning decades [2] and is hardly a "sham." It's well known that weak isolation doesn't guarantee the ACID properties as traditionally defined. My point is that many databases don't provide ACID as they promise.

It's still a different world than trying to mimic ACID properties in a NoSQL database

In terms of current offerings, I'm sympathetic to this viewpoint, but you might be surprised how cheaply we can get properties like the transactional atomicity you mention.

In general, I'm curious how easily anyone's able to take their application level requirements and map them down into an isolation like "read committed," especially given how awkwardly they're defined [3] and how many corner cases there are.

[1] e.g., http://www.bailis.org/blog/when-is-acid-acid-rarely/#arbitra...

[2] "Granularity of Locks and Degrees of Consistency in a Shared Data Base," Jim Gray et al., 1976 http://diaswww.epfl.ch/courses/adms07/papers/GrayLocks.pdf

[3] e.g., http://www.bailis.org/blog/when-is-acid-acid-rarely/#weak-no...

Things get harder when you're distributed. For example, if you cluster with a sharded master-slave configuration, then, to serialize transactions that span shards/partitions, you'll need to do 2 phase commit or similar between masters for writes and, for most read/write transactions, make sure you don't read from slaves. If you cluster via master-master/active-active, then, for serializability, you'll need locking or some other concurrency control across masters for each shard/partition. Both setups are definitely do-able (if not highly available) but require non-trivial engineering.

Serializability ("I") ensures that database consistency, or maintenance of integrity constraints ("C"), is not violated. While it's possible to get consistency ("C") without serializability (which would give up traditional "I" in favor of a weaker form of isolation), it's often difficult [see http://www.bailis.org/blog/when-is-acid-acid-rarely/#arbitra...].

> "Activities of users at terminals and most application programs should remain unaffected when the internal representation of data is changed and even when some aspects of the external representation are changed." http://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

It's not clear from the slides how RDBMSs manage to conflate these two concerns in practice.

It's also unclear to me how the "Lambda Architecture" differs from what we've been calling [soft real-time] materialized view maintenance for decades.

I'd also add that the consistency related to ACID semantics from relational databases refers to transactional consistency, not replica consistency. Indeed, distributed RDBMSs often opt for strong (replica) consistency models, but there is no reason a distributed relational database can't be weakly (replica) consistent while maintaining ACID semantics on a single machine. Moreover, if the RDBMS must needs to be available in the presence of partitions, it must be weakly (replica) consistent.