Serializable, Lockless, Distributed: Isolation in CockroachDB

https://www.cockroachlabs.com/blog/serializable-lockless-distributed-isolation-cockroachdb/

by orangechairs • 10 years ago

130 52 10 years ago

tyingq4• 10 years ago

I love the transparency this project operates with. Looking forward to when joins are implemented so I can try using it with something non-trivial.

chillaxtian• 10 years ago

Looking forward to when joins are implemented so I can try using it with something non-trivial.

these types of databases typically don't have joins. you'll be waiting a while.

tyingq4• 10 years ago

It's not a nosql database if that's what you're thinking.

https://github.com/cockroachdb/cockroach/issues/2970

mjibson• 10 years ago

Joins are coming, although they will take some time.

teraflop4• 10 years ago

CockroachDB doesn't currently support joins, but it's been designed so that it can potentially support them, unlike most NoSQL databases. In particular, it supports cross-machine transactions, which are a critical building block for both correctness and performance.

For instance, suppose you want to join on a column that's not a primary key. No big deal in a typical RDBMS; just do an index lookup on the join column. But if your data is sharded across machines, that doesn't work, because you can't update the index without running the risk that readers will observe it in an inconsistent state. Unless you can do transactions, that is.

So I'm optimistic that Cockroach will get join support before too long. The necessary primitives are available, making it "merely" a matter of figuring out the engineering details.

petermattis2• 10 years ago

(employee/founder here)

Re joins: we have top men working on it right now. Joins are definitely an interesting problem for a distributed database.

jandrewrogers• 10 years ago

It is possible to massively distribute joins but it requires a much more sophisticated database design than you see in most distributed database implementations because the whole system has to be designed for that use case e.g. support for ad hoc inter-node orchestration and data flows. At that point you basically have a parallel database instead of just a distributed one.

And if you add an additional requirement to correctly execute ad hoc consistent joins under very high write workloads and continuous failures, then it is definitely non-trivial engineering. But it is possible, I've designed implementations like this before, it just requires a very high degree of effort and skill that is rarely applied to the design of typical NoSQL databases.

manigandham2• 10 years ago

MemSQL does distributed joins really well, using a combination of in-memory rowstore + disk columnstore and the ability to have certain tables replicated to every node for faster joining.

danieltoshea• 10 years ago

How does this work if the clocks drift between the nodes? Does this allow incorrect behavior because one transaction looks like it happened before another?

knz423• 10 years ago

This was discussed earlier on the same blog: https://www.cockroachlabs.com/blog/living-without-atomic-clo...

Short answer: the DB will check for drifts and correct small drifts automatically.

mrtracy3• 10 years ago

(blog author here)

Interestingly, clock drift does not affect the serializability of the transaction history; this system guarantees that the history is serializable, regardless of clock drift.

However, "serializable" only means that the history is equivalent to some serial ordering of transactions - it makes no guarantee that the equivalent serial ordering is consistent with the real-time ordering of the involved transactions. A history with that property (agrees with real-time) is termed "linearizable", and requires additional rules to guarantee in an environment with clock drift.

As mentioned by knz42, there was another Cockroach Labs blog post (written by Spencer Kimball) that addressed this in some detail; that blog post contrasted our strategy for dealing with drift with that of Google's Spanner.

A quick overview of CockroachDB's properties re linearizability: it guarantees that access to any individual key is linearizable, and by composition any two transactions which share a key (that one of the transactions modifies) will be linearizable with respect to each other. However, if two transactions do not have any overlap in modified keys, Cockroach does not (by default) guarantee the resulting commit history is linearizable. CockroachDB's underlying KV layer does have a "linearizable" flag on transactions that can guarantee this, but it requires that transactions be slowed down considerably; Spencer's blog post addresses some other strategies that CockroachDB is considering to address the issue.

lobster_johnson2• 10 years ago

Can Cockroach do the equivalent of a "select ... for update" (e.g., PostgreSQL), where you lock one thing while applying changes elsewhere?

Concrete example: We have app that has a "documents" table and a "translog" table. The translog is like a series of diff-patches, representing changes to the documents. When we write to the translog, we first lock the document with a "select ... for update", so that no intervening translog entries can be written concurrently against the same document, then we patch the document, and then we write the translog entry and commit.

We do this with Postgres, and we can do the same thing with Redis' MULTI since Redis is completely single-threaded. I can't think of any other NoSQL data store that allows a similar "lock A, update A, insert B, unlock A"; for example, Cassandra's "lightweight transactions" are only transactional in the context of a single row.

(By "lock" I'd also accept optimistic locking, where you can retry on failure.)

mankurt2• 10 years ago

Hybrid logical and physical clocks. http://muratbuffalo.blogspot.com/2014/07/hybrid-logical-cloc...

sriram_malhar2• 10 years ago

For serializability, all you care about it is some sequential order. You get that with hybrid logical clocks (http://www.cse.buffalo.edu/tech-reports/2014-04.pdf). It gives you a monotonically increasing timestamp that you can use instead of dumb version numbers.

On the other hand, if you want to ensure linearizability, you do care about the worst case clock drift, which in CockroachDB is a configurable parameter. One can adopt Google's Spanner's approach ("commit wait"), which is to wait out the response to the client to ride out NTP uncertainty (typically a few milliseconds inside a data center, but 100s of milliseconds in the wide area).

barking2• 10 years ago

Sorry if this is a little bit off topic This is a startup with employees that is making a non-commercial open source database system. How will they make a financial return on such a product?

sgarman• 10 years ago

It's common in the industry to build an open source product and then do paid support, hosting, etc with it.

Joyent/Node Sonatype Nexus

barking2• 10 years ago

OK thanks, I sort of thought that it might be something like that but wondered if I was missing some other angle.

LoSboccacc5• 10 years ago

By coincidence I was looking around for a datastore. I almost settled on couchbase when I saw this; easy cluster deployment is my main draw after looking at how bad setting up master-master system is in other solutions (hbase, mongo, couchdb all have eterogeneus nodes and weird failure modes)

One quick question since I saw the devs around and I can't find a final answer on it on google: are there any strong roadblock or performance drawbacks against storing principally medium size binary data like images, say, < 100mb blobs?

Yeah I could use something more appropriate but I'd be back to figuring out hadoop installation or fighting s3 eventual consistency.

ansible• 10 years ago

I don't know that you would be happy trying to store blobs of that size in any distributed database, current or future.

I'd suggest having an immutable distributed blob store, and just store the index in the distributed database.

Of course, now you are half way towards a distributed filesystem...

LoSboccacc5• 10 years ago

but then you'd need to store file path in the datastore, with all the failure modes that follows.

I know what the current best practices are, but for bootstrapped one man startups you always end up with dozen moving parts to be tamed and instead of building stuff you need to solve the same problems over and over again

I'm implementing a datastore on top of glusterfs, which while amateurish is a wonderful learning experience, but since it's nowhere close to being workable I am also looking around for what's happening in this space.

I've this longer term goal about having a serverless framework where the datastore also provide oauth for users, which was inspired by https://github.com/serverless/serverless - would be a boon for client side webapp app style startups.

smoyer• 10 years ago

As a long-time CouchDB user, I'm going to assume that by "weird failure modes", you mean "conflicts". There are some awesome aspects to using CouchDB, but getting used to conflicts certainly took some time. In short, your application needs to include the code to resolve problems that arise due to network partitions or concurrent writes to different nodes. On the other hand, it's a really stable platform and the write-only database files worked really well (we lost zero data in over 5 years of operation ... even with tests that included powering down a node while in use).

But ... I also believe that CockroachDB is going to be the project to finally solve these problems and it's got an SQL interface! I'm waiting for SQL joins, and then I suspect I'll be moving at least some of my clustered PostgreSQL instances to CockroachDB.

LoSboccacc5• 10 years ago

no I mean things like this:

http://docs.couchdb.org/en/stable/cluster/nodes.html#removin...

http://docs.couchdb.org/en/stable/cluster/sharding.html#movi...

http://docs.couchdb.org/en/stable/cluster/sharding.html#resh...

sharding needs to be taken care manually, there is nowhere on the docs handling what happens in the event of a failover and no how to replace a failed populated node with an empty one so that the cluster can recover.

those are quite big concerns if sharding with a replica set for fault tolerance is the main objective.

hnkimb35582• 10 years ago

(employee/founder here)

Anything under 64K is perfectly reasonable to store in a CockroachDB column. Between 64K and maybe 1M is trending towards trouble. Values greater than this are going to go through CockroachDB like a goat through a python.

Why is this the case? For starters, at the level of RocksDB, values greater than 64K are not jammed into SSTables (to avoid constantly rewriting them during compactions of the LSM tree). Instead, individual files are created. Also, CockroachDB has quite a lot of write amplification, which is generally OK for structured relational data, but becomes progressively more terrible for large blobs. Write amplification comes from the Raft log, as well as RocksDB's write-ahead log.

What we really need is an integrated storage system for immutable blobs, something we're taking very seriously. Roughly half of the original team which built Colossus at Google are working on CockroachDB, so there's some knowledge of how to go about building such a system.

While we're not sure where it would fall on our roadmap, the idea is that large blob values would be efficiently replicated and maintained through a separate subsystem. The blob column itself would just contain a pointer to the blob. The value in tight integration (a single CockroachDB cluster providing both OLTP SQL database as well as a distributed blob store) would be one deployment & admin console, and transactionally consistent blob column values (e.g. no fighting s3 eventual consistency).

LoSboccacc5• 10 years ago

Thanks! That's fantastic to hear even if it's going to materialize later/eventually/never at least it's great to know the need is recognized.

Disregarding write amplification issues for a sec, would it make things better to split binaries in 64k chunks and have them in a chunk table keyed by name and offset?

grogers• 10 years ago

Naively it looks like your conflict resolution is prone to livelock, where concurrent transactions for a key keep aborting each other without getting any work done. The same can happen if you run a single node RDBMS in serializable isolation mode and read a row before writing to it. In that case you can add locking reads on rows you intend to later write to, which avoids the livelock.

Have you done any studies to quantify how bad that effect is in cockroachdb? Assuming the effect exists and I didn't just miss something silly, are there any workarounds since cockroachdb is only OCC? (Exponential backoff between retries and keeping transactions short don't count, I assume those are a given)

knz423• 10 years ago

When transactions conflict, the priority of the losing transaction is internally ratcheted up. At some point it's just higher than everything after it and it succeeeds.

mrtracy3• 10 years ago

(author)

This is a good insight; Live Lock was one of the things that kept me up at night, although my fellow contributors have allayed my concerns considerably.

In a write-heavy workload where the transactions follow a read-modify-write pattern, it does seem possible that your application could be facing live lock concerns. So, let's look at where those concerns come from in CockroachDB:

1. For write-write conflicts, live-lock concerns comes from the fact that a later transaction can abort your in-progress transaction if it has a priority. On top of this, if your transaction ends up aborting an earlier transaction, the other transaction may retry with a potentially higher priority, and this can result in a "priority war" of sorts.

2. "Read-write" conflicts have a worse problem: if a transaction with a later timestamp reads a key before your transaction writes to it, then your transaction always aborts. In read-modify-write workloads where the read is first, this seems to be the biggest theoretical source of live-lock.

Now, as for dealing with those issues.

+ The "Write-write" issue is the smaller concern here. The ratcheting-up of priorities is probabilistic; currently, after enough retries your transaction will have a high enough priority that it will almost certainly make progress. However, we are not totally content with this: we have an issue for our 1.0 release (https://github.com/cockroachdb/cockroach/issues/5727) to do some serious investigation of this, with some alternatives already suggested. For example, one such alternative is using "lowest original timestamp wins" to settle conflicts instead of a random priority.

+ The read-write concern seems more problematic; our read timestamp cache retains minimal data due to memory concerns, and thus aborts a bit conservatively (i.e. aborts transactions that might have been able to continue). This can be dealt with by modifying your application pattern - in particular, I would suggest using our "SNAPSHOT" isolation level for many workloads. I didn't cover this in the blog post, but in short the SNAPSHOT mode allows RW conflicts to occur without aborting transactions. SNAPSHOT transactions are subject to the "write skew" anomaly, but this anomaly does not occur if the involved transactions write to a common key. This is fortunately the case for many OLTP-type workloads, meaning SNAPSHOT can be used without anomalies; this also moves conflict-detection responsibility entirely to WW conflicts, which abort less conservatively than RW and should ameliorate any live-lock problems.

ruggeri• 10 years ago

I just wanted to thank the team for this writeup. I've been excited to read it since the last post several months back. This was definitely very useful, and very clearly written.

So many thanks!

Serializable, Lockless, Distributed: Isolation in CockroachDB

Related Stories