Live data from Hacker News

Why Cassandra Doesn't Need Vector Clocks

datastax.com

41–50 of 69 posts

Re: Why Cassandra Doesn't Need Vector Clocks

#41
post #38
post #25

Earlier quoted context omitted.

Sorry, I was speaking loosely. More formally: In a system which uses LWW as the conflict resolution strategy, there exist no circumstances under which you can guarantee that a value written to a given key will be causally connected to any future state of the system, unless all values written to that key are identical, or a strong external coordinator (e.g. Zookeeper) orders timestamps. If you have siblings and vclock…

> Since Cassandra did not (until today) offer transactional isolation for any type of multi-cell update I guess it depends on what you mean by "transactional isolation" and "multi-cell update". Certainly there is nothing like ACID, but a single multi-cell update to a given record is guaranteed to be _atomic_, and if you have two concurrent multi-cell updates to a single record, they are guaranteed to eventually resol…

...a single multi-cell update to a given record is guaranteed to be _atomic_, and if you have two concurrent multi-cell updates to a single record, they are guaranteed to eventually resolve to a consistent ordering of those operations (though without a strong clock/timestamp it is non-deterministic from the callers' POV).

I disagree. https://gist.github.com/aphyr/6402464

Re: Why Cassandra Doesn't Need Vector Clocks

#42
post #41
post #38

Earlier quoted context omitted.

> Since Cassandra did not (until today) offer transactional isolation for any type of multi-cell update I guess it depends on what you mean by "transactional isolation" and "multi-cell update". Certainly there is nothing like ACID, but a single multi-cell update to a given record is guaranteed to be _atomic_, and if you have two concurrent multi-cell updates to a single record, they are guaranteed to eventually resol…

...a single multi-cell update to a given record is guaranteed to be _atomic_, and if you have two concurrent multi-cell updates to a single record, they are guaranteed to eventually resolve to a consistent ordering of those operations (though without a strong clock/timestamp it is non-deterministic from the callers' POV). I disagree. https://gist.github.com/aphyr/6402464

Okay, you do raise a good point about what happens if the timestamps happen to be precisely identical. Most of the scenarios I've had where the precise same timestamp was at all likely, the updates would also have been identical. If you want to have overlapping cells resolving highly concurrent writes (not even using wide rows to make precisely concurrent writes go to different cells anyway), Cassandra is probably not the right tool to you.

Of course, if that were considered a likely scenario (generally microsecond collisions at the row level would only be at high probability if you had high concurrency on a record), you have a number of paths open for resolving it, the one that I've usually ended up with is that the two concurrent updates actually should be to two different records ANYWAY (usually you add a client ID to the key, for example) because you want to have a record of them which is later resolved when any partitioning issues are addressed (so, you write with ANY consistency to a log, have sloppy real-time reads that are consistency ONE, but then have another process which does ALL consistency reads on the log and then resolves any conflicts using application logic, before writing with QUORUM consistency to the "source of truth".

Alternatively, you can simply provide a client generated timestamp which has a different scale/resolution with a lower order bits being truly random values. For example, if you have that kind of high-concurrency, you probably don't need to handle a range of timestamps beyond ~50 days. You can then use a client generated timestamp which is a combination of 32 high order bits for milliseconds since the epoch and then a random 32-bit value for the low order bits, which makes the odds of a collision on the timestamp pretty good even for highly concurrent cases.

I'm curious about the use case where you'd have all the concurrency with different but overlapping values, but you'd not want to record them separately and then have some custom app logic for resolving them.

Re: Why Cassandra Doesn't Need Vector Clocks

#43
post #34

Earlier quoted context omitted.

I believe that is precisely what Riak does in the "Riak now does this" link provided, and that's effectively what is going on under the hood with Cassandra. This means more overhead per column and the loss of the ability to just encode the data fields in an application native serialization structure. In effect, you throw out a lot of the less talked about advantages of NoSQL and end up with something more like tradit…

It's not how Riak does this, and it's not what's going on under the hood with Cassandra, either.

Riak has something pretty close to this, and if your table in cassandra looked like:

create bucket.users ( id uuid, username text, email text, phone text, primary key (uuid, username) );

That would be exactly how the data was encoded.

Re: Why Cassandra Doesn't Need Vector Clocks

#44
post #43

Earlier quoted context omitted.

It's not how Riak does this, and it's not what's going on under the hood with Cassandra, either.

Riak has something pretty close to this, and if your table in cassandra looked like: create bucket.users ( id uuid, username text, email text, phone text, primary key (uuid, username) ); That would be exactly how the data was encoded.

The difference is that all the cells with the same `id` would belong to the same partition and stored together, so you'd be able to write them atomically and read them together cheaply in a single operation.

What marshray suggested would look like this:

create table bucket.users (name text, field text, value text, primary key ((name, field))); - with a composite partition key. Then you'd have two separate single-cell partitions "jbellis:email" : "jbellis@example.com" and "jbellis:phone" : "555-5555". You don't want to do that in either Riak or Cassandra.

Re: Why Cassandra Doesn't Need Vector Clocks

#45
post #36
post #27

It's worth noting that HBase has the same method of using LWW on column level updates. While this usually is what you want and like Cassandra it gives you the ability to do fast blind writes there are sometimes that you need to make sure you aren't having conflicting writes. The solution that HBase employs is to have checkAndPut functionality. Basically what this lets you do is write a value and only successfully sav…

Cassandra exposes functionality similar to checkAndPut as Lightweight Transactions: www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0

Ah, good to know that functionality was added. I haven't used Cassandra since the 0.6.x days so my knowledge of what's possible there is rusty.

Re: Why Cassandra Doesn't Need Vector Clocks

#46
post #43

Earlier quoted context omitted.

Riak has something pretty close to this, and if your table in cassandra looked like: create bucket.users ( id uuid, username text, email text, phone text, primary key (uuid, username) ); That would be exactly how the data was encoded.

The difference is that all the cells with the same `id` would belong to the same partition and stored together, so you'd be able to write them atomically and read them together cheaply in a single operation. What marshray suggested would look like this: create table bucket.users (name text, field text, value text, primary key ((name, field))); - with a composite partition key. Then you'd have two separate single-cell…

> What marshray suggested would look like this: create table bucket.users (name text, field text, value text, primary key ((name, field))); - with a composite partition key. Then you'd have two separate single-cell partitions "jbellis:email" : "jbellis@example.com" and "jbellis:phone" : "555-5555". You don't want to do that in either Riak or Cassandra.

Ah I see what you mean. I thought the intent was to group by some unique ID for the user.

Re: Why Cassandra Doesn't Need Vector Clocks

#47
post #37
post #3

Earlier quoted context omitted.

I concur; this is punting on the resolution problem. As far as I can determine in testing with Jepsen, there are no cases where one can safely (e.g. in a way which guarantees some causal connection of your write to a future state of the system) update a cell in Cassandra without a strong timestamp coordinator: either an external system like Zookeeper, or Cassandra 2.0 paxos transactions. Most of the production users…

> As far as I can determine in testing with Jepsen, there are no cases where one can safely (e.g. in a way which guarantees some causal connection of your write to a future state of the system) update a cell in Cassandra without a strong timestamp coordinator: either an external system like Zookeeper, or Cassandra 2.0 paxos transactions. It depends on what you mean by "guarantees". In most real world systems, if you…

The world of consistency is rich: not all systems require serializability, linearizability, or any one write winning. It might be interesting to skim http://pmg.csail.mit.edu/papers/adya-phd.pdf, http://ftp.research.microsoft.com/pub/tr/tr-95-51.pdf, and pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/RR-6956.pdf‎ for a taste.

Re: Why Cassandra Doesn't Need Vector Clocks

#48
post #42
post #41

Earlier quoted context omitted.

...a single multi-cell update to a given record is guaranteed to be _atomic_, and if you have two concurrent multi-cell updates to a single record, they are guaranteed to eventually resolve to a consistent ordering of those operations (though without a strong clock/timestamp it is non-deterministic from the callers' POV). I disagree. https://gist.github.com/aphyr/6402464

Okay, you do raise a good point about what happens if the timestamps happen to be precisely identical. Most of the scenarios I've had where the precise same timestamp was at all likely, the updates would also have been identical. If you want to have overlapping cells resolving highly concurrent writes (not even using wide rows to make precisely concurrent writes go to different cells anyway), Cassandra is probably no…

if that were considered a likely scenario

When timestamps are selected by the Cassandra nodes, I can replicate this failure in 2% to 5% of writes. When timestamps collide, I can replicate this failure in 99.9% of writes. Given that the whole point of isolation is to provide invariants during concurrent modification, it doesn't make any sense to claim that a write is transactionally isolated only insofar as it is not concurrent with other writes.

Re: Why Cassandra Doesn't Need Vector Clocks

#49
post #28

I don't know much about CAP but it doesn't sound right to me. Let's see, you store your data tuple for example for a position say {X,Y} as 2 coordinates. X in one column and Y in another one. Now when it gets updated concurrently and it needs to merge two conflicting {X1,Y1} and {X2,Y2} positions you could end up instead with {X1,Y2} non-existing/impossible/broken position. Is that really that easily broken? Or am I…

In Cassandra the second update agreed upon by the cluster would "win", so either (X1,Y1) or (X2,Y2). Since there is no clock mechanism there is no way for the cluster to see that the data has changed since the requester decided it wanted to update the value.

Rows are not isolated. You might see (X1, Y1), (X1, Y2), (X2, Y1), or (X2, Y2) if timestamps happen to conflict. https://gist.github.com/aphyr/6402464

Re: Why Cassandra Doesn't Need Vector Clocks

#50
post #43

Earlier quoted context omitted.

Riak has something pretty close to this, and if your table in cassandra looked like: create bucket.users ( id uuid, username text, email text, phone text, primary key (uuid, username) ); That would be exactly how the data was encoded.

The difference is that all the cells with the same `id` would belong to the same partition and stored together, so you'd be able to write them atomically and read them together cheaply in a single operation. What marshray suggested would look like this: create table bucket.users (name text, field text, value text, primary key ((name, field))); - with a composite partition key. Then you'd have two separate single-cell…

you'd be able to write them atomically

To clarify, this is only the case if you use Cassandra 2.0 transactions; normal batched writes are not atomic in the sense you're probably thinking.

Post reply on HN