You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by GitBox <gi...@apache.org> on 2022/11/28 21:41:02 UTC
[GitHub] [cassandra-accord] aweisberg commented on a diff in pull request #15: Routables refactor
aweisberg commented on code in PR #15:
URL: https://github.com/apache/cassandra-accord/pull/15#discussion_r1033813598
##########
accord-core/src/main/java/accord/api/Key.java:
##########
@@ -18,10 +18,12 @@
package accord.api;
+import accord.primitives.SortableKey;
+import accord.primitives.Seekable;
+
/**
* A routing key for determining which shards are involved in a transaction
Review Comment:
Should this comment be updated?
##########
accord-core/src/main/java/accord/primitives/Routables.java:
##########
@@ -0,0 +1,69 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+/**
+ * Either a Route or a collection of Routable
+ */
+public interface Routables<K extends Routable, U extends Routables<K, ?>> extends Iterable<K>, Sortables<K, U>
+{
+ enum RoutablesKind
+ {
+ RoutingKeys, PartialKeyRoute, FullKeyRoute, RoutingRanges, PartialRangeRoute, FullRangeRoute;
+ public boolean isRoute()
+ {
+ return this != RoutingKeys;
+ }
+
+ public boolean isFullRoute()
+ {
+ switch (this)
+ {
+ default: throw new AssertionError();
+ case FullKeyRoute:
+ case FullRangeRoute:
+ return true;
+ case RoutingKeys:
+ case PartialKeyRoute:
+ case RoutingRanges:
Review Comment:
It's just `Ranges` as a class name. The differentiation between `Routable` and `Seekable` ranges doesn't exist yet.
##########
accord-core/src/main/java/accord/primitives/AbstractKeys.java:
##########
@@ -2,24 +2,22 @@
import java.util.Arrays;
import java.util.Iterator;
-import java.util.function.BiFunction;
+import java.util.function.Consumer;
+import java.util.function.Function;
import java.util.function.IntFunction;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import accord.api.RoutingKey;
-import accord.utils.IndexedFold;
-import accord.utils.IndexedFoldIntersectToLong;
-import accord.utils.IndexedFoldToLong;
-import accord.utils.IndexedPredicate;
-import accord.utils.IndexedRangeFoldToLong;
-import accord.utils.SortedArrays;
+import accord.utils.*;
import net.nicoulaj.compilecommand.annotations.Inline;
+import static accord.primitives.Sortable.Kind.Key;
+
@SuppressWarnings("rawtypes")
// TODO: check that foldl call-sites are inlined and optimised by HotSpot
-public abstract class AbstractKeys<K extends RoutingKey, KS extends AbstractKeys<K, KS>> implements Iterable<K>
+public abstract class AbstractKeys<K extends SortableKey, KS extends Sortables<K, ?>> implements Iterable<K>, Sortables<K, KS>
Review Comment:
```suggestion
// AbstractKeys should be avoided in favor of derived classes because it doesn't restrict to a single kind of key (Routable, Seekable)
public abstract class AbstractKeys<K extends SortableKey, KS extends Sortables<K, ?>> implements Iterable<K>, Sortables<K, KS>
```
##########
accord-core/src/main/java/accord/primitives/Sortables.java:
##########
@@ -0,0 +1,257 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+import accord.utils.IndexedFold;
+import accord.utils.IndexedFoldToLong;
+import accord.utils.IndexedRangeFoldToLong;
+import accord.utils.SortedArrays;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import static accord.utils.SortedArrays.Search.FLOOR;
+
+/**
+ * Either a Route or a collection of Sortable
+ */
+public interface Sortables<K extends Sortable, U extends Sortables<K, ?>> extends Iterable<K>
+{
+ int indexOf(K item);
+ K get(int i);
+ int size();
+
+ boolean isEmpty();
+ boolean intersects(AbstractRanges<?> ranges);
+ boolean contains(SortableKey key);
+ boolean containsAll(Sortables<?, ?> keysOrRanges);
+
+ U slice(Ranges ranges);
+ Sortables<K, U> union(U with);
+
+ /**
+ * @return an arbitrary key that relates to this Findable - this may or may not be contained by this Findable,
+ * as this is preferably the
+ */
+ RoutingKey candidateShardKey();
+
+ /**
+ * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection
+ * that intersect with each other. Return their position packed in a long, with low bits representing
+ * the resultant {@code thisIndex} and high bits {@code withIndex}.
+ */
+ long findNextIntersection(int thisIndex, AbstractRanges<?> with, int withIndex);
+
+ /**
+ * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection
+ * that intersect with each other. Return their position packed in a long, with low bits representing
+ * the resultant {@code thisIndex} and high bits {@code withIndex}.
+ */
+ long findNextIntersection(int thisIndex, AbstractKeys<?, ?> with, int withIndex);
+
+ /**
+ * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection
+ * that intersect with each other. Return their position packed in a long, with low bits representing
+ * the resultant {@code thisIndex} and high bits {@code withIndex}.
+ */
+ long findNextIntersection(int thisIndex, Sortables<K, ?> with, int withIndex);
+
+ /**
+ * Perform {@link SortedArrays#exponentialSearch} from {@code thisIndex} looking for {@code find} with behaviour of {@code search}
+ */
+ int findNext(int thisIndex, Range find, SortedArrays.Search search);
+
+ /**
+ * Perform {@link SortedArrays#exponentialSearch} from {@code thisIndex} looking for {@code find} with behaviour of {@code search}
+ */
+ int findNext(int thisIndex, K find, SortedArrays.Search search);
+
+ FullRoute<?> toRoute(RoutingKey homeKey);
+
+ Sortable.Kind kindOfContents();
+
+ @Inline
+ static <Input extends Sortable, T> T foldl(Sortables<Input, ?> inputs, AbstractRanges<?> matching, IndexedFold<? super Input, T> fold, T initialValue)
+ {
+ return Helper.foldl(Sortables::findNextIntersection, Helper::findLimit, inputs, matching, fold, initialValue);
+ }
+
+ @Inline
+ static <Input extends SortableKey, T> T foldl(AbstractKeys<Input, ?> inputs, AbstractRanges<?> matching, IndexedFold<? super Input, T> fold, T initialValue)
+ {
+ return Helper.foldl(AbstractKeys::findNextIntersection, Helper::findLimit, inputs, matching, fold, initialValue);
+ }
+
+ @Inline
+ static <Input extends SortableKey> long foldl(AbstractKeys<Input, ?> inputs, AbstractRanges<?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.foldl(AbstractKeys::findNextIntersection, Helper::findLimit, inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends Sortable> long foldl(Sortables<Input, ?> inputs, AbstractRanges<?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.foldl(Sortables::findNextIntersection, Helper::findLimit, inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends Sortable> long foldl(Sortables<Input, ?> inputs, AbstractKeys<?, ?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.foldl(Sortables::findNextIntersection, (ls, li, rs, ri) -> li + 1,
+ inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends RoutingKey, Matching extends Sortable> long foldl(AbstractKeys<Input, ?> inputs, Sortables<Matching, ?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.foldl((ls, li, rs, ri) -> SortedArrays.swapHighLow32b(rs.findNextIntersection(ri, ls, li)), (ls, li, rs, ri) -> li + 1,
+ inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends Sortable> long rangeFoldl(Sortables<Input, ?> inputs, AbstractRanges<?> matching, IndexedRangeFoldToLong fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.rangeFoldl(Sortables::findNextIntersection, (ls, li, rs, ri) -> li + 1,
+ inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends Sortable> long rangeFoldl(Sortables<Input, ?> inputs, AbstractKeys<?, ?> matching, IndexedRangeFoldToLong fold, long param, long initialValue, long terminalValue)
+ {
+ return Helper.rangeFoldl(Sortables::findNextIntersection, (ls, li, rs, ri) -> li + 1,
+ inputs, matching, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ static <Input extends Sortable> long foldlMissing(Sortables<Input, ?> inputs, Sortables<Input, ?> notMatching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue)
Review Comment:
These look newish, I know there are a lot of `foldl` implementations, is this worth adding unit tests?
##########
accord-core/src/main/java/accord/primitives/Seekable.java:
##########
@@ -0,0 +1,5 @@
+package accord.primitives;
+
+public interface Seekable extends Sortable
Review Comment:
Both `Seekable` and `SortableKey` extend `Sortable`. Maybe only one should?
##########
accord-core/src/main/java/accord/topology/Topology.java:
##########
@@ -229,56 +237,92 @@ public Topology forKeys(AbstractKeys<?, ?> select, Collection<Id> nodes, Indexed
return new Topology(epoch, shards, ranges, nodeLookup, rangeSubset, newSubset);
}
- private int[] subsetForKeys(AbstractKeys<?, ?> select, IndexedPredicate<Shard> predicate)
+ private int[] subsetFor(Routables<?, ?> select, IndexedPredicate<Shard> predicate)
{
- int subsetIndex = 0;
int count = 0;
int[] newSubset = new int[Math.min(select.size(), subsetOfRanges.size())];
- for (int i = 0 ; i < select.size() ; )
+ Routables<?, ?> as = select;
+ Ranges bs = subsetOfRanges;
+ int ai = 0, bi = 0;
+ // ailim tracks which ai have been included; since there may be multiple matches
+ // we cannot increment ai to avoid missing a match with a second bi
+ int ailim = 0;
+
+ if (subsetOfRanges == ranges)
{
- // TODO: use SortedArrays.findNextIntersection
- // find the range containing the key at i
- subsetIndex = subsetOfRanges.rangeIndexForKey(subsetIndex, subsetOfRanges.size(), select.get(i));
- if (subsetIndex < 0 || subsetIndex >= subsetOfRanges.size())
- throw new IllegalArgumentException("Range not found for " + select.get(i));
- int supersetIndex = supersetIndexes[subsetIndex];
- Shard shard = shards[supersetIndex];
- if (predicate.test(subsetIndex, shard))
- newSubset[count++] = supersetIndex;
- // find the first key outside this range
- i = shard.range.nextHigherKeyIndex(select, i);
+ while (true)
+ {
+ long abi = as.findNextIntersection(ai, bs, bi);
+ if (abi < 0)
+ {
+ if (ailim < select.size())
+ throw new IllegalArgumentException("Range not found for " + select.get(ailim));
+ break;
+ }
+
+ bi = (int)(abi >>> 32);
+ if (ailim < (int)abi)
+ throw new IllegalArgumentException("Range not found for " + select.get(ailim));
+
+ if (predicate.test(bi, shards[bi]))
+ newSubset[count++] = bi;
+
+ ai = (int)abi;
+ ailim = as.findNext(ai + 1, bs.get(bi), FLOOR);
+ if (ailim < 0) ailim = -1 - ailim;
Review Comment:
What is this trying to do here?
From the docs
```
* If no entries match, similar to Arrays.binarySearch return either:
* FAST, CEIL: the entry following {@code find}, i.e. -1 - insertPos (== Arrays.binarySearch)
* FLOOR: the entry preceding {@code find}, i.e. -2 - insertPos
```
##########
accord-core/src/main/java/accord/local/CommandStore.java:
##########
@@ -91,12 +90,17 @@ public int generation()
return generation;
}
- public boolean hashIntersects(RoutingKey key)
+ public boolean hashIntersects(SortableKey key)
{
return ShardedRanges.keyIndex(key, numShards) == shardIndex;
}
- public boolean intersects(Keys keys, KeyRanges ranges)
+ public boolean hashIntersects(Sortable routable)
Review Comment:
Same thing here. Why `Sortable`? Can it be more specific?
##########
accord-core/src/main/java/accord/primitives/AbstractKeys.java:
##########
@@ -2,24 +2,22 @@
import java.util.Arrays;
import java.util.Iterator;
-import java.util.function.BiFunction;
+import java.util.function.Consumer;
+import java.util.function.Function;
import java.util.function.IntFunction;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import accord.api.RoutingKey;
-import accord.utils.IndexedFold;
-import accord.utils.IndexedFoldIntersectToLong;
-import accord.utils.IndexedFoldToLong;
-import accord.utils.IndexedPredicate;
-import accord.utils.IndexedRangeFoldToLong;
-import accord.utils.SortedArrays;
+import accord.utils.*;
import net.nicoulaj.compilecommand.annotations.Inline;
+import static accord.primitives.Sortable.Kind.Key;
+
@SuppressWarnings("rawtypes")
// TODO: check that foldl call-sites are inlined and optimised by HotSpot
-public abstract class AbstractKeys<K extends RoutingKey, KS extends AbstractKeys<K, KS>> implements Iterable<K>
+public abstract class AbstractKeys<K extends SortableKey, KS extends Sortables<K, ?>> implements Iterable<K>, Sortables<K, KS>
Review Comment:
We discussed unit tests. Most of the things that looked testable got moved to `SortedArrays` or `Sortables`.
##########
accord-core/src/main/java/accord/local/CommandStores.java:
##########
@@ -171,7 +169,7 @@ public long all()
return -1L >>> (64 - shards.length);
}
- public long shards(AbstractKeys<?, ?> keys, long minEpoch, long maxEpoch)
+ public long shards(AbstractRoutableKeys<?> keys, long minEpoch, long maxEpoch)
Review Comment:
Unused?
##########
accord-core/src/main/java/accord/local/CommandStore.java:
##########
@@ -50,9 +50,9 @@ CommandStore create(int id,
public interface RangesForEpoch
{
- KeyRanges at(long epoch);
- KeyRanges between(long fromInclusive, long toInclusive);
- KeyRanges since(long epoch);
+ Ranges at(long epoch);
+ Ranges between(long fromInclusive, long toInclusive);
+ Ranges since(long epoch);
boolean owns(long epoch, RoutingKey key);
boolean intersects(long epoch, AbstractKeys<?, ?> keys);
Review Comment:
Unused?
##########
accord-core/src/main/java/accord/local/CommandStores.java:
##########
@@ -181,17 +179,59 @@ public long shards(AbstractKeys<?, ?> keys, long minEpoch, long maxEpoch)
return accumulate;
}
- KeyRanges currentRanges()
+ public <T extends Sortable> long shards(Sortables<T, ?> keysOrRanges, long minEpoch, long maxEpoch)
+ {
+ long terminalValue = -1L >>> (32 - shards.length);
+ switch (keysOrRanges.kindOfContents())
+ {
+ default: throw new AssertionError();
+ case Key:
+ {
+ long accumulate = 0L;
+ for (int i = Math.max(0, indexForEpoch(minEpoch)), maxi = indexForEpoch(maxEpoch); i <= maxi ; ++i)
+ {
+ accumulate = Sortables.foldl((AbstractKeys<?, ?>)keysOrRanges, ranges[i], ShardedRanges::addKeyIndex, shards.length, accumulate, terminalValue);
+ }
+ return accumulate;
+ }
+
+ case Range:
+ {
+ long accumulate = 0L;
+ for (int i = Math.max(0, indexForEpoch(minEpoch)), maxi = indexForEpoch(maxEpoch); i <= maxi ; ++i)
+ {
+ // include every shard if we match a range
+ accumulate = Sortables.foldl((Ranges)keysOrRanges, ranges[i], (idx, k, p, a) -> p, terminalValue, accumulate, terminalValue);
+ }
+ return accumulate;
+ }
+ }
+ }
+
+ long shard(RoutingKey scope, long minEpoch, long maxEpoch)
Review Comment:
Unused?
##########
accord-core/src/main/java/accord/primitives/Routable.java:
##########
@@ -0,0 +1,10 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
Review Comment:
Unused import
##########
accord-core/src/main/java/accord/primitives/PartialTxn.java:
##########
@@ -8,31 +8,21 @@
public interface PartialTxn extends Txn
{
- KeyRanges covering();
+ Ranges covering();
// TODO: merge efficient merge when more than one input
PartialTxn with(PartialTxn add);
- Txn reconstitute(Route route);
- PartialTxn reconstitutePartial(PartialRoute route);
+ Txn reconstitute(FullRoute<?> route);
+ PartialTxn reconstitutePartial(PartialRoute<?> route);
- default boolean covers(KeyRanges ranges)
+ default boolean covers(Routables<?, ?> routables)
{
- return covering().contains(ranges);
- }
-
- default boolean covers(AbstractKeys<?, ?> keys)
- {
- // TODO: this distinction seems brittle
- if (keys instanceof AbstractRoute)
- return covers((AbstractRoute)keys);
-
- return covering().containsAll(keys);
- }
-
- default boolean covers(AbstractRoute route)
- {
- if (query() == null && route.contains(route.homeKey))
- return false;
- return covering().containsAll(route);
+ if (query() == null)
Review Comment:
I think this needs an explanation/comment. My take is that if this `PartialTxn` doesn't have the `query` we don't know if the `query` was never set for this `Txn` or if we just don't have it because the `Routable` doesn't contain the home key so we don't know what the home shard would know about the nullity of `query`.
##########
accord-core/src/main/java/accord/primitives/Routables.java:
##########
@@ -0,0 +1,69 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+/**
+ * Either a Route or a collection of Routable
+ */
+public interface Routables<K extends Routable, U extends Routables<K, ?>> extends Iterable<K>, Sortables<K, U>
+{
+ enum RoutablesKind
+ {
+ RoutingKeys, PartialKeyRoute, FullKeyRoute, RoutingRanges, PartialRangeRoute, FullRangeRoute;
+ public boolean isRoute()
Review Comment:
Why is `RoutingRanges` a `Route`?
##########
accord-core/src/main/java/accord/primitives/Range.java:
##########
@@ -32,17 +31,17 @@
/**
* A range of keys
*/
-public abstract class KeyRange implements Comparable<RoutingKey>
+public abstract class Range implements Comparable<SortableKey>, Routable, Seekable
Review Comment:
- [ ] For keys you seem to have quite successfully separated `Routable` and `Seekable`. `AbstractKeys` is minimally used outside of support code that doesn't care if it's `Routable` or `Seekable` so we get the static checking we want.
`Range` doesn't seem to have that. There is no `Seekable` key that can construct `Range` currently (and don't we need users to be able to express seekable key ranges?). Yet `Range` implements `Seekable`. So I went about removing `Seekable` from `Range` and everything compiled?
I assume this is a WIP until range transactions exist for users?
##########
accord-core/src/main/java/accord/primitives/Sortable.java:
##########
@@ -0,0 +1,14 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+/**
+ * Either a RoutingKey, Key or a Range
+ */
+public interface Sortable
+{
+ enum Kind { Key, Range }
+ Kind kind();
+ Routable toRoutable();
Review Comment:
So generally when trying to understand the relationship between routable and seekables, it's always possible to convert a `Seekable` to a `Routable`, and a `Routable` is always a `Routable` and I had the theory that the static typing is so consistent that we don't actually need `toRoutable` here and it only needs to be in `Seekable`.
This is after I already removed `Seekable` as an interface of `Range`. I did the move and cleaned things up and it compiles and it makes sense to me that we would only ever need to convert a `Seekable` to a `Routable` because in practice we always know if what we have is a `Seekable`s or `Routable`s.
##########
accord-core/src/main/java/accord/local/PreLoadContext.java:
##########
@@ -38,37 +39,47 @@
/**
* @return keys of the {@link CommandsForKey} objects that need to be loaded into memory before this operation is run
*/
- Iterable<Key> keys();
+ Seekables<?, ?> keys();
- static PreLoadContext contextFor(Iterable<TxnId> txnIds, Iterable<Key> keys)
+ static PreLoadContext contextFor(Iterable<TxnId> txnIds, Seekables<?, ?> keys)
{
return new PreLoadContext()
{
@Override
public Iterable<TxnId> txnIds() { return txnIds; }
@Override
- public Iterable<Key> keys() { return keys; }
+ public Seekables<?, ?> keys() { return keys; }
};
}
- static PreLoadContext contextFor(TxnId txnId, Iterable<Key> keys)
+ static PreLoadContext contextFor(TxnId txnId, Seekables<?, ?> keysOrRanges)
{
- return contextFor(Collections.singleton(txnId), keys);
+ switch (keysOrRanges.kindOfContents())
+ {
+ default: throw new AssertionError();
+ case Range: return contextFor(txnId); // TODO (soon): this won't work for actual range queries
Review Comment:
Why not store the `Seekables` so they can be loaded?
##########
accord-core/src/main/java/accord/primitives/AbstractRanges.java:
##########
@@ -0,0 +1,544 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.primitives;
+
+import accord.api.RoutingKey;
+import accord.utils.ArrayBuffers.ObjectBuffers;
+import accord.utils.Invariants;
+import accord.utils.SortedArrays;
+import com.google.common.collect.Iterators;
+
+import javax.annotation.Nonnull;
+import java.util.*;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import static accord.utils.ArrayBuffers.cachedRanges;
+import static accord.utils.SortedArrays.Search.FAST;
+import static accord.utils.SortedArrays.swapHighLow32b;
+
+public abstract class AbstractRanges<RS extends Sortables<Range, ?>> implements Iterable<Range>, Sortables<Range, RS>
+{
+ static final Range[] NO_RANGES = new Range[0];
+
+ final Range[] ranges;
+
+ AbstractRanges(@Nonnull Range[] ranges)
+ {
+ this.ranges = Invariants.nonNull(ranges);
+ }
+
+ public int indexOf(SortableKey key)
+ {
+ return SortedArrays.binarySearch(ranges, 0, ranges.length, key, (k, r) -> -r.compareTo(k), FAST);
+ }
+
+ public int indexOf(Range find)
+ {
+ return SortedArrays.binarySearch(ranges, 0, ranges.length, find, Range::compareIntersecting, FAST);
+ }
+
+ public boolean contains(SortableKey key)
+ {
+ return indexOf(key) >= 0;
+ }
+
+ public boolean containsAll(Sortables<?, ?> that)
+ {
+ switch (that.kindOfContents())
+ {
+ default: throw new AssertionError();
+ case Key: return containsAll((AbstractKeys<?, ?>) that);
+ case Range: return containsAll((AbstractRanges<?>) that);
+ }
+ }
+
+ /**
+ * @return true iff {@code that} is fully contained within {@code this}
+ */
+ public boolean containsAll(AbstractKeys<?, ?> that)
+ {
+ if (this.isEmpty()) return that.isEmpty();
+ if (that.isEmpty()) return true;
+ return Sortables.rangeFoldl(that, this, (from, to, p, v) -> v + (to - from), 0, 0, 0) == that.size();
+ }
+
+ /**
+ * @return true iff {@code that} is a subset of {@code this}
+ */
+ public boolean containsAll(AbstractRanges<?> that)
+ {
+ if (this.isEmpty()) return that.isEmpty();
+ if (that.isEmpty()) return true;
+ return ((int) supersetLinearMerge(this.ranges, that.ranges)) == that.size();
+ }
+
+ public int size()
+ {
+ return ranges.length;
+ }
+
+ @Override
+ public final Routable.Kind kindOfContents()
+ {
+ return Routable.Kind.Range;
+ }
+
+ @Override
+ public final Range get(int i)
+ {
+ return ranges[i];
+ }
+
+ @Override
+ public final boolean isEmpty()
+ {
+ return size() == 0;
+ }
+
+ public final boolean intersects(AbstractKeys<?, ?> keys)
+ {
+ return findNextIntersection(0, keys, 0) >= 0;
+ }
+
+ public final <K extends SortableKey> boolean intersects(AbstractKeys<K, ?> keys, Predicate<? super K> matches)
+ {
+ int ri = 0, ki = 0;
+ while (true)
+ {
+ long rki = findNextIntersection(ri, keys, ki);
+ if (rki < 0)
+ return false;
+
+ ri = (int) (rki);
+ ki = (int) (rki >>> 32);
+
+ if (matches.test(keys.get(ki)))
+ return true;
+
+ ki++;
+ }
+ }
+
+ public boolean intersects(AbstractRanges<?> that)
+ {
+ return SortedArrays.findNextIntersection(this.ranges, 0, that.ranges, 0, Range::compareIntersecting) >= 0;
+ }
+
+ public boolean intersects(Range that)
+ {
+ return SortedArrays.binarySearch(ranges, 0, ranges.length, that, Range::compareIntersecting, SortedArrays.Search.FAST) >= 0;
+ }
+
+ // returns ri in low 32 bits, ki in top, or -1 if no match found
+ public long findNextIntersection(int ri, AbstractKeys<?, ?> keys, int ki)
+ {
+ return swapHighLow32b(SortedArrays.findNextIntersectionWithMultipleMatches(keys.keys, ki, ranges, ri));
+ }
+
+ // returns ki in bottom 32 bits, ri in top, or -1 if no match found
+ public long findNextIntersection(int thisi, AbstractRanges<?> that, int thati)
+ {
+ return SortedArrays.findNextIntersectionWithMultipleMatches(ranges, thisi, that.ranges, thati, Range::compareIntersecting, Range::compareIntersecting);
+ }
+
+ @Override
+ public final long findNextIntersection(int thisIndex, Sortables<Range, ?> with, int withIndex)
+ {
+ return findNextIntersection(thisIndex, (AbstractRanges<?>) with, withIndex);
+ }
+
+ @Override
+ public int findNext(int thisIndex, Range find, SortedArrays.Search search)
+ {
+ return SortedArrays.exponentialSearch(ranges, thisIndex, size(), find, Range::compareIntersecting, search);
+ }
+
+ @Override
+ public FullRoute<Range> toRoute(RoutingKey homeKey)
+ {
+ return new FullRangeRoute(homeKey, ranges);
Review Comment:
Doesn't seem very safe since this may be a partial route? Similar unsafety on the key side. We seem to only do this once when a `Txn` is first started.
##########
accord-core/src/main/java/accord/primitives/Sortables.java:
##########
@@ -0,0 +1,257 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+import accord.utils.IndexedFold;
+import accord.utils.IndexedFoldToLong;
+import accord.utils.IndexedRangeFoldToLong;
+import accord.utils.SortedArrays;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import static accord.utils.SortedArrays.Search.FLOOR;
+
+/**
+ * Either a Route or a collection of Sortable
+ */
+public interface Sortables<K extends Sortable, U extends Sortables<K, ?>> extends Iterable<K>
+{
+ int indexOf(K item);
+ K get(int i);
+ int size();
+
+ boolean isEmpty();
+ boolean intersects(AbstractRanges<?> ranges);
+ boolean contains(SortableKey key);
+ boolean containsAll(Sortables<?, ?> keysOrRanges);
+
+ U slice(Ranges ranges);
+ Sortables<K, U> union(U with);
+
+ /**
+ * @return an arbitrary key that relates to this Findable - this may or may not be contained by this Findable,
Review Comment:
`Findable` isn't a thing anymore?
##########
accord-core/src/main/java/accord/primitives/Sortable.java:
##########
@@ -0,0 +1,14 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+/**
+ * Either a RoutingKey, Key or a Range
+ */
+public interface Sortable
+{
+ enum Kind { Key, Range }
+ Kind kind();
+ Routable toRoutable();
+ RoutingKey someIntersectingRoutingKey();
Review Comment:
This doesn't necessarily seem like it belongs in `Sortable`, but I tried to find a way to move it or maybe have different versions for `Seekable` and `Sortable` with limited success.
##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -301,28 +302,27 @@ public AcceptOutcome accept(SafeCommandStore safeStore, Ballot ballot, PartialRo
}
TxnId txnId = txnId();
- KeyRanges coordinateRanges = coordinateRanges(safeStore);
- KeyRanges executeRanges = txnId.epoch == executeAt.epoch ? coordinateRanges : safeStore.ranges().at(executeAt.epoch);
- KeyRanges acceptRanges = txnId.epoch == executeAt.epoch ? coordinateRanges : safeStore.ranges().between(txnId.epoch, executeAt.epoch);
+ Ranges coordinateRanges = coordinateRanges(safeStore);
+// Ranges executeRanges = txnId.epoch == executeAt.epoch ? coordinateRanges : safeStore.ranges().at(executeAt.epoch);
Review Comment:
Remove `executeRanges`? Why don't we use the ranges at the `executeAt.epoch` anymore?
##########
accord-core/src/main/java/accord/coordinate/FindRoute.java:
##########
@@ -20,26 +18,31 @@ public class FindRoute extends CheckShards
{
public static class Result
{
- public final Route route;
+ public final FullRoute<?> route;
public final Timestamp executeAt;
- public Result(Route route, Timestamp executeAt)
+ public Result(FullRoute<?> route, Timestamp executeAt)
{
this.route = route;
this.executeAt = executeAt;
}
public Result(CheckStatusOk ok)
{
- this.route = (Route)ok.route;
+ this.route = Route.castToFullRoute(ok.route);
this.executeAt = ok.saveStatus.status.compareTo(Status.PreCommitted) >= 0 ? ok.executeAt : null;
}
}
final BiConsumer<Result, Throwable> callback;
FindRoute(Node node, TxnId txnId, RoutingKey homeKey, BiConsumer<Result, Throwable> callback)
{
- super(node, txnId, RoutingKeys.of(homeKey), txnId.epoch, IncludeInfo.Route);
+ this(node, txnId, RoutingKeys.of(homeKey), callback);
+ }
+
+ private FindRoute(Node node, TxnId txnId, RoutingKeys homeKey, BiConsumer<Result, Throwable> callback)
Review Comment:
Why have the additional constructor?
##########
accord-core/src/main/java/accord/local/CommandStores.java:
##########
@@ -181,17 +179,59 @@ public long shards(AbstractKeys<?, ?> keys, long minEpoch, long maxEpoch)
return accumulate;
}
- KeyRanges currentRanges()
+ public <T extends Sortable> long shards(Sortables<T, ?> keysOrRanges, long minEpoch, long maxEpoch)
Review Comment:
A lot more `Sortable` is it possible to be more specific like `Routable`?
##########
accord-core/src/main/java/accord/primitives/Route.java:
##########
@@ -3,50 +3,99 @@
import accord.api.RoutingKey;
import com.google.common.base.Preconditions;
-public class Route extends AbstractRoute
+import javax.annotation.Nullable;
+
+public interface Route<K extends Routable> extends Routables<K, Route<K>>
{
- public static class SerializationSupport
+ RoutingKey homeKey();
+
+ default boolean isRoute() { return true; }
+ boolean covers(Ranges ranges);
+ boolean intersects(AbstractRanges<?> ranges);
+ Route<K> union(Route<K> route);
+ PartialRoute<K> slice(Ranges ranges);
+ PartialRoute<K> sliceStrict(Ranges ranges);
+
+ /**
+ * @return a Routable that includes every shard we know of, not just those we contact
+ * (i.e., includes the homeKey if not already included)
+ */
+ Routables<K, ?> toMaximalRoutables();
+
+ // this method exists solely to circumvent JDK bug with testing and casting interfaces
+ static boolean isFullRoute(@Nullable Routables<?, ?> routables) { return routables != null && routables.kind().isFullRoute(); }
+
+ // this method exists solely to circumvent JDK bug with testing and casting interfaces
+ static boolean isRoute(@Nullable Routables<?, ?> routables) { return routables != null && routables.kind().isRoute(); }
+
+ // this method exists solely to circumvent JDK bug with testing and casting interfaces
+ static FullRoute<?> castToFullRoute(@Nullable Routables<?, ?> routables)
{
- public static Route create(RoutingKey homeKey, RoutingKey[] keys)
+ if (routables == null)
+ return null;
+
+ switch (routables.kindOfContents())
{
- return new Route(homeKey, keys);
+ default: throw new AssertionError();
+ case Key: return (FullKeyRoute) routables;
+ case Range: return (FullRangeRoute) routables;
}
}
- public Route(RoutingKey homeKey, RoutingKey[] keys)
+ static Route<?> castToRoute(@Nullable Routables<?, ?> routables)
{
- super(keys, homeKey);
- }
+ if (routables == null)
+ return null;
- @Override
- public boolean covers(KeyRanges ranges)
- {
- Preconditions.checkNotNull(ranges);
- return true;
+ switch (routables.kindOfContents())
+ {
+ default: throw new AssertionError();
+ case Key: return (KeyRoute) routables;
+ case Range: return (RangeRoute) routables;
+ }
}
- @Override
- public AbstractRoute union(AbstractRoute that)
+ // this method exists solely to circumvent JDK bug with testing and casting interfaces
+ static Route<?> tryCastToRoute(@Nullable Routables<?, ?> routables)
{
- Preconditions.checkNotNull(that);
- return this;
- }
+ if (routables == null)
+ return null;
- @Override
- public PartialRoute slice(KeyRanges ranges)
- {
- return new PartialRoute(ranges, homeKey, slice(ranges, RoutingKey[]::new));
+ switch (routables.kind())
+ {
+ default: throw new AssertionError();
+ case RoutingKeys:
+ case RoutingRanges:
+ return null;
+ case PartialKeyRoute:
+ return (PartialKeyRoute) routables;
+ case PartialRangeRoute:
+ return (PartialRangeRoute) routables;
+ case FullKeyRoute:
+ return (FullKeyRoute) routables;
+ case FullRangeRoute:
+ return (FullRangeRoute) routables;
+ }
}
- @Override
- public PartialRoute sliceStrict(KeyRanges ranges)
+ // this method exists solely to circumvent JDK bug with testing and casting interfaces
+ static PartialRoute<?> castToPartialRoute(@Nullable Routables<?, ?> routables)
Review Comment:
Unused?
##########
accord-core/src/main/java/accord/topology/Topology.java:
##########
@@ -229,56 +237,92 @@ public Topology forKeys(AbstractKeys<?, ?> select, Collection<Id> nodes, Indexed
return new Topology(epoch, shards, ranges, nodeLookup, rangeSubset, newSubset);
}
- private int[] subsetForKeys(AbstractKeys<?, ?> select, IndexedPredicate<Shard> predicate)
+ private int[] subsetFor(Routables<?, ?> select, IndexedPredicate<Shard> predicate)
Review Comment:
Is this worth unit testing explicitly? Spend some time understanding it and it make sense.
##########
accord-core/src/main/java/accord/local/CommandStore.java:
##########
@@ -91,12 +90,17 @@ public int generation()
return generation;
}
- public boolean hashIntersects(RoutingKey key)
+ public boolean hashIntersects(SortableKey key)
{
return ShardedRanges.keyIndex(key, numShards) == shardIndex;
}
- public boolean intersects(Keys keys, KeyRanges ranges)
+ public boolean hashIntersects(Sortable routable)
+ {
+ return routable instanceof Range || hashIntersects((SortableKey) routable);
+ }
+
+ public boolean intersects(Keys keys, Ranges ranges)
Review Comment:
When do we have `Ranges` that are ranges of `Seekables` no `Routables` (and thus work with `Keys`? I checked and this seems unused and I think is also wrong.
Also maybe `AbstractKeys.any` shouldn't compile with this attempted usage?
##########
accord-core/src/main/java/accord/local/CommandStores.java:
##########
@@ -181,17 +179,59 @@ public long shards(AbstractKeys<?, ?> keys, long minEpoch, long maxEpoch)
return accumulate;
}
- KeyRanges currentRanges()
+ public <T extends Sortable> long shards(Sortables<T, ?> keysOrRanges, long minEpoch, long maxEpoch)
+ {
+ long terminalValue = -1L >>> (32 - shards.length);
+ switch (keysOrRanges.kindOfContents())
+ {
+ default: throw new AssertionError();
+ case Key:
+ {
+ long accumulate = 0L;
+ for (int i = Math.max(0, indexForEpoch(minEpoch)), maxi = indexForEpoch(maxEpoch); i <= maxi ; ++i)
+ {
+ accumulate = Sortables.foldl((AbstractKeys<?, ?>)keysOrRanges, ranges[i], ShardedRanges::addKeyIndex, shards.length, accumulate, terminalValue);
+ }
+ return accumulate;
+ }
+
+ case Range:
+ {
+ long accumulate = 0L;
+ for (int i = Math.max(0, indexForEpoch(minEpoch)), maxi = indexForEpoch(maxEpoch); i <= maxi ; ++i)
+ {
+ // include every shard if we match a range
+ accumulate = Sortables.foldl((Ranges)keysOrRanges, ranges[i], (idx, k, p, a) -> p, terminalValue, accumulate, terminalValue);
+ }
+ return accumulate;
+ }
+ }
+ }
+
+ long shard(RoutingKey scope, long minEpoch, long maxEpoch)
+ {
+ long result = 0L;
+ for (int i = Math.max(0, indexForEpoch(minEpoch)), maxi = indexForEpoch(maxEpoch); i <= maxi ; ++i)
+ {
+ int index = ranges[i].indexOf(scope);
+ if (index < 0)
+ continue;
+ result = addKeyIndex(0, scope, shards.length, result);
+ }
+ return result;
+ }
+
+ Ranges currentRanges()
{
return ranges[ranges.length - 1];
}
- static long keyIndex(RoutingKey key, long numShards)
+ static long keyIndex(SortableKey key, long numShards)
Review Comment:
`RoutableKey`?
##########
accord-core/src/main/java/accord/local/CommandStore.java:
##########
@@ -91,12 +90,17 @@ public int generation()
return generation;
}
- public boolean hashIntersects(RoutingKey key)
+ public boolean hashIntersects(SortableKey key)
Review Comment:
Sortable is non-specific? This has to be either a Seekable or a Routable right? If it's the wrong kind then it won't intersect correctly?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org
For additional commands, e-mail: pr-help@cassandra.apache.org