Avoid full cache scanning for pruning
The full cache scanning should be avoided at all costs
because of the massive CPU and JVM heap utilisation due
to the deserialisation of the cached values.
The prune() of the cache cannot rely on any ordering
of entries and therefore needs another data structure
to remember the historical insertion ordering of the
keys.
Use an in-memory linked hash set so that MRU keys are propagated by
remove-add on each key access to the tail of it whereas LRU key is
always available as a head key (therefore it is cheap to remove LRU
keys). In addition to key store also the value insertion time so that
expiring entries for maxAge is also possible.
TODO: The queue is currently in memory which isn't going
to work across restarts. The queue needs to be persisted
to disk as a circular file with automatic reorganiation.
Bug: Issue 15121
Change-Id: Ifa3068e2d27713b452c4bcab6a611e3c9b511868
diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndex.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndex.java
new file mode 100644
index 0000000..34e3eac
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndex.java
@@ -0,0 +1,127 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed 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 com.googlesource.gerrit.modules.cache.chroniclemap;
+
+import static java.util.stream.Collectors.toUnmodifiableSet;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.errorprone.annotations.CompatibleWith;
+import java.util.Collections;
+import java.util.LinkedHashSet;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
+import java.util.function.Consumer;
+
+class CacheKeysIndex<T> {
+ /** As opposed to TimedValue keys are equal when their key equals. */
+ class TimedKey {
+ private final T key;
+ private final long created;
+
+ private TimedKey(T key, long created) {
+ this.key = key;
+ this.created = created;
+ }
+
+ T getKey() {
+ return key;
+ }
+
+ long getCreated() {
+ return created;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o instanceof CacheKeysIndex.TimedKey) {
+ @SuppressWarnings("unchecked")
+ TimedKey other = (TimedKey) o;
+ return Objects.equals(key, other.key);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(key);
+ }
+ }
+
+ private final Set<TimedKey> keys;
+
+ CacheKeysIndex() {
+ this.keys = Collections.synchronizedSet(new LinkedHashSet<>());
+ }
+
+ @SuppressWarnings("unchecked")
+ void add(@CompatibleWith("T") Object key, long created) {
+ Objects.requireNonNull(key, "Key value cannot be [null].");
+ TimedKey timedKey = new TimedKey((T) key, created);
+
+ // bubble up MRU key by re-adding it to a set
+ keys.remove(timedKey);
+ keys.add(timedKey);
+ }
+
+ void refresh(T key) {
+ add(key, System.currentTimeMillis());
+ }
+
+ void removeAndConsumeKeysOlderThan(long time, Consumer<T> consumer) {
+ Set<TimedKey> toRemoveAndConsume;
+ synchronized (keys) {
+ toRemoveAndConsume =
+ keys.stream().filter(key -> key.created < time).collect(toUnmodifiableSet());
+ }
+ toRemoveAndConsume.forEach(
+ key -> {
+ keys.remove(key);
+ consumer.accept(key.getKey());
+ });
+ }
+
+ boolean removeAndConsumeLruKey(Consumer<T> consumer) {
+ Optional<TimedKey> lruKey;
+ synchronized (keys) {
+ lruKey = keys.stream().findFirst();
+ }
+
+ return lruKey
+ .map(
+ key -> {
+ keys.remove(key);
+ consumer.accept(key.getKey());
+ return true;
+ })
+ .orElse(false);
+ }
+
+ void invalidate(@CompatibleWith("T") Object key) {
+ keys.remove(key);
+ }
+
+ void clear() {
+ keys.clear();
+ }
+
+ @VisibleForTesting
+ Set<TimedKey> keys() {
+ return keys;
+ }
+}
diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfig.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfig.java
index 1235e53..7011f65 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfig.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfig.java
@@ -35,7 +35,6 @@
private final Duration refreshAfterWrite;
private final int maxBloatFactor;
private final int percentageFreeSpaceEvictionThreshold;
- private final int percentageHotKeys;
private final String configKey;
public interface Factory {
@@ -115,23 +114,12 @@
configKey,
"percentageFreeSpaceEvictionThreshold",
Defaults.percentageFreeSpaceEvictionThreshold());
-
- this.percentageHotKeys =
- cfg.getInt("cache", configKey, "percentageHotKeys", Defaults.percentageHotKeys());
-
- if (percentageHotKeys <= 0 || percentageHotKeys >= 100) {
- throw new IllegalArgumentException("Invalid 'percentageHotKeys': should be in range [1-99]");
- }
}
public int getPercentageFreeSpaceEvictionThreshold() {
return percentageFreeSpaceEvictionThreshold;
}
- public int getpercentageHotKeys() {
- return percentageHotKeys;
- }
-
public Duration getExpireAfterWrite() {
return expireAfterWrite;
}
@@ -178,7 +166,6 @@
public static final int DEFAULT_MAX_BLOAT_FACTOR = 1;
public static final int DEFAULT_PERCENTAGE_FREE_SPACE_EVICTION_THRESHOLD = 90;
- public static final int DEFAULT_PERCENTAGE_HOT_KEYS = 50;
private static final ImmutableMap<String, DefaultConfig> defaultMap =
new ImmutableMap.Builder<String, DefaultConfig>()
@@ -224,9 +211,5 @@
public static int percentageFreeSpaceEvictionThreshold() {
return DEFAULT_PERCENTAGE_FREE_SPACE_EVICTION_THRESHOLD;
}
-
- public static int percentageHotKeys() {
- return DEFAULT_PERCENTAGE_HOT_KEYS;
- }
}
}
diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheFactory.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheFactory.java
index 1161699..98d7f42 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheFactory.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheFactory.java
@@ -117,11 +117,7 @@
cache =
new ChronicleMapCacheImpl<>(
- in,
- config,
- metricMaker,
- memLoader,
- new InMemoryCacheLoadingFromStoreImpl<>(mem, false));
+ in, config, memLoader, new InMemoryCacheLoadingFromStoreImpl<>(mem, false));
} catch (IOException e) {
throw new UncheckedIOException(e);
@@ -169,11 +165,7 @@
cache =
new ChronicleMapCacheImpl<>(
- in,
- config,
- metricMaker,
- memLoader,
- new InMemoryCacheLoadingFromStoreImpl<>(mem, true));
+ in, config, memLoader, new InMemoryCacheLoadingFromStoreImpl<>(mem, true));
} catch (IOException e) {
throw new UncheckedIOException(e);
}
diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheImpl.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheImpl.java
index b704a7b..12a463b 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheImpl.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheImpl.java
@@ -13,11 +13,11 @@
// limitations under the License.
package com.googlesource.gerrit.modules.cache.chroniclemap;
+import com.google.common.annotations.VisibleForTesting;
import com.google.common.cache.AbstractLoadingCache;
import com.google.common.cache.CacheStats;
import com.google.common.flogger.FluentLogger;
import com.google.common.util.concurrent.MoreExecutors;
-import com.google.gerrit.metrics.Description;
import com.google.gerrit.metrics.DisabledMetricMaker;
import com.google.gerrit.metrics.MetricMaker;
import com.google.gerrit.server.cache.PersistentCache;
@@ -27,6 +27,7 @@
import java.sql.Timestamp;
import java.time.Duration;
import java.time.Instant;
+import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.atomic.LongAdder;
@@ -45,7 +46,7 @@
private final LongAdder loadSuccessCount = new LongAdder();
private final LongAdder loadExceptionCount = new LongAdder();
private final LongAdder totalLoadTime = new LongAdder();
- private final InMemoryLRU<K> hotEntries;
+ private final CacheKeysIndex<K> keysIndex;
private final PersistentCacheDef<K, V> cacheDefinition;
private final ChronicleMapCacheLoader<K, V> memLoader;
private final InMemoryCache<K, V> mem;
@@ -56,37 +57,26 @@
this.cacheDefinition = def;
this.config = config;
- this.hotEntries =
- new InMemoryLRU<>(
- (int) Math.max(config.getMaxEntries() * config.getpercentageHotKeys() / 100, 1));
+ this.keysIndex = new CacheKeysIndex<>();
this.store = createOrRecoverStore(def, config, metricMaker);
this.memLoader =
new ChronicleMapCacheLoader<>(
MoreExecutors.directExecutor(), store, config.getExpireAfterWrite());
this.mem = memLoader.asInMemoryCacheBypass();
-
- ChronicleMapCacheMetrics metrics = new ChronicleMapCacheMetrics(metricMaker);
- metrics.registerCallBackMetrics(def.name(), this);
}
ChronicleMapCacheImpl(
PersistentCacheDef<K, V> def,
ChronicleMapCacheConfig config,
- MetricMaker metricMaker,
ChronicleMapCacheLoader<K, V> memLoader,
InMemoryCache<K, V> mem) {
this.cacheDefinition = def;
this.config = config;
- this.hotEntries =
- new InMemoryLRU<>(
- (int) Math.max(config.getMaxEntries() * config.getpercentageHotKeys() / 100, 1));
+ this.keysIndex = new CacheKeysIndex<>();
this.memLoader = memLoader;
this.mem = mem;
this.store = memLoader.getStore();
-
- ChronicleMapCacheMetrics metrics = new ChronicleMapCacheMetrics(metricMaker);
- metrics.registerCallBackMetrics(def.name(), this);
}
@SuppressWarnings({"unchecked", "cast", "rawtypes"})
@@ -145,36 +135,6 @@
return cacheDefinition;
}
- private static class ChronicleMapCacheMetrics {
-
- private final MetricMaker metricMaker;
-
- ChronicleMapCacheMetrics(MetricMaker metricMaker) {
- this.metricMaker = metricMaker;
- }
-
- <K, V> void registerCallBackMetrics(String name, ChronicleMapCacheImpl<K, V> cache) {
- String sanitizedName = metricMaker.sanitizeMetricName(name);
- String HOT_KEYS_CAPACITY_METRIC = "cache/chroniclemap/hot_keys_capacity_" + sanitizedName;
- String HOT_KEYS_SIZE_METRIC = "cache/chroniclemap/hot_keys_size_" + sanitizedName;
-
- metricMaker.newConstantMetric(
- HOT_KEYS_CAPACITY_METRIC,
- cache.hotEntries.getCapacity(),
- new Description(
- String.format(
- "The number of hot cache keys for %s cache that can be kept in memory", name)));
-
- metricMaker.newCallbackMetric(
- HOT_KEYS_SIZE_METRIC,
- Integer.class,
- new Description(
- String.format(
- "The number of hot cache keys for %s cache that are currently in memory", name)),
- cache.hotEntries::size);
- }
- }
-
public ChronicleMapCacheConfig getConfig() {
return config;
}
@@ -187,6 +147,7 @@
return null;
}
+ keysIndex.add(objKey, timedValue.getCreated());
return timedValue.getValue();
}
@@ -199,6 +160,9 @@
if (needsRefresh(valueHolder.getCreated())) {
store.remove(keyWrapper);
mem.refresh(key);
+ keysIndex.refresh(key);
+ } else {
+ keysIndex.add(key, valueHolder.getCreated());
}
return valueHolder.getValue();
}
@@ -211,11 +175,12 @@
@Override
public V get(K key, Callable<? extends V> valueLoader) throws ExecutionException {
try {
- return mem.get(key, () -> getFromStore(key, valueLoader)).getValue();
+ TimedValue<V> value = mem.get(key, () -> getFromStore(key, valueLoader));
+ keysIndex.add(key, value.getCreated());
+ return value.getValue();
+ } catch (ExecutionException e) {
+ throw e;
} catch (Exception e) {
- if (e instanceof ExecutionException) {
- throw (ExecutionException) e;
- }
throw new ExecutionException(e);
}
}
@@ -259,6 +224,7 @@
KeyWrapper<?> wrappedKey = new KeyWrapper<>(key);
if (store.tryPut((KeyWrapper<K>) wrappedKey, (TimedValue<V>) wrappedValue)) {
mem.put((K) key, (TimedValue<V>) wrappedValue);
+ keysIndex.add(key, wrappedValue.getCreated());
}
}
@@ -276,6 +242,7 @@
public void putUnchecked(KeyWrapper<Object> wrappedKey, TimedValue<Object> wrappedValue) {
if (store.tryPut((KeyWrapper<K>) wrappedKey, (TimedValue<V>) wrappedValue)) {
mem.put((K) wrappedKey.getValue(), (TimedValue<V>) wrappedValue);
+ keysIndex.add(wrappedKey.getValue(), wrappedValue.getCreated());
}
}
@@ -284,27 +251,20 @@
TimedValue<V> timedVal = new TimedValue<>(val);
if (putTimedToStore(key, timedVal)) {
mem.put(key, timedVal);
+ keysIndex.add(key, timedVal.getCreated());
}
}
boolean putTimedToStore(K key, TimedValue<V> timedVal) {
KeyWrapper<K> wrappedKey = new KeyWrapper<>(key);
- boolean putSuccess = store.tryPut(wrappedKey, timedVal);
- if (putSuccess) {
- hotEntries.add(key);
- }
- return putSuccess;
+ return store.tryPut(wrappedKey, timedVal);
}
public void prune() {
if (!config.getExpireAfterWrite().isZero()) {
- store.forEachEntry(
- c -> {
- if (memLoader.expired(c.value().get().getCreated())) {
- hotEntries.remove(c.key().get().getValue());
- c.context().remove(c);
- }
- });
+ long expirationTime = System.currentTimeMillis() - config.getExpireAfterWrite().toMillis();
+ keysIndex.removeAndConsumeKeysOlderThan(
+ expirationTime, key -> store.remove(new KeyWrapper<>(key)));
}
if (runningOutOfFreeSpace()) {
@@ -324,13 +284,8 @@
}
private void evictColdEntries() {
- store.forEachEntryWhile(
- e -> {
- if (!hotEntries.contains(e.key().get().getValue())) {
- e.doRemove();
- }
- return runningOutOfFreeSpace();
- });
+ while (runningOutOfFreeSpace()
+ && keysIndex.removeAndConsumeLruKey(key -> store.remove(new KeyWrapper<>(key)))) ;
}
@SuppressWarnings("unchecked")
@@ -339,14 +294,14 @@
KeyWrapper<K> wrappedKey = (KeyWrapper<K>) new KeyWrapper<>(key);
store.remove(wrappedKey);
mem.invalidate(key);
- hotEntries.remove((K) key);
+ keysIndex.invalidate(key);
}
@Override
public void invalidateAll() {
store.clear();
- hotEntries.invalidateAll();
mem.invalidateAll();
+ keysIndex.clear();
}
ChronicleMap<KeyWrapper<K>, TimedValue<V>> getStore() {
@@ -387,4 +342,9 @@
public String name() {
return store.name();
}
+
+ @VisibleForTesting
+ Set<CacheKeysIndex<K>.TimedKey> keys() {
+ return keysIndex.keys();
+ }
}
diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRU.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRU.java
deleted file mode 100644
index dcf7a68..0000000
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRU.java
+++ /dev/null
@@ -1,77 +0,0 @@
-// Copyright (C) 2020 The Android Open Source Project
-//
-// Licensed 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 com.googlesource.gerrit.modules.cache.chroniclemap;
-
-import com.google.common.annotations.VisibleForTesting;
-import java.util.Collections;
-import java.util.LinkedHashMap;
-import java.util.Map;
-
-public class InMemoryLRU<K> {
-
- private final Map<K, Boolean> LRUMap;
-
- private static final Boolean dummyValue = Boolean.TRUE;
- private final int capacity;
-
- public InMemoryLRU(int capacity) {
- this.capacity = capacity;
-
- LRUMap =
- Collections.synchronizedMap(
- new LinkedHashMap<K, Boolean>(capacity, 0.75f, true) {
- private static final long serialVersionUID = 1L;
-
- @Override
- protected boolean removeEldestEntry(Map.Entry<K, Boolean> eldest) {
- return size() > capacity;
- }
- });
- }
-
- public void add(K objKey) {
- LRUMap.putIfAbsent(objKey, dummyValue);
- }
-
- public boolean contains(K key) {
- return LRUMap.containsKey(key);
- }
-
- /**
- * Remove a key from the map
- *
- * @param key element to remove from the map
- * @return true when key was in the map, null otherwise
- */
- public Boolean remove(K key) {
- return LRUMap.remove(key);
- }
-
- public void invalidateAll() {
- LRUMap.clear();
- }
-
- public int size() {
- return LRUMap.size();
- }
-
- @VisibleForTesting
- protected Object[] toArray() {
- return LRUMap.keySet().toArray();
- }
-
- public int getCapacity() {
- return capacity;
- }
-}
diff --git a/src/main/resources/Documentation/config.md b/src/main/resources/Documentation/config.md
index 60d4ae1..0cacd22 100644
--- a/src/main/resources/Documentation/config.md
+++ b/src/main/resources/Documentation/config.md
@@ -128,24 +128,6 @@
If the cache expands you will see an increase in the available free space.
[official documentation](https://javadoc.io/static/net.openhft/chronicle-map/3.20.83/net/openhft/chronicle/map/ChronicleMap.html#percentageFreeSpace--)
-* `percentageHotKeys`
-: The percentage of _hot_ keys that can be kept in-memory.
-When performing evictions, _hot_ keys will be preserved and only _cold_ keys
-will be evicted from chronicle-map, in random order.
-
-This value implies a trade-off between eviction speed and eviction accuracy.
-
-The smaller the number of hotKeys allocated, the quicker the eviction phase
-will be. However, this will increase the chance of evicting entries that were
-recently accessed.
-
-Conversely, the higher the number of hotKeys allocated, the higher will be the
-accuracy in evicting only recently accessed keys, at the price of a longer
-time spent doing evictions.
-
-In order to ensure there is always a cold entry to be evicted, the number of
-`percentageHotKeys` always needs to be less than `maxEntries`.
-
*Constraints*: [1-99]
*Default*: 50
diff --git a/src/main/resources/Documentation/metrics.md b/src/main/resources/Documentation/metrics.md
index 2928708..565fe62 100644
--- a/src/main/resources/Documentation/metrics.md
+++ b/src/main/resources/Documentation/metrics.md
@@ -20,11 +20,5 @@
* cache/chroniclemap/max_autoresizes_<cache-name>
: The maximum number of times the cache can automatically expand its capacity.
-* cache/chroniclemap/hot_keys_capacity_<cache-name>
- : Constant number of hot keys for the cache that can be kept in memory.
-
-* cache/chroniclemap/hot_keys_size_<cache-name>
- : The number of hot keys for the cache that are currently in memory.
-
* "cache/chroniclemap/store_put_failures_<cache-name>
: The number of errors caught when inserting entries in chronicle-map store
\ No newline at end of file
diff --git a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndexTest.java b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndexTest.java
new file mode 100644
index 0000000..405e5a5
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndexTest.java
@@ -0,0 +1,108 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed 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 com.googlesource.gerrit.modules.cache.chroniclemap;
+
+import static com.google.common.truth.Truth.assertThat;
+import static java.util.stream.Collectors.toList;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.verifyNoInteractions;
+
+import java.util.List;
+import java.util.function.Consumer;
+import org.junit.Before;
+import org.junit.Test;
+
+public class CacheKeysIndexTest {
+ private CacheKeysIndex<String> index;
+
+ @Before
+ public void setup() {
+ index = new CacheKeysIndex<>();
+ }
+
+ @Test
+ public void add_shouldUpdateElementPositionWhenAlreadyInSet() {
+ index.add("foo", 2L);
+ index.add("bar", 1L);
+ assertThat(keys(index)).containsExactly("foo", "bar");
+
+ index.add("foo", 1L);
+ assertThat(keys(index)).containsExactly("bar", "foo");
+ }
+
+ @Test
+ public void add_shouldUpdateElementInsertionTimeWhenNewerGetsAdded() {
+ index.add("foo", 1L);
+ index.add("foo", 2L);
+
+ CacheKeysIndex<String>.TimedKey key = index.keys().iterator().next();
+ assertThat(key.getKey()).isEqualTo("foo");
+ assertThat(key.getCreated()).isEqualTo(2L);
+ }
+
+ @Test
+ public void refresh_shouldRefreshInsertionTimeOnRefresh() {
+ index.add("foo", 1L);
+ index.refresh("foo");
+
+ CacheKeysIndex<String>.TimedKey key = index.keys().iterator().next();
+ assertThat(key.getKey()).isEqualTo("foo");
+ assertThat(key.getCreated()).isGreaterThan(1L);
+ }
+
+ @Test
+ @SuppressWarnings("unchecked")
+ public void remove_shouldRemoveAndConsumeKeysOlderThan() {
+ long than = 5l;
+ index.add("newerThan", 10L);
+ index.add("olderThan", 2L);
+ Consumer<String> consumer = mock(Consumer.class);
+
+ index.removeAndConsumeKeysOlderThan(than, consumer);
+
+ verify(consumer).accept("olderThan");
+ assertThat(keys(index)).containsExactly("newerThan");
+ }
+
+ @Test
+ @SuppressWarnings("unchecked")
+ public void remove_shouldReturnFalseIfThereIsNoLruToRemove() {
+ Consumer<String> consumer = mock(Consumer.class);
+
+ boolean actual = index.removeAndConsumeLruKey(consumer);
+
+ assertThat(actual).isEqualTo(false);
+ verifyNoInteractions(consumer);
+ }
+
+ @Test
+ @SuppressWarnings("unchecked")
+ public void remove_shouldRemoveAndConsumeLruKey() {
+ index.add("older", 1L);
+ index.add("newer", 1L);
+ Consumer<String> consumer = mock(Consumer.class);
+
+ boolean actual = index.removeAndConsumeLruKey(consumer);
+
+ assertThat(actual).isEqualTo(true);
+ verify(consumer).accept("older");
+ assertThat(keys(index)).containsExactly("newer");
+ }
+
+ private static List<String> keys(CacheKeysIndex<String> index) {
+ return index.keys().stream().map(CacheKeysIndex.TimedKey::getKey).collect(toList());
+ }
+}
diff --git a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfigTest.java b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfigTest.java
index 8cb28c1..08f5977 100644
--- a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfigTest.java
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheConfigTest.java
@@ -14,13 +14,11 @@
package com.googlesource.gerrit.modules.cache.chroniclemap;
import static com.google.common.truth.Truth.assertThat;
-import static com.google.gerrit.testing.GerritJUnit.assertThrows;
import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_AVG_KEY_SIZE;
import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_AVG_VALUE_SIZE;
import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_MAX_BLOAT_FACTOR;
import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_MAX_ENTRIES;
import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_PERCENTAGE_FREE_SPACE_EVICTION_THRESHOLD;
-import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.DEFAULT_PERCENTAGE_HOT_KEYS;
import com.google.gerrit.server.config.SitePaths;
import java.io.File;
@@ -177,37 +175,6 @@
.isEqualTo(DEFAULT_PERCENTAGE_FREE_SPACE_EVICTION_THRESHOLD);
}
- @Test
- public void shouldProvidePercentageHotKeysDefault() throws Exception {
- assertThat(configUnderTest(gerritConfig).getpercentageHotKeys())
- .isEqualTo(DEFAULT_PERCENTAGE_HOT_KEYS);
- }
-
- @Test
- public void shouldProvidePercentageHotKeysWhenConfigured() throws Exception {
- int percentageHotKeys = 20;
- gerritConfig.setInt("cache", cacheKey, "percentageHotKeys", percentageHotKeys);
- gerritConfig.save();
-
- assertThat(configUnderTest(gerritConfig).getpercentageHotKeys()).isEqualTo(percentageHotKeys);
- }
-
- @Test
- public void shouldThrowWhenPercentageHotKeysIs100() throws Exception {
- gerritConfig.setInt("cache", cacheKey, "percentageHotKeys", 100);
- gerritConfig.save();
-
- assertThrows(IllegalArgumentException.class, () -> configUnderTest(gerritConfig));
- }
-
- @Test
- public void shouldThrowWhenPercentageHotKeysIs0() throws Exception {
- gerritConfig.setInt("cache", cacheKey, "percentageHotKeys", 0);
- gerritConfig.save();
-
- assertThrows(IllegalArgumentException.class, () -> configUnderTest(gerritConfig));
- }
-
private ChronicleMapCacheConfig configUnderTest(StoredConfig gerritConfig) {
File persistentFile =
ChronicleMapCacheFactory.fileName(
diff --git a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheTest.java b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheTest.java
index 0041c53..ecc457a 100644
--- a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheTest.java
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/ChronicleMapCacheTest.java
@@ -306,7 +306,6 @@
final String fooValue = "foo";
gerritConfig.setInt("cache", testCacheName, "maxEntries", 2);
- gerritConfig.setInt("cache", testCacheName, "percentageHotKeys", 10);
gerritConfig.setInt("cache", testCacheName, "avgKeySize", "foo1".getBytes().length);
gerritConfig.setInt("cache", testCacheName, "avgValueSize", valueSize(fooValue));
gerritConfig.save();
@@ -326,7 +325,6 @@
throws Exception {
final String fooValue = "foo";
gerritConfig.setInt("cache", testCacheName, "maxEntries", 2);
- gerritConfig.setInt("cache", testCacheName, "percentageHotKeys", 10);
gerritConfig.setInt("cache", testCacheName, "avgKeySize", "foo1".getBytes().length);
gerritConfig.setInt("cache", testCacheName, "avgValueSize", valueSize(fooValue));
gerritConfig.save();
@@ -347,7 +345,6 @@
public void shouldEvictEntriesUntilFreeSpaceIsRecovered() throws Exception {
final int uuidSize = valueSize(UUID.randomUUID().toString());
gerritConfig.setInt("cache", "foo", "maxEntries", 50);
- gerritConfig.setInt("cache", "foo", "percentageHotKeys", 10);
gerritConfig.setInt("cache", "foo", "avgKeySize", uuidSize);
gerritConfig.setInt("cache", "foo", "avgValueSize", uuidSize);
gerritConfig.save();
@@ -458,65 +455,11 @@
}
@Test
- public void shouldTriggerHotKeysCapacityCacheMetric() throws Exception {
+ public void shouldResetKeysIndexWhenInvalidateAll() throws Exception {
String cachedValue = UUID.randomUUID().toString();
- int percentageHotKeys = 60;
- int maxEntries = 10;
- int expectedCapacity = 6;
- String hotKeysCapacityMetricName = "cache/chroniclemap/hot_keys_capacity_" + testCacheName;
- gerritConfig.setInt("cache", testCacheName, "maxEntries", maxEntries);
- gerritConfig.setInt("cache", testCacheName, "percentageHotKeys", percentageHotKeys);
- gerritConfig.save();
-
- newCacheWithMetrics(testCacheName, cachedValue);
-
- assertThat(getMetric(hotKeysCapacityMetricName).getValue()).isEqualTo(expectedCapacity);
- }
-
- @Test
- public void shouldTriggerHotKeysSizeCacheMetric() throws Exception {
- String cachedValue = UUID.randomUUID().toString();
- int percentageHotKeys = 30;
int maxEntries = 10;
int maxHotKeyCapacity = 3;
- final Duration METRIC_TRIGGER_TIMEOUT = Duration.ofSeconds(2);
- String hotKeysSizeMetricName = "cache/chroniclemap/hot_keys_size_" + testCacheName;
gerritConfig.setInt("cache", testCacheName, "maxEntries", maxEntries);
- gerritConfig.setInt("cache", testCacheName, "percentageHotKeys", percentageHotKeys);
- gerritConfig.save();
-
- ChronicleMapCacheImpl<String, String> cache = newCacheWithMetrics(testCacheName, cachedValue);
-
- assertThat(getMetric(hotKeysSizeMetricName).getValue()).isEqualTo(0);
-
- for (int i = 0; i < maxHotKeyCapacity; i++) {
- cache.put(cachedValue + i, cachedValue);
- }
-
- WaitUtil.waitUntil(
- () -> (int) getMetric(hotKeysSizeMetricName).getValue() == maxHotKeyCapacity,
- METRIC_TRIGGER_TIMEOUT);
-
- cache.put(cachedValue + maxHotKeyCapacity + 1, cachedValue);
-
- assertThrows(
- InterruptedException.class,
- () ->
- WaitUtil.waitUntil(
- () -> (int) getMetric(hotKeysSizeMetricName).getValue() > maxHotKeyCapacity,
- METRIC_TRIGGER_TIMEOUT));
- }
-
- @Test
- public void shouldResetHotKeysWhenInvalidateAll() throws Exception {
- String cachedValue = UUID.randomUUID().toString();
- int percentageHotKeys = 30;
- int maxEntries = 10;
- int maxHotKeyCapacity = 3;
- final Duration METRIC_TRIGGER_TIMEOUT = Duration.ofSeconds(2);
- String hotKeysSizeMetricName = "cache/chroniclemap/hot_keys_size_" + testCacheName;
- gerritConfig.setInt("cache", testCacheName, "maxEntries", maxEntries);
- gerritConfig.setInt("cache", testCacheName, "percentageHotKeys", percentageHotKeys);
gerritConfig.save();
ChronicleMapCacheImpl<String, String> cache = newCacheWithMetrics(testCacheName, cachedValue);
@@ -525,33 +468,24 @@
cache.put(cachedValue + i, cachedValue);
}
- WaitUtil.waitUntil(
- () -> (int) getMetric(hotKeysSizeMetricName).getValue() == maxHotKeyCapacity,
- METRIC_TRIGGER_TIMEOUT);
-
+ assertThat(cache.keys()).isNotEmpty();
cache.invalidateAll();
-
- WaitUtil.waitUntil(
- () -> (int) getMetric(hotKeysSizeMetricName).getValue() == 0, METRIC_TRIGGER_TIMEOUT);
+ assertThat(cache.keys()).isEmpty();
}
@Test
public void shouldSanitizeUnwantedCharsInMetricNames() throws Exception {
String cacheName = "very+confusing.cache#name";
String sanitized = "very_confusing_cache_name";
- String hotKeySizeMetricName = "cache/chroniclemap/hot_keys_size_" + sanitized;
String percentageFreeMetricName = "cache/chroniclemap/percentage_free_space_" + sanitized;
String autoResizeMetricName = "cache/chroniclemap/remaining_autoresizes_" + sanitized;
String maxAutoResizeMetricName = "cache/chroniclemap/max_autoresizes_" + sanitized;
- String hotKeyCapacityMetricName = "cache/chroniclemap/hot_keys_capacity_" + sanitized;
newCacheWithMetrics(cacheName, null);
- getMetric(hotKeySizeMetricName);
getMetric(percentageFreeMetricName);
getMetric(autoResizeMetricName);
getMetric(maxAutoResizeMetricName);
- getMetric(hotKeyCapacityMetricName);
}
private int valueSize(String value) {
diff --git a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRUTest.java b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRUTest.java
deleted file mode 100644
index 3d435c9..0000000
--- a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRUTest.java
+++ /dev/null
@@ -1,61 +0,0 @@
-// Copyright (C) 2020 The Android Open Source Project
-//
-// Licensed 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 com.googlesource.gerrit.modules.cache.chroniclemap;
-
-import static com.google.common.truth.Truth.assertThat;
-
-import org.junit.Test;
-
-public class InMemoryLRUTest {
-
- @Test
- public void add_shouldUpdateElementPositionWhenAlreadyInSet() {
- final InMemoryLRU<Object> map = new InMemoryLRU<>(2);
-
- map.add("A");
- map.add("B");
-
- assertThat(map.toArray()).asList().containsExactly("A", "B");
-
- map.add("A");
- assertThat(map.toArray()).asList().containsExactly("B", "A");
- }
-
- @Test
- public void add_shouldEvictLRUElement() {
- final InMemoryLRU<Object> map = new InMemoryLRU<>(2);
-
- map.add("A");
- map.add("B");
- map.add("C");
-
- assertThat(map.toArray()).asList().containsExactly("B", "C");
- }
-
- @Test
- public void remove_unexistingEntryShouldReturnNull() {
- InMemoryLRU<Object> map = new InMemoryLRU<>(1);
-
- assertThat(map.remove("foo")).isNull();
- }
-
- @Test
- public void remove_unexistingEntryShouldReturnTrue() {
- InMemoryLRU<Object> map = new InMemoryLRU<>(1);
-
- map.add("foo");
-
- assertThat(map.remove("foo")).isTrue();
- }
-}
