This is an automated email from the ASF dual-hosted git repository. agura pushed a commit to branch ignite-14389 in repository https://gitbox.apache.org/repos/asf/ignite-3.git
commit a58026e019b4b6343357855d6b0df5c0b20c7b04 Author: Andrey Gura <[email protected]> AuthorDate: Wed Mar 31 18:18:09 2021 +0300 IGNITE-14398: Meta storage: added update counter --- .../ignite/internal/metastorage/server/Entry.java | 37 +++++++++--- .../metastorage/server/KeyValueStorage.java | 2 + .../server/SimpleInMemoryKeyValueStorage.java | 70 +++++++++++++--------- .../ignite/internal/metastorage/server/Value.java | 27 +++++++++ .../server/SimpleInMemoryKeyValueStorageTest.java | 29 +++++++++ 5 files changed, 130 insertions(+), 35 deletions(-) diff --git a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Entry.java b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Entry.java index 442aef9..263a88b 100644 --- a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Entry.java +++ b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Entry.java @@ -44,20 +44,31 @@ public class Entry { final private long rev; /** + * Update counter corresponds to this particular entry. + * <p> + * {@code updCntr == 0} for {@link #empty()} entry, + * {@code updCntr > 0} for regular and {@link #tombstone()} entries. + * </p> + */ + final private long updCntr; + + /** * Constructor. * * @param key Key bytes. Couldn't be {@code null}. * @param val Value bytes. Couldn't be {@code null}. * @param rev Revision. + * @param updCntr Update counter. */ // TODO: It seems user will never create Entry, so we can reduce constructor scope to protected or package-private and reuse it from two-place private constructor. - public Entry(@NotNull byte[] key, @NotNull byte[] val, long rev) { + public Entry(@NotNull byte[] key, @NotNull byte[] val, long rev, long updCntr) { assert key != null : "key can't be null"; assert val != null : "value can't be null"; this.key = key; this.val = val; this.rev = rev; + this.updCntr = updCntr; } /** @@ -65,13 +76,15 @@ public class Entry { * * @param key Key bytes. Couldn't be {@code null}. * @param rev Revision. + * @param updCntr Update counter. */ - private Entry(@NotNull byte[] key, long rev) { + private Entry(@NotNull byte[] key, long rev, long updCntr) { assert key != null : "key can't be null"; this.key = key; this.val = null; this.rev = rev; + this.updCntr = updCntr; } /** @@ -82,20 +95,22 @@ public class Entry { */ @NotNull public static Entry empty(byte[] key) { - return new Entry(key, 0); + return new Entry(key, 0, 0); } /** * Creates an instance of tombstone entry for a given key and a revision. * * @param key Key bytes. Couldn't be {@code null}. + * @param rev Revision. + * @param updCntr Update counter. * @return Empty entry. */ @NotNull - public static Entry tombstone(byte[] key, long rev) { + public static Entry tombstone(byte[] key, long rev, long updCntr) { assert rev > 0 : "rev must be positive for tombstone entry."; - return new Entry(key, rev); + return new Entry(key, rev, updCntr); } /** @@ -127,12 +142,20 @@ public class Entry { } /** + * Returns a update counter. + * @return Update counter. + */ + public long updateCounter() { + return updCntr; + } + + /** * Returns value which denotes whether entry is tombstone or not. * * @return {@code True} if entry is tombstone, otherwise - {@code false}. */ public boolean tombstone() { - return val == null && rev > 0; + return val == null && rev > 0 && updCntr > 0; } /** @@ -141,6 +164,6 @@ public class Entry { * @return {@code True} if entry is empty, otherwise - {@code false}. */ public boolean empty() { - return val == null && rev == 0; + return val == null && rev == 0 && updCntr == 0; } } diff --git a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java index 1bf6b78..e245e08 100644 --- a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java +++ b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/KeyValueStorage.java @@ -8,6 +8,8 @@ public interface KeyValueStorage { long revision(); + long updateCounter(); + @NotNull Entry put(byte[] key, byte[] value); diff --git a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java index 9059aec..b764998 100644 --- a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java +++ b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorage.java @@ -12,23 +12,25 @@ import java.util.TreeMap; import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.TestOnly; +import static org.apache.ignite.internal.metastorage.server.Value.TOMBSTONE; + /** * WARNING: Only for test purposes and only for non-distributed (one static instance) storage. */ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { private static final Comparator<byte[]> LEXICOGRAPHIC_COMPARATOR = Arrays::compare; - private static final byte[] TOMBSTONE = new byte[0]; - private static final long LATEST_REV = -1; private final Watcher watcher; private NavigableMap<byte[], List<Long>> keysIdx = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); - private NavigableMap<Long, NavigableMap<byte[], byte[]>> revsIdx = new TreeMap<>(); + private NavigableMap<Long, NavigableMap<byte[], Value>> revsIdx = new TreeMap<>(); - private long grev = 0; + private long rev; + + private long updCntr; private final Object mux = new Object(); @@ -37,35 +39,45 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { } @Override public long revision() { - return grev; + return rev; + } + + @Override public long updateCounter() { + return updCntr; } @NotNull - @Override public Entry put(byte[] key, byte[] val) { + @Override public Entry put(byte[] key, byte[] bytes) { synchronized (mux) { - long crev = ++grev; + long curRev = ++rev; + + long curUpdCntr = ++updCntr; // Update keysIdx. List<Long> revs = keysIdx.computeIfAbsent(key, k -> new ArrayList<>()); - long lrev = revs.isEmpty() ? 0 : lastRevision(revs); + long lastRev = revs.isEmpty() ? 0 : lastRevision(revs); - revs.add(crev); + revs.add(curRev); // Update revsIdx. - NavigableMap<byte[], byte[]> entries = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); + NavigableMap<byte[], Value> entries = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); + + Value val = new Value(bytes, curUpdCntr); entries.put(key, val); - revsIdx.put(crev, entries); + revsIdx.put(curRev, entries); // Return previous value. - if (lrev == 0) + if (lastRev == 0) return Entry.empty(key); - NavigableMap<byte[], byte[]> lastVal = revsIdx.get(lrev); + NavigableMap<byte[], Value> lastRevVals = revsIdx.get(lastRev); + + Value lastVal = lastRevVals.get(key); - Entry res = new Entry(key, lastVal.get(key), lrev); + Entry res = new Entry(key, lastVal.bytes(), lastRev, lastVal.updateCounter()); //TODO: notify watchers @@ -158,16 +170,18 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { //return new AbstractMap.SimpleImmutableEntry<>(key, null); } - NavigableMap<byte[], byte[]> vals = revsIdx.get(rev); + NavigableMap<byte[], Value> vals = revsIdx.get(rev); if (vals == null || vals.isEmpty()) { throw new IllegalStateException("vals == null || vals.isEmpty()"); //return new AbstractMap.SimpleImmutableEntry<>(key, null); } - byte[] val = vals.get(key); + Value val = vals.get(key); - return val == TOMBSTONE ? Entry.tombstone(key, rev) : new Entry(key, val, rev); + return val.tombstone() ? + Entry.tombstone(key, rev, val.updateCounter()) : + new Entry(key, val.bytes(), rev, val.updateCounter()); } } }; @@ -178,7 +192,7 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { synchronized (mux) { NavigableMap<byte[], List<Long>> compactedKeysIdx = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); - NavigableMap<Long, NavigableMap<byte[], byte[]>> compactedRevsIdx = new TreeMap<>(); + NavigableMap<Long, NavigableMap<byte[], Value>> compactedRevsIdx = new TreeMap<>(); keysIdx.forEach((key, revs) -> compactForKey(key, revs, compactedKeysIdx, compactedRevsIdx)); @@ -192,18 +206,18 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { byte[] key, List<Long> revs, NavigableMap<byte[], List<Long>> compactedKeysIdx, - NavigableMap<Long, NavigableMap<byte[], byte[]>> compactedRevsIdx + NavigableMap<Long, NavigableMap<byte[], Value>> compactedRevsIdx ) { Long lrev = lastRevision(revs); - NavigableMap<byte[], byte[]> kv = revsIdx.get(lrev); + NavigableMap<byte[], Value> kv = revsIdx.get(lrev); - byte[] lastVal = kv.get(key); + Value lastVal = kv.get(key); - if (lastVal != TOMBSTONE) { + if (!lastVal.tombstone()) { compactedKeysIdx.put(key, listOf(lrev)); - NavigableMap<byte[], byte[]> compactedKv = compactedRevsIdx.computeIfAbsent( + NavigableMap<byte[], Value> compactedKv = compactedRevsIdx.computeIfAbsent( lrev, k -> new TreeMap<>(LEXICOGRAPHIC_COMPARATOR) ); @@ -227,17 +241,17 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { long lrev = rev == LATEST_REV ? lastRevision(revs) : rev; - NavigableMap<byte[], byte[]> entries = revsIdx.get(lrev); + NavigableMap<byte[], Value> entries = revsIdx.get(lrev); if (entries == null || entries.isEmpty()) return Entry.empty(key); - byte[] val = entries.get(key); + Value val = entries.get(key); - if (val == TOMBSTONE) - return Entry.tombstone(key, lrev); + if (val.tombstone()) + return Entry.tombstone(key, lrev, val.updateCounter()); - return new Entry(key, val , lrev); + return new Entry(key, val.bytes() , lrev, val.updateCounter()); } private static boolean isPrefix(byte[] pref, byte[] term) { diff --git a/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Value.java b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Value.java new file mode 100644 index 0000000..250a5ea --- /dev/null +++ b/modules/metastorage-server/src/main/java/org/apache/ignite/internal/metastorage/server/Value.java @@ -0,0 +1,27 @@ +package org.apache.ignite.internal.metastorage.server; + +import org.jetbrains.annotations.NotNull; + +public class Value { + public static final byte[] TOMBSTONE = new byte[0]; + + private final byte[] bytes; + private final long updCntr; + + public Value(@NotNull byte[] bytes, long updCntr) { + this.bytes = bytes; + this.updCntr = updCntr; + } + + public byte[] bytes() { + return bytes; + } + + public long updateCounter() { + return updCntr; + } + + boolean tombstone() { + return bytes == TOMBSTONE; + } +} diff --git a/modules/metastorage-server/src/test/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorageTest.java b/modules/metastorage-server/src/test/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorageTest.java index f7fb17e..eae76fd 100644 --- a/modules/metastorage-server/src/test/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorageTest.java +++ b/modules/metastorage-server/src/test/java/org/apache/ignite/internal/metastorage/server/SimpleInMemoryKeyValueStorageTest.java @@ -31,11 +31,13 @@ class SimpleInMemoryKeyValueStorageTest { byte[] val2_2 = kv(2, 2); assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); // Previous entry is empty. Entry emptyEntry = storage.put(key1, val1_1); assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); assertTrue(emptyEntry.empty()); // Entry with rev == 1. @@ -46,12 +48,15 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key1, e1_1.key()); assertArrayEquals(val1_1, e1_1.value()); assertEquals(1, e1_1.revision()); + assertEquals(1, e1_1.updateCounter()); assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); // Previous entry is empty. emptyEntry = storage.put(key2, val2_2); assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); assertTrue(emptyEntry.empty()); // Entry with rev == 2. @@ -62,7 +67,9 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key2, e2.key()); assertArrayEquals(val2_2, e2.value()); assertEquals(2, e2.revision()); + assertEquals(2, e2.updateCounter()); assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); // Previous entry is not empty. e1_1 = storage.put(key1, val1_3); @@ -72,7 +79,9 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key1, e1_1.key()); assertArrayEquals(val1_1, e1_1.value()); assertEquals(1, e1_1.revision()); + assertEquals(1, e1_1.updateCounter()); assertEquals(3, storage.revision()); + assertEquals(3, storage.updateCounter()); // Entry with rev == 3. Entry e1_3 = storage.get(key1); @@ -82,7 +91,9 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key1, e1_3.key()); assertArrayEquals(val1_3, e1_3.value()); assertEquals(3, e1_3.revision()); + assertEquals(3, e1_3.updateCounter()); assertEquals(3, storage.revision()); + assertEquals(3, storage.updateCounter()); // Remove existing entry. Entry e2_2 = storage.remove(key2); @@ -92,7 +103,9 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key2, e2_2.key()); assertArrayEquals(val2_2, e2_2.value()); assertEquals(2, e2_2.revision()); + assertEquals(2, e2_2.updateCounter()); assertEquals(4, storage.revision()); // Storage revision is changed. + assertEquals(4, storage.updateCounter()); // Remove already removed entry. Entry tombstoneEntry = storage.remove(key2); @@ -100,11 +113,13 @@ class SimpleInMemoryKeyValueStorageTest { assertFalse(tombstoneEntry.empty()); assertTrue(tombstoneEntry.tombstone()); assertEquals(4, storage.revision()); // Storage revision is not changed. + assertEquals(4, storage.updateCounter()); // Compact and check that tombstones are removed. storage.compact(); assertEquals(4, storage.revision()); + assertEquals(4, storage.updateCounter()); assertTrue(storage.remove(key2).empty()); assertTrue(storage.get(key2).empty()); @@ -116,7 +131,9 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(key1, e1_3.key()); assertArrayEquals(val1_3, e1_3.value()); assertEquals(3, e1_3.revision()); + assertEquals(3, e1_3.updateCounter()); assertEquals(5, storage.revision()); // Storage revision is changed. + assertEquals(5, storage.updateCounter()); // Remove already removed entry. tombstoneEntry = storage.remove(key1); @@ -124,11 +141,13 @@ class SimpleInMemoryKeyValueStorageTest { assertFalse(tombstoneEntry.empty()); assertTrue(tombstoneEntry.tombstone()); assertEquals(5, storage.revision()); // // Storage revision is not changed. + assertEquals(5, storage.updateCounter()); // Compact and check that tombstones are removed. storage.compact(); assertEquals(5, storage.revision()); + assertEquals(5, storage.updateCounter()); assertTrue(storage.remove(key1).empty()); assertTrue(storage.get(key1).empty()); } @@ -136,33 +155,40 @@ class SimpleInMemoryKeyValueStorageTest { @Test void compact() { assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); // Compact empty. storage.compact(); assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); // Compact non-empty. fill(storage, 1, 1); assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); fill(storage, 2, 2); assertEquals(3, storage.revision()); + assertEquals(3, storage.updateCounter()); fill(storage, 3, 3); assertEquals(6, storage.revision()); + assertEquals(6, storage.updateCounter()); storage.remove(k(3)); assertEquals(7, storage.revision()); + assertEquals(7, storage.updateCounter()); assertTrue(storage.get(k(3)).tombstone()); storage.compact(); assertEquals(7, storage.revision()); + assertEquals(7, storage.updateCounter()); Entry e1 = storage.get(k(1)); @@ -171,6 +197,7 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(k(1), e1.key()); assertArrayEquals(kv(1,1), e1.value()); assertEquals(1, e1.revision()); + assertEquals(1, e1.updateCounter()); Entry e2 = storage.get(k(2)); @@ -180,6 +207,7 @@ class SimpleInMemoryKeyValueStorageTest { assertArrayEquals(kv(2,2), e2.value()); assertTrue(storage.get(k(2), 2).empty()); assertEquals(3, e2.revision()); + assertEquals(3, e2.updateCounter()); Entry e3 = storage.get(k(3)); @@ -200,6 +228,7 @@ class SimpleInMemoryKeyValueStorageTest { fill("zoo", storage, expZooMap); assertEquals(300, storage.revision()); + assertEquals(300, storage.updateCounter()); assertIterate("key", storage, expKeyMap); assertIterate("zoo", storage, expZooMap);
