This is an automated email from the ASF dual-hosted git repository. dcapwell pushed a commit to branch CASSANDRA-18804 in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
commit ee0fcf21e4f6a7d6db4e7b3e94d9878493f07e2c Author: David Capwell <[email protected]> AuthorDate: Tue Nov 28 14:19:26 2023 -0800 make it so we can compute prefix keyx within ranges --- .../test/java/accord/impl/PrefixedIntHashKey.java | 25 ++++--- .../src/test/java/accord/local/CommandsTest.java | 21 ++---- .../java/accord/primitives/AbstractRangesTest.java | 72 +++----------------- .../src/test/java/accord/utils/AccordGens.java | 79 +++++++++++++++++++++- .../src/test/java/accord/utils/CRCUtils.java | 51 ++++++++++++++ .../src/test/java/accord/utils/CRCUtilsTest.java | 40 +++++++++++ 6 files changed, 194 insertions(+), 94 deletions(-) diff --git a/accord-core/src/test/java/accord/impl/PrefixedIntHashKey.java b/accord-core/src/test/java/accord/impl/PrefixedIntHashKey.java index 28618f60..2cf1b504 100644 --- a/accord-core/src/test/java/accord/impl/PrefixedIntHashKey.java +++ b/accord-core/src/test/java/accord/impl/PrefixedIntHashKey.java @@ -18,22 +18,24 @@ package accord.impl; +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; +import javax.annotation.Nonnull; + import accord.api.RoutingKey; import accord.local.ShardDistributor; import accord.primitives.Ranges; import accord.primitives.RoutableKey; +import accord.utils.CRCUtils; import accord.utils.Invariants; -import javax.annotation.Nonnull; -import java.util.ArrayList; -import java.util.List; -import java.util.Objects; -import java.util.zip.CRC32; - import static accord.utils.Utils.toArray; public class PrefixedIntHashKey implements RoutableKey { + public static final int MIN_KEY = Integer.MIN_VALUE + 1; + public static class Splitter implements ShardDistributor.EvenSplit.Splitter<Long> { @Override @@ -180,7 +182,7 @@ public class PrefixedIntHashKey implements RoutableKey else { if (key == Integer.MIN_VALUE) - throw new IllegalArgumentException(); + throw new IllegalArgumentException("Key was int MIN_VALUE but not for hash"); this.key = key; this.hash = hash(key); } @@ -199,6 +201,8 @@ public class PrefixedIntHashKey implements RoutableKey public static accord.primitives.Range[] ranges(int prefix, int count) { List<accord.primitives.Range> result = new ArrayList<>(count); + // The hash is crc32, which is 32 bits, but to keep this logic simple shrink the domain to 16 bits. + // Since this method is only for testing, changing this to 32 bits in the future is fine. long delta = 0xffff / count; long start = 0; Hash prev = new Hash(prefix, (int) start); @@ -246,12 +250,7 @@ public class PrefixedIntHashKey implements RoutableKey static int hash(int key) { - CRC32 crc32c = new CRC32(); - crc32c.update(key); - crc32c.update(key >> 8); - crc32c.update(key >> 16); - crc32c.update(key >> 24); - return (int) crc32c.getValue() & 0xffff; + return CRCUtils.crc32LittleEnding(key); } @Override diff --git a/accord-core/src/test/java/accord/local/CommandsTest.java b/accord-core/src/test/java/accord/local/CommandsTest.java index 967ceecc..f91003e8 100644 --- a/accord-core/src/test/java/accord/local/CommandsTest.java +++ b/accord-core/src/test/java/accord/local/CommandsTest.java @@ -32,12 +32,10 @@ import accord.impl.basic.RandomDelayQueue; import accord.impl.basic.SimulatedDelayedExecutorService; import accord.impl.list.ListAgent; import accord.messages.MessageType; -import accord.messages.PreAccept; import accord.messages.ReplyContext; import accord.messages.Request; import accord.primitives.Timestamp; import accord.topology.TopologyUtils; -import accord.primitives.FullRoute; import accord.primitives.Keys; import accord.primitives.Range; import accord.primitives.Ranges; @@ -65,7 +63,6 @@ import java.util.function.LongSupplier; import java.util.function.Supplier; import static accord.Utils.listWriteTxn; -import static accord.Utils.writeTxn; import static accord.utils.Property.qt; import static accord.utils.Utils.addAll; @@ -77,7 +74,7 @@ class CommandsTest void addAndRemoveRangesValidate() { Gen<List<Node.Id>> nodeGen = Gens.lists(AccordGens.nodes()).ofSizeBetween(1, 100); - qt().withSeed(-8991099031722289106L).check(rs -> { + qt().check(rs -> { List<Node.Id> nodes = nodeGen.next(rs); if (!nodes.contains(N1)) nodes.add(N1); @@ -86,8 +83,7 @@ class CommandsTest Range[] prefix0 = PrefixedIntHashKey.ranges(0, nodes.size()); Range[] prefix1 = PrefixedIntHashKey.ranges(1, nodes.size()); Range[] allRanges = addAll(prefix0, prefix1); -// boolean add = rs.nextBoolean(); - boolean add = false; + boolean add = rs.nextBoolean(); Topology initialTopology = TopologyUtils.topology(1, nodes, Ranges.of(add ? prefix0 : allRanges), rf); Topology updatedTopology = TopologyUtils.topology(2, nodes, Ranges.of(add ? allRanges : prefix0), rf); @@ -98,19 +94,10 @@ class CommandsTest public void process(Node node, Node.Id from, ReplyContext replyContext) { Ranges localRange = node.topology().localRangesForEpoch(initialTopology.epoch()); - int prefix; if (!add) - { - // use the removed range - localRange = Ranges.ofSortedAndDeoverlapped(prefix1); - prefix = 1; - } - else - { - prefix = rs.pickInt(0, 1); - } + localRange = Ranges.ofSortedAndDeoverlapped(prefix1); // make sure to use the range removed - Gen<Key> keyGen = AccordGens.prefixedIntHashKey(ignore -> prefix).filter(localRange::contains); + Gen<Key> keyGen = AccordGens.prefixedIntHashKeyInsideRanges(localRange); Keys keys = Keys.of(Gens.lists(keyGen).unique().ofSizeBetween(1, 10).next(rs)); Txn txn = listWriteTxn(from, keys); diff --git a/accord-core/src/test/java/accord/primitives/AbstractRangesTest.java b/accord-core/src/test/java/accord/primitives/AbstractRangesTest.java index b7bc1fb6..82f3d78e 100644 --- a/accord-core/src/test/java/accord/primitives/AbstractRangesTest.java +++ b/accord-core/src/test/java/accord/primitives/AbstractRangesTest.java @@ -18,8 +18,6 @@ package accord.primitives; -import java.util.TreeSet; - import accord.api.Key; import accord.impl.IntKey; import accord.utils.AccordGens; @@ -31,7 +29,6 @@ import org.assertj.core.api.Assertions; import org.junit.jupiter.api.Test; import javax.annotation.Nonnull; -import javax.annotation.Nullable; import static accord.utils.Property.qt; import static org.assertj.core.api.Assertions.assertThat; @@ -69,69 +66,20 @@ class AbstractRangesTest private Keys intKeyInside(RandomSource rs, accord.primitives.Ranges ranges) { - int size = rs.nextInt(1, 10); - TreeSet<Key> keys = new TreeSet<>(); - for (int i = 0; i < size; i++) - { - Range range = ranges.get(rs.nextInt(0, ranges.size())); - // retries - for (int j = 0; j < 10 && !keys.add(intKeyInside(rs, range)); j++) {} - } - return Keys.of(keys); - } - - private Key intKeyInside(RandomSource rs, Range range) - { - int start = intKey(range.start()); - int end = intKey(range.end()); - // end inclusive, so +1 the result to include end and exclude start - return IntKey.key(rs.nextInt(start, end) + 1); - } - - private static int intKey(RoutableKey key) - { - return ((IntKey.Routing) key).key; + return Gens.lists(AccordGens.intKeysInsideRanges(ranges)) + .unique() + .ofSizeBetween(1, 10) + .map(l -> Keys.ofUnique(l.toArray(Key[]::new))) + .next(rs); } private Keys intKeyOutside(RandomSource rs, accord.primitives.Ranges ranges) { - int size = rs.nextInt(1, 10); - TreeSet<Key> keys = new TreeSet<>(); - for (int i = 0; i < size; i++) - { - int index = rs.nextInt(0, ranges.size()); - Range first = index == 0 ? null : ranges.get(index - 1); - Range second = ranges.get(index); - // retries - for (int j = 0; j < 10; j++) - { - Key key = intKeyOutside(rs, first, second); - if (key == null) - continue; - if (keys.add(key)) - break; - } - } - return Keys.of(keys); - } - - private Key intKeyOutside(RandomSource rs, @Nullable Range first, Range second) - { - int start; - int end; - if (first == null) - { - start = Integer.MIN_VALUE; - end = intKey(second.start()); // start is not inclusive, so can use - } - else - { - start = intKey(first.end()) + 1; // end is inclusive, so +1 to skip - end = intKey(second.start()); // start is not inclusive, so can use - } - if (start == end) - return null; - return IntKey.key(rs.nextInt(start, end + 1)); + return Gens.lists(AccordGens.intKeysOutsideRanges(ranges)) + .unique() + .ofSizeBetween(1, 10) + .map(l -> Keys.ofUnique(l.toArray(Key[]::new))) + .next(rs); } private static Range range(Object prefix, int start, int end) diff --git a/accord-core/src/test/java/accord/utils/AccordGens.java b/accord-core/src/test/java/accord/utils/AccordGens.java index 7dc7c798..c296d07c 100644 --- a/accord-core/src/test/java/accord/utils/AccordGens.java +++ b/accord-core/src/test/java/accord/utils/AccordGens.java @@ -27,6 +27,8 @@ import java.util.Objects; import java.util.Set; import java.util.function.BiFunction; +import javax.annotation.Nullable; + import accord.api.Key; import accord.api.RoutingKey; import accord.impl.IntHashKey; @@ -39,6 +41,7 @@ import accord.primitives.Range; import accord.primitives.RangeDeps; import accord.primitives.Ranges; import accord.primitives.Routable; +import accord.primitives.RoutableKey; import accord.primitives.Timestamp; import accord.primitives.Txn; import accord.primitives.TxnId; @@ -82,6 +85,62 @@ public class AccordGens return rs -> new IntKey.Raw(rs.nextInt()); } + public static Gen<Key> intKeysInsideRanges(Ranges ranges) + { + return rs -> { + Range range = ranges.get(rs.nextInt(0, ranges.size())); + int start = intKey(range.start()); + int end = intKey(range.end()); + // end inclusive, so +1 the result to include end and exclude start + return IntKey.key(rs.nextInt(start, end) + 1); + }; + } + + public static Gen<Key> intKeysOutsideRanges(Ranges ranges) + { + return rs -> { + for (int i = 0; i < 10; i++) + { + int index = rs.nextInt(0, ranges.size()); + Range first = index == 0 ? null : ranges.get(index - 1); + Range second = ranges.get(index); + // retries + for (int j = 0; j < 10; j++) + { + Key key = intKeyOutside(rs, first, second); + if (key == null) + continue; + return key; + } + } + throw new AssertionError("Unable to find keys within the range " + ranges); + }; + } + + private static Key intKeyOutside(RandomSource rs, @Nullable Range first, Range second) + { + int start; + int end; + if (first == null) + { + start = Integer.MIN_VALUE; + end = intKey(second.start()); // start is not inclusive, so can use + } + else + { + start = intKey(first.end()) + 1; // end is inclusive, so +1 to skip + end = intKey(second.start()); // start is not inclusive, so can use + } + if (start == end) + return null; + return IntKey.key(rs.nextInt(start, end + 1)); + } + + private static int intKey(RoutableKey key) + { + return ((IntKey.Routing) key).key; + } + public static Gen<IntKey.Routing> intRoutingKey() { return rs -> IntKey.routing(rs.nextInt()); @@ -94,12 +153,12 @@ public class AccordGens public static Gen<Key> prefixedIntHashKey() { - return prefixedIntHashKey(RandomSource::nextInt, RandomSource::nextInt); + return prefixedIntHashKey(RandomSource::nextInt, rs -> rs.nextInt(PrefixedIntHashKey.MIN_KEY, Integer.MAX_VALUE)); } public static Gen<Key> prefixedIntHashKey(Gen.IntGen prefixGen) { - return prefixedIntHashKey(prefixGen, RandomSource::nextInt); + return prefixedIntHashKey(prefixGen, rs -> rs.nextInt(PrefixedIntHashKey.MIN_KEY, Integer.MAX_VALUE)); } public static Gen<Key> prefixedIntHashKey(Gen.IntGen prefixGen, Gen.IntGen valueGen) @@ -107,6 +166,22 @@ public class AccordGens return rs -> PrefixedIntHashKey.key(prefixGen.nextInt(rs), valueGen.nextInt(rs)); } + public static Gen<Key> prefixedIntHashKeyInsideRanges(Ranges ranges) + { + return rs -> { + Range range = ranges.get(rs.nextInt(0, ranges.size())); + PrefixedIntHashKey start = (PrefixedIntHashKey) range.start(); + PrefixedIntHashKey end = (PrefixedIntHashKey) range.end(); + // end inclusive, so +1 the result to include end and exclude start + int hash = rs.nextInt(start.hash, end.hash) + 1; + int key = CRCUtils.reverseCRC32LittleEnding(hash); + PrefixedIntHashKey.Key ret = PrefixedIntHashKey.key(start.prefix, key); + // we have tests to make sure this doesn't fail... just a safety check + assert ret.hash == hash; + return ret; + }; + } + public static Gen<KeyDeps> keyDeps(Gen<? extends Key> keyGen) { return keyDeps(keyGen, txnIds()); diff --git a/accord-core/src/test/java/accord/utils/CRCUtils.java b/accord-core/src/test/java/accord/utils/CRCUtils.java new file mode 100644 index 00000000..d0a5179f --- /dev/null +++ b/accord-core/src/test/java/accord/utils/CRCUtils.java @@ -0,0 +1,51 @@ +/* + * 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.utils; + +import java.util.zip.CRC32; + +public class CRCUtils +{ + private static final int POLY = 0xedb88320; + + private CRCUtils() {} + + public static int crc32LittleEnding(int key) + { + CRC32 crc32c = new CRC32(); + crc32c.update(key); + crc32c.update(key >> 8); + crc32c.update(key >> 16); + crc32c.update(key >> 24); + return (int) crc32c.getValue(); + } + + public static int reverseCRC32LittleEnding(int c) + { + for (int i = 0; i < 32; i++) + { + c = (c >>> 31) == 0 ? + (c ^ POLY) << 1 | 1 + : c << 1; + } + // flip bits + c = c ^ 0xffffffff; + return c; + } +} diff --git a/accord-core/src/test/java/accord/utils/CRCUtilsTest.java b/accord-core/src/test/java/accord/utils/CRCUtilsTest.java new file mode 100644 index 00000000..1ac9fdc9 --- /dev/null +++ b/accord-core/src/test/java/accord/utils/CRCUtilsTest.java @@ -0,0 +1,40 @@ +/* + * 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.utils; + +import org.junit.jupiter.api.Test; + +import org.assertj.core.api.Assertions; + +import static accord.utils.CRCUtils.crc32LittleEnding; +import static accord.utils.CRCUtils.reverseCRC32LittleEnding; +import static accord.utils.Property.qt; + +class CRCUtilsTest +{ + @Test + void backAndForth() + { + qt().withExamples(100_000).forAll(Gens.ints().all()).check(key -> { + int hash = crc32LittleEnding(key); + int unhash = reverseCRC32LittleEnding(hash); + Assertions.assertThat(unhash).isEqualTo(key); + }); + } +} \ No newline at end of file --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
