surrealdb/vart

A timed adaptive radix trie data-structure, used in SurrealKV

vart: Versioned Adaptive Radix Trie for Rust

vart is a Rust library that implements an immutable Versioned Adaptive Radix Trie data structure. It allows you to efficiently manage key-value pairs with multiple versions and timestamps, making it a useful datastructure for applications that require tracking changes over time and enabling snapshot reads. With vart, you can handle versioned data, insert, delete, and query key-value items based on specific versions.

Features

• Immutable: Built on an immutable radix trie data structure employing copy-on-write semantics. This design allows for the storage and retrieval of multiple versions of the same key.

• Version Tracking: Track modifications to the key and manage multiple versions of the same key within the data structure.

• Snapshot Reads: Capture the current state of the trie and create immutable snapshots, allowing for point-in-time views of the data.

vart's Issues

Range Scan doesn't produce ordered keys

The range scan does not produce keys in an ordered format. Linked to surrealkv issue. Can be seen in this test case

    #[test]
    fn range_scan_order() {
        let mut tree = Tree::<VariableKey, i32>::new();

        let insert_words = [
            "test6", "test5", "test3", "test4", "test1",
        ];
        
        let entries: Vec<KV<VariableKey, i32>> = insert_words.iter()
        .map(|word| KV {
            key: VariableKey::from_str(word).unwrap(),
            value: 1,
            version: 1,
            ts: 1,
        })
        .collect(); 

        tree.bulk_insert(&entries).unwrap();


        // Test inclusive range
        let range = VariableKey::from("test1".as_bytes().to_vec())..=VariableKey::from("test7".as_bytes().to_vec());    
        for p in tree.range(range) {
            println!("{:?}", p);
        }
    }

Address Rust String Null Byte Handling

Description:

Rust strings can freely contain null bytes. For example, "foo\0bar" is allowed in Rust and has a length of 7. Adding a null byte in Rust might result in a prefixed string.

As an alternative, consider using something like 0b10111111. All Rust strings are valid UTF-8, and a UTF-8 character can never begin with a 10-bit pattern, as this is the starting pattern of a continuation byte. Utilizing 0b10111111 in Rust strings would ensure that no byte slice derived from a string serves as a prefix for another.

Action Items:

• Evaluate the possibility of using 0b10111111 as an alternative to null bytes.

Additional Context:

This consideration aims to prevent unintended string prefixing when adding bytes in Rust. This was raised by @DelSkayn here

whether vart is thread safe and how vart is used in production?

Firstly, thanks for sharing this repo. Recently I learn about surrealdb use ART in production and created versioned ART, I am very curious about vart and have some question: is it thread safe or how vart is used in production, I can not found vart usage in surrealdb main repo

Address Rust String Null Byte Handling

          Just a note that rust strings can freely contain null bytes. `"foo\0bar"` is allowed in rust and will have a lenght of 7. So in rust adding a null byte you might still end up with a prefixed string.

Maybe instead of a null byte you could add something like 0b10111111? All rust strings are valid UTF-8 and a UTF-8 character can never begin with a 10 bit pattern as this the start pattern of a continuation byte. So for rust strings this would ensure that no byte slice derived from a string is a prefix of another.

Originally posted by @DelSkayn in surrealdb/surrealkv#5 (comment)