A small C++17 file-backed key/value store for exploring binary record validation,
log recovery, ownership, batch semantics, snapshots, and stateful fuzzing. The
library uses the standard library only.
Status
The storage library, CLI, and two libFuzzer entry points are present. This is an
unverified source draft. No build, test, sanitizer, static-analysis, or Fuzz
result is claimed. The current CMake configuration references
tests/test_store.cpp, which has not yet been written. Add that source or remove
its test target before running the build commands below. Setting
BUILD_TESTING=OFF alone does not remove the unconditional test executable.
Execution was stopped at the user’s request. The examples are future usage
instructions, not records of completed validation.
Features
Binary-safe, nonempty keys and binary-safe values stored in a sorted index.
Put, get, erase, ordered batches, and compare/exchange operations.
Append-only, checksummed transaction records with contiguous sequences.
Recovery of committed records and optional incomplete-tail truncation.
Immutable in-memory snapshots and optimistic transaction conflict checks.
Snapshot backup, log compaction, prefix/range queries, and snapshot diffs.
Escaped text import/export and a tab-separated batch command format.
Journal inspection, per-key history, and replay up to a sequence number.
Configurable limits on keys, values, records, files, batches, and entries.
Layout
Location
Responsibility
include/kv/format.hpp, src/format.cpp
Binary format, CRC32, bounded decoding, recovery, and atomic in-memory batch application
include/kv/store.hpp, src/store.cpp
Directory lock, file persistence, snapshots, transactions, compaction, and backup
include/kv/query.hpp, src/query.cpp
Filtering, diffs, text formats, batch parsing, and statistics
include/kv/journal.hpp, src/journal.cpp
Journal inspection, record extraction, prefix replay, and history
src/main.cpp
CLI
fuzz/fuzz_recovery.cpp
Corrupt/truncated journal recovery and snapshot equivalence
fuzz/fuzz_operations.cpp
In-memory operations versus a reference map, record roundtrips, and text export/import
Keep the shared ../cmake/ProjectOptions.cmake beside the project. The store
directory contains data.log; a .lock directory represents exclusive access.
Build and Basic Usage
After resolving the missing test-source item, use CMake 3.16+, a C++17 compiler,
and Ninja. Linux/WSL is the intended environment for compaction and Fuzz examples.
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug
cmake --build build
ctest --test-dir build --output-on-failure
build/kv_cli put demo-db user/1 Alice
build/kv_cli put demo-db user/2 Bob
build/kv_cli get demo-db user/1
build/kv_cli list demo-db user/
build/kv_cli stats demo-db
build/kv_cli erase demo-db user/2
build/kv_cli export demo-db > exported.tsv
build/kv_cli backup demo-db backup.mkv
build/kv_cli compact demo-db
build/kv_cli check demo-db/data.log
build/kv_cli inspect demo-db/data.log
build/kv_cli history demo-db/data.log user/1
The CLI returns 0 on success, 1 on an operation error, 2 on invalid usage, and
3 for a missing get or erase key. diff returns 1 when snapshots differ.
Read commands open an existing store instead of implicitly creating one.
get and text output escape binary bytes rather than writing raw control
characters. Backup refuses an existing destination. Compaction replaces the
active journal with a checksummed snapshot while retaining its sequence number.
Library Example
#include "kv/store.hpp"
kv::Store store("demo-db");
kv::Batch batch;
batch.put("account/alice", "100");
batch.put("account/bob", "50");
store.write(batch);
auto snapshot = store.snapshot();
kv::Transaction transaction(store);
transaction.put("account/alice", "90");
transaction.put("account/bob", "60");
transaction.commit();
// The copied snapshot still contains the earlier values.
auto old_value = snapshot.get("account/alice");
Batch operations execute in order; repeated keys are allowed. Empty batches do
not increment the sequence. An erase of a missing key is still logged when
issued through the store. A transaction reads from its own working copy and
commits only if the store sequence still equals its starting sequence. A
conflicting commit raises kv::Error; rollback or create a new transaction.
Text Import and Batch Commands
Export/import uses exactly two tab-separated fields per nonempty line:
user/1<TAB>Alice
user/2<TAB>Bob
<TAB> above means a literal tab. Escapes are \\, \t, \n, \r, and
\xHH. Imports are one batch and replace matching keys without removing others.
Batch files additionally include the command name:
Batch files accept blank lines and lines beginning with # as comments.
Import files do not interpret # as a comment. Replay cannot reconstruct
history removed by compaction; sequence requests below the journal base fail.
Binary Journal Format
All integers are unsigned and big-endian. The 16-byte file header contains:
Offset
Size
Meaning
0
4
ASCII MKV1
4
4
Format version 1
8
8
Base sequence
Each transaction has a 24-byte header:
Offset
Size
Meaning
0
4
ASCII TXN1
4
4
Payload length
8
8
Positive transaction sequence
16
4
Operation count
20
4
CRC32
The payload is a sequence of operations: 1-byte kind, 4-byte key length, 4-byte
value length, key bytes, and value bytes. Kind 1 is put; kind 2 is erase and must
have an empty value. CRC32 covers header bytes 0–19 followed by the payload.
It uses polynomial 0xEDB88320, initial state 0xffffffff, and final complement.
The file header itself does not have a checksum.
A nonempty compacted snapshot uses one put-only transaction at the current
sequence and a base sequence one lower. An empty snapshot is only a file header.
Consequently, compaction is limited by the maximum operations and payload size
of a single record, even when the live store could otherwise hold more entries.
Recovery, Locking, and Durability
Recovery validates sequence continuity, record lengths, operation limits, and
checksums before applying each complete transaction. A partial final record may
be ignored when tolerate_tail is enabled. A complete record with a bad checksum
is rejected rather than silently discarded. A writable store truncates an
accepted incomplete tail before appending; a read-only store does not alter it.
The lock directory is exclusive for every Store, including read-only opens.
Read-only mode therefore still requires permission to create/remove the lock
directory. The library is single-threaded and does not implement shared readers
or synchronization between threads.
A process crash may leave .lock behind. Confirm that no process owns the store
before manually removing a stale lock. Compaction refuses a preexisting
compact.tmp; inspect such a file before cleanup. Replacement uses filesystem
rename semantics and is intended for Linux/WSL. Native Windows may reject rename
over an existing destination; in that case compaction fails and retains the old
journal.
Writes close their output stream but do not issue fsync, synchronize the parent
directory, or promise durability across power loss. This is an educational
storage engine, not a production database. Do not rely on it for valuable data.
Clang, CodeChecker, and compatible CTU mapping tools are separate prerequisites.
Useful paths to inspect include decoding into operation records, applying a
batch before journal append, cleanup after I/O failure, and snapshot replacement.
Static detection of particular bugs depends on enabled checkers and the compiler.
Fuzz builds enable libFuzzer, ASan, and UBSan. A separate ordinary sanitizer build
can use -DENABLE_SANITIZERS=ON. Replay a saved input with the matching Fuzz
executable and its filename. No campaign has been run for this draft.
The recovery harness feeds arbitrary journal bytes, compares tolerant recovery
with strict recovery of the accepted prefix, and checks compacted snapshots.
The operation harness decodes bounded byte commands, compares kv::apply against
an independent std::map, and checks record and text-format roundtrips. It does
not fuzz filesystem durability or operating-system failures.
Optional Demonstration Defects
Configure a separate build-bugs directory with -DENABLE_DEMO_BUGS=ON and
-DENABLE_FUZZING=ON. The normal CTest registration is disabled there.
ID
Location
Trigger
Expected detector
Repair
KV-001
src/format.cpp, decode_record
A valid record containing a long key beginning with LEGACY:
ASan; possible static buffer diagnostic
Preserve dynamically sized key storage and remove strcpy
KV-002
src/format.cpp, apply
Key __legacy_free__
ASan and potentially double-free analysis
Use one owning object and one cleanup path
KV-003
src/format.cpp, apply
Put then erase key __legacy_keep__
Reference-model equality oracle
Apply every validated erase operation
KV-001 can be reproduced by creating its fixture with a normal build, then
decoding the journal with the buggy recovery target:
build/kv_cli put bug-seed-db 'LEGACY:abcdefghijklmnopqrstuvwxyz' value
build-bugs/kv_fuzz_recovery bug-seed-db/data.log
build-bugs/kv_cli put demo-bug-db __legacy_free__ value
KV-003 is a logic defect, so sanitizers alone are insufficient. A direct library
case is:
The operation Fuzz harness also compares this behavior against a reference map.
Run memory-error demonstrations individually because sanitizer findings terminate
their process. Do not reuse a demonstration store for ordinary examples.
Intended Validation and Remaining Work
Planned tests cover reopen persistence, empty and repeated-key batches, atomic
rejection of invalid batches, sequence overflow, truncated tails, checksum and
length corruption, snapshot isolation, transaction conflicts, lock contention,
read-only behavior, backup/compaction equivalence, and deterministic randomized
operations against a reference map.
The unit-test file and prepared regression corpus remain to be completed. Final
compilation, tests, and the 3000–5000-line source acceptance check are pending.
The shared ../tools/count_loc.py can perform the line-count check after the
source is complete; it excludes documentation, blank lines, comments, and build
artifacts.
Mini KV Store: Static Analysis and Fuzzing Lab
A small C++17 file-backed key/value store for exploring binary record validation, log recovery, ownership, batch semantics, snapshots, and stateful fuzzing. The library uses the standard library only.
Status
The storage library, CLI, and two libFuzzer entry points are present. This is an unverified source draft. No build, test, sanitizer, static-analysis, or Fuzz result is claimed. The current CMake configuration references
tests/test_store.cpp, which has not yet been written. Add that source or remove its test target before running the build commands below. SettingBUILD_TESTING=OFFalone does not remove the unconditional test executable.Execution was stopped at the user’s request. The examples are future usage instructions, not records of completed validation.
Features
Layout
include/kv/format.hpp,src/format.cppinclude/kv/store.hpp,src/store.cppinclude/kv/query.hpp,src/query.cppinclude/kv/journal.hpp,src/journal.cppsrc/main.cppfuzz/fuzz_recovery.cppfuzz/fuzz_operations.cppKeep the shared
../cmake/ProjectOptions.cmakebeside the project. The store directory containsdata.log; a.lockdirectory represents exclusive access.Build and Basic Usage
After resolving the missing test-source item, use CMake 3.16+, a C++17 compiler, and Ninja. Linux/WSL is the intended environment for compaction and Fuzz examples.
The CLI returns 0 on success, 1 on an operation error, 2 on invalid usage, and 3 for a missing
getorerasekey.diffreturns 1 when snapshots differ. Read commands open an existing store instead of implicitly creating one.getand text output escape binary bytes rather than writing raw control characters. Backup refuses an existing destination. Compaction replaces the active journal with a checksummed snapshot while retaining its sequence number.Library Example
Batch operations execute in order; repeated keys are allowed. Empty batches do not increment the sequence. An erase of a missing key is still logged when issued through the store. A transaction reads from its own working copy and commits only if the store sequence still equals its starting sequence. A conflicting commit raises
kv::Error; rollback or create a new transaction.Text Import and Batch Commands
Export/import uses exactly two tab-separated fields per nonempty line:
<TAB>above means a literal tab. Escapes are\\,\t,\n,\r, and\xHH. Imports are one batch and replace matching keys without removing others.Batch files additionally include the command name:
Batch files accept blank lines and lines beginning with
#as comments. Import files do not interpret#as a comment. Replay cannot reconstruct history removed by compaction; sequence requests below the journal base fail.Binary Journal Format
All integers are unsigned and big-endian. The 16-byte file header contains:
MKV1Each transaction has a 24-byte header:
TXN1The payload is a sequence of operations: 1-byte kind, 4-byte key length, 4-byte value length, key bytes, and value bytes. Kind 1 is put; kind 2 is erase and must have an empty value. CRC32 covers header bytes 0–19 followed by the payload. It uses polynomial
0xEDB88320, initial state0xffffffff, and final complement. The file header itself does not have a checksum.A nonempty compacted snapshot uses one put-only transaction at the current sequence and a base sequence one lower. An empty snapshot is only a file header. Consequently, compaction is limited by the maximum operations and payload size of a single record, even when the live store could otherwise hold more entries.
Recovery, Locking, and Durability
Recovery validates sequence continuity, record lengths, operation limits, and checksums before applying each complete transaction. A partial final record may be ignored when
tolerate_tailis enabled. A complete record with a bad checksum is rejected rather than silently discarded. A writable store truncates an accepted incomplete tail before appending; a read-only store does not alter it.The lock directory is exclusive for every
Store, including read-only opens. Read-only mode therefore still requires permission to create/remove the lock directory. The library is single-threaded and does not implement shared readers or synchronization between threads.A process crash may leave
.lockbehind. Confirm that no process owns the store before manually removing a stale lock. Compaction refuses a preexistingcompact.tmp; inspect such a file before cleanup. Replacement uses filesystem rename semantics and is intended for Linux/WSL. Native Windows may reject rename over an existing destination; in that case compaction fails and retains the old journal.Writes close their output stream but do not issue
fsync, synchronize the parent directory, or promise durability across power loss. This is an educational storage engine, not a production database. Do not rely on it for valuable data.Static Analysis
Clang, CodeChecker, and compatible CTU mapping tools are separate prerequisites. Useful paths to inspect include decoding into operation records, applying a batch before journal append, cleanup after I/O failure, and snapshot replacement. Static detection of particular bugs depends on enabled checkers and the compiler.
Sanitizers and Fuzzing
After completing the build prerequisites:
Fuzz builds enable libFuzzer, ASan, and UBSan. A separate ordinary sanitizer build can use
-DENABLE_SANITIZERS=ON. Replay a saved input with the matching Fuzz executable and its filename. No campaign has been run for this draft.The recovery harness feeds arbitrary journal bytes, compares tolerant recovery with strict recovery of the accepted prefix, and checks compacted snapshots. The operation harness decodes bounded byte commands, compares
kv::applyagainst an independentstd::map, and checks record and text-format roundtrips. It does not fuzz filesystem durability or operating-system failures.Optional Demonstration Defects
Configure a separate
build-bugsdirectory with-DENABLE_DEMO_BUGS=ONand-DENABLE_FUZZING=ON. The normal CTest registration is disabled there.src/format.cpp,decode_recordLEGACY:strcpysrc/format.cpp,apply__legacy_free__src/format.cpp,apply__legacy_keep__KV-001 can be reproduced by creating its fixture with a normal build, then decoding the journal with the buggy recovery target:
KV-003 is a logic defect, so sanitizers alone are insufficient. A direct library case is:
The operation Fuzz harness also compares this behavior against a reference map. Run memory-error demonstrations individually because sanitizer findings terminate their process. Do not reuse a demonstration store for ordinary examples.
Intended Validation and Remaining Work
Planned tests cover reopen persistence, empty and repeated-key batches, atomic rejection of invalid batches, sequence overflow, truncated tails, checksum and length corruption, snapshot isolation, transaction conflicts, lock contention, read-only behavior, backup/compaction equivalence, and deterministic randomized operations against a reference map.
The unit-test file and prepared regression corpus remain to be completed. Final compilation, tests, and the 3000–5000-line source acceptance check are pending. The shared
../tools/count_loc.pycan perform the line-count check after the source is complete; it excludes documentation, blank lines, comments, and build artifacts.