4 ms·
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
by benesch 8y ago
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-sigmod12.pdf http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1...
- sacheendra 8y agoYou just described optimistic concurrency control. That's one way of doing things if your workload is not highly contentious.
- benesch 8y agoI'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.
- freels 8y agoThere 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.
- mjevans 8y agoThat 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?
- angry_octet 8y agoHow 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.
- abadid 8y agoOLLP 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 http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf (2) http://www.cs.umd.edu/~abadi/papers/calvin-tods14.pdf http://www.cs.umd.edu/~abadi/papers/calvin-tods14.pdf (3) http://www.cs.umd.edu/~abadi/papers/determinism-eval.pdf 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.
- Ericson2314 8y agoThis double read sounds a lot like 2PC itself! Definitely not a coincidence.
- abadid 8y ago2PC 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.
- Ericson2314 8y agoThere'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.