[
https://issues.apache.org/jira/browse/CASSANDRA-5062?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13591778#comment-13591778
]
Cristian Opris commented on CASSANDRA-5062:
-------------------------------------------
Jonathan, even if you could rely on monotonically increasing timestamps (which
is a big assumption), I don't think this will work because it does not clearly
demarcate between paxos rounds.
So you could have a scenario where you end up with different values committed
at each replica:
{code}
R1 R2 R3
1. C0 C0 C0 //initial state ts=0
2. P1 < P1< //R3 initiates proposal ts=1
3. A1 < A1< //accept ts=1
4. C1 //R2 has majority, commits ts=1
5. >P2 >P2 //R1 initiates proposal ts=2
6. >A2 >A2 //accept ts=2; note this breaks Paxos since R1
should have chosen A1
7. C2 //R1 commits C2
{code}
After step 7, R1=C2, R2=C0, R3=C1
If a read comes in at this point, what would it resolve to ? You could say "use
the highest timestamp" but that would require a read ALL
More importantly, if a CAS request comes in, the validation of that depends on
which replica it executes (unless again we do a read ALL before)
The reason I suggested version counters is because this allows a replica to
detect
it has missed paxos rounds and needs to sync up before proceeding.
The example above modified:
{code}
R1 R2 R3
1. C0 C0 C0 //initial state v=0
2. P1 < P1< //R3 initiates proposal v=1
3. A1 < A1< //accept ts=1
4. C1 //R2 has majority, commits ts=1
5a. >P1' //R1 wants to initiate its own P1
5b. << nack P1' //but rejected since already committed
5c. << read C1 //read and commit C1 (finish round 1)
5d. >P2 //restarts proposal with v=2
5e. >P2 & C1 //R2 receives P2 and notices it's missing C1
which it needs to commit first
6. >A2 >A2 //accept v=2; this is ok for Paxos as it's truly
a new round
7. C2 //R1 commits C2
{code}
After step 7
R1=(C2,A2) R2=(C1,A2) R3=(C1,A1)
The most ambiguous quorum is R2,R3. Let's even assume that R1 has failed.
The ambiguity can still be solved by initiating a new paxos round at version
v=2 which will necessarily accept and commit A2. (this follows from Paxos)
So to have a consistent read, the read might perform a paxos round to commit A2.
This is a sketch of a proof this is correct:
- if no replica can participate in a paxos round for version V, as acceptor or
proposer, until it learns and commits locally the previous version V-1
- then for Paxos to achieve a quorum of accept at V, a quorum of replicas must
have committed V-1
- once a quorum has accepted the same value for V, all replicas can eventually
learn and commit V by simply rerunning a paxos round at V with value Nil (this
can be triggered by an attempt to write V+1, or a read as shown above)
> Support CAS
> -----------
>
> Key: CASSANDRA-5062
> URL: https://issues.apache.org/jira/browse/CASSANDRA-5062
> Project: Cassandra
> Issue Type: New Feature
> Components: API, Core
> Reporter: Jonathan Ellis
> Fix For: 2.0
>
> Attachments: half-baked commit 1.jpg, half-baked commit 2.jpg,
> half-baked commit 3.jpg
>
>
> "Strong" consistency is not enough to prevent race conditions. The classic
> example is user account creation: we want to ensure usernames are unique, so
> we only want to signal account creation success if nobody else has created
> the account yet. But naive read-then-write allows clients to race and both
> think they have a green light to create.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
