Repository: cassandra Updated Branches: refs/heads/trunk 5805a76ca -> a17120adf
Optimize the overlapping lookup by calculating all the bounds in advance. Patch by Dikang Gu; reviewed by marcuse for CASSANDRA-11571 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/a17120ad Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/a17120ad Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/a17120ad Branch: refs/heads/trunk Commit: a17120adffe6889ebbc4e76adb493898b6799a0d Parents: 5805a76 Author: Dikang Gu <[email protected]> Authored: Tue Apr 19 09:40:31 2016 +0200 Committer: Marcus Eriksson <[email protected]> Committed: Tue Apr 19 13:25:58 2016 +0200 ---------------------------------------------------------------------- CHANGES.txt | 2 + .../db/compaction/LeveledManifest.java | 42 ++++++++++++++------ .../LongLeveledCompactionStrategyTest.java | 2 +- 3 files changed, 32 insertions(+), 14 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/a17120ad/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 7a77cd4..1e6bcd6 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,6 @@ 3.6 + * Optimize the overlapping lookup by calculating all the + bounds in advance (CASSANDRA-11571) * Support json/yaml output in noetool tablestats (CASSANDRA-5977) * (stress) Add datacenter option to -node options (CASSANDRA-11591) * Fix handling of empty slices (CASSANDRA-11513) http://git-wip-us.apache.org/repos/asf/cassandra/blob/a17120ad/src/java/org/apache/cassandra/db/compaction/LeveledManifest.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/compaction/LeveledManifest.java b/src/java/org/apache/cassandra/db/compaction/LeveledManifest.java index 3a1f475..3dba954 100644 --- a/src/java/org/apache/cassandra/db/compaction/LeveledManifest.java +++ b/src/java/org/apache/cassandra/db/compaction/LeveledManifest.java @@ -518,25 +518,30 @@ public class LeveledManifest return overlapping(first, last, others); } - @VisibleForTesting - static Set<SSTableReader> overlapping(SSTableReader sstable, Iterable<SSTableReader> others) + private static Set<SSTableReader> overlappingWithBounds(SSTableReader sstable, Map<SSTableReader, Bounds<Token>> others) { - return overlapping(sstable.first.getToken(), sstable.last.getToken(), others); + return overlappingWithBounds(sstable.first.getToken(), sstable.last.getToken(), others); } /** * @return sstables from @param sstables that contain keys between @param start and @param end, inclusive. */ - private static Set<SSTableReader> overlapping(Token start, Token end, Iterable<SSTableReader> sstables) + @VisibleForTesting + static Set<SSTableReader> overlapping(Token start, Token end, Iterable<SSTableReader> sstables) + { + return overlappingWithBounds(start, end, genBounds(sstables)); + } + + private static Set<SSTableReader> overlappingWithBounds(Token start, Token end, Map<SSTableReader, Bounds<Token>> sstables) { assert start.compareTo(end) <= 0; Set<SSTableReader> overlapped = new HashSet<>(); Bounds<Token> promotedBounds = new Bounds<Token>(start, end); - for (SSTableReader candidate : sstables) + + for (Map.Entry<SSTableReader, Bounds<Token>> pair : sstables.entrySet()) { - Bounds<Token> candidateBounds = new Bounds<Token>(candidate.first.getToken(), candidate.last.getToken()); - if (candidateBounds.intersects(promotedBounds)) - overlapped.add(candidate); + if (pair.getValue().intersects(promotedBounds)) + overlapped.add(pair.getKey()); } return overlapped; } @@ -549,6 +554,16 @@ public class LeveledManifest } }; + private static Map<SSTableReader, Bounds<Token>> genBounds(Iterable<SSTableReader> ssTableReaders) + { + Map<SSTableReader, Bounds<Token>> boundsMap = new HashMap<>(); + for (SSTableReader sstable : ssTableReaders) + { + boundsMap.put(sstable, new Bounds<Token>(sstable.first.getToken(), sstable.last.getToken())); + } + return boundsMap; + } + /** * @return highest-priority sstables to compact for the given level. * If no compactions are possible (because of concurrent compactions or because some sstables are blacklisted @@ -589,14 +604,14 @@ public class LeveledManifest // basically screwed, since we expect all or most L0 sstables to overlap with each L1 sstable. // So if an L1 sstable is suspect we can't do much besides try anyway and hope for the best. Set<SSTableReader> candidates = new HashSet<>(); - Set<SSTableReader> remaining = new HashSet<>(); - Iterables.addAll(remaining, Iterables.filter(getLevel(0), Predicates.not(suspectP))); - for (SSTableReader sstable : ageSortedSSTables(remaining)) + Map<SSTableReader, Bounds<Token>> remaining = genBounds(Iterables.filter(getLevel(0), Predicates.not(suspectP))); + + for (SSTableReader sstable : ageSortedSSTables(remaining.keySet())) { if (candidates.contains(sstable)) continue; - Sets.SetView<SSTableReader> overlappedL0 = Sets.union(Collections.singleton(sstable), overlapping(sstable, remaining)); + Sets.SetView<SSTableReader> overlappedL0 = Sets.union(Collections.singleton(sstable), overlappingWithBounds(sstable, remaining)); if (!Sets.intersection(overlappedL0, compactingL0).isEmpty()) continue; @@ -649,10 +664,11 @@ public class LeveledManifest // look for a non-suspect keyspace to compact with, starting with where we left off last time, // and wrapping back to the beginning of the generation if necessary + Map<SSTableReader, Bounds<Token>> sstablesNextLevel = genBounds(getLevel(level + 1)); for (int i = 0; i < getLevel(level).size(); i++) { SSTableReader sstable = getLevel(level).get((start + i) % getLevel(level).size()); - Set<SSTableReader> candidates = Sets.union(Collections.singleton(sstable), overlapping(sstable, getLevel(level + 1))); + Set<SSTableReader> candidates = Sets.union(Collections.singleton(sstable), overlappingWithBounds(sstable, sstablesNextLevel)); if (Iterables.any(candidates, suspectP)) continue; if (Sets.intersection(candidates, compacting).isEmpty()) http://git-wip-us.apache.org/repos/asf/cassandra/blob/a17120ad/test/long/org/apache/cassandra/db/compaction/LongLeveledCompactionStrategyTest.java ---------------------------------------------------------------------- diff --git a/test/long/org/apache/cassandra/db/compaction/LongLeveledCompactionStrategyTest.java b/test/long/org/apache/cassandra/db/compaction/LongLeveledCompactionStrategyTest.java index 0f05524..fe1871b 100644 --- a/test/long/org/apache/cassandra/db/compaction/LongLeveledCompactionStrategyTest.java +++ b/test/long/org/apache/cassandra/db/compaction/LongLeveledCompactionStrategyTest.java @@ -128,7 +128,7 @@ public class LongLeveledCompactionStrategyTest if (level > 0) {// overlap check for levels greater than 0 - Set<SSTableReader> overlaps = LeveledManifest.overlapping(sstable, sstables); + Set<SSTableReader> overlaps = LeveledManifest.overlapping(sstable.first.getToken(), sstable.last.getToken(), sstables); assert overlaps.size() == 1 && overlaps.contains(sstable); } }
