Why Cassandra Doesn't Need Vector Clocks • Hacker News Board

Re: Why Cassandra Doesn't Need Vector Clocks

#11

Post by jbellis » Wed, Sep 04, 2013, 9:47 PM UTC

seancribbs wrote: post #2

Since they're not likely to approve my comment on their blog, here's what I said: "Way to misrepresent[1] vector clock usage in Riak! LWW deliberately ignores the vector clock. No one would use that in production without a strong assurance that they will never have concurrent writes. Also note that later in the post[2] Kyle shows how using them properly leads to zero data-loss. [1] https://yourlogicalfallacyis.com/st…

I explained my reasoning in more detail in the paragraphs starting with "Vector clocks are good at helping clients with simple merges like the above user object, but it’s important to understand that vector clocks only tell you that a conflict occurred, and not how to resolve it" and "What Cassandra gives up here is the ability to create custom behavior for updates-based-on-existing-values. However, as counters illustrate, vector clocks are often inadequate for this as well. Usually you end up having to store the entire version history, which Cassandra supports by clustering with uuids."

I think what you and aphyr are getting hung up on is this last part.

In any case, I wrote this because I got tired of people who read the Dynamo paper but haven't thought it through reacting to Cassandra with ZOMG YOU'LL SURELY LOSE DATA WITHOUT VECTOR CLOCKS. When in fact, this decision represents one that we made deliberately, for the reasons I've tried to describe. Maybe some not casting aspersions on other valid designs might be in order all around.

Thanks for reading!

Re: Why Cassandra Doesn't Need Vector Clocks

#12

Post by aphyr » Wed, Sep 04, 2013, 9:50 PM UTC

jbellis wrote: post #11

seancribbs wrote: post #2

Since they're not likely to approve my comment on their blog, here's what I said: "Way to misrepresent[1] vector clock usage in Riak! LWW deliberately ignores the vector clock. No one would use that in production without a strong assurance that they will never have concurrent writes. Also note that later in the post[2] Kyle shows how using them properly leads to zero data-loss. [1] https://yourlogicalfallacyis.com/st…

I explained my reasoning in more detail in the paragraphs starting with "Vector clocks are good at helping clients with simple merges like the above user object, but it’s important to understand that vector clocks only tell you that a conflict occurred, and not how to resolve it" and "What Cassandra gives up here is the ability to create custom behavior for updates-based-on-existing-values. However, as counters illus…

But... you will lose data if your conflict resolution strategy is LWW, unless you do all writes to unique objects. Siblings+vclocks are provably equivalent to that strategy; they just allow you to garbage-collect unnecessary parts of the causal history more efficiently. Neither strategy frees you from having to define a commutative, associative, and idempotent merge function to perform a read.

Re: Why Cassandra Doesn't Need Vector Clocks

#13

Post by astral303 » Wed, Sep 04, 2013, 9:50 PM UTC

jbellis wrote: post #9

astral303 wrote: post #7

Cassandra counters once were implemented as a blazing-fast vector-clock patch [1,2] that did not involve read-before-write on update. The biggest (IMO) downside is that it did not support decrements. So Cassandra tech leadership decided [2] to implement counters as "read, increment, write." However, that came with two major downsides: 1) counter updates were now no longer replayable--so if you experience an update ti…

I think you've misread the 580 patch. By definition, you need to read the existing vector clock value before you can issue an update against it. /Member of the presumedly incompetent Cassandra tech leadership

Based on the algorithm described in the link here: http://www.slideshare.net/kakugawa/distributed-counters-in-c... -- the insert path does not perform any reads, unless the column is already in the memtable (so no disk read). Am I missing something?

Re: Why Cassandra Doesn't Need Vector Clocks

#14

Post by marshray » Wed, Sep 04, 2013, 9:52 PM UTC

Riak/C* noob here. Couldn't I just store data as column cells in Riak?

    bucket: 'users'
    'jbellis/email', 'jbellis@example.com'
    'jbellis/phone', '555-5555'

What would I lose by doing this?

Re: Why Cassandra Doesn't Need Vector Clocks

#15

Post by jbellis » Wed, Sep 04, 2013, 9:56 PM UTC

astral303 wrote: post #13

jbellis wrote: post #9

Earlier quoted context omitted.

I think you've misread the 580 patch. By definition, you need to read the existing vector clock value before you can issue an update against it. /Member of the presumedly incompetent Cassandra tech leadership

Based on the algorithm described in the link here: http://www.slideshare.net/kakugawa/distributed-counters-in-c... -- the insert path does not perform any reads, unless the column is already in the memtable (so no disk read). Am I missing something?

That is describing the 1072 approach aka the one in Cassandra today. Incrementing without read-before-write was one of the reasons Twitter liked it.

Unfortunately, while you can increment on a single node without read-before-write, you need to merge it with the existing value before you can replicate to the others. Read-before-replicate, if you will.

Theres a more recent, quite long discussion over https://issues.apache.org/jira/browse/CASSANDRA-4775 that boils down to, "this is actually the best we can do."

Re: Why Cassandra Doesn't Need Vector Clocks

#16

Post by jbellis » Wed, Sep 04, 2013, 9:59 PM UTC

aphyr wrote: post #12

jbellis wrote: post #11

Earlier quoted context omitted.

I explained my reasoning in more detail in the paragraphs starting with "Vector clocks are good at helping clients with simple merges like the above user object, but it’s important to understand that vector clocks only tell you that a conflict occurred, and not how to resolve it" and "What Cassandra gives up here is the ability to create custom behavior for updates-based-on-existing-values. However, as counters illus…

But... you will lose data if your conflict resolution strategy is LWW, unless you do all writes to unique objects. Siblings+vclocks are provably equivalent to that strategy; they just allow you to garbage-collect unnecessary parts of the causal history more efficiently. Neither strategy frees you from having to define a commutative, associative, and idempotent merge function to perform a read.

The whole point is that "conflicting" updates to a single column is supposed to cause overwrites ("data loss"). If I wanted to keep multiple values in a column around I'd use a Map or a Set instead!

Maybe the disconnect is that in Riak, you have to fetch the existing document before modifying it anyway, so there is a lot of "update-based-on-existing-document" code around. Cassandra is designed to encourage "blind," idempotent updates instead.

Re: Why Cassandra Doesn't Need Vector Clocks

#17

Post by aphyr » Wed, Sep 04, 2013, 10:10 PM UTC

jbellis wrote: post #16

aphyr wrote: post #12

Earlier quoted context omitted.

But... you will lose data if your conflict resolution strategy is LWW, unless you do all writes to unique objects. Siblings+vclocks are provably equivalent to that strategy; they just allow you to garbage-collect unnecessary parts of the causal history more efficiently. Neither strategy frees you from having to define a commutative, associative, and idempotent merge function to perform a read.

The whole point is that "conflicting" updates to a single column is supposed to cause overwrites ("data loss"). If I wanted to keep multiple values in a column around I'd use a Map or a Set instead! Maybe the disconnect is that in Riak, you have to fetch the existing document before modifying it anyway, so there is a lot of "update-based-on-existing-document" code around. Cassandra is designed to encourage "blind," i…

If I wanted to keep multiple values in a column around I'd use a Map or a Set instead!

[edit: thanks iamalesky, correction on cell keys]

If you're following along at home, Lists are implemented by choosing a UUID cell key for each distinct element of the collection; Maps and Sets use the key and value, respectively. The conflict resolution function applied at read time is, for Sets, set union, plus tombstones elements for deletion. Depending on the resolution strategy used, similar consistency anomalies to LWW may be present; e.g clock skew allows for various possible outcomes of logically concurrent mutation of a collection.

Re: Why Cassandra Doesn't Need Vector Clocks

#18

Post by iamaleksey » Wed, Sep 04, 2013, 10:34 PM UTC

marshray wrote: post #14

Riak/C* noob here. Couldn't I just store data as column cells in Riak? bucket: 'users' 'jbellis/email', 'jbellis@example.com' 'jbellis/phone', '555-5555' What would I lose by doing this?

Performance, mostly. To read both the email and the phone you'll have to make two requests (or a single multiget). The keys have a good chance of belonging to different replicas, too, and even if they don't, you are still going to have 2x disk reads.

Re: Why Cassandra Doesn't Need Vector Clocks

#19

Post by brown9-2 » Wed, Sep 04, 2013, 10:35 PM UTC

jbellis wrote: post #16

aphyr wrote: post #12

Earlier quoted context omitted.

But... you will lose data if your conflict resolution strategy is LWW, unless you do all writes to unique objects. Siblings+vclocks are provably equivalent to that strategy; they just allow you to garbage-collect unnecessary parts of the causal history more efficiently. Neither strategy frees you from having to define a commutative, associative, and idempotent merge function to perform a read.

The whole point is that "conflicting" updates to a single column is supposed to cause overwrites ("data loss"). If I wanted to keep multiple values in a column around I'd use a Map or a Set instead! Maybe the disconnect is that in Riak, you have to fetch the existing document before modifying it anyway, so there is a lot of "update-based-on-existing-document" code around. Cassandra is designed to encourage "blind," i…

Doesn't this assume that both writers want their value for the column to win, instead of one of them possibly deciding that it shouldn't write it's value if one already exists for the field?

Re: Why Cassandra Doesn't Need Vector Clocks

#20

Post by iamaleksey » Wed, Sep 04, 2013, 10:38 PM UTC

aphyr wrote: post #17

jbellis wrote: post #16

Earlier quoted context omitted.

The whole point is that "conflicting" updates to a single column is supposed to cause overwrites ("data loss"). If I wanted to keep multiple values in a column around I'd use a Map or a Set instead! Maybe the disconnect is that in Riak, you have to fetch the existing document before modifying it anyway, so there is a lot of "update-based-on-existing-document" code around. Cassandra is designed to encourage "blind," i…

If I wanted to keep multiple values in a column around I'd use a Map or a Set instead! [edit: thanks iamalesky, correction on cell keys] If you're following along at home, Lists are implemented by choosing a UUID cell key for each distinct element of the collection; Maps and Sets use the key and value, respectively. The conflict resolution function applied at read time is, for Sets, set union, plus tombstones element…

In case you are talking about Cassandra collections (maps and sets), and not abstract maps/sets, then you are wrong. Only CQL3 Lists work like that - there are no UUIDs anywhere in CQL3 maps/sets implementations.