folio

Overview ¶

Full document enumeration in a single pass.

All scans data records (_r=2) across the heap and sparse regions, extracting label and content by byte scanning. Unlike the List+Get pattern, it never follows index pointers — content is read directly from the data record, avoiding per-document seek overhead.

The scan uses the same sorted-region awareness as Search: only the heap and sparse regions are visited, skipping the index section entirely. Records retired by Set or Delete have their type byte patched from 2 to 3 (history), so the type check at TypePos naturally excludes them.

Database teardown.

Public entry points for the two common Repair modes.

Compression for inline history snapshots.

Each record's _h field stores the document content at the time of write. The content is Zstd-compressed for size, then Ascii85-encoded to produce a printable string that can be embedded directly in a JSON value without escaping. This avoids the 33% overhead of base64 while remaining newline-free (critical for the line-delimited format).

Core type definitions and structural helpers.

Concurrency is managed in three layers, each serving a different scope:

1. Atomic state machine (db.state): gates whether new operations are allowed at all. Transitions: StateAll → StateRead → StateNone → StateClosed. Checked at the top of every public method.

2. sync.RWMutex (db.mu): coordinates in-process readers and writers. Readers hold RLock; writers and Repair hold Lock.

3. OS file lock (db.lock): coordinates across processes via flock(2) or LockFileEx. See internal/flock for lifetime management.

When an operation starts, it waits (via db.cond) until the state allows it, then acquires the appropriate lock level at layers 2 and 3.

Soft deletion — the record is converted to history so its compressed snapshot survives for version retrieval, but it no longer appears in lookups or listings because its index is erased.

Package folio provides an append-only document database backed by a single JSONL file. Documents are stored as newline-delimited JSON records with automatic versioning — every update preserves the previous content as a compressed history snapshot.

The file is divided into a heap, index, and sparse region. The heap co-locates data and history records sorted by ID then timestamp, so all versions of a document are contiguous. Indexes follow the heap in sorted order. The sparse region collects new writes and is scanned linearly. Compaction merges the sparse region back into the heap. This design keeps all state on disk without requiring in-memory indexes, though an optional bloom filter can accelerate negative lookups in the sparse region.

Concurrency gating for the three-layer lock protocol.

blockWrite and blockRead acquire all three concurrency layers (state check → OS flock → RWMutex) before allowing an operation to proceed. On return the caller holds db.mu (Lock or RLock) and db.lock; both must be released in the defer of the calling method.

Document retrieval using the two-region lookup strategy.

Lookups check the sorted index section first (binary search, O(log n)), then fall back to the sparse region (linear scan) for records written since the last compaction. The optional bloom filter can skip the sparse scan entirely when an ID is definitively absent.

Hash algorithms for deriving the _id field from a document label.

_id is always 16 hex characters (64 bits). This fixed width is what allows scanm to extract IDs at a known byte offset without parsing. The algorithm is stored in the header so all records in a file use the same one; Rehash can migrate between algorithms in place because the output width is identical across all three.

xxHash3 is the default because it has the best throughput for short strings (document labels) and excellent distribution. FNV-1a exists as a stdlib-only fallback for environments that cannot use cgo or external dependencies. Blake2b is offered for users who want cryptographic-quality distribution to minimise collision probability, at the cost of ~10x slower hashing — relevant only for very large databases where birthday-bound collisions on 64-bit hashes become a concern.

The header occupies the first 128 bytes of the database file. It stores section boundaries, document count, and a dirty flag for crash recovery. The fixed size allows the dirty flag to be toggled with a single-byte write at a known offset, avoiding a full header rewrite on every mutation.

Version history retrieval from compressed _h snapshots.

Both current Records (_r=2) and retired History records (_r=3) carry a compressed snapshot in _h. History collects all of them for a given label, decompresses each, and yields them in chronological write order.

After compaction, all versions of a document are contiguous in the heap (sorted by ID then timestamp). History uses group() to binary-search the heap for the ID group, then linearly scans the sparse region for any records appended since the last compaction.

Because results must be sorted by file offset (the ground truth for write order), all versions are collected and sorted before yielding. The iterator API provides consistency with Search, MatchLabel, and List even though this method buffers internally.

Label enumeration across the entire file.

Memory-mapped file I/O for Unix platforms.

mmapFile maps a file read-only with MAP_SHARED so that in-place patches made through the writer fd are visible immediately (both fds share the kernel page cache). Only appends that extend the file beyond the mapped region require a remap.

Database creation and opening.

Low-level read primitives for the newline-delimited record format.

Every record is a single JSON line terminated by '\n'. These functions read individual lines and find record boundaries via io.ReaderAt so that concurrent readers do not interfere with each other's offsets.

All read functions accept a source (an io.ReaderAt with a known size) rather than *os.File directly. When memory-mapping is enabled the source wraps the mmap'd region; otherwise it wraps the read-only fd.

Record format and type definitions.

Every line in the database file is a JSON object beginning with {"_r":N where N identifies the record type. This fixed prefix allows type detection and ID extraction at known byte offsets without JSON parsing — critical for binary search and compaction where millions of records may be scanned.

Three types coexist in the file:

• Index (_r=1): maps a label's hash to the byte offset of its data record.
• Record (_r=2): the current content of a document.
• History (_r=3): a previous version with compressed content in _h.

On update, the old Record is retyped to History (byte patch from 2→3) and its _d field is blanked. This preserves the compressed snapshot in _h for version retrieval while making the record invisible to data scans.

In-place hash algorithm migration.

All three algorithms produce a 16 hex character (8 byte) _id, and the _id field sits at a fixed byte offset in every record. This means Rehash can overwrite each _id in place without moving or resizing any records — no temp file, no rewrite, just a linear scan with targeted byte patches.

The dirty flag is set before any patches begin and cleared after the header is updated. A crash mid-rehash leaves the flag set, so the next Open triggers automatic Repair — which rebuilds all IDs from labels, restoring consistency regardless of how many patches completed.

Label renaming with in-place patching when possible.

When old and new labels have the same byte length, Rename patches _id and _l directly in the data record and index record — no new version is created and no history entry is added. When lengths differ, it falls back to appending a new record+index and blanking the old ones (equivalent to Set+Delete but under a single lock hold).

History records are not patched in either path: they retain the old ID and become unreachable via History(newLabel). This matches the behaviour callers would get from the manual Get+Set+Delete approach.

Repair rebuilds the database file with all records in sorted order.

Over time, appends accumulate in the sparse region and lookups degrade toward linear scans. Repair reads every record, sorts by ID, and writes a new file with a contiguous heap (data + history sorted by ID then timestamp) followed by sorted indexes — restoring O(log n) binary search. It also serves as crash recovery: on Open, if a .tmp file or dirty flag is found, Repair is run automatically to restore consistency.

A temporary file (.tmp) is used instead of rewriting in place because in-place rewrite risks total data loss on crash: if the process dies mid-rewrite, both the old and new data are gone. Writing to a temp file, syncing, then atomically renaming means the original file is intact until the rename succeeds. A crash during the write phase at worst orphans the .tmp file, which is cleaned up on next Open.

The operation proceeds in two phases to minimise the time readers are blocked:

• Phase 1 (read lock): scan the old file and write the new .tmp file. Concurrent readers continue using the old file.
• Phase 2 (write lock): swap file handles from the old file to the new one. This is a brief exclusive lock for the atomic rename.

When called for crash recovery (BlockReaders=true), a write lock is held for the entire operation since the file may be inconsistent.

Scan strategies for the two-region file layout.

After compaction the file contains a sorted heap (data + history interleaved by ID then timestamp) followed by sorted indexes. New writes are appended after the indexes into a sparse (unsorted) region. Lookups therefore need two strategies:

• scan: binary search over a sorted section. O(log n) seeks. Pass recordType=0 to match any type (type-agnostic).
• sparse: linear scan over the unsorted region. O(n) but bounded to records written since the last compaction.

scanm is a compaction-only variant that extracts metadata at fixed byte positions without JSON parsing, since compaction must touch every record but only needs ID, type, timestamp, and label.

Search over document content and labels.

Search scans data records (_r=2) and matches against the _d field. After compaction the file has three sections: heap (data + history), index, and sparse. Search only needs the heap and sparse regions — the index section contains no _d fields. The scan skips the index section entirely by reading [HeaderSize..heapEnd) then [sparseStart..EOF). Before any compaction both boundaries are zero, so the first range is empty and the second covers the whole file — identical to a full scan.

Literal patterns (no regex metacharacters) take a fast path: the query is JSON-escaped and matched with bytes.Contains, avoiding both regex overhead and the need to unescape record content. Patterns containing regex metacharacters fall back to regexp.Match with optional decode.

The literal path works by escaping the search term into the same JSON representation used on disk (via json.Marshal), then matching raw bytes directly. This avoids per-record unescape overhead entirely. However, it assumes the on-disk encoding matches what json.Marshal produces. If Decode is set, the caller explicitly wants unescape-then-match semantics (e.g. to handle non-standard encodings like \u0041 for 'A'), so the literal path is bypassed to guarantee equivalent results.

Case-insensitive literal search uses bytes.ToLower on both needle and content. This allocates a copy of the _d slice per record. A zero-alloc alternative (sliding bytes.EqualFold) would trade O(n) for O(n*m) but eliminate GC pressure. We keep ToLower for now because search terms are typically short and the allocation is bounded to the _d field, not the full record line. Revisit if profiling shows GC pressure from search.

MatchLabel scans index records (_r=1) and matches against _l. It scans only the index section and sparse region, skipping the heap entirely.

Both stream through the file line-by-line to avoid loading it into memory. Callers consume results lazily via range and can break early to stop the scan without reading the rest of the file.

Document creation and update using append-then-blank.

A Set always appends a new Record+Index pair at the tail. If an older version exists, it is then patched in place: its type byte is changed from Record (2) to History (3), its _d content is blanked with spaces, and its index line is overwritten with spaces. The compressed snapshot in _h is preserved so History can still retrieve the old content. This approach avoids rewriting the file on every update while keeping the latest version immediately accessible via the newest index.

Batch amortises lock acquisition across multiple documents. All inputs are validated before any writes begin — if validation fails, no documents are written.

Write primitives for the append-only file.

New records are always appended at db.tail (the current end of file). The dirty flag is set on the first write of a session so that an unclean shutdown can be detected on next Open and trigger automatic repair. It is cleared during Close once all data has been flushed.

package main

import (
	"fmt"
	"log"
	"os"
	"path/filepath"

	"github.com/jpl-au/folio"
)

func main() {
	dir, _ := os.MkdirTemp("", "folio-example")
	defer os.RemoveAll(dir)

	// Open or create a database
	db, err := folio.Open(filepath.Join(dir, "myapp.folio"), folio.Config{})
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()

	// Store a document
	db.Set("readme", "# My App\n\nWelcome to my application.")

	// Retrieve it
	content, _ := db.Get("readme")
	fmt.Println(content)
}

Output:
# My App

Welcome to my application.