You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@cassandra.apache.org by Timmy Turner <ti...@gmail.com> on 2014/10/16 01:45:40 UTC
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?
RE: Why is Quorum not sufficient for Linearization?
Posted by "Ruebenacker, Oliver A" <Ol...@altisource.com>.
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:doanduyhai@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 <ti...@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?
Posted by DuyHai Doan <do...@gmail.com>.
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 <ti...@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?
>
Re: Why is Quorum not sufficient for Linearization?
Posted by Peter Lin <wo...@gmail.com>.
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 <ti...@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?
>
Re: Why is Quorum not sufficient for Linearization?
Posted by Evan Weaver <ev...@fauna.org>.
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 <do...@gmail.com> 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 <ev...@fauna.org> 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 <ti...@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?
>
>
Re: Why is Quorum not sufficient for Linearization?
Posted by DuyHai Doan <do...@gmail.com>.
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 <ev...@fauna.org> 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 <ti...@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?
>
Re: Why is Quorum not sufficient for Linearization?
Posted by Evan Weaver <ev...@fauna.org>.
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 <ti...@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?