Re: Why is Quorum not sufficient for Linearization?
This is my understanding, others disagree. Sequential consistency: each program's order of reads is preserved Linearizability: each program's order of all reads as well as writes is preserved Assume a single process is making reads and writes to the same partition key, the replication factor is 3, and the process is submitting its own timestamps so there is no clock drift. TS1: Commit value A to R1 and R2: success TS2: Read value from R2 and R3: A TS3: Commit value B to R1 only: E (timeout error) TS4: Read value from R2 and R3: A TS5: Read value from R1 and R2: B The valid linearizations were either A-E-A or A-E-B, not A-E-A-B. There are other linearizability violations without failures, as well as violations of sequential consistency, if multiple clocks are used for writing to the same partition key by different processes or different coordinators. Evan On Sat, Oct 18, 2014 at 9:19 AM, DuyHai Doan wrote: > Hello Evan > > Why, in a scenario of resurrections of unacknowledged writes, don't we get > linearizability ? Can you give more detailed explanation on such scenario ? > > @Oliver: true, the formal definition of linearizability is not related to > isolation. My bad. And for your question "What does Cassandra do in the case > of inconsistent reads? Wait or report failure? I could not find that one in > the docs. ", if you're reading at CL >= QUORUM, Cassandra will repair the > data before sending the good result (good = data with latest timestamp, last > write win rule) to the client. > > Regards > > On Thu, Oct 16, 2014 at 7:16 PM, Evan Weaver wrote: >> >> Quorum reads and writes in Cassandra guarantee sequential consistency. >> The reason this doesn't satisfy linearizability is because >> resurrections of unacknowledged writes can occur. A read of a >> half-committed write will trigger synchronous read repair and the >> order will be stable from that point forward. >> >> Isolation is an unrelated issue. >> >> Evan >> >> On Wed, Oct 15, 2014 at 4:45 PM, Timmy Turner wrote: >> > Cassandra in general can't provide guarantee any ordering of the >> > executed >> > queries, since nodes may fail or rejoin the in arbitrary points in time. >> > >> > But why can't it provide ordering for queries run at at least the quorum >> > level? Given that none of the updates get lost, why would order still an >> > issue? >> > >> > Can you maybe illustrate a scenario which shows how/where the order >> > would >> > get lost if writes and reads always occurred with quorum consistency? > >
Re: Why is Quorum not sufficient for Linearization?
Hello Evan Why, in a scenario of resurrections of unacknowledged writes, don't we get linearizability ? Can you give more detailed explanation on such scenario ? @Oliver: true, the formal definition of linearizability is not related to isolation. My bad. And for your question "What does Cassandra do in the case of inconsistent reads? Wait or report failure? I could not find that one in the docs. ", if you're reading at CL >= QUORUM, Cassandra will repair the data before sending the good result (good = data with latest timestamp, last write win rule) to the client. Regards On Thu, Oct 16, 2014 at 7:16 PM, Evan Weaver wrote: > Quorum reads and writes in Cassandra guarantee sequential consistency. > The reason this doesn't satisfy linearizability is because > resurrections of unacknowledged writes can occur. A read of a > half-committed write will trigger synchronous read repair and the > order will be stable from that point forward. > > Isolation is an unrelated issue. > > Evan > > On Wed, Oct 15, 2014 at 4:45 PM, Timmy Turner wrote: > > Cassandra in general can't provide guarantee any ordering of the executed > > queries, since nodes may fail or rejoin the in arbitrary points in time. > > > > But why can't it provide ordering for queries run at at least the quorum > > level? Given that none of the updates get lost, why would order still an > > issue? > > > > Can you maybe illustrate a scenario which shows how/where the order would > > get lost if writes and reads always occurred with quorum consistency? >
Re: Why is Quorum not sufficient for Linearization?
Quorum reads and writes in Cassandra guarantee sequential consistency. The reason this doesn't satisfy linearizability is because resurrections of unacknowledged writes can occur. A read of a half-committed write will trigger synchronous read repair and the order will be stable from that point forward. Isolation is an unrelated issue. Evan On Wed, Oct 15, 2014 at 4:45 PM, Timmy Turner wrote: > Cassandra in general can't provide guarantee any ordering of the executed > queries, since nodes may fail or rejoin the in arbitrary points in time. > > But why can't it provide ordering for queries run at at least the quorum > level? Given that none of the updates get lost, why would order still an > issue? > > Can you maybe illustrate a scenario which shows how/where the order would > get lost if writes and reads always occurred with quorum consistency?
Re: Why is Quorum not sufficient for Linearization?
To the best of my knowledge, only guaranteed way is with an ACID compliant system. The examples other have already provided should give you a decent idea. If that's not enough, you would need to read papers on CRDT's and how they compare to ACID systems. http://highscalability.com/blog/2010/12/23/paper-crdts-consistency-without-concurrency-control.html http://www.eatcs.org/beatcs/index.php/beatcs/article/viewFile/120/115 It also helps to read up on Paxos. Warning on paxos, it's tough to understand and takes time to really get a solid understanding. There aren't many people that can write a great paxos implementation, but there are guys like Cliff Click that have open sourced their code. http://0xdata.com/personal/2012/04/hack-life-hack-life/ hope that helps peter On Wed, Oct 15, 2014 at 7:45 PM, Timmy Turner wrote: > Cassandra in general can't provide guarantee any ordering of the executed > queries, since nodes may fail or rejoin the in arbitrary points in time. > > But why can't it provide ordering for queries run at at least the quorum > level? Given that none of the updates get lost, why would order still an > issue? > > Can you maybe illustrate a scenario which shows how/where the order would > get lost if writes and reads always occurred with quorum consistency? >
RE: Why is Quorum not sufficient for Linearization?
Hello, The fact that things can always change immediately is not an obstacle to linearizability. The lack of linearizability manifests in inconsistency, i.e. you read from multiple nodes and get different results. What does Cassandra do in the case of inconsistent reads? Wait or report failure? I could not find that one in the docs. Thanks! Best, Oliver From: DuyHai Doan [mailto:doanduy...@gmail.com] Sent: Thursday, October 16, 2014 1:59 AM To: user@cassandra.apache.org Subject: Re: Why is Quorum not sufficient for Linearization? Hello Timmy Even when you write and read using quorum, you still don't have isolation. Example: Client A write "John Doe" to 3 replicas. Since CL = Quorum, the coordinator waits for 2 acks from the replicas before telling client A that the write is successful. Now suppose that between the first ack and second ack, another client B writes "Helen Sue" at quorum. If client A reads the data immediately after the 2nd ack, it would see "Helen Sue" and not "John Doe". Since you don't have isolation, linearization is not possible. The only way to achieve it is to rely on Paxos using lightweight transaction. But even then, you only have linearization on 1 partition only. On Thu, Oct 16, 2014 at 1:45 AM, Timmy Turner mailto:timm.t...@gmail.com>> wrote: Cassandra in general can't provide guarantee any ordering of the executed queries, since nodes may fail or rejoin the in arbitrary points in time. But why can't it provide ordering for queries run at at least the quorum level? Given that none of the updates get lost, why would order still an issue? Can you maybe illustrate a scenario which shows how/where the order would get lost if writes and reads always occurred with quorum consistency? *** This email message and any attachments are intended solely for the use of the addressee. If you are not the intended recipient, you are prohibited from reading, disclosing, reproducing, distributing, disseminating or otherwise using this transmission. If you have received this message in error, please promptly notify the sender by reply email and immediately delete this message from your system. This message and any attachments may contain information that is confidential, privileged or exempt from disclosure. Delivery of this message to any person other than the intended recipient is not intended to waive any right or privilege. Message transmission is not guaranteed to be secure or free of software viruses. ***
Re: Why is Quorum not sufficient for Linearization?
Hello Timmy Even when you write and read using quorum, you still don't have isolation. Example: Client A write "John Doe" to 3 replicas. Since CL = Quorum, the coordinator waits for 2 acks from the replicas before telling client A that the write is successful. Now suppose that between the first ack and second ack, another client B writes "Helen Sue" at quorum. If client A reads the data immediately after the 2nd ack, it would see "Helen Sue" and not "John Doe". Since you don't have isolation, linearization is not possible. The only way to achieve it is to rely on Paxos using lightweight transaction. But even then, you only have linearization on 1 partition only. On Thu, Oct 16, 2014 at 1:45 AM, Timmy Turner wrote: > Cassandra in general can't provide guarantee any ordering of the executed > queries, since nodes may fail or rejoin the in arbitrary points in time. > > But why can't it provide ordering for queries run at at least the quorum > level? Given that none of the updates get lost, why would order still an > issue? > > Can you maybe illustrate a scenario which shows how/where the order would > get lost if writes and reads always occurred with quorum consistency? >
Why is Quorum not sufficient for Linearization?
Cassandra in general can't provide guarantee any ordering of the executed queries, since nodes may fail or rejoin the in arbitrary points in time. But why can't it provide ordering for queries run at at least the quorum level? Given that none of the updates get lost, why would order still an issue? Can you maybe illustrate a scenario which shows how/where the order would get lost if writes and reads always occurred with quorum consistency?
