[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17315894#comment-17315894
]
Vytenis Silgalis commented on CASSANDRA-12126:
--
Just a note that the bug that this fixes usually pops up as the following
timeout for people looking for reasons why SERIAL or LOCAL_SERIAL are seeing
read timeouts >3.11.10. Setting the flag to the opt-out option will `fix` it,
but probably shouldn't be reading at this level if you run into this.
{code:java}
! com.datastax.driver.core.exceptions.ReadTimeoutException: Cassandra timeout
during read query at consistency LOCAL_SERIAL (2 responses were required but
only 0 replica responded)
{code}
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Fix For: 3.0.24, 3.11.10, 4.0, 4.0-beta4
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17241347#comment-17241347 ] Benjamin Lerer commented on CASSANDRA-12126: [~feeblefakie] C can be unreachable for different reasons. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 4.0-beta4, 3.0.24, 3.11.10 > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17241218#comment-17241218 ] Hiroyuki Yamada commented on CASSANDRA-12126: - > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. Sorry, I'm not fully sure about the current implementation and how realistic my proposal is but, can we read all the replicas to do the read recovery in step 3 to solve the issue? It only reads A and B but if we read C as well, we know that the proposal is not accepted by the majority. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 4.0-beta4, 3.0.24, 3.11.10 > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17227449#comment-17227449 ] Benedict Elliott Smith commented on CASSANDRA-12126: Yes, that sounds like a great idea, and I really appreciate you offering to take that to the list. I'll chime in with any necessary details to help inform the decision, but will try not to influence it otherwise. I don't have a strong opinion about which of those four options we select, except that my experiments do suggest (3) is perhaps dangerous for some of our users. It's probably a trade-off that should be made with careful business consideration and experimentation by each end user. As far as delaying 4.0 is concerned, that's probably also a matter of community decision-making. We could quite quickly have a patch, that has been reviewed by multiple committers, posted in fairly short order - perhaps before we exit beta. This work will have had much greater validation than the current implementation, but publishing all of this validation work will take longer - likely also achievable before GA, but we might have to invert our process a little. Perhaps this is acceptable, given the balance of correctness and regression we're considering as an alternative, but given my proximity to the work (and that I also don't have a strong position either way), I would prefer to let others make that call. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 3.0.x, 3.11.x, 4.0-beta > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17227379#comment-17227379 ] Benjamin Lerer commented on CASSANDRA-12126: It seem to me that there are several options here: # Try to use your proposal for 4.0 if the community has the appetite for it. The main issue there is some potential extra delay for 4.0 # Do nothing for 4.0. Meaning do not commit the patch. We have lived a long time with that issue and we can probably wait a bit more for a proper solution. # Commit the patch as such, fixing the correctness but introducting potentially some performance issue until we release a better solution. # Changing the patch to default to the current behavior but allowing people to enable the new one if the correctness is a problem for them. May be we should trigger a discussion on the mailing list and see what is other people opinion. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 3.0.x, 3.11.x, 4.0-beta > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17227354#comment-17227354 ] Benedict Elliott Smith commented on CASSANDRA-12126: To some extent that is all up for debate. My plan so far has been to avoid interfering with 4.0 release, so I have been working towards targeting 4.x. This would also permit time to produce documentation and reach out to the list to begin the slow handshake to see if the project wants the work, and in what manner. However, the main body of work is essentially complete, so it is possible that this could be brought forwards if there were appetite. As to target version, it would be possible to target 3.0+, at least for a portion of the work that would encompass this issue, without a great deal of work. The project's appetite would be the main decider, as it's a significant body of work. The main contribution would be a parallel implementation of the same underlying Paxos algorithm, that is able to run concurrently alongside it (supporting live migration), but with several latency improvements, as well as several fixes to correctness. Alongside this is related work to guarantee linearizability across range movements in the form of modifications to repair, bootstrap, replace etc. Related to this work are several patches to wider Cassandra to support automated verification of its correctness, by permitting deterministic simulation of Cassandra clusters with adversarial ordering of events. We have so far simulated billions of transactions to verify its linearizability. I anticipate that this work will be useful for the project's overall goal of improving quality, but they are themselves quite significant and will require their own discussions around timeline and scope. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 3.0.x, 3.11.x, 4.0-beta > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17226714#comment-17226714
]
Benjamin Lerer commented on CASSANDRA-12126:
{quote}I hope that I will be able to provide the community with an alternative
solution in the near future, without these (and many other existing)
pitfalls.{quote}
[~benedict] Few questions regarding your comment:
* What timeframe do you have in mind?
* Is it a solution only for 4.0 or for all the branches?
* Can we help you with that?
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Fix For: 3.0.x, 3.11.x, 4.0-beta
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17226668#comment-17226668
]
Benedict Elliott Smith commented on CASSANDRA-12126:
So, before we commit this I wanted to share that some internal experimentation
found that this can lead to a significant increase in timeouts, particularly
for read-heavy workloads, that previously would not have competed with each
other. I think committing this to a patch release is honestly problematic, as
it could surprise users with a service outage. At the very least, there should
be HUGE warnings in {{NEWS.txt}}, but honestly I would prefer to have users
opt-in for patch releases.
As much as I agree that it is problematic to provide the wrong semantics, I
think it is also problematic to force a decision between stability and
correctness onto our users without their informed and positive consent.
I hope that I will be able to provide the community with an alternative
solution in the near future, without these (and many other existing) pitfalls.
However I'm not sure how that should affect this decision.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Fix For: 3.0.x, 3.11.x, 4.0-beta
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17226643#comment-17226643 ] Sylvain Lebresne commented on CASSANDRA-12126: -- Thanks for the review. I've rebased the branches, but since the last runs were a while ago, I restarted CI runs. I'll commit if those look clean. ||branch||CI|| |[3.0|https://github.com/pcmanus/cassandra/tree/C-12126-3.0]|[Run #171|https://ci-cassandra.apache.org/job/Cassandra-devbranch/171/]| |[3.11|https://github.com/pcmanus/cassandra/tree/C-12126-3.11]|[Run #172|https://ci-cassandra.apache.org/job/Cassandra-devbranch/172/]| |[4.0|https://github.com/pcmanus/cassandra/tree/C-12126-4.0]|[Run #173|https://ci-cassandra.apache.org/job/Cassandra-devbranch/173/]| > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 3.0.x, 3.11.x, 4.0-beta > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17220716#comment-17220716 ] Benjamin Lerer commented on CASSANDRA-12126: Sorry, for the delay. The patches looks good. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Fix For: 3.0.x, 3.11.x, 4.0-beta > > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17140578#comment-17140578 ] Sylvain Lebresne commented on CASSANDRA-12126: -- Alright, my "tomorrow" is off by 1, but pushed an additional commit to implement the optimization suggested by Benedict above. Restarted CI for good measure. ||branch||CI|| |[3.0|https://github.com/pcmanus/cassandra/tree/C-12126-3.0]|[Run #155|https://ci-cassandra.apache.org/job/Cassandra-devbranch/155/]| |[3.11|https://github.com/pcmanus/cassandra/tree/C-12126-3.11]|[Run #156|https://ci-cassandra.apache.org/job/Cassandra-devbranch/156/]| |[4.0|https://github.com/pcmanus/cassandra/tree/C-12126-4.0]|[Run #157|https://ci-cassandra.apache.org/job/Cassandra-devbranch/157/]| > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138578#comment-17138578 ] Sylvain Lebresne commented on CASSANDRA-12126: -- Ok, I understand what you are suggesting now and I agree this should work as well. And it does is more optimal. I like to think of our algorithm as "pure Paxos instances" separated by the MRC to tell us when we can forget the previous instance and start a new one. Committing empty updates as any other updates still fits that mental model, while your suggestion adds a bit of a special case in that it bends the Paxos rules slightly, allowing to sometime ignore a previously accepted value in a promise (when it's empty). Which is not a criticism, just thinking out loud. It's more performant and this is likely worth the slight special casing since it's not too hard to reason about its correctness. I'll sleep on it and modify to your suggestion tomorrow (which is trivial, just need to massage an appropriate comment to explain it). > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138536#comment-17138536 ] Benedict Elliott Smith commented on CASSANDRA-12126: To say it another way: the only purpose of an empty proposal is to poison earlier proposals, and this can be done just as well without moving the proposal to the MRC column in the table. If we treat it as any other "in progress" proposal for invalidating earlier proposals, then once we reach a quorum we must in future be witnessed alongside any earlier proposals and invalidate them. If we didn't reach a quorum, then it doesn't matter if we are witnessed or not, or if any earlier proposals are invalidated. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138503#comment-17138503
]
Benedict Elliott Smith commented on CASSANDRA-12126:
I'm not proposing we do anything different for your patch, just clarifying that
this isn't strictly necessary - it is quite possible to modify the algorithm to
never commit empty proposals. The problem today is that we:
# "Refresh" a quorum with the MRC if not witnessed by all promisers
# Filter out empty proposals when deciding if we have an in progress proposal
({{mostRecentInProgressCommit}} vs {{mostRecentInProgressCommitWithUpdate}})
If instead we did not refresh empty commits, and we did not filter out empty
proposals when _updating_ {{mostRecentInProgressCommitWithUpdate}} but did not
_complete_ any empty proposals we found then everything would be fine.
{{mostRecentInProgressCommitWithUpdate}} confuses matters because it is poorly
named, and is updated by its naming rather than intent - I think it is _meant_
to be {{mostRecentInProgressProposal}} whereas {{mostRecentInProgressCommit}}
should be e.g. {{mostRecentInProgressPromiseOrProposal}}, and
{{mostRecentInProgressProposal}} would gain empty proposals as well as
non-empty ones, and correctly discount the older in progress proposal that was
invalidated by the newer read that did not witness it.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138473#comment-17138473 ] Sylvain Lebresne commented on CASSANDRA-12126: -- I'll have to apologize, but I don't understand what you are suggesting. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138464#comment-17138464
]
Benedict Elliott Smith commented on CASSANDRA-12126:
The problem here stems only from the overload of
{{mostRecentInProgressCommitWithUpdate}}, which assumes an empty update is for
a higher promise rather than an "incomplete" proposal. If the empty proposal
were to be correctly merged with {{mostRecentInProgressCommitWithUpdate}}, it
would override the early non-empty incomplete proposal.
Which its a long-winded way of saying there's no need to update the paxos state
table with the "committed" status of this empty proposal so long as it remains
in the table _as an accepted proposal_ and so long as this accepted proposal
continues to override earlier in progress proposals.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138455#comment-17138455 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. I'm reasonably sure it cannot be necessary for us to commit an empty proposal, because we do not ever need to witness it. We may have to be precise. We do not need to "apply" an empty commit, since it's a no-op, and the patch actually ensures we don't bother. But "committed" do something else, it update the "mrc" value, and _that_ needs to be done. Otherwise, if we _accept_ an empty proposal, yet does not update the "mrc" value, we will not do progress anymore (well, without additional modification to the algorithm that is). But I could be misunderstanding what you are suggesting here. I'll note though, just in case that help, that the logic I'm calling faulty is not the _commit_ of empty updates (though, as said above, I think it's necessary for the sake of the mrc value), it's the fact the don't replay the _proposal_ of empty updates. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138439#comment-17138439 ] Benedict Elliott Smith commented on CASSANDRA-12126: So, I'm reasonably sure it cannot be necessary for us to commit an empty proposal, because we do not ever need to witness it. Either the proposal was agreed by a quorum (and the proposer can report this) but it has no visible effect on future proposals, and does not need to be witnessed by anybody else, or it was not agreed and it does not need to be either proposed again, committed or witnessed by anybody else. However we have to be consistent about it: we either need to _never_ commit them, or _always_ commit them. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17138370#comment-17138370
]
Sylvain Lebresne commented on CASSANDRA-12126:
--
I noticed that the previous version of the patches wasn't working in all cases
due to an existing quirk of the CAS implementation.
Namely, accepted updates that were empty were not replayed by
{{beginAndRepairPaxos}}. Which is a problem for the new empty commits made
during serial reads/non-applying CAS. I added tests to show that if the commit
messages for those empty commits were lost/delayed, we could still have
linearizability violations.
Now, the logic of not replaying empty updates looks wrong to me. There
shouldn't be anything special about an empty update, and if one is explicitely
accepted by a quorum of nodes, we shouldn't ignore it, or that's a break of the
Paxos algorithm (as kind of can be demonstrated by the tests I added).
To be clear, that logic was added *by me* in CASSANDRA-6012 and that was the
sole purpose of that ticket. Except that I can't make sense of my reasoning
back then, and since I didn't included a test to demonstrate the problem I was
solving back then (which was wrong, mea culpa), I have to assume that I was
just confused (maybe I mixed in my head promised ballots and accepted ones?).
Anyway, I think the fix here is simply to remove that bad logic, which fixes
the issue, and I included an additional commit for that.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17134239#comment-17134239
]
Sylvain Lebresne commented on CASSANDRA-12126:
--
Ok, I've rebased the patch against 4.0 and started CI on it all:
||branch||CI||
|[3.0|https://github.com/pcmanus/cassandra/tree/C-12126-3.0]|[Run
#146|https://ci-cassandra.apache.org/job/Cassandra-devbranch/146/]|
|[3.11|https://github.com/pcmanus/cassandra/tree/C-12126-3.11]|[Run
#147|https://ci-cassandra.apache.org/job/Cassandra-devbranch/147/]|
|[4.0|https://github.com/pcmanus/cassandra/tree/C-12126-4.0]|[Run
#148|https://ci-cassandra.apache.org/job/Cassandra-devbranch/148/]|
I included a commit to add the flag that disables the new empty commit for
SERIAL reads as suggested by [~bdeggleston] earlier. Still slightly on the
fence on the need for such flag, but I call it "unsafe"
({{-Dcassandra.unsafe.disable-serial-reads-linearizability}} to be specific)
and log a warning when used, so I'm at peace with that.
I'll note for future reviewers that while the 3.11 branch is almost a straight
away merge up of 3.0, there is a minor differences on the 4.0 branch, namely:
* the added in-jvm dtests needed a few changes to reflect 4.0 changes. To make
that easier, I squashed 2 of the commits from the 3.0/3.11 branches, which is
why that branch has one less commit.
* There is a few changes related to the translation of
{{WriteTimeoutException}} into {{CasWriteTimeoutException}} (I pushed it down
in some cases). I believe this fixes a minor "bug" where the "contentions"
number we returned with {{CasWriteTimeoutException}} was potentially inaccurate
(namely, if we timed out in {{beginRepairAndPaxos}}, contention leading to that
exception would be ignored)
I'll wait on getting usable CI results to officially mark it 'ready to review',
but it is in spirit if anyone is burning to look at this.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17130517#comment-17130517 ] Benedict Elliott Smith commented on CASSANDRA-12126: > I'd like to move this forward personally. Sure, go for it. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17126937#comment-17126937 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. The test cases I provided demonstrate several consistency violations during range movements. Yes, sorry I hadn't read them before commenting. And I certainly agree those are problematic (I was about to open a ticket so it's tracked, but I'd say CASSANDRA-15745 kind of cover those). bq. There are also (more debatably) issues with TTL on system.paxos Agreed this has always been a weak point. It does feel somewhat separated of other consistency points though, and maybe short term we can just offer a way to override the TTL (with documentation on the tradeoffs involved)? bq. Also, mixing LOCAL_SERIAL and SERIAL is entirely unsafe Yeah. I'm not sure how to fix that one without a breaking API change though (namely, limiting their unrestricted use together). It's not "that" different from the fact we allow unrestricted mixing of serial and non-serial operations. Which is something I don't like and I'm happy to discuss moving forward, but imo post-3.X material in the best of cases. bq. I think it is worth considering if we should instead aggressively try to remedy all of the known issues, have a strong verification push, and then roll out all of the changes at-once - including a fix for this that does not regress performance. It is certainly an option worth bringing, and thank you for that. I'm not sure how to really know what is the best option though, so I can only offer my current opinion. Which is that I feel this issue is a very serious issue. And I don't mean that in a way that diminishes the seriousness of the other problems you mentioned, I mean that in absolute terms (the range movement issues are also fairly bad imo for instance). But leaving less of our known serious unaddressed feels better than not, so I'd personally prefer fixing that issue ASAP. Basically, I'm worried that waiting for a more all-encompassing fix might take us quite some time, with no absolute guarantee that we'll be collectively at ease with pushing that to 3.X. Anyway, I'd like to move this forward personally. How do we decide if we do? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117855#comment-17117855
]
Benedict Elliott Smith commented on CASSANDRA-12126:
The test cases I provided demonstrate several consistency violations during
range movements. I've just thought of another one, and am writing a test case
for it. Perhaps we could claim that range movements are always consistency
violations, but they are particularly keenly felt when you claim a linearisable
history.
There are also (more debatably) issues with TTL on {{system.paxos}},
particularly when mixed with non-global commit; perhaps we could claim this is
the user's problem, but it's not clear why we support global consensus that can
be lost through local commit, and I don't think we communicate clearly the
consistency implications to not call this a bug.
Also, mixing LOCAL_SERIAL and SERIAL is entirely unsafe, and even supporting
them both is arguably a consistency violation without mechanisms to safely
transition from one level to another.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117833#comment-17117833 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. But we do have other serious consistency violations that should also be fixed. Could you expand on that? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117652#comment-17117652 ] Benedict Elliott Smith commented on CASSANDRA-12126: bq. I'm rather cold on that because, tbh. I think non-strict serializability is a theoretical notion that is useless in practice and that it is something we should not offer. And I'd rather avoid one more "feature" for which we spend our time saying "don't use it". Yeah, I'm very sympathetic to this view, and have always assumed linearizability with partitions as the object. I'm just really trying to morally justify providing some time to fix this without any negative repercussions. Either way, we should definitely clarify what we mean by SERIAL in some official project documentation somewhere though. We probably need to do so in terms of strict serializability as opposed to linearizability, so that it can be consistent with a future in which we support multi-partition transactions (which as a project we really need to deliver in the not-too-distant future). bq. non-applying CAS for that FWIW, I think this particular case is a no-brainer; there's no real cost to strengthening the semantics of non-applying CAS IMO, since users should anticipate their CAS operations will ordinarily take this long. Whatever the conclusion of our discussion, I think we should apply a fix at least for the non-applying case immediately, and I do not believe any flag to disable this part of the fix is necessary. Reads are trickier, because the user will see a significant performance penalty on patch version upgrade. I'm sympathetic to the view we should just fix the read part immediately, performance regressions be damned. But we do have other serious consistency violations that should also be fixed. I think it is worth _considering_ if we should instead aggressively try to remedy all of the known issues, have a strong verification push, and then roll out all of the changes at-once - including a fix for this that does not regress performance. It might seem a lot for a patch version, but I'm not sure risk is a concern when we know there are several serious problems today, and have been for years. I'm not going to advocate super strongly for either approach, as I don't think there's a clear answer, I just want to raise the alternative as an option to expressly consider. bq. Awesome, thanks. I'll look at integrating those in the branch if you don't mind. Absolutely, that was my intention. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117628#comment-17117628 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. I'm amenable to such flag Actually, let me rephrase that a bit. I'd *really* prefer not adding such flag. If someone is ok with serializability without linearizability, then they can use QUORUM reads, and given how things are implemented, it provides (non-strict) serializability. Granted, for someone that uses SERIAL today, is ok with the lack of linearizability and can't afford the performance penalty, it'll require a client side change, which this flag would avoid, so there is not zero value to such flag. But I suspect user fitting that category (knowingly ok with lack of linearizability) is really really small, and we always have to make trade-offs. So in that case I feel adding one more flag, one I consider dangerous, is not worth it. So to clarify, if a consensus appears for such flag, so be it, I'll add it, but I'm personally not neutral either. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117615#comment-17117615
]
Sylvain Lebresne commented on CASSANDRA-12126:
--
{quote}I think we should include a flag to disable the fix
{quote}
The option of having a flag occurred to me, but I rejected it initially because
I continue to believe the current behavior is wrong (a moral judgment, I guess)
and in principle, having a "please, make my database broken" flag does not feel
like a good idea.
But I reckon that it _may_ exists advanced users that did noticed the lack of
linearizability for reads and effectively built around it knowingly, for which
the performance impact may be considered a regression with no upside (but if
you sense skepticism on my part when reading that sentence, you're radar is not
completely off).
And as we're talking minor upgrade here, I'm amenable to such flag, though I'd
prefer making it clear somehow that it is unsafe/risky and something we may
remove in the future with no particular warning.
{quote}It would be good to have a test for that as well.
{quote}
Certainly, good point, I can add the 2 missing interleaving.
{quote}do we actually claim our consistency properties are for SERIAL?
{quote}
While our official doc on the matter is certainly lacking (not spelling much
guarantee at all afaict, and I'm happy to piggy-back on this ticket to correct
that), we've always implied linearizability. I have, at least, and I'm sure I
can dig up other doing it as well on the mailing list if necessary. We did this
both by throwing the linearizable word out from time to time, but also by
repeatedly recommending that when a write times out, one needs to issue a
SERIAL read to 'observe' if that write went through or not (and as an aside, if
you can't rely on either reads or non-applying CAS for that, I'm not even sure
how to use LWTs, except maybe for excessively specific cases).
{quote}perhaps we should instead introduce a new STRICT_SERIAL consistency level
{quote}
I'm rather cold on that because, tbh. I think non-strict serializability is a
theoretical notion that is useless in practice and that it is something we
should not offer. And I'd rather avoid one more "feature" for which we spend
our time saying "don't use it".
{quote}I've pushed various test cases
{quote}
Awesome, thanks. I'll look at integrating those in the branch if you don't mind.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117597#comment-17117597
]
Benedict Elliott Smith commented on CASSANDRA-12126:
I've pushed various test cases
[here|https://github.com/belliottsmith/cassandra/tree/12126-tests-3.0] - most
of them marked {{@Ignore}} because they are known to fail, and won't be
resolved immediately.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117172#comment-17117172 ] Benedict Elliott Smith commented on CASSANDRA-12126: So, a thought has occurred to me: what do we actually claim our consistency properties are for SERIAL? My understanding was that we claimed only serializability, in which case I don't think that strictly speaking this is a bug. I think it's only a bug if we claim strict serializability. However the only docs I can find claiming either are DataStax's which mixes linearizable up with serializable. FWIW, I consider this to be a bug, as we should at least support the more intuitively correct semantics. But perhaps we should instead introduce a new STRICT_SERIAL consistency level to solve it, and clarify what SERIAL means in our docs? I would also be OK with simply claiming strict serializability for SERIAL. But perhaps this technicality/ambiguity buys us some time and cover to solve the problem without introducing major performance penalties? I also have some relevant test cases I will share tomorrow, along with test cases for other correctness failures of LWTs. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17117143#comment-17117143 ] Blake Eggleston commented on CASSANDRA-12126: - Agreed that's the most straightforward way to address both issues (although I've only skimmed your patch). In 3.x though, and at least for the serial read fix, I think we should include a flag to disable the fix, in case a) there's a problem with the fix or b) operators would rather trade the performance impact for linearizability for whatever reason. There's also a variant of the non-applying update issue where it's exposed by a read, not another insert. It would be good to have a test for that as well. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Assignee: Sylvain Lebresne >Priority: Normal > Labels: LWT, pull-request-available > Time Spent: 10m > Remaining Estimate: 0h > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17116578#comment-17116578
]
Sylvain Lebresne commented on CASSANDRA-12126:
--
It definitively doesn't look good that this messages comes so late, but I feel
this is a serious issue of the {{SERIAL}}/{{LOCAL_SERIAL}} consistency levels
since this breaks the basic guarantee they exist to provide, and as such should
be fixed all the way down 3.0, and the sooner, the better.
In an attempt to sum this up quickly, the problem we have here affects both
serial reads _and_ LWT updates that do not apply (whose condition evaluates to
{{false}}). In both case, while the current code replays "effectively
committed" proposals (those whose proposal has been accepted by majority of
replica) with {{beginAndRepairPaxos}}, neither make proposals of their own, so
nothing will prevent a proposal accepted by a minority of replica (say just
one) to be later replayed (and thus committed).
I've pushed [2 in-jvm
dtests|https://github.com/pcmanus/cassandra/commit/3442277905362b38e0d6a2b8170916fcfd18d469]
that demonstrate the issue for both cases (again, serial reads and
non-applying updates). They use "filters" to selectively drop messages to make
failure consistent but aren't otherwise very involved.
As [~kohlisankalp] mentioned initially, the "simplest"\[1\] way to fix this
that I see is to commit an empty update in both cases. Actually committing,
which sets the {{mostRecentCommit}} value in the Paxos state, ensures that no
prior proposal can ever be replayed. I've pushed a patch to do so on 3.0/3.11
below (will merge up on 4.0, but wanted to make sure we're ok on the approach
first):
||version||
| [3.0|https://github.com/pcmanus/cassandra/commits/C-12126-3.0] |
| [3.11|https://github.com/pcmanus/cassandra/commits/C-12126-3.11] |
The big downside of this patch however is the performance impact. Currently, a
{{SERIAL}} read (that finds nothing in progress it needs to replay) is 2
round-trips (a prepare phase, followed by the actual read). With this patch, it
is 3 round-trips as we have to propose our empty commit and get acceptance (we
don't really have to wait for responses on the commit though), which will be
noticeable for performance sensitive use-cases. Similarly, the performance of
LWT that don't apply will be impacted.
That said, I don't seen another approach to fixing this that would be as
acceptable for 3.0/3.11 in terms of risks, and imo 'slower but correct' beats
'faster but broken' any day, so I'm in favor of moving forward with this fix.
Opinions?
\[1\]: I mean by that both the simplicity of the change, but also of validating
that this fix the problem at hand without creating new correctness problems.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Feature/Lightweight Transactions, Legacy/Coordination
>Reporter: Sankalp Kohli
>Assignee: Sylvain Lebresne
>Priority: Normal
> Labels: LWT, pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16964198#comment-16964198 ] Benedict Elliott Smith commented on CASSANDRA-12126: It looks like I never noted that IMO the real problem is that we do not serialize the evaluation of a condition if the condition is not met, so other commands are also not serialized wrt the evaluation of such conditions either. The evaluation of a condition should always be a serialized wrt other events, so we should be agreeing on the conditional operation, and then performing it, not evaluating the condition and then serializing the choice of a new value. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Feature/Lightweight Transactions, Legacy/Coordination >Reporter: Sankalp Kohli >Priority: Normal > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16726929#comment-16726929 ] Ariel Weisberg commented on CASSANDRA-12126: Having reviewed the code I think what Benedict says is correct. The criteria we use for identifying if there is an progress paxos round that needs resolution is incorrect because it assumes we have visibility to all accepted ballots when we only have visibility to a majority. I think this optimization can be done correctly, but it's a bit of surgery. Right now reads do a prepare and modify the promised ballot at each acceptor. If instead we only read the promised ballot from each acceptor then we could check the promised ballot matches the most recent committed ballot. If those are the same we know nothing is in progress because a higher ballot than the most recent accepted/committed ballot has not been promised by a majority which means there can be no lingering accepted ballot since a majority of promises must be collected first. If that isn't the case then we can go ahead and do a prepare + propose to make them match and subsequent reads won't have to do a propose. This may also impact our choice of how many replicas to contact in each phase since we want them to have consistent paxos state so reads can be one roundtrip. I am not sure if we contact them all (like with mutations) or just a majority. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16631226#comment-16631226 ] Benedict commented on CASSANDRA-12126: -- bq. We read nothing in node Y, yet node Z read something in the next request. I think the problem here is that, at the API level, there isn't enough information to say that X didn't simply 'occur' *after* both Y and Z. That is, unless the rejection of Y occurs after X's timeout. In this case, it would seem to be an API-visible error, as at the point of timeout the indeterminacy should be fixed. Timeouts should not ‘live forever’ as the bogeyman, ready to mess with history. I think, though, that the suggested mechanism could result in this. Take three nodes (RF=3) A, B and C; and any three CAS operations X, Y and Z such that: * X and Y can always succeed * Z can only succeed if X has succeeded Setup: # Prepare _and_ Propose X with ballot 1; proposal accepted only by A #* this will be the last and only node’s proposal acceptance # Prepare Y with ballot 2; reach B and C before ballot 1, so they do not accept # Now, lock X and Y in battle, always failing to proceed to the propose step before the other reaches the prepare step again # X and Y both timeout having failed to cleanly apply Part 2: # Z is now attempted; it prepares to only B and C, seeing no in-progress proposal # As a result, it does not see X; it is rejected, so there is no new proposal/commit # Read at SERIAL is performed; this time, A is consulted # Suddenly, a wild X appears. From nowhere. It does seem, in essence, to be an incidence of the bug (or a very similar one) described in the ticket. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16630850#comment-16630850
]
Jeffrey F. Lukman commented on CASSANDRA-12126:
---
Thank you for your responses, [~jjordan] and [~kohlisankalp].
I think you have cleared up some misunderstandings for me (and our team) where
timeout is a "gray area" for the client
to determine whether a request has been successfully processed.
One thing that we would like to point out maybe, based on the early discussion
in this bug description, quote
{quote}However we need to fix step 2, since it caused reads to not be
linearizable with respect to writes and other reads. In this case, we know that
majority of acceptors have no inflight commit which means we have majority that
nothing was accepted by majority. I think we should run a propose step here
with empty commit and that will cause write written in step 1 to not be visible
ever after.
{quote}
What we tried to mimic with our model checker in the beginning actually was
this scenario where node Y saw that the majority of nodes do not have
inProgress value, but then suddenly node Z saw that there is an inProgress
value from node X and tried to repair and commit it.
So, we confirm that we can also see this behavior:
{quote}2: Read -> Nothing
3: Read -> Something
{quote}
We read nothing in node Y, yet node Z read something in the next request.
To sum up, at least, our scenario explains this behavior: Node Y does not try
to repair the Paxos because node X's prepare response comes last, therefore
node Y ignores the node X's prepare response and based its decision to not
repair the Paxos.
But in node Z's client request, node Z decides to repair the Paxos based on
node X's existing inProgress value_1="A" because node X's prepare response
comes early (1st or 2nd). Which cause an inconsistent reaction in some way
between node Y and node Z (although this is correct based on the original Paxos
algorithm).
A solution to avoid this inconsistent reactions from these two nodes maybe is
for each node to decide whether to repair a Paxos or not based on the complete
view of the alive nodes, therefore if the response X's comes last with an
inProgress value, node Y will still repair the Paxos.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Coordination
>Reporter: sankalp kohli
>Priority: Major
> Labels: LWT
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16630772#comment-16630772 ] sankalp kohli commented on CASSANDRA-12126: --- I agree with [~jjordan] that this is a correct response. Also in the future please open a new Jira if it is a different issue. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16630700#comment-16630700
]
Jeremiah Jordan commented on CASSANDRA-12126:
-
bq. client request-1: Timed out, client request-2: Rejected, client request-3:
Timed out
Given those responses to the queries. The client side does not know the state
of the system without issuing a READ at SERIAL (or doing another INSERT that
gets a success).
bq. There we get an inconsistency between the client side and the server side,
where all requests actually failed, but when we read the end result again from
all nodes, we get value_1='A', value_2=null, value_3=null.
Given the responses you got, there is no inconsistency. The client received
"timed out" exceptions. A timed out exception means "your query may or may not
have been applied, the server doesn't know, you should retry it if you want to
ensure it goes through". In this case request-1 was successful, and request-3
failed. So {value_1='A', value_2=null, value_3=null} is a valid state and not
inconsistent.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Coordination
>Reporter: sankalp kohli
>Priority: Major
> Labels: LWT
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16630688#comment-16630688
]
Jeffrey F. Lukman commented on CASSANDRA-12126:
---
During our testing with our model checker, we limit the round of Paxos for each
query,
because if not, it is possible that we get stuck in a very long sequence of
message transactions among the nodes without progressing anywhere. So, what we
do is we only execute one round of Paxos for each query.
To enlight our test and combine our whole story, here is what happened in
detail:
* We first prepared the 3 node-cluster with the test.tests table as initial
table structure and yes, the initial table began with:
{name:'testing', owner:'user_1', value1:null, value2:null, value3:null}
* Next, we run the model checker that will start the 3 node-cluster.
* Inject the 3 client requests in order: query 1, then query 2, then query 3.
This cause query 1 to have ballot number < query 2 ballot number < query 3
ballot number.
* Now this means, in the beginning, the model checker already see there will
be 9 prepare messages in its queue that will be reordered in some way.
* When the bug is manifested, we ended up having:
** Node X's prepare messages proceed and all nodes response with true back to
node X.
** Node X sends its propose message with value_1='A' to itself first and get a
response true as well.
** At this moment, Node X inProgress value is updated to the proposed value,
value_1='A'
** But then node Y prepare messages proceed and all nodes response with true
back to node Y,
because prepare messages of node Y have a higher ballot number.
** But when node Y about to proceed the propose messages it realized that the
current data does not fulfill the IF condition, so it does not proceed to
propose messages. --> Client request 2 to node Y is therefore rejected
** Continuing node X propose messages to node Y and Z, both requests are
returned with false to node X
** Now at this point node X should be able to retry the Paxos with a higher
ballot number, but since we limit the round of Paxos for each query to one,
therefore client request 1 to node X is timed out.
** Lastly, node Z sends its prepare messages to all nodes, and get response
true messages from all nodes,
because the ballot number is higher as well.
** At this point, if the node X response message is returned first to node X,
what will happen is node Z will realize that node X still has an inProgress
value in the process (value_1='A'). This cause node Z to send propose messages
and commit messages but for client request 1 using the current highest ballot
number.
Here we have our first data update saved: value_1='A', value_2=null,
value_3=null.
** Back to our constraint of one round Paxos for each query, we ended up not
retrying client request-3 because we reached timeout.
* To sum up:
** client request-1: Timed out
** client request-2: Rejected
** client request-3: Timed out
There we get an inconsistency between the client side and the server side,
where all requests actually failed, but when we read the end result again from
all nodes, we get value_1='A', value_2=null, value_3=null.
I made a wrong statement at the end of my first comment:
{quote}9. Therefore, we ended up having client request 1 stored to the server,
although client request-3 was the one that is said successful.
{quote}
It should be failed due to timeout.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Coordination
>Reporter: sankalp kohli
>Priority: Major
> Labels: LWT
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16629950#comment-16629950
]
Benedict commented on CASSANDRA-12126:
--
I'm not sure if I'm following, but it seems the bug report is suggesting that
operation #3 is returned to the client as successful, but #1's state is the
only state visible. However, if #1 was successful and the state of the cluster
prior to #3 succeeding, then #3 should have also modified the cluster state
since its IF statement should have evaluated to true.
As with CASSANDRA-12438, the read queries you are performing, to which nodes,
at what point and with what consistency levels would be helpful to know. Also,
can we assume that the state of the table began with \\{name:'testing',
owner:'user_1', value1:null, value2:null, value3:null}\?
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Coordination
>Reporter: sankalp kohli
>Priority: Major
> Labels: LWT
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16629689#comment-16629689 ] sankalp kohli commented on CASSANDRA-12126: --- Why is end result not correct? second and third operation did not succeed because first 1 did not finish? Can you combine the example with the earlier comment please > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[
https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16629685#comment-16629685
]
Jeffrey F. Lukman commented on CASSANDRA-12126:
---
To complete our scenario, here is the setup for our Cassandra:
We run the scenario with Cassandra-v2.0.15.
Here is the scheme that we use:
*
CREATE KEYSPACE test WITH REPLICATION = \{'class': 'SimpleStrategy',
'replication_factor': 3};
*
CREATE TABLE tests ( name text PRIMARY KEY, owner text, value_1 text, value_2
text, value_3 text);
Here are the queries that we submit:
* client request to node X (1st): UPDATE test.tests SET value_1 = 'A' WHERE
name = 'testing' IF owner = 'user_1';
* client request to node Y (2nd): UPDATE test.tests SET value_2 = 'B' WHERE
name = 'testing' IF value_1 = 'A';
* client request to node Z (3rd): UPDATE test.tests SET value_3 = 'C' WHERE
name = 'testing' IF value_1 = 'A';
To confirm, when the bug is manifested, the end result will be: value_1='A',
value_2=null, value_3=null
[~jjirsa], regarding our tool, at this point, it is not open for public.
> CAS Reads Inconsistencies
> --
>
> Key: CASSANDRA-12126
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12126
> Project: Cassandra
> Issue Type: Bug
> Components: Coordination
>Reporter: sankalp kohli
>Priority: Major
> Labels: LWT
>
> While looking at the CAS code in Cassandra, I found a potential issue with
> CAS Reads. Here is how it can happen with RF=3
> 1) You issue a CAS Write and it fails in the propose phase. A machine replies
> true to a propose and saves the commit in accepted filed. The other two
> machines B and C does not get to the accept phase.
> Current state is that machine A has this commit in paxos table as accepted
> but not committed and B and C does not.
> 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the
> value written in step 1. This step is as if nothing is inflight.
> 3) Issue another CAS Read and it goes to A and B. Now we will discover that
> there is something inflight from A and will propose and commit it with the
> current ballot. Now we can read the value written in step 1 as part of this
> CAS read.
> If we skip step 3 and instead run step 4, we will never learn about value
> written in step 1.
> 4. Issue a CAS Write and it involves only B and C. This will succeed and
> commit a different value than step 1. Step 1 value will never be seen again
> and was never seen before.
> If you read the Lamport “paxos made simple” paper and read section 2.3. It
> talks about this issue which is how learners can find out if majority of the
> acceptors have accepted the proposal.
> In step 3, it is correct that we propose the value again since we dont know
> if it was accepted by majority of acceptors. When we ask majority of
> acceptors, and more than one acceptors but not majority has something in
> flight, we have no way of knowing if it is accepted by majority of acceptors.
> So this behavior is correct.
> However we need to fix step 2, since it caused reads to not be linearizable
> with respect to writes and other reads. In this case, we know that majority
> of acceptors have no inflight commit which means we have majority that
> nothing was accepted by majority. I think we should run a propose step here
> with empty commit and that will cause write written in step 1 to not be
> visible ever after.
> With this fix, we will either see data written in step 1 on next serial read
> or will never see it which is what we want.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16629542#comment-16629542 ] Jeff Jirsa commented on CASSANDRA-12126: [~jeffreyflukman] thanks for this report. Suspect that most of the folks who are interested in this are already cc'd and received an email notification of your response, but explicitly tagging [~benedict] [~iamaleksey] and [~bdeggleston] as people who aren't yet watching it but may be interested. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16629455#comment-16629455 ] Jeffrey F. Lukman commented on CASSANDRA-12126: --- Hi all, Our team from UCARE University of Chicago, have been able to reproduce similar manifestation to this bug consistently with our model checker. (Our scenario is different with what [~kohlisankalp] proposed) Here are the workload and scenario of the bug: Workload: 3 nodes-cluster, 3 client requests (but no crash event) Scenario: # Start 3-nodes cluster and inject all of 3 client requests to 3 different nodes (node X, Y, Z) # Node X sends its prepare messages (ballot number=1) to all nodes and all nodes accept it # Node X sends its propose message to itself, causing its inProgress value to be "X". # Node Y sends its prepare messages (ballot number=2) to all nodes. This also causes the rest of node X propose messages to be invalid because its ballot number is smaller than node Y prepare messages. # In our scenario, the prepare response messages from node Y and Z comes first before prepare response message from node X, causing the node Y to unrecognize the state of node X which already accepted value "X" (step 3). # But since our query of client request 2 has an IF, that said IF value_1='X', therefore node Y will not continue on sending propose messages to all nodes. Up to this point, it means none of the queries are committed to the server. # Node Z now sends its prepare messages to all nodes and all nodes accept it. # In our scenario, now the node X returns its response first where it also let node Z knows about its inProgress Value "X". >From here, node Z will propose and commit client request-1 (with value "X") >instead of client-request-3. # Therefore, we ended up having client request 1 stored to the server, although client request-3 was the one that is said successful. We are ready to assist, if any further information is needed. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Priority: Major > Labels: LWT > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v7.6.3#76005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15974873#comment-15974873 ] Sylvain Lebresne commented on CASSANDRA-12126: -- Exactly. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15974834#comment-15974834 ] Jonathan Ellis commented on CASSANDRA-12126: I see. So you are saying that 1: Write 2: Read -> Nothing 3: Read -> Something Is broken because to go from Nothing to Something there needs to be a write in between. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15974342#comment-15974342 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. What is the distinction you are proposing? Not sure, I think we don't put the same definitions on operation visibility. What I'm saying is that "if an operation has a visible outcome, then that outcome should be visible (by serial operations) by any subsequent operation (so as soon as the operation returns to the client if you will)". In particular, if a serial read follows a serial write (meaning that it's started after the write returned, even with a timeout), then if the write has any effect, the read should see it. Note that when you get a timeout on the initial write, you don't know if the write has been applied or not, but the whole point of a serial read is to be able to unequivocally decide what was that outcome. If we can't guarantee that, if there is no way to observe if a timed-out write has been applied or not, then I'm not sure how one would use LWT in the first place. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15973117#comment-15973117 ] Jonathan Ellis commented on CASSANDRA-12126: I'm confused, because it sounds like you're saying "all operations should be visible once finished." Of course that's not actually what you mean that would require participation from all replicas to finish in-flight requests and not just a majority. What is the distinction you are proposing? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972899#comment-15972899 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. I am saying that we actually also satisfy (1) because the write is not complete until Sankalp's step 3. Your definition of "completion" doesn't work logically. You're suggesting (1) only complete when it is visible (in (3)), but linearizabilty is about when operations that complete are visible, so if you define completion as "when it's visible", you're in for trouble. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972890#comment-15972890 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. But we stipulated that 1 times out and did not complete. It completed in the sense that the operation is finished and returned to the client (albeit with a timeout). Don't get me wrong, theory is blind, so if you want to define than an operation completes only if it "finished and did not timeout" and define linearizability only in term of completing operation (with that definition of completion), then sure, I agree this particular definition of linearizability is not broken by the description of this ticket. But how useful is a definition of linearizability that says nothing about operations that timeouts (especially keeping in mind that our implementation is particularly prone to timeouts)? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972886#comment-15972886 ] Jonathan Ellis commented on CASSANDRA-12126: Bailis: # once a write completes, all later reads (where “later” is defined by wall-clock start time) should return the value of that write or the value of a later write. # Once a read returns a particular value, all later reads should return that value or the value of a later write. I think we all agree that our current behavior satisfies (2). I am saying that we actually also satisfy (1) because the write is not complete until Sankalp's step 3. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972883#comment-15972883 ] Jonathan Ellis commented on CASSANDRA-12126: But we stipulated that 1 times out and did not complete. (If it did complete it would be guaranteed to be visible by any majority of course.) > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972861#comment-15972861 ] Sylvain Lebresne commented on CASSANDRA-12126: -- bq. 1 -> 2 -> 3. The value V from 1 is not seen in 2, but once it is seen in 3 it is always seen. As 1 "completes" before 2, it's result should be visible by 2 (or not ever) for linearizability (taken in the sense discussed here for instance: http://www.bailis.org/blog/linearizability-versus-serializability/). More pragmatically, outside of any theoretical definition, if serial read can't guarantee they will see any previous operation (even failed one, as long as they returned to the client), then they are not very useful in the first place. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15972815#comment-15972815 ] Jonathan Ellis commented on CASSANDRA-12126: I see you outlining two series of steps: 1 -> 2 -> 3. The value V from 1 is not seen in 2, but once it is seen in 3 it is always seen. 1 -> 2 -> 4. V is never seen. It seems to me that both of these maintain linearizability. What am I missing? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug > Components: Coordination >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15960582#comment-15960582 ] Stefan Podkowinski commented on CASSANDRA-12126: I've now revisited this issue again and took a closer look at the work I've done back then months ago (after rebasing on trunk). The patch follows the suggested solution by [~kohlisankalp] by using an empty commit as additional propose step. It also implements an optimization to avoid this step in case no paxos rounds for writing new values have been conducted between serial reads. * [CASSANDRA-12126-trunk|https://github.com/spodkowinski/cassandra/tree/CASSANDRA-12126-trunk] * [CircleCI results|https://circleci.com/gh/spodkowinski/cassandra/5] Except the actual fix, there's also a lot of tests included, which I'd hate to throw away, as we're clearly lacking tests for CAS operations. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli >Assignee: Stefan Podkowinski > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15372670#comment-15372670 ] Stefan Podkowinski commented on CASSANDRA-12126: Another take on how to test coordination aspects for this ticket would be to make use of the MessagingService mocking classes implemented in CASSANDRA-12016. I've created a couple of tests [here|https://github.com/spodkowinski/cassandra/tree/WIP-12126/test/unit/org/apache/cassandra/service/paxos] to get a better idea how this would look like. Although limited to observing the behavior of a single node/state machine, it's probably more lightweight and easier to implement than doing the same using dtests or Jepsen. As of the described edge case, I'd agree with [~kohlisankalp]'s suggestion (if I understood correctly) to do an additional proposal round. However, it would be nice to optimize this a bit so we don't trigger new proposals for each and every SERIAL read. I did a first implementation for this [here|https://github.com/spodkowinski/cassandra/commit/96ec151992f49c773e5af5d85ce69ec87d8b7bc5] (with [CASReadTriggerEmptyProposal|https://github.com/spodkowinski/cassandra/blob/WIP-12126/test/unit/org/apache/cassandra/service/paxos/CASReadTriggerEmptyProposal.java] as corresponding test) for the sake of discussion. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15362888#comment-15362888 ] sankalp kohli commented on CASSANDRA-12126: --- I was able to repro it in a not so good way :) Here are the steps 1. Create a 3 node C* cluster(A,B and C) 2. Create a keyspace with RF=3 and a simple table 3. Insert System.exit PaxosState.propose method to simulate a failure in A and B. 4. Do a CAS Write. Now with this, only C will be able to store the propose and not A and B. 4. Now bring down machine C and remove the System.exit from A and B and bring them up again. 5. Do a CAS Read and this will involve only A and B and will not return the data. 6. Bring down A and bring up C. 7. Do a CAS Read and you will be able to read the data. If we can use some test framework to simulate such failures then that will be better. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15362602#comment-15362602 ] Joel Knighton commented on CASSANDRA-12126: --- Sure - I have Jepsen tests for LWT and a few other similar tests I've been building. I haven't seen an issue like this reproduced through them so far, but I'll try and see if I can reproduce this reliably. It certainly seems feasible to hit. I definitely think it is a good idea to run any proposed patch through LWT tests for a while. > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15362279#comment-15362279 ] Sylvain Lebresne commented on CASSANDRA-12126: -- I "think" you are right that this can happen, and that committing an empty commit on SERIAL reads "should" fix it. Paxos is however subtle enough that I would feel more confident with this if we had a reproduction test first, if only so we can validate whatever patch we come up with. [~jkni] I believe you've spend some time on jespen-like tests for paxos, do you think this is something we could use to try to reproduce something like that relatively consistently? > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-12126) CAS Reads Inconsistencies
[ https://issues.apache.org/jira/browse/CASSANDRA-12126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15359380#comment-15359380 ] sankalp kohli commented on CASSANDRA-12126: --- cc [~slebresne] and [~jbellis] > CAS Reads Inconsistencies > -- > > Key: CASSANDRA-12126 > URL: https://issues.apache.org/jira/browse/CASSANDRA-12126 > Project: Cassandra > Issue Type: Bug >Reporter: sankalp kohli > > While looking at the CAS code in Cassandra, I found a potential issue with > CAS Reads. Here is how it can happen with RF=3 > 1) You issue a CAS Write and it fails in the propose phase. A machine replies > true to a propose and saves the commit in accepted filed. The other two > machines B and C does not get to the accept phase. > Current state is that machine A has this commit in paxos table as accepted > but not committed and B and C does not. > 2) Issue a CAS Read and it goes to only B and C. You wont be able to read the > value written in step 1. This step is as if nothing is inflight. > 3) Issue another CAS Read and it goes to A and B. Now we will discover that > there is something inflight from A and will propose and commit it with the > current ballot. Now we can read the value written in step 1 as part of this > CAS read. > If we skip step 3 and instead run step 4, we will never learn about value > written in step 1. > 4. Issue a CAS Write and it involves only B and C. This will succeed and > commit a different value than step 1. Step 1 value will never be seen again > and was never seen before. > If you read the Lamport “paxos made simple” paper and read section 2.3. It > talks about this issue which is how learners can find out if majority of the > acceptors have accepted the proposal. > In step 3, it is correct that we propose the value again since we dont know > if it was accepted by majority of acceptors. When we ask majority of > acceptors, and more than one acceptors but not majority has something in > flight, we have no way of knowing if it is accepted by majority of acceptors. > So this behavior is correct. > However we need to fix step 2, since it caused reads to not be linearizable > with respect to writes and other reads. In this case, we know that majority > of acceptors have no inflight commit which means we have majority that > nothing was accepted by majority. I think we should run a propose step here > with empty commit and that will cause write written in step 1 to not be > visible ever after. > With this fix, we will either see data written in step 1 on next serial read > or will never see it which is what we want. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
