ImmuKV

An embedded immutable key-value database with cryptographic proofs of inclusion and history.

Overview

ImmuKV is a persistent key-value store where data is append-only: every write keeps the previous value reachable on disk and contributes to a per-key chain of cryptographic hashes anchored in a Merkle root over a radix trie. This makes it possible to prove, to a third party, both the current value of a key and the full sequence of past values, with no way to silently omit an intermediate version.

Features

• Immutable history: Every value ever written stays on disk and is retrievable by version.
• Per-key hash chain: Each record stores prevHash, so omitting an intermediate version is detectable.
• Merkle root over a radix trie: A single SHA-256 root commits to all keys and their current values.
• Path-compressed index: radix nodes use variable-length edge labels (whole key segments) by default, so sparse keys with long shared prefixes stay shallow; nodes transparently fall back to a dense single-byte encoding when they grow too full. The root hash is identical either way.
• Inclusion proofs: Prove(key) returns a verifiable proof that the key resolves to its current value under the root.
• History proofs: ProveHistory(key, fromVersion) returns a Merkle-anchored proof of all versions of a key from fromVersion to the current one.
• Point-in-time reads: GetAt(key, version), NewRangeIteratorAt, and NewPrefixIteratorAt return the value (or iterate the keyspace) as it stood at the end of any past transaction.
• ACID transactions with commit / rollback.
• Write-Ahead Logging (WAL) for crash recovery.
• Concurrent access: one writer plus multiple readers.

Architecture

An ImmuKV database is made of:

1. Main file — append-only log of all key/value records. Each record carries the previous version's hash.
2. Index file — radix trie (radix pages + leaf pages) mapping keys to the latest record offset. Radix nodes are stored in one of two interchangeable encodings: a variable-length ('V') form whose edges carry whole key segments (the default — path compression), and a dense single-byte ('S') form used as the overflow fallback for nodes that grow too full. A node hashes the same in either form, so promotion, splitting, and 'V'→'S' demotion never change the Merkle root. Point-in-time reads reconstruct 'V' nodes at past versions from compact, pointer-free structural history records (see architecture-notes.md §6a).
3. WAL file — flushed index pages, for durability.
4. Hash sidecar file (-index-hashes) — per-sub-page Merkle material (radix: sparse child hashes; leaf: dense per-entry hData lists) in a variable-size chunk allocator, plus hash metadata in the sidecar header. Leaf hashes are pinned per page-cache snapshot so readers on older index versions do not follow freed chunk offsets (see architecture-notes.md §5).
5. Index history file (-index-history) — single append-only log of per-sub-page changes (radix and leaf) that allows reconstructing any prior version for historical proofs.

Why keys and values are never deleted

ImmuKV has no Delete API: nothing on disk is ever removed. Calling Set(key, nil) only appends a new record with an empty value, chained to the previous version. Get then returns an empty value (no "not found" error) for that key, while GetChanges and ProveHistory still expose every prior version.

Usage

Basic operations

// Open or create a database
db, err := immukv.Open("path/to/database")
if err != nil {
    // Handle error
}
defer db.Close()

// Set a key-value pair
err = db.Set([]byte("key"), []byte("value"))

// Get a value
value, err := db.Get([]byte("key"))

// Overwrite the key's value with nil; the previous value stays in history.
// There is no Delete: keys and values cannot be removed from the database.
err = db.Set([]byte("key"), nil)

Transactions

// Begin a transaction
tx, err := db.Begin()
if err != nil {
    // Handle error
}

// Perform operations within the transaction
err = tx.Set([]byte("key1"), []byte("value1"))
err = tx.Set([]byte("key2"), []byte("value2"))

// Commit or rollback
if everythingOk {
    err = tx.Commit()
} else {
    err = tx.Rollback()
}

Proofs

// Current Merkle root over the radix trie
root := db.RootHash()

// Inclusion proof for the current value of a key (returned as bytes,
// ready to ship over the wire)
proof, err := db.Prove([]byte("key"))
err = immukv.VerifyProof(proof, root)

// History proof: every version from `fromVersion` up to the current one,
// chained by per-version hashes and anchored at `root`
hp, err := db.ProveHistory([]byte("key"), fromVersion)
err = immukv.VerifyHistoryProof(hp, root)

// Callers that want to read fields out of a proof (Value, Version,
// PrevHash, …) can decode it explicitly:
//   p, _ := immukv.ParseProof(proof)
//   _ = p.Value

// Merkle root at an older version
oldRoot, err := db.RootHashAt(version)

History without proofs

// Iterate every past version of a key
changes, err := db.GetChanges([]byte("key"), 0, 0, immukv.OldestFirst)
for _, c := range changes {
    // c.Version, c.Value
}

Iteration

// Full keyspace (forward)
it := db.NewRangeIterator(nil, nil, false)

// Key range [start, end): start inclusive, end exclusive
it = db.NewRangeIterator([]byte("a"), []byte("c"), false)

// All keys with a given prefix
it = db.NewPrefixIterator([]byte("user:"), false)

defer it.Close()
for ; it.Valid(); it.Next() {
    // it.Key(), it.Value()
}

Point-in-time reads

// Value of a key at a historical version
oldValue, err := db.GetAt([]byte("key"), version)

// Iterate the keyspace as it stood at a historical version. Range and
// direction semantics match NewRangeIterator: forward iteration uses
// [start, end) with start inclusive and end exclusive; reverse uses
// (end, start] with start as the inclusive upper bound.
rangeIt, err := db.NewRangeIteratorAt(nil, nil, false, version)
defer rangeIt.Close()
for ; rangeIt.Valid(); rangeIt.Next() {
    // rangeIt.Key(), rangeIt.Value()
}

// Iterate all keys with a given prefix at a historical version
prefixIt, err := db.NewPrefixIteratorAt([]byte("user:"), false, version)
defer prefixIt.Close()
for ; prefixIt.Valid(); prefixIt.Next() {
    // prefixIt.Key(), prefixIt.Value()
}

Configuration

options := immukv.Options{
    "ReadOnly":            true,                // Open in read-only mode
    "CacheSizeThreshold":  10000,               // Maximum number of pages in cache
    "DirtyPageThreshold":  5000,                // Maximum dirty pages before flush
    "CheckpointThreshold": 1024 * 1024,         // WAL size before checkpoint (1 MB)
}

db, err := immukv.Open("path/to/database", options)

Limits

• Keys: up to 2 KB
• Values: up to 128 MB
• Page size: 4 KB

Recovery

On open, ImmuKV reads the main file header, validates the index/WAL, scans for commit markers in the main file, and rebuilds the index and hash sidecar files when needed. Historical queries (RootHashAt, ProveAt, GetAt, …) load Merkle hashes from the append-only -index-history log rather than recomputing them from the live index; full hash recomputation runs only when sidecar files are missing, corrupt, or stale (RebuildHashes).

Concurrency

Single writer, multiple readers per database file. Only one process can open the database for writing at a time.

License

Apache 2.0