Canopydb: Transactional Key-Value Storage Engine

Canopydb is an embedded, transactional, ordered key-value storage engine. It is best suited for:

• Read-heavy workloads: Where reads significantly outnumber writes.
• Transactional requirements: When you need ACID guarantees but find SQLite too slow or heavy.
• Embedded scenarios: When you want to avoid managing separate database processes.

Comparison Summary:

• vs SQLite: SQLite is a full relational database with SQL support (joins, aggregations). Canopydb is a lower-level, faster, and simpler key-value store.
• vs LMDB: Canopydb is pure Rust, provides a safer API, supports concurrent write transactions, and uses an optional Write-Ahead-Log (WAL). LMDB is C-based and uses memory-mapped files.
• vs Redb: Redb offers strongly typed tables and savepoints. Canopydb focuses on a byte-oriented API and provides concurrent writes and transparent compression.
• vs RocksDB/Fjall: These use LSM Trees, which are better for extreme random write performance and write-heavy workloads, but may have higher CPU/memory overhead.

Canopydb is a transactional embedded key-value store with the following core characteristics:

Concurrency Model

• MVCC (Multi-Version Concurrency Control): Enables lock-free reads. Read transactions never block writers or other readers.
• OCC (Optimistic Concurrency Control): Enables concurrent writes via Snapshot Isolation (SI).

Storage & Performance

• Ordered Map API: Efficient range queries, prefix scans, ordered iteration, and range deletes (similar to BTreeMap).
• Compact B+Tree: Uses transparent key compression via prefix/suffix truncation.
• Write-Ahead Log (WAL): Optional WAL for efficient durable commits, including support for async durability (background fsyncs).
• Memory Efficiency: Supports transactions larger than available memory.

Data Organization

• Keyspaces (Trees): Multiple trees per database, all fully transactional.
• Environments: Multiple databases can reside in one environment, sharing resources like the WAL and page cache, allowing for atomic cross-database commits.

Canopydb provides an ordered map API similar to std::collections::BTreeMap. You can perform basic Create, Read, Update, and Delete operations using write transactions. A single database can contain multiple trees (keyspaces) which are fully transactional.

Key operations:

• Database::new(path): Initializes a new database at the given path.
• db.begin_write(): Starts a write transaction.
• tx.get_or_create_tree(name): Accesses or creates a specific keyspace.
• tree.insert(key, value): Inserts a key-value pair.
• tree.get(key): Retrieves a value.
• tx.commit(): Persists changes.
• db.begin_read(): Starts a read-only transaction.
• tree.range(start..end): Performs range queries.
• tree.iter(): Performs a full scan.

let _dir = tempfile::tempdir().unwrap();
let db = canopydb::Database::new(_dir.path()).unwrap();

// Write transaction
let tx = db.begin_write().unwrap();
{
    let mut tree1 = tx.get_or_create_tree(b"tree1").unwrap();
    tree1.insert(b"foo", b"bar").unwrap();
    
    // Read within the same transaction
    let maybe_value = tree1.get(b"foo").unwrap();
    assert_eq!(maybe_value.as_deref(), Some(&b"bar"[..]));
}
tx.commit().unwrap();

// Read transaction
let rx = db.begin_read().unwrap();
let tree = rx.get_tree(b"tree1").unwrap().unwrap();
let maybe_value = tree.get(b"foo").unwrap();
assert_eq!(maybe_value.as_deref(), Some(&b"bar"[..]));

// Range iteration
for kv_pair_result in tree.range(&b"foo"[..]..).unwrap() {
    let (db_k, db_v) = kv_pair_result.unwrap();
    println!("{db_k:?} => {db_v:?}");
}

Canopydb allows you to manage multiple databases within a single Environment. This enables atomic commits across different databases, ensuring that changes to multiple databases either all succeed or all fail together, establishing a consistent state between them.

To use this:

1. Create an Environment using canopydb::Environment::new(path).
2. Retrieve or create databases within that environment using env.get_or_create_database(name).
3. Start write transactions for each database (db.begin_write()).
4. Use env.group_commit([tx1, tx2, ...], false) to commit the transactions atomically.

Note: All databases in the same environment share resources like the page cache and WAL. You can configure these via canopydb::EnvOptions before creating the environment.

let _dir = tempfile::tempdir().unwrap();
let mut options = canopydb::EnvOptions::new(_dir.path());
options.page_cache_size = 1024 * 1024 * 1024; // 1GB cache

let env = canopydb::Environment::new(_dir.path()).unwrap();
let db1 = env.get_or_create_database("db1").unwrap();
let db2 = env.get_or_create_database("db2").unwrap();

let tx1 = db1.begin_write().unwrap();
let tx2 = db2.begin_write().unwrap();

// ... perform operations on tx1 and tx2 ...

// Commit both databases atomically
env.group_commit([tx1, tx2], false).unwrap();

Canopydb uses Multi-Version-Concurrency-Control (MVCC) via Copy-On-Write (COW) to provide consistent snapshots and efficient mutations.

Transaction Types

• ReadTransaction: Read-only transactions that provide consistent snapshots of the database.
• WriteTransaction: Can mutate data and read its own changes. Changes are only visible to others after calling .commit(). Dropping the transaction performs a rollback.

Write Transaction Modes

• Exclusive Write Transactions: Only one can be active at a time. They are simpler and do not return Error::WriteConflict on commit.
• Concurrent Write Transactions: Multiple write transactions can run simultaneously. Conflict detection happens at commit time. If a conflict is detected, .commit() returns Error::WriteConflict, and the application should retry the transaction. Note that conflicts are detected at the page level, so unrelated keys in the same leaf page might trigger a 'false' conflict.

// Example of a concurrent write transaction with retry logic
loop {
    let mut tx = db.begin_write_concurrent()?;
    // ... perform operations on tx ...
    
    match tx.commit() {
        Ok(_) => break,
        Err(Error::WriteConflict) => continue, // Retry on conflict
        Err(e) => return Err(e),
    }
}

A checkpoint in Canopydb is the process of moving dirty pages from memory to the persistent storage and updating the database's Metapage.

The Checkpoint Lifecycle:

1. Collection: The system identifies dirty pages that have been modified since the last snapshot_tx_id.
2. Reservation: Space is reserved in the database file to accommodate new pages, compressed pages, and freelists.
3. Writing: Pages are written to disk. If a page is compressed, it is transformed using LZ4 before being written.
4. Syncing: The system performs an fsync on the WAL and the data file to ensure durability, then writes the new Metapage.
5. Cleanup: Once the checkpoint is successful, old snapshots that are no longer needed by any active transaction are released, and their associated free space is merged back into the allocator.

Memory Pressure Handling: When a checkpoint is triggered by CheckpointReason::MemoryPressure, the engine switches from a 'minimal' checkpoint (only pages since the last snapshot) to a 'full' checkpoint (all committed dirty pages) to aggressively reclaim memory.