This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch cassandra-4.0
in repository https://gitbox.apache.org/repos/asf/cassandra.git
The following commit(s) were added to refs/heads/cassandra-4.0 by this push:
new fbe28f3bb3 During streaming Bounds.getNonOverlappingBounds produces
incorrect bounds leading to row/counter cache not invalidate correctly
fbe28f3bb3 is described below
commit fbe28f3bb361077eb41b4119a68bf2fbb99c59c7
Author: Alan Wang <[email protected]>
AuthorDate: Fri Aug 28 12:59:05 2026 -0700
During streaming Bounds.getNonOverlappingBounds produces incorrect bounds
leading to row/counter cache not invalidate correctly
patch by Alan Wang; reviewed by David Capwell, Marcus Eriksson for
CASSANDRA-21594
---
CHANGES.txt | 1 +
src/java/org/apache/cassandra/dht/Bounds.java | 30 +++++-----
test/unit/org/apache/cassandra/dht/BoundsTest.java | 67 ++++++++++++++++++++--
3 files changed, 77 insertions(+), 21 deletions(-)
diff --git a/CHANGES.txt b/CHANGES.txt
index 9a23d0f160..16ad4de905 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
4.0.22
+ * During streaming Bounds.getNonOverlappingBounds produces incorrect bounds
leading to row/counter cache not invalidate correctly (CASSANDRA-21594)
* Make runWithCompactionsDisabled return non-null on success (CASSANDRA-21527)
* Validate authz before performing role check in LIST ROLES/PERMISSIONS
(CASSANDRA-21560)
* Ensure transferred_ranges reset on decommision re-attempt when pending
ranges cannot be proven continous (CASSANDRA-16290)
diff --git a/src/java/org/apache/cassandra/dht/Bounds.java
b/src/java/org/apache/cassandra/dht/Bounds.java
index 626eaa60f0..cd64b1ea88 100644
--- a/src/java/org/apache/cassandra/dht/Bounds.java
+++ b/src/java/org/apache/cassandra/dht/Bounds.java
@@ -17,14 +17,13 @@
*/
package org.apache.cassandra.dht;
-import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterators;
-import com.google.common.collect.Lists;
import com.google.common.collect.PeekingIterator;
import com.google.common.collect.Sets;
@@ -155,32 +154,29 @@ public class Bounds<T extends RingPosition<T>> extends
AbstractBounds<T>
* [ ] [ ] [ ] [ ]
* [ ] [ ]
* This method will return the following bounds:
- * [ ] [ ]
+ * [ ] [ ]
*
* @param bounds unsorted bounds to find overlaps
* @return the non-overlapping bounds
*/
public static <T extends RingPosition<T>> Set<Bounds<T>>
getNonOverlappingBounds(Iterable<Bounds<T>> bounds)
{
- ArrayList<Bounds<T>> sortedBounds = Lists.newArrayList(bounds);
- Collections.sort(sortedBounds, new Comparator<Bounds<T>>()
- {
- public int compare(Bounds<T> o1, Bounds<T> o2)
- {
- return o1.left.compareTo(o2.left);
- }
- });
-
+ List<Bounds<T>> sortedBounds =
ImmutableList.sortedCopyOf(Comparator.comparing(o -> o.left), bounds);
Set<Bounds<T>> nonOverlappingBounds = Sets.newHashSet();
PeekingIterator<Bounds<T>> it =
Iterators.peekingIterator(sortedBounds.iterator());
while (it.hasNext())
{
- Bounds<T> beginBound = it.next();
- Bounds<T> endBound = beginBound;
- while (it.hasNext() && endBound.right.compareTo(it.peek().left) >=
0)
- endBound = it.next();
- nonOverlappingBounds.add(new Bounds<>(beginBound.left,
endBound.right));
+ Bounds<T> startBound = it.next();
+ T end = startBound.right;
+ while (it.hasNext() && end.compareTo(it.peek().left) >= 0)
+ {
+ Bounds<T> bound = it.next();
+ if (end.compareTo(bound.right) < 0)
+ end = bound.right;
+ }
+
+ nonOverlappingBounds.add(new Bounds<>(startBound.left, end));
}
return nonOverlappingBounds;
diff --git a/test/unit/org/apache/cassandra/dht/BoundsTest.java
b/test/unit/org/apache/cassandra/dht/BoundsTest.java
index 2ac06d9022..a4ba9bef21 100644
--- a/test/unit/org/apache/cassandra/dht/BoundsTest.java
+++ b/test/unit/org/apache/cassandra/dht/BoundsTest.java
@@ -18,7 +18,7 @@
package org.apache.cassandra.dht;
-import java.util.LinkedList;
+import java.util.ArrayList;
import java.util.List;
import java.util.Set;
@@ -29,21 +29,20 @@ import static org.junit.Assert.assertTrue;
public class BoundsTest
{
-
private Bounds<Token> bounds(long left, long right)
{
return new Bounds<Token>(new Murmur3Partitioner.LongToken(left), new
Murmur3Partitioner.LongToken(right));
}
- @Test
/**
* [0,1],[0,5],[1,8],[4,10] = [0, 10]
* [15,19][19,20] = [15,20]
* [21, 22] = [21,22]
*/
+ @Test
public void testGetNonOverlappingBounds()
{
- List<Bounds<Token>> bounds = new LinkedList<>();
+ List<Bounds<Token>> bounds = new ArrayList<>();
bounds.add(bounds(19, 20));
bounds.add(bounds(0, 1));
bounds.add(bounds(4, 10));
@@ -58,4 +57,64 @@ public class BoundsTest
assertTrue(nonOverlappingBounds.contains(bounds(15,20)));
assertTrue(nonOverlappingBounds.contains(bounds(21,22)));
}
+
+ /**
+ * [1, 100] [2, 5] = [1, 100]
+ */
+ @Test
+ public void testGetNonOverlappingBounds2()
+ {
+ List<Bounds<Token>> bounds = new ArrayList<>();
+ bounds.add(bounds(1, 100));
+ bounds.add(bounds(2, 5));
+
+ Set<Bounds<Token>> nonOverlappingBounds =
Bounds.getNonOverlappingBounds(bounds);
+ assertEquals(1, nonOverlappingBounds.size());
+ assertTrue(nonOverlappingBounds.contains(bounds(1, 100)));
+ }
+
+ /**
+ * [1, 100] [99, 101] = [1, 101]
+ */
+ @Test
+ public void testGetNonOverlappingBounds3()
+ {
+ List<Bounds<Token>> bounds = new ArrayList<>();
+ bounds.add(bounds(1, 100));
+ bounds.add(bounds(99, 101));
+
+ Set<Bounds<Token>> nonOverlappingBounds =
Bounds.getNonOverlappingBounds(bounds);
+ assertEquals(1, nonOverlappingBounds.size());
+ assertTrue(nonOverlappingBounds.contains(bounds(1, 101)));
+ }
+
+ /**
+ * [0, 2] [1, 100] = [0, 100]
+ */
+ @Test
+ public void testGetNonOverlappingBounds4()
+ {
+ List<Bounds<Token>> bounds = new ArrayList<>();
+ bounds.add(bounds(0, 2));
+ bounds.add(bounds(1, 100));
+
+ Set<Bounds<Token>> nonOverlappingBounds =
Bounds.getNonOverlappingBounds(bounds);
+ assertEquals(1, nonOverlappingBounds.size());
+ assertTrue(nonOverlappingBounds.contains(bounds(0, 100)));
+ }
+
+ /**
+ * [0, 0] [0, 100] = [0, 100]
+ */
+ @Test
+ public void testGetNonOverlappingBounds5()
+ {
+ List<Bounds<Token>> bounds = new ArrayList<>();
+ bounds.add(bounds(0, 0));
+ bounds.add(bounds(0, 100));
+
+ Set<Bounds<Token>> nonOverlappingBounds =
Bounds.getNonOverlappingBounds(bounds);
+ assertEquals(1, nonOverlappingBounds.size());
+ assertTrue(nonOverlappingBounds.contains(bounds(0, 100)));
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
