4 ms·

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

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.
rystsov 11y ago
The idea is pretty simple. For example, long time ago when Zookeeper didn't support multi key transaction I had to implement them and came to the same algorithm - http://rystsov.info/2012/09/01/cas.html http://rystsov.info/2012/09/01/cas.html. It would be great to know its name to simplify communication with the colleagues, do you know it?

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.

rystsov 11y ago

The idea is pretty simple. For example, long time ago when Zookeeper didn't support multi key transaction I had to implement them and came to the same algorithm - http://rystsov.info/2012/09/01/cas.html http://rystsov.info/2012/09/01/cas.html. It would be great to know its name to simplify communication with the colleagues, do you know it?