Evict cache entries when free space gets low
Chronicle-map cannot expand indefinitely, but only to an upper limit
which is based on the maxBloatFactor.
When the number of possible expansions drops to zero and the percentage
of free space in the last available segment falls under a configurable
threshold (percentageFreeSpaceEvictionThreshold), cold cache entries are
evicted from chronicle-map.
Hot entries are kept in an LRU in-memory cache that holds a configurable
fraction of the cache size.
A cold cache entry is an entry that does not belong to this hot-cache and
thus subject to eviction, in random order.
Bug: Issue 13536
Change-Id: Iaf94a041943fb0680c2e3a222f3adda19915ae19
diff --git a/config.md b/config.md
index 7c8b222..26b163d 100644
--- a/config.md
+++ b/config.md
@@ -76,6 +76,20 @@
https://www.javadoc.io/doc/net.openhft/chronicle-map/3.8.0/net/openhft/chronicle/hash/ChronicleHashBuilder.html#maxBloatFactor-double-
)
+* `cache.<name>.percentageFreeSpaceEvictionThreshold`
+: The percentage of free space in the last available expansion of chronicle-map
+beyond which cold cache entries will start being evicted.
+
+Since the eviction routine is scheduled as background task every 30 seconds,
+this value should always be < 100. This is to allow for additional entries to be
+inserted into the cache between the execution of two eviction runs.
+
+How much that margin is, depends on how fast the cache can increase between two
+eviction runs: caches that populate more quickly might need a lower value, and
+vice-versa.
+
+Default: *90*
+
### Defaults
Unless overridden by configuration, sensible default values are be provided for
@@ -106,11 +120,34 @@
The limit to the number of times the map can expand is set via the `maxBloatFactor`.
if `remainingAutoResizes` drops to zero,this cache is no longer able to expand
and it will not be able to take more entries, failing with a `IllegalStateException`
+[official documentation](https://javadoc.io/static/net.openhft/chronicle-map/3.20.83/net/openhft/chronicle/map/ChronicleMap.html#remainingAutoResizes--)
* `percentageFreeSpace`
: the amount of free space in the cache as a percentage. When the free space gets
low ( around 5% ) the cache will automatically expand (see `remainingAutoResizes`).
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
These are the provided default values:
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 071bada..b0b66b5 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
@@ -43,6 +43,8 @@
private final Duration refreshAfterWrite;
private final int maxBloatFactor;
private final int version;
+ private final int percentageFreeSpaceEvictionThreshold;
+ private final int percentageHotKeys;
public interface Factory {
ChronicleMapCacheConfig create(
@@ -95,6 +97,28 @@
this.maxBloatFactor =
cfg.getInt("cache", configKey, "maxBloatFactor", Defaults.maxBloatFactorFor(configKey));
+
+ this.percentageFreeSpaceEvictionThreshold =
+ cfg.getInt(
+ "cache",
+ 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 int getVersion() {
@@ -161,6 +185,9 @@
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>()
.put("web_sessions", DefaultConfig.create(45, 221, 1000, 1))
@@ -201,5 +228,13 @@
.map(DefaultConfig::maxBloatFactor)
.orElse(DEFAULT_MAX_BLOAT_FACTOR);
}
+
+ 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 bf5ca56..01bc2cc 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
@@ -123,9 +123,7 @@
@Override
public void start() {
for (ChronicleMapCacheImpl<?, ?> cache : caches) {
- if (!cache.getConfig().getExpireAfterWrite().isZero()) {
- cleanup.scheduleWithFixedDelay(cache::prune, 30, 30, TimeUnit.SECONDS);
- }
+ cleanup.scheduleWithFixedDelay(cache::prune, 30, 30, TimeUnit.SECONDS);
}
}
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 e7adc26..88c93c8 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
@@ -43,6 +43,7 @@
private final LongAdder loadExceptionCount = new LongAdder();
private final LongAdder totalLoadTime = new LongAdder();
private final LongAdder evictionCount = new LongAdder();
+ private final InMemoryLRU<K> hotEntries;
@SuppressWarnings("unchecked")
ChronicleMapCacheImpl(
@@ -50,6 +51,9 @@
throws IOException {
this.config = config;
this.loader = loader;
+ this.hotEntries =
+ new InMemoryLRU<>(
+ (int) Math.max(config.getMaxEntries() * config.getpercentageHotKeys() / 100, 1));
final Class<K> keyClass = (Class<K>) def.keyType().getRawType();
final Class<TimedValue<V>> valueWrapperClass = (Class<TimedValue<V>>) (Class) TimedValue.class;
@@ -109,6 +113,7 @@
TimedValue<V> vTimedValue = store.get(objKey);
if (!expired(vTimedValue.getCreated())) {
hitCount.increment();
+ hotEntries.add((K) objKey);
return vTimedValue.getValue();
} else {
invalidate(objKey);
@@ -124,6 +129,7 @@
TimedValue<V> vTimedValue = store.get(key);
if (!needsRefresh(vTimedValue.getCreated())) {
hitCount.increment();
+ hotEntries.add(key);
return vTimedValue.getValue();
}
}
@@ -176,15 +182,23 @@
public void put(K key, V val) {
TimedValue<V> wrapped = new TimedValue<>(val);
store.put(key, wrapped);
+ hotEntries.add(key);
}
public void prune() {
- store.forEachEntry(
- c -> {
- if (expired(c.value().get().getCreated())) {
- c.context().remove(c);
- }
- });
+ if (!config.getExpireAfterWrite().isZero()) {
+ store.forEachEntry(
+ c -> {
+ if (expired(c.value().get().getCreated())) {
+ hotEntries.remove(c.key().get());
+ c.context().remove(c);
+ }
+ });
+ }
+
+ if (runningOutOfFreeSpace()) {
+ evictColdEntries();
+ }
}
private boolean expired(long created) {
@@ -199,14 +213,31 @@
return !refreshAfterWrite.isZero() && age.compareTo(refreshAfterWrite) > 0;
}
+ protected boolean runningOutOfFreeSpace() {
+ return store.remainingAutoResizes() == 0
+ && store.percentageFreeSpace() <= config.getPercentageFreeSpaceEvictionThreshold();
+ }
+
+ private void evictColdEntries() {
+ store.forEachEntryWhile(
+ e -> {
+ if (!hotEntries.contains(e.key().get())) {
+ e.doRemove();
+ }
+ return runningOutOfFreeSpace();
+ });
+ }
+
@Override
public void invalidate(Object key) {
store.remove(key);
+ hotEntries.remove((K) key);
}
@Override
public void invalidateAll() {
store.clear();
+ hotEntries.invalidateAll();
}
@Override
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
new file mode 100644
index 0000000..150ab18
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRU.java
@@ -0,0 +1,59 @@
+// 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;
+
+ public InMemoryLRU(int capacity) {
+
+ LRUMap =
+ Collections.synchronizedMap(
+ new LinkedHashMap<K, Boolean>(capacity, 0.75f, true) {
+ @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);
+ }
+
+ public boolean remove(K key) {
+ return LRUMap.remove(key);
+ }
+
+ public void invalidateAll() {
+ LRUMap.clear();
+ }
+
+ @VisibleForTesting
+ protected Object[] toArray() {
+ return LRUMap.keySet().toArray();
+ }
+}
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 febff2f..d2a830b 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
@@ -19,6 +19,8 @@
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.IOException;
@@ -197,6 +199,54 @@
assertThat(configUnderTest(gerritConfig).getRefreshAfterWrite()).isEqualTo(refreshAfterWrite);
}
+ @Test
+ public void shouldProvidePercentageFreeSpaceEvictionThresholdWhenConfigured() throws Exception {
+ int percentageFreeThreshold = 70;
+ gerritConfig.setInt(
+ "cache", cacheKey, "percentageFreeSpaceEvictionThreshold", percentageFreeThreshold);
+ gerritConfig.save();
+
+ assertThat(configUnderTest(gerritConfig).getPercentageFreeSpaceEvictionThreshold())
+ .isEqualTo(percentageFreeThreshold);
+ }
+
+ @Test
+ public void shouldProvidePercentageFreeSpaceEvictionThresholdDefault() throws Exception {
+ assertThat(configUnderTest(gerritConfig).getPercentageFreeSpaceEvictionThreshold())
+ .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) throws IOException {
return new ChronicleMapCacheConfig(
gerritConfig,
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 bf0317d..124a7f3 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
@@ -25,10 +25,12 @@
import com.google.gerrit.server.config.SitePaths;
import com.google.inject.TypeLiteral;
import java.io.IOException;
+import java.nio.ByteBuffer;
import java.nio.file.Files;
import java.time.Duration;
import java.util.UUID;
import java.util.concurrent.ExecutionException;
+import net.openhft.chronicle.bytes.Bytes;
import org.eclipse.jgit.lib.StoredConfig;
import org.eclipse.jgit.storage.file.FileBasedConfig;
import org.eclipse.jgit.util.FS;
@@ -262,6 +264,77 @@
assertThat(cache.size()).isEqualTo(0);
}
+ @Test
+ public void shouldEvictOldestElementInCacheWhenIsNeverAccessed() throws Exception {
+ final String fooValue = "foo";
+
+ gerritConfig.setInt("cache", "foo", "maxEntries", 2);
+ gerritConfig.setInt("cache", "foo", "percentageHotKeys", 10);
+ gerritConfig.setInt("cache", "foo", "avgKeySize", "foo1".getBytes().length);
+ gerritConfig.setInt("cache", "foo", "avgValueSize", valueSize(fooValue));
+ gerritConfig.save();
+
+ ChronicleMapCacheImpl<String, String> cache = newCacheWithLoader(fooValue);
+ cache.put("foo1", fooValue);
+ cache.put("foo2", fooValue);
+
+ cache.prune();
+
+ assertThat(cache.size()).isEqualTo(1);
+ assertThat(cache.get("foo2")).isNotNull();
+ }
+
+ @Test
+ public void shouldEvictRecentlyInsertedElementInCacheWhenOldestElementIsAccessed()
+ throws Exception {
+ final String fooValue = "foo";
+ gerritConfig.setInt("cache", "foo", "maxEntries", 2);
+ gerritConfig.setInt("cache", "foo", "percentageHotKeys", 10);
+ gerritConfig.setInt("cache", "foo", "avgKeySize", "foo1".getBytes().length);
+ gerritConfig.setInt("cache", "foo", "avgValueSize", valueSize(fooValue));
+ gerritConfig.save();
+
+ ChronicleMapCacheImpl<String, String> cache = newCacheWithLoader(fooValue);
+ cache.put("foo1", fooValue);
+ cache.put("foo2", fooValue);
+
+ cache.get("foo1");
+
+ cache.prune();
+
+ assertThat(cache.size()).isEqualTo(1);
+ assertThat(cache.get("foo1")).isEqualTo(fooValue);
+ }
+
+ @Test
+ 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();
+
+ ChronicleMapCacheImpl<String, String> cache = newCacheWithLoader();
+ while (!cache.runningOutOfFreeSpace()) {
+ cache.put(UUID.randomUUID().toString(), UUID.randomUUID().toString());
+ }
+ assertThat(cache.runningOutOfFreeSpace()).isTrue();
+
+ cache.prune();
+
+ assertThat(cache.runningOutOfFreeSpace()).isFalse();
+ }
+
+ private int valueSize(String value) {
+ final TimedValueMarshaller<String> marshaller =
+ new TimedValueMarshaller<>(StringCacheSerializer.INSTANCE);
+
+ Bytes<ByteBuffer> out = Bytes.elasticByteBuffer();
+ marshaller.write(out, new TimedValue<>(value));
+ return out.toByteArray().length;
+ }
+
private ChronicleMapCacheImpl<String, String> newCache(
Boolean withLoader,
@Nullable String cachedValue,
@@ -333,7 +406,7 @@
@Override
public String name() {
- return "chronicle-map-test-cache";
+ return "foo";
}
@Override
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
new file mode 100644
index 0000000..af27216
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/InMemoryLRUTest.java
@@ -0,0 +1,45 @@
+// 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");
+ }
+}
