Repository: cassandra Updated Branches: refs/heads/cassandra-3.0 ce8c9b559 -> ab0adf9f9 refs/heads/cassandra-3.11 0bc45aa46 -> 2a24acfa9 refs/heads/trunk 289f6b157 -> 6b4c8a973
AssertionError prepending to a list patch by jasobrown, reviewed by Sam Tunnicliffe for CASSANDRA-13149 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/ab0adf9f Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/ab0adf9f Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/ab0adf9f Branch: refs/heads/cassandra-3.0 Commit: ab0adf9f9bc72074a02025bdecd9479f790d6463 Parents: ce8c9b5 Author: Jason Brown <jasedbr...@gmail.com> Authored: Tue Sep 12 17:05:13 2017 -0700 Committer: Jason Brown <jasedbr...@gmail.com> Committed: Fri Sep 29 05:18:54 2017 -0700 ---------------------------------------------------------------------- CHANGES.txt | 1 + src/java/org/apache/cassandra/cql3/Lists.java | 76 +++++++-- .../org/apache/cassandra/cql3/ListsTest.java | 166 +++++++++++++++++++ 3 files changed, 226 insertions(+), 17 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/ab0adf9f/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 7745e8c..a1f49cd 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 3.0.15 + * AssertionError prepending to a list (CASSANDRA-13149) * Fix support for SuperColumn tables (CASSANDRA-12373) * Handle limit correctly on tables with strict liveness (CASSANDRA-13883) * Fix missing original update in TriggerExecutor (CASSANDRA-13894) http://git-wip-us.apache.org/repos/asf/cassandra/blob/ab0adf9f/src/java/org/apache/cassandra/cql3/Lists.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/cql3/Lists.java b/src/java/org/apache/cassandra/cql3/Lists.java index 559cf3f..065f74a 100644 --- a/src/java/org/apache/cassandra/cql3/Lists.java +++ b/src/java/org/apache/cassandra/cql3/Lists.java @@ -25,6 +25,8 @@ import java.util.List; import java.util.concurrent.atomic.AtomicReference; import java.util.stream.Collectors; +import com.google.common.annotations.VisibleForTesting; + import org.apache.cassandra.config.ColumnDefinition; import org.apache.cassandra.cql3.functions.Function; import org.apache.cassandra.db.*; @@ -243,18 +245,17 @@ public abstract class Lists } } - /* + /** * For prepend, we need to be able to generate unique but decreasing time - * UUID, which is a bit challenging. To do that, given a time in milliseconds, - * we adds a number representing the 100-nanoseconds precision and make sure - * that within the same millisecond, that number is always decreasing. We - * do rely on the fact that the user will only provide decreasing - * milliseconds timestamp for that purpose. + * UUIDs, which is a bit challenging. To do that, given a time in milliseconds, + * we add a number representing the 100-nanoseconds precision and make sure + * that within the same millisecond, that number is always decreasing. */ - private static class PrecisionTime + static class PrecisionTime { // Our reference time (1 jan 2010, 00:00:00) in milliseconds. private static final long REFERENCE_TIME = 1262304000000L; + static final int MAX_NANOS = 9999; private static final AtomicReference<PrecisionTime> last = new AtomicReference<>(new PrecisionTime(Long.MAX_VALUE, 0)); public final long millis; @@ -266,21 +267,52 @@ public abstract class Lists this.nanos = nanos; } - static PrecisionTime getNext(long millis) + static PrecisionTime getNext(long millis, int count) { + if (count == 0) + return last.get(); + while (true) { PrecisionTime current = last.get(); - assert millis <= current.millis; - PrecisionTime next = millis < current.millis - ? new PrecisionTime(millis, 9999) - : new PrecisionTime(millis, Math.max(0, current.nanos - 1)); + final PrecisionTime next; + if (millis < current.millis) + { + next = new PrecisionTime(millis, MAX_NANOS - count); + } + else + { + // in addition to being at the same millisecond, we handle the unexpected case of the millis parameter + // being in the past. That could happen if the System.currentTimeMillis() not operating montonically + // or if one thread is just a really big loser in the compareAndSet game of life. + long millisToUse = millis <= current.millis ? millis : current.millis; + + // if we will go below zero on the nanos, decrement the millis by one + final int nanosToUse; + if (current.nanos - count >= 0) + { + nanosToUse = current.nanos - count; + } + else + { + nanosToUse = MAX_NANOS - count; + millisToUse -= 1; + } + + next = new PrecisionTime(millisToUse, nanosToUse); + } if (last.compareAndSet(current, next)) return next; } } + + @VisibleForTesting + static void set(long millis, int nanos) + { + last.set(new PrecisionTime(millis, nanos)); + } } public static class Setter extends Operation @@ -422,13 +454,23 @@ public abstract class Lists if (value == null || value == UNSET_VALUE) return; - long time = PrecisionTime.REFERENCE_TIME - (System.currentTimeMillis() - PrecisionTime.REFERENCE_TIME); - List<ByteBuffer> toAdd = ((Value) value).elements; - for (int i = toAdd.size() - 1; i >= 0; i--) + final int totalCount = toAdd.size(); + + // we have to obey MAX_NANOS per batch - in the unlikely event a client has decided to prepend a list with + // an insane number of entries. + PrecisionTime pt = null; + int remainingInBatch = 0; + for (int i = totalCount - 1; i >= 0; i--) { - PrecisionTime pt = PrecisionTime.getNext(time); - ByteBuffer uuid = ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(pt.millis, pt.nanos)); + if (remainingInBatch == 0) + { + long time = PrecisionTime.REFERENCE_TIME - (System.currentTimeMillis() - PrecisionTime.REFERENCE_TIME); + remainingInBatch = Math.min(PrecisionTime.MAX_NANOS, i) + 1; + pt = PrecisionTime.getNext(time, remainingInBatch); + } + + ByteBuffer uuid = ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(pt.millis, (pt.nanos + remainingInBatch--))); params.addCell(column, CellPath.create(uuid), toAdd.get(i)); } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/ab0adf9f/test/unit/org/apache/cassandra/cql3/ListsTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/cql3/ListsTest.java b/test/unit/org/apache/cassandra/cql3/ListsTest.java new file mode 100644 index 0000000..9ca0010 --- /dev/null +++ b/test/unit/org/apache/cassandra/cql3/ListsTest.java @@ -0,0 +1,166 @@ +/* + * 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 org.apache.cassandra.cql3; + +import java.nio.ByteBuffer; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.util.UUID; + +import com.google.common.collect.Iterators; +import org.junit.Assert; +import org.junit.Test; + +import org.apache.cassandra.config.CFMetaData; +import org.apache.cassandra.config.ColumnDefinition; +import org.apache.cassandra.cql3.Lists.PrecisionTime; +import org.apache.cassandra.db.Clustering; +import org.apache.cassandra.db.DecoratedKey; +import org.apache.cassandra.db.rows.Cell; +import org.apache.cassandra.db.rows.Row; +import org.apache.cassandra.dht.Murmur3Partitioner; +import org.apache.cassandra.utils.ByteBufferUtil; +import org.apache.cassandra.utils.UUIDGen; + +public class ListsTest extends CQLTester +{ + private static final long DEFAULT_MILLIS = 424242424242L; + private static final int DEFAULT_NANOS = PrecisionTime.MAX_NANOS; + + @Test + public void testPrecisionTime_getNext_simple() + { + PrecisionTime.set(DEFAULT_MILLIS, DEFAULT_NANOS); + + long millis = DEFAULT_MILLIS - 100; + int count = 1; + PrecisionTime next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(millis, next.millis); + Assert.assertEquals(DEFAULT_NANOS - count, next.nanos); + + next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(millis, next.millis); + Assert.assertEquals(DEFAULT_NANOS - (count * 2), next.nanos); + } + + @Test + public void testPrecisionTime_getNext_Mulitple() + { + PrecisionTime.set(DEFAULT_MILLIS, DEFAULT_NANOS); + + long millis = DEFAULT_MILLIS - 100; + int count = DEFAULT_NANOS / 2; + PrecisionTime next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(millis, next.millis); + Assert.assertEquals(DEFAULT_NANOS - count, next.nanos); + } + + @Test + public void testPrecisionTime_getNext_RollOverNanos() + { + final int remainingNanos = 0; + PrecisionTime.set(DEFAULT_MILLIS, remainingNanos); + + long millis = DEFAULT_MILLIS; + int count = 1; + PrecisionTime next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(millis - 1, next.millis); + Assert.assertEquals(DEFAULT_NANOS - count, next.nanos); + + next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(millis - 1, next.millis); + Assert.assertEquals(DEFAULT_NANOS - (count * 2), next.nanos); + } + + @Test + public void testPrecisionTime_getNext_BorkedClock() + { + final int remainingNanos = 1; + PrecisionTime.set(DEFAULT_MILLIS, remainingNanos); + + long millis = DEFAULT_MILLIS + 100; + int count = 1; + PrecisionTime next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(DEFAULT_MILLIS, next.millis); + Assert.assertEquals(remainingNanos - count, next.nanos); + + // this should roll the clock + next = PrecisionTime.getNext(millis, count); + Assert.assertEquals(DEFAULT_MILLIS - 1, next.millis); + Assert.assertEquals(DEFAULT_NANOS - count, next.nanos); + } + + @Test + public void testPrepender_SmallList() + { + List<ByteBuffer> terms = new ArrayList<>(); + terms.add(ByteBufferUtil.bytes(1)); + terms.add(ByteBufferUtil.bytes(2)); + terms.add(ByteBufferUtil.bytes(3)); + terms.add(ByteBufferUtil.bytes(4)); + terms.add(ByteBufferUtil.bytes(5)); + testPrepender_execute(terms); + } + + @Test + public void testPrepender_HugeList() + { + List<ByteBuffer> terms = new ArrayList<>(); + // create a large enough array, then remove some off the end, just to make it an odd size + for (int i = 0; i < PrecisionTime.MAX_NANOS * 4 - 287; i++) + terms.add(ByteBufferUtil.bytes(i)); + testPrepender_execute(terms); + } + + private void testPrepender_execute(List<ByteBuffer> terms) + { + createTable("CREATE TABLE %s (k int PRIMARY KEY, l list<text>)"); + CFMetaData metaData = currentTableMetadata(); + + ColumnDefinition columnDefinition = metaData.getColumnDefinition(ByteBufferUtil.bytes("l")); + Term term = new Lists.Value(terms); + Lists.Prepender prepender = new Lists.Prepender(columnDefinition, term); + + ByteBuffer keyBuf = ByteBufferUtil.bytes("key"); + DecoratedKey key = Murmur3Partitioner.instance.decorateKey(keyBuf); + UpdateParameters parameters = new UpdateParameters(metaData, null, null, System.currentTimeMillis(), 1000, Collections.emptyMap()); + Clustering clustering = new Clustering(ByteBufferUtil.bytes(1)); + parameters.newRow(clustering); + prepender.execute(key, parameters); + + Row row = parameters.buildRow(); + Assert.assertEquals(terms.size(), Iterators.size(row.cells().iterator())); + + int idx = 0; + UUID last = null; + for (Cell cell : row.cells()) + { + UUID uuid = UUIDGen.getUUID(cell.path().get(0)); + + if (last != null) + Assert.assertTrue(last.compareTo(uuid) < 0); + last = uuid; + + Assert.assertEquals(String.format("different values found: expected: '%d', found '%d'", ByteBufferUtil.toInt(terms.get(idx)), ByteBufferUtil.toInt(cell.value())), + terms.get(idx), cell.value()); + idx++; + } + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
