7 ms·
(blog author here) Interestingly, clock drift does not affect the serializability of the transaction history; this system guarantees that the history is serial
by mrtracy 10y 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_johnson 10y agoCan 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.)
- tdrd 10y ago(employee here) It seems to me that your use-case does not require locking specifically - you just want to make sure no concurrent transactions can clobber your "update A". As mrtracy explained, such overlapping transactions are linearizable in CockroachDB, so this invariant is preserved without the need for explicit locking.
- lobster_johnson 10y agoHi, thanks for responding. What I need is for our translog to reflect the order of updates. So if diff A was applied before B, then the translog order also needs to be A, B. (The order only needs to be consistent per document.) This is because we have listeners — through APIs — that play the translog as it happens and maintain various state based on it. Currently, the translog is ordered by a sequential number (because it's cheap in Postgres), but every entry also records the ID of the previous entry (so B will point at A). One could sort by time and then reorder by causality before emitting the linear log to consumers, but that would of course be more complicated than one that is already linear.
- ams6110 10y agoI think it does require locking, because in PostGres (or Oracle) readers do not block writers and writers do not block readers. So to be sure you update the same version you read, you have to select...for update.
- teraflop 10y agoHaving serializable transactions is equivalent to adding "FOR UPDATE" to every SELECT statement, so it sounds like CockroachDB already does what you want. A typical RDBMS will prevent conflicts by forcing queries to block until they can be executed in a conflict-free ordering. CockroachDB instead detects conflicts after the fact and prevents inconsistent transactions from committing, forcing them to retry. The end result -- that is, the set of possible outcomes of a series of transactions -- is the same, but the performance characteristics will be different.