[
https://issues.apache.org/jira/browse/CASSANDRA-8920?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14367573#comment-14367573
]
Benedict commented on CASSANDRA-8920:
-------------------------------------
OK, so following our discussion this morning I thought this afternoon I'd have
a quick crack at just making it faster. It's actually possible to make the
amortized cost constant, and I've introduced a new class to do this. Mostly
it's boiler plate, the interesting code is just a few lines.
Basically we sort the intervals in ascending order of both min _and_ max. Each
time we visit a key, we search forwards from the last key in the min-ordered
collection, inserting every item that is now behind us. We then search forwards
from the last key in the max-ordered collection _removing_ everything that is
now before us. We maintain this collection in a HashSet, and iterate the
contents of the hashset, performing our BF lookups on the contents of this set.
The result is behaviour that is algorithmically optimal for both LCS and STCS.
I've wired up some randomised testing that ensures the results are identical to
performing an interval tree search, which helpfully also corroborates that this
collection is behaving correctly.
The only caveat is that algorithmic performance is O(max(N,S)/N) where S is the
number of sstables, and N the number of keys we're compacting. So if somehow S
is much larger than N, performance will not be constant. But this would be
indicative of significantly larger problems.
> Remove IntervalTree from maxPurgeableTimestamp calculation
> ----------------------------------------------------------
>
> Key: CASSANDRA-8920
> URL: https://issues.apache.org/jira/browse/CASSANDRA-8920
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Benedict
> Assignee: Benedict
> Priority: Minor
> Fix For: 2.1.4
>
> Attachments: 8920.txt
>
>
> The IntervalTree only maps partition keys. Since a majority of users deploy a
> hashed partitioner the work is mostly wasted, since they will be evenly
> distributed across the full token range owned by the node - and in some cases
> it is a significant amount of work. We can perform a corroboration against
> the file bounds if we get a BF match as a sanity check if we like, but
> performing an IntervalTree search is significantly more expensive (esp. once
> murmur hash calculation memoization goes mainstream).
> In LCS, the keys are bounded, to it might appear that it would help, but in
> this scenario we only compact against like bounds, so again it is not helpful.
> With a ByteOrderedPartitioner it could potentially be of use, but this is
> sufficiently rare to not optimise for IMO.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
