1.. _module-pw_kvs: 2 3====== 4pw_kvs 5====== 6.. pigweed-module:: 7 :name: pw_kvs 8 9.. tab-set:: 10 11 .. tab-item:: app.cpp 12 13 .. code-block:: cpp 14 15 #include <cstddef> 16 17 #include "pw_kvs/flash_test_partition.h" 18 #include "pw_kvs/key_value_store.h" 19 // Not a required dep; just here for demo comms 20 #include "pw_sys_io/sys_io.h" 21 22 // Create our key-value store (KVS). Sector and entry vals for this 23 // demo are based on @pigweed//pw_kvs:fake_flash_64_aligned_partition 24 constexpr size_t kMaxSectors = 6; 25 constexpr size_t kMaxEntries = 64; 26 static constexpr pw::kvs::EntryFormat kvs_format = { 27 .magic = 0xd253a8a9, // Prod apps should use a random number here 28 .checksum = nullptr 29 }; 30 pw::kvs::KeyValueStoreBuffer<kMaxEntries, kMaxSectors> kvs( 31 &pw::kvs::FlashTestPartition(), 32 kvs_format 33 ); 34 35 kvs.Init(); // Initialize our KVS 36 std::byte in; 37 pw::sys_io::ReadByte(&in).IgnoreError(); // Get a char from the user 38 kvs.Put("in", in); // Save the char to our key-value store (KVS) 39 std::byte out; 40 kvs.Get("in", &out); // Test that the KVS stored the data correctly 41 pw::sys_io::WriteByte(out).IgnoreError(); // Echo the char back out 42 43 .. tab-item:: BUILD.bazel 44 45 .. code-block:: py 46 47 cc_binary( 48 name = "app", 49 srcs = ["app.cc"], 50 # ... 51 deps = [ 52 # ... 53 "@pigweed//pw_kvs", 54 "@pigweed//pw_kvs:fake_flash_64_aligned_partition", 55 # ... 56 ] 57 # ... 58 ) 59 60``pw_kvs`` is a flash-backed, persistent key-value storage (KVS) system with 61integrated :ref:`wear leveling <module-pw_kvs-design-wear>`. It's a relatively 62lightweight alternative to a file system. 63 64.. grid:: 2 65 66 .. grid-item-card:: :octicon:`rocket` Get started 67 :link: module-pw_kvs-start 68 :link-type: ref 69 :class-item: sales-pitch-cta-primary 70 71 Integrate pw_kvs into your project 72 73 .. grid-item-card:: :octicon:`code-square` Reference 74 :link: module-pw_kvs-reference 75 :link-type: ref 76 :class-item: sales-pitch-cta-secondary 77 78 pw_kvs API reference 79 80.. grid:: 2 81 82 .. grid-item-card:: :octicon:`stack` Design 83 :link: module-pw_kvs-design 84 :link-type: ref 85 :class-item: sales-pitch-cta-secondary 86 87 How pw_kvs manages state, does garbage collection, etc. 88 89 .. grid-item-card:: :octicon:`graph` Code size analysis 90 :link: module-pw_kvs-size 91 :link-type: ref 92 :class-item: sales-pitch-cta-secondary 93 94 The code size impact of using pw_kvs in your project 95 96.. _module-pw_kvs-start: 97 98----------- 99Get started 100----------- 101.. tab-set:: 102 103 .. tab-item:: Bazel 104 105 Add ``@pigweed//pw_kvs`` to your target's ``deps``: 106 107 .. code-block:: 108 109 cc_binary( 110 # ... 111 deps = [ 112 # ... 113 "@pigweed//pw_kvs", 114 # ... 115 ] 116 ) 117 118 This assumes that your Bazel ``WORKSPACE`` has a `repository 119 <https://bazel.build/concepts/build-ref#repositories>`_ named ``@pigweed`` 120 that points to the upstream Pigweed repository. 121 122 .. tab-item:: GN 123 124 Add ``$dir_pw_kvs`` to the ``deps`` list in your ``pw_executable()`` 125 build target: 126 127 .. code-block:: 128 129 pw_executable("...") { 130 # ... 131 deps = [ 132 # ... 133 "$dir_pw_kvs", 134 # ... 135 ] 136 } 137 138 .. tab-item:: CMake 139 140 Link your library to ``pw_kvs``: 141 142 .. code-block:: 143 144 add_library(my_lib ...) 145 target_link_libraries(my_lib PUBLIC pw_kvs) 146 147Use ``pw_kvs`` in your C++ code: 148 149.. code-block:: c++ 150 151 #include "pw_kvs/key_value_store.h" 152 153 // ... 154 155.. _pw_kvs/flash_memory.h: https://cs.opensource.google/pigweed/pigweed/+/main:pw_kvs/public/pw_kvs/flash_memory.h 156 157Implement the :ref:`flash memory <module-pw_kvs-design-memory>` and 158:ref:`flash partition <module-pw_kvs-design-partitions>` interfaces for 159your hardware. See `pw_kvs/flash_memory.h`_. 160 161.. _module-pw_kvs-reference: 162 163--------- 164Reference 165--------- 166 167.. _module-pw_kvs-reference-keyvaluestore: 168 169``pw::kvs::KeyValueStore`` 170========================== 171See :ref:`module-pw_kvs-design` for architectural details. 172 173.. doxygenclass:: pw::kvs::KeyValueStore 174 :members: 175 176Configuration 177============= 178.. doxygendefine:: PW_KVS_LOG_LEVEL 179.. doxygendefine:: PW_KVS_MAX_FLASH_ALIGNMENT 180.. doxygendefine:: PW_KVS_REMOVE_DELETED_KEYS_IN_HEAVY_MAINTENANCE 181 182.. _module-pw_kvs-design: 183 184------ 185Design 186------ 187:cpp:class:`pw::kvs::KeyValueStore` ("the KVS") stores key and value data 188pairs. The key-value pairs are stored in :ref:`flash partition 189<module-pw_kvs-design-memory>` as a :ref:`key-value entry 190<module-pw_kvs-design-entries>` (KV entry) that consists of a header/metadata, 191the key data, and value data. KV entries are accessed through ``Put()``, 192``Get()``, and ``Delete()`` operations. 193 194.. _module-pw_kvs-design-entries: 195 196Key-value entries 197================= 198Each key-value (KV) entry consists of a header/metadata, the key data, and 199value data. Individual KV entries are contained within a single flash sector; 200they do not cross sector boundaries. Because of this the maximum KV entry size 201is the partition sector size. 202 203KV entries are appended as needed to sectors, with append operations spread 204over time. Each individual KV entry is written completely as a single 205high-level operation. KV entries are appended to a sector as long as space is 206available for a given KV entry. Multiple sectors can be active for writing at 207any time. 208 209When an entry is updated, an entirely new entry is written to a new location 210that may or may not be located in the same sectore as the old entry. The new 211entry uses a transaction ID greater than the old entry. The old entry remains 212unaltered "on-disk" but is considered "stale". It is :ref:`garbage collected 213<module-pw_kvs-design-garbage>` at some future time. 214 215.. _module-pw_kvs-design-state: 216 217State 218===== 219The KVS does not store any data/metadata/state in flash beyond the KV 220entries. All KVS state can be derived from the stored KV entries. 221Current state is determined at boot from flash-stored KV entries and 222then maintained in RAM by the KVS. At all times the KVS is in a valid state 223on-flash; there are no windows of vulnerability to unexpected power loss or 224crash. The old entry for a key is maintained until the new entry for that key 225is written and verified. 226 227Each KV entry has a unique transaction ID that is incremented for each KVS 228update transaction. When determining system state from flash-stored KV entries, 229the valid entry with the highest transaction ID is considered to be the 230"current" entry of the key. All stored entries of the same key with lower 231transaction IDs are considered old or "stale". 232 233Updates/rewrites of a key that has been previously stored is done as a new KV 234entry with an updated transaction ID and the new value for the key. The 235internal state of the KVS is updated to reflect the new entry. The 236previously stored KV entries for that key are not modified or removed from 237flash storage, until garbage collection reclaims the "stale" entries. 238 239`Garbage collection`_ is done by copying any currently valid KV entries in the 240sector to be garbage collected to a different sector and then erasing the 241sector. 242 243Flash sectors 244============= 245Each flash sector is written sequentially in an append-only manner, with each 246following entry write being at a higher address than all of the previous entry 247writes to that sector since erase. Once information (header, metadata, data, 248etc.) is written to flash, that information is not modified or cleared until a 249full sector erase occurs as part of garbage collection. 250 251Individual KV entries are contained within a single flash sector; they do 252not cross sector boundaries. Flash sectors can contain as many KV entries as 253fit in the sector. 254 255Sectors are the minimum erase size for both :ref:`module-pw_kvs-design-memory` 256and :ref:`module-pw_kvs-design-partitions`. Partitions may have a different 257logical sector size than the memory they are part of. Partition logical sectors 258may be smaller due to partition overhead (encryption, wear tracking, etc) or 259larger due to combining raw sectors into larger logical sectors. 260 261.. _module-pw_kvs-design-layers: 262 263Storage layers 264============== 265The flash storage used by the KVS is comprised of two layers, flash memory 266and flash partitions. 267 268.. _module-pw_kvs-design-memory: 269 270Flash memory 271------------ 272``pw::kvs::FlashMemory`` is the lower storage layer that manages the raw 273read/write/erase of the flash memory device. It is an abstract base class that 274needs a concrete implementation before it can be used. 275 276``pw::kvs::FakeFlashMemory`` is a variant that uses RAM rather than flash as 277the storage media. This is helpful for reducing physical flash wear during unit 278tests and development. 279 280.. _module-pw_kvs-design-partitions: 281 282Flash partitions 283---------------- 284``pw::kvs::FlashPartition`` is a subset of a ``pw::kvs::FlashMemory``. Flash 285memory may have one or multiple partition instances that represent different 286parts of the memory, such as partitions for KVS, OTA, snapshots/crashlogs, etc. 287Each partition has its own separate logical address space starting from zero to 288``size`` bytes of the partition. Partition logical addresses do not always map 289directly to memory addresses due to partition encryption, sector headers, etc. 290 291Partitions support access via ``pw::kvs::NonSeekableWriter`` and 292``pw::kvs::SeekableReader``. The reader defaults to the full size of the 293partition but can optionally be limited to a smaller range. 294 295``pw::kvs::FlashPartition`` is a concrete class that can be used directly. It 296has several derived variants available, such as 297``pw::kvs::FlashPartitionWithStats`` and 298``pw::kvs::FlashPartitionWithLogicalSectors``. 299 300.. _module-pw_kvs-design-alignment: 301 302Alignment 303========= 304Writes to flash must have a start address that is a multiple of the flash 305write alignment. Write size must also be a multiple of flash write alignment. 306Write alignment varies by flash device and partition type. Reads from flash do 307not have any address or size alignment requirement; reads always have a 308minimum alignment of 1. 309 310:ref:`module-pw_kvs-design-partitions` may have a different alignment than the 311:ref:`module-pw_kvs-design-memory` they are part of, so long as the partition's 312alignment is a multiple of the alignment for the memory. 313 314.. _module-pw_kvs-design-allocation: 315 316Allocation 317---------- 318The KVS requires more storage space than the size of the key-value data 319stored. This is due to the always-free sector required for garbage collection 320and the "write and garbage collect later" approach it uses. 321 322The KVS works poorly when stored data takes up more than 75% of the 323available storage. It works best when stored data is less than 50%. 324Applications that need to do garbage collection at scheduled times or that 325write very heavily can benefit from additional flash store space. 326 327The flash storage used by the KVS is multiplied by the amount of 328:ref:`module-pw_kvs-design-redundancy` used. A redundancy of 2 will use twice 329the storage, for example. 330 331.. _module-pw_kvs-design-redundancy: 332 333Redundancy 334========== 335The KVS supports storing redundant copies of KV entries. For a given redundancy 336level (N), N total copies of each KV entry are stored. Redundant copies are 337always stored in different sectors. This protects against corruption or even 338full sector loss in N-1 sectors without data loss. 339 340Redundancy increases flash usage proportional to the redundancy level. The RAM 341usage for KVS internal state has a small increase with redundancy. 342 343.. _module-pw_kvs-design-garbage: 344 345Garbage collection 346================== 347Storage space occupied by stale :ref:`module-pw_kvs-design-entries` is 348reclaimed and made available for reuse through a garbage collection process. 349The base garbage collection operation is done to reclaim one sector at a time. 350 351The KVS always keeps at least one sector free at all times to ensure the 352ability to garbage collect. This free sector is used to copy valid entries from 353the sector to be garbage collected before erasing the sector to be garbage 354collected. The always-free sector is rotated as part of the KVS 355:ref:`wear leveling <module-pw_kvs-design-wear>`. 356 357Garbage collection can be performed manually, by invoking the methods below, 358or it can be configured to happen automatically. 359 360* :cpp:func:`pw::kvs::KeyValueStore::HeavyMaintenance()` 361* :cpp:func:`pw::kvs::KeyValueStore::FullMaintenance()` 362* :cpp:func:`pw::kvs::KeyValueStore::PartialMaintenance()` 363 364.. _module-pw_kvs-design-wear: 365 366Wear leveling (flash wear management) 367===================================== 368Wear leveling is accomplished by cycling selection of the next sector to write 369to. This cycling spreads flash wear across all free sectors so that no one 370sector is prematurely worn out. 371 372The wear leveling decision-making process follows these guidelines: 373 374* Location of new writes/rewrites of KV entries will prefer sectors already 375 in-use (partially filled), with new (blank) sectors used when no in-use 376 sectors have large enough available space for the new write. 377* New (blank) sectors selected cycle sequentially between available free 378 sectors. 379* The wear leveling system searches for the first available sector, starting 380 from the current write sector + 1 and wraps around to start at the end of a 381 partition. This spreads the erase/write cycles for heavily written/rewritten 382 KV entries across all free sectors, reducing wear on any single sector. 383* Erase count is not considered in the wear leveling decision-making process. 384* Sectors with already written KV entries that are not modified will remain in 385 the original sector and not participate in wear-leveling, so long as the 386 KV entries in the sector remain unchanged. 387 388.. _module-pw_kvs-size: 389 390------------------ 391Code size analysis 392------------------ 393The following size report details the memory usage of ``KeyValueStore`` and 394``FlashPartition``. 395 396.. include:: kvs_size 397