Comment by DivineTraube | Hacker News Reader

Comment by DivineTraube | Hacker News Reader

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

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

It would be interesting to have one of the CochroachDB guys comment on the novelty of their approach.

Post author here:

In terms of Google products, CockroachDB much more closely resembles a combination Spanner (http://research.google.com/archive/spanner.html) and F1 (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/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-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.

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

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.

It would be great to know its name to simplify communication with the colleagues, do you know it?

Amazon doesn't mention Google or Percolator either.

But are they written in Go?

Reply on news.ycombinator.com