incubator-cassandra-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yang <teddyyyy...@gmail.com>
Subject Re: one way to make counter delete work better
Date Mon, 13 Jun 2011 17:12:15 GMT
I think this approach also works for your scenario:

I thought that the issue is only concerned with merging within the same
leader; but you pointed out
that a similar merging happens between leaders too, now I see that the same
rules on epoch number
also applies to inter-leader data merging, specifically in your case:


everyone starts with epoch of 0, ( they should be same, if not, it also
works, we just consider them to be representing diffferent time snapshots of
the same counter state)

node A      add 1    clock:  0.100  (epoch = 0, clock number = 100)

node A      delete    clock:  0.200

node B     add 2     clock:  0.300

node A    gets B's state:  add 2 clock 0.300, but rejects it because A has
already produced a delete, with epoch of 0, so A considers epoch 0 already
ended, it won't accept any replicated state with epoch < 1.

node B    gets A's delete  0.200,  it zeros its own count of "2", and
updates its future expected epoch to 1.

at this time, the state of system is:
node A     expected epoch =1  [A:nil] [B:nil]
same for node B



let's say we have following further writes:

node B  add 3  clock  1.400

node A adds 4  clock 1.500

node B receives A's add 4,   node B updates its copy of A
node A receives B's add 3,    updates its copy of B


then state is:
node A  , expected epoch == 1    [A:4  clock=400] [B:3   clock=500]
node B same



generally I think it should be complete if we add the following rule for
inter-leader replication:

each leader keeps a var in memory (and also persist to sstable when
flushing)  expected_epoch , initially set to 0

node P does:
on receiving updates from  node Q
        if Q.expected_epoch > P.expected_epoch
              /** an epoch bump inherently means a previous delete, which we
probably missed , so we need to apply the delete
                  a delete is global to all leaders, so apply it on all my
replicas **/
             for all leaders in my vector
                  count = nil

             P.expected_epoch =  Q.expected_epoch
        if Q.expected_epoch == P.expected_epoch
             update P's copy of Q according to standard rules
        /** if Q.expected_epoch < P.expected_epoch  , that means Q is less
up to date than us, just ignore


replicate_on_write(to Q):
      if  P.operation == delete
            P.expected_epoch ++
            set all my copies of all leaders to nil
      send to Q ( P.total , P.expected_epoch)




overall I don't think delete being not commutative is a fundamental blocker
: regular columns are also not commutative, yet we achieve stable result no
matter what order they are applied, because of the ordering rule used in
reconciliation; here we just need to find a similar ordering rule. the epoch
thing could be a step on this direction.


Thanks
Yang




On Mon, Jun 13, 2011 at 9:04 AM, Jonathan Ellis <jbellis@gmail.com> wrote:

> I don't think that's bulletproof either.  For instance, what if the
> two adds go to replica 1 but the delete to replica 2?
>
> Bottom line (and this was discussed on the original
> delete-for-counters ticket,
> https://issues.apache.org/jira/browse/CASSANDRA-2101), counter deletes
> are not fully commutative which makes them fragile.
>
> On Mon, Jun 13, 2011 at 10:54 AM, Yang <teddyyyy123@gmail.com> wrote:
> > as https://issues.apache.org/jira/browse/CASSANDRA-2101
> > indicates, the problem with counter delete is  in scenarios like the
> > following:
> > add 1, clock 100
> > delete , clock 200
> > add  2 , clock 300
> > if the 1st and 3rd operations are merged in SStable compaction, then we
> > have
> > delete  clock 200
> > add 3,  clock 300
> > which shows wrong result.
> >
> > I think a relatively simple extension can be used to complete fix this
> > issue: similar to ZooKeeper, we can prefix an "Epoch" number to the
> clock,
> > so that
> >    1) a delete operation increases future epoch number by 1
> >    2) merging of delta adds can be between only deltas of the same epoch,
> > deltas of older epoch are simply ignored during merging. merged result
> keeps
> > the epoch number of the newest seen.
> > other operations remain the same as current. note that the above 2 rules
> are
> > only concerned with merging within the deltas on the leader, and not
> related
> > to the replicated count, which is a simple final state, and observes the
> > rule of "larger clock trumps". naturally the ordering rule is:
> epoch1.clock1
> >> epoch2.clock2  iff epoch1 > epoch2 || epoch1 == epoch2 && clock1
>
> clock2
> > intuitively "epoch" can be seen as the serial number on a new
> "incarnation"
> > of a counter.
> >
> > code change should be mostly localized to CounterColumn.reconcile(),
> >  although, if an update does not find existing entry in memtable, we need
> to
> > go to sstable to fetch any possible epoch number, so
> > compared to current write path, in the "no replicate-on-write" case, we
> need
> > to add a read to sstable. but in the "replicate-on-write" case, we
> already
> > read that, so it's no extra time cost.  "no replicate-on-write" is not a
> > very useful setup in reality anyway.
> >
> > does this sound a feasible way?   if this works, expiring counter should
> > also naturally work.
> >
> > Thanks
> > Yang
>
>
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com
>

Mime
View raw message