SparseFS — An Append‑Only Micro Filesystem for Event Logs

What and why

If your MCU has a handful of kilobytes of flash and you need reliable event logging (errors, sensor samples, telemetry) without a FAT or a POSIX layer, an append‑only micro filesystem is a great fit. SparseFS is a tiny design pattern: append records sequentially, detect incomplete records after power loss, and compact sectors when needed. It’s minimal, flash‑friendly, and intentionally simple so you can implement it on ATtiny class parts or tiny ARM Cortex‑M chips.

Design goals

• Crash tolerance: detect and ignore partially written records after brownouts.
• Low RAM: scanning record headers only, no big buffers.
• Wear friendliness: move live records in blocks and erase sectors only when necessary.
• Small API: append(), iterate(), compact().

Flash layout

SparseFS organizes flash into N equal erase blocks (sectors). Each sector contains zero or more variable‑length records packed back‑to‑back. Records are never updated in place; they’re appended. When a sector is mostly stale, live records are copied to a fresh sector and the old sector is erased.

Record format (all little‑endian) — intentionally tiny:

struct record_hdr { uint8_t magic; uint32_t seq; uint16_t len; uint8_t type; uint8_t hdr_crc; }

Followed immediately by len bytes of payload and then a single uint8_t tail_crc that covers the payload. Magic byte is 0x7E for a written header; empty flash is 0xFF. We mark a record as complete only if both hdr_crc and tail_crc match.

Why this layout?

1. Writing order: program header, stream payload, program tail_crc. If power fails mid‑payload or before tail_crc, the record is ignored on startup.
2. Header has seq number so readers can find newest events without keeping state in RAM.
3. Small CRCs (8‑bit) are cheap and catch common corruption; you can bump to 16‑bit if you have CPU headroom.

APIs and small code sketches

Three primitive operations are enough.

1. append(type, data, len)
2. iterate(callback) — scan sectors and invoke callback on each valid record
3. compact() — reclaim space when free bytes drop below threshold

Append sketch (pseudocode; adapt to your flash driver):

uint32_t append(uint8_t type, const uint8_t *data, uint16_t len) { addr = find_write_address(); hdr.magic = 0x7E; hdr.seq = next_seq++; hdr.len = len; hdr.type = type; hdr.hdr_crc = crc8(&hdr, sizeof(hdr)-1); flash_write(addr, &hdr, sizeof(hdr)); addr += sizeof(hdr); flash_write(addr, data, len); addr += len; uint8_t tail = crc8(data, len); flash_write(addr, &tail, 1); return hdr.seq; }

Iterate sketch (scan only, minimal RAM):

void iterate(void (*cb)(uint32_t seq, uint8_t type, const uint8_t *data, uint16_t len)) { for (sector : sectors) { addr = sector.start; while (addr < sector.end) { uint8_t magic = flash_read8(addr); if (magic == 0xFF) break; // rest is empty if (magic != 0x7E) { addr++; continue; } // garbage – advance record_hdr hdr; flash_read(addr, &hdr, sizeof(hdr)); if (hdr.hdr_crc != crc8(&hdr, sizeof(hdr)-1)) { addr++; continue; } payload = buf_small; // allocate small buffer or stream to callback flash_read(addr+sizeof(hdr), payload, hdr.len); uint8_t tail = flash_read8(addr+sizeof(hdr)+hdr.len); if (tail != crc8(payload, hdr.len)) { addr++; continue; } cb(hdr.seq, hdr.type, payload, hdr.len); addr += sizeof(hdr) + hdr.len + 1; } } }

Garbage collection — compacting without big buffers

When free space drops below a threshold, pick the least‑live sector and copy its live records into an empty sector. The copy loop uses the same iterate code but writes records into the new sector with new seq numbers or preserved seq if you prefer monotonic ordering. After successful copy, mark old sector as erased (perform erase operation).

To avoid needing RAM for entire records, stream records: read payload in small chunks (32–128 bytes) and write them out. This keeps RAM tiny at the cost of a few extra flash writes during compaction.

Startup recovery

On boot, scan all sectors and build two tiny pieces of state: highest seq seen and the write address (first free byte after last complete record). Ignore records missing a valid tail_crc or with corrupted hdr_crc. Because records are appended and only finalized when tail_crc is written, incomplete records are naturally ignored.

Tip: store a small redundant pointer in a reserved page if startup scanning is slow and your device boots frequently. Keep two copies and validate with CRC to recover quickly.

Tradeoffs and gotchas

• Append‑only means fragmentation until compaction runs; tune threshold for your write pattern.
• CRC8 is small and cheap but weaker; if you log critical data (firmware checksums, security events), use CRC16 or a lightweight MAC with a secret key.
• If your flash requires word‑aligned writes, pad records or enforce alignment in the write path.
• Avoid storing large blobs unless you are comfortable with long copy times during compaction; split big payloads into chunks if needed.

Debugging and testing

1. Simulate power loss: interrupt append mid‑payload and reboot. The incomplete record must be ignored.
2. Fill flash, compact, and verify seq monotonicity and no duplicate or lost records (unless deliberate).
3. Stress test with frequent small writes to ensure compaction keeps up and wear is balanced across sectors.

Wrap‑up

SparseFS is intentionally small and pragmatic: append with a small header, validate with CRCs, stream during compaction, and keep RAM tiny. It’s not a full filesystem — that’s by design. For telemetry, diagnostics, or any data you want to survive brownouts on a shingled little MCU, an append‑only layout like this hits the sweet spot between durability and simplicity.

If you want, I can drop a ready‑to‑flash C implementation for an MCU family (ATtiny/ARM M0) with a 256‑byte RAM budget. Tell me your chip and flash geometry and I’ll tailor it.