denis-chudov commented on code in PR #1807: URL: https://github.com/apache/ignite-3/pull/1807#discussion_r1146067543
########## modules/core/src/main/java/org/apache/ignite/internal/causality/BaseVersionedValue.java: ########## @@ -0,0 +1,338 @@ +/* + * 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.ignite.internal.causality; + +import static java.util.concurrent.CompletableFuture.completedFuture; +import static org.apache.ignite.lang.IgniteStringFormatter.format; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.NavigableMap; +import java.util.concurrent.CompletableFuture; +import java.util.concurrent.CompletionException; +import java.util.concurrent.ConcurrentNavigableMap; +import java.util.concurrent.ConcurrentSkipListMap; +import java.util.concurrent.CopyOnWriteArrayList; +import java.util.concurrent.locks.ReadWriteLock; +import java.util.concurrent.locks.ReentrantReadWriteLock; +import java.util.function.Supplier; +import org.apache.ignite.internal.logger.IgniteLogger; +import org.apache.ignite.internal.logger.Loggers; +import org.apache.ignite.internal.util.Lazy; +import org.jetbrains.annotations.Nullable; + +/** + * Base implementation of a {@code VersionedValue} intended to be used by other implementations. + */ +class BaseVersionedValue<T> implements VersionedValue<T> { + private final IgniteLogger log = Loggers.forClass(BaseVersionedValue.class); + + /** Token until the value is initialized. */ + private static final long NOT_INITIALIZED = -1L; + + /** Default history size. */ + private static final int DEFAULT_MAX_HISTORY_SIZE = 10; + + /** Size of the history of changes to store, including last applied token. */ + private final int maxHistorySize; + + /** List of completion listeners, see {@link #whenComplete}. */ + private final List<CompletionListener<T>> completionListeners = new CopyOnWriteArrayList<>(); + + /** Versioned value storage. */ + private final ConcurrentNavigableMap<Long, CompletableFuture<T>> history = new ConcurrentSkipListMap<>(); + + /** Default value that is used when a Versioned Value is completed without an explicit value. */ + @Nullable + private final Lazy<T> defaultValue; + + /** + * Last applied causality token. + * + * <p>Multi-threaded access is guarded by the {@link #readWriteLock}. + */ + private long actualToken = NOT_INITIALIZED; + + private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock(); + + BaseVersionedValue(@Nullable Supplier<T> defaultValueSupplier) { + this(DEFAULT_MAX_HISTORY_SIZE, defaultValueSupplier); + } + + BaseVersionedValue(int maxHistorySize, @Nullable Supplier<T> defaultValueSupplier) { + this.maxHistorySize = maxHistorySize; + this.defaultValue = defaultValueSupplier == null ? null : new Lazy<>(defaultValueSupplier); + } + + @Override + public CompletableFuture<T> get(long causalityToken) { + assert causalityToken > NOT_INITIALIZED; + + readWriteLock.readLock().lock(); + + try { + if (causalityToken > actualToken) { + return history.computeIfAbsent(causalityToken, t -> new CompletableFuture<>()); + } + + Entry<Long, CompletableFuture<T>> histEntry = history.floorEntry(causalityToken); + + if (histEntry == null) { + throw new OutdatedTokenException(causalityToken, actualToken, maxHistorySize); + } + + return histEntry.getValue(); + } finally { + readWriteLock.readLock().unlock(); + } + } + + @Override + public @Nullable T latest() { + for (CompletableFuture<T> fut : history.descendingMap().values()) { + if (fut.isDone()) { + return fut.join(); + } + } + + return getDefault(); + } + + /** + * Returns the default value. + */ + @Nullable T getDefault() { + return defaultValue == null ? null : defaultValue.get(); + } + + /** + * Completes the Versioned Value for the given token. This method will look for the previous complete token and complete all registered + * futures in the {@code (prevToken, causalityToken]} range. If no {@code complete} methods have been called before, all these futures + * will be complete with the configured default value. + * + * <p>Calling this method will trigger the {@link #whenComplete} listeners for the given token. + * + * @param causalityToken Causality token. + */ + void complete(long causalityToken) { Review Comment: This method is in every implementation of VV, why it is not in interface? ########## modules/core/src/test/java/org/apache/ignite/internal/causality/IncrementalVersionedValueTest.java: ########## @@ -0,0 +1,442 @@ +/* + * 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.ignite.internal.causality; + +import static java.util.concurrent.CompletableFuture.completedFuture; +import static java.util.concurrent.CompletableFuture.failedFuture; +import static org.apache.ignite.internal.testframework.IgniteTestUtils.assertThrowsWithCause; +import static org.apache.ignite.internal.testframework.IgniteTestUtils.runRace; +import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willBe; +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.containsString; +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; +import static org.junit.jupiter.api.Assertions.assertThrows; +import static org.junit.jupiter.api.Assertions.assertTrue; +import static org.mockito.ArgumentMatchers.any; +import static org.mockito.ArgumentMatchers.anyLong; +import static org.mockito.Mockito.clearInvocations; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.never; +import static org.mockito.Mockito.verify; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.UUID; +import java.util.concurrent.CompletableFuture; +import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.atomic.AtomicReference; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import org.apache.ignite.lang.IgniteInternalException; +import org.jetbrains.annotations.Nullable; +import org.junit.jupiter.api.RepeatedTest; +import org.junit.jupiter.api.Test; + +/** + * Tests for {@link IncrementalVersionedValue}. + */ +public class IncrementalVersionedValueTest { + /** Test value. */ + private static final int TEST_VALUE = 1; + + /** The test revision register is used to move the revision forward. */ + private final TestRevisionRegister register = new TestRevisionRegister(); + + /** Test exception is used for exceptionally completion Versioned value object. */ + private static final Exception TEST_EXCEPTION = new Exception("Test exception"); + + /** + * Checks that the update method work as expected when the previous value is known. + * + * @throws Exception If failed. + */ + @Test + public void testUpdate() throws Exception { + var versionedValue = new IncrementalVersionedValue<Integer>(register); + + versionedValue.update(0, (integer, throwable) -> completedFuture(TEST_VALUE)); + + register.moveRevision(0L).join(); + + CompletableFuture<Integer> fut = versionedValue.get(1); + + assertFalse(fut.isDone()); + + int incrementCount = 10; + + for (int i = 0; i < incrementCount; i++) { + versionedValue.update(1, (previous, e) -> completedFuture(++previous)); + + assertFalse(fut.isDone()); + } + + register.moveRevision(1L).join(); + + assertTrue(fut.isDone()); + + assertEquals(TEST_VALUE + incrementCount, fut.get()); + + assertThrows(AssertionError.class, () -> versionedValue.update(1L, (i, t) -> completedFuture(null))); + } + + /** + * Checks that the update method work as expected when there is no history to calculate previous value. + * + * @throws Exception If failed. + */ + @Test + public void testUpdatePredefined() throws Exception { + var versionedValue = new IncrementalVersionedValue<Integer>(register); + + CompletableFuture<Integer> fut = versionedValue.get(0); + + assertFalse(fut.isDone()); + + versionedValue.update(0, (previous, e) -> { + assertNull(previous); + + return completedFuture(TEST_VALUE); + }); + + assertFalse(fut.isDone()); + + register.moveRevision(0L).join(); + + assertTrue(fut.isDone()); + + assertEquals(TEST_VALUE, fut.get()); + } + + /** + * Test asynchronous update closure. + */ + @Test + public void testAsyncUpdate() { + IncrementalVersionedValue<Integer> vv = new IncrementalVersionedValue<>(register); + + CompletableFuture<Integer> fut = new CompletableFuture<>(); + + vv.update(0L, (v, e) -> fut); + + CompletableFuture<Integer> vvFut = vv.get(0L); + + CompletableFuture<?> revFut = register.moveRevision(0L); + + assertFalse(fut.isDone()); + assertFalse(vvFut.isDone()); + assertFalse(revFut.isDone()); + + fut.complete(1); + + revFut.join(); + + assertTrue(vvFut.isDone()); + } + + /** + * Test the case when exception happens in updater. + */ + @Test + public void testExceptionOnUpdate() { + IncrementalVersionedValue<Integer> vv = new IncrementalVersionedValue<>(register, () -> 0); + + final int count = 4; + final int successfulCompletionsCount = count / 2; + + AtomicInteger actualSuccessfulCompletionsCount = new AtomicInteger(); + + final String exceptionMsg = "test msg"; + + for (int i = 0; i < count; i++) { + vv.update(0L, (v, e) -> { + if (e != null) { + return failedFuture(e); + } + + if (v == successfulCompletionsCount) { + throw new IgniteInternalException(exceptionMsg); + } + + actualSuccessfulCompletionsCount.incrementAndGet(); + + return completedFuture(++v); + }); + } + + AtomicReference<Throwable> exceptionRef = new AtomicReference<>(); + + vv.whenComplete((t, v, e) -> exceptionRef.set(e)); + + vv.complete(0L); + + assertThrowsWithCause(() -> vv.get(0L).join(), IgniteInternalException.class); + + assertThat(exceptionRef.get().getMessage(), containsString(exceptionMsg)); + } + + /** + * Test with multiple versioned values and asynchronous completion. + */ + @Test + public void testAsyncMultiVv() { + final String registryName = "Registry"; + final String assignmentName = "Assignment"; + final String tableName = "T1_"; + + IncrementalVersionedValue<Map<UUID, String>> tablesVv = new IncrementalVersionedValue<>(f -> { + }, HashMap::new); + IncrementalVersionedValue<Map<UUID, String>> schemasVv = new IncrementalVersionedValue<>(register, HashMap::new); + IncrementalVersionedValue<Map<UUID, String>> assignmentsVv = new IncrementalVersionedValue<>(register, HashMap::new); + + schemasVv.whenComplete((token, value, ex) -> tablesVv.complete(token)); + + BiFunction<Long, UUID, CompletableFuture<String>> schemaRegistry = + (token, uuid) -> schemasVv.get(token).thenApply(schemas -> schemas.get(uuid)); + + // Adding table. + long token = 0L; + UUID tableId = UUID.randomUUID(); + + CompletableFuture<String> tableFut = schemaRegistry.apply(token, tableId) + .thenCombine(assignmentsVv.get(token), (registry, assignments) -> tableName + registry + assignments.get(tableId)); + + tablesVv.update(token, (old, e) -> tableFut.thenApply(table -> { + Map<UUID, String> val = new HashMap<>(old); + + val.put(tableId, table); + + return val; + })); + + CompletableFuture<String> userFut = tablesVv.get(token).thenApply(map -> map.get(tableId)); + + schemasVv.update(token, (old, e) -> { + old.put(tableId, registryName); + + return completedFuture(old); + }); + + assignmentsVv.update(token, (old, e) -> { + old.put(tableId, assignmentName); + + return completedFuture(old); + }); + + assertFalse(tableFut.isDone()); + assertFalse(userFut.isDone()); + + register.moveRevision(token).join(); + + tableFut.join(); + + assertEquals(tableName + registryName + assignmentName, userFut.join()); + } + + /** + * Tests a default value supplier. + */ + @Test + public void testDefaultValueSupplier() { + IncrementalVersionedValue<Integer> vv = new IncrementalVersionedValue<>(register, () -> TEST_VALUE); + + checkDefaultValue(vv, TEST_VALUE); + } + + /** + * Tests a case when there is no default value supplier. + */ + @Test + public void testWithoutDefaultValue() { + IncrementalVersionedValue<Integer> vv = new IncrementalVersionedValue<>(register); + + checkDefaultValue(vv, null); + } + + @RepeatedTest(100) + void testConcurrentGetAndComplete() { + var versionedValue = new IncrementalVersionedValue<>(register, () -> 1); + + // Set initial value. + versionedValue.complete(1); + + runRace( + () -> versionedValue.complete(3), + () -> { + CompletableFuture<Integer> readerFuture = versionedValue.get(2); + + assertThat(readerFuture, willBe(1)); + } + ); + } + + @RepeatedTest(100) + void testConcurrentGetAndCompleteWithHistoryTrimming() { + var versionedValue = new IncrementalVersionedValue<>(register, () -> 1); + + // Set initial value (history size 1). + versionedValue.complete(2); + // Set history size to 2. + versionedValue.complete(3); + + runRace( + () -> { + versionedValue.update(4, (i, t) -> completedFuture(i + 1)); + // Trigger history trimming + versionedValue.complete(4); + }, + () -> { + try { + CompletableFuture<Integer> readerFuture = versionedValue.get(2); + + assertThat(readerFuture, willBe(1)); + } catch (OutdatedTokenException ignored) { + // This is considered as a valid outcome. + } + } + ); + + assertThat(versionedValue.get(4), willBe(2)); Review Comment: You did not specify the history size so the trimming doesnt actually happen here. Also, it would be nice to add check that get(2) throws OutdatedTokenException, to make sure that history is really trimmed -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
