Struct CRDT 

pub struct CRDT<K: Ord + Hash + Eq + Clone, C: Hash + Eq + Clone, V: Clone> { /* private fields */ }

Main CRDT structure, generic over key (K), column (C), and value (V) types.

This implements a column-based CRDT with last-write-wins semantics.

Sorted Keys Feature

When the sorted-keys feature is enabled, the internal storage uses BTreeMap instead of HashMap, enabling ordered iteration and range queries at the cost of O(log n) operations instead of O(1).

Type Requirements

K (record key) must implement Ord + Hash + Eq + Clone:

• Ord is required for potential use with sorted-keys feature (BTreeMap)
• Even without sorted-keys, requiring Ord keeps the API consistent and enables seamless feature toggling. Most common types (String, u64, etc.) already implement Ord.
• This is consistent with PersistedCRDT which also requires K: Ord for serialization.

Implementations

impl<K: Ord + Hash + Eq + Clone, C: Hash + Eq + Clone, V: Clone> CRDT<K, C, V>

pub fn new(node_id: NodeId, parent: Option<Arc<CRDT<K, C, V>>>) -> Self

Creates a new empty CRDT.

Arguments

• node_id - Unique identifier for this CRDT node
• parent - Optional parent CRDT for hierarchical structures

pub fn from_changes(node_id: NodeId, changes: Vec<Change<K, C, V>>) -> Self

Creates a CRDT from a list of changes (e.g., loaded from disk).

Arguments

• node_id - The unique identifier for this CRDT node
• changes - A list of changes to apply to reconstruct the CRDT state

pub fn reset(&mut self, changes: Vec<Change<K, C, V>>)

Resets the CRDT to a state as if it was constructed with the given changes.

Arguments

• changes - A list of changes to apply to reconstruct the CRDT state

pub fn insert_or_update<I>( &mut self, record_id: &K, fields: I, ) -> Vec<Change<K, C, V>>

where I: IntoIterator<Item = (C, V)>,

Inserts a new record or updates an existing record in the CRDT.

Arguments

• record_id - The unique identifier for the record
• fields - An iterator of (column_name, value) pairs

Returns

A vector of changes created by this operation

pub fn insert_or_update_with_flags<I>( &mut self, record_id: &K, flags: u32, fields: I, ) -> Vec<Change<K, C, V>>

where I: IntoIterator<Item = (C, V)>,

Inserts a new record or updates an existing record with flags.

Arguments

• record_id - The unique identifier for the record
• flags - Flags to indicate the type of change
• fields - An iterator of (column_name, value) pairs

Returns

A vector of changes created by this operation

pub fn delete_record(&mut self, record_id: &K) -> Option<Change<K, C, V>>

Deletes a record by marking it as tombstoned.

Arguments

• record_id - The unique identifier for the record

Returns

An optional Change representing the deletion

pub fn delete_record_with_flags( &mut self, record_id: &K, flags: u32, ) -> Option<Change<K, C, V>>

Deletes a record with flags.

Arguments

• record_id - The unique identifier for the record
• flags - Flags to indicate the type of change

Returns

An optional Change representing the deletion

pub fn delete_field( &mut self, record_id: &K, field_name: &C, ) -> Option<Change<K, C, V>>

Deletes a specific field from a record.

Arguments

• record_id - The unique identifier for the record
• field_name - The name of the field to delete

Returns

An optional Change representing the field deletion. Returns None if:

• The record is tombstoned
• The record doesn’t exist
• The field doesn’t exist in the record

pub fn delete_field_with_flags( &mut self, record_id: &K, field_name: &C, flags: u32, ) -> Option<Change<K, C, V>>

Deletes a specific field from a record with flags.

Arguments

• record_id - The unique identifier for the record
• field_name - The name of the field to delete
• flags - Flags to indicate the type of change

Returns

An optional Change representing the field deletion. Returns None if:

• The record is tombstoned
• The record doesn’t exist
• The field doesn’t exist in the record

pub fn merge_changes<R: MergeRule<K, C, V>>( &mut self, changes: Vec<Change<K, C, V>>, merge_rule: &R, ) -> Vec<Change<K, C, V>>

Merges incoming changes into the CRDT.

Arguments

• changes - Vector of changes to merge
• merge_rule - The merge rule to use for conflict resolution

Returns

Vector of accepted changes (if requested)

pub fn get_changes_since(&self, last_db_version: u64) -> Vec<Change<K, C, V>>

where K: Ord, C: Ord,

Retrieves all changes since a given last_db_version.

Arguments

• last_db_version - The database version to retrieve changes since

Returns

A vector of changes

pub fn get_changes_since_excluding( &self, last_db_version: u64, excluding: &HashSet<NodeId>, ) -> Vec<Change<K, C, V>>

where K: Ord, C: Ord,

Retrieves all changes since a given last_db_version, excluding specific nodes.

pub fn compress_changes(changes: &mut Vec<Change<K, C, V>>)

where K: Ord, C: Ord,

Compresses a vector of changes in-place by removing redundant changes.

Changes are sorted and then compressed using a two-pointer technique.

Performance

This method uses sort_unstable_by which provides O(n log n) average time complexity but does not preserve the relative order of equal elements. Since the comparator provides a total ordering, stability is not required.

pub fn get_record(&self, record_id: &K) -> Option<&Record<C, V>>

Retrieves a reference to a record if it exists.

pub fn is_tombstoned(&self, record_id: &K) -> bool

Checks if a record is tombstoned.

pub fn get_tombstone(&self, record_id: &K) -> Option<TombstoneInfo>

Gets tombstone information for a record.

pub fn compact_tombstones(&mut self, min_acknowledged_version: u64) -> usize

Removes tombstones older than the specified version.

Safety and DoS Mitigation

IMPORTANT: Only call this method when ALL participating nodes have acknowledged the min_acknowledged_version. Compacting too early may cause deleted records to reappear on nodes that haven’t received the deletion yet.

To prevent DoS via tombstone accumulation:

• Call this method periodically as part of your sync protocol
• Track which versions have been acknowledged by all nodes
• Consider implementing a tombstone limit and rejecting operations when exceeded

Arguments

• min_acknowledged_version - Tombstones with db_version < this value will be removed

Returns

The number of tombstones removed

pub fn tombstone_count(&self) -> usize

Gets the number of tombstones currently stored.

pub fn get_clock(&self) -> &LogicalClock

Gets the current logical clock.

pub fn get_data(&self) -> &HashMap<K, Record<C, V>>

Gets a reference to the internal data map.

pub fn get_changed_since( &self, since_version: u64, ) -> (HashMap<K, Record<C, V>>, HashMap<K, TombstoneInfo>)

Gets records and tombstones that have changed since a specific version.

This is used for creating incremental snapshots, which only contain records that have been modified since the base snapshot.

Arguments

• since_version - Only return changes after this db_version

Returns

Tuple of (changed_records, new_tombstones)

Example

// Get all changes since version 1000
let (records, tombstones) = crdt.get_changed_since(1000);
// records contains only records modified after version 1000
// tombstones contains only records deleted after version 1000

Trait Implementations

impl<K: Debug + Ord + Hash + Eq + Clone, C: Debug + Hash + Eq + Clone, V: Debug + Clone> Debug for CRDT<K, C, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.