cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From marc...@apache.org
Subject cassandra git commit: Optimize the overlapping lookup by calculating all the bounds in advance.
Date Tue, 19 Apr 2016 11:39:00 GMT
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 <dikang85@gmail.com>
Authored: Tue Apr 19 09:40:31 2016 +0200
Committer: Marcus Eriksson <marcuse@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);
                 }
             }


Mime
View raw message