[jira] [Comment Edited] (CASSANDRA-6271) Replace SnapTree in AtomicSortedColumns

["Jonathan Ellis (JIRA)" <ji...@apache.org>]

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