Crates.io | crdt-lite |
lib.rs | crdt-lite |
version | 0.1.0 |
source | src |
created_at | 2024-09-22 15:38:11.646802 |
updated_at | 2024-09-22 15:38:11.646802 |
description | A simple CRDT library for Rust |
homepage | |
repository | https://github.com/sinkingsugar/crdt-lite |
max_upload_size | |
id | 1383057 |
size | 48,995 |
This implementation includes:
K
) and value (V
) types.#[test]
framework to ensure correctness.The LogicalClock
maintains a monotonically increasing counter to preserve causality across events.
#[derive(Debug, Clone)]
struct LogicalClock {
time: u64,
}
impl LogicalClock {
fn new() -> Self { /* ... */ }
fn tick(&mut self) -> u64 { /* ... */ }
fn update(&mut self, received_time: u64) -> u64 { /* ... */ }
fn current_time(&self) -> u64 { /* ... */ }
}
ColumnVersion
tracks the versioning information for each column within a record, enabling fine-grained conflict resolution.
#[derive(Debug, Clone, PartialEq, Eq)]
struct ColumnVersion {
col_version: u64,
db_version: u64,
site_id: u64,
seq: u64,
}
impl ColumnVersion {
fn new(col_version: u64, db_version: u64, site_id: u64, seq: u64) -> Self { /* ... */ }
}
Record
represents an individual record in the CRDT, containing field values and their corresponding version information.
#[derive(Debug, Clone)]
struct Record<V> {
fields: HashMap<String, V>,
column_versions: HashMap<String, ColumnVersion>,
}
impl<V> Record<V> {
fn new(fields: HashMap<String, V>, column_versions: HashMap<String, ColumnVersion>) -> Self { /* ... */ }
}
The CRDT
struct manages the overall state, including data records, tombstones for deletions, and methods to manipulate and merge data.
#[derive(Debug, Clone)]
struct CRDT<K, V>
where
K: Eq + Hash + Clone,
{
node_id: u64,
clock: LogicalClock,
data: HashMap<K, Record<V>>,
tombstones: HashSet<K>,
}
LogicalClock
.Inserts a new record if it's not already tombstoned.
fn insert(&mut self, record_id: K, fields: HashMap<String, V>) { /* ... */ }
col_version
to 1 for all columns.Updates existing record fields if the record isn't tombstoned.
fn update(&mut self, record_id: &K, updates: HashMap<String, V>) { /* ... */ }
col_version
and seq
for updated columns.Deletes a record by marking it as tombstoned.
fn delete(&mut self, record_id: &K) { /* ... */ }
tombstones
and removes from data
.Retrieves all changes since a specified last_db_version
.
fn get_changes_since(&self, last_db_version: u64) -> Vec<Change<K, V>> { /* ... */ }
Change
structs representing the modifications.Merges incoming changes into the CRDT, resolving conflicts based on versioning and site IDs.
fn merge_changes(&mut self, changes: &[Change<K, V>]) { /* ... */ }
col_version
: Accepts the change.col_version
:
site_id
and seq
as tie-breakers.Prints the current state for debugging.
fn print_data(&self) { /* ... */ }
Represents a single change in the CRDT.
#[derive(Debug, Clone)]
struct Change<K, V> {
record_id: K,
col_name: String,
value: Option<V>,
col_version: u64,
db_version: u64,
site_id: u64,
seq: u64,
}
Comprehensive tests ensure the correctness of the CRDT implementation. They cover scenarios like:
Ensure Rust is Installed: If not, install it from rustup.rs.
Save the Code: Save the above code in a file named crdt.rs
.
Create a New Cargo Project:
cargo new crdt_project
cd crdt_project
Replace src/lib.rs
with crdt.rs
: Alternatively, place crdt.rs
in src/
and adjust accordingly.
Add Dependencies: Add uuid
to Cargo.toml
for generating unique identifiers.
[dependencies]
uuid = { version = "1.2", features = ["v4"] }
Run Tests:
cargo test
All tests should pass, indicating that the CRDT behaves as expected.
This project is licensed under the MIT License - see the LICENSE file for details.