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 fbc4e575a054cc38d8f8e99e56a54da095ae9ea5 Author: Andrey Gura <[email protected]> AuthorDate: Tue Apr 6 22:25:03 2021 +0300 IGNITE-14389 Added get and do smth semantic --- .../metastorage/server/KeyValueStorage.java | 12 +- .../server/SimpleInMemoryKeyValueStorage.java | 147 +++++++++---- .../server/SimpleInMemoryKeyValueStorageTest.java | 235 +++++++++++++++++++-- 3 files changed, 329 insertions(+), 65 deletions(-) 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 e245e08..ead1043 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 @@ -11,16 +11,20 @@ public interface KeyValueStorage { long updateCounter(); @NotNull - Entry put(byte[] key, byte[] value); - - @NotNull Entry get(byte[] key); @NotNull Entry get(byte[] key, long rev); + void put(byte[] key, byte[] value); + + @NotNull + Entry getAndPut(byte[] key, byte[] value); + + void remove(byte[] key); + @NotNull - Entry remove(byte[] key); + Entry getAndRemove(byte[] key); Iterator<Entry> iterate(byte[] key); 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 b764998..3700f4a 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 @@ -46,49 +46,26 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { return updCntr; } - @NotNull - @Override public Entry put(byte[] key, byte[] bytes) { + @Override public void put(byte[] key, byte[] value) { synchronized (mux) { - long curRev = ++rev; - - long curUpdCntr = ++updCntr; - - // Update keysIdx. - List<Long> revs = keysIdx.computeIfAbsent(key, k -> new ArrayList<>()); - - long lastRev = revs.isEmpty() ? 0 : lastRevision(revs); - - revs.add(curRev); - - // Update revsIdx. - NavigableMap<byte[], Value> entries = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); - - Value val = new Value(bytes, curUpdCntr); - - entries.put(key, val); + doPut(key, value); + } + } - revsIdx.put(curRev, entries); + @NotNull + @Override public Entry getAndPut(byte[] key, byte[] bytes) { + synchronized (mux) { + long lastRev = doPut(key, bytes); // Return previous value. - if (lastRev == 0) - return Entry.empty(key); - - NavigableMap<byte[], Value> lastRevVals = revsIdx.get(lastRev); - - Value lastVal = lastRevVals.get(key); - - Entry res = new Entry(key, lastVal.bytes(), lastRev, lastVal.updateCounter()); - - //TODO: notify watchers - - return res; + return doGetValue(key, lastRev); } } @NotNull @Override public Entry get(byte[] key) { synchronized (mux) { - return doGet(key, LATEST_REV); + return doGet(key, LATEST_REV, false); } } @@ -96,19 +73,31 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { @TestOnly @Override public Entry get(byte[] key, long rev) { synchronized (mux) { - return doGet(key, rev); + return doGet(key, rev, true); + } + } + + @Override + public void remove(byte[] key) { + synchronized (mux) { + Entry e = doGet(key, LATEST_REV, false); + + if (e.empty() || e.tombstone()) + return; + + doPut(key, TOMBSTONE); } } @NotNull - @Override public Entry remove(byte[] key) { + @Override public Entry getAndRemove(byte[] key) { synchronized (mux) { - Entry e = doGet(key, LATEST_REV); + Entry e = doGet(key, LATEST_REV, false); - if (e.value() == null) + if (e.empty() || e.tombstone()) return e; - return put(key, TOMBSTONE); + return getAndPut(key, TOMBSTONE); } } @@ -233,25 +222,91 @@ public class SimpleInMemoryKeyValueStorage implements KeyValueStorage { * @param rev Revision. * @return Entry for given key. */ - @NotNull private Entry doGet(byte[] key, long rev) { + @NotNull + private Entry doGet(byte[] key, long rev, boolean exactRev) { + assert rev == LATEST_REV && !exactRev || rev > LATEST_REV : + "Invalid arguments: [rev=" + rev + ", exactRev=" + exactRev + ']'; + List<Long> revs = keysIdx.get(key); if (revs == null || revs.isEmpty()) return Entry.empty(key); - long lrev = rev == LATEST_REV ? lastRevision(revs) : rev; + long lastRev; - NavigableMap<byte[], Value> entries = revsIdx.get(lrev); + if (rev == LATEST_REV) + lastRev = lastRevision(revs); + else + lastRev = exactRev ? rev : maxRevision(revs, rev); - if (entries == null || entries.isEmpty()) + // lastRev can be -1 if maxRevision return -1. + if (lastRev == -1) return Entry.empty(key); - Value val = entries.get(key); + return doGetValue(key, lastRev); + } + + /** + * Returns 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 Appropriate revision or {@code -1} if there is no such revision. + */ + private static long maxRevision(List<Long> revs, long upperBoundRev) { + int i = revs.size() - 1; + + for (; i >= 0 ; i--) { + long rev = revs.get(i); + + if (rev <= upperBoundRev) + return rev; + } + + return -1; + } + + @NotNull + private Entry doGetValue(byte[] key, long lastRev) { + if (lastRev == 0) + return Entry.empty(key); + + NavigableMap<byte[], Value> lastRevVals = revsIdx.get(lastRev); + + if (lastRevVals == null || lastRevVals.isEmpty()) + return Entry.empty(key); + + Value lastVal = lastRevVals.get(key); + + if (lastVal.tombstone()) + return Entry.tombstone(key, lastRev, lastVal.updateCounter()); + + return new Entry(key, lastVal.bytes() , lastRev, lastVal.updateCounter()); + } + + private long doPut(byte[] key, byte[] bytes) { + long curRev = ++rev; + + long curUpdCntr = ++updCntr; + + // Update keysIdx. + List<Long> revs = keysIdx.computeIfAbsent(key, k -> new ArrayList<>()); + + long lastRev = revs.isEmpty() ? 0 : lastRevision(revs); + + revs.add(curRev); + + // Update revsIdx. + NavigableMap<byte[], Value> entries = new TreeMap<>(LEXICOGRAPHIC_COMPARATOR); + + Value val = new Value(bytes, curUpdCntr); + + entries.put(key, val); - if (val.tombstone()) - return Entry.tombstone(key, lrev, val.updateCounter()); + revsIdx.put(curRev, entries); - return new Entry(key, val.bytes() , lrev, val.updateCounter()); + return lastRev; } private static boolean isPrefix(byte[] pref, byte[] term) { 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 eae76fd..5b797fc 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 @@ -22,7 +22,212 @@ class SimpleInMemoryKeyValueStorageTest { } @Test - void putGetRemoveCompact() { + public void put() { + byte[] key = k(1); + byte[] val = kv(1, 1); + + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + storage.put(key, val); + + assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); + + Entry e = storage.get(key); + + assertFalse(e.empty()); + assertFalse(e.tombstone()); + assertEquals(1, e.revision()); + assertEquals(1, e.updateCounter()); + + storage.put(key, val); + + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + + e = storage.get(key); + + assertFalse(e.empty()); + assertFalse(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + } + + @Test + public void getAndPut() { + byte[] key = k(1); + byte[] val = kv(1, 1); + + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + Entry e = storage.getAndPut(key, val); + + assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); + assertTrue(e.empty()); + assertFalse(e.tombstone()); + assertEquals(0, e.revision()); + assertEquals(0, e.updateCounter()); + + e = storage.getAndPut(key, val); + + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + assertFalse(e.empty()); + assertFalse(e.tombstone()); + assertEquals(1, e.revision()); + assertEquals(1, e.updateCounter()); + } + + @Test + public void remove() { + byte[] key = k(1); + byte[] val = kv(1, 1); + + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + // Remove non-existent entry. + storage.remove(key); + + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + storage.put(key, val); + + assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); + + // Remove existent entry. + storage.remove(key); + + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + + Entry e = storage.get(key); + + assertFalse(e.empty()); + assertTrue(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + + // Remove already removed entry (tombstone can't be removed). + storage.remove(key); + + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + + e = storage.get(key); + + assertFalse(e.empty()); + assertTrue(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + } + + @Test + public void getAndRemove() { + byte[] key = k(1); + byte[] val = kv(1, 1); + + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + // Remove non-existent entry. + Entry e = storage.getAndRemove(key); + + assertTrue(e.empty()); + assertEquals(0, storage.revision()); + assertEquals(0, storage.updateCounter()); + assertTrue(storage.get(key).empty()); + + storage.put(key, val); + + assertEquals(1, storage.revision()); + assertEquals(1, storage.updateCounter()); + + // Remove existent entry. + e = storage.getAndRemove(key); + + assertFalse(e.empty()); + assertFalse(e.tombstone()); + assertEquals(1, e.revision()); + assertEquals(1, e.updateCounter()); + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + + e = storage.get(key); + + assertFalse(e.empty()); + assertTrue(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + + // Remove already removed entry (tombstone can't be removed). + e = storage.getAndRemove(key); + + assertFalse(e.empty()); + assertTrue(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + + e = storage.get(key); + + assertFalse(e.empty()); + assertTrue(e.tombstone()); + assertEquals(2, e.revision()); + assertEquals(2, e.updateCounter()); + } + + @Test + public void getAfterRemove() { + byte[] key = k(1); + byte[] val = kv(1, 1); + + storage.getAndPut(key, val); + + storage.getAndRemove(key); + + Entry e = storage.get(key); + + assertEquals(2, storage.revision()); + assertEquals(2, storage.updateCounter()); + assertEquals(2, e.revision()); + assertTrue(e.tombstone()); + } + + @Test + public void getAndPutAfterRemove() { + byte[] key = k(1); + + byte[] val = kv(1, 1); + + storage.getAndPut(key, val); + + storage.getAndRemove(key); + + Entry e = storage.getAndPut(key, val); + + assertEquals(3, storage.revision()); + + assertEquals(3, storage.updateCounter()); + + assertEquals(2, e.revision()); + + assertTrue(e.tombstone()); + } + + @Test + public void putGetRemoveCompact() { byte[] key1 = k(1); byte[] val1_1 = kv(1, 1); byte[] val1_3 = kv(1, 3); @@ -34,7 +239,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(0, storage.updateCounter()); // Previous entry is empty. - Entry emptyEntry = storage.put(key1, val1_1); + Entry emptyEntry = storage.getAndPut(key1, val1_1); assertEquals(1, storage.revision()); assertEquals(1, storage.updateCounter()); @@ -53,7 +258,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(1, storage.updateCounter()); // Previous entry is empty. - emptyEntry = storage.put(key2, val2_2); + emptyEntry = storage.getAndPut(key2, val2_2); assertEquals(2, storage.revision()); assertEquals(2, storage.updateCounter()); @@ -72,7 +277,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(2, storage.updateCounter()); // Previous entry is not empty. - e1_1 = storage.put(key1, val1_3); + e1_1 = storage.getAndPut(key1, val1_3); assertFalse(e1_1.empty()); assertFalse(e1_1.tombstone()); @@ -96,7 +301,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(3, storage.updateCounter()); // Remove existing entry. - Entry e2_2 = storage.remove(key2); + Entry e2_2 = storage.getAndRemove(key2); assertFalse(e2_2.empty()); assertFalse(e2_2.tombstone()); @@ -108,7 +313,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(4, storage.updateCounter()); // Remove already removed entry. - Entry tombstoneEntry = storage.remove(key2); + Entry tombstoneEntry = storage.getAndRemove(key2); assertFalse(tombstoneEntry.empty()); assertTrue(tombstoneEntry.tombstone()); @@ -120,11 +325,11 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(4, storage.revision()); assertEquals(4, storage.updateCounter()); - assertTrue(storage.remove(key2).empty()); + assertTrue(storage.getAndRemove(key2).empty()); assertTrue(storage.get(key2).empty()); // Remove existing entry. - e1_3 = storage.remove(key1); + e1_3 = storage.getAndRemove(key1); assertFalse(e1_3.empty()); assertFalse(e1_3.tombstone()); @@ -136,7 +341,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(5, storage.updateCounter()); // Remove already removed entry. - tombstoneEntry = storage.remove(key1); + tombstoneEntry = storage.getAndRemove(key1); assertFalse(tombstoneEntry.empty()); assertTrue(tombstoneEntry.tombstone()); @@ -148,12 +353,12 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(5, storage.revision()); assertEquals(5, storage.updateCounter()); - assertTrue(storage.remove(key1).empty()); + assertTrue(storage.getAndRemove(key1).empty()); assertTrue(storage.get(key1).empty()); } @Test - void compact() { + public void compact() { assertEquals(0, storage.revision()); assertEquals(0, storage.updateCounter()); @@ -179,7 +384,7 @@ class SimpleInMemoryKeyValueStorageTest { assertEquals(6, storage.revision()); assertEquals(6, storage.updateCounter()); - storage.remove(k(3)); + storage.getAndRemove(k(3)); assertEquals(7, storage.revision()); assertEquals(7, storage.updateCounter()); @@ -218,7 +423,7 @@ class SimpleInMemoryKeyValueStorageTest { } @Test - void iterate() { + public void iterate() { TreeMap<String, String> expFooMap = new TreeMap<>(); TreeMap<String, String> expKeyMap = new TreeMap<>(); TreeMap<String, String> expZooMap = new TreeMap<>(); @@ -270,13 +475,13 @@ class SimpleInMemoryKeyValueStorageTest { byte[] val = valStr.getBytes(); - storage.put(key, val); + storage.getAndPut(key, val); } } private static void fill(KeyValueStorage storage, int keySuffix, int num) { for (int i = 0; i < num; i++) - storage.put(k(keySuffix), kv(keySuffix, i + 1)); + storage.getAndPut(k(keySuffix), kv(keySuffix, i + 1)); } private static byte[] k(int k) {
