cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Fabien Rousseau (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-5677) Performance improvements of RangeTombstones/IntervalTree
Date Fri, 12 Jul 2013 13:21:49 GMT

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

Fabien Rousseau commented on CASSANDRA-5677:
--------------------------------------------

bq. Well, it's not abnormal and this is consistent with what we do in other places for such
min/max calculation (minTimestamp in SSTableWriter.appendFromStream for instance).

Ok

bq. Are we good with that fixed?

Yep, it's ok for me
                
> Performance improvements of RangeTombstones/IntervalTree
> --------------------------------------------------------
>
>                 Key: CASSANDRA-5677
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-5677
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>    Affects Versions: 1.2.0
>            Reporter: Fabien Rousseau
>            Assignee: Sylvain Lebresne
>            Priority: Minor
>             Fix For: 1.2.7
>
>         Attachments: 5677-1.2.overlappingfix.txt, 5677-1.2.txt, 5677-new-IntervalTree-implementation.patch
>
>
> Using massively range tombstones leads to bad response time (ie 100-500 ranges tombstones
per row).
> After investigation, it seems that the culprit is how the DeletionInfo are merged. Each
time a RangeTombstone is added into the DeletionInfo, the whole IntervalTree is rebuilt (thus,
if you have 100 tombstones in one row, then 100 instances of IntervalTree are created, the
first one having one interval, the second one 2 intervals,... the 100th one : 100 intervals...)
> It seems that once the IntervalTree is built, it is not possible to add a new Interval.
Idea is to change the implementation of the IntervalTree by another one which support "insert
interval".
> Attached is a proposed patch which :
>  - renames the IntervalTree implementation to IntervalTreeCentered (the renaming is inspired
from : http://en.wikipedia.org/wiki/Interval_tree)
>  - adds a new implementation IntervalTreeAvl (which is described here : http://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
and here : http://en.wikipedia.org/wiki/AVL_tree )
>  - adds a new interface IIntervalTree to abstract the implementation
>  - adds a new configuration option (interval_tree_provider) which allows to choose between
the two implementations (defaults to previous IntervalTreeCentered)
>  - updates IntervalTreeTest unit tests to test both implementations
>  - creates a mini benchmark between the two implementations (tree creation, point lookup,
interval lookup)
>  - creates a mini benchmark between the two implementations when merging DeletionInfo
(which shows a big performance improvement when using 500 tombstones for a row)
> This patch applies for 1.2 branch...

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message