Hacker News Reader

Comment by freels | Hacker News Reader

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

View on HN

From my reading of the article, it seems that this may fall under the "don't provide properties that make it easy to build systems on top of them" category. I wasn't even aware that this article was pitching Calvin as a good alternative, it seemed that the article presents Calvin as preliminary research rather than a proof that this is a good model for databases we can build systems on.

You can't do dependent transactions in Calvin. Without experience building systems without dependent transactions, I'm worried that we may underestimate how much of an impact removing dependent transactions has on our ability to design working systems on time and under budget. This echoes earlier problems we had when everyone was building systems that didn't rely on database consistency... we often underestimated how difficult it was to build a working system without database consistency.

You can always execute dependent transactions in a system that does not support them by running two non-dependent transactions. This is covered in section 3.2.1 of the Calvin paper [0] as the Optimistic Lock Location Prediction (OLLP) scheme.

Basically, when you have a dependent transaction (i.e., a transaction where the write set depends on the results of earlier reads in the transaction), you split it into two separate transactions. The first transaction, the reconnaissance transaction, reads all the data necessary to determine the transaction's write set. Then the second transaction can declare the full read/write set based on the results of the recon transaction. While executing the second transaction, you verify that the data you're reading is the same as the data you read in the recon transaction; if it's not, you need to start the whole process over.

This is certainly unfortunate, because you have to perform every read twice. But perhaps it's performant enough. Have you tried using FaunaDB/Calvin for your workload? It sounds like FaunaDB has support for dependent transactions using OLLP baked in, but I'm curious to know if there's a significant performant hit to using it.

[0]: http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1...

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.

That or even just keeping a 'small' recently read cache if the source knows the results are part of a recon operation. The implementation details probably do depend on questions like: is there only one authoritative source for that data?

This double read sounds a lot like 2PC itself! Definitely not a coincidence.

2PC requires two network round trips and a global synchronization point. Plus it has the blocking problem and the cloggage problem described in the blog post. The first read of OLLP is before the first lock is acquired, so it doesn't result in any additional cloggage, and definitely no blocking problem.

There's two round trips if the read is foreign as it needs to be done twice.

But my point was supposed to be positive. Doing something like 2PC or something like it only when it's needed is a huge improvement in the "pay for what you use" vein.

You just described optimistic concurrency control. That's one way of doing things if your workload is not highly contentious.

I'm not sure what you're arguing here. Yes, I described a very specific type of optimistic concurrency control that can be layered on top of Calvin to provide support for dependent transactions. (The "optimistic" is in the name of OLLP, after all.) But the underlying Calvin protocol is not optimistic, as it acquires locks. The result is a hybrid scheme that is neither fully optimistic nor fully pessimistic.

How is it guaranteed that a transaction will make progress? It sounds like every (initial state -> a,b,c,d),(initial state = a,b,c,d; modified state -> a,B,C,d) can be aborted by another transaction? Is there some queuing system for transactions, or timed locks?

And for distributed shared systems, not all shards will have all of (a,b,c,d) in order to make a decision.

If one of the shards fails (i.e. write error) how would the transaction on the other shards abort? If there was shard redundancy I can see this becoming less likely, but by no means impossible.

Sure, maybe they can roll back transactions, but that presents a time window of wrong state to the world.

OLLP by itself is not guaranteed to make progress, but it is easy to prevent starvation via exerting more control at the preprocessing layer. The three papers to read related to this subject are:

(1) http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf

(2) http://www.cs.umd.edu/~abadi/papers/calvin-tods14.pdf

(3) http://www.cs.umd.edu/~abadi/papers/determinism-eval.pdf

Aborts due to OLLP are state-based aborts, so other shards fail via the conditional logic described in the blog post.

To clarify a couple of things:

(1) Calvin does support dependent transactions (it uses OLLP to support them.

(2) Calvin is just one example of a system that disallows arbitrary aborts. We've built a bunch of them in my lab.

(3) I do not believe that disallowing arbitrary aborts results in fundamentally new limitations of the system. You can still use pessimistic or optimistic concurrency control. You can use deterministic or nondeterministic systems. You don't have to assume you know the read-write set in advance. And you can certainly support dependent transactions.

Thanks for clarifying, this was definitely not clear from the article. Is this article part of a series? It's still not clear to me why OLLP works. When I think of optimistic concurrency my next concern is whether the system is guaranteed to make progress.

I wasn't intending for it to be part of a series, but I agree that the OLLP technique may be of interest to a general audience and therefore a good subject for a future post.

Reply on news.ycombinator.com