You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ag...@apache.org on 2021/04/28 23:44:45 UTC
[ignite-3] 02/07: IGNITE-14398: Meta storage: added update counter
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 097fa8fd93ff79e5fc85b6c9d5e23e1c473fa244
Author: Andrey Gura <ag...@apache.org>
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);