diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index e08c214..9700013 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -28,10 +28,12 @@
         "alignment.cc",
         "checksum.cc",
         "entry.cc",
+        "entry_cache.cc",
         "flash_memory.cc",
         "format.cc",
         "key_value_store.cc",
         "public/pw_kvs/internal/entry.h",
+        "public/pw_kvs/internal/entry_cache.h",
         "public/pw_kvs/internal/hash.h",
         "public/pw_kvs/internal/key_descriptor.h",
         "public/pw_kvs/internal/sector_descriptor.h",
@@ -118,6 +120,12 @@
 )
 
 pw_cc_test(
+    name = "entry_cache_test",
+    srcs = ["entry_cache_test.cc"],
+    deps = [":pw_kvs"],
+)
+
+pw_cc_test(
     name = "key_value_store_test",
     srcs = ["key_value_store_test.cc"],
     deps = [
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index 519ee3b..b682455 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -33,10 +33,12 @@
     "alignment.cc",
     "checksum.cc",
     "entry.cc",
+    "entry_cache.cc",
     "flash_memory.cc",
     "format.cc",
     "key_value_store.cc",
     "public/pw_kvs/internal/entry.h",
+    "public/pw_kvs/internal/entry_cache.h",
     "public/pw_kvs/internal/hash.h",
     "public/pw_kvs/internal/key_descriptor.h",
     "public/pw_kvs/internal/sector_descriptor.h",
@@ -55,6 +57,7 @@
   ]
   friend = [
     ":entry_test",
+    ":entry_cache_test",
     ":key_value_store_test",
     ":key_value_store_binary_format_test",
     ":key_value_store_map_test",
@@ -98,6 +101,7 @@
     ":alignment_test",
     ":checksum_test",
     ":entry_test",
+    ":entry_cache_test",
     ":key_value_store_test",
     ":key_value_store_binary_format_test",
     ":key_value_store_fuzz_test",
@@ -128,6 +132,11 @@
   sources = [ "entry_test.cc" ]
 }
 
+pw_test("entry_cache_test") {
+  deps = [ ":pw_kvs" ]
+  sources = [ "entry_cache_test.cc" ]
+}
+
 pw_test("key_value_store_test") {
   deps = [
     ":crc16",
diff --git a/pw_kvs/entry_cache.cc b/pw_kvs/entry_cache.cc
new file mode 100644
index 0000000..eec4044
--- /dev/null
+++ b/pw_kvs/entry_cache.cc
@@ -0,0 +1,202 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+//     https://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.
+
+#include "pw_kvs/internal/entry_cache.h"
+
+#include <cinttypes>
+
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/entry.h"
+#include "pw_kvs/internal/hash.h"
+#include "pw_kvs_private/macros.h"
+#include "pw_log/log.h"
+
+namespace pw::kvs::internal {
+namespace {
+
+using std::string_view;
+
+constexpr FlashPartition::Address kNoAddress = FlashPartition::Address(-1);
+
+}  // namespace
+
+void EntryMetadata::Reset(const KeyDescriptor& descriptor, Address address) {
+  *descriptor_ = descriptor;
+
+  addresses_[0] = address;
+  for (size_t i = 1; i < addresses_.size(); ++i) {
+    addresses_[i] = kNoAddress;
+  }
+  addresses_ = addresses_.first(1);
+}
+
+Status EntryCache::Find(FlashPartition& partition,
+                        string_view key,
+                        EntryMetadata* metadata) const {
+  const uint32_t hash = internal::Hash(key);
+  Entry::KeyBuffer key_buffer;
+
+  for (size_t i = 0; i < descriptors_.size(); ++i) {
+    if (descriptors_[i].key_hash == hash) {
+      TRY(Entry::ReadKey(
+          partition, *first_address(i), key.size(), key_buffer.data()));
+
+      if (key == string_view(key_buffer.data(), key.size())) {
+        PW_LOG_DEBUG("Found match for key hash 0x%08" PRIx32, hash);
+        *metadata = EntryMetadata(descriptors_[i], addresses(i));
+        return Status::OK;
+      } else {
+        PW_LOG_WARN("Found key hash collision for 0x%08" PRIx32, hash);
+        return Status::ALREADY_EXISTS;
+      }
+    }
+  }
+  return Status::NOT_FOUND;
+}
+
+Status EntryCache::FindExisting(FlashPartition& partition,
+                                string_view key,
+                                EntryMetadata* metadata) const {
+  Status status = Find(partition, key, metadata);
+
+  // If the key's hash collides with an existing key or if the key is deleted,
+  // treat it as if it is not in the KVS.
+  if (status == Status::ALREADY_EXISTS ||
+      (status.ok() && metadata->deleted())) {
+    return Status::NOT_FOUND;
+  }
+  return status;
+}
+
+EntryMetadata EntryCache::AddNew(const KeyDescriptor& descriptor,
+                                 Address entry_address) {
+  // TODO(hepler): DCHECK(!full());
+  Address* first_address = ResetAddresses(descriptors_.size(), entry_address);
+  descriptors_.push_back(descriptor);
+  return EntryMetadata(descriptors_.back(), span(first_address, 1));
+}
+
+// TODO: This method is the trigger of the O(valid_entries * all_entries) time
+// complexity for reading. At some cost to memory, this could be optimized by
+// using a hash table instead of scanning, but in practice this should be fine
+// for a small number of keys
+Status EntryCache::AddNewOrUpdateExisting(const KeyDescriptor& descriptor,
+                                          Address address,
+                                          size_t sector_size_bytes) {
+  // With the new key descriptor, either add it to the descriptor table or
+  // overwrite an existing entry with an older version of the key.
+  const int index = FindIndex(descriptor.key_hash);
+
+  // Write a new entry if there is room.
+  if (index == -1) {
+    if (full()) {
+      return Status::RESOURCE_EXHAUSTED;
+    }
+    AddNew(descriptor, address);
+    return Status::OK;
+  }
+
+  // Existing entry is old; replace the existing entry with the new one.
+  if (descriptor.transaction_id > descriptors_[index].transaction_id) {
+    descriptors_[index] = descriptor;
+    ResetAddresses(index, address);
+    return Status::OK;
+  }
+
+  // If the entries have a duplicate transaction ID, add the new (redundant)
+  // entry to the existing descriptor.
+  if (descriptors_[index].transaction_id == descriptor.transaction_id) {
+    if (descriptors_[index].key_hash != descriptor.key_hash) {
+      PW_LOG_ERROR("Duplicate entry for key 0x%08" PRIx32
+                   " with transaction ID %" PRIu32 " has non-matching hash",
+                   descriptor.key_hash,
+                   descriptor.transaction_id);
+      return Status::DATA_LOSS;
+    }
+
+    // Verify that this entry is not in the same sector as an existing copy of
+    // this same key.
+    for (Address existing_address : addresses(index)) {
+      if (existing_address / sector_size_bytes == address / sector_size_bytes) {
+        PW_LOG_DEBUG("Multiple Redundant entries in same sector %zu",
+                     address / sector_size_bytes);
+        return Status::DATA_LOSS;
+      }
+    }
+
+    AddAddressIfRoom(index, address);
+  } else {
+    PW_LOG_DEBUG("Found stale entry when appending; ignoring");
+  }
+  return Status::OK;
+}
+
+size_t EntryCache::present_entries() const {
+  size_t present_entries = 0;
+
+  for (const KeyDescriptor& descriptor : descriptors_) {
+    if (descriptor.state != EntryState::kDeleted) {
+      present_entries += 1;
+    }
+  }
+
+  return present_entries;
+}
+
+int EntryCache::FindIndex(uint32_t key_hash) const {
+  for (size_t i = 0; i < descriptors_.size(); ++i) {
+    if (descriptors_[i].key_hash == key_hash) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+void EntryCache::AddAddressIfRoom(size_t descriptor_index, Address address) {
+  Address* const existing = first_address(descriptor_index);
+
+  for (size_t i = 0; i < redundancy(); ++i) {
+    if (existing[i] == kNoAddress) {
+      existing[i] = address;
+      addresses(descriptor_index);
+      return;
+    }
+  }
+}
+
+span<EntryCache::Address> EntryCache::addresses(size_t descriptor_index) const {
+  Address* const addresses = first_address(descriptor_index);
+
+  size_t size = 0;
+  while (size < redundancy() && addresses[size] != kNoAddress) {
+    size += 1;
+  }
+
+  return span(addresses, size);
+}
+
+EntryCache::Address* EntryCache::ResetAddresses(size_t descriptor_index,
+                                                Address address) {
+  Address* first = first_address(descriptor_index);
+  *first = address;
+
+  // Clear the additional addresses, if any.
+  for (size_t i = 1; i < redundancy_; ++i) {
+    first[i] = kNoAddress;
+  }
+
+  return first;
+}
+
+}  // namespace pw::kvs::internal
diff --git a/pw_kvs/entry_cache_test.cc b/pw_kvs/entry_cache_test.cc
new file mode 100644
index 0000000..df1ae90
--- /dev/null
+++ b/pw_kvs/entry_cache_test.cc
@@ -0,0 +1,45 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+//     https://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.
+
+#include "pw_kvs/internal/entry_cache.h"
+
+#include "gtest/gtest.h"
+
+namespace pw::kvs::internal {
+
+class EmptyEntryCache : public ::testing::Test {
+ protected:
+  static constexpr size_t kRedundancy = 3;
+
+  EmptyEntryCache() : entries_(descriptors_, addresses_, kRedundancy) {}
+
+  Vector<KeyDescriptor, 32> descriptors_;
+  EntryCache::AddressList<32, kRedundancy> addresses_;
+
+  EntryCache entries_;
+};
+
+TEST_F(EmptyEntryCache, AddNew) {
+  EntryMetadata metadata = entries_.AddNew(
+      {.key_hash = 1, .transaction_id = 123, .state = EntryState::kValid}, 5);
+  EXPECT_EQ(1u, metadata.hash());
+  EXPECT_EQ(123u, metadata.transaction_id());
+
+  EXPECT_EQ(5u, metadata.first_address());
+  EXPECT_EQ(1u, metadata.addresses().size());
+}
+
+// TODO(hepler): Expand these tests!
+
+}  // namespace pw::kvs::internal
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index d76323e..2ad68fa 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -19,10 +19,7 @@
 #include <cstring>
 #include <type_traits>
 
-#include "pw_kvs/format.h"
-
 #define PW_LOG_USE_ULTRA_SHORT_NAMES 1
-#include "pw_kvs/internal/entry.h"
 #include "pw_kvs_private/macros.h"
 #include "pw_log/log.h"
 
@@ -47,16 +44,18 @@
 }  // namespace
 
 KeyValueStore::KeyValueStore(FlashPartition* partition,
-                             Vector<KeyDescriptor>& key_descriptor_list,
-                             Vector<SectorDescriptor>& sector_descriptor_list,
-                             size_t redundancy,
                              span<const EntryFormat> formats,
-                             const Options& options)
+                             const Options& options,
+                             size_t redundancy,
+                             Vector<SectorDescriptor>& sector_descriptor_list,
+                             const SectorDescriptor** temp_sectors_to_skip,
+                             Vector<KeyDescriptor>& key_descriptor_list,
+                             Address* addresses)
     : partition_(*partition),
       formats_(formats),
-      key_descriptors_(key_descriptor_list),
+      entry_cache_(key_descriptor_list, addresses, redundancy),
       sectors_(sector_descriptor_list),
-      redundancy_(redundancy),
+      temp_sectors_to_skip_(temp_sectors_to_skip),
       options_(options) {
   initialized_ = false;
   last_new_sector_ = nullptr;
@@ -67,7 +66,7 @@
   initialized_ = false;
   last_new_sector_ = nullptr;
   last_transaction_id_ = 0;
-  key_descriptors_.clear();
+  entry_cache_.Reset();
 
   INF("Initializing key value store");
   if (partition_.sector_count() > sectors_.max_size()) {
@@ -172,26 +171,23 @@
   }
 
   DBG("Second pass: Count valid bytes in each sector");
-  const KeyDescriptor* newest_key = nullptr;
+  Address newest_key = 0;
 
   // For every valid key, increment the valid bytes for that sector.
-  for (KeyDescriptor& key_descriptor : key_descriptors_) {
-    for (auto& address : key_descriptor.addresses()) {
+
+  for (const EntryMetadata& metadata : entry_cache_) {
+    for (Address address : metadata.addresses()) {
       Entry entry;
       TRY(Entry::Read(partition_, address, formats_, &entry));
       SectorFromAddress(address)->AddValidBytes(entry.size());
     }
-    if (key_descriptor.IsNewerThan(last_transaction_id_)) {
-      last_transaction_id_ = key_descriptor.transaction_id();
-      newest_key = &key_descriptor;
+    if (metadata.IsNewerThan(last_transaction_id_)) {
+      last_transaction_id_ = metadata.transaction_id();
+      newest_key = metadata.addresses().back();
     }
   }
 
-  if (newest_key == nullptr) {
-    last_new_sector_ = sectors_.begin();
-  } else {
-    last_new_sector_ = SectorFromAddress(newest_key->addresses().back());
-  }
+  last_new_sector_ = SectorFromAddress(newest_key);
 
   if (!empty_sector_found) {
     // TODO: Record/report the error condition and recovery result.
@@ -208,7 +204,7 @@
   INF("KeyValueStore init complete: active keys %zu, deleted keys %zu, sectors "
       "%zu, logical sector size %zu bytes",
       size(),
-      (key_descriptors_.size() - size()),
+      (entry_cache_.total_entries() - size()),
       sectors_.size(),
       partition_.sector_size_bytes());
 
@@ -261,11 +257,10 @@
   TRY(entry.VerifyChecksumInFlash());
 
   // A valid entry was found, so update the next entry address before doing any
-  // of the checks that happen in AppendNewOrOverwriteStaleExistingDescriptor().
+  // of the checks that happen in AddNewOrUpdateExisting.
   *next_entry_address = entry.next_address();
-  TRY(AppendNewOrOverwriteStaleExistingDescriptor(entry.descriptor(key)));
-
-  return Status::OK;
+  return entry_cache_.AddNewOrUpdateExisting(
+      entry.descriptor(key), entry.address(), partition_.sector_size_bytes());
 }
 
 // Scans flash memory within a sector to find a KVS entry magic.
@@ -295,73 +290,15 @@
   return Status::NOT_FOUND;
 }
 
-// TODO: This method is the trigger of the O(valid_entries * all_entries) time
-// complexity for reading. At some cost to memory, this could be optimized by
-// using a hash table instead of scanning, but in practice this should be fine
-// for a small number of keys
-Status KeyValueStore::AppendNewOrOverwriteStaleExistingDescriptor(
-    const KeyDescriptor& key_descriptor) {
-  // With the new key descriptor, either add it to the descriptor table or
-  // overwrite an existing entry with an older version of the key.
-  KeyDescriptor* existing_descriptor = FindDescriptor(key_descriptor.hash());
-
-  // Write a new entry.
-  if (existing_descriptor == nullptr) {
-    if (key_descriptors_.full()) {
-      return Status::RESOURCE_EXHAUSTED;
-    }
-    key_descriptors_.push_back(key_descriptor);
-  } else if (key_descriptor.IsNewerThan(
-                 existing_descriptor->transaction_id())) {
-    // Existing entry is old; replace the existing entry with the new one.
-    *existing_descriptor = key_descriptor;
-  } else if (existing_descriptor->transaction_id() ==
-             key_descriptor.transaction_id()) {
-    // If the entries have a duplicate transaction ID, add the new (redundant)
-    // entry to the existing descriptor.
-    if (existing_descriptor->hash() != key_descriptor.hash()) {
-      ERR("Duplicate entry for key 0x%08" PRIx32 " with transaction ID %" PRIu32
-          " has non-matching hash",
-          key_descriptor.hash(),
-          key_descriptor.transaction_id());
-      return Status::DATA_LOSS;
-    }
-
-    // Verify that this entry is not in the same sector as an existing copy of
-    // this same key.
-    for (auto address : existing_descriptor->addresses()) {
-      if (SectorFromAddress(address) ==
-          SectorFromAddress(key_descriptor.address())) {
-        DBG("Multiple Redundant entries in same sector %u",
-            SectorIndex(SectorFromAddress(address)));
-        return Status::DATA_LOSS;
-      }
-    }
-    existing_descriptor->addresses().push_back(key_descriptor.address());
-  } else {
-    DBG("Found stale entry when appending; ignoring");
-  }
-  return Status::OK;
-}
-
-KeyValueStore::KeyDescriptor* KeyValueStore::FindDescriptor(uint32_t hash) {
-  for (KeyDescriptor& key_descriptor : key_descriptors_) {
-    if (key_descriptor.hash() == hash) {
-      return &key_descriptor;
-    }
-  }
-  return nullptr;
-}
-
 StatusWithSize KeyValueStore::Get(string_view key,
                                   span<byte> value_buffer,
                                   size_t offset_bytes) const {
   TRY_WITH_SIZE(CheckOperation(key));
 
-  const KeyDescriptor* key_descriptor;
-  TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
+  EntryMetadata metadata;
+  TRY_WITH_SIZE(entry_cache_.FindExisting(partition_, key, &metadata));
 
-  return Get(key, *key_descriptor, value_buffer, offset_bytes);
+  return Get(key, metadata, value_buffer, offset_bytes);
 }
 
 Status KeyValueStore::PutBytes(string_view key, span<const byte> value) {
@@ -378,17 +315,16 @@
     return Status::INVALID_ARGUMENT;
   }
 
-  KeyDescriptor* key_descriptor;
-  Status status = FindKeyDescriptor(key, &key_descriptor);
+  EntryMetadata metadata;
+  Status status = entry_cache_.Find(partition_, key, &metadata);
 
   if (status.ok()) {
     // TODO: figure out logging how to support multiple addresses.
-    DBG("Overwriting entry for key 0x%08" PRIx32 " in %u sectors including %u",
-        key_descriptor->hash(),
-        unsigned(key_descriptor->addresses().size()),
-        SectorIndex(SectorFromAddress(key_descriptor->address())));
-    return WriteEntryForExistingKey(
-        key_descriptor, KeyDescriptor::kValid, key, value);
+    DBG("Overwriting entry for key 0x%08" PRIx32 " in %zu sectors including %u",
+        metadata.hash(),
+        metadata.addresses().size(),
+        SectorIndex(SectorFromAddress(metadata.first_address())));
+    return WriteEntryForExistingKey(metadata, EntryState::kValid, key, value);
   }
 
   if (status == Status::NOT_FOUND) {
@@ -401,16 +337,15 @@
 Status KeyValueStore::Delete(string_view key) {
   TRY(CheckOperation(key));
 
-  KeyDescriptor* key_descriptor;
-  TRY(FindExistingKeyDescriptor(key, &key_descriptor));
+  EntryMetadata metadata;
+  TRY(entry_cache_.FindExisting(partition_, key, &metadata));
 
   // TODO: figure out logging how to support multiple addresses.
-  DBG("Writing tombstone for key 0x%08" PRIx32 " in %u sectors including %u",
-      key_descriptor->hash(),
-      unsigned(key_descriptor->addresses().size()),
-      SectorIndex(SectorFromAddress(key_descriptor->address())));
-  return WriteEntryForExistingKey(
-      key_descriptor, KeyDescriptor::kDeleted, key, {});
+  DBG("Writing tombstone for key 0x%08" PRIx32 " in %zu sectors including %u",
+      metadata.hash(),
+      metadata.addresses().size(),
+      SectorIndex(SectorFromAddress(metadata.first_address())));
+  return WriteEntryForExistingKey(metadata, EntryState::kDeleted, key, {});
 }
 
 void KeyValueStore::Item::ReadKey() {
@@ -420,7 +355,7 @@
   // TODO: add support for using one of the redundant entries if reading the
   // first copy fails.
   if (Entry::Read(
-          kvs_.partition_, descriptor_->address(), kvs_.formats_, &entry)
+          kvs_.partition_, iterator_->first_address(), kvs_.formats_, &entry)
           .ok()) {
     entry.ReadKey(key_buffer_);
   }
@@ -428,53 +363,39 @@
 
 KeyValueStore::iterator& KeyValueStore::iterator::operator++() {
   // Skip to the next entry that is valid (not deleted).
-  while (++item_.descriptor_ != item_.kvs_.key_descriptors_.end() &&
-         item_.descriptor_->deleted()) {
+  while (++item_.iterator_ != item_.kvs_.entry_cache_.end() &&
+         item_.iterator_->deleted()) {
   }
   return *this;
 }
 
 KeyValueStore::iterator KeyValueStore::begin() const {
-  const KeyDescriptor* descriptor = key_descriptors_.begin();
+  internal::EntryCache::iterator cache_iterator = entry_cache_.begin();
   // Skip over any deleted entries at the start of the descriptor list.
-  while (descriptor != key_descriptors_.end() && descriptor->deleted()) {
-    ++descriptor;
+  while (cache_iterator != entry_cache_.end() && cache_iterator->deleted()) {
+    ++cache_iterator;
   }
-  return iterator(*this, descriptor);
-}
-
-// TODO(hepler): The valid entry count could be tracked in the KVS to avoid the
-// need for this for-loop.
-size_t KeyValueStore::size() const {
-  size_t valid_entries = 0;
-
-  for (const KeyDescriptor& key_descriptor : key_descriptors_) {
-    if (!key_descriptor.deleted()) {
-      valid_entries += 1;
-    }
-  }
-
-  return valid_entries;
+  return iterator(*this, cache_iterator);
 }
 
 StatusWithSize KeyValueStore::ValueSize(string_view key) const {
   TRY_WITH_SIZE(CheckOperation(key));
 
-  const KeyDescriptor* key_descriptor;
-  TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
+  EntryMetadata metadata;
+  TRY_WITH_SIZE(entry_cache_.FindExisting(partition_, key, &metadata));
 
-  return ValueSize(*key_descriptor);
+  return ValueSize(metadata);
 }
 
 StatusWithSize KeyValueStore::Get(string_view key,
-                                  const KeyDescriptor& descriptor,
+                                  const EntryMetadata& metadata,
                                   span<std::byte> value_buffer,
                                   size_t offset_bytes) const {
   Entry entry;
   // TODO: add support for using one of the redundant entries if reading the
   // first copy fails.
   TRY_WITH_SIZE(
-      Entry::Read(partition_, descriptor.address(), formats_, &entry));
+      Entry::Read(partition_, metadata.first_address(), formats_, &entry));
 
   StatusWithSize result = entry.ReadValue(value_buffer, offset_bytes);
   if (result.ok() && options_.verify_on_read && offset_bytes == 0u) {
@@ -495,19 +416,19 @@
                                    size_t size_bytes) const {
   TRY(CheckOperation(key));
 
-  const KeyDescriptor* descriptor;
-  TRY(FindExistingKeyDescriptor(key, &descriptor));
+  EntryMetadata metadata;
+  TRY(entry_cache_.FindExisting(partition_, key, &metadata));
 
-  return FixedSizeGet(key, *descriptor, value, size_bytes);
+  return FixedSizeGet(key, metadata, value, size_bytes);
 }
 
 Status KeyValueStore::FixedSizeGet(std::string_view key,
-                                   const KeyDescriptor& descriptor,
+                                   const EntryMetadata& metadata,
                                    void* value,
                                    size_t size_bytes) const {
   // Ensure that the size of the stored value matches the size of the type.
   // Otherwise, report error. This check avoids potential memory corruption.
-  TRY_ASSIGN(const size_t actual_size, ValueSize(descriptor));
+  TRY_ASSIGN(const size_t actual_size, ValueSize(metadata));
 
   if (actual_size != size_bytes) {
     DBG("Requested %zu B read, but value is %zu B", size_bytes, actual_size);
@@ -515,17 +436,17 @@
   }
 
   StatusWithSize result =
-      Get(key, descriptor, span(static_cast<byte*>(value), size_bytes), 0);
+      Get(key, metadata, span(static_cast<byte*>(value), size_bytes), 0);
 
   return result.status();
 }
 
-StatusWithSize KeyValueStore::ValueSize(const KeyDescriptor& descriptor) const {
+StatusWithSize KeyValueStore::ValueSize(const EntryMetadata& metadata) const {
   Entry entry;
   // TODO: add support for using one of the redundant entries if reading the
   // first copy fails.
   TRY_WITH_SIZE(
-      Entry::Read(partition_, descriptor.address(), formats_, &entry));
+      Entry::Read(partition_, metadata.first_address(), formats_, &entry));
 
   return StatusWithSize(entry.value_size());
 }
@@ -540,152 +461,97 @@
   return Status::OK;
 }
 
-// Searches for a KeyDescriptor that matches this key and sets *result to point
-// to it if one is found.
-//
-//             OK: there is a matching descriptor and *result is set
-//      NOT_FOUND: there is no descriptor that matches this key, but this key
-//                 has a unique hash (and could potentially be added to the KVS)
-// ALREADY_EXISTS: there is no descriptor that matches this key, but the
-//                 key's hash collides with the hash for an existing descriptor
-//
-Status KeyValueStore::FindKeyDescriptor(string_view key,
-                                        const KeyDescriptor** result) const {
-  const uint32_t hash = internal::Hash(key);
-  Entry::KeyBuffer key_buffer;
-
-  for (auto& descriptor : key_descriptors_) {
-    if (descriptor.hash() == hash) {
-      // TODO: add support for using one of the redundant entries if reading the
-      // first copy fails.
-      TRY(Entry::ReadKey(
-          partition_, descriptor.address(), key.size(), key_buffer.data()));
-
-      if (key == string_view(key_buffer.data(), key.size())) {
-        DBG("Found match for key hash 0x%08" PRIx32, hash);
-        *result = &descriptor;
-        return Status::OK;
-      } else {
-        WRN("Found key hash collision for 0x%08" PRIx32, hash);
-        return Status::ALREADY_EXISTS;
-      }
-    }
-  }
-  return Status::NOT_FOUND;
-}
-
-// Searches for a KeyDescriptor that matches this key and sets *result to point
-// to it if one is found.
-//
-//          OK: there is a matching descriptor and *result is set
-//   NOT_FOUND: there is no descriptor that matches this key
-//
-Status KeyValueStore::FindExistingKeyDescriptor(
-    string_view key, const KeyDescriptor** result) const {
-  Status status = FindKeyDescriptor(key, result);
-
-  // If the key's hash collides with an existing key or if the key is deleted,
-  // treat it as if it is not in the KVS.
-  if (status == Status::ALREADY_EXISTS ||
-      (status.ok() && (*result)->deleted())) {
-    return Status::NOT_FOUND;
-  }
-  return status;
-}
-
-Status KeyValueStore::WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
-                                               KeyDescriptor::State new_state,
+Status KeyValueStore::WriteEntryForExistingKey(EntryMetadata& metadata,
+                                               EntryState new_state,
                                                string_view key,
                                                span<const byte> value) {
   // Read the original entry to get the size for sector accounting purposes.
   Entry entry;
   // TODO: add support for using one of the redundant entries if reading the
   // first copy fails.
-  TRY(Entry::Read(partition_, key_descriptor->address(), formats_, &entry));
+  TRY(Entry::Read(partition_, metadata.first_address(), formats_, &entry));
 
-  return WriteEntry(key, value, new_state, key_descriptor, entry.size());
+  return WriteEntry(key, value, new_state, &metadata, entry.size());
 }
 
 Status KeyValueStore::WriteEntryForNewKey(string_view key,
                                           span<const byte> value) {
-  if (key_descriptors_.full()) {
+  if (entry_cache_.full()) {
     WRN("KVS full: trying to store a new entry, but can't. Have %zu entries",
-        key_descriptors_.size());
+        entry_cache_.total_entries());
     return Status::RESOURCE_EXHAUSTED;
   }
 
-  return WriteEntry(key, value, KeyDescriptor::kValid);
+  return WriteEntry(key, value, EntryState::kValid);
 }
 
 Status KeyValueStore::WriteEntry(string_view key,
                                  span<const byte> value,
-                                 KeyDescriptor::State new_state,
-                                 KeyDescriptor* prior_descriptor,
+                                 EntryState new_state,
+                                 EntryMetadata* prior_metadata,
                                  size_t prior_size) {
   const size_t entry_size = Entry::size(partition_, key, value);
 
   // List of addresses for sectors with space for this entry.
-  // TODO: The derived class should allocate space for this address list.
-  Vector<Address, internal::kEntryRedundancy> addresses;
+  Address* reserved_addresses = entry_cache_.TempReservedAddressesForWrite();
 
   // Find sectors to write the entry to. This may involve garbage collecting one
   // or more sectors.
-  for (size_t i = 0; i < redundancy_; i++) {
+  for (size_t i = 0; i < redundancy(); i++) {
     SectorDescriptor* sector;
-    TRY(GetSectorForWrite(&sector, entry_size, addresses));
+    TRY(GetSectorForWrite(&sector, entry_size, span(reserved_addresses, i)));
 
     DBG("Found space for entry in sector %u", SectorIndex(sector));
-    addresses.push_back(NextWritableAddress(sector));
+    reserved_addresses[i] = NextWritableAddress(sector);
   }
 
   // Write the entry at the first address that was found.
-  Entry entry = CreateEntry(addresses.front(), key, value, new_state);
+  Entry entry = CreateEntry(reserved_addresses[0], key, value, new_state);
   TRY(AppendEntry(entry, key, value));
 
   // After writing the first entry successfully, update the key descriptors.
   // Once a single new the entry is written, the old entries are invalidated.
-  KeyDescriptor& new_descriptor =
-      UpdateKeyDescriptor(entry, key, prior_descriptor, prior_size);
+  EntryMetadata new_metadata =
+      UpdateKeyDescriptor(entry, key, prior_metadata, prior_size);
 
   // Write the additional copies of the entry, if redundancy is greater than 1.
-  for (size_t i = 1; i < addresses.size(); ++i) {
-    entry.set_address(addresses[i]);
+  for (size_t i = 1; i < redundancy(); ++i) {
+    entry.set_address(reserved_addresses[i]);
     TRY(AppendEntry(entry, key, value));
-    new_descriptor.addresses().push_back(addresses[i]);
+    new_metadata.AddNewAddress(reserved_addresses[i]);
   }
   return Status::OK;
 }
 
-internal::KeyDescriptor& KeyValueStore::UpdateKeyDescriptor(
+KeyValueStore::EntryMetadata KeyValueStore::UpdateKeyDescriptor(
     const Entry& entry,
     string_view key,
-    KeyDescriptor* prior_descriptor,
+    EntryMetadata* prior_metadata,
     size_t prior_size) {
   // If there is no prior descriptor, create a new one.
-  if (prior_descriptor == nullptr) {
-    key_descriptors_.push_back(entry.descriptor(key));
-    return key_descriptors_.back();
+  if (prior_metadata == nullptr) {
+    return entry_cache_.AddNew(entry.descriptor(key), entry.address());
   }
 
   // Remove valid bytes for the old entry and its copies, which are now stale.
-  for (Address address : prior_descriptor->addresses()) {
+  for (Address address : prior_metadata->addresses()) {
     SectorFromAddress(address)->RemoveValidBytes(prior_size);
   }
 
-  *prior_descriptor = entry.descriptor(prior_descriptor->hash());
-  return *prior_descriptor;
+  prior_metadata->Reset(entry.descriptor(key), entry.address());
+  return *prior_metadata;
 }
 
-// Find a sector to use for writing a new entry to. Do automatic garbage
+// Finds a sector to use for writing a new entry to. Does automatic garbage
 // collection if needed and allowed.
 //
 //                 OK: Sector found with needed space.
 // RESOURCE_EXHAUSTED: No sector available with the needed space.
 Status KeyValueStore::GetSectorForWrite(SectorDescriptor** sector,
                                         size_t entry_size,
-                                        span<const Address> addresses_to_skip) {
+                                        span<const Address> reserved) {
   Status result =
-      FindSectorWithSpace(sector, entry_size, kAppendEntry, addresses_to_skip);
+      FindSectorWithSpace(sector, entry_size, kAppendEntry, {}, reserved);
 
   size_t gc_sector_count = 0;
   bool do_auto_gc = options_.gc_on_write != GargbageCollectOnWrite::kDisabled;
@@ -698,7 +564,7 @@
       do_auto_gc = false;
     }
     // Garbage collect and then try again to find the best sector.
-    Status gc_status = GarbageCollectPartial(addresses_to_skip);
+    Status gc_status = GarbageCollectPartial(reserved);
     if (!gc_status.ok()) {
       if (gc_status == Status::NOT_FOUND) {
         // Not enough space, and no reclaimable bytes, this KVS is full!
@@ -707,8 +573,8 @@
       return gc_status;
     }
 
-    result = FindSectorWithSpace(
-        sector, entry_size, kAppendEntry, addresses_to_skip);
+    result =
+        FindSectorWithSpace(sector, entry_size, kAppendEntry, {}, reserved);
 
     gc_sector_count++;
     // Allow total sectors + 2 number of GC cycles so that once reclaimable
@@ -753,9 +619,9 @@
   return Status::OK;
 }
 
-Status KeyValueStore::RelocateEntry(KeyDescriptor& key_descriptor,
+Status KeyValueStore::RelocateEntry(const EntryMetadata& metadata,
                                     KeyValueStore::Address& address,
-                                    span<const Address> addresses_to_skip) {
+                                    span<const Address> reserved_addresses) {
   Entry entry;
   TRY(Entry::Read(partition_, address, formats_, &entry));
 
@@ -767,34 +633,18 @@
   // an immediate extra relocation).
   SectorDescriptor* new_sector;
 
-  // Avoid both this entry's sectors and sectors in addresses_to_skip.
-  //
-  // This is overly strict. addresses_to_skip is populated when there are
-  // sectors reserved for a new entry. It is safe to garbage collect into these
-  // sectors, as long as there remains room for the pending entry. These
-  // reserved sectors could also be garbage collected if they have recoverable
-  // space.
-  // TODO(hepler): Look into improving garbage collection.
-  //
-  // TODO: The derived class should allocate space for this address list.
-  Vector<Address, internal::kEntryRedundancy* 2> all_addresses_to_skip =
-      key_descriptor.addresses();
-  for (Address address : addresses_to_skip) {
-    if (!Contains(all_addresses_to_skip, address)) {
-      // TODO: DCHECK(!all_addresses_to_skip.full)
-      all_addresses_to_skip.push_back(address);
-    }
-  }
-
-  TRY(FindSectorWithSpace(
-      &new_sector, entry.size(), kGarbageCollect, all_addresses_to_skip));
+  TRY(FindSectorWithSpace(&new_sector,
+                          entry.size(),
+                          kGarbageCollect,
+                          metadata.addresses(),
+                          reserved_addresses));
 
   const Address new_address = NextWritableAddress(new_sector);
   const StatusWithSize result = entry.Copy(new_address);
   new_sector->RemoveWritableBytes(result.size());
   TRY(result);
 
-  // Entry was written successfully; update the key descriptor and the sector
+  // Entry was written successfully; update descriptor's address and the sector
   // descriptors to reflect the new entry.
   SectorFromAddress(address)->RemoveValidBytes(result.size());
   new_sector->AddValidBytes(result.size());
@@ -811,7 +661,8 @@
     SectorDescriptor** found_sector,
     size_t size,
     FindSectorMode find_mode,
-    span<const Address> addresses_to_skip) {
+    span<const Address> addresses_to_skip,
+    span<const Address> reserved_addresses) {
   SectorDescriptor* first_empty_sector = nullptr;
   bool at_least_two_empty_sectors = (find_mode == kGarbageCollect);
 
@@ -819,19 +670,30 @@
   SectorDescriptor* non_empty_least_reclaimable_sector = nullptr;
   const size_t sector_size_bytes = partition_.sector_size_bytes();
 
-  // Build a vector of sectors to avoid.
-  // TODO(hepler): Consolidate the different address / sector lists.
-  Vector<SectorDescriptor*, internal::kEntryRedundancy * 2> sectors_to_skip;
+  // Build a list of sectors to avoid.
+  //
+  // This is overly strict. reserved_addresses is populated when there are
+  // sectors reserved for a new entry. It is safe to garbage collect into
+  // these sectors, as long as there remains room for the pending entry. These
+  // reserved sectors could also be garbage collected if they have recoverable
+  // space. For simplicitly, avoid both the relocating key's redundant entries
+  // (addresses_to_skip) and the sectors reserved for pending writes
+  // (reserved_addresses).
+  // TODO(hepler): Look into improving garbage collection.
+  size_t sectors_to_skip = 0;
   for (Address address : addresses_to_skip) {
-    sectors_to_skip.push_back(SectorFromAddress(address));
+    temp_sectors_to_skip_[sectors_to_skip++] = SectorFromAddress(address);
+  }
+  for (Address address : reserved_addresses) {
+    temp_sectors_to_skip_[sectors_to_skip++] = SectorFromAddress(address);
   }
 
   DBG("Find sector with %zu bytes available, starting with sector %u, %s",
       size,
       SectorIndex(last_new_sector_),
       (find_mode == kAppendEntry) ? "Append" : "GC");
-  for (auto& skip_sector : sectors_to_skip) {
-    DBG("  Skip sector %u", SectorIndex(skip_sector));
+  for (size_t i = 0; i < sectors_to_skip; ++i) {
+    DBG("  Skip sector %u", SectorIndex(temp_sectors_to_skip_[i]));
   }
 
   // The last_new_sector_ is the sector that was last selected as the "new empty
@@ -865,7 +727,7 @@
     }
 
     // Skip sectors in the skip list.
-    if (Contains(sectors_to_skip, sector)) {
+    if (Contains(span(temp_sectors_to_skip_, sectors_to_skip), sector)) {
       continue;
     }
 
@@ -925,18 +787,18 @@
 // abstraction for the sector list. Look in to being able to unit test this as
 // its own thing
 KeyValueStore::SectorDescriptor* KeyValueStore::FindSectorToGarbageCollect(
-    span<const Address> addresses_to_avoid) {
+    span<const Address> reserved_addresses) {
   const size_t sector_size_bytes = partition_.sector_size_bytes();
   SectorDescriptor* sector_candidate = nullptr;
   size_t candidate_bytes = 0;
 
   // Build a vector of sectors to avoid.
-  // TODO(hepler): Consolidate the three address / sector lists.
-  Vector<const SectorDescriptor*, internal::kEntryRedundancy> sectors_to_skip;
-  for (auto& address : addresses_to_avoid) {
-    sectors_to_skip.push_back(SectorFromAddress(address));
-    DBG("    Skip sector %u", SectorIndex(SectorFromAddress(address)));
+  for (size_t i = 0; i < reserved_addresses.size(); ++i) {
+    temp_sectors_to_skip_[i] = SectorFromAddress(reserved_addresses[i]);
+    DBG("    Skip sector %u",
+        SectorIndex(SectorFromAddress(reserved_addresses[i])));
   }
+  const span sectors_to_skip(temp_sectors_to_skip_, reserved_addresses.size());
 
   // Step 1: Try to find a sectors with stale keys and no valid keys (no
   // relocation needed). If any such sectors are found, use the sector with the
@@ -1009,15 +871,15 @@
 }
 
 Status KeyValueStore::GarbageCollectPartial(
-    span<const Address> addresses_to_skip) {
+    span<const Address> reserved_addresses) {
   DBG("Garbage Collect a single sector");
-  for (auto address : addresses_to_skip) {
+  for (Address address : reserved_addresses) {
     DBG("   Avoid address %u", unsigned(address));
   }
 
   // Step 1: Find the sector to garbage collect
   SectorDescriptor* sector_to_gc =
-      FindSectorToGarbageCollect(addresses_to_skip);
+      FindSectorToGarbageCollect(reserved_addresses);
 
   if (sector_to_gc == nullptr) {
     // Nothing to GC.
@@ -1025,19 +887,19 @@
   }
 
   // Step 2: Garbage collect the selected sector.
-  return GarbageCollectSector(sector_to_gc, addresses_to_skip);
+  return GarbageCollectSector(sector_to_gc, reserved_addresses);
 }
 
 Status KeyValueStore::RelocateKeyAddressesInSector(
-    internal::SectorDescriptor& sector_to_gc,
-    internal::KeyDescriptor& descriptor,
-    span<const Address> addresses_to_skip) {
-  for (FlashPartition::Address& address : descriptor.addresses()) {
+    SectorDescriptor& sector_to_gc,
+    const EntryMetadata& metadata,
+    span<const Address> reserved_addresses) {
+  for (FlashPartition::Address& address : metadata.addresses()) {
     if (AddressInSector(sector_to_gc, address)) {
-      DBG("  Relocate entry for Key 0x%08zx, sector %u",
-          size_t(descriptor.hash()),
+      DBG("  Relocate entry for Key 0x%08" PRIx32 ", sector %u",
+          metadata.hash(),
           SectorIndex(SectorFromAddress(address)));
-      TRY(RelocateEntry(descriptor, address, addresses_to_skip));
+      TRY(RelocateEntry(metadata, address, reserved_addresses));
     }
   }
 
@@ -1045,12 +907,12 @@
 };
 
 Status KeyValueStore::GarbageCollectSector(
-    SectorDescriptor* sector_to_gc, span<const Address> addresses_to_skip) {
+    SectorDescriptor* sector_to_gc, span<const Address> reserved_addresses) {
   // Step 1: Move any valid entries in the GC sector to other sectors
   if (sector_to_gc->valid_bytes() != 0) {
-    for (KeyDescriptor& descriptor : key_descriptors_) {
+    for (const EntryMetadata& metadata : entry_cache_) {
       TRY(RelocateKeyAddressesInSector(
-          *sector_to_gc, descriptor, addresses_to_skip));
+          *sector_to_gc, metadata, reserved_addresses));
     }
   }
 
@@ -1073,7 +935,7 @@
 KeyValueStore::Entry KeyValueStore::CreateEntry(Address address,
                                                 string_view key,
                                                 span<const byte> value,
-                                                KeyDescriptor::State state) {
+                                                EntryState state) {
   // Always bump the transaction ID when creating a new entry.
   //
   // Burning transaction IDs prevents inconsistencies between flash and memory
@@ -1088,7 +950,7 @@
   // By always burning transaction IDs, the above problem can't happen.
   last_transaction_id_ += 1;
 
-  if (state == KeyDescriptor::kDeleted) {
+  if (state == EntryState::kDeleted) {
     return Entry::Tombstone(
         partition_, address, formats_.primary(), key, last_transaction_id_);
   }
@@ -1100,7 +962,7 @@
                       last_transaction_id_);
 }
 
-void KeyValueStore::LogDebugInfo() {
+void KeyValueStore::LogDebugInfo() const {
   const size_t sector_size_bytes = partition_.sector_size_bytes();
   DBG("====================== KEY VALUE STORE DUMP =========================");
   DBG(" ");
@@ -1113,18 +975,18 @@
   DBG("  Alignment        = %zu", partition_.alignment_bytes());
   DBG(" ");
   DBG("Key descriptors:");
-  DBG("  Entry count     = %zu", key_descriptors_.size());
-  DBG("  Max entry count = %zu", key_descriptors_.max_size());
+  DBG("  Entry count     = %zu", entry_cache_.total_entries());
+  DBG("  Max entry count = %zu", entry_cache_.max_entries());
   DBG(" ");
   DBG("      #     hash        version    address   address (hex)");
-  for (size_t i = 0; i < key_descriptors_.size(); ++i) {
-    const KeyDescriptor& kd = key_descriptors_[i];
+  size_t i = 0;
+  for (const EntryMetadata& metadata : entry_cache_) {
     DBG("   |%3zu: | %8zx  |%8zu  | %8zu | %8zx",
-        i,
-        size_t(kd.hash()),
-        size_t(kd.transaction_id()),
-        size_t(kd.address()),
-        size_t(kd.address()));
+        i++,
+        size_t(metadata.hash()),
+        size_t(metadata.transaction_id()),
+        size_t(metadata.first_address()),
+        size_t(metadata.first_address()));
   }
   DBG(" ");
 
@@ -1188,13 +1050,13 @@
 }
 
 void KeyValueStore::LogKeyDescriptor() const {
-  DBG("Key descriptors: count %zu", key_descriptors_.size());
-  for (auto& key : key_descriptors_) {
-    DBG("  - Key: %s, hash %#zx, transaction ID %zu, address %#zx",
-        key.deleted() ? "Deleted" : "Valid",
-        static_cast<size_t>(key.hash()),
-        static_cast<size_t>(key.transaction_id()),
-        static_cast<size_t>(key.address()));
+  DBG("Key descriptors: count %zu", entry_cache_.total_entries());
+  for (auto& metadata : entry_cache_) {
+    DBG("  - Key: %s, hash %#zx, transaction ID %zu, first address %#zx",
+        metadata.deleted() ? "Deleted" : "Valid",
+        static_cast<size_t>(metadata.hash()),
+        static_cast<size_t>(metadata.transaction_id()),
+        static_cast<size_t>(metadata.first_address()));
   }
 }
 
diff --git a/pw_kvs/public/pw_kvs/internal/entry.h b/pw_kvs/public/pw_kvs/internal/entry.h
index c2f9cf7..bcb6e41 100644
--- a/pw_kvs/public/pw_kvs/internal/entry.h
+++ b/pw_kvs/public/pw_kvs/internal/entry.h
@@ -25,6 +25,7 @@
 #include "pw_kvs/checksum.h"
 #include "pw_kvs/flash_memory.h"
 #include "pw_kvs/format.h"
+#include "pw_kvs/internal/hash.h"
 #include "pw_kvs/internal/key_descriptor.h"
 #include "pw_span/span.h"
 
@@ -87,19 +88,13 @@
   Entry() = default;
 
   KeyDescriptor descriptor(std::string_view key) const {
-    return KeyDescriptor(
-        key,
-        transaction_id(),
-        address(),
-        deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
+    return descriptor(Hash(key));
   }
 
   KeyDescriptor descriptor(uint32_t key_hash) const {
-    return KeyDescriptor(
-        key_hash,
-        transaction_id(),
-        address(),
-        deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
+    return KeyDescriptor{key_hash,
+                         transaction_id(),
+                         deleted() ? EntryState::kDeleted : EntryState::kValid};
   }
 
   StatusWithSize Write(std::string_view key, span<const std::byte> value) const;
diff --git a/pw_kvs/public/pw_kvs/internal/entry_cache.h b/pw_kvs/public/pw_kvs/internal/entry_cache.h
new file mode 100644
index 0000000..5cbef5c
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/internal/entry_cache.h
@@ -0,0 +1,219 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+//     https://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.
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+#include <string_view>
+
+#include "pw_containers/vector.h"
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/key_descriptor.h"
+#include "pw_span/span.h"
+
+namespace pw::kvs::internal {
+
+// Caches information about a key-value entry. Facilitates quickly finding
+// entries without having to read flash.
+class EntryMetadata {
+ public:
+  using Address = FlashPartition::Address;
+
+  EntryMetadata() = default;
+
+  uint32_t hash() const { return descriptor_->key_hash; }
+
+  uint32_t transaction_id() const { return descriptor_->transaction_id; }
+
+  EntryState state() const { return descriptor_->state; }
+
+  bool deleted() const { return state() == EntryState::kDeleted; }
+
+  // The first known address of this entry.
+  uint32_t first_address() const { return addresses_[0]; }
+
+  // All addresses for this entry, including redundant entries.
+  const span<Address>& addresses() const { return addresses_; }
+
+  // True if the KeyDesctiptor's transaction ID is newer than the specified ID.
+  bool IsNewerThan(uint32_t other_transaction_id) const {
+    // TODO: Consider handling rollover.
+    return transaction_id() > other_transaction_id;
+  }
+
+  // Adds a new address to the entry metadata. MUST NOT be called more than
+  // allowed by the redundancy.
+  void AddNewAddress(Address address) {
+    addresses_[addresses_.size()] = address;
+    addresses_ = span(addresses_.begin(), addresses_.size() + 1);
+  }
+
+  // Resets the KeyDescrtiptor and addresses to refer to the provided
+  // KeyDescriptor and address.
+  void Reset(const KeyDescriptor& descriptor, Address address);
+
+ private:
+  friend class EntryCache;
+
+  constexpr EntryMetadata(KeyDescriptor& descriptor, span<Address> addresses)
+      : descriptor_(&descriptor), addresses_(addresses) {}
+
+  KeyDescriptor* descriptor_;
+  span<Address> addresses_;
+};
+
+// Tracks entry metadata. Combines KeyDescriptors and with their associated
+// addresses.
+class EntryCache {
+ public:
+  using Address = FlashPartition::Address;
+
+  // The type to use for an address list with the specified number of entries
+  // and redundancy. kRedundancy extra entries are added to make room for a
+  // temporary list of entry addresses.
+  template <size_t kMaxEntries, size_t kRedundancy>
+  using AddressList = Address[kMaxEntries * kRedundancy + kRedundancy];
+
+  constexpr EntryCache(Vector<KeyDescriptor>& descriptors,
+                       Address* addresses,
+                       size_t redundancy)
+      : descriptors_(descriptors),
+        addresses_(addresses),
+        redundancy_(redundancy) {}
+
+  // Clears all
+  void Reset() { descriptors_.clear(); }
+
+  // Finds the metadata for an entry matching a particular key. Searches for a
+  // KeyDescriptor that matches this key and sets *metadata to point to it if
+  // one is found.
+  //
+  //             OK: there is a matching descriptor and *metadata is set
+  //      NOT_FOUND: there is no descriptor that matches this key, but this key
+  //                 has a unique hash (and could potentially be added to the
+  //                 KVS)
+  // ALREADY_EXISTS: there is no descriptor that matches this key, but the
+  //                 key's hash collides with the hash for an existing
+  //                 descriptor
+  //
+  Status Find(FlashPartition& partition,
+              std::string_view key,
+              EntryMetadata* metadata) const;
+
+  // Searches for a KeyDescriptor that matches this key and sets *metadata to
+  // point to it if one is found.
+  //
+  //          OK: there is a matching descriptor and *metadata is set
+  //   NOT_FOUND: there is no descriptor that matches this key
+  //
+  Status FindExisting(FlashPartition& partition,
+                      std::string_view key,
+                      EntryMetadata* metadata) const;
+
+  // Adds a new descriptor to the descriptor list. Must NOT be full!
+  EntryMetadata AddNew(const KeyDescriptor& entry, Address address);
+
+  // Adds a new descriptor, overwrites an existing one, or adds an additional
+  // redundant address to one. The sector size is included for checking that
+  // redundant entries are in different sectors.
+  Status AddNewOrUpdateExisting(const KeyDescriptor& descriptor,
+                                Address address,
+                                size_t sector_size_bytes);
+
+  // Returns a pointer to an array of redundancy() addresses for temporary use.
+  // This is used by the KeyValueStore to track reserved addresses when finding
+  // space for a new entry.
+  Address* TempReservedAddressesForWrite() const {
+    return &addresses_[descriptors_.max_size() * redundancy_];
+  }
+
+  // The number of copies of each entry.
+  size_t redundancy() const { return redundancy_; }
+
+  // True if no more entries can be added to the cache.
+  bool full() const { return descriptors_.full(); }
+
+  // The total number of entries, including tombstone entries.
+  size_t total_entries() const { return descriptors_.size(); }
+
+  // The total number of present (non-tombstone) entries.
+  size_t present_entries() const;
+
+  // The maximum number of entries supported by this EntryCache.
+  size_t max_entries() const { return descriptors_.max_size(); }
+
+  // Iterates over the EntryCache as EntryMetadata objects.
+  class iterator {
+   public:
+    iterator& operator++() {
+      ++metadata_.descriptor_;
+      return *this;
+    }
+    iterator& operator++(int) { return operator++(); }
+
+    // Updates the EntryMetadata object.
+    const EntryMetadata& operator*() const {
+      metadata_.addresses_ = entry_cache_.addresses(
+          metadata_.descriptor_ - entry_cache_.descriptors_.begin());
+      return metadata_;
+    }
+    const EntryMetadata* operator->() const { return &operator*(); }
+
+    constexpr bool operator==(const iterator& rhs) const {
+      return metadata_.descriptor_ == rhs.metadata_.descriptor_;
+    }
+    constexpr bool operator!=(const iterator& rhs) const {
+      return metadata_.descriptor_ != rhs.metadata_.descriptor_;
+    }
+
+   private:
+    friend class EntryCache;
+
+    constexpr iterator(const EntryCache* entry_cache, KeyDescriptor* descriptor)
+        : entry_cache_(*entry_cache), metadata_(*descriptor, {}) {}
+
+    const EntryCache& entry_cache_;
+
+    // Mark this mutable so it can be updated in the const operator*() method.
+    // This allows lazy updating of the EntryMetadata.
+    mutable EntryMetadata metadata_;
+  };
+
+  using const_iterator = iterator;
+
+  iterator begin() const { return iterator(this, descriptors_.begin()); }
+  iterator end() const { return iterator(this, descriptors_.end()); }
+
+ private:
+  int FindIndex(uint32_t key_hash) const;
+
+  // Adds the address to the descriptor at the specified index if there is an
+  // address slot available.
+  void AddAddressIfRoom(size_t descriptor_index, Address address);
+
+  // Returns a span of the valid addresses for the descriptor.
+  span<Address> addresses(size_t descriptor_index) const;
+
+  Address* first_address(size_t descriptor_index) const {
+    return &addresses_[descriptor_index * redundancy_];
+  }
+
+  Address* ResetAddresses(size_t descriptor_index, Address address);
+
+  Vector<KeyDescriptor>& descriptors_;
+  FlashPartition::Address* const addresses_;
+  const size_t redundancy_;
+};
+
+}  // namespace pw::kvs::internal
diff --git a/pw_kvs/public/pw_kvs/internal/key_descriptor.h b/pw_kvs/public/pw_kvs/internal/key_descriptor.h
index aa915f9..a7c7183 100644
--- a/pw_kvs/public/pw_kvs/internal/key_descriptor.h
+++ b/pw_kvs/public/pw_kvs/internal/key_descriptor.h
@@ -13,85 +13,19 @@
 // the License.
 #pragma once
 
-#include <cstddef>
 #include <cstdint>
-#include <string_view>
-
-#include "pw_containers/vector.h"
-#include "pw_kvs/flash_memory.h"
-#include "pw_kvs/internal/hash.h"
 
 namespace pw::kvs::internal {
 
-constexpr size_t kEntryRedundancy = 2;
+// Whether an entry is present or deleted.
+enum class EntryState : bool { kValid, kDeleted };
 
-// Caches information about a key-value entry. Facilitates quickly finding
-// entries without having to read flash.
-class KeyDescriptor {
- public:
-  enum State { kValid, kDeleted };
+// Essential metadata for an entry that is stored in memory.
+struct KeyDescriptor {
+  uint32_t key_hash;
+  uint32_t transaction_id;
 
-  uint32_t hash() const { return key_hash_; }
-  uint32_t transaction_id() const { return transaction_id_; }
-
-  // TODO: remove address() once all the use of it is gone.
-  uint32_t address() const { return addresses_[0]; }
-
-  Status UpdateAddress(FlashPartition::Address old_address,
-                       FlashPartition::Address new_address) {
-    for (auto& address : addresses()) {
-      if (address == old_address) {
-        address = new_address;
-        return Status::OK;
-      }
-    }
-
-    // Unable to find the address to update.
-    return Status::INVALID_ARGUMENT;
-  }
-
-  Vector<FlashPartition::Address, kEntryRedundancy>& addresses() {
-    return addresses_;
-  }
-  const Vector<FlashPartition::Address, kEntryRedundancy>& addresses() const {
-    return addresses_;
-  }
-
-  State state() const { return state_; }
-
-  // True if the KeyDesctiptor's transaction ID is newer than the specified ID.
-  bool IsNewerThan(uint32_t other_transaction_id) const {
-    // TODO: Consider handling rollover.
-    return transaction_id() > other_transaction_id;
-  }
-
-  bool deleted() const { return state_ == kDeleted; }
-
- private:
-  friend class Entry;
-
-  KeyDescriptor(uint32_t key_hash,
-                uint32_t version,
-                FlashPartition::Address address,
-                State initial_state)
-      : key_hash_(key_hash), transaction_id_(version), state_(initial_state) {
-    addresses_.assign(1, address);
-  }
-
-  KeyDescriptor(std::string_view key,
-                uint32_t version,
-                FlashPartition::Address address,
-                State initial_state)
-      : KeyDescriptor(Hash(key), version, address, initial_state) {}
-
-  uint32_t key_hash_;
-  uint32_t transaction_id_;
-
-  static_assert(kEntryRedundancy > 0u);
-  Vector<FlashPartition::Address, kEntryRedundancy> addresses_;
-
-  // TODO: This information could be packed into the above fields to save RAM.
-  State state_;
+  EntryState state;  // TODO: Pack into transaction ID? or something?
 };
 
 }  // namespace pw::kvs::internal
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 9888e7f..8276c20 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -24,6 +24,7 @@
 #include "pw_kvs/flash_memory.h"
 #include "pw_kvs/format.h"
 #include "pw_kvs/internal/entry.h"
+#include "pw_kvs/internal/entry_cache.h"
 #include "pw_kvs/internal/key_descriptor.h"
 #include "pw_kvs/internal/sector_descriptor.h"
 #include "pw_kvs/internal/span_traits.h"
@@ -183,7 +184,7 @@
     return GarbageCollectPartial(span<const Address>());
   }
 
-  void LogDebugInfo();
+  void LogDebugInfo() const;
 
   // Classes and functions to support STL-style iteration.
   class iterator;
@@ -197,7 +198,7 @@
     // KeyValueStore::Get.
     StatusWithSize Get(span<std::byte> value_buffer,
                        size_t offset_bytes = 0) const {
-      return kvs_.Get(key(), *descriptor_, value_buffer, offset_bytes);
+      return kvs_.Get(key(), *iterator_, value_buffer, offset_bytes);
     }
 
     template <typename Pointer,
@@ -205,24 +206,24 @@
     Status Get(const Pointer& pointer) const {
       using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
       CheckThatObjectCanBePutOrGet<T>();
-      return kvs_.FixedSizeGet(key(), *descriptor_, pointer, sizeof(T));
+      return kvs_.FixedSizeGet(key(), *iterator_, pointer, sizeof(T));
     }
 
     // Reads the size of the value referred to by this iterator. Equivalent to
     // KeyValueStore::ValueSize.
-    StatusWithSize ValueSize() const { return kvs_.ValueSize(*descriptor_); }
+    StatusWithSize ValueSize() const { return kvs_.ValueSize(*iterator_); }
 
    private:
     friend class iterator;
 
     constexpr Item(const KeyValueStore& kvs,
-                   const internal::KeyDescriptor* descriptor)
-        : kvs_(kvs), descriptor_(descriptor), key_buffer_{} {}
+                   const internal::EntryCache::iterator& iterator)
+        : kvs_(kvs), iterator_(iterator), key_buffer_{} {}
 
     void ReadKey();
 
     const KeyValueStore& kvs_;
-    const internal::KeyDescriptor* descriptor_;
+    internal::EntryCache::iterator iterator_;
 
     // Buffer large enough for a null-terminated version of any valid key.
     std::array<char, internal::Entry::kMaxKeyLength + 1> key_buffer_;
@@ -241,24 +242,23 @@
     }
 
     const Item* operator->() {
-      operator*();  // Read the key into the Item object.
-      return &item_;
+      return &operator*();  // Read the key into the Item object.
     }
 
     constexpr bool operator==(const iterator& rhs) const {
-      return item_.descriptor_ == rhs.item_.descriptor_;
+      return item_.iterator_ == rhs.item_.iterator_;
     }
 
     constexpr bool operator!=(const iterator& rhs) const {
-      return item_.descriptor_ != rhs.item_.descriptor_;
+      return item_.iterator_ != rhs.item_.iterator_;
     }
 
    private:
     friend class KeyValueStore;
 
     constexpr iterator(const KeyValueStore& kvs,
-                       const internal::KeyDescriptor* descriptor)
-        : item_(kvs, descriptor) {}
+                       const internal::EntryCache::iterator& iterator)
+        : item_(kvs, iterator) {}
 
     Item item_;
   };
@@ -266,12 +266,12 @@
   using const_iterator = iterator;  // Standard alias for iterable types.
 
   iterator begin() const;
-  iterator end() const { return iterator(*this, key_descriptors_.end()); }
+  iterator end() const { return iterator(*this, entry_cache_.end()); }
 
   // Returns the number of valid entries in the KeyValueStore.
-  size_t size() const;
+  size_t size() const { return entry_cache_.present_entries(); }
 
-  size_t max_size() const { return key_descriptors_.max_size(); }
+  size_t max_size() const { return entry_cache_.max_entries(); }
 
   size_t empty() const { return size() == 0u; }
 
@@ -288,7 +288,8 @@
 
   StorageStats GetStorageStats() const;
 
-  size_t redundancy() { return redundancy_; }
+  // Level of redundancy to use for writing entries.
+  size_t redundancy() const { return entry_cache_.redundancy(); }
 
  protected:
   using Address = FlashPartition::Address;
@@ -299,13 +300,18 @@
   // In the future, will be able to provide additional EntryFormats for
   // backwards compatibility.
   KeyValueStore(FlashPartition* partition,
-                Vector<KeyDescriptor>& key_descriptor_list,
-                Vector<SectorDescriptor>& sector_descriptor_list,
+                span<const EntryFormat> formats,
+                const Options& options,
                 size_t redundancy,
-                span<const EntryFormat> format,
-                const Options& options);
+                Vector<SectorDescriptor>& sector_descriptor_list,
+                const SectorDescriptor** temp_sectors_to_skip,
+                Vector<KeyDescriptor>& key_descriptor_list,
+                Address* addresses);
 
  private:
+  using EntryMetadata = internal::EntryMetadata;
+  using EntryState = internal::EntryState;
+
   template <typename T>
   static constexpr void CheckThatObjectCanBePutOrGet() {
     static_assert(
@@ -319,17 +325,13 @@
   Status ScanForEntry(const SectorDescriptor& sector,
                       Address start_address,
                       Address* next_entry_address);
-  Status AppendNewOrOverwriteStaleExistingDescriptor(
-      const KeyDescriptor& key_descriptor);
-
-  KeyDescriptor* FindDescriptor(uint32_t hash);
 
   Status PutBytes(std::string_view key, span<const std::byte> value);
 
-  StatusWithSize ValueSize(const KeyDescriptor& descriptor) const;
+  StatusWithSize ValueSize(const EntryMetadata& metadata) const;
 
   StatusWithSize Get(std::string_view key,
-                     const KeyDescriptor& descriptor,
+                     const EntryMetadata& metadata,
                      span<std::byte> value_buffer,
                      size_t offset_bytes) const;
 
@@ -338,32 +340,14 @@
                       size_t size_bytes) const;
 
   Status FixedSizeGet(std::string_view key,
-                      const KeyDescriptor& descriptor,
+                      const EntryMetadata& descriptor,
                       void* value,
                       size_t size_bytes) const;
 
   Status CheckOperation(std::string_view key) const;
 
-  Status FindKeyDescriptor(std::string_view key,
-                           const KeyDescriptor** result) const;
-
-  // Non-const version of FindKeyDescriptor.
-  Status FindKeyDescriptor(std::string_view key, KeyDescriptor** result) {
-    return static_cast<const KeyValueStore&>(*this).FindKeyDescriptor(
-        key, const_cast<const KeyDescriptor**>(result));
-  }
-
-  Status FindExistingKeyDescriptor(std::string_view key,
-                                   const KeyDescriptor** result) const;
-
-  Status FindExistingKeyDescriptor(std::string_view key,
-                                   KeyDescriptor** result) {
-    return static_cast<const KeyValueStore&>(*this).FindExistingKeyDescriptor(
-        key, const_cast<const KeyDescriptor**>(result));
-  }
-
-  Status WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
-                                  KeyDescriptor::State new_state,
+  Status WriteEntryForExistingKey(EntryMetadata& metadata,
+                                  EntryState new_state,
                                   std::string_view key,
                                   span<const std::byte> value);
 
@@ -371,14 +355,14 @@
 
   Status WriteEntry(std::string_view key,
                     span<const std::byte> value,
-                    KeyDescriptor::State new_state,
-                    KeyDescriptor* prior_descriptor = nullptr,
+                    EntryState new_state,
+                    EntryMetadata* prior_metadata = nullptr,
                     size_t prior_size = 0);
 
-  KeyDescriptor& UpdateKeyDescriptor(const Entry& new_entry,
-                                     std::string_view key,
-                                     KeyDescriptor* prior_descriptor,
-                                     size_t prior_size);
+  EntryMetadata UpdateKeyDescriptor(const Entry& new_entry,
+                                    std::string_view key,
+                                    EntryMetadata* prior_metadata,
+                                    size_t prior_size);
 
   Status GetSectorForWrite(SectorDescriptor** sector,
                            size_t entry_size,
@@ -388,26 +372,25 @@
                      std::string_view key,
                      span<const std::byte> value);
 
-  Status RelocateEntry(KeyDescriptor& key_descriptor,
+  Status RelocateEntry(const EntryMetadata& metadata,
                        KeyValueStore::Address& address,
                        span<const Address> addresses_to_skip);
 
-  Status MoveEntry(Address new_address, Entry& entry);
-
   enum FindSectorMode { kAppendEntry, kGarbageCollect };
 
   Status FindSectorWithSpace(SectorDescriptor** found_sector,
                              size_t size,
                              FindSectorMode find_mode,
-                             span<const Address> addresses_to_skip);
+                             span<const Address> addresses_to_skip,
+                             span<const Address> reserved_addresses);
 
   SectorDescriptor* FindSectorToGarbageCollect(
       span<const Address> addresses_to_avoid);
 
   Status GarbageCollectPartial(span<const Address> addresses_to_skip);
 
-  Status RelocateKeyAddressesInSector(internal::SectorDescriptor& sector_to_gc,
-                                      internal::KeyDescriptor& descriptor,
+  Status RelocateKeyAddressesInSector(SectorDescriptor& sector_to_gc,
+                                      const EntryMetadata& descriptor,
                                       span<const Address> addresses_to_skip);
 
   Status GarbageCollectSector(SectorDescriptor* sector_to_gc,
@@ -428,13 +411,17 @@
     return SectorIndex(sector) * partition_.sector_size_bytes();
   }
 
-  SectorDescriptor* SectorFromAddress(const FlashPartition::Address address) {
+  SectorDescriptor* SectorFromAddress(Address address) {
     const size_t index = address / partition_.sector_size_bytes();
     // TODO: Add boundary checking once asserts are supported.
     // DCHECK_LT(index, sector_map_size_);`
     return &sectors_[index];
   }
 
+  const SectorDescriptor* SectorFromAddress(Address address) const {
+    return &sectors_[address / partition_.sector_size_bytes()];
+  }
+
   Address NextWritableAddress(const SectorDescriptor* sector) const {
     return SectorBaseAddress(sector) + partition_.sector_size_bytes() -
            sector->writable_bytes();
@@ -443,7 +430,7 @@
   internal::Entry CreateEntry(Address address,
                               std::string_view key,
                               span<const std::byte> value,
-                              KeyDescriptor::State state);
+                              EntryState state);
 
   void LogSectors() const;
   void LogKeyDescriptor() const;
@@ -453,13 +440,14 @@
 
   // Unordered list of KeyDescriptors. Finding a key requires scanning and
   // verifying a match by reading the actual entry.
-  Vector<KeyDescriptor>& key_descriptors_;
+  internal::EntryCache entry_cache_;
 
   // List of sectors used by this KVS.
   Vector<SectorDescriptor>& sectors_;
 
-  // Level of redundancy to use for writing entries.
-  const size_t redundancy_;
+  // Temp buffer with redundancy() * 2 - 1 entries for use in RelocateEntry.
+  // Used in FindSectorWithSpace and FindSectorToGarbageCollect.
+  const SectorDescriptor** const temp_sectors_to_skip_;
 
   Options options_;
 
@@ -503,11 +491,13 @@
                       span<const EntryFormat, kEntryFormats> formats,
                       const Options& options = {})
       : KeyValueStore(partition,
-                      key_descriptors_,
-                      sectors_,
-                      kRedundancy,
                       formats_,
-                      options) {
+                      options,
+                      kRedundancy,
+                      sectors_,
+                      temp_sectors_to_skip_,
+                      key_descriptors_,
+                      addresses_) {
     std::copy(formats.begin(), formats.end(), formats_.begin());
   }
 
@@ -515,11 +505,28 @@
   static_assert(kMaxEntries > 0u);
   static_assert(kMaxUsableSectors > 0u);
   static_assert(kRedundancy > 0u);
-  static_assert(kRedundancy <= internal::kEntryRedundancy);
   static_assert(kEntryFormats > 0u);
 
-  Vector<KeyDescriptor, kMaxEntries> key_descriptors_;
   Vector<SectorDescriptor, kMaxUsableSectors> sectors_;
+
+  // Allocate space for an list of SectorDescriptors to avoid while searching
+  // for space to write entries. This is used to avoid changing sectors that are
+  // reserved for a new entry or marked as having other redundant copies of an
+  // entry. Up to kRedundancy sectors are reserved for a new entry, and up to
+  // kRedundancy - 1 sectors can have redundant copies of an entry, giving a
+  // maximum of 2 * kRedundancy - 1 sectors to avoid.
+  const SectorDescriptor* temp_sectors_to_skip_[2 * kRedundancy - 1];
+
+  // KeyDescriptors for use by the KVS's EntryCache.
+  Vector<KeyDescriptor, kMaxEntries> key_descriptors_;
+
+  // An array of addresses associated with the KeyDescriptors for use with the
+  // EntryCache. To support having KeyValueStores with different redundancies,
+  // the addresses are stored in a parallel array instead of inside
+  // KeyDescriptors.
+  internal::EntryCache::AddressList<kRedundancy, kMaxEntries> addresses_;
+
+  // EntryFormats that can be read by this KeyValueStore.
   std::array<EntryFormat, kEntryFormats> formats_;
 };