diff --git a/pw_kvs/public/pw_kvs/assert.h b/pw_kvs/public/pw_kvs/assert.h
deleted file mode 100644
index cc20a61..0000000
--- a/pw_kvs/public/pw_kvs/assert.h
+++ /dev/null
@@ -1,69 +0,0 @@
-// 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 <algorithm>
-#include <type_traits>
-
-// Compares the provided value to nullptr and returns it. This is intended to be
-// used as part of another statement.
-#define CHECK_NOTNULL(value) \
-  ::pw::log::CheckNotNull("", __LINE__, #value " != nullptr", value)
-
-// In release builds, DCHECK_NOTNULL simply passes along the value.
-// DCHECK_NOTNULL must not be used as a standalone expression, since the result
-// would be unused on release builds. Use DCHECK_NE instead.
-//#define DCHECK_NOTNULL(value) value
-
-#define DCHECK_NOTNULL(value) \
-  ::pw::log::DCheckNotNull("", __LINE__, #value " != nullptr", value)
-
-namespace pw::log {
-
-template <typename T>
-constexpr T CheckNotNull(const char* /* file */,
-                         unsigned /* line */,
-                         const char* /* message */,
-                         T&& value) {
-  static_assert(!std::is_null_pointer<T>(),
-                "CHECK_NOTNULL statements cannot be passed nullptr");
-  if (value == nullptr) {
-    // std::exit(1);
-  }
-  return std::forward<T>(value);
-}
-
-// DCHECK_NOTNULL cannot be used in standalone expressions, so add a
-// [[nodiscard]] attribute to prevent this in debug builds. Standalone
-// DCHECK_NOTNULL statements in release builds trigger an unused-value warning.
-template <typename T>
-[[nodiscard]] constexpr T DCheckNotNull(const char* file,
-                                        unsigned line,
-                                        const char* message,
-                                        T&& value) {
-  return CheckNotNull<T>(file, line, message, std::forward<T>(value));
-}
-
-}  // namespace pw::log
-
-// Assert stubs
-#define DCHECK CHECK
-#define DCHECK_EQ CHECK_EQ
-
-#define CHECK(...)
-#define CHECK_EQ(...)
-#define CHECK_GE(...)
-#define CHECK_GT(...)
-#define CHECK_LE(...)
-#define CHECK_LT(...)
diff --git a/pw_kvs/public/pw_kvs/checksum.h b/pw_kvs/public/pw_kvs/checksum.h
new file mode 100644
index 0000000..f7b01a1
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/checksum.h
@@ -0,0 +1,57 @@
+// 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 "pw_span/span.h"
+#include "pw_status/status.h"
+
+namespace pw::kvs {
+
+class ChecksumAlgorithm {
+ public:
+  // Resets the checksum to its initial state.
+  virtual void Reset() = 0;
+
+  // Updates the checksum with the provided data.
+  virtual Status Update(span<const std::byte> data_to_checksum) = 0;
+
+  // Convnenience wrapper.
+  Status Update(const void* data, size_t size) {
+    return Update(span(static_cast<const std::byte*>(data), size));
+  }
+
+  // Returns the current state of the checksum algorithm.
+  constexpr const span<const std::byte>& state() const { return state_; }
+
+  // Returns the size of the checksum's state.
+  constexpr size_t size_bytes() const { return state_.size(); }
+
+  // Compares a calculated checksum to this checksum's data.
+  Status Verify(span<const std::byte> calculated_checksum) const;
+
+ protected:
+  // Derived class provides a span of its state buffer.
+  constexpr ChecksumAlgorithm(span<const std::byte> state) : state_(state) {}
+
+  // Protected destructor prevents deleting ChecksumAlgorithms from the base
+  // class, so that it is safe to have a non-virtual destructor.
+  ~ChecksumAlgorithm() = default;
+
+ private:
+  span<const std::byte> state_;
+};
+
+}  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/flash.h b/pw_kvs/public/pw_kvs/flash.h
deleted file mode 100644
index 819f8e2..0000000
--- a/pw_kvs/public/pw_kvs/flash.h
+++ /dev/null
@@ -1,33 +0,0 @@
-// 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 "pw_kvs/flash_memory.h"
-
-namespace pw::kvs {
-
-// Writes a buffer which is not guaranteed to be aligned, pads remaining
-// bytes with 0.
-Status PaddedWrite(FlashPartition* partition,
-                   FlashPartition::Address address,
-                   const void* buffer,
-                   uint16_t size);
-
-// Read into a buffer when size is not guaranteed to be aligned.
-Status UnalignedRead(FlashPartition* partition,
-                     void* buffer,
-                     FlashPartition::Address address,
-                     uint16_t size);
-
-}  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
index b69eeb2..5495141 100644
--- a/pw_kvs/public/pw_kvs/flash_memory.h
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -13,32 +13,50 @@
 // the License.
 #pragma once
 
-#include <algorithm>
-#include <cinttypes>
-#include <cstring>
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
 
-#include "pw_kvs/assert.h"
-#include "pw_kvs/partition_table_entry.h"
-#include "pw_log/log.h"
+#include "pw_span/span.h"
 #include "pw_status/status.h"
+#include "pw_status/status_with_size.h"
+
+namespace pw {
+
+// TODO: These are general-purpose utility functions that should be moved
+//       elsewhere.
+constexpr size_t AlignDown(size_t value, size_t alignment) {
+  return (value / alignment) * alignment;
+}
+
+constexpr size_t AlignUp(size_t value, size_t alignment) {
+  return (value + alignment - 1) / alignment * alignment;
+}
+
+}  // namespace pw
 
 namespace pw::kvs {
 
+enum class PartitionPermission : bool {
+  kReadOnly,
+  kReadAndWrite,
+};
+
 class FlashMemory {
  public:
   // The flash address is in the range of: 0 to FlashSize.
   typedef uint32_t Address;
-  constexpr FlashMemory(uint32_t sector_size,
-                        uint32_t sector_count,
-                        uint8_t alignment,
+  constexpr FlashMemory(size_t sector_size,
+                        size_t sector_count,
+                        size_t alignment,
                         uint32_t start_address = 0,
                         uint32_t sector_start = 0,
-                        uint8_t erased_memory_content = 0xFF)
+                        std::byte erased_memory_content = std::byte{0xFF})
       : sector_size_(sector_size),
         flash_sector_count_(sector_count),
         alignment_(alignment),
         start_address_(start_address),
-        sector_start_(sector_start),
+        start_sector_(sector_start),
         erased_memory_content_(erased_memory_content) {}
 
   virtual ~FlashMemory() = default;
@@ -54,43 +72,40 @@
   //          TIMEOUT, on timeout.
   //          INVALID_ARGUMENT, if address or sector count is invalid.
   //          UNKNOWN, on HAL error
-  virtual Status Erase(Address flash_address, uint32_t num_sectors) = 0;
+  virtual Status Erase(Address flash_address, size_t num_sectors) = 0;
 
   // Reads bytes from flash into buffer. Blocking call.
   // Returns: OK, on success.
   //          TIMEOUT, on timeout.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  virtual Status Read(uint8_t* destination_ram_address,
-                      Address source_flash_address,
-                      uint32_t len) = 0;
+  virtual StatusWithSize Read(Address address, span<std::byte> output) = 0;
 
   // Writes bytes to flash. Blocking call.
   // Returns: OK, on success.
   //          TIMEOUT, on timeout.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  virtual Status Write(Address destination_flash_address,
-                       const uint8_t* source_ram_address,
-                       uint32_t len) = 0;
+  virtual StatusWithSize Write(Address destination_flash_address,
+                               span<const std::byte> data) = 0;
 
   // Convert an Address to an MCU pointer, this can be used for memory
   // mapped reads. Return NULL if the memory is not memory mapped.
-  virtual uint8_t* FlashAddressToMcuAddress(Address) const { return nullptr; }
+  virtual std::byte* FlashAddressToMcuAddress(Address) const { return nullptr; }
 
-  // GetStartSector() is useful for FlashMemory instances where the
+  // start_sector() is useful for FlashMemory instances where the
   // sector start is not 0. (ex.: cases where there are portions of flash
   // that should be handled independently).
-  constexpr uint32_t GetStartSector() const { return sector_start_; }
-  constexpr uint32_t GetSectorSizeBytes() const { return sector_size_; }
-  constexpr uint32_t GetSectorCount() const { return flash_sector_count_; }
-  constexpr uint8_t GetAlignmentBytes() const { return alignment_; }
-  constexpr uint32_t GetSizeBytes() const {
+  constexpr uint32_t start_sector() const { return start_sector_; }
+  constexpr size_t sector_size_bytes() const { return sector_size_; }
+  constexpr size_t sector_count() const { return flash_sector_count_; }
+  constexpr size_t alignment_bytes() const { return alignment_; }
+  constexpr size_t size_bytes() const {
     return sector_size_ * flash_sector_count_;
   }
   // Address of the start of flash (the address of sector 0)
-  constexpr uint32_t GetStartAddress() const { return start_address_; }
-  constexpr uint8_t GetErasedMemoryContent() const {
+  constexpr uint32_t start_address() const { return start_address_; }
+  constexpr std::byte erased_memory_content() const {
     return erased_memory_content_;
   }
 
@@ -99,14 +114,14 @@
   const uint32_t flash_sector_count_;
   const uint8_t alignment_;
   const uint32_t start_address_;
-  const uint32_t sector_start_;
-  const uint8_t erased_memory_content_;
+  const uint32_t start_sector_;
+  const std::byte erased_memory_content_;
 };
 
 class FlashPartition {
  public:
   // The flash address is in the range of: 0 to PartitionSize.
-  typedef uint32_t Address;
+  using Address = uint32_t;
 
   constexpr FlashPartition(
       FlashMemory* flash,
@@ -118,12 +133,17 @@
         sector_count_(sector_count),
         permission_(permission) {}
 
-  constexpr FlashPartition(FlashMemory* flash, PartitionTableEntry entry)
+#if 0
+  constexpr FlashPartition(
+      FlashMemory* flash,
+      uint32_t start_sector_index,
+      uint32_t end_sector_index,
+      PartitionPermission permission = PartitionPermission::kReadAndWrite)
       : flash_(*flash),
-        start_sector_index_(entry.partition_start_sector_index),
-        sector_count_(entry.partition_end_sector_index -
-                      entry.partition_start_sector_index + 1),
-        permission_(entry.partition_permission) {}
+        start_sector_index_(start_sector_index),
+        sector_count_(end_sector_index - start_sector_index + 1),
+        permission_(permission) {}
+#endif
 
   virtual ~FlashPartition() = default;
 
@@ -134,32 +154,17 @@
   //          INVALID_ARGUMENT, if address or sector count is invalid.
   //          PERMISSION_DENIED, if partition is read only.
   //          UNKNOWN, on HAL error
-  virtual Status Erase(Address address, uint32_t num_sectors) {
-    if (permission_ == PartitionPermission::kReadOnly) {
-      return Status::PERMISSION_DENIED;
-    }
-    if (Status status =
-            CheckBounds(address, num_sectors * GetSectorSizeBytes());
-        !status.ok()) {
-      return status;
-    }
-    return flash_.Erase(PartitionToFlashAddress(address), num_sectors);
-  }
+  virtual Status Erase(Address address, size_t num_sectors);
 
   // Reads bytes from flash into buffer. Blocking call.
   // Returns: OK, on success.
   //          TIMEOUT, on timeout.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  virtual Status Read(uint8_t* destination_ram_address,
-                      Address source_flash_address,
-                      uint32_t len) {
-    if (Status status = CheckBounds(source_flash_address, len); !status.ok()) {
-      return status;
-    }
-    return flash_.Read(destination_ram_address,
-                       PartitionToFlashAddress(source_flash_address),
-                       len);
+  virtual StatusWithSize Read(Address address, span<std::byte> output);
+
+  StatusWithSize Read(Address address, size_t length, void* output) {
+    return Read(address, span(static_cast<std::byte*>(output), length));
   }
 
   // Writes bytes to flash. Blocking call.
@@ -168,20 +173,10 @@
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          PERMISSION_DENIED, if partition is read only.
   //          UNKNOWN, on HAL error
-  virtual Status Write(Address destination_flash_address,
-                       const uint8_t* source_ram_address,
-                       uint32_t len) {
-    if (permission_ == PartitionPermission::kReadOnly) {
-      return Status::PERMISSION_DENIED;
-    }
-    if (Status status = CheckBounds(destination_flash_address, len);
-        !status.ok()) {
-      return status;
-    }
-    return flash_.Write(PartitionToFlashAddress(destination_flash_address),
-                        source_ram_address,
-                        len);
-  }
+  virtual StatusWithSize Write(Address address, span<const std::byte> data);
+
+  StatusWithSize Write(Address start_address,
+                       std::initializer_list<span<const std::byte>> data);
 
   // Check to see if chunk of flash memory is erased. Address and len need to
   // be aligned with FlashMemory.
@@ -189,87 +184,40 @@
   //          TIMEOUT, on timeout.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  virtual Status IsChunkErased(Address source_flash_address,
-                               uint32_t len,
-                               bool* is_erased) {
-    // Max alignment is artifical to keep the stack usage low for this
-    // function. Using 16 because it's the alignment of encrypted flash.
-    const uint8_t kMaxAlignment = 16;
-    // Relying on Read() to check address and len arguments.
-    if (!is_erased) {
-      return Status::INVALID_ARGUMENT;
-    }
-    uint8_t alignment = GetAlignmentBytes();
-    if (alignment > kMaxAlignment || kMaxAlignment % alignment ||
-        len % alignment) {
-      return Status::INVALID_ARGUMENT;
-    }
+  // TODO: StatusWithBool
+  virtual Status IsRegionErased(Address source_flash_address,
+                                size_t len,
+                                bool* is_erased);
 
-    uint8_t buffer[kMaxAlignment];
-    uint8_t erased_pattern_buffer[kMaxAlignment];
-    size_t offset = 0;
-    std::memset(erased_pattern_buffer,
-                flash_.GetErasedMemoryContent(),
-                sizeof(erased_pattern_buffer));
-    *is_erased = false;
-    while (len > 0) {
-      // Check earlier that len is aligned, no need to round up
-      uint16_t read_size = std::min(static_cast<uint32_t>(sizeof(buffer)), len);
-      if (Status status =
-              Read(buffer, source_flash_address + offset, read_size);
-          !status.ok()) {
-        return status;
-      }
-      if (std::memcmp(buffer, erased_pattern_buffer, read_size)) {
-        // Detected memory chunk is not entirely erased
-        return Status::OK;
-      }
-      offset += read_size;
-      len -= read_size;
-    }
-    *is_erased = true;
-    return Status::OK;
+  constexpr uint32_t sector_size_bytes() const {
+    return flash_.sector_size_bytes();
   }
 
-  constexpr uint32_t GetSectorSizeBytes() const {
-    return flash_.GetSectorSizeBytes();
+  // Overridden by base classes which store metadata at the start of a sector.
+  virtual uint32_t sector_available_size_bytes() const {
+    return sector_size_bytes();
   }
 
-  uint32_t GetSizeBytes() const {
-    return GetSectorCount() * GetSectorSizeBytes();
-  }
+  size_t size_bytes() const { return sector_count() * sector_size_bytes(); }
 
-  virtual uint8_t GetAlignmentBytes() const {
-    return flash_.GetAlignmentBytes();
-  }
+  virtual size_t alignment_bytes() const { return flash_.alignment_bytes(); }
 
-  virtual uint32_t GetSectorCount() const { return sector_count_; }
+  virtual size_t sector_count() const { return sector_count_; }
 
   // Convert a FlashMemory::Address to an MCU pointer, this can be used for
   // memory mapped reads. Return NULL if the memory is not memory mapped.
-  uint8_t* PartitionAddressToMcuAddress(Address address) const {
+  std::byte* PartitionAddressToMcuAddress(Address address) const {
     return flash_.FlashAddressToMcuAddress(PartitionToFlashAddress(address));
   }
 
   FlashMemory::Address PartitionToFlashAddress(Address address) const {
-    return flash_.GetStartAddress() +
-           (start_sector_index_ - flash_.GetStartSector()) *
-               GetSectorSizeBytes() +
+    return flash_.start_address() +
+           (start_sector_index_ - flash_.start_sector()) * sector_size_bytes() +
            address;
   }
 
  protected:
-  Status CheckBounds(Address address, size_t len) const {
-    if (address + len > GetSizeBytes()) {
-      PW_LOG_ERROR(
-          "Attempted out-of-bound flash memory access (address: %" PRIu32
-          " length: %zu)",
-          address,
-          len);
-      return Status::INVALID_ARGUMENT;
-    }
-    return Status::OK;
-  }
+  Status CheckBounds(Address address, size_t len) const;
 
  private:
   FlashMemory& flash_;
@@ -278,74 +226,4 @@
   const PartitionPermission permission_;
 };
 
-// FlashSubPartition defines a new partition which maps itself as a smaller
-// piece of another partition. This can used when a partition has special
-// behaviours (for example encrypted flash).
-// For example, this will be the first sector of test_partition:
-//    FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
-class FlashSubPartition : public FlashPartition {
- public:
-  constexpr FlashSubPartition(FlashPartition* parent_partition,
-                              uint32_t start_sector_index,
-                              uint32_t sector_count)
-      : FlashPartition(*parent_partition),
-        partition_(parent_partition),
-        start_sector_index_(start_sector_index),
-        sector_count_(sector_count) {}
-
-  Status Erase(Address address, uint32_t num_sectors) override {
-    if (Status status =
-            CheckBounds(address, num_sectors * GetSectorSizeBytes());
-        !status.ok()) {
-      return status;
-    }
-    return partition_->Erase(ParentAddress(address), num_sectors);
-  }
-
-  Status Read(uint8_t* destination_ram_address,
-              Address source_flash_address,
-              uint32_t len) override {
-    if (Status status = CheckBounds(source_flash_address, len); !status.ok()) {
-      return status;
-    }
-    return partition_->Read(
-        destination_ram_address, ParentAddress(source_flash_address), len);
-  }
-
-  Status Write(Address destination_flash_address,
-               const uint8_t* source_ram_address,
-               uint32_t len) override {
-    if (Status status = CheckBounds(destination_flash_address, len);
-        !status.ok()) {
-      return status;
-    }
-    return partition_->Write(
-        ParentAddress(destination_flash_address), source_ram_address, len);
-  }
-
-  Status IsChunkErased(Address source_flash_address,
-                       uint32_t len,
-                       bool* is_erased) override {
-    if (Status status = CheckBounds(source_flash_address, len); !status.ok()) {
-      return status;
-    }
-    return partition_->IsChunkErased(
-        ParentAddress(source_flash_address), len, is_erased);
-  }
-
-  uint8_t GetAlignmentBytes() const override {
-    return partition_->GetAlignmentBytes();
-  }
-
-  uint32_t GetSectorCount() const override { return sector_count_; }
-
- private:
-  Address ParentAddress(Address address) const {
-    return address + start_sector_index_ * partition_->GetSectorSizeBytes();
-  }
-  FlashPartition* partition_;
-  const uint32_t start_sector_index_;
-  const uint32_t sector_count_;
-};
-
 }  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/in_memory_fake_flash.h b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
index d2ea67c..901684e 100644
--- a/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
+++ b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
@@ -14,6 +14,7 @@
 #pragma once
 
 #include <array>
+#include <cstring>
 
 #include "pw_kvs/flash_memory.h"
 #include "pw_status/status.h"
@@ -38,17 +39,17 @@
   // Returns: OK, on success.
   //          INVALID_ARGUMENT, if address or sector count is invalid.
   //          UNKNOWN, on HAL error
-  Status Erase(Address addr, uint32_t num_sectors) override {
-    if (addr % GetSectorSizeBytes() != 0) {
+  Status Erase(Address addr, size_t num_sectors) override {
+    if (addr % sector_size_bytes() != 0) {
       return Status::INVALID_ARGUMENT;
     }
-    if (addr / GetSectorSizeBytes() + num_sectors > GetSectorCount()) {
+    if (addr / sector_size_bytes() + num_sectors > sector_count()) {
       return Status::UNKNOWN;
     }
-    if (addr % GetAlignmentBytes() != 0) {
+    if (addr % alignment_bytes() != 0) {
       return Status::INVALID_ARGUMENT;
     }
-    memset(&buffer_[addr], 0xFF, GetSectorSizeBytes() * num_sectors);
+    std::memset(&buffer_[addr], 0xFF, sector_size_bytes() * num_sectors);
     return Status::OK;
   }
 
@@ -56,13 +57,11 @@
   // Returns: OK, on success.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  Status Read(uint8_t* dest_ram_addr,
-              Address source_flash_addr,
-              uint32_t len) override {
-    if ((source_flash_addr + len) >= GetSectorCount() * GetSizeBytes()) {
+  StatusWithSize Read(Address address, span<std::byte> output) override {
+    if (address + output.size() >= sector_count() * size_bytes()) {
       return Status::INVALID_ARGUMENT;
     }
-    memcpy(dest_ram_addr, &buffer_[source_flash_addr], len);
+    std::memcpy(output.data(), &buffer_[address], output.size());
     return Status::OK;
   }
 
@@ -70,22 +69,20 @@
   // Returns: OK, on success.
   //          INVALID_ARGUMENT, if address or length is invalid.
   //          UNKNOWN, on HAL error
-  Status Write(Address dest_flash_addr,
-               const uint8_t* source_ram_addr,
-               uint32_t len) override {
-    if ((dest_flash_addr + len) >= GetSectorCount() * GetSizeBytes() ||
-        dest_flash_addr % GetAlignmentBytes() != 0 ||
-        len % GetAlignmentBytes() != 0) {
+  StatusWithSize Write(Address address, span<const std::byte> data) override {
+    if ((address + data.size()) >= sector_count() * size_bytes() ||
+        address % alignment_bytes() != 0 ||
+        data.size() % alignment_bytes() != 0) {
       return Status::INVALID_ARGUMENT;
     }
     // Check in erased state
-    for (unsigned i = 0; i < len; i++) {
-      if (buffer_[dest_flash_addr + i] != 0xFF) {
+    for (unsigned i = 0; i < data.size(); i++) {
+      if (buffer_[address + i] != 0xFF) {
         return Status::UNKNOWN;
       }
     }
-    memcpy(&buffer_[dest_flash_addr], source_ram_addr, len);
-    return Status::OK;
+    std::memcpy(&buffer_[address], data.data(), data.size());
+    return StatusWithSize(data.size());
   }
 
  private:
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 2faa512..115bea0 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -13,402 +13,301 @@
 // the License.
 #pragma once
 
+#include <array>
 #include <cstddef>
 #include <cstdint>
-#include <limits>
 #include <string_view>
-#include <type_traits>
 
+#include "pw_kvs/checksum.h"
 #include "pw_kvs/flash_memory.h"
 #include "pw_span/span.h"
 #include "pw_status/status.h"
 #include "pw_status/status_with_size.h"
 
 namespace pw::kvs {
-namespace cfg {
-
-// KVS requires a temporary buffer for some operations, this config allows
-// tuning the buffer size. This is a trade-off between a value which is large
-// and therefore requires more RAM, or having a value which is small which will
-// result in some operations taking longer, as the operations are broken into
-// smaller chunks.
-// NOTE: This value can not be smaller then the flash alignment, and it will
-//       round the size down to be a multiple of the flash alignment for all
-//       operations.
-inline constexpr size_t kKvsBufferSize = 64;
-
-// This represents the maximum amount of keys which can be in the KVS at any
-// given time.
-inline constexpr uint8_t kKvsMaxKeyCount = 50;
-
-// This is the maximum amount of sectors the KVS can operate on, an invalid
-// value will cause an error during enable.
-inline constexpr uint32_t kKvsMaxSectorCount = 20;
-
-}  // namespace cfg
-
 namespace internal {
 
+template <typename T, typename = decltype(span(std::declval<T>()))>
+constexpr bool ConvertsToSpan(int) {
+  return true;
+}
+
+// If the expression span(T) fails, then the type can't be converted to a span.
+template <typename T>
+constexpr bool ConvertsToSpan(...) {
+  return false;
+}
+
+}  // namespace internal
+
 // Traits class to detect if the type is a span. std::is_same is insufficient
 // because span is a class template. This is used to ensure that the correct
 // overload of the Put function is selected.
-template <typename>
-struct IsSpan : std::false_type {};
+template <typename T>
+using ConvertsToSpan =
+    std::bool_constant<internal::ConvertsToSpan<std::remove_reference_t<T>>(0)>;
 
-template <typename T, size_t kExtent>
-struct IsSpan<span<T, kExtent>> : std::true_type {};
+// Internal-only persistent storage header format.
+struct EntryHeader;
 
-}  // namespace internal
+struct EntryHeaderFormat {
+  uint32_t magic;  // unique identifier
+  ChecksumAlgorithm* checksum;
+};
 
-// This object is very large (can be over 1500 B, depending on configuration)
-// and should not typically be placed on the stack.
+// TODO: Select the appropriate defaults, add descriptions.
+struct Options {
+  bool partial_gc_on_write = true;
+  bool verify_on_read = true;
+  bool verify_on_write = true;
+};
+
 class KeyValueStore {
  public:
-  constexpr KeyValueStore(FlashPartition* partition) : partition_(*partition) {}
+  // TODO: Make these configurable
+  static constexpr size_t kMaxKeyLength = 64;
+  static constexpr size_t kMaxEntries = 64;
+  static constexpr size_t kUsableSectors = 64;
 
-  KeyValueStore(const KeyValueStore&) = delete;
-  KeyValueStore& operator=(const KeyValueStore&) = delete;
+  // In the future, will be able to provide additional EntryHeaderFormats for
+  // backwards compatibility.
+  constexpr KeyValueStore(FlashPartition* partition,
+                          const EntryHeaderFormat& format,
+                          const Options& options = {})
+      : partition_(*partition),
+        entry_header_format_(format),
+        options_(options),
+        key_map_{},
+        key_map_size_(0),
+        sector_map_{},
+        last_written_sector_(0) {}
 
-  // Enable the KVS, scans the sectors of the partition for any current KVS
-  // data. Erases and initializes any sectors which are not initialized.
-  // Checks the CRC of all data in the KVS; on failure the corrupted data is
-  // lost and Enable will return Status::DATA_LOSS, but the KVS will still load
-  // other data and will be enabled.
-  Status Enable();
+  Status Init();
+  bool initialized() const { return false; }  // TODO: Implement this
 
-  bool IsEnabled() const { return enabled_; }
+  StatusWithSize Get(std::string_view key, span<std::byte> value) const;
 
-  void Disable() {
-    if (enabled_ == false) {
-      return;
-    }
-    // TODO: LOCK MUTEX
-    enabled_ = false;
-  }
-
-  // Erase a key value element.
-  // key is a null terminated c string.
-  // Returns OK if erased
-  //         NOT_FOUND if key was not found.
-  Status Erase(const std::string_view& key);
-
-  // Copy the first size bytes of key's value into value buffer.
-  // key is a null terminated c string. Size is the amount of bytes to read,
-  // Optional offset argument supports reading size bytes starting at the
-  // specified offset.
-  // Returns OK if successful
-  //         NOT_FOUND if key was not found
-  //         DATA_LOSS if the value failed crc check
-  Status Get(const std::string_view& key,
-             const span<std::byte>& value,
-             uint16_t offset = 0);
-
-  // Interpret the key's value as the given type and return it.
-  // Returns OK if successful
-  //         NOT_FOUND if key was not found
-  //         DATA_LOSS if the value failed crc check
-  //         INVALID_ARGUMENT if size of value != sizeof(T)
   template <typename T>
   Status Get(const std::string_view& key, T* value) {
     static_assert(std::is_trivially_copyable<T>(), "KVS values must copyable");
     static_assert(!std::is_pointer<T>(), "KVS values cannot be pointers");
 
-    StatusWithSize result = GetValueSize(key);
+    StatusWithSize result = ValueSize(key);
     if (!result.ok()) {
       return result.status();
     }
     if (result.size() != sizeof(T)) {
       return Status::INVALID_ARGUMENT;
     }
-    return Get(key, as_writable_bytes(span(value, 1)));
+    return Get(key, as_writable_bytes(span(value, 1))).status();
   }
 
-  // Writes the key value store to the partition. If the key already exists it
-  // will be deleted before writing the new value.
-  //
-  // Returns OK if successful
-  //         RESOURCE_EXHAUSTED if there is not enough available space
-  Status Put(const std::string_view& key, const span<const std::byte>& value);
+  Status Put(std::string_view key, span<const std::byte> value);
 
-  // Alternate Put function that takes an object. The object must be trivially
-  // copyable and cannot be a pointer or span.
   template <typename T,
             typename = std::enable_if_t<std::is_trivially_copyable_v<T> &&
                                         !std::is_pointer_v<T> &&
-                                        !internal::IsSpan<T>()>>
+                                        !ConvertsToSpan<T>::value>>
   Status Put(const std::string_view& key, const T& value) {
     return Put(key, as_bytes(span(&value, 1)));
   }
 
-  // Gets the size of the value stored for provided key.
-  // Returns OK if successful
-  //         INVALID_ARGUMENT if args are invalid.
-  //         FAILED_PRECONDITION if KVS is not enabled.
-  //         NOT_FOUND if key was not found.
-  StatusWithSize GetValueSize(const std::string_view& key);
+  Status Delete(std::string_view key);
 
-  // Tests if the proposed key value entry can be stored in the KVS.
-  bool CanFitEntry(uint16_t key_len, uint16_t value_len) {
-    return kSectorInvalid != FindSpace(ChunkSize(key_len, value_len));
+  StatusWithSize ValueSize(std::string_view key) const {
+    (void)key;
+    return Status::UNIMPLEMENTED;
   }
 
-  // CleanAll cleans each sector which is currently marked for cleaning.
-  // Note: if any data is invalid/corrupt it could be lost.
-  Status CleanAll() {
-    // TODO: LOCK MUTEX
-    return CleanAllInternal();
-  }
-  size_t PendingCleanCount() {
-    // TODO: LOCK MUTEX
-    size_t ret = 0;
-    for (size_t i = 0; i < SectorCount(); i++) {
-      ret += sector_space_remaining_[i] == 0 ? 1 : 0;
+  // Classes and functions to support STL-style iteration.
+  class Iterator;
+
+  class Entry {
+   public:
+    // Guaranteed to be null-terminated
+    std::string_view key() const { return key_buffer_.data(); }
+
+    Status Get(span<std::byte> value_buffer) const {
+      return kvs_.Get(key(), value_buffer).status();
     }
-    return ret;
-  }
 
-  // Clean a single sector and return, if all sectors are clean it will set
-  // all_sectors_have_been_cleaned to true and return.
-  Status CleanOneSector(bool* all_sectors_have_been_cleaned);
+    template <typename T>
+    Status Get(T* value) const {
+      return kvs_.Get(key(), value);
+    }
 
-  // For debugging, logging, and testing. (Don't use in regular code)
-  // Note: a key_index is not valid after an element is erased or updated.
-  size_t KeyCount() const;
-  std::string_view GetKey(size_t idx) const;
-  size_t GetValueSize(size_t idx) const;
-  size_t GetMaxKeys() const { return kListCapacityMax; }
-  bool HasEmptySector() const { return HasEmptySectorImpl(kSectorInvalid); }
+    StatusWithSize ValueSize() const { return kvs_.ValueSize(key()); }
 
-  static constexpr size_t kHeaderSize = 8;  // Sector and KVS Header size
-  static constexpr uint16_t MaxValueLength() { return kChunkValueLengthMax; }
+   private:
+    friend class Iterator;
+
+    constexpr Entry(const KeyValueStore& kvs) : kvs_(kvs), key_buffer_{} {}
+
+    const KeyValueStore& kvs_;
+    std::array<char, kMaxKeyLength + 1> key_buffer_;  // +1 for null-terminator
+  };
+
+  class Iterator {
+   public:
+    Iterator& operator++() {
+      index_ += 1;
+      return *this;
+    }
+
+    Iterator& operator++(int) { return operator++(); }
+
+    // Reads the entry's key from flash.
+    const Entry& operator*();
+
+    const Entry* operator->() {
+      operator*();  // Read the key into the Entry object.
+      return &entry_;
+    }
+
+    constexpr bool operator==(const Iterator& rhs) const {
+      return index_ == rhs.index_;
+    }
+
+    constexpr bool operator!=(const Iterator& rhs) const {
+      return index_ != rhs.index_;
+    }
+
+   private:
+    friend class KeyValueStore;
+
+    constexpr Iterator(const KeyValueStore& kvs, size_t index)
+        : entry_(kvs), index_(index) {}
+
+    Entry entry_;
+    size_t index_;
+  };
+
+  // Standard aliases for iterator types.
+  using iterator = Iterator;
+  using const_iterator = Iterator;
+
+  Iterator begin() const { return Iterator(*this, 0); }
+  Iterator end() const { return Iterator(*this, empty() ? 0 : size() - 1); }
+
+  // Returns the number of valid entries in the KeyValueStore.
+  size_t size() const { return key_map_size_; }
+
+  static constexpr size_t max_size() { return kMaxKeyLength; }
+
+  size_t empty() const { return size() == 0u; }
 
  private:
-  using KeyIndex = uint8_t;
-  using SectorIndex = uint32_t;
+  using Address = FlashPartition::Address;
 
-  static constexpr uint16_t kVersion = 1;
-  static constexpr KeyIndex kListCapacityMax = cfg::kKvsMaxKeyCount;
-  static constexpr SectorIndex kSectorCountMax = cfg::kKvsMaxSectorCount;
-
-  // Number of bits for fields in KVSHeader:
-  static constexpr int kChunkHeaderKeyFieldNumBits = 4;
-  static constexpr int kChunkHeaderChunkFieldNumBits = 12;
-
-  static constexpr uint16_t kSectorReadyValue = 0xABCD;
-  static constexpr uint16_t kChunkSyncValue = 0x55AA;
-
-  static constexpr uint16_t kChunkLengthMax =
-      ((1 << kChunkHeaderChunkFieldNumBits) - 1);
-  static constexpr uint16_t kChunkKeyLengthMax =
-      ((1 << kChunkHeaderKeyFieldNumBits) - 1);
-  static constexpr uint16_t kChunkValueLengthMax =
-      (kChunkLengthMax - kChunkKeyLengthMax);
-
-  static constexpr SectorIndex kSectorInvalid = 0xFFFFFFFFul;
-  static constexpr FlashPartition::Address kAddressInvalid = 0xFFFFFFFFul;
-  static constexpr uint64_t kSectorCleanNotPending = 0xFFFFFFFFFFFFFFFFull;
-
-  static constexpr uint16_t kFlagsIsErasedMask = 0x0001;
-  static constexpr uint16_t kMaxAlignmentBytes = 128;
-
-  // This packs into 16 bytes.
-  struct KvsSectorHeaderMeta {
-    uint16_t synchronize_token;
-    uint16_t version;
-    uint16_t alignment_bytes;  // alignment used for each chunk in this sector.
-    uint16_t padding;          // padding to support uint64_t alignment.
-  };
-  static_assert(sizeof(KvsSectorHeaderMeta) == kHeaderSize,
-                "Invalid KvsSectorHeaderMeta size");
-
-  // sector_clean_pending is broken off from KvsSectorHeaderMeta to support
-  // larger than sizeof(KvsSectorHeaderMeta) flash write alignments.
-  struct KvsSectorHeaderCleaning {
-    // When this sector is not marked for cleaning this will be in the erased
-    // state. When marked for clean this value indicates the order the sectors
-    // were marked for cleaning, and therfore which data is the newest.
-    // To remain backwards compatible with v2 and v3 KVS this is 8 bytes, if the
-    // alignment is greater than 8 we will check the entire alignment is in the
-    // default erased state.
-    uint64_t sector_clean_order;
-  };
-  static_assert(sizeof(KvsSectorHeaderCleaning) == kHeaderSize,
-                "Invalid KvsSectorHeaderCleaning size");
-
-  // This packs into 8 bytes, to support uint64_t alignment.
-  struct KvsHeader {
-    uint16_t synchronize_token;
-    uint16_t crc;  // Crc of the key + data (Ignoring any padding bytes)
-    // flags is a Bitmask: bits 15-1 reserved = 0,
-    // bit 0: is_erased [0 when not erased, 1 when erased]
-    uint16_t flags;
-    // On little endian the length fields map to memory as follows:
-    // byte array: [ 0x(c0to3 k0to3) 0x(c8to11 c4to7) ]
-    // Key length does not include trailing zero. That is not stored.
-    uint16_t key_len : kChunkHeaderKeyFieldNumBits;
-    // Chunk length is the total length of the chunk before alignment.
-    // That way we can work out the length of the value as:
-    // (chunk length - key length - size of chunk header).
-    uint16_t chunk_len : kChunkHeaderChunkFieldNumBits;
-  };
-  static_assert(sizeof(KvsHeader) == kHeaderSize, "Invalid KvsHeader size");
-
-  struct KeyMap {
-    std::string_view key() const { return {key_buffer, key_length}; }
-
-    FlashPartition::Address address;
-    char key_buffer[kChunkKeyLengthMax + 1];  // +1 for null terminator
-    uint8_t key_length;
-    bool is_erased;
-    uint16_t chunk_len;
-
-    static_assert(kChunkKeyLengthMax <=
-                  std::numeric_limits<decltype(key_length)>::max());
+  struct KeyMapEntry {
+    uint32_t key_hash;
+    uint32_t key_version;
+    Address address;  // In partition address.
   };
 
-  static constexpr bool InvalidKey(const std::string_view& key) {
-    return key.empty() || key.size() > kChunkKeyLengthMax;
-  }
+  struct SectorMapEntry {
+    uint16_t tail_free_bytes;
+    uint16_t valid_bytes;  // sum of sizes of valid entries
 
-  // NOTE: All public APIs handle the locking, the internal methods assume the
-  // lock has already been acquired.
-
-  SectorIndex AddressToSectorIndex(FlashPartition::Address address) const {
-    return address / partition_.GetSectorSizeBytes();
-  }
-
-  FlashPartition::Address SectorIndexToAddress(SectorIndex index) const {
-    return index * partition_.GetSectorSizeBytes();
-  }
-
-  // Returns kAddressInvalid if no space is found, otherwise the address.
-  FlashPartition::Address FindSpace(size_t requested_size) const;
-
-  // Attempts to rewrite a key's value by appending the new value to the same
-  // sector. If the sector is full the value is written to another sector, and
-  // the sector is marked for cleaning.
-  // Returns RESOURCE_EXHAUSTED if no space is available, OK otherwise.
-  Status RewriteValue(KeyIndex key_index,
-                      const span<const std::byte>& value,
-                      bool is_erased = false);
-
-  bool ValueMatches(KeyIndex key_index,
-                    const span<const std::byte>& value,
-                    bool is_erased);
-
-  // ResetSector erases the sector and writes the sector header.
-  Status ResetSector(SectorIndex sector_index);
-  Status WriteKeyValue(FlashPartition::Address address,
-                       const std::string_view& key,
-                       const span<const std::byte>& value,
-                       bool is_erased = false);
-  uint32_t SectorSpaceRemaining(SectorIndex sector_index) const;
-
-  // Returns idx if key is found, otherwise kListCapacityMax.
-  KeyIndex FindKeyInMap(const std::string_view& key) const;
-  bool IsKeyInMap(const std::string_view& key) const {
-    return FindKeyInMap(key) != kListCapacityMax;
-  }
-
-  void RemoveFromMap(KeyIndex key_index);
-  Status AppendToMap(const std::string_view& key,
-                     FlashPartition::Address address,
-                     size_t chunk_len,
-                     bool is_erased = false);
-  void UpdateMap(KeyIndex key_index,
-                 FlashPartition::Address address,
-                 uint16_t chunk_len,
-                 bool is_erased = false);
-  uint16_t CalculateCrc(const std::string_view& key,
-                        const span<const std::byte>& value) const;
-
-  // Calculates the CRC by reading the value from flash in chunks.
-  Status CalculateCrcFromValueAddress(const std::string_view& key,
-                                      FlashPartition::Address value_address,
-                                      uint16_t value_size,
-                                      uint16_t* crc_ret);
-
-  uint16_t RoundUpForAlignment(uint16_t size) const {
-    if (size % alignment_bytes_ != 0) {
-      return size + alignment_bytes_ - size % alignment_bytes_;
+    bool HasSpace(size_t required_space) const {
+      return (tail_free_bytes >= required_space);
     }
-    return size;
+  };
+
+  Status InvalidOperation(std::string_view key) const;
+
+  static constexpr bool InvalidKey(std::string_view key) {
+    return key.empty() || (key.size() > kMaxKeyLength);
   }
 
-  // The buffer is chosen to be no larger then the config value, and
-  // be a multiple of the flash alignment.
-  size_t TempBufferAlignedSize() const {
-    CHECK_GE(sizeof(temp_buffer_), partition_.GetAlignmentBytes());
-    return sizeof(temp_buffer_) -
-           (sizeof(temp_buffer_) % partition_.GetAlignmentBytes());
+  Status FindKeyMapEntry(std::string_view key,
+                         const KeyMapEntry** result) const;
+
+  // Non-const version of FindKeyMapEntry.
+  Status FindKeyMapEntry(std::string_view key, KeyMapEntry** result) {
+    return static_cast<const KeyValueStore&>(*this).FindKeyMapEntry(
+        key, const_cast<const KeyMapEntry**>(result));
   }
 
-  // Moves a key/value chunk from one address to another, all fields expected to
-  // be aligned.
-  Status MoveChunk(FlashPartition::Address dest_address,
-                   FlashPartition::Address src_address,
-                   uint16_t size);
+  Status ReadEntryHeader(const KeyMapEntry& entry, EntryHeader* header) const;
+  Status ReadEntryKey(const KeyMapEntry& entry,
+                      size_t key_length,
+                      char* key) const;
 
-  // Size of a chunk including header, key, value, and alignment padding.
-  size_t ChunkSize(size_t key_length, size_t value_length) const {
-    return RoundUpForAlignment(sizeof(KvsHeader)) +
-           RoundUpForAlignment(key_length) + RoundUpForAlignment(value_length);
+  StatusWithSize ReadEntryValue(const KeyMapEntry& entry,
+                                const EntryHeader& header,
+                                span<std::byte> value) const;
+
+  Status ValidateEntryChecksum(const EntryHeader& header,
+                               std::string_view key,
+                               span<const std::byte> value) const;
+
+  Status WriteEntryForExistingKey(KeyMapEntry* key_map_entry,
+                                  std::string_view key,
+                                  span<const std::byte> value);
+
+  Status WriteEntryForNewKey(std::string_view key, span<const std::byte> value);
+
+  SectorMapEntry* FindSectorWithSpace(size_t size);
+
+  Status FindOrRecoverSectorWithSpace(SectorMapEntry** sector, size_t size);
+
+  Status GarbageCollectOneSector(SectorMapEntry** sector);
+
+  SectorMapEntry* FindSectorToGarbageCollect();
+
+  Status AppendEntry(SectorMapEntry* sector,
+                     KeyMapEntry* entry,
+                     std::string_view key,
+                     span<const std::byte> value);
+
+  Status VerifyEntry(SectorMapEntry* sector, KeyMapEntry* entry);
+
+  span<const std::byte> CalculateEntryChecksum(
+      const EntryHeader& header,
+      std::string_view key,
+      span<const std::byte> value) const;
+
+  Status RelocateEntry(KeyMapEntry* entry);
+
+  bool SectorEmpty(const SectorMapEntry& sector) const {
+    return (sector.tail_free_bytes == partition_.sector_available_size_bytes());
   }
 
-  // Sectors should be cleaned when full, every valid (Most recent, not erased)
-  // chunk of data is moved to another sector and the sector is erased.
-  // TODO: Clean sectors with lots of invalid data, without a rewrite
-  // or erase triggering it.
-  Status MarkSectorForClean(SectorIndex sector);
-  Status CleanSector(SectorIndex sector);
-  Status CleanAllInternal();
-  Status GarbageCollectImpl(bool clean_pending_sectors,
-                            bool exit_when_have_free_sector);
-  Status FullGarbageCollect();
-  Status EnforceFreeSector();
-
-  SectorIndex SectorCount() const {
-    return std::min(partition_.GetSectorCount(), kSectorCountMax);
+  size_t RecoverableBytes(const SectorMapEntry& sector) {
+    return partition_.sector_size_bytes() - sector.valid_bytes -
+           sector.tail_free_bytes;
   }
 
-  size_t SectorSpaceAvailableWhenEmpty() const {
-    return partition_.GetSectorSizeBytes() -
-           RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)) -
-           RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning));
+  Address SectorBaseAddress(SectorMapEntry* sector) const {
+    return (sector - sector_map_.data()) * partition_.sector_size_bytes();
   }
 
-  bool HasEmptySectorImpl(SectorIndex skip_sector) const {
-    for (SectorIndex i = 0; i < SectorCount(); i++) {
-      if (i != skip_sector &&
-          sector_space_remaining_[i] == SectorSpaceAvailableWhenEmpty()) {
-        return true;
-      }
-    }
-    return false;
+  Address NextWritableAddress(SectorMapEntry* sector) const {
+    return SectorBaseAddress(sector) + partition_.sector_size_bytes() -
+           sector->tail_free_bytes;
   }
 
-  bool IsInLastFreeSector(FlashPartition::Address address) {
-    return sector_space_remaining_[AddressToSectorIndex(address)] ==
-               SectorSpaceAvailableWhenEmpty() &&
-           !HasEmptySectorImpl(AddressToSectorIndex(address));
+  bool EntryMapFull() const { return key_map_size_ == kMaxEntries; }
+
+  span<KeyMapEntry> entries() { return span(key_map_.data(), key_map_size_); }
+
+  span<const KeyMapEntry> entries() const {
+    return span(key_map_.data(), key_map_size_);
   }
 
   FlashPartition& partition_;
-  // TODO: MUTEX
-  bool enabled_ = false;
-  uint8_t alignment_bytes_ = 0;
-  uint64_t next_sector_clean_order_ = 0;
+  EntryHeaderFormat entry_header_format_;
+  Options options_;
 
-  // Free space available in each sector, set to 0 when clean is pending/active
-  uint32_t sector_space_remaining_[kSectorCountMax] = {0};
-  uint64_t sector_clean_order_[kSectorCountMax] = {kSectorCleanNotPending};
-  KeyMap key_map_[kListCapacityMax] = {};
-  KeyIndex map_size_ = 0;
+  // Map is unordered; finding a key requires scanning and
+  // verifying a match by reading the actual entry.
+  std::array<KeyMapEntry, kMaxEntries> key_map_;
+  size_t key_map_size_;  // Number of valid entries in entry_map
 
-  // Add +1 for a null terminator. The keys are used as string_views, but the
-  // null-terminator provides additional safetly.
-  char temp_key_buffer_[kChunkKeyLengthMax + 1u] = {0};
-  uint8_t temp_buffer_[cfg::kKvsBufferSize] = {0};
+  // This is dense, so sector_id == indexof(SectorMapEntry) in sector_map
+  std::array<SectorMapEntry, kUsableSectors> sector_map_;
+  size_t last_written_sector_;  // TODO: this variable is not used!
 };
 
 }  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/partition_table_entry.h b/pw_kvs/public/pw_kvs/partition_table_entry.h
deleted file mode 100644
index 9aa111d..0000000
--- a/pw_kvs/public/pw_kvs/partition_table_entry.h
+++ /dev/null
@@ -1,51 +0,0 @@
-// 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 <cstdint>
-
-namespace pw {
-
-namespace partition_table {
-
-enum DataType { kRawData, kKvs };
-
-}  // namespace partition_table
-
-enum class PartitionPermission : bool {
-  kReadOnly = true,
-  kReadAndWrite = false,
-};
-
-struct PartitionTableEntry {
-  constexpr PartitionTableEntry(
-      const uint32_t start_sector_index,
-      const uint32_t end_sector_index,
-      const uint8_t partition_identifier,
-      partition_table::DataType datatype,
-      PartitionPermission permission = PartitionPermission::kReadAndWrite)
-      : partition_start_sector_index(start_sector_index),
-        partition_end_sector_index(end_sector_index),
-        partition_id(partition_identifier),
-        data_type(datatype),
-        partition_permission(permission) {}
-
-  const uint32_t partition_start_sector_index;
-  const uint32_t partition_end_sector_index;
-  const uint8_t partition_id;
-  const partition_table::DataType data_type;
-  const PartitionPermission partition_permission;
-};
-
-}  // namespace pw