[
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.
