8 ms·

How CockroachDB Does Distributed, Atomic Transactions

147 points by orangechairs 11y ago

jchrisa 11y ago
I'm not sure if CockroachDB has multi-DC async replication, but the challenge I've always found in this stuff is ensuring the transaction also commits on remote replicas in an all-or-nothing way. Maybe I didn't read close enough...
- sargun 11y ago
  They have Multi-Raft running between all of the replicas of a specific key range to ensure that there is an atomic commit across all DCs.
- mrtracy 11y ago
  Post author here Sargun is correct, all of our replication is performed by Raft, which exists at a lower level than the content covered in this post. Every command executed against a cockroach key (i.e. "create write intent", "begin this transaction") is persisted to the Raft log before executing; Commands will not proceed if they are not confirmed by Raft. The outcome of all commands is deterministic, so this provides complete replication of all mutations to each key. If you're interested, there's more information available in our primary design document: (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#raft---consistency-of-range-replicas https://github.com/cockroachdb/cockroach/blob/master/docs/de...)
saganus 11y ago
This looks very interesting, but I still don't get how do they avoid concurrency on the switch: "The switch cannot be concurrently accessed – reads and writes of the switch are strictly ordered". If not with a lock file, maybe a log-based architecture?
- nicwolff 11y ago
  The detail section says "by a combination of raft and our underlying storage engine"
- mrtracy 11y ago
  Post author here! The on disk part of the "switch", our transaction record, can only be accessed internally. There are only a small number of operations to perform on it - create it, read its value, and a small number of deterministic "read-then-write" operations. For example, in the case of an "abandoned" transaction, a later transaction may want to read the abandoned transaction record, see if it is still "pending", and then mark it as "aborted" if it is. Our runtime orders all such operations on the same record so that they are completely sequential - that is, even for a "read-then-write" operation, it must completely finish before any other operation can occur on that key. This is done using basic runtime synchronization primitives (mutexes, channels, etc).
  - saganus 11y ago
    Thanks for the detailed explanation. Looking forward for the next post!
ahachete 11y ago
Thank you for sharing your strategy for concurrent transactions. It's a very interesting topic :) I see however some possible pain points in this strategy. My main concerns are: * This looks to me a lot like some poor (no pun intended) form of MVCC (https://en.wikipedia.org/wiki/Multiversion_concurrency_control https://en.wikipedia.org/wiki/Multiversion_concurrency_contr...). Basically, it supports only two "V"s, the "on" and "off", while "normal" MVCC implementations support as many as required. * Related to the above, I don't see how you can support more than one overlapping tx with this strategy. Sure, I'll keep tuned for the next post on this topic, but I fail to see how --without exclusive locking-- it could be done based on these principles. * Every read seems like it needs to check the switch. I understand this might be expensive, specially if there is a concurrent modification in progress. Keys are co-located in the node, but they still require random access. * It looks like even aborted transactions require writes to the database. And every transaction requires at least two writes (the write intent and its consolidation to the key). I don't expect good performance here. Please help me clarify these questions, specially if I'm missing something. Hope it helps anyway. Thanks!
- wicknicks 11y ago
  Yeah, I am not sure how multiple queries will co-exist in this strategy. Especially, if you have two queries which are not commutative (say, one which increments a column and the other one which replaces the column with its square root). Also, how does this work in the presence of replicas? Does every replica go through the strategy? What if one or more replicas go down during a transaction?
- saganus 11y ago
  Excellent questions! thanks for this, I Was too lazy to lay them down like this. I hope they get an answer!
- openasocket 11y ago
  I'm not at all associated with the Cockroach folks, but I'm pretty sure they actually do use MVCC, and the description they gave in this post is a simplification of the actual implementation. At least, there are a bunch of references to MVCC in their codebase: https://github.com/cockroachdb/cockroach/tree/master/storage/engine https://github.com/cockroachdb/cockroach/tree/master/storage...
sargun 11y ago
Why didn't you go down the route of Paxos Commit for your ACP versus the Yabandeh-style ACP? I realize that they have very different semantics, but Paxos Commit seems to have (nearly) all the same properties, and benefits without a single key, that basically acts as the "coordinator" for the transaction (a process as opposed to a key).
tbrock 11y ago
Interesting read, the CochroachDB guys are top notch engineers. I'm excited to see how this product develops.
DivineTraube 11y ago
This is the transaction protocol from Google Percolator - with slightly different wording. I don't know if that's a well known fact but I was surprised they did not even mention it. OSDI Paper on Percolator: https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf https://www.usenix.org/legacy/event/osdi10/tech/full_papers/... Percolator is the processing system Google uses to manage its search index incrementally. It's built on BigTable which provides cell-level linearizability, similar to what CockroachDB seems to achieve by using Raft. What CockroachDB calls "intents" are per-value columns called "write" in Percolator and ordered by BigTables timestamp system. Percolators "master lock" is rebranded to "switch" and, tada, there you have CockroachDBs fancy lockless algorithm. Edit: Amazon DynamoDB, too, uses a very similar approach to this in their client-driven transaction implementation https://github.com/awslabs/dynamodb-transactions/blob/master/DESIGN.md https://github.com/awslabs/dynamodb-transactions/blob/master... It would be interesting to have one of the CochroachDB guys comment on the novelty of their approach.
- glibgil 11y ago
  Amazon doesn't mention Google or Percolator either.
- sparaker 11y ago
  But are they written in Go?
- teraflop 11y ago
  I don't think either CockroachDB or Percolator is claiming any novelty for this basic approach. The Percolator article cites another paper from 1981 that discusses essentially the same idea. (I think it's the same, at least -- the writing is pretty terse, and I've only skimmed it so far.) http://www.cs.berkeley.edu/~brewer/cs262/concurrency-distributed-databases.pdf http://www.cs.berkeley.edu/~brewer/cs262/concurrency-distrib... Many of the general principles for this kind of distributed database have been known for decades; the key to making it practical is in the details.
- mrtracy 11y ago
  Post author here: In terms of Google products, CockroachDB much more closely resembles a combination Spanner (http://research.google.com/archive/spanner.html http://research.google.com/archive/spanner.html) and F1 (http://research.google.com/pubs/pub41344.html http://research.google.com/pubs/pub41344.html). However, while we do share many traits with these systems (a consistently replicated, transactional key/value store with a SQL interface), our internal transactional model is actually quite different. If you're interested in some of the papers that inspired CockroachDB's transactional model, we have mentioned a number of them in our design doc (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#lock-free-distributed-transactions https://github.com/cockroachdb/cockroach/blob/master/docs/de...). As for Percolator, that system is not a general purpose database but an "incremental processor" for large datasets (such as a web crawler). While it does use a snapshot transaction system internally, it appears to use real exclusive access locks, which CockroachDB does not use. Our write intents are not locks, because they do not guarantee exclusive access to a resource (I've expanded on this in another comment on the blog: http://www.cockroachlabs.com/blog/how-cockroachdb-distributes-atomic-transactions/#comment-2232720938 http://www.cockroachlabs.com/blog/how-cockroachdb-distribute...) We are not claiming our transaction model to be exceptionally novel, this post is just trying to shed light on a specific property of that model.
Exuma 11y ago
Could you have picked a worse more disgusting name? You want people to feel good when they think of your product, not repulsed.
- Strom 11y ago
  You may also want to hint that user data will survive even a nuclear winter.
  - wingerlang 11y ago
    I think a nicer name would be RoachDB. But CockroachDB/Cockroach labs is quite a memorable name, more so than roachdb for sure.
hartror 11y ago
I look forward to a Kyle Kingsbury (Aphyr) "Call me maybe" post. eg. https://aphyr.com/posts/324-call-me-maybe-aerospike https://aphyr.com/posts/324-call-me-maybe-aerospike
joshribakoff 11y ago
So they do it without a lock by using a "switch" instead. What is the difference? Or is it the same concept as a "lock" but they've just created a whole new confusion around terms by trying to be different? Edit - there's an answer on the blog's comments. Apparently it differs from a lock because " it won't prevent any operations from executing, it will just properly order them"
grogers 11y ago
I'll be interested to see the further details discussed in the isolation post, which might answer some questions. This is basically the same how the DynamoDB client transaction library works. The two major problems with that library are: * High write amplification (7N for DDB, probably similar for CockroachDB) * Poor throughput under contention. This is mostly due to the immediately abort conflicting pending transactions policy, which could be changed if contention is frequent (client side exponential back off is probably good enough for most cases). The special sauce they didn't mention might also help here.
knodi 11y ago
I love CockroachDB but the name is dismissed by many that don't know all its capabilities.
aidenn0 11y ago
I'm much more interested in how they get "C" in a distributed DB than how they get "A"
ruggeri 11y ago
The writeup mentions that concurrent attempts to update a row will be discussed in a future post. The simplified discussion here says that a writer who encounters a write intent of an uncommitted transaction aborts the concurrent transaction. I believe also that non-repeatable reads would be a potential problem. A transaction could read a row, then read it a second time; if a concurrent, committed transaction mutated the row, the repeated read will return a different result. I believe that both these problems would be solved by MVCC which I suspect is the next blog post. But I'm not super great at distributed DB stuff, so please correct me if I've misunderstood!
- mrtracy 11y ago
  Post Author here! Your understanding of this particular issue is correct: the system described in this post would not be able to provide repeatable reads. However, as you've alluded to, Cockroach transactions use a form of snapshot isolation (implemented with MVCC) which does provide repeatable reads. And yes, that will be the subject of my next post. :)

147 points by orangechairs 11y ago

I'm not sure if CockroachDB has multi-DC async replication, but the challenge I've always found in this stuff is ensuring the transaction also commits on remote replicas in an all-or-nothing way. Maybe I didn't read close enough...

sargun 11y ago
They have Multi-Raft running between all of the replicas of a specific key range to ensure that there is an atomic commit across all DCs.
mrtracy 11y ago
Post author here Sargun is correct, all of our replication is performed by Raft, which exists at a lower level than the content covered in this post. Every command executed against a cockroach key (i.e. "create write intent", "begin this transaction") is persisted to the Raft log before executing; Commands will not proceed if they are not confirmed by Raft. The outcome of all commands is deterministic, so this provides complete replication of all mutations to each key. If you're interested, there's more information available in our primary design document: (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#raft---consistency-of-range-replicas https://github.com/cockroachdb/cockroach/blob/master/docs/de...)

saganus 11y ago

This looks very interesting, but I still don't get how do they avoid concurrency on the switch: "The switch cannot be concurrently accessed – reads and writes of the switch are strictly ordered". If not with a lock file, maybe a log-based architecture?

nicwolff 11y ago
The detail section says "by a combination of raft and our underlying storage engine"
mrtracy 11y ago
Post author here! The on disk part of the "switch", our transaction record, can only be accessed internally. There are only a small number of operations to perform on it - create it, read its value, and a small number of deterministic "read-then-write" operations. For example, in the case of an "abandoned" transaction, a later transaction may want to read the abandoned transaction record, see if it is still "pending", and then mark it as "aborted" if it is. Our runtime orders all such operations on the same record so that they are completely sequential - that is, even for a "read-then-write" operation, it must completely finish before any other operation can occur on that key. This is done using basic runtime synchronization primitives (mutexes, channels, etc).
- saganus 11y ago
  Thanks for the detailed explanation. Looking forward for the next post!

ahachete 11y ago

Thank you for sharing your strategy for concurrent transactions. It's a very interesting topic :) I see however some possible pain points in this strategy. My main concerns are: * This looks to me a lot like some poor (no pun intended) form of MVCC (https://en.wikipedia.org/wiki/Multiversion_concurrency_control https://en.wikipedia.org/wiki/Multiversion_concurrency_contr...). Basically, it supports only two "V"s, the "on" and "off", while "normal" MVCC implementations support as many as required. * Related to the above, I don't see how you can support more than one overlapping tx with this strategy. Sure, I'll keep tuned for the next post on this topic, but I fail to see how --without exclusive locking-- it could be done based on these principles. * Every read seems like it needs to check the switch. I understand this might be expensive, specially if there is a concurrent modification in progress. Keys are co-located in the node, but they still require random access. * It looks like even aborted transactions require writes to the database. And every transaction requires at least two writes (the write intent and its consolidation to the key). I don't expect good performance here. Please help me clarify these questions, specially if I'm missing something. Hope it helps anyway. Thanks!

wicknicks 11y ago
Yeah, I am not sure how multiple queries will co-exist in this strategy. Especially, if you have two queries which are not commutative (say, one which increments a column and the other one which replaces the column with its square root). Also, how does this work in the presence of replicas? Does every replica go through the strategy? What if one or more replicas go down during a transaction?
saganus 11y ago
Excellent questions! thanks for this, I Was too lazy to lay them down like this. I hope they get an answer!
openasocket 11y ago
I'm not at all associated with the Cockroach folks, but I'm pretty sure they actually do use MVCC, and the description they gave in this post is a simplification of the actual implementation. At least, there are a bunch of references to MVCC in their codebase: https://github.com/cockroachdb/cockroach/tree/master/storage/engine https://github.com/cockroachdb/cockroach/tree/master/storage...

sargun 11y ago

Why didn't you go down the route of Paxos Commit for your ACP versus the Yabandeh-style ACP? I realize that they have very different semantics, but Paxos Commit seems to have (nearly) all the same properties, and benefits without a single key, that basically acts as the "coordinator" for the transaction (a process as opposed to a key).

tbrock 11y ago

Interesting read, the CochroachDB guys are top notch engineers. I'm excited to see how this product develops.

DivineTraube 11y ago

This is the transaction protocol from Google Percolator - with slightly different wording. I don't know if that's a well known fact but I was surprised they did not even mention it. OSDI Paper on Percolator: https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf https://www.usenix.org/legacy/event/osdi10/tech/full_papers/... Percolator is the processing system Google uses to manage its search index incrementally. It's built on BigTable which provides cell-level linearizability, similar to what CockroachDB seems to achieve by using Raft. What CockroachDB calls "intents" are per-value columns called "write" in Percolator and ordered by BigTables timestamp system. Percolators "master lock" is rebranded to "switch" and, tada, there you have CockroachDBs fancy lockless algorithm. Edit: Amazon DynamoDB, too, uses a very similar approach to this in their client-driven transaction implementation https://github.com/awslabs/dynamodb-transactions/blob/master/DESIGN.md https://github.com/awslabs/dynamodb-transactions/blob/master... It would be interesting to have one of the CochroachDB guys comment on the novelty of their approach.

glibgil 11y ago
Amazon doesn't mention Google or Percolator either.
sparaker 11y ago
But are they written in Go?
teraflop 11y ago
I don't think either CockroachDB or Percolator is claiming any novelty for this basic approach. The Percolator article cites another paper from 1981 that discusses essentially the same idea. (I think it's the same, at least -- the writing is pretty terse, and I've only skimmed it so far.) http://www.cs.berkeley.edu/~brewer/cs262/concurrency-distributed-databases.pdf http://www.cs.berkeley.edu/~brewer/cs262/concurrency-distrib... Many of the general principles for this kind of distributed database have been known for decades; the key to making it practical is in the details.
mrtracy 11y ago
Post author here: In terms of Google products, CockroachDB much more closely resembles a combination Spanner (http://research.google.com/archive/spanner.html http://research.google.com/archive/spanner.html) and F1 (http://research.google.com/pubs/pub41344.html http://research.google.com/pubs/pub41344.html). However, while we do share many traits with these systems (a consistently replicated, transactional key/value store with a SQL interface), our internal transactional model is actually quite different. If you're interested in some of the papers that inspired CockroachDB's transactional model, we have mentioned a number of them in our design doc (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#lock-free-distributed-transactions https://github.com/cockroachdb/cockroach/blob/master/docs/de...). As for Percolator, that system is not a general purpose database but an "incremental processor" for large datasets (such as a web crawler). While it does use a snapshot transaction system internally, it appears to use real exclusive access locks, which CockroachDB does not use. Our write intents are not locks, because they do not guarantee exclusive access to a resource (I've expanded on this in another comment on the blog: http://www.cockroachlabs.com/blog/how-cockroachdb-distributes-atomic-transactions/#comment-2232720938 http://www.cockroachlabs.com/blog/how-cockroachdb-distribute...) We are not claiming our transaction model to be exceptionally novel, this post is just trying to shed light on a specific property of that model.

Exuma 11y ago

Could you have picked a worse more disgusting name? You want people to feel good when they think of your product, not repulsed.

Strom 11y ago
You may also want to hint that user data will survive even a nuclear winter.
- wingerlang 11y ago
  I think a nicer name would be RoachDB. But CockroachDB/Cockroach labs is quite a memorable name, more so than roachdb for sure.

hartror 11y ago

I look forward to a Kyle Kingsbury (Aphyr) "Call me maybe" post. eg. https://aphyr.com/posts/324-call-me-maybe-aerospike https://aphyr.com/posts/324-call-me-maybe-aerospike

joshribakoff 11y ago

So they do it without a lock by using a "switch" instead. What is the difference? Or is it the same concept as a "lock" but they've just created a whole new confusion around terms by trying to be different? Edit - there's an answer on the blog's comments. Apparently it differs from a lock because " it won't prevent any operations from executing, it will just properly order them"

grogers 11y ago

I'll be interested to see the further details discussed in the isolation post, which might answer some questions. This is basically the same how the DynamoDB client transaction library works. The two major problems with that library are: * High write amplification (7N for DDB, probably similar for CockroachDB) * Poor throughput under contention. This is mostly due to the immediately abort conflicting pending transactions policy, which could be changed if contention is frequent (client side exponential back off is probably good enough for most cases). The special sauce they didn't mention might also help here.

knodi 11y ago

I love CockroachDB but the name is dismissed by many that don't know all its capabilities.

aidenn0 11y ago

I'm much more interested in how they get "C" in a distributed DB than how they get "A"

ruggeri 11y ago

The writeup mentions that concurrent attempts to update a row will be discussed in a future post. The simplified discussion here says that a writer who encounters a write intent of an uncommitted transaction aborts the concurrent transaction. I believe also that non-repeatable reads would be a potential problem. A transaction could read a row, then read it a second time; if a concurrent, committed transaction mutated the row, the repeated read will return a different result. I believe that both these problems would be solved by MVCC which I suspect is the next blog post. But I'm not super great at distributed DB stuff, so please correct me if I've misunderstood!

mrtracy 11y ago
Post Author here! Your understanding of this particular issue is correct: the system described in this post would not be able to provide repeatable reads. However, as you've alluded to, Cockroach transactions use a form of snapshot isolation (implemented with MVCC) which does provide repeatable reads. And yes, that will be the subject of my next post. :)