DOCSEARCHbyAlgolia
Submit Docs

SurrealKV Documentation

repository·main·Indexed 17 days ago

https://github.com/surrealdb/surrealkv

A low-level, versioned, embedded, ACID-compliant key-value database for Rust built on an LSM (Log-Structured Merge) tree architecture. It provides snapshot isolation, time-travel capabilities, and point-in-time reads, specifically optimized for use within SurrealDB. Features include configurable compression per LSM level, a Value Log (VLog) for large values, and support for database checkpoints for backup and recovery.

Tokens
13.1K
Snippets
37
Records
54
Agent score
69%

What's inside surrealkv

  1. Understand the LSM Tree architecture in SurrealKV

    main

    SurrealKV has transitioned from a VART-based (Versioned Adaptive Radix Trie) architecture to an LSM (Log-Structured Merge) tree architecture.

    Key differences and benefits of the LSM Tree design:

    • Scalability: Unlike the previous VART design, which required the entire index to reside in memory, the LSM tree supports datasets much larger than available RAM.
    • Compaction: Uses a leveled compaction strategy (score-based) for efficient space utilization.
    • Reduced Overhead: Avoids the high recovery overhead of scanning all log segments to rebuild an in-memory index on startup.

  2. How Time-Travel Queries work

    main

    Time-travel queries allow you to access data as it existed at a specific timestamp.

    1. Enable Versioning: Use with_versioning(true, retention_ns) during setup.
    2. Write with Timestamps: Use txn.set_at(key, value, timestamp) to insert data at a specific point in time.
    3. Point-in-Time Reads: Use txn.get_at(key, timestamp) to retrieve the value associated with that key at that specific time.
    4. Historical Iteration: Use the history(start, end) or history_with_options(start, end, options) API to stream all versions of keys in a range. This includes tombstones (deletions) if configured via HistoryOptions.
    // Writing versioned data
let mut tx = tree.begin()?;
tx.set_at(b"key1", b"value_v1", 100)?;
tx.commit().await?;

// Point-in-time read
let tx = tree.begin()?;
let value = tx.get_at(b"key1", 100)?;

// Retrieving history
let mut iter = tx.history(b"key1", b"key2")?;
iter.seek_first()?;
while iter.valid() {
    let timestamp = iter.timestamp();
    if iter.is_tombstone() {
        println!("Deleted at {}", timestamp);
    } else {
        println!("Value: {:?} at {}", iter.value()?, timestamp);
    }
    iter.next()?;
}

  3. Quick Start with SurrealKV

    main

    To get started with SurrealKV, use TreeBuilder to initialize a new LSM tree and tree.begin() to start a transaction. Transactions are committed asynchronously using .commit().await.

    use surrealkv::{Tree, TreeBuilder};

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create a new LSM tree using TreeBuilder
    let tree = TreeBuilder::new()
        .with_path("path/to/db".into())
        .build()?;

    // Start a read-write transaction
    let mut txn = tree.begin()?;

    // Set some key-value pairs
    txn.set(b"hello", b"world")?;

    // Commit the transaction (async)
    txn.commit().await?;

    Ok(())
}

  4. Create database checkpoints for backup and recovery

    main

    You can create consistent point-in-time snapshots of your database using create_checkpoint. A checkpoint includes all SSTables, current WAL segments, the level manifest, VLog directories (if enabled), and checkpoint metadata.

    Use tree.create_checkpoint(checkpoint_dir) to generate a snapshot. This returns a metadata object containing the timestamp, sequence number, SSTable count, and total size.

    let checkpoint_dir = "path/to/checkpoint";
let metadata = tree.create_checkpoint(&checkpoint_dir)?;

println!("Checkpoint created at timestamp: {}", metadata.timestamp);
println!("Sequence number: {}", metadata.sequence_number);
println!("SSTable count: {}", metadata.sstable_count);
println!("Total size: {} bytes", metadata.total_size);

  5. Configure Basic LSM Tree Settings

    main

    Use TreeBuilder to configure the fundamental parameters of the LSM tree:

    • with_path(path): The directory where SSTables and WAL files are stored.
    • with_max_memtable_size(size): Threshold in bytes for flushing the memtable to an SSTable.
    • with_block_size(size): Size of data blocks in SSTables (affects read performance).
    • with_level_count(count): The number of levels in the LSM tree structure.
    use surrealkv::TreeBuilder;

let tree = TreeBuilder::new()
    .with_path("path/to/db".into())           // Database directory path
    .with_max_memtable_size(100 * 1024 * 1024) // 100MB memtable size
    .with_block_size(4096)                    // 4KB block size
    .with_level_count(7)                      // Number of levels in LSM tree
    .build()?;

  6. Restore a database from a checkpoint

    main

    To recover a database to a specific state, use restore_from_checkpoint.

    Warning: Restoring from a checkpoint discards any pending writes in the active memtable and any data written after the checkpoint was created. The database will return to the exact state it was in when the checkpoint was taken.

    // Restore database to checkpoint state
tree.restore_from_checkpoint(&checkpoint_dir)?;

  7. How HistoryIterator works for point-in-time reads

    main

    A HistoryIterator is a streaming iterator used to traverse versioned data in SurrealKV. It allows for point-in-time reads by filtering entries based on a snapshot_seq_num.

    Key Behaviors:

    • Forward Iteration (Streaming): Iterates through keys in ascending order. It uses a streaming approach to avoid loading all data into memory. It applies several visibility rules:
      • Sequence Number: Only entries with seq_num <= snapshot_seq_num are visible.
      • Barriers: It respects HARD_DELETE and REPLACE markers. A HARD_DELETE as the latest version for a key causes the entire key to be skipped. A REPLACE marker acts as a barrier where older versions are skipped.
      • Tombstones: If include_tombstones is false, soft deletes (tombstones) are filtered out.
    • Backward Iteration (Buffered): Iterates through keys in descending order. Because of how LSM-trees are structured, backward iteration is buffered. The iterator collects all visible versions of a single user_key into a buffer, applies filtering (barriers and tombstones), and then yields them in ascending order (oldest to newest) before moving to the previous key.
    • Filtering: Supports lower_bound, upper_bound, and ts_range (timestamp range) to restrict the scan.

  8. How TransactionHistoryIterator provides RYOW semantics

    main

    The TransactionHistoryIterator is a merge iterator designed to provide RYOW (Read Your Own Writes) semantics within a transaction. It achieves this by merging two distinct data sources:

    1. Snapshot: Committed data stored in the LSM tree, containing all historical versions.
    2. Write-set: Uncommitted writes belonging to the current transaction (pending changes).

    By overlaying the write-set on top of the snapshot, the iterator ensures that a transaction can see its own uncommitted writes as if they were already committed. When a key and timestamp exist in both sources, the write-set entry takes precedence.

    Data Model

    Each entry in the merged stream consists of (key, timestamp, value):

    • Key: The user-provided key.
    • Timestamp: The version number (higher values indicate newer versions).
    • Value: The data associated with the key, or a tombstone marker for soft deletes.

    Ordering Logic

    Iteration order depends on the direction:

    • Forward iteration (seek_first, next):
      • Primary: key ASC (e.g., a < b < c)
      • Secondary: timestamp DESC (newer versions appear before older ones)
    • Backward iteration (seek_last, prev):
      • Primary: key DESC (e.g., c > b > a)
      • Secondary: timestamp ASC (older versions appear before newer ones)
    Snapshot (committed):          Write-set (transaction):
┌─────────┬────┬───────┐       ┌─────────┬────┬───────┐
│ Key     │ TS │ Value │       │ Key     │ TS │ Value │
├─────────┼────┼───────┤       ├─────────┼────┼───────┤
│ "a"     │ 50 │ "v1"  │       │ "b"     │ 80 │ "v4"  │
│ "a"     │ 30 │ "v0"  │       └─────────┴────┴───────┘
│ "c"     │ 40 │ "v2"  │
└─────────┴────┴───────┘

Forward iteration produces:
  ("a",50) ← snap wins, "a" < "b"
  ("a",30) ← snap wins, "a" < "b"
  ("b",80) ← write-set wins, "b" < "c"
  ("c",40) ← snap (write-set exhausted)

  9. Understand InternalKey and InternalKeyRef

    main

    SurrealKV uses an internal key format to manage metadata alongside user keys.

    • InternalKey: An owned representation containing the user_key, timestamp (nanoseconds since epoch), and a trailer (which encodes the sequence number and the InternalKeyKind).
    • InternalKeyRef: A zero-copy reference to an encoded internal key. It is used by iterators to provide access to key components without allocating new memory.

    InternalKeyKind values:

    • Delete, SoftDelete, Set, Merge, LogData, RangeDelete, Replace, Separator, Max.

  10. How the MergingIterator works

    main

    The MergingIterator is a K-way merge iterator used to traverse multiple sorted runs (from different LSM levels or files) as a single continuous stream. It uses a binary heap to efficiently pick the next key.

    Key Features:

    • Tiebreaking: When keys are identical, the iterator uses level_idx as a tiebreaker. A lower level_idx indicates newer data (higher priority), ensuring newer data shadows older data.
    • Direction Switching: The iterator supports both Forward and Backward iteration. Switching directions (e.g., from next() to prev()) involves clearing the current heap, seeking all child iterators to the target position, and rebuilding the appropriate heap (min_heap for forward, max_heap for backward).
    • Complexity: Advancing the iterator is an $O(\log K)$ operation, where $K$ is the number of child iterators.

  11. Configure Versioning and Time-Travel Queries

    main

    To enable point-in-time reads, you must enable versioning.

    Important Requirements:

    • Versioning requires the Value Log (VLog) to be enabled. Calling with_versioning(true, ...) automatically enables VLog.
    • Out-of-order timestamps: If you need to insert historical data with timestamps earlier than existing ones, you must enable the B+tree versioned index using .with_versioned_index(true). Without this, the LSM tree (which orders by key ascending and sequence descending) will not read earlier timestamps correctly.

    Options:

    • with_versioning(enabled, retention_ns): Enables versioning. retention_ns = 0 means no retention limit.
    use surrealkv::{Options, TreeBuilder};

let opts = Options::new()
    .with_path("path/to/db".into())
    .with_versioning(true, 0);  // Enable versioning, retention_ns = 0 means no limit

let tree = TreeBuilder::with_options(opts).build()?;

  12. How snapshot visibility works in compaction

    main

    SurrealKV uses SnapshotVisibility to determine if a version of a key must be preserved for active snapshots or can be garbage collected during compaction.

    There are three visibility states:

    • BoundedBySnapshot(u64): The version is visible to all snapshots with a sequence number greater than or equal to the contained value. This value represents the earliest snapshot that can see this version. Versions in the same visibility boundary can be deduplicated, where the newer version supersedes the older one.
    • NoActiveSnapshots: No snapshots are currently active. Visibility is determined solely by retention rules (e.g., versioning settings).
    • NewerThanAllSnapshots: The version was written after all currently active snapshots were created. It is not visible to any existing snapshot and can be dropped if a newer version exists in the same boundary.

    Visibility Boundary Example: If snapshots exist at sequence numbers 50 and 150:

    • A version with seq=30 is BoundedBySnapshot(50).
    • A version with seq=80 is BoundedBySnapshot(150).
    • A version with seq=120 is BoundedBySnapshot(150).
    • A version with seq=200 is NewerThanAllSnapshots.

    Because seq=80 and seq=120 both fall into the BoundedBySnapshot(150) boundary, the older version (seq=80) can be safely dropped during compaction in favor of the newer one.