Skip to main content

ConflictFreeMerger

prolly

Trait ConflictFreeMerger 

Source 
pub trait ConflictFreeMerger<S: Store> {
    // Required method
    fn crdt_merge(
        &self,
        store: &S,
        base: &Tree,
        left: &Tree,
        right: &Tree,
        config: &CrdtConfig,
    ) -> Result<Tree, Error>;
}
Expand description

Trait for conflict-free merge operations using CRDT semantics.

Unlike the standard merge which can return Error::Conflict, implementations of this trait guarantee that merges always succeed by applying deterministic resolution strategies. This makes it suitable for distributed systems where concurrent modifications are common and automatic resolution is preferred.

§CRDT Semantics

CRDT (Conflict-free Replicated Data Type) merges ensure:

  • Commutativity: merge(A, B) = merge(B, A)
  • Associativity: merge(merge(A, B), C) = merge(A, merge(B, C))
  • Idempotence: merge(A, A) = A

These properties guarantee eventual consistency in distributed systems.

§Guarantees

  • Never returns Error::Conflict: All conflicts are automatically resolved
  • Deterministic: Same inputs always produce the same output
  • Preserves non-conflicting changes: Changes to different keys are always preserved

§Type Parameters

  • S - The storage backend type implementing Store

§Example

use prolly::{Prolly, MemStore, Config, ConflictFreeMerger, DefaultConflictFreeMerger, CrdtConfig};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());

let base = prolly.create();
let base = prolly.put(&base, b"key".to_vec(), b"value".to_vec()).unwrap();

// Create divergent branches
let left = prolly.put(&base, b"key".to_vec(), b"left".to_vec()).unwrap();
let right = prolly.put(&base, b"key".to_vec(), b"right".to_vec()).unwrap();

// CRDT merge never fails
let merger = DefaultConflictFreeMerger;
let config = CrdtConfig::default();
// merged = merger.crdt_merge(&store, &base, &left, &right, &config).unwrap();

Required Methods§

Source

fn crdt_merge( &self, store: &S, base: &Tree, left: &Tree, right: &Tree, config: &CrdtConfig, ) -> Result<Tree, Error>

Merge two trees without conflicts using CRDT semantics.

Performs a three-way merge using base as the common ancestor. All conflicts are automatically resolved using the configured strategy.

§Arguments
  • store - The storage backend
  • base - The common ancestor tree
  • left - The left branch tree
  • right - The right branch tree
  • config - CRDT configuration specifying merge strategy and policies
§Returns
  • Ok(Tree) - The merged tree (never returns Error::Conflict)
  • Err(Error) - Only on storage or deserialization errors
§Conflict Resolution

When both branches modify the same key differently:

  • LWW: Value with higher timestamp wins; ties broken lexicographically
  • MV: Both values are combined into a MultiValueSet
  • Custom: User-provided function determines the result

When one branch deletes and another modifies:

  • DeleteWins: Key is absent from result
  • UpdateWins: Key is present with the updated value

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§