This is an automated email from the ASF dual-hosted git repository.
tkalkirill pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/ignite-3.git
The following commit(s) were added to refs/heads/main by this push:
new 5911d727e3 IGNITE-23286 Throw CompactedException for get list
metastorage methods (#4541)
5911d727e3 is described below
commit 5911d727e3ef801a5dc4cfaa714b208bd615d18f
Author: Kirill Tkalenko <[email protected]>
AuthorDate: Fri Oct 11 15:03:01 2024 +0300
IGNITE-23286 Throw CompactedException for get list metastorage methods
(#4541)
---
.../internal/metastorage/MetaStorageManager.java | 88 +++++++++--
.../metastorage/impl/MetaStorageManagerImpl.java | 11 +-
.../metastorage/server/KeyValueStorage.java | 84 +++++++++-
.../metastorage/server/KeyValueStorageUtils.java | 23 ++-
.../server/persistence/RocksDbKeyValueStorage.java | 110 +++++---------
.../AbstractCompactionKeyValueStorageTest.java | 169 +++++++++++++++++++++
.../server/KeyValueStorageUtilsTest.java | 19 +++
.../server/SimpleInMemoryKeyValueStorage.java | 85 ++++-------
8 files changed, 431 insertions(+), 158 deletions(-)
diff --git
a/modules/metastorage-api/src/main/java/org/apache/ignite/internal/metastorage/MetaStorageManager.java
b/modules/metastorage-api/src/main/java/org/apache/ignite/internal/metastorage/MetaStorageManager.java
index 4685ff6f3b..9cf32ec6b4 100644
---
a/modules/metastorage-api/src/main/java/org/apache/ignite/internal/metastorage/MetaStorageManager.java
+++
b/modules/metastorage-api/src/main/java/org/apache/ignite/internal/metastorage/MetaStorageManager.java
@@ -124,18 +124,88 @@ public interface MetaStorageManager extends
IgniteComponent {
CompletableFuture<Entry> get(ByteArray key, long revUpperBound);
/**
- * Returns all entries corresponding to the given key and bounded by given
revisions.
- * All these entries are ordered by revisions and have the same key.
- * The lower bound and the upper bound are inclusive.
+ * Returns all entries (ordered by revisions) corresponding to the given
key and bounded by given revisions locally.
*
* <p>This method doesn't wait for the storage's revision to become
greater or equal to the revUpperBound parameter, so it is
- * up to user to wait for the appropriate time to call this method.
- * TODO: IGNITE-19735 move this method to another interface for
interaction with local KeyValueStorage.
+ * up to user to wait for the appropriate time to call this method.</p>
*
- * @param key The key.
- * @param revLowerBound The lower bound of revision.
- * @param revUpperBound The upper bound of revision.
- * @return Entries corresponding to the given key.
+ * <p>Let's consider examples of the work of the method and compaction of
the metastorage. Let's assume that we have keys with
+ * revisions "foo" [2, 4] and "bar" [2, 4 (tombstone)], and the key "some"
has never been in the metastorage.</p>
+ * <ul>
+ * <li>Compaction revision is {@code 1}.
+ * <ul>
+ * <li>getLocally("foo", 1, 1) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 1, 2) - will return a single value with
revision 2.</li>
+ * <li>getLocally("foo", 1, 3) - will return a single value with
revision 2.</li>
+ * <li>getLocally("bar", 1, 1) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 1, 2) - will return a single value with
revision 2.</li>
+ * <li>getLocally("bar", 1, 3) - will return a single value with
revision 2.</li>
+ * <li>getLocally("some", 1, 1) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 1, 2) - will return an empty list.</li>
+ * <li>getLocally("some", 1, 3) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 2}.
+ * <ul>
+ * <li>getLocally("foo", 1, 2) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 2, 2) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 1, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 2, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 3, 3) - will return an empty list.</li>
+ * <li>getLocally("foo", 3, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("bar", 1, 2) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 2, 2) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 1, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 2, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 3, 3) - will return an empty list.</li>
+ * <li>getLocally("bar", 3, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("some", 1, 2) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 2, 2) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 2, 3) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 3, 3) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 3}.
+ * <ul>
+ * <li>getLocally("foo", 1, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 2, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 3, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("foo", 3, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("foo", 4, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("bar", 1, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 2, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 3, 3) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 3, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("bar", 4, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("some", 2, 3) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 3, 4) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 4, 4) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 4}.
+ * <ul>
+ * <li>getLocally("foo", 3, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("foo", 4, 4) - will return a single value with
revision 4.</li>
+ * <li>getLocally("foo", 4, 5) - will return a single value with
revision 4.</li>
+ * <li>getLocally("foo", 5, 5) - will return an empty list.</li>
+ * <li>getLocally("bar", 3, 4) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 4, 4) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 4, 5) - a {@link CompactedException} will
be thrown.</li>
+ * <li>getLocally("bar", 5, 5) - will return an empty list.</li>
+ * <li>getLocally("some", 3, 4) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 4, 4) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 4, 5) - a {@link CompactedException}
will be thrown.</li>
+ * <li>getLocally("some", 5, 5) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * </ul>
+ *
+ * @param key Key.
+ * @param revLowerBound Lower bound of revision (inclusive).
+ * @param revUpperBound Upper bound of revision (inclusive).
+ * @throws IgniteInternalException with cause {@link
NodeStoppingException} if the node is in the process of stopping.
+ * @throws CompactedException If no entries could be found and the {@code
revLowerBound} is less than or equal to the last compacted
+ * one.
*/
@Deprecated
List<Entry> getLocally(byte[] key, long revLowerBound, long revUpperBound);
diff --git
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/impl/MetaStorageManagerImpl.java
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/impl/MetaStorageManagerImpl.java
index 936495685f..fee2698fcf 100644
---
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/impl/MetaStorageManagerImpl.java
+++
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/impl/MetaStorageManagerImpl.java
@@ -93,7 +93,6 @@ import org.apache.ignite.internal.util.Cursor;
import org.apache.ignite.internal.util.ExceptionUtils;
import org.apache.ignite.internal.util.IgniteSpinBusyLock;
import org.apache.ignite.internal.util.IgniteUtils;
-import org.apache.ignite.lang.IgniteException;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.annotations.TestOnly;
@@ -755,15 +754,7 @@ public class MetaStorageManagerImpl implements
MetaStorageManager, MetastorageGr
@Override
public List<Entry> getLocally(byte[] key, long revLowerBound, long
revUpperBound) {
- if (!busyLock.enterBusy()) {
- throw new IgniteException(new NodeStoppingException());
- }
-
- try {
- return storage.get(key, revLowerBound, revUpperBound);
- } finally {
- busyLock.leaveBusy();
- }
+ return inBusyLock(busyLock, () -> storage.get(key, revLowerBound,
revUpperBound));
}
@Override
diff --git
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java
index 15d9357bbd..0120df0c88 100644
---
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java
+++
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java
@@ -119,14 +119,84 @@ public interface KeyValueStorage extends
ManuallyCloseable {
Entry get(byte[] key, long revUpperBound);
/**
- * Returns all entries corresponding to the given key and bounded by given
revisions.
- * All these entries are ordered by revisions and have the same key.
- * The lower bound and the upper bound are inclusive.
+ * Returns all entries (ordered by revisions) corresponding to the given
key and bounded by given revisions.
*
- * @param key The key.
- * @param revLowerBound The lower bound of revision.
- * @param revUpperBound The upper bound of revision.
- * @return Entries corresponding to the given key.
+ * <p>Let's consider examples of the work of the method and compaction of
the metastorage. Let's assume that we have keys with
+ * revisions "foo" [2, 4] and "bar" [2, 4 (tombstone)], and the key "some"
has never been in the metastorage.</p>
+ * <ul>
+ * <li>Compaction revision is {@code 1}.
+ * <ul>
+ * <li>get("foo", 1, 1) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 1, 2) - will return a single value with revision
2.</li>
+ * <li>get("foo", 1, 3) - will return a single value with revision
2.</li>
+ * <li>get("bar", 1, 1) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 1, 2) - will return a single value with revision
2.</li>
+ * <li>get("bar", 1, 3) - will return a single value with revision
2.</li>
+ * <li>get("some", 1, 1) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 1, 2) - will return an empty list.</li>
+ * <li>get("some", 1, 3) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 2}.
+ * <ul>
+ * <li>get("foo", 1, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 2, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 1, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 3, 3) - will return an empty list.</li>
+ * <li>get("foo", 3, 4) - will return a single value with revision
4.</li>
+ * <li>get("bar", 1, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 2, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 1, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 3, 3) - will return an empty list.</li>
+ * <li>get("bar", 3, 4) - will return a single value with revision
4.</li>
+ * <li>get("some", 1, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 2, 2) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 3, 3) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 3}.
+ * <ul>
+ * <li>get("foo", 1, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 3, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("foo", 3, 4) - will return a single value with revision
4.</li>
+ * <li>get("foo", 4, 4) - will return a single value with revision
4.</li>
+ * <li>get("bar", 1, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 3, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 3, 4) - will return a single value with revision
4.</li>
+ * <li>get("bar", 4, 4) - will return a single value with revision
4.</li>
+ * <li>get("some", 2, 3) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 3, 4) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 4, 4) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * <li>Compaction revision is {@code 4}.
+ * <ul>
+ * <li>get("foo", 3, 4) - will return a single value with revision
4.</li>
+ * <li>get("foo", 4, 4) - will return a single value with revision
4.</li>
+ * <li>get("foo", 4, 5) - will return a single value with revision
4.</li>
+ * <li>get("foo", 5, 5) - will return an empty list.</li>
+ * <li>get("bar", 3, 4) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 4, 4) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 4, 5) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("bar", 5, 5) - will return an empty list.</li>
+ * <li>get("some", 3, 4) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 4, 4) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 4, 5) - a {@link CompactedException} will be
thrown.</li>
+ * <li>get("some", 5, 5) - will return an empty list.</li>
+ * </ul>
+ * </li>
+ * </ul>
+ *
+ * @param key Key.
+ * @param revLowerBound Lower bound of revision (inclusive).
+ * @param revUpperBound Upper bound of revision (inclusive).
+ * @throws CompactedException If no entries could be found and the {@code
revLowerBound} is less than or equal to the last
+ * {@link #setCompactionRevision compacted} one.
*/
List<Entry> get(byte[] key, long revLowerBound, long revUpperBound);
diff --git
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtils.java
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtils.java
index 5657008a34..705907e08a 100644
---
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtils.java
+++
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtils.java
@@ -57,7 +57,7 @@ public class KeyValueStorageUtils {
}
/**
- * Returns index of maximum revision which must be less or equal to {@code
upperBoundRevision}. If there is no such revision then
+ * Returns index of maximum revision which is less or equal to {@code
upperBoundRevision}. If there is no such revision then
* {@link #NOT_FOUND} will be returned.
*
* @param keyRevisions Metastorage key revisions in ascending order.
@@ -77,6 +77,27 @@ public class KeyValueStorageUtils {
return i;
}
+ /**
+ * Returns index of minimum revision which is greater or equal to {@code
lowerBoundRevision}. If there is no such revision then
+ * {@link #NOT_FOUND} will be returned.
+ *
+ * @param keyRevisions Metastorage key revisions in ascending order.
+ * @param lowerBoundRevision Revision lower bound.
+ */
+ public static int minRevisionIndex(long[] keyRevisions, long
lowerBoundRevision) {
+ int i = binarySearch(keyRevisions, lowerBoundRevision);
+
+ if (i < 0) {
+ if (i == -(keyRevisions.length + 1)) {
+ return NOT_FOUND;
+ }
+
+ i = -(i + 1);
+ }
+
+ return i;
+ }
+
/** Returns {@link true} if the requested index is the last index of the
array. */
public static boolean isLastIndex(long[] arr, int index) {
assert index >= 0 && index < arr.length : "index=" + index + ",
arr.length=" + arr.length;
diff --git
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/persistence/RocksDbKeyValueStorage.java
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/persistence/RocksDbKeyValueStorage.java
index 39e96deda2..d288d7b6bd 100644
---
a/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/persistence/RocksDbKeyValueStorage.java
+++
b/modules/metastorage/src/main/java/org/apache/ignite/internal/metastorage/server/persistence/RocksDbKeyValueStorage.java
@@ -24,6 +24,8 @@ import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.assertRequestedRevisionLessThanOrEqualToCurrent;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.indexToCompact;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.isLastIndex;
+import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.maxRevisionIndex;
+import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.minRevisionIndex;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.toUtf8String;
import static org.apache.ignite.internal.metastorage.server.Value.TOMBSTONE;
import static
org.apache.ignite.internal.metastorage.server.persistence.RocksStorageUtils.appendLong;
@@ -98,7 +100,6 @@ import
org.apache.ignite.internal.metastorage.impl.MetaStorageManagerImpl;
import org.apache.ignite.internal.metastorage.server.Condition;
import org.apache.ignite.internal.metastorage.server.If;
import org.apache.ignite.internal.metastorage.server.KeyValueStorage;
-import org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils;
import org.apache.ignite.internal.metastorage.server.MetastorageChecksum;
import org.apache.ignite.internal.metastorage.server.OnRevisionAppliedCallback;
import org.apache.ignite.internal.metastorage.server.Statement;
@@ -1138,7 +1139,7 @@ public class RocksDbKeyValueStorage implements
KeyValueStorage {
assert revUpperBound >= 0 : revUpperBound;
long[] keyRevisions = getRevisionsForOperation(key);
- int maxRevisionIndex =
KeyValueStorageUtils.maxRevisionIndex(keyRevisions, revUpperBound);
+ int maxRevisionIndex = maxRevisionIndex(keyRevisions, revUpperBound);
if (maxRevisionIndex == NOT_FOUND) {
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revUpperBound,
compactionRevision);
@@ -1157,46 +1158,49 @@ public class RocksDbKeyValueStorage implements
KeyValueStorage {
return EntryImpl.toEntry(key, revision, value);
}
- /**
- * Returns all entries corresponding to the given key and bounded by given
revisions.
- * All these entries are ordered by revisions and have the same key.
- * The lower bound and the upper bound are inclusive.
- *
- * @param key The key.
- * @param revLowerBound The lower bound of revision.
- * @param revUpperBound The upper bound of revision.
- * @return Entries corresponding to the given key.
- */
private List<Entry> doGet(byte[] key, long revLowerBound, long
revUpperBound) {
- assert revLowerBound >= 0 : "Invalid arguments: [revLowerBound=" +
revLowerBound + ']';
- assert revUpperBound >= 0 : "Invalid arguments: [revUpperBound=" +
revUpperBound + ']';
- assert revUpperBound >= revLowerBound
- : "Invalid arguments: [revLowerBound=" + revLowerBound + ",
revUpperBound=" + revUpperBound + ']';
+ assert revLowerBound >= 0 : revLowerBound;
+ assert revUpperBound >= 0 : revUpperBound;
+ assert revUpperBound >= revLowerBound : "revLowerBound=" +
revLowerBound + ", revUpperBound=" + revUpperBound;
- long[] revs;
+ long[] keyRevisions = getRevisionsForOperation(key);
- try {
- revs = getRevisions(key);
- } catch (RocksDBException e) {
- throw new MetaStorageException(OP_EXECUTION_ERR, e);
- }
+ int minRevisionIndex = minRevisionIndex(keyRevisions, revLowerBound);
+ int maxRevisionIndex = maxRevisionIndex(keyRevisions, revUpperBound);
- if (revs.length == 0) {
- return Collections.emptyList();
+ if (minRevisionIndex == NOT_FOUND || maxRevisionIndex == NOT_FOUND) {
+
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revLowerBound,
compactionRevision);
+
+ return List.of();
}
- int firstRevIndex = minRevisionIndex(revs, revLowerBound);
- int lastRevIndex = maxRevisionIndex(revs, revUpperBound);
+ var entries = new ArrayList<Entry>();
- // firstRevIndex can be -1 if minRevisionIndex return -1. lastRevIndex
can be -1 if maxRevisionIndex return -1.
- if (firstRevIndex == -1 || lastRevIndex == -1) {
- return Collections.emptyList();
- }
+ for (int i = minRevisionIndex; i <= maxRevisionIndex; i++) {
+ long revision = keyRevisions[i];
+
+ Value value;
- List<Entry> entries = new ArrayList<>();
+ // More complex check to read less from disk.
+ if (revision <= compactionRevision) {
+ if (!isLastIndex(keyRevisions, i)) {
+ continue;
+ }
+
+ value = getValueForOperation(key, revision);
+
+ if (value.tombstone()) {
+ continue;
+ }
+ } else {
+ value = getValueForOperation(key, revision);
+ }
- for (int i = firstRevIndex; i <= lastRevIndex; i++) {
- entries.add(doGetValue(key, revs[i]));
+ entries.add(EntryImpl.toEntry(key, revision, value));
+ }
+
+ if (entries.isEmpty()) {
+
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revLowerBound,
compactionRevision);
}
return entries;
@@ -1252,46 +1256,6 @@ public class RocksDbKeyValueStorage implements
KeyValueStorage {
return -1;
}
- /**
- * Returns index of minimum revision which must be greater or equal to
{@code lowerBoundRev}.
- * If there is no such revision then {@code -1} will be returned.
- *
- * @param revs Revisions list.
- * @param lowerBoundRev Revision lower bound.
- * @return Index of minimum revision or {@code -1} if there is no such
revision.
- */
- private static int minRevisionIndex(long[] revs, long lowerBoundRev) {
- for (int i = 0; i < revs.length; i++) {
- long rev = revs[i];
-
- if (rev >= lowerBoundRev) {
- return i;
- }
- }
-
- return -1;
- }
-
- /**
- * Returns index of maximum revision which must be less or equal to {@code
upperBoundRev}.
- * If there is no such revision then {@code -1} will be returned.
- *
- * @param revs Revisions list.
- * @param upperBoundRev Revision upper bound.
- * @return Index of maximum revision or {@code -1} if there is no such
revision.
- */
- private static int maxRevisionIndex(long[] revs, long upperBoundRev) {
- for (int i = revs.length - 1; i >= 0; i--) {
- long rev = revs[i];
-
- if (rev <= upperBoundRev) {
- return i;
- }
- }
-
- return -1;
- }
-
/**
* Gets the value by a key and a revision.
*
diff --git
a/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/AbstractCompactionKeyValueStorageTest.java
b/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/AbstractCompactionKeyValueStorageTest.java
index e5c6cca3ac..c3e10a8316 100644
---
a/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/AbstractCompactionKeyValueStorageTest.java
+++
b/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/AbstractCompactionKeyValueStorageTest.java
@@ -534,6 +534,160 @@ public abstract class
AbstractCompactionKeyValueStorageTest extends AbstractKeyV
assertDoesNotThrowCompactedExceptionForGetAll(6, FOO_KEY, BAR_KEY,
NOT_EXISTS_KEY);
}
+ @Test
+ void testGetListAndCompactionForFooKey() {
+ // FOO_KEY has revisions: [1, 3, 5].
+ storage.setCompactionRevision(1);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 1, 1);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 1, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 3);
+
+ storage.setCompactionRevision(2);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 1, 1);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 1, 2);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 2, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 3, 3);
+
+ storage.setCompactionRevision(3);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 1, 3);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 2, 3);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 3, 3);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 3, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 4, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 3, 5);
+
+ storage.setCompactionRevision(4);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 3, 4);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 4, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 3, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 5, 5);
+
+ storage.setCompactionRevision(5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 3, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 5, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 5, 6);
+
+ storage.setCompactionRevision(6);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 3, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 5, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(FOO_KEY, 5, 6);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 6, 6);
+ assertThrowsCompactedExceptionForGetList(FOO_KEY, 6, 7);
+ }
+
+ @Test
+ void testGetListAndCompactionForBarKey() {
+ // BAR_KEY has revisions: [1, 2, 5 (tombstone)].
+ storage.setCompactionRevision(1);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 1);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 1, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 1, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 2, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 2, 3);
+
+ storage.setCompactionRevision(2);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 1);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 2);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 2, 2);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 3);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 2, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 3, 3);
+
+ storage.setCompactionRevision(3);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 3);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 2, 3);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 3, 3);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 3, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 4, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 3, 5);
+
+ storage.setCompactionRevision(4);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 3, 4);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 4, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 1, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 2, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 3, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 5, 5);
+
+ storage.setCompactionRevision(5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 2, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 3, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 4, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 5, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 5, 6);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 6, 6);
+
+ storage.setCompactionRevision(6);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 1, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 2, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 3, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 4, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 5, 5);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 5, 6);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 6, 6);
+ assertThrowsCompactedExceptionForGetList(BAR_KEY, 6, 7);
+ assertDoesNotThrowsCompactedExceptionForGetList(BAR_KEY, 7, 7);
+ }
+
+ @Test
+ void testGetListAndCompactionForNotExistsKey() {
+ storage.setCompactionRevision(1);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 1, 1);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 1, 2);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 2, 2);
+
+ storage.setCompactionRevision(2);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 1, 2);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 2, 2);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 2, 3);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 3, 3);
+
+ storage.setCompactionRevision(3);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 2, 3);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 3, 3);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 3, 4);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 4, 4);
+
+ storage.setCompactionRevision(4);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 3, 4);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 4, 4);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 4, 5);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 5, 5);
+
+ storage.setCompactionRevision(5);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 4, 5);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 5, 5);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 5, 6);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 6, 6);
+
+ storage.setCompactionRevision(6);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 5, 6);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 6, 6);
+ assertThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 6, 7);
+ assertDoesNotThrowsCompactedExceptionForGetList(NOT_EXISTS_KEY, 7, 7);
+ }
+
private List<Integer> collectRevisions(byte[] key) {
var revisions = new ArrayList<Integer>();
@@ -598,6 +752,21 @@ public abstract class
AbstractCompactionKeyValueStorageTest extends AbstractKeyV
}
}
+ private void assertThrowsCompactedExceptionForGetList(byte[] key, long
revLowerBound, long revUpperBound) {
+ assertThrows(
+ CompactedException.class,
+ () -> storage.get(key, revLowerBound, revUpperBound),
+ () -> String.format("key=%s, revLowerBound=%s,
revUpperBound=%s", toUtf8String(key), revLowerBound, revUpperBound)
+ );
+ }
+
+ private void assertDoesNotThrowsCompactedExceptionForGetList(byte[] key,
long revLowerBound, long revUpperBound) {
+ assertDoesNotThrow(
+ () -> storage.get(key, revLowerBound, revUpperBound),
+ () -> String.format("key=%s, revLowerBound=%s,
revUpperBound=%s", toUtf8String(key), revLowerBound, revUpperBound)
+ );
+ }
+
private static String toUtf8String(byte[]... keys) {
return Arrays.stream(keys)
.map(KeyValueStorageUtils::toUtf8String)
diff --git
a/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtilsTest.java
b/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtilsTest.java
index 4211790552..121d4827eb 100644
---
a/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtilsTest.java
+++
b/modules/metastorage/src/test/java/org/apache/ignite/internal/metastorage/server/KeyValueStorageUtilsTest.java
@@ -22,6 +22,7 @@ import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.indexToCompact;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.isLastIndex;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.maxRevisionIndex;
+import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.minRevisionIndex;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.toUtf8String;
import static org.apache.ignite.internal.util.ArrayUtils.LONG_EMPTY_ARRAY;
import static org.junit.jupiter.api.Assertions.assertEquals;
@@ -107,4 +108,22 @@ public class KeyValueStorageUtilsTest {
assertTrue(isLastIndex(array, 2));
}
+
+ @Test
+ void testMinRevisionIndex() {
+ long[] keyRevisions = {3, 5, 7};
+
+ assertEquals(0, minRevisionIndex(keyRevisions, 1));
+ assertEquals(0, minRevisionIndex(keyRevisions, 2));
+ assertEquals(0, minRevisionIndex(keyRevisions, 3));
+
+ assertEquals(1, minRevisionIndex(keyRevisions, 4));
+ assertEquals(1, minRevisionIndex(keyRevisions, 5));
+
+ assertEquals(2, minRevisionIndex(keyRevisions, 6));
+ assertEquals(2, minRevisionIndex(keyRevisions, 7));
+
+ assertEquals(NOT_FOUND, minRevisionIndex(keyRevisions, 8));
+ assertEquals(NOT_FOUND, minRevisionIndex(keyRevisions, 9));
+ }
}
diff --git
a/modules/metastorage/src/testFixtures/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java
b/modules/metastorage/src/testFixtures/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java
index 4068ab8531..06bb3e10c0 100644
---
a/modules/metastorage/src/testFixtures/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java
+++
b/modules/metastorage/src/testFixtures/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java
@@ -27,6 +27,8 @@ import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.assertRequestedRevisionLessThanOrEqualToCurrent;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.indexToCompact;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.isLastIndex;
+import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.maxRevisionIndex;
+import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.minRevisionIndex;
import static
org.apache.ignite.internal.metastorage.server.KeyValueStorageUtils.toUtf8String;
import static org.apache.ignite.internal.metastorage.server.Value.TOMBSTONE;
import static
org.apache.ignite.internal.metastorage.server.raft.MetaStorageWriteHandler.IDEMPOTENT_COMMAND_PREFIX;
@@ -43,7 +45,6 @@ import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
-import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
@@ -728,7 +729,7 @@ public class SimpleInMemoryKeyValueStorage implements
KeyValueStorage {
assert revUpperBound >= 0 : revUpperBound;
long[] keyRevisions = toLongArray(keysIdx.get(key));
- int maxRevisionIndex =
KeyValueStorageUtils.maxRevisionIndex(keyRevisions, revUpperBound);
+ int maxRevisionIndex = maxRevisionIndex(keyRevisions, revUpperBound);
if (maxRevisionIndex == NOT_FOUND) {
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revUpperBound,
compactionRevision);
@@ -748,29 +749,37 @@ public class SimpleInMemoryKeyValueStorage implements
KeyValueStorage {
}
private List<Entry> doGet(byte[] key, long revLowerBound, long
revUpperBound) {
- assert revLowerBound >= 0 : "Invalid arguments: [revLowerBound=" +
revLowerBound + ']';
- assert revUpperBound >= 0 : "Invalid arguments: [revUpperBound=" +
revUpperBound + ']';
- assert revUpperBound >= revLowerBound
- : "Invalid arguments: [revLowerBound=" + revLowerBound + ",
revUpperBound=" + revUpperBound + ']';
+ assert revLowerBound >= 0 : revLowerBound;
+ assert revUpperBound >= 0 : revUpperBound;
+ assert revUpperBound >= revLowerBound : "revLowerBound=" +
revLowerBound + ", revUpperBound=" + revUpperBound;
- List<Long> revs = keysIdx.get(key);
+ long[] keyRevisions = toLongArray(keysIdx.get(key));
- if (revs == null || revs.isEmpty()) {
- return Collections.emptyList();
- }
+ int minRevisionIndex = minRevisionIndex(keyRevisions, revLowerBound);
+ int maxRevisionIndex = maxRevisionIndex(keyRevisions, revUpperBound);
- int firstRevIndex = minRevisionIndex(revs, revLowerBound);
- int lastRevIndex = maxRevisionIndex(revs, revUpperBound);
+ if (minRevisionIndex == NOT_FOUND || maxRevisionIndex == NOT_FOUND) {
+
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revLowerBound,
compactionRevision);
- // firstRevIndex can be -1 if minRevisionIndex return -1. lastRevIndex
can be -1 if maxRevisionIndex return -1.
- if (firstRevIndex == -1 || lastRevIndex == -1) {
- return Collections.emptyList();
+ return List.of();
}
- List<Entry> entries = new ArrayList<>();
+ var entries = new ArrayList<Entry>();
+
+ for (int i = minRevisionIndex; i <= maxRevisionIndex; i++) {
+ long revision = keyRevisions[i];
+
+ Value value = getValue(key, revision);
+
+ if (revision <= compactionRevision && (!isLastIndex(keyRevisions,
i) || value.tombstone())) {
+ continue;
+ }
+
+ entries.add(EntryImpl.toEntry(key, revision, value));
+ }
- for (int i = firstRevIndex; i <= lastRevIndex; i++) {
- entries.add(doGetValue(key, revs.get(i)));
+ if (entries.isEmpty()) {
+
CompactedException.throwIfRequestedRevisionLessThanOrEqualToCompacted(revLowerBound,
compactionRevision);
}
return entries;
@@ -798,46 +807,6 @@ public class SimpleInMemoryKeyValueStorage implements
KeyValueStorage {
return -1;
}
- /**
- * Returns index of minimum revision which must be greater or equal to
{@code lowerBoundRev}.
- * If there is no such revision then {@code -1} will be returned.
- *
- * @param revs Revisions list.
- * @param lowerBoundRev Revision lower bound.
- * @return Index of minimum revision or {@code -1} if there is no such
revision.
- */
- private static int minRevisionIndex(List<Long> revs, long lowerBoundRev) {
- for (int i = 0; i < revs.size(); i++) {
- long rev = revs.get(i);
-
- if (rev >= lowerBoundRev) {
- return i;
- }
- }
-
- return -1;
- }
-
- /**
- * Returns index of maximum revision which must be less or equal to {@code
upperBoundRev}.
- * If there is no such revision then {@code -1} will be returned.
- *
- * @param revs Revisions list.
- * @param upperBoundRev Revision upper bound.
- * @return Index of maximum revision or {@code -1} if there is no such
revision.
- */
- private static int maxRevisionIndex(List<Long> revs, long upperBoundRev) {
- for (int i = revs.size() - 1; i >= 0; i--) {
- long rev = revs.get(i);
-
- if (rev <= upperBoundRev) {
- return i;
- }
- }
-
- return -1;
- }
-
private Entry doGetValue(byte[] key, long lastRev) {
if (lastRev == 0) {
return EntryImpl.empty(key);
