Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Cassandra Doesn't Need Vector Clocks

datastax.com

Post reply on HN
Print view View original

61–69 of 69 posts

Re: Why Cassandra Doesn't Need Vector Clocks

#61

Post by cbsmith »

aphyr wrote: post #58
cbsmith wrote: post #54

Earlier quoted context omitted.

> I can replicate this failure in 2% to 5% of writes. Yeah, I'm curious about how you achieved those numbers. Your test that gets that 2-5% of writes (though your docs say 7.5%) to be messed up... what is really is measuring is the probability that out of 5 concurrent clients writing to 4 servers, at least two will finish writing to a row with the exact same timestamp... AND that they will be the LAST ones to write t…

Yeah, I'm curious about how you achieved those numbers. Jepsen's code is open source ( http://github.com/aphyr/jepsen ) and I've written extensively about the techniques involved; see http://aphyr.com/tags/jepsen for details. Cassandra work is upcoming; no formal writeup yet. Your test that gets that 2-5% of writes (though your docs say 7.5%) to be messed up... Sorry, 2-5% was my mistake. Been playing around with the…

> Each client in the Jepsen test harness is (independently) scheduling n writes per second.

Umm... that's kind of an important detail. I'm betting that your mechanism for achieving this effectively synchronizes your clients to act in concert, or at least as close to "in concert" as is possible for your clock to measure. That explains the probability.

> There's an interesting probability anecdote called the Birthday Paradox

Yeah, I thought of the Birthday Paradox with this problem, but this is a different variant. The probability that two people in the room have the same birthday and no one else in the room has a birthday later in the year follows different probabilities.

Try writing a program that spawns 5000 threads and has them get the current time in microseconds, and then write it in a file. You won't have any collisions unless you do some kind of precise coordination between them. In fact, you likely only have a shot at getting the same timestamp if you call from different threads, because just executing the instructions to read the current time takes long enough that two calls in a row will get different values.

> TL;DR: microsecond timestamps do not provide sufficient entropy for uniqueness constraints over common workloads.

See, that's the part I have a problem with, because I've had quite the opposite experience (without even having Cassandra involved).

Re: Why Cassandra Doesn't Need Vector Clocks

#62

Post by aphyr »

cbsmith wrote: post #61
aphyr wrote: post #58

Earlier quoted context omitted.

Yeah, I'm curious about how you achieved those numbers. Jepsen's code is open source ( http://github.com/aphyr/jepsen ) and I've written extensively about the techniques involved; see http://aphyr.com/tags/jepsen for details. Cassandra work is upcoming; no formal writeup yet. Your test that gets that 2-5% of writes (though your docs say 7.5%) to be messed up... Sorry, 2-5% was my mistake. Been playing around with the…

> Each client in the Jepsen test harness is (independently) scheduling n writes per second. Umm... that's kind of an important detail. I'm betting that your mechanism for achieving this effectively synchronizes your clients to act in concert, or at least as close to "in concert" as is possible for your clock to measure. That explains the probability. > There's an interesting probability anecdote called the Birthday P…

Like I said, mean free paths will vary depending on your write profile. None of this alters my original assertion, which is that row operations are not isolated.

Re: Why Cassandra Doesn't Need Vector Clocks

#63

Post by cbsmith »

aphyr wrote: post #62
cbsmith wrote: post #61

Earlier quoted context omitted.

> Each client in the Jepsen test harness is (independently) scheduling n writes per second. Umm... that's kind of an important detail. I'm betting that your mechanism for achieving this effectively synchronizes your clients to act in concert, or at least as close to "in concert" as is possible for your clock to measure. That explains the probability. > There's an interesting probability anecdote called the Birthday P…

Like I said, mean free paths will vary depending on your write profile. None of this alters my original assertion, which is that row operations are not isolated.

You've got a corner case that is way harder to hit than you think you've measured it to be, and the scenarios where it may happen would have almost certainly not have the design required to cause it. Even so, it is addressable.

Based on my own experiences with this scenario, I'd be surprised if you managed to experience any problems if you turned off throttling (and didn't force everything to the same timestamp).

So yeah, you have a scenario that can happen, and I'd recommend anyone who absolutely cannot have that happen either not use Cassandra or design their schema accordingly. Absent that scenario though, row operations are isolated.

Re: Why Cassandra Doesn't Need Vector Clocks

#64

Post by rbranson »

cbsmith wrote: post #63
aphyr wrote: post #62

Earlier quoted context omitted.

Like I said, mean free paths will vary depending on your write profile. None of this alters my original assertion, which is that row operations are not isolated.

You've got a corner case that is way harder to hit than you think you've measured it to be, and the scenarios where it may happen would have almost certainly not have the design required to cause it. Even so, it is addressable. Based on my own experiences with this scenario, I'd be surprised if you managed to experience any problems if you turned off throttling (and didn't force everything to the same timestamp). So…

Finding corner cases is the point of Jepsen :)

Re: Why Cassandra Doesn't Need Vector Clocks

#65

Post by aphyr »

jeremiahjordan wrote: post #59
aphyr wrote: post #50

Earlier quoted context omitted.

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.

They are atomic, they are not isolated. Those are two different properties. The "A" vs the "I" in ACID. http://en.wikipedia.org/wiki/ACID Edit: Actually, they are isolated in the sense of ACID, doesn't matter what order you do to operations, the answer will be the same. But not isolated the way you want isolated described.

No, they are not isolated in the sense of ACID. This behavior violates P0.

Re: Why Cassandra Doesn't Need Vector Clocks

#66

Post by aphyr »

cbsmith wrote: post #63
aphyr wrote: post #62

Earlier quoted context omitted.

Like I said, mean free paths will vary depending on your write profile. None of this alters my original assertion, which is that row operations are not isolated.

You've got a corner case that is way harder to hit than you think you've measured it to be, and the scenarios where it may happen would have almost certainly not have the design required to cause it. Even so, it is addressable. Based on my own experiences with this scenario, I'd be surprised if you managed to experience any problems if you turned off throttling (and didn't force everything to the same timestamp). So…

You're presuming that all reads occur after the system has quiesced. This is not always the case. I'm happy your write pattern works for you, and that you measure your consistency; I'm just trying to keep folks honest about what their systems actually provide; and give them tools to analyze those constraints.

Re: Why Cassandra Doesn't Need Vector Clocks

#67

Post by cbsmith »

jeremiahjordan wrote: post #59
aphyr wrote: post #50

Earlier quoted context omitted.

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.

They are atomic, they are not isolated. Those are two different properties. The "A" vs the "I" in ACID. http://en.wikipedia.org/wiki/ACID Edit: Actually, they are isolated in the sense of ACID, doesn't matter what order you do to operations, the answer will be the same. But not isolated the way you want isolated described.

The scenario that he's found is when the two timestamps are actually identical. In that scenario, Cassandra cannot maintain its atomicity guarantee.

Re: Why Cassandra Doesn't Need Vector Clocks

#68

Post by cbsmith »

aphyr wrote: post #66
cbsmith wrote: post #63

Earlier quoted context omitted.

You've got a corner case that is way harder to hit than you think you've measured it to be, and the scenarios where it may happen would have almost certainly not have the design required to cause it. Even so, it is addressable. Based on my own experiences with this scenario, I'd be surprised if you managed to experience any problems if you turned off throttling (and didn't force everything to the same timestamp). So…

You're presuming that all reads occur after the system has quiesced. This is not always the case. I'm happy your write pattern works for you, and that you measure your consistency; I'm just trying to keep folks honest about what their systems actually provide; and give them tools to analyze those constraints.

> You're presuming that all reads occur after the system has quiesced.

It sure looked like they did, but maybe I misread the code.

> This is not always the case.

Even if that weren't the case, you might check out the probabilities on your birthday problem. What you've got is effectively a calendar with 100 million days (microseconds in the benchmark's 100 seconds) and 5 people (5 writes to the same record). You've managed to end up with those 5 people sharing a birthday well over 1% of the time.

> I'm just trying to keep folks honest about what their systems actually provide

I appreciate that you've found an interesting corner case that I'd not considered.

Actually, it's not that I hadn't considered it. When creating client side timestamps I do tend to think about this scenario, but with server side timestamps, I tend to think of it much like I think of collisions on Type 1 UUID's, but in truth the probabilities are higher.

I do think Cassandra ought to consider either a) using Type 1 UUID or similar strategies to make the risk of these collisions all but ridiculous or b) when resolving ties in the timestamps on cells by choosing a winning node or thread or something other than the value in the cell, but rather tied to the update operation. That would avoid this scenario in a fashion more fitting with the rest of the semantics of the system.

> give them tools to analyze those constraints

I think unfortunately in this case the analysis of those constraints is flawed.

Re: Why Cassandra Doesn't Need Vector Clocks

#69

Post by cbsmith »

rbranson wrote: post #64
cbsmith wrote: post #63

Earlier quoted context omitted.

You've got a corner case that is way harder to hit than you think you've measured it to be, and the scenarios where it may happen would have almost certainly not have the design required to cause it. Even so, it is addressable. Based on my own experiences with this scenario, I'd be surprised if you managed to experience any problems if you turned off throttling (and didn't force everything to the same timestamp). So…

Finding corner cases is the point of Jepsen :)

> Finding corner cases is the point of Jepsen :)

And with that it obviously did a great job. The probabilities of finding those corner cases is unfortunately completely misrepresented.

I'd worry though that this distortion of the probabilities might mean it also doesn't find other kinds of corner cases.

Post reply on HN