Skip to main content

LWWMap

Struct LWWMap 

Source
pub struct LWWMap<K: Eq + Hash + Ord, V> {
    pub entries: Vec<(K, (V, u64, String))>,
    pub vclock: VectorClock,
}
Expand description

LWW-Map: A Last-Write-Wins Map CRDT.

An LWW-Map is a key-value map where each entry independently resolves conflicts using Last-Write-Wins (LWW) semantics. This is achieved by storing a timestamp and node identifier for each key-value pair.

§Key Properties

  • Map Semantics: Stores key-value pairs.
  • Per-Key LWW: Each key’s value is determined by the latest timestamp.
  • Add/Update Wins: Updates with higher timestamps overwrite older ones.

§Algebraic Properties

  • Commutativity: Yes.
  • Associativity: Yes.
  • Idempotence: Yes.

§Example

use crdt_data_types::LWWMap;

let mut map1 = LWWMap::new();
map1.insert("node_a", "key1".to_string(), "value1".to_string(), 100);

let mut map2 = LWWMap::new();
map2.insert("node_b", "key1".to_string(), "value2".to_string(), 200);

map1.merge(&map2);
assert_eq!(map1.get(&"key1".to_string()), Some(&"value2".to_string())); // Higher timestamp wins

Fields§

§entries: Vec<(K, (V, u64, String))>

Internal storage for map entries: key -> (value, timestamp, node_id).

§vclock: VectorClock

Vector clock representing the causal history of the map.

Implementations§

Source§

impl<K: Eq + Hash + Ord, V> LWWMap<K, V>

Source

pub fn new() -> Self

Creates a new, empty LWW-Map.

Source§

impl<K, V> LWWMap<K, V>
where K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static, V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,

Source

pub fn insert(&mut self, node_id: &str, key: K, value: V, timestamp: u64)

Inserts or updates a value for a specific key.

The update is applied only if the new timestamp is higher than the current one for that key, or if they are equal and the new node_id is lexicographically greater.

Source

pub fn remove(&mut self, key: &K)

Removes a key (and its value) from the map.

Note: Standard LWW-Map removals usually require tombstones to be commutative in all scenarios. This simple implementation clears local state.

Source

pub fn get(&self, key: &K) -> Option<&V>

Returns the value associated with the key, if any.

Source

pub fn merge(&mut self, other: &Self)

Merges another LWW-Map into this one.

Trait Implementations§

Source§

impl<K: Clone + Eq + Hash + Ord, V: Clone> Clone for LWWMap<K, V>

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<K, V> Crdt for LWWMap<K, V>
where K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static, V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,

Source§

type Reader<'a> = LWWMapReader<'a, K, V>

Zero-copy reader type associated with this CRDT.
Source§

fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError>

Merges N CRDTs from zero-copy readers into a single new CRDT instance. Read more
Source§

fn to_capnp_bytes(&self) -> Vec<u8> ⓘ

Serializes the CRDT to a byte buffer using Cap’n Proto. Read more
Source§

fn is_empty(&self) -> bool

Returns true if the CRDT is in its default (empty) state.
Source§

fn validate(&self) -> Result<(), CrdtError>

Validates the internal consistency of the CRDT state. Read more
Source§

impl<K: Debug + Eq + Hash + Ord, V: Debug> Debug for LWWMap<K, V>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<K: Eq + Hash + Ord, V> Default for LWWMap<K, V>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<'de, K, V> Deserialize<'de> for LWWMap<K, V>

Source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
Source§

impl<K: Eq + Eq + Hash + Ord, V: Eq> Eq for LWWMap<K, V>

Source§

impl<K: PartialEq + Eq + Hash + Ord, V: PartialEq> PartialEq for LWWMap<K, V>

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl<K, V> Serialize for LWWMap<K, V>
where K: Serialize + Eq + Hash + Ord, V: Serialize,

Source§

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>
where __S: Serializer,

Serialize this value into the given Serde serializer. Read more
Source§

impl<K: PartialEq + Eq + Hash + Ord, V: PartialEq> StructuralPartialEq for LWWMap<K, V>

Auto Trait Implementations§

§

impl<K, V> Freeze for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: Freeze,

§

impl<K, V> RefUnwindSafe for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: RefUnwindSafe,

§

impl<K, V> Send for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: Send,

§

impl<K, V> Sync for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: Sync,

§

impl<K, V> Unpin for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: Unpin,

§

impl<K, V> UnsafeUnpin for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: UnsafeUnpin,

§

impl<K, V> UnwindSafe for LWWMap<K, V>
where Vec<(K, (V, u64, String))>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,

Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.