redb

redb uses Multi-Version Concurrency Control (MVCC) built on a copy-on-write B+tree to isolate transactions.

Transaction Isolation

• Read Transactions: Create a private copy of the B+tree root. Pages referenced by this root are protected from being freed until the transaction completes.
• Write Transactions: Use copy-on-write for committed pages. Modifications result in new page allocations rather than in-place updates. Dirty pages (allocated within the current transaction) can be modified in-place.

Savepoints

Savepoints allow you to capture a snapshot of the database and rollback to it. They are implemented using the same MVCC structures as transactions.

There are two types of savepoints:

1. Ephemeral: Automatically deallocated when dropped. They do not persist across restarts.
2. Persistent: Stored in a table within the system table tree and persist across restarts. These must be explicitly deallocated to avoid resource leaks.

redb is a high-performance, ACID-compliant, embedded key-value store written in pure Rust. It uses copy-on-write B+trees and supports MVCC for concurrent readers and writers without blocking.

To use redb, you typically:

1. Define a TableDefinition with specific key and value types.
2. Create a Database instance pointing to a file.
3. Start a write transaction using db.begin_write() to modify data.
4. Start a read transaction using db.begin_read() to access data.
5. Commit write transactions using .commit() to persist changes.

use redb::{Database, Error, ReadableDatabase, TableDefinition};

const TABLE: TableDefinition<&str, u64> = TableDefinition::new("my_data");

fn main() -> Result<(), Error> {
    let db = Database::create("my_db.redb")?;
    let write_txn = db.begin_write()?;
    {
        let mut table = write_txn.open_table(TABLE)?;
        table.insert("my_key", &123)?;
    }
    write_txn.commit()?;

    let read_txn = db.begin_read()?;
    let table = read_txn.open_table(TABLE)?;
    assert_eq!(table.get("my_key")?.unwrap().value(), 123);

    Ok()
}

If a database experiences an unclean shutdown, it may require repair to ensure consistency between the super-header and the allocator state.

Quick Repair

If the last commit had quick-repair enabled, the primary commit slot is guaranteed to be valid via a 2-phase commit, and the allocator state is stored in the allocator state table. This makes repair trivial.

Full Repair

If quick-repair is not available, a full repair is required:

1. Update Super-header: If the primary commit slot is invalid, switch to the secondary slot to reference the last fully committed transaction.
2. Rebuild Allocator State: Rebuild the state by walking the following trees and marking all referenced pages as allocated:
   • data tree
   • system tree
   • freed tree (including all pending free pages contained within)

Note: All pages referenced by a savepoint must be accounted for in this process, as they are either committed pages or pages in a pending free state within the freed tree.

redb provides different commit strategies depending on your requirements for durability and security:

Non-durable commits

• Behavior: No guarantee of durability in the event of a crash.
• Consistency: The database is still guaranteed to be consistent and will roll back to either the last non-durable commit or the last full commit.
• Use Case: High-performance scenarios where losing the most recent transaction is acceptable.

1-phase + checksum durable commits (1PC+C)

• Behavior: The default strategy. Uses a single fsync.
• Mechanism: Writes data, checksums, and a transaction ID, then flips the primary page and calls fsync.
• Recovery: If a crash occurs, redb verifies the transaction ID and checksums. If invalid, it rolls back to the secondary page.
• Security Note: Uses non-cryptographic XXH3 checksums. Theoretically vulnerable to attackers who can control disk flush order and crash timing to forge valid checksums for partial writes.

2-phase durable commits (2PC)

• Behavior: Mitigates theoretical attacks involving malicious data and high control over the process.
• Mechanism:
  1. Write data to a new B+tree copy.
  2. Perform fsync.
  3. Flip the primary byte.
  4. Perform a second fsync.
• Use Case: Required when accepting potentially malicious input where checksum collision resistance is a concern.

The database uses two 128-byte 'commit slots' (slot 0 and slot 1) for atomic commits. The god byte toggles between them. Each slot follows this layout:

The database header (64 bytes) contains immutable configuration and state information. It is part of the 512-byte super-header.