Introduction

This repository contains a case study of a storage layer for embedded applications, named record. Such systems typically rely on flash memory, which has unique properties and failure modes.

This case study is intended for embedded engineers interested in flash storage design, recovery algorithms, and failure-tolerant systems. It prioritizes clarity and auditability over feature completeness.

The constraints:

• flash memory wear and failure are a reality
• data integrity requirements imposed by the application
• the need to validate and reason about recovery behavior
• limited CPU, RAM, and flash resources typical of embedded platforms

Goals:

• good wear leveling
• flash failure assumptions embedded in the design
• built-in unclean shutdown operation mode
• deterministic and explainable recovery behavior in all supported failure modes
• simplicity
• auditability of the recovery algorithms
• good recovery runtime performance under normal operation conditions

Non-goals:

• ready to deploy/built-in replacement
• hierarchical data storage support
• support for all types of flash memories
• optimal recovery times in all conditions

Throughout this document, record refers to the storage component, entry refers to a single stored element, and record area / journal area refer to flash regions.

To achieve the above goals the following decisions and tradeoffs have been made:

1. store data as a sequence of entries in a circular buffer fashion - this allows for good wear leveling by spreading erase cycles across flash memory pages in a FIFO manner
2. use of checksums over the entries and entries headers (which now become the metadata), when a CRC check fails, both the data and its associated metadata are discarded; the component must remain usable in this state
3. write checks to detect corrupted writes and retry in subsequent slots
4. store with each entry a sequence number, the whole circular buffer becomes a long list of entries which are ordered and the recovery algorithm only task is to identify the most recent tail of this ordered list
5. use a dedicated journal area with hints of the head and tail of the record area to speed up record area recovery
6. allow for recovery in case of complete journal loss
7. automatic recycling of old entries, in order to keep the API simple

The main tradeoff here is between the recovery algorithm relying on accurate journal hints and recovery times. record uses journal hints but in case of journal area severe corruption record finds the most recent head and tail of the record area at the expense of potentially doing linear searches over large sections of memory.

Unlike traditional flash circular buffers that rely on intact metadata, record is designed to remain usable even after complete journal loss.

The data is presented as a flat list of entries to the user and the user has to deal with the possibility that some of the entries are corrupted, see record_read() and record_count() in record.h.

record is not suitable for applications that need hierarchical data storage, suitable applications for record might be:

• sensor acquisition application that temporarily needs to store data
• any data recording
• event log

Supported hardware and software

record has been developed with NRF Connect SDK V3.1.1 which is based on Zephyr RTOS. More information about NRF Connect SDK and Zephyr can be found on NordicSemi website

record has been tested with NRF52840-DK board, more information can be found here

Quick start

1. Clone and build

> git clone https://github.com/bogdan-petrica/record

# start your tool chain environment
# see https://docs.nordicsemi.com/bundle/ncs-latest/page/nrf/app_dev/config_and_build/building.html

# go to the directory
> cd record

# build
> west build --board nrf52840dk/nrf52840

2. Flash the image and connect over serial to the board

> west flash

Connect over the serial to UART0, for nrf58240dk the default UART0 settings are:

• speed: 115200
• data bits: 8
• stop bits: 1
• flow control: RTSCTS

Current KConfig enables shell, ztest and ztest_shell.

3. Run existing tests on the board

> ztest run-all

The tests run on the board and are sent to the host over serial, output might look like this:

...
[00:07:22.033,843] <inf> record: record boot - partial scan, head: 0, count: 96
[00:07:22.049,346] <inf> record: record boot - failed, no valid record found, err: -1001
[00:07:22.057,830] <inf> record: journal next seq: 0x0000
[00:07:22.063,629] <inf> record: record next seq: 0x00000000
[00:07:22.069,702] <inf> record: journal commit: 0
basic_test_append_entries, count: 80
basic_test_append_entries, count: 17
old count: 96, count: 81, lost: 16
old first seq: 0, first seq: 16
basic_test_append_entries, count: 13
basic_test_check_entries, record_count: 94
 PASS - record_read_invalid in 1.105 seconds
===================================================================
TESTSUITE basic_test succeeded

------ TESTSUITE SUMMARY START ------

SUITE PASS - 100.00% [basic_test]: pass = 23, fail = 0, skip = 0, total = 23 duration = 42.447 seconds
 - PASS - [basic_test.clean_init] duration = 0.291 seconds
 - PASS - [basic_test.clean_shutdown_data] duration = 5.308 seconds
 - PASS - [basic_test.corrupt_journal_and_data] duration = 8.036 seconds
 - PASS - [basic_test.corrupt_journal_around_tail] duration = 2.899 seconds
 - PASS - [basic_test.full_scan_ordered] duration = 0.945 seconds
 - PASS - [basic_test.full_scan_ordered_max_capacity] duration = 1.220 seconds
 - PASS - [basic_test.full_scan_wrapped_case_a] duration = 0.698 seconds
 - PASS - [basic_test.full_scan_wrapped_case_b] duration = 1.194 s
...

An example:

Below is example of a complete record usage, including initialization, appending, reading and shutdown.

    struct record_cfg = {
        .dev = DEVICE_DT_GET(DT_NODELABEL(mx25r64)),    //< the device tree node the for the QSPI NOR flash memory in nrf52840-dk board
        .off = 0,
        .size = 0x800000,                               //< 8MB
        .page_size = 4096,                              //< mx25r64 page size
        .write_size = 16                                //< mx25r64 write size
    };

    // initialize record; assumes flash was already 'formatted'
    rc = record_init(&cfg, 0);
    if (rc < 0) {
        // failed to initialize
        return rc; 
    }

    // add an entry
    struct record r = { };
    strcpy(r.raw, "Hello, record!");
    rc = record_append(&r);
    if (rc < 0) {
        // failed to append
        return rc;
    }

    // read the most recent entry, it highlight the fact that
    // count is the number of entries not necessarily all valid
    int j = record_count();
    do {
        --j;
        rc = record_read(j, &r);
    } while ((j > 0) && (rc < 0));

    if (rc < 0) {
        // failed to read
        return rc;
    }

    // under normal operation, expect that valid data is returned
    // by read after validated writes, the most recent entry has to
    // contain "Hello, record!"
    assert(!strcmp(r.raw, "Hello, record!"));

    // finally perform clean shutdown
    rc = record_shutdown();
    if (rc < 0) {
        return rc;
    }

Failure model

Expected failure modes embedded in the design:

• missing journal entries due to unclean shutdown
• partial writes
• corruption during reads or writes due to flash memory controller
• corruption of data due to flash memory wear
• complete loss of journal area

Failure modes with degraded behavior:

• large sequence of faulty pages makes the write algorithm stuck, the record area becomes read only

Failure modes not supported:

• intermittent write/read failure - write failure forces the append algorithm to advance and write to the next available slot, a read success for the memory where write failed could later lead to recovery algorithm report out of sequence. This can lead to ambiguous ordering and not handled to keep design simple.

Details

The basic block of storage is the entry, a circular buffer of entries called entry area.

Each entry contains a magic, a sequence number and a CRC checksum. The sequence numbers are used to identify the most recent entry.

The sequence numbers and the magic in the entry headers are included in the CRC calculation, allowing the recovery algorithm to validate the monotonicity of the sequence.

For reads the CRC is computed for the entry and verified against stored CRC, only valid records are passed to the user.

Writes are checked for corruption and retried on subsequent slots in the circular buffer.

Recovery algorithm

The algorithm is performed during boot to find the most recent head and tail within an entry area. It relies on sequence numbers stored in the entries headers; which are CRC validated.

Currently the algorithm is designed to stop linear searches on empty block detection( all 0xFFFF... or all 0x0000...).

The recovery algorithm performs binary probes and linear searches in its search area, the larger the search area the more linear searches might be needed which impacts performance.

The algorithm starts with a initial [low, high] area and a search area [j, k[, the initial value can be correct or stale, the algorithm will expand [low, high] until [j, k[ is empty or stops due to empty block detection.

Currently the algorithm runtime performance degrades gracefully depending on the accuracy of the hint:

• hint is most recent; validation of the head and tail and early stop
• hint is slightly stale; searches around head and tail and early stop
• hint is completely off or missing; many probes and searches are needed, worst case full scan;

For details see comments on struct record_search in record.c.

Overall structure and use of journal

The storage is split into two entry areas, record area and journal area. The record area stores the entries with the user data while the journal area stores hints of the heads and tails of the record area.

The journal hints are appended always after the record entries, and usually at a lower frequency (defined by JOURNAL_COMMIT_PERIOD).

The use of journal hints allow for faster recovery of the record area during boot, see recovery algorithm about details.

It is expected for the most recent journal hint to be out of sync with the record area, mainly due to unclean shutdowns(power cut, bugs, etc.) and potentially due to corruption, in such cases during boot a new journal entry is appended.

Comments of record_boot in record.c describe the usage of the journal hint to recover the record area.

Capacities

Currently the entries in the main data area use a 32 bit sequence number this limits the capacity to RECORD_ENTRY_SIZE * 2^31 = 512 GB.

The entries in the journal area use a 16 bit sequence number which limits the capacity to JOURNAL_ENTRY_SIZE * 2^15 = 512KB.

The capacities can't exceed 31 bits(or 15 bits) to avoid the ambiguity when the sequence numbers wrap around. For details on the bounds see comments for cmp_seq16() and cmp_seq32() in record.c.

Wear leveling performance calculation

The wear of the main area is as good as you can get with a circular buffer, however the wear of the journal area is higher due to smaller size compared to the main area, there is a formula to compute the wear ratio between the two, see record.h for details.

Here is a formula for journal area wear to record area wear ratio(assuming no bad pages due to wear):

((main size) / (journal size)) * ((journal entry size) / (record entry size) / (journal commit period))

Suppose default settings with 8MB main size, 8KB journal and 100'000 minimum erase cycles before wear, we get:

(8MB/8KB) * ((16) / (256) / (16)) = 1024/256 = 4 // journal area wears out at 4x rate compared to main area

8MB * 100'000 / 4 ~= 195GB // written to main area before wear in the journal

Suppose we have 1GB main area with 32 journal commit period:

(1GB/8KB) * ((16) / (256) / (32)) = 131072 / 512 = 256

1GB * 100'000 / 256 ~= 415GB // written to main area before wear in the journal

Suppose the same example as above but use 64 journal commit period and 16KB journal area:

(1GB/16KB) * ((16) / (256) / (64)) = 64

1GB * 100'000 / 64 ~= 1.5TB // written to main area before wear in the journal

Limitations and caveats

Currently the implementation assumes a page size of 4KB and record area entries sizes of 256b, increasing record entry size past 4096b can be done by increasing the page size to at least record size; for 8KB records use at least 8KB pages.

Another limitation is that at least two pages are allocated for the journal and record and record area, this is for simplicity of some checks but technically not needed.

Note that using only one page for the journal area is not effective as complete loss of journal entries is possible; consider a power cut after a journal page erase and a journal entry append.

The journal area uses 16b entries, to keep the required size small and improve wear performance, however it imposes a maximum of 16b flash memory write size.

The record_append() error reporting is suboptimal; caller can't distinguish between a record area entry appending failure(serious condition) and a journal area entry appending failure(not a serious as data is stored safely, only the recovery performance is impacted).

Possible further improvements

Limited API record_read()

The current API record_count(), record_read() exposes entries which can't be checked to the user and also the indices are not stable, especially the most recent entry index.

One possible solution is to use an iterator pattern for access, something like:

    struct record r;
    
    struct record_it it;
    // first element from the end, for example
    record_iter_init(&it, RECORD_ITER_END, 0);

    if (record_iter_valid(&it)) {
        rc = record_read(&it, &r);
        if (rc < 0) {
            return rc;
        }

        // use r
    }

Stuck record_append() due to large memory area failure.

One idea is to expose the failure to the caller and also allow for recording the next slot, the tuple (head, tail) from journal hint and entry area will get a new member (head, tail, next). next will indicate the next slot to append to, on success tail is advanced to next.

Support write/read failure mode

See failure model. One way to avoid out of sequence condition with duplicates is to advance the sequence number when retrying, this still means the following invariant will hold:

last - head >= last_seq - head_seq

However, to implement it needs to: recompute the CRC when going to the next slot in case of failure during append(can be optimized, consider sequence as the last element in the entry and use CRC updates) and accept duplicates at a higher level.

Recovery runtime performance improvement opportunity

The recovery algorithm runtime performance is dependent on the initial search window(see recovery algorithm), the smaller the unexplored region the faster the better the runtime performance.

There are cases when search window can be significant while the journal hint is only slightly stale, consider the expected scenario(accurate journal hint), with tail wrapping around head:

    tail = hint.tail < head = hint.head

With this setup the unexplored region [hint.tail, hint.head[, needs to be examined and if the record area utilization is near maximum capacity the region is really small.

A minute stale journal hint would lead to the following, situation:

    hint.tail < tail < head = hint.head

Still, the unexplored region is small and the record area most recent head and tail are found fast.

Now consider this scenario, with journal hint being properly stale:

    hint.tail < hint.head < tail < head

The unexplored region is [hint.head, hint.tail[; this is because the sequence number at the hint.head is more recent than hint.tail (due to new elements being appended). The unexplored region size is almost size of the record area, even tough the algorithm benefits from doing binary slices, it's still poorly initialized.

Testing

Tests are executed on real hardware (nrf52840-DK) unless otherwise stated.

Following tests have been conducted on record:

• normal operation
• normal operation with clean shutdown
• API tests
• power cut tests; all sorts of scenarios
• forced full scan for record area recovery; all sorts of scenarios
• journal entries corruption
• journal entries and record entries corruption
• append retries due to failed write checks

Following tests have not been conducted:

• flash API failure reporting for writes, reads and erases
• out of sequence condition in record area
• recovery performance with large flash memories

There is a performance test inside basic_test.c, called basic_test::performance_check that allows evaluation of recovery runtime performance for 2MB(8192 entries) flash memory with 8000 entries available.

Linear scan takes ~0.735ms, full scan with linear probes takes ~0.0903ms and clean shutdown recovery takes ~0.0263ms.