6 ms·

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?

knz42 10y ago
This was discussed earlier on the same blog: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ https://www.cockroachlabs.com/blog/living-without-atomic-clo... Short answer: the DB will check for drifts and correct small drifts automatically.
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 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.)
  - 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 ago
      Hi, 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 ago
      I 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.
mankurt2 10y ago
Hybrid logical and physical clocks. http://muratbuffalo.blogspot.com/2014/07/hybrid-logical-clocks.html http://muratbuffalo.blogspot.com/2014/07/hybrid-logical-cloc...
sriram_malhar 10y 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 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).

knz42 10y ago

This was discussed earlier on the same blog: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ https://www.cockroachlabs.com/blog/living-without-atomic-clo... Short answer: the DB will check for drifts and correct small drifts automatically.

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 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.)
- 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 ago
    Hi, 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 ago
    I 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.

mankurt2 10y ago

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

sriram_malhar 10y 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 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).