.. _module-pw_kvs:

======
pw_kvs
======
.. pigweed-module::
   :name: pw_kvs

.. tab-set::

   .. tab-item:: app.cpp

      .. code-block:: cpp

         #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

   .. tab-item:: BUILD.bazel

      .. code-block:: py

         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 :ref:`wear leveling <module-pw_kvs-design-wear>`. It's a relatively
lightweight alternative to a file system.

.. grid:: 2

   .. grid-item-card:: :octicon:`rocket` Get started
      :link: module-pw_kvs-start
      :link-type: ref
      :class-item: sales-pitch-cta-primary

      Integrate pw_kvs into your project

   .. grid-item-card:: :octicon:`code-square` Reference
      :link: module-pw_kvs-reference
      :link-type: ref
      :class-item: sales-pitch-cta-secondary

      pw_kvs API reference

.. grid:: 2

   .. grid-item-card:: :octicon:`stack` Design
      :link: module-pw_kvs-design
      :link-type: ref
      :class-item: sales-pitch-cta-secondary

      How pw_kvs manages state, does garbage collection, etc.

   .. grid-item-card:: :octicon:`graph` Code size analysis
      :link: module-pw_kvs-size
      :link-type: ref
      :class-item: sales-pitch-cta-secondary

      The code size impact of using pw_kvs in your project

.. _module-pw_kvs-start:

-----------
Get started
-----------
.. tab-set::

   .. tab-item:: Bazel

      Add ``@pigweed//pw_kvs`` to your target's ``deps``:

      .. code-block::

         cc_binary(
           # ...
           deps = [
             # ...
             "@pigweed//pw_kvs",
             # ...
           ]
         )

      This assumes that your Bazel ``WORKSPACE`` has a `repository
      <https://bazel.build/concepts/build-ref#repositories>`_ named ``@pigweed``
      that points to the upstream Pigweed repository.

   .. tab-item:: GN

      Add ``$dir_pw_kvs`` to the ``deps`` list in your ``pw_executable()``
      build target:

      .. code-block::

         pw_executable("...") {
           # ...
           deps = [
             # ...
             "$dir_pw_kvs",
             # ...
           ]
         }

   .. tab-item:: CMake

      Link your library to ``pw_kvs``:

      .. code-block::

         add_library(my_lib ...)
         target_link_libraries(my_lib PUBLIC pw_kvs)

Use ``pw_kvs`` in your C++ code:

.. code-block:: c++

   #include "pw_kvs/key_value_store.h"

   // ...

.. _pw_kvs/flash_memory.h: https://cs.opensource.google/pigweed/pigweed/+/main:pw_kvs/public/pw_kvs/flash_memory.h

Implement the :ref:`flash memory <module-pw_kvs-design-memory>` and
:ref:`flash partition <module-pw_kvs-design-partitions>` interfaces for
your hardware. See `pw_kvs/flash_memory.h`_.

.. _module-pw_kvs-reference:

---------
Reference
---------

.. _module-pw_kvs-reference-keyvaluestore:

``pw::kvs::KeyValueStore``
==========================
See :ref:`module-pw_kvs-design` for architectural details.

.. doxygenclass:: pw::kvs::KeyValueStore
   :members:

Configuration
=============
.. doxygendefine:: PW_KVS_LOG_LEVEL
.. doxygendefine:: PW_KVS_MAX_FLASH_ALIGNMENT
.. doxygendefine:: PW_KVS_REMOVE_DELETED_KEYS_IN_HEAVY_MAINTENANCE

.. _module-pw_kvs-design:

------
Design
------
:cpp:class:`pw::kvs::KeyValueStore` ("the KVS") stores key and value data
pairs. The key-value pairs are stored in :ref:`flash partition
<module-pw_kvs-design-memory>` as a :ref:`key-value entry
<module-pw_kvs-design-entries>` (KV entry) that consists of a header/metadata,
the key data, and value data. KV entries are accessed through ``Put()``,
``Get()``, and ``Delete()`` operations.

.. _module-pw_kvs-design-entries:

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 :ref:`garbage collected
<module-pw_kvs-design-garbage>` at some future time.

.. _module-pw_kvs-design-state:

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 :ref:`module-pw_kvs-design-memory`
and :ref:`module-pw_kvs-design-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.

.. _module-pw_kvs-design-layers:

Storage layers
==============
The flash storage used by the KVS is comprised of two layers, flash memory
and flash partitions.

.. _module-pw_kvs-design-memory:

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.

.. _module-pw_kvs-design-partitions:

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``.

.. _module-pw_kvs-design-alignment:

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.

:ref:`module-pw_kvs-design-partitions` may have a different alignment than the
:ref:`module-pw_kvs-design-memory` they are part of, so long as the partition's
alignment is a multiple of the alignment for the memory.

.. _module-pw_kvs-design-allocation:

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
:ref:`module-pw_kvs-design-redundancy` used. A redundancy of 2 will use twice
the storage, for example.

.. _module-pw_kvs-design-redundancy:

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.

.. _module-pw_kvs-design-garbage:

Garbage collection
==================
Storage space occupied by stale :ref:`module-pw_kvs-design-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
:ref:`wear leveling <module-pw_kvs-design-wear>`.

Garbage collection can be performed manually, by invoking the methods below,
or it can be configured to happen automatically.

* :cpp:func:`pw::kvs::KeyValueStore::HeavyMaintenance()`
* :cpp:func:`pw::kvs::KeyValueStore::FullMaintenance()`
* :cpp:func:`pw::kvs::KeyValueStore::PartialMaintenance()`

.. _module-pw_kvs-design-wear:

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.

.. _module-pw_kvs-size:

------------------
Code size analysis
------------------
The following size report details the memory usage of ``KeyValueStore`` and
``FlashPartition``.

.. include:: kvs_size