DSON

DSON is a low-level library providing core data structures and algorithms for delta-state CRDTs.

Key constraints for developers:

• No Networking: The crate does not include any networking protocols. You are responsible for implementing the transport layer (e.g., WebSockets, P2P, etc.) to broadcast deltas between replicas.
• Abstraction Layer: Because it is low-level, users are encouraged to build a typed abstraction layer on top of the provided primitives for their specific use cases.

DSON is built from three fundamental, composable CRDT (Conflict-Free Replicated Datatype) primitives that can be nested to create complex, JSON-like data structures:

• OrMap: An Observed-Remove Map that maps string keys to other CRDT values.
• OrArray: An Observed-Remove Array providing a list-like structure.
• MvReg: A Multi-Value Register used for storing primitive values. In the event of concurrent writes, the register holds all conflicting values.

All modifications to these structures produce a delta, which is a compact set of changes designed to be transmitted efficiently to other replicas.

DSON utilizes Observed-Remove (OR) semantics for its maps and arrays. Under this model:

1. An element can only be removed if its addition has been previously observed.
2. If an element is updated concurrently with its removal, the update wins and the element is preserved.

This approach, combined with DSON's causal history model, allows for tombstone-free removals, preventing the unbounded metadata growth typically seen in long-lived documents in other CRDT implementations.

The repository includes two benchmark harnesses for performance testing.

Tango (Regression Testing)

Used for paired-testing to detect performance regressions.

# Establish baseline
cargo bench --bench tango

# After making changes, compare against baseline
cargo bench --bench tango -- compare

# Filter specific benchmarks
cargo bench --bench tango -- compare -f "transaction::map::*"

# Quick absolute timings (non-comparative mode)
cargo bench --bench tango -- solo -f "transaction::map::*" -s 100

IAI-Callgrind (Instruction-level Profiling)

Requires Linux and Valgrind. Provides instruction-level profiling.

# Run IAI benchmarks
cargo bench --bench iai
cargo bench --bench nested_transactions

The CollapsedValue enum provides an ergonomic, read-only view of a CRDT that assumes no conflicts exist. If a conflict is encountered during the snapshot process, an error is returned.

Variants:

• Register(&'doc MvRegValue): A single value from a register.
• Map(OrMap<'doc, String, CollapsedValue<'doc, Custom>>): An observed-remove map.
• Array(OrArray<CollapsedValue<'doc, Custom>>): An observed-remove array.
• Custom(Custom::Value): A custom CRDT type's single value.

// CollapsedValue is used when you want a 'normal' data view
match collapsed_snapshot {
    CollapsedValue::Register(val) => { /* val is a single MvRegValue */ }
    CollapsedValue::Map(map) => { /* access map */ }
    // ...
}

Sentinels are types used to inspect, observe, or validate changes being applied to a CRDT. They are primarily used for schema validation, logging, or collecting metrics during document mutations (such as during a DotStoreJoin::join).

There are two main categories of Sentinels based on their error handling:

• Observers: Sentinels where Error = Infallible. They only observe changes and cannot stop a mutation.
• Validators: Sentinels that can return an Err. They can stop a change from being applied if it violates a rule.

To effectively track where in the document tree a change is occurring, a Sentinel should implement the Visit<K> trait alongside other specialized traits. This allows the Sentinel to maintain an internal pointer to the current node by responding to traversal events.

The AllValues enum is a read-only representation of a CRDT that preserves all concurrent values in multi-value registers. It mirrors the structure of the actual CRDTs but cannot be modified.

Variants:

• Register(MvReg<'doc>): A multi-value register containing all concurrent values.
• Map(OrMap<'doc, String, AllValues<'doc, Custom>>): An observed-remove map.
• Array(OrArray<AllValues<'doc, Custom>>): An observed-remove array.
• Custom(Custom::Values): A custom CRDT type's values.

// AllValues is an enum representing the full state including conflicts
match all_values_snapshot {
    AllValues::Register(mvreg) => {
        for val in mvreg.iter() { /* handle multiple values */ }
    }
    AllValues::Map(map) => { /* access map keys/values */ }
    // ...
}

The OrArray follows Observed-Remove semantics. This means that updates (like apply) that are concurrent with a delete or clear operation may still persist.

Specifically, if a user performs an update on an element that another user concurrently deletes, the update is not 'observed' by the delete operation. When the states are joined, the update can survive, potentially resulting in an array that contains the updated element even though a delete was issued. This is visible in the nested_update_vs_remove test case where an update to a nested map survives an outer array deletion.

Because ArrayTransaction applies changes eagerly to its internal working_store, you can read back values you have just inserted within the same transaction using .get(idx).

let mut tx = ArrayTransaction::new(&mut store, id);

// Insert a value
tx.insert_register(0, MvRegValue::String("hello".to_string()));

// Read the value back immediately (before commit)
match tx.get(0) {
    Some(CrdtValue::Register(reg)) => {
        // This will succeed and contain "hello"
    }
    _ => {}
}

let delta = tx.commit();