You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by be...@apache.org on 2024/11/22 12:33:29 UTC
(cassandra-accord) 01/01: Key transaction recovery should witness range transactions
This is an automated email from the ASF dual-hosted git repository.
benedict pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
commit 5f1d4766e3a1b3254a4f2e2fa0e8523842e07012
Author: David Capwell <dc...@apache.org>
AuthorDate: Thu Oct 17 13:58:25 2024 -0700
Key transaction recovery should witness range transactions
patch by Benedict; reviewed by David for CASSANDRA-20105
---
.../java/accord/utils/CheckpointIntervalArray.java | 31 +++++++++++++++++++++
.../utils/CheckpointIntervalArrayBuilder.java | 3 ++
.../java/accord/utils/SearchableRangeList.java | 32 ----------------------
.../accord/utils/SearchableRangeListBuilder.java | 18 ++++++++++++
4 files changed, 52 insertions(+), 32 deletions(-)
diff --git a/accord-core/src/main/java/accord/utils/CheckpointIntervalArray.java b/accord-core/src/main/java/accord/utils/CheckpointIntervalArray.java
index d5a60b71..9661ebfc 100644
--- a/accord-core/src/main/java/accord/utils/CheckpointIntervalArray.java
+++ b/accord-core/src/main/java/accord/utils/CheckpointIntervalArray.java
@@ -24,6 +24,7 @@ import accord.utils.CheckpointIntervalArrayBuilder.Accessor;
import net.nicoulaj.compilecommand.annotations.Inline;
import static accord.utils.SortedArrays.Search.CEIL;
+import static accord.utils.SortedArrays.Search.FLOOR;
public class CheckpointIntervalArray<Ranges, Range, Key>
{
@@ -216,4 +217,34 @@ public class CheckpointIntervalArray<Ranges, Range, Key>
forEachRange.accept(p1, p2, p3, p4, start, end);
return end;
}
+
+ @Inline
+ public <P1, P2, P3, P4> int forEachKey(Key key, IndexedQuadConsumer<P1, P2, P3, P4> forEachScanOrCheckpoint, IndexedRangeQuadConsumer<P1, P2, P3, P4> forEachRange, P1 p1, P2 p2, P3 p3, P4 p4, int minIndex)
+ {
+ if (accessor.size(ranges) == 0 || minIndex == accessor.size(ranges))
+ return minIndex;
+
+ int end = accessor.binarySearch(ranges, minIndex, accessor.size(ranges), key, (a, b) -> -accessor.compareStartTo(b, a), FLOOR);
+ if (end < 0) end = -1 - end;
+ if (end <= minIndex) return minIndex;
+
+ int floor = accessor.binarySearch(ranges, minIndex, accessor.size(ranges), key, (a, b) -> -accessor.compareStartTo(b, a), CEIL);
+ int start = floor;
+ if (floor < 0)
+ {
+ // if there's no precise match on start, step backwards;
+ // if this range does not overlap us, step forwards again for start
+ // but retain the floor index for performing scan and checkpoint searches from
+ // as this contains all ranges that might overlap us (whereas those that end
+ // after us but before the next range's start would be missed by the next range index)
+ start = floor = -2 - floor;
+ if (start < 0)
+ start = floor = 0;
+ else if (accessor.compareEndTo(accessor.get(ranges, start), key) < 0)
+ ++start;
+ }
+
+ int bound = accessor.endInclusive(ranges) ? -1 : 0;
+ return forEach(start, end, floor, key, bound, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, p4, minIndex);
+ }
}
diff --git a/accord-core/src/main/java/accord/utils/CheckpointIntervalArrayBuilder.java b/accord-core/src/main/java/accord/utils/CheckpointIntervalArrayBuilder.java
index 95e1d86e..c50c0eb4 100644
--- a/accord-core/src/main/java/accord/utils/CheckpointIntervalArrayBuilder.java
+++ b/accord-core/src/main/java/accord/utils/CheckpointIntervalArrayBuilder.java
@@ -76,6 +76,9 @@ public class CheckpointIntervalArrayBuilder<Ranges, Range, RoutingKey>
RoutingKey end(Ranges ranges, int index);
RoutingKey end(Range range);
Comparator<RoutingKey> keyComparator();
+ int compareEndTo(Range range, RoutingKey key);
+ int compareStartTo(Range range, RoutingKey key);
+ boolean endInclusive(Ranges ranges);
int binarySearch(Ranges ranges, int from, int to, RoutingKey find, AsymmetricComparator<RoutingKey, Range> comparator, SortedArrays.Search op);
}
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeList.java b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
index 5e677e82..c0741810 100644
--- a/accord-core/src/main/java/accord/utils/SearchableRangeList.java
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
@@ -22,11 +22,9 @@ import accord.primitives.Range;
import accord.primitives.RoutableKey;
import accord.utils.CheckpointIntervalArrayBuilder.Links;
import accord.utils.CheckpointIntervalArrayBuilder.Strategy;
-import net.nicoulaj.compilecommand.annotations.Inline;
import static accord.utils.CheckpointIntervalArrayBuilder.Links.LINKS;
import static accord.utils.CheckpointIntervalArrayBuilder.Strategy.ACCURATE;
-import static accord.utils.SortedArrays.Search.*;
/**
* Based on CINTIA, the Checkpoint INTerval Array
@@ -85,36 +83,6 @@ public class SearchableRangeList extends CheckpointIntervalArray<Range[], Range,
super(SearchableRangeListBuilder.RANGE_ACCESSOR, ranges, lowerBounds, headers, checkpointLists, maxScanAndCheckpointMatches);
}
- @Inline
- public <P1, P2, P3, P4> int forEachKey(RoutableKey key, IndexedQuadConsumer<P1, P2, P3, P4> forEachScanOrCheckpoint, IndexedRangeQuadConsumer<P1, P2, P3, P4> forEachRange, P1 p1, P2 p2, P3 p3, P4 p4, int minIndex)
- {
- if (ranges.length == 0 || minIndex == ranges.length)
- return minIndex;
-
- int end = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> -b.compareStartTo(a), FLOOR);
- if (end < 0) end = -1 - end;
- if (end <= minIndex) return minIndex;
-
- int floor = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> -b.compareStartTo(a), CEIL);
- int start = floor;
- if (floor < 0)
- {
- // if there's no precise match on start, step backwards;
- // if this range does not overlap us, step forwards again for start
- // but retain the floor index for performing scan and checkpoint searches from
- // as this contains all ranges that might overlap us (whereas those that end
- // after us but before the next range's start would be missed by the next range index)
- start = floor = -2 - floor;
- if (start < 0)
- start = floor = 0;
- else if (ranges[start].compareEndTo(key) < 0)
- ++start;
- }
-
- int bound = ranges[0].endInclusive() ? -1 : 0;
- return forEach(start, end, floor, key, bound, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, p4, minIndex);
- }
-
public static SearchableRangeList build(Range[] ranges)
{
if (ranges.length == 0)
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
index 546ee16a..73d6dc77 100644
--- a/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
@@ -74,6 +74,24 @@ public class SearchableRangeListBuilder extends CheckpointIntervalArrayBuilder<R
return Comparator.naturalOrder();
}
+ @Override
+ public int compareEndTo(Range range, RoutableKey key)
+ {
+ return range.compareEndTo(key);
+ }
+
+ @Override
+ public int compareStartTo(Range range, RoutableKey key)
+ {
+ return range.compareStartTo(key);
+ }
+
+ @Override
+ public boolean endInclusive(Range[] ranges)
+ {
+ return ranges[0].endInclusive();
+ }
+
@Override
public int binarySearch(Range[] ranges, int from, int to, RoutableKey find, AsymmetricComparator<RoutableKey, Range> comparator, SortedArrays.Search op)
{
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org