pw_kvs#
Lightweight, persistent key-value store
Stable C++17 Code Size Impact: ~12 kB
#include <cstddef>
#include "pw_kvs/flash_test_partition.h"
#include "pw_kvs/key_value_store.h"
// Not a required dep; just here for demo comms
#include "pw_sys_io/sys_io.h"
// Create our key-value store (KVS). Sector and entry vals for this
// demo are based on @pigweed//pw_kvs:fake_flash_64_aligned_partition
constexpr size_t kMaxSectors = 6;
constexpr size_t kMaxEntries = 64;
static constexpr pw::kvs::EntryFormat kvs_format = {
.magic = 0xd253a8a9, // Prod apps should use a random number here
.checksum = nullptr
};
pw::kvs::KeyValueStoreBuffer<kMaxEntries, kMaxSectors> kvs(
&pw::kvs::FlashTestPartition(),
kvs_format
);
kvs.Init(); // Initialize our KVS
std::byte in;
pw::sys_io::ReadByte(&in).IgnoreError(); // Get a char from the user
kvs.Put("in", in); // Save the char to our key-value store (KVS)
std::byte out;
kvs.Get("in", &out); // Test that the KVS stored the data correctly
pw::sys_io::WriteByte(out).IgnoreError(); // Echo the char back out
cc_binary(
name = "app",
srcs = ["app.cc"],
# ...
deps = [
# ...
"@pigweed//pw_kvs",
"@pigweed//pw_kvs:fake_flash_64_aligned_partition",
# ...
]
# ...
)
pw_kvs is a flash-backed, persistent key-value storage (KVS) system with
integrated wear leveling. It’s a relatively
lightweight alternative to a file system.
Get started#
Add @pigweed//pw_kvs to your target’s deps:
cc_binary(
# ...
deps = [
# ...
"@pigweed//pw_kvs",
# ...
]
)
This assumes that your Bazel WORKSPACE has a repository named @pigweed
that points to the upstream Pigweed repository.
Add $dir_pw_kvs to the deps list in your pw_executable()
build target:
pw_executable("...") {
# ...
deps = [
# ...
"$dir_pw_kvs",
# ...
]
}
Link your library to pw_kvs:
add_library(my_lib ...)
target_link_libraries(my_lib PUBLIC pw_kvs)
Use pw_kvs in your C++ code:
#include "pw_kvs/key_value_store.h"
// ...
Implement the flash memory and flash partition interfaces for your hardware. See pw_kvs/flash_memory.h.
Reference#
pw::kvs::KeyValueStore#
See Design for architectural details.
-
class KeyValueStore#
Flash-backed persistent key-value store (KVS) with integrated wear-leveling.
Instances are declared as instances of
pw::kvs::KeyValueStoreBuffer<MAX_ENTRIES, MAX_SECTORS>, which allocates buffers for tracking entries and flash sectors.#include "pw_kvs/key_value_store.h" #include "pw_kvs/flash_test_partition.h" constexpr size_t kMaxSectors = 6; constexpr size_t kMaxEntries = 64; static constexpr pw::kvs::EntryFormat kvs_format = { .magic = 0xd253a8a9, // Prod apps should use a random number here .checksum = nullptr }; pw::kvs::KeyValueStoreBuffer<kMaxEntries, kMaxSectors> kvs( &pw::kvs::FlashTestPartition(), kvs_format ); kvs.Init();
Subclassed by pw::kvs::KeyValueStoreBuffer< kMaxEntries, kMaxUsableSectors, kRedundancy, kEntryFormats >
Public Functions
-
StatusWithSize Get(std::string_view key, span<std::byte> value, size_t offset_bytes = 0) const#
Reads the value of an entry in the KVS. The value is read into the provided buffer and the number of bytes read is returned. Reads can be started at an offset.
- Parameters:
key – [in] The name of the key.
value – [out] The buffer to read the key’s value into.
offset_bytes – [in] The byte offset to start the read at. Optional.
- Returns:
Code
Description
The entry was successfully read.
The key is not present in the KVS.
Found the entry, but the data was corrupted.
The buffer could not fit the entire value, but as many bytes as possible were written to it. The number of of bytes read is returned. The remainder of the value can be read by calling
Get()again with an offset.The KVS is not initialized. Call
Init()before calling this method.keyis empty or too long, orvalueis too large.
-
template<typename Pointer, typename = std::enable_if_t<std::is_pointer<Pointer>::value>>
inline Status Get( - const std::string_view &key,
- const Pointer &pointer,
Overload of
Get()that accepts a pointer to a trivially copyable object.If
valueis an array, callGet()withas_writable_bytes(span(array)), or pass a pointer to the array instead of the array itself.
-
template<typename T, typename std::enable_if_t<ConvertsToSpan<T>::value>* = nullptr>
inline Status Put( - const std::string_view &key,
- const T &value,
Adds a key-value entry to the KVS. If the key was already present, its value is overwritten.
- Parameters:
key – [in] The name of the key. All keys in the KVS must have a unique hash. If the hash of your key matches an existing key, nothing is added and
ALREADY_EXISTSis returned.value – [in] The value for the key. This can be a span of bytes or a trivially copyable object.
- Returns:
Code
Description
The entry was successfully added or updated.
Checksum validation failed after writing data.
Not enough space to add the entry.
The entry could not be added because a different key with the same hash is already in the KVS.
The KVS is not initialized. Call
Init()before calling this method.keyis empty or too long, orvalueis too large.
-
Status Delete(std::string_view key)#
Removes a key-value entry from the KVS.
- Parameters:
key – [in] - The name of the key-value entry to delete.
- Returns:
Code
Description
The entry was successfully deleted.
keyis not present in the KVS.Checksum validation failed after recording the erase.
Insufficient space to mark the entry as deleted.
The KVS is not initialized. Call
Init()before calling this method.keyis empty or too long.
-
StatusWithSize ValueSize(std::string_view key) const#
Returns the size of the value corresponding to the key.
- Parameters:
key – [in] - The name of the key.
- Returns:
Code
Description
The size was returned successfully.
keyis not present in the KVS.Checksum validation failed after reading the entry.
The KVS is not initialized. Call
Init()before calling this method.keyis empty or too long.
-
inline Status HeavyMaintenance()#
Performs all maintenance possible, including all needed repairing of corruption and garbage collection of reclaimable space in the KVS. When configured for manual recovery, this (along with
FullMaintenance()) is the only way KVS repair is triggered.Warning
Performs heavy garbage collection of all reclaimable space, regardless of whether there’s other valid data in the sector. This method may cause a significant amount of moving of valid entries.
-
inline Status FullMaintenance()#
Perform all maintenance possible, including all needed repairing of corruption and garbage collection of reclaimable space in the KVS. When configured for manual recovery, this (along with
HeavyMaintenance()) is the only way KVS repair is triggered.Does not garbage collect sectors with valid data unless the KVS is mostly full.
-
Status PartialMaintenance()#
Performs a portion of KVS maintenance. If configured for at least lazy recovery, will do any needed repairing of corruption. Does garbage collection of part of the KVS, typically a single sector or similar unit that makes sense for the KVS implementation.
-
inline iterator end() const#
- Returns:
The last key-value entry in the container. Used for iteration.
-
inline size_t size() const#
- Returns:
The number of valid entries in the KVS.
-
inline size_t total_entries_with_deleted() const#
- Returns:
The number of valid entries and deleted entries yet to be collected.
-
inline size_t max_size() const#
- Returns:
The maximum number of KV entries that’s possible in the KVS.
-
inline size_t empty() const#
- Returns:
trueif the KVS is empty.
-
inline uint32_t transaction_count() const#
- Returns:
The number of transactions that have occurred since the KVS was first used. This value is retained across initializations, but is reset if the underlying flash is erased.
-
StorageStats GetStorageStats() const#
- Returns:
A
StorageStatsstruct with details about the current and past state of the KVS.
-
inline size_t redundancy() const#
- Returns:
The number of identical copies written for each entry. A redundancy of 1 means that only a single copy is written for each entry.
-
inline bool error_detected() const#
- Returns:
trueif the KVS has any unrepaired errors.
-
inline size_t max_key_value_size_bytes() const#
- Returns:
The maximum number of bytes allowed for a key-value combination.
-
bool CheckForErrors()#
Checks the KVS for any error conditions and returns
trueif any errors are present. Primarily intended for test and internal use.
Public Static Functions
-
static inline constexpr size_t max_key_value_size_bytes(size_t partition_sector_size_bytes)#
- Returns:
The maximum number of bytes allowed for a given sector size for a key-value combination.
-
class Item#
Representation of a key-value entry during iteration.
Public Functions
-
inline const char *key() const#
- Returns:
The key as a null-terminated string.
-
inline StatusWithSize Get(span<std::byte> value_buffer, size_t offset_bytes = 0) const#
- Returns:
The value referred to by this iterator. Equivalent to
pw::kvs::KeyValueStore::Get().
-
inline const char *key() const#
-
class iterator#
Supported iteration methods.
Public Functions
-
struct StorageStats#
Statistics about the KVS.
Statistics are since the KVS init. They’re not retained across reboots.
Public Members
-
size_t writable_bytes#
The number of writeable bytes remaining in the KVS. This number doesn’t include the one empty sector required for KVS garbage collection.
-
size_t in_use_bytes#
The number of bytes in the KVS that are already in use.
-
size_t reclaimable_bytes#
The maximum number of bytes possible to reclaim by garbage collection. The number of bytes actually reclaimed by maintenance depends on the type of maintenance that’s performed.
-
size_t sector_erase_count#
The total count of individual sector erases that have been performed.
-
size_t corrupt_sectors_recovered#
The number of corrupt sectors that have been recovered.
-
size_t missing_redundant_entries_recovered#
The number of missing redundant copies of entries that have been recovered.
-
size_t writable_bytes#
-
StatusWithSize Get(std::string_view key, span<std::byte> value, size_t offset_bytes = 0) const#
Configuration#
-
PW_KVS_LOG_LEVEL#
Which log level to use for
pw_kvslogs.
-
PW_KVS_MAX_FLASH_ALIGNMENT#
The maximum flash alignment supported.
-
PW_KVS_REMOVE_DELETED_KEYS_IN_HEAVY_MAINTENANCE#
Whether to remove deleted keys in heavy maintanence. This feature costs some code size (>1KB) and is only necessary if arbitrary key names are used. Without this feature, deleted key entries can fill the KVS, making it impossible to add more keys, even though most keys are deleted.
Design#
pw::kvs::KeyValueStore (“the KVS”) stores key and value data
pairs. The key-value pairs are stored in flash partition as a key-value entry (KV entry) that consists of a header/metadata,
the key data, and value data. KV entries are accessed through Put(),
Get(), and Delete() operations.
Key-value entries#
Each key-value (KV) entry consists of a header/metadata, the key data, and value data. Individual KV entries are contained within a single flash sector; they do not cross sector boundaries. Because of this the maximum KV entry size is the partition sector size.
KV entries are appended as needed to sectors, with append operations spread over time. Each individual KV entry is written completely as a single high-level operation. KV entries are appended to a sector as long as space is available for a given KV entry. Multiple sectors can be active for writing at any time.
When an entry is updated, an entirely new entry is written to a new location that may or may not be located in the same sectore as the old entry. The new entry uses a transaction ID greater than the old entry. The old entry remains unaltered “on-disk” but is considered “stale”. It is garbage collected at some future time.
State#
The KVS does not store any data/metadata/state in flash beyond the KV entries. All KVS state can be derived from the stored KV entries. Current state is determined at boot from flash-stored KV entries and then maintained in RAM by the KVS. At all times the KVS is in a valid state on-flash; there are no windows of vulnerability to unexpected power loss or crash. The old entry for a key is maintained until the new entry for that key is written and verified.
Each KV entry has a unique transaction ID that is incremented for each KVS update transaction. When determining system state from flash-stored KV entries, the valid entry with the highest transaction ID is considered to be the “current” entry of the key. All stored entries of the same key with lower transaction IDs are considered old or “stale”.
Updates/rewrites of a key that has been previously stored is done as a new KV entry with an updated transaction ID and the new value for the key. The internal state of the KVS is updated to reflect the new entry. The previously stored KV entries for that key are not modified or removed from flash storage, until garbage collection reclaims the “stale” entries.
Garbage collection is done by copying any currently valid KV entries in the sector to be garbage collected to a different sector and then erasing the sector.
Flash sectors#
Each flash sector is written sequentially in an append-only manner, with each following entry write being at a higher address than all of the previous entry writes to that sector since erase. Once information (header, metadata, data, etc.) is written to flash, that information is not modified or cleared until a full sector erase occurs as part of garbage collection.
Individual KV entries are contained within a single flash sector; they do not cross sector boundaries. Flash sectors can contain as many KV entries as fit in the sector.
Sectors are the minimum erase size for both Flash memory and Flash partitions. Partitions may have a different logical sector size than the memory they are part of. Partition logical sectors may be smaller due to partition overhead (encryption, wear tracking, etc) or larger due to combining raw sectors into larger logical sectors.
Storage layers#
The flash storage used by the KVS is comprised of two layers, flash memory and flash partitions.
Flash memory#
pw::kvs::FlashMemory is the lower storage layer that manages the raw
read/write/erase of the flash memory device. It is an abstract base class that
needs a concrete implementation before it can be used.
pw::kvs::FakeFlashMemory is a variant that uses RAM rather than flash as
the storage media. This is helpful for reducing physical flash wear during unit
tests and development.
Flash partitions#
pw::kvs::FlashPartition is a subset of a pw::kvs::FlashMemory. Flash
memory may have one or multiple partition instances that represent different
parts of the memory, such as partitions for KVS, OTA, snapshots/crashlogs, etc.
Each partition has its own separate logical address space starting from zero to
size bytes of the partition. Partition logical addresses do not always map
directly to memory addresses due to partition encryption, sector headers, etc.
Partitions support access via pw::kvs::NonSeekableWriter and
pw::kvs::SeekableReader. The reader defaults to the full size of the
partition but can optionally be limited to a smaller range.
pw::kvs::FlashPartition is a concrete class that can be used directly. It
has several derived variants available, such as
pw::kvs::FlashPartitionWithStats and
pw::kvs::FlashPartitionWithLogicalSectors.
Alignment#
Writes to flash must have a start address that is a multiple of the flash write alignment. Write size must also be a multiple of flash write alignment. Write alignment varies by flash device and partition type. Reads from flash do not have any address or size alignment requirement; reads always have a minimum alignment of 1.
Flash partitions may have a different alignment than the Flash memory they are part of, so long as the partition’s alignment is a multiple of the alignment for the memory.
Allocation#
The KVS requires more storage space than the size of the key-value data stored. This is due to the always-free sector required for garbage collection and the “write and garbage collect later” approach it uses.
The KVS works poorly when stored data takes up more than 75% of the available storage. It works best when stored data is less than 50%. Applications that need to do garbage collection at scheduled times or that write very heavily can benefit from additional flash store space.
The flash storage used by the KVS is multiplied by the amount of Redundancy used. A redundancy of 2 will use twice the storage, for example.
Redundancy#
The KVS supports storing redundant copies of KV entries. For a given redundancy level (N), N total copies of each KV entry are stored. Redundant copies are always stored in different sectors. This protects against corruption or even full sector loss in N-1 sectors without data loss.
Redundancy increases flash usage proportional to the redundancy level. The RAM usage for KVS internal state has a small increase with redundancy.
Garbage collection#
Storage space occupied by stale Key-value entries is reclaimed and made available for reuse through a garbage collection process. The base garbage collection operation is done to reclaim one sector at a time.
The KVS always keeps at least one sector free at all times to ensure the ability to garbage collect. This free sector is used to copy valid entries from the sector to be garbage collected before erasing the sector to be garbage collected. The always-free sector is rotated as part of the KVS wear leveling.
Garbage collection can be performed manually, by invoking the methods below, or it can be configured to happen automatically.
Wear leveling (flash wear management)#
Wear leveling is accomplished by cycling selection of the next sector to write to. This cycling spreads flash wear across all free sectors so that no one sector is prematurely worn out.
The wear leveling decision-making process follows these guidelines:
Location of new writes/rewrites of KV entries will prefer sectors already in-use (partially filled), with new (blank) sectors used when no in-use sectors have large enough available space for the new write.
New (blank) sectors selected cycle sequentially between available free sectors.
The wear leveling system searches for the first available sector, starting from the current write sector + 1 and wraps around to start at the end of a partition. This spreads the erase/write cycles for heavily written/rewritten KV entries across all free sectors, reducing wear on any single sector.
Erase count is not considered in the wear leveling decision-making process.
Sectors with already written KV entries that are not modified will remain in the original sector and not participate in wear-leveling, so long as the KV entries in the sector remain unchanged.
Code size analysis#
The following size report details the memory usage of KeyValueStore and
FlashPartition.
Label |
Segment |
Delta |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
KeyValueStore |
FLASH
|
+10,152 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
FlashPartition |
FLASH
|
+1,832 |