You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by ma...@apache.org on 2016/04/19 13:39:00 UTC
cassandra git commit: Optimize the overlapping lookup by calculating
all the bounds in advance.
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 <di...@gmail.com>
Authored: Tue Apr 19 09:40:31 2016 +0200
Committer: Marcus Eriksson <ma...@apache.org>
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);
}
}