cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sylvain Lebresne (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-5677) Performance improvements of RangeTombstones/IntervalTree
Date Thu, 04 Jul 2013 12:23:50 GMT


Sylvain Lebresne commented on CASSANDRA-5677:

So first, let's remark how inefficient is our current use of the IntervalTree. I wrote a small
benchmark test (1 node, locally, nothing fancy) that does the following:
* Creates the following table: CREATE TABLE test (k int, v int, PRIMARY KEY (k, v))
* Inserts N (CQL3) rows for a given (fixed) partition key (so: INSERT INTO test(k, v) VALUES
(0, <n>)).
* Deletes those N (CQL3) rows (DELETE FROM test WHERE k=0 AND v=<n>). This involves
insert a range tombstone (because it's not a compact table).
* Queries all rows for that partition key (SELECT * FROM test WHERE k=0), thus getting no
results. I also did the same query in revsed order to exercise that code path too.
I ran that 10 times (with a different partition key for each run) and timed all operation.
For N=2K (so pretty small), on trunk the results on my machine are:
        |         Insertions |          Deletions |              Query |     Reversed query
 Run 0  |           3418.0ms |          36950.6ms |          26100.5ms |          26147.3ms
 Run 1  |           2295.7ms |          36073.0ms |          28388.8ms |          28127.0ms
 Run 2  |           1641.2ms |          36119.4ms |          26953.1ms |          26177.8ms
 Run 3  |           1647.0ms |          30383.9ms |          28118.1ms |          27737.7ms
 Run 4  |           1472.9ms |          35913.1ms |          28172.3ms |          28046.6ms
 Run 5  |            679.8ms |          30472.8ms |          28197.5ms |          27756.0ms
 Run 6  |           1417.5ms |          30428.8ms |          28022.0ms |          27826.3ms
 Run 7  |            657.7ms |          30366.9ms |          28047.5ms |          28081.4ms
 Run 8  |            662.8ms |          30369.6ms |          28123.5ms |          27768.7ms
 Run 9  |            667.2ms |          30459.5ms |          32821.0ms |          32430.0ms
 Avg    |           1456.0ms |          32753.8ms |          28294.4ms |          28009.9ms
 8 last |           1105.8ms |          31814.3ms |          28556.9ms |          28228.1ms
Even ignoring the 2 first run (to let the JVM warm up), both deletion and query take about
30 seconds each! That's obviously very broken.

Now, Fabien's patch does fix the brokenness. After rebase to trunk (for fairness since my
tests are on trunk), and for N=10K (so 8x more that the previous test, the reason I've only
use 2K on bare trunk is that it's too long with 10K :)) I get:
        |         Insertions |          Deletions |              Query |     Reversed query
 Run 0  |           3460.4ms |           2575.7ms |             69.7ms |             93.7ms
 Run 1  |           1223.7ms |           1772.9ms |             64.3ms |             57.4ms
 Run 2  |           1416.7ms |            744.3ms |             25.8ms |             27.9ms
 Run 3  |            673.0ms |            298.5ms |             39.3ms |             29.4ms
 Run 4  |            470.5ms |            666.8ms |             31.7ms |             25.4ms
 Run 5  |            303.0ms |            591.8ms |             34.9ms |             26.4ms
 Run 6  |            512.9ms |            293.0ms |             26.3ms |             28.1ms
 Run 7  |            437.2ms |            595.0ms |             39.0ms |             24.8ms
 Run 8  |            295.6ms |            494.2ms |             32.5ms |             23.7ms
 Run 9  |            533.8ms |            258.7ms |             32.7ms |             25.6ms
 Avg    |            932.7ms |            829.1ms |             39.6ms |             36.2ms
 8 last |            580.3ms |            492.8ms |             32.8ms |             26.4ms
So, it's sane again (the query is a lot faster than the writes because my test do the insert/deletes
sequentially one at a time, I was mostly interested by read time anyway).  It's worth noting
that it's not really that our current "centered" interval tree implementation is bad in itself,
it's just that you can't add new interval once built which make it ill-suited for range tombstones
(but it's fine for our other use case of storing sstables).

However, as hinted in my previous comment, we can do better and generally improve our handling
of range tombstones by using the following properties:
# we don't care about overlapping range tombstone. If we have say the following range tombstones:
[0, 10]@3, [5, 8]@1, [8, 15]@4 (which we currently all store as-is), then we'd be fine just
storing: [0, 8]@3, [8, 15]@4. And in fact, storing the latter is more efficient (we have less
ranges) and would simplify some things slightly (for the ColumnIndexer for instance, by knowing
it can only have one "open" range tombstone at any time).
# During reads, we'll read range tombstone in sorted order, so we can use that fact to speed
up their insertion to the DeletionInfo the same way we do it in ArrayBackedSortedColumns for
# If we have a lot of range tombstones for a column family (which we can), the DeletionInfo
can start to represent quite a lot of memory/objects, because each range tombstone is a separate
object that has yet another DeletionTime object, plus the IntervalTree structure. We could
do something along the lines of CASSANDRA-5019, but it's a lot easier in that case because
the use we do of range tombstone is a lot more controlled.

So, I've pushed a patch at with what I have
in mind. Instead of providing a generic IntervalTree implementation, it adds a specialized
RangeTombstoneList (I take better name suggestions) structure just for range tombstones. That
structure keeps range tombstones as a sorted list, and when adding a new range, it only adds
the relevant part (it stores only [0, 8]@3, [8, 15]@4 if the 3 tombtones of my example above
are added).  It also tries to be reasonably memory efficient (which makes the implementation
slightly more verbose that could probably be, but it's well contained in the RangeTombstoneList
class so I think it's worth it overall) and optimize for the "inserts tombstone in sorted
order" case.  The result of the test above with that patch (N=10K to compare it to Fabien's
        |         Insertions |          Deletions |              Query |     Reversed query
 Run 0  |           3567.9ms |           2766.4ms |             42.8ms |             42.4ms
 Run 1  |           1718.5ms |           1723.9ms |             62.8ms |             33.0ms
 Run 2  |           1288.7ms |            722.4ms |              6.1ms |             21.9ms
 Run 3  |            720.0ms |            363.6ms |             10.3ms |             27.4ms
 Run 4  |            602.3ms |            642.6ms |             14.0ms |             13.4ms
 Run 5  |            272.8ms |            610.8ms |              9.3ms |             12.3ms
 Run 6  |            492.2ms |            278.1ms |             12.5ms |             26.2ms
 Run 7  |            550.8ms |            621.5ms |              5.5ms |             14.1ms
 Run 8  |            278.5ms |            586.0ms |             10.3ms |             19.9ms
 Run 9  |            534.1ms |            282.8ms |             10.7ms |             26.0ms
 Avg    |           1002.6ms |            859.8ms |             18.4ms |             23.7ms
 8 last |            592.4ms |            513.5ms |              9.8ms |             20.2ms
Deletions are about as fast (maybe a few percent slower, but even that could be noise of the
benchmark since it's not optimize for that part) but reads are more than 3x faster.  I will
note that I did not optimize for reverse queries, i.e.  RangeTombstoneList always keep tombstone
in comparator order, so reverse queries are hitting the worst possible case for that structure.
It wouldn't be very hard to optimize for it the same way we do it in ArrayBackedSortedColumns
but I'd rather keep that to a followup ticket because as can be seen above, even in the reverse
case RangeTombstoneList is faster, so there is probably no big rush.

I'll note that my patch is against trunk. I'm not sure what to do for 1.2. Neither my patch
nor Fabien's one are completely trivial, though at the same time the current performance is
fairly bad if you have more than a few range tombstones.

> Performance improvements of RangeTombstones/IntervalTree
> --------------------------------------------------------
>                 Key: CASSANDRA-5677
>                 URL:
>             Project: Cassandra
>          Issue Type: Improvement
>    Affects Versions: 1.2.0
>            Reporter: Fabien Rousseau
>            Priority: Minor
>         Attachments: 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
> Attached is a proposed patch which :
>  - renames the IntervalTree implementation to IntervalTreeCentered (the renaming is inspired
from :
>  - adds a new implementation IntervalTreeAvl (which is described here :
and here : )
>  - 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:

View raw message