cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jonathan Ellis (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (CASSANDRA-6271) Replace SnapTree in AtomicSortedColumns
Date Wed, 01 Jan 2014 22:48:50 GMT

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

Jonathan Ellis edited comment on CASSANDRA-6271 at 1/1/14 10:47 PM:
--------------------------------------------------------------------

I still don't quite follow.  Shouldn't we increment the root-index by 1, instead of end-of-keys?
 If we've visited the children less than the key at index, then the next one to visit should
be that key, then the children before the next key.

E.g. suppose we have this tree: http://xml.apache.org/xindice/dev/images/btree.png

and we call successor() when current node is the leaf containing 32.  Then successor should
be root node, key of 37.  (Subsequently the children of 37 should also be visited.)

(I guess I should have looked a bit harder for a diagram since their tree allows duplicates,
but hopefully that is still clear enough.)


was (Author: jbellis):
I still don't quite follow.  Shouldn't we increment the root-index by 1, instead of end-of-keys?
 If we've visited the children less than the key at index, then the next one to visit should
be that key, then the children before the next key.

E.g. suppose we have this tree: http://xml.apache.org/xindice/dev/images/btree.png

and we call successor() when current node is the leaf containing 32.  Then successor should
be root node, key of 37.  (Subsequently the children of 37 should also be visited.)

> Replace SnapTree in AtomicSortedColumns
> ---------------------------------------
>
>                 Key: CASSANDRA-6271
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-6271
>             Project: Cassandra
>          Issue Type: Improvement
>            Reporter: Benedict
>            Assignee: Benedict
>              Labels: performance
>         Attachments: oprate.svg
>
>
> On the write path a huge percentage of time is spent in GC (>50% in my tests, if accounting
for slow down due to parallel marking). SnapTrees are both GC unfriendly due to their structure
and also very expensive to keep around - each column name in AtomicSortedColumns uses >
100 bytes on average (excluding the actual ByteBuffer).
> I suggest using a sorted array; changes are supplied at-once, as opposed to one at a
time, and if < 10% of the keys in the array change (and data equal to < 10% of the size
of the key array) we simply overlay a new array of changes only over the top. Otherwise we
rewrite the array. This method should ensure much less GC overhead, and also save approximately
80% of the current memory overhead.
> TreeMap is similarly difficult object for the GC, and a related task might be to remove
it where not strictly necessary, even though we don't keep them hanging around for long. TreeMapBackedSortedColumns,
for instance, seems to be used in a lot of places where we could simply sort the columns.



--
This message was sent by Atlassian JIRA
(v6.1.5#6160)

Mime
View raw message