diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
index 948aaee..6b2b546 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
@@ -206,7 +206,7 @@
 
     return configFactory.createWithValues(
         currentChronicleMapConfig.getConfigKey(),
-        resolveNewFile(currentChronicleMapConfig.getPersistedFile().getName()),
+        resolveNewFile(currentChronicleMapConfig.getCacheFile().getName()),
         currentChronicleMapConfig.getExpireAfterWrite(),
         currentChronicleMapConfig.getRefreshAfterWrite(),
         newMaxEntries,
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
index a6f608d..430a95e 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndex.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndex.java
@@ -17,11 +17,24 @@
 import static java.util.stream.Collectors.toUnmodifiableSet;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.flogger.FluentLogger;
 import com.google.errorprone.annotations.CompatibleWith;
 import com.google.gerrit.metrics.Description;
 import com.google.gerrit.metrics.Description.Units;
 import com.google.gerrit.metrics.MetricMaker;
 import com.google.gerrit.metrics.Timer0;
+import com.google.gerrit.server.cache.serialize.CacheSerializer;
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
 import java.util.Collections;
 import java.util.LinkedHashSet;
 import java.util.Objects;
@@ -117,12 +130,21 @@
     }
   }
 
+  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
+
   private final Set<TimedKey> keys;
   private final Metrics metrics;
+  private final String name;
+  private final File indexFile;
+  private final File tempIndexFile;
 
-  CacheKeysIndex(MetricMaker metricMaker, String name) {
+  CacheKeysIndex(MetricMaker metricMaker, String name, File indexFile, boolean cacheFileExists) {
     this.keys = Collections.synchronizedSet(new LinkedHashSet<>());
     this.metrics = new Metrics(metricMaker, name);
+    this.name = name;
+    this.indexFile = indexFile;
+    this.tempIndexFile = tempIndexFile(indexFile);
+    restore(cacheFileExists);
   }
 
   @SuppressWarnings("unchecked")
@@ -186,4 +208,90 @@
   Set<TimedKey> keys() {
     return keys;
   }
+
+  void persist() {
+    logger.atInfo().log("Persisting cache keys index %s to %s file", name, indexFile);
+    ArrayList<TimedKey> toPersist;
+    synchronized (keys) {
+      toPersist = new ArrayList<>(keys);
+    }
+    CacheSerializer<T> serializer = CacheSerializers.getKeySerializer(name);
+    try (DataOutputStream dos =
+        new DataOutputStream(new BufferedOutputStream(new FileOutputStream(tempIndexFile)))) {
+      for (TimedKey key : toPersist) {
+        writeKey(serializer, dos, key);
+      }
+      dos.flush();
+      indexFile.delete();
+      if (!tempIndexFile.renameTo(indexFile)) {
+        logger.atSevere().log(
+            "Renaming temporary index file %s to %s was not successful. Persisting cache key index failed.",
+            tempIndexFile, indexFile);
+        return;
+      }
+      logger.atInfo().log("Cache keys index %s was persisted to %s file", name, indexFile);
+    } catch (Exception e) {
+      logger.atSevere().withCause(e).log("Persisting cache keys index %s failed", name);
+    }
+  }
+
+  void restore(boolean cacheFileExists) {
+    try {
+      if (tempIndexFile.isFile()) {
+        logger.atWarning().log(
+            "Gerrit was not closed properly as index persist operation was not finished: temporary"
+                + " index storage file %s exists for %s cache.",
+            tempIndexFile, name);
+        if (!tempIndexFile.delete()) {
+          logger.atSevere().log(
+              "Cannot delete the temporary index storage file %s.", tempIndexFile);
+          return;
+        }
+      }
+
+      if (!indexFile.isFile() || !indexFile.canRead()) {
+        if (cacheFileExists) {
+          logger.atWarning().log(
+              "Restoring cache keys index %s not possible. File %s doesn't exist or cannot be read."
+                  + " Existing persisted entries will be pruned only when they are accessed after"
+                  + " Gerrit start.",
+              name, indexFile.getPath());
+        }
+        return;
+      }
+
+      logger.atInfo().log("Restoring cache keys index %s from %s file", name, indexFile);
+      CacheSerializer<T> serializer = CacheSerializers.getKeySerializer(name);
+      try (DataInputStream dis =
+          new DataInputStream(new BufferedInputStream(new FileInputStream(indexFile)))) {
+        while (dis.available() > 0) {
+          keys.add(readKey(serializer, dis));
+        }
+        logger.atInfo().log("Cache keys index %s was restored from %s file", name, indexFile);
+      }
+    } catch (Exception e) {
+      logger.atSevere().withCause(e).log("Restoring cache keys index %s failed", name);
+    }
+  }
+
+  static final File tempIndexFile(File indexFile) {
+    return new File(String.format("%s.tmp", indexFile.getPath()));
+  }
+
+  private void writeKey(CacheSerializer<T> serializer, DataOutput out, TimedKey key)
+      throws IOException {
+    byte[] serializeKey = serializer.serialize(key.getKey());
+    out.writeLong(key.getCreated());
+    out.writeInt(serializeKey.length);
+    out.write(serializeKey);
+  }
+
+  private TimedKey readKey(CacheSerializer<T> serializer, DataInput in) throws IOException {
+    long created = in.readLong();
+    int keySize = in.readInt();
+    byte[] serializedKey = new byte[keySize];
+    in.readFully(serializedKey);
+    T key = serializer.deserialize(serializedKey);
+    return new TimedKey(key, created);
+  }
 }
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 7011f65..2b81078 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
@@ -22,12 +22,16 @@
 import com.google.inject.assistedinject.Assisted;
 import com.google.inject.assistedinject.AssistedInject;
 import java.io.File;
+import java.nio.file.Path;
 import java.time.Duration;
 import java.util.Optional;
+import org.apache.commons.io.FilenameUtils;
 import org.eclipse.jgit.lib.Config;
 
 public class ChronicleMapCacheConfig {
-  private final File persistedFile;
+  private final File cacheFile;
+  private final boolean cacheFileExists;
+  private final File indexFile;
   private final long maxEntries;
   private final long averageKeySize;
   private final long averageValueSize;
@@ -40,13 +44,13 @@
   public interface Factory {
     ChronicleMapCacheConfig create(
         @Assisted("ConfigKey") String configKey,
-        @Assisted File persistedFile,
+        @Assisted File cacheFile,
         @Nullable @Assisted("ExpireAfterWrite") Duration expireAfterWrite,
         @Nullable @Assisted("RefreshAfterWrite") Duration refreshAfterWrite);
 
     ChronicleMapCacheConfig createWithValues(
         @Assisted("ConfigKey") String configKey,
-        @Assisted File persistedFile,
+        @Assisted File cacheFile,
         @Nullable @Assisted("ExpireAfterWrite") Duration expireAfterWrite,
         @Nullable @Assisted("RefreshAfterWrite") Duration refreshAfterWrite,
         @Assisted("maxEntries") long maxEntries,
@@ -59,14 +63,14 @@
   ChronicleMapCacheConfig(
       @GerritServerConfig Config cfg,
       @Assisted("ConfigKey") String configKey,
-      @Assisted File persistedFile,
+      @Assisted File cacheFile,
       @Nullable @Assisted("ExpireAfterWrite") Duration expireAfterWrite,
       @Nullable @Assisted("RefreshAfterWrite") Duration refreshAfterWrite) {
 
     this(
         cfg,
         configKey,
-        persistedFile,
+        cacheFile,
         expireAfterWrite,
         refreshAfterWrite,
         cfg.getLong("cache", configKey, "maxEntries", Defaults.maxEntriesFor(configKey)),
@@ -79,14 +83,16 @@
   ChronicleMapCacheConfig(
       @GerritServerConfig Config cfg,
       @Assisted("ConfigKey") String configKey,
-      @Assisted File persistedFile,
+      @Assisted File cacheFile,
       @Nullable @Assisted("ExpireAfterWrite") Duration expireAfterWrite,
       @Nullable @Assisted("RefreshAfterWrite") Duration refreshAfterWrite,
       @Assisted("maxEntries") long maxEntries,
       @Assisted("avgKeySize") long avgKeySize,
       @Assisted("avgValueSize") long avgValueSize,
       @Assisted("maxBloatFactor") int maxBloatFactor) {
-    this.persistedFile = persistedFile;
+    this.cacheFile = cacheFile;
+    this.cacheFileExists = cacheFile.exists();
+    this.indexFile = resolveIndexFile(cacheFile);
     this.configKey = configKey;
 
     this.maxEntries = maxEntries;
@@ -132,8 +138,16 @@
     return maxEntries;
   }
 
-  public File getPersistedFile() {
-    return persistedFile;
+  public File getCacheFile() {
+    return cacheFile;
+  }
+
+  public boolean getCacheFileExists() {
+    return cacheFileExists;
+  }
+
+  public File getIndexFile() {
+    return indexFile;
   }
 
   public long getAverageKeySize() {
@@ -152,6 +166,13 @@
     return configKey;
   }
 
+  private static File resolveIndexFile(File persistedCacheFile) {
+    String cacheFileName = persistedCacheFile.getName();
+    String indexFileName = String.format("%s.index", FilenameUtils.getBaseName(cacheFileName));
+
+    return Path.of(persistedCacheFile.getParent()).resolve(indexFileName).toFile();
+  }
+
   private static long toSeconds(@Nullable Duration duration) {
     return duration != null ? duration.getSeconds() : 0;
   }
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 3740959..8f33271 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
@@ -55,7 +55,9 @@
 
     this.cacheDefinition = def;
     this.config = config;
-    this.keysIndex = new CacheKeysIndex<>(metricMaker, def.name());
+    this.keysIndex =
+        new CacheKeysIndex<>(
+            metricMaker, def.name(), config.getIndexFile(), config.getCacheFileExists());
     this.store = createOrRecoverStore(def, config, metricMaker);
     this.memLoader =
         new ChronicleMapCacheLoader<>(
@@ -72,7 +74,9 @@
 
     this.cacheDefinition = def;
     this.config = config;
-    this.keysIndex = new CacheKeysIndex<>(metricMaker, def.name());
+    this.keysIndex =
+        new CacheKeysIndex<>(
+            metricMaker, def.name(), config.getIndexFile(), config.getCacheFileExists());
     this.memLoader = memLoader;
     this.mem = mem;
     this.store = memLoader.getStore();
@@ -112,7 +116,7 @@
             + "a function of the number of entries in the cache",
         def.diskLimit(), def.name());
     ChronicleMap<KeyWrapper<K>, TimedValue<V>> store =
-        mapBuilder.createOrRecoverPersistedTo(config.getPersistedFile());
+        mapBuilder.createOrRecoverPersistedTo(config.getCacheFile());
 
     logger.atInfo().log(
         "Initialized '%s'|version: %s|avgKeySize: %s bytes|avgValueSize:"
@@ -269,6 +273,8 @@
     if (runningOutOfFreeSpace()) {
       evictColdEntries();
     }
+
+    keysIndex.persist();
   }
 
   private boolean needsRefresh(long created) {
@@ -321,7 +327,7 @@
   public DiskStats diskStats() {
     return new DiskStats(
         store.longSize(),
-        config.getPersistedFile().length(),
+        config.getCacheFile().length(),
         hitCount.longValue(),
         missCount.longValue());
   }
@@ -332,6 +338,7 @@
 
   public void close() {
     store.close();
+    keysIndex.persist();
   }
 
   public double percentageUsedAutoResizes() {
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
index 27c9e76..c8a8b66 100644
--- a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndexTest.java
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/CacheKeysIndexTest.java
@@ -15,23 +15,35 @@
 package com.googlesource.gerrit.modules.cache.chroniclemap;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.googlesource.gerrit.modules.cache.chroniclemap.CacheKeysIndex.tempIndexFile;
 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 com.google.gerrit.metrics.DisabledMetricMaker;
+import com.google.gerrit.server.cache.serialize.StringCacheSerializer;
+import java.io.File;
+import java.io.IOException;
 import java.util.List;
 import java.util.function.Consumer;
 import org.junit.Before;
+import org.junit.Rule;
 import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
 
 public class CacheKeysIndexTest {
+  private static final String CACHE_NAME = "test-cache";
+  @Rule public TemporaryFolder temporaryFolder = new TemporaryFolder();
+
   private CacheKeysIndex<String> index;
+  private File indexFile;
 
   @Before
-  public void setup() {
-    index = new CacheKeysIndex<>(new DisabledMetricMaker(), "test-cache");
+  public void setup() throws IOException {
+    CacheSerializers.registerCacheKeySerializer(CACHE_NAME, StringCacheSerializer.INSTANCE);
+    indexFile = temporaryFolder.newFolder().toPath().resolve("cache.index").toFile();
+    index = new CacheKeysIndex<>(new DisabledMetricMaker(), CACHE_NAME, indexFile, false);
   }
 
   @Test
@@ -103,6 +115,35 @@
     assertThat(keys(index)).containsExactly("newer");
   }
 
+  @Test
+  public void persist_shouldPersistAndRestoreKeys() {
+    index.add("older", 1L);
+    index.add("newer", 1L);
+    assertThat(indexFile.exists()).isFalse();
+
+    index.persist();
+    assertThat(indexFile.isFile()).isTrue();
+    assertThat(indexFile.canRead()).isTrue();
+
+    index.clear();
+    assertThat(keys(index)).isEmpty();
+
+    index.restore(true);
+    assertThat(keys(index)).containsExactly("newer", "older");
+  }
+
+  @Test
+  public void restore_shouldDeleteExistingTemporaryIndexStorageFileDuringRestore()
+      throws IOException {
+    File indexTempFile = tempIndexFile(indexFile);
+    indexTempFile.createNewFile();
+    assertThat(indexTempFile.isFile()).isTrue();
+
+    index.restore(true);
+
+    assertThat(indexTempFile.exists()).isFalse();
+  }
+
   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 08f5977..61cacca 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
@@ -59,10 +59,10 @@
   }
 
   @Test
-  public void shouldProvidePersistedFile() throws Exception {
+  public void shouldProvideCacheFile() throws Exception {
     assertThat(
             configUnderTest(gerritConfig)
-                .getPersistedFile()
+                .getCacheFile()
                 .toPath()
                 .getParent()
                 .toRealPath()
@@ -71,6 +71,19 @@
   }
 
   @Test
+  public void shouldProvideIndexFileThatIsRelatedToCacheFile() {
+    ChronicleMapCacheConfig config = configUnderTest(gerritConfig);
+    File cacheFile = config.getCacheFile();
+    File indexFile = config.getIndexFile();
+
+    assertThat(indexFile.getParentFile()).isEqualTo(cacheFile.getParentFile());
+    String cacheFileName = cacheFile.getName();
+    assertThat(indexFile.getName())
+        .isEqualTo(
+            String.format("%s.index", cacheFileName.substring(0, cacheFileName.indexOf(".dat"))));
+  }
+
+  @Test
   public void shouldProvideConfiguredMaxEntriesWhenDefined() throws Exception {
     long maxEntries = 10;
     gerritConfig.setLong("cache", cacheKey, "maxEntries", maxEntries);
@@ -176,7 +189,7 @@
   }
 
   private ChronicleMapCacheConfig configUnderTest(StoredConfig gerritConfig) {
-    File persistentFile =
+    File cacheFile =
         ChronicleMapCacheFactory.fileName(
             sitePaths.site_path.resolve(cacheDirectory), cacheName, version);
     sitePaths
@@ -185,6 +198,6 @@
         .toFile();
 
     return new ChronicleMapCacheConfig(
-        gerritConfig, cacheKey, persistentFile, expireAfterWrite, refreshAfterWrite);
+        gerritConfig, cacheKey, cacheFile, expireAfterWrite, refreshAfterWrite);
   }
 }