cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Kelvin Kakugawa (JIRA)" <j...@apache.org>
Subject [jira] Issue Comment Edited: (CASSANDRA-580) vector clock support
Date Wed, 23 Dec 2009 05:55:29 GMT

    [ https://issues.apache.org/jira/browse/CASSANDRA-580?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12793938#action_12793938
] 

Kelvin Kakugawa edited comment on CASSANDRA-580 at 12/23/09 5:55 AM:
---------------------------------------------------------------------

The patch adds a new package:
db/context

which contains:
IContext
VersionVectorContext

IContext is just a general interface to manipulate context byte[].  Basically, create(), update()
and reconcile().

create(): create a new/empty context.
update(): update this context w/ the local node's id.
reconcile(): pass in a list of context-value pairs and it'll return a merged context (that
supersedes all the passed in contexts) and a list of values that it couldn't automatically
reconcile.

VersionVectorContext is a version vector implementation.

The VV format is a concatenated list of node id (IPv4's 4 bytes), count (int), and timestamp
(long) tuples in a byte[].

create(): returns an empty byte[].
update(): will look for the local node's tuple in the byte[], increment its count, then prepend
it to the front of the byte[] w/ an updated timestamp.  So, that the byte[] is always in timestamp
descending order.
reconcile(): looks for all disjoint (incompatible) VVs and collapses all VVs that are a subset
of another VV in the list.  (implementation note: if 2 VVs are equal, but they're values are
not equivalent, both values will be added to the set of values that need to be manually reconciled.
 It seems inefficient, though, so when I go through the rest of the system, I'm going to see
if I can avoid this check.  Since, it's a problem that can only happen on the local node.)

VersionVectorContext helper methods of interest:
compareContexts(): sorts contexts by id, then steps through both contexts to determine pairwise:
equality, superset, subset, disjoint.
mergeContexts(): creates a map from node id to count-timestamp pairs, then create a timestamp-sorted
array and pulls off up to the max entries to form the new merged context.


      was (Author: kelvin):
    The patch adds a new package:
db/context

which contains:
IContext
VersionVectorContext

IContext is just a general interface to manipulate context byte[].  Basically, create(), update()
and reconcile().

create(): create a new/empty context.
update(): update this context w/ the local node's id.
reconcile(): pass in a list of context-value pairs and it'll return a merged context (that
supersedes all the passed in contexts) and a list of values that it couldn't automatically
reconciled.

VersionVectorContext is a version vector implementation.

The VV format is a concatenated list of node id (IPv4's 4 bytes), count (int), and timestamp
(long) tuples in a byte[].

create(): returns an empty byte[].
update(): will look for the local node's tuple in the byte[], increment its count, then prepend
it to the front of the byte[] w/ an updated timestamp.  So, that the byte[] is always in timestamp
descending order.
reconcile(): looks for all disjoint (incompatible) VVs and collapses all VVs that are a subset
of another VV in the list.  (implementation note: if 2 VVs are equal, but they're values are
not equivalent, both values will be added to the set of values that need to be manually reconciled.
 It seems inefficient, though, so when I go through the rest of the system, I'm going to see
if I can avoid this check.  Since, it's a problem that can only happen on the local node.)

VersionVectorContext helper methods of interest:
compareContexts(): sorts contexts by id, then steps through both contexts to determine pairwise:
equality, superset, subset, disjoint.
mergeContexts(): creates a map from node id to count-timestamp pairs, then create a timestamp-sorted
array and pulls off up to the max entries to form the new merged context.

  
> vector clock support
> --------------------
>
>                 Key: CASSANDRA-580
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-580
>             Project: Cassandra
>          Issue Type: New Feature
>          Components: Core
>         Environment: N/A
>            Reporter: Kelvin Kakugawa
>            Assignee: Kelvin Kakugawa
>         Attachments: 580-context-v1.patch, 580-interface-1-add-vector-clock.diff, 580-interface-2-add-vector-clock.diff,
580-thrift-v3.patch, 580-thrift-v4.patch, 580-thrift-v5.patch
>
>   Original Estimate: 672h
>  Remaining Estimate: 672h
>
> Allow a ColumnFamily to be versioned via vector clocks, instead of long timestamps. 
Purpose: enable incr/decr; flexible conflict resolution.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message