Skip to main content

crdt_data_types/
lww_map.rs

1// Copyright (c) 2026 Adrian Robinson. All rights reserved.
2// Licensed under the MIT License. See LICENSE file in the project root for full license information.
3
4use crate::lww_map_capnp;
5use crate::traits::{Crdt, CrdtError, CrdtReader};
6use crate::vector_clock::VectorClock;
7use capnp::message::{Builder, HeapAllocator, ReaderOptions};
8use capnp::serialize;
9use serde::{de::DeserializeOwned, Deserialize, Serialize};
10use std::cmp::Ordering;
11use std::hash::Hash;
12
13/// LWW-Map: A Last-Write-Wins Map CRDT.
14///
15/// An LWW-Map is a key-value map where each entry independently resolves conflicts
16/// using Last-Write-Wins (LWW) semantics. This is achieved by storing a timestamp
17/// and node identifier for each key-value pair.
18///
19/// # Key Properties
20///
21/// - **Map Semantics**: Stores key-value pairs.
22/// - **Per-Key LWW**: Each key's value is determined by the latest timestamp.
23/// - **Add/Update Wins**: Updates with higher timestamps overwrite older ones.
24///
25/// # Algebraic Properties
26///
27/// - **Commutativity**: Yes.
28/// - **Associativity**: Yes.
29/// - **Idempotence**: Yes.
30///
31/// # Example
32///
33/// ```
34/// use crdt_data_types::LWWMap;
35///
36/// let mut map1 = LWWMap::new();
37/// map1.insert("node_a", "key1".to_string(), "value1".to_string(), 100);
38///
39/// let mut map2 = LWWMap::new();
40/// map2.insert("node_b", "key1".to_string(), "value2".to_string(), 200);
41///
42/// map1.merge(&map2);
43/// assert_eq!(map1.get(&"key1".to_string()), Some(&"value2".to_string())); // Higher timestamp wins
44/// ```
45#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
46#[serde(bound(
47    serialize = "K: Serialize, V: Serialize",
48    deserialize = "K: DeserializeOwned + Eq + Hash + Ord, V: DeserializeOwned"
49))]
50pub struct LWWMap<K: Eq + Hash + Ord, V> {
51    /// Internal storage for map entries: key -> (value, timestamp, node_id).
52    #[serde(serialize_with = "serialize_entries", deserialize_with = "deserialize_entries")]
53    pub entries: Vec<(K, (V, u64, String))>,
54    /// Vector clock representing the causal history of the map.
55    #[serde(default)]
56    pub vclock: VectorClock,
57}
58
59fn serialize_entries<S, K, V>(
60    entries: &Vec<(K, (V, u64, String))>,
61    serializer: S,
62) -> Result<S::Ok, S::Error>
63where
64    S: serde::Serializer,
65    K: Serialize,
66    V: Serialize,
67{
68    use serde::ser::SerializeMap;
69    let mut map = serializer.serialize_map(Some(entries.len()))?;
70    for (k, v) in entries {
71        map.serialize_entry(k, v)?;
72    }
73    map.end()
74}
75
76type LWWMapEntry<K, V> = (K, (V, u64, String));
77
78fn deserialize_entries<'de, D, K, V>(deserializer: D) -> Result<Vec<LWWMapEntry<K, V>>, D::Error>
79where
80    D: serde::Deserializer<'de>,
81    K: DeserializeOwned + Eq + Hash + Ord,
82    V: DeserializeOwned,
83{
84    struct EntriesVisitor<K, V>(std::marker::PhantomData<(K, V)>);
85
86    impl<'de, K, V> serde::de::Visitor<'de> for EntriesVisitor<K, V>
87    where
88        K: DeserializeOwned + Eq + Hash + Ord,
89        V: DeserializeOwned,
90    {
91        type Value = Vec<LWWMapEntry<K, V>>;
92
93        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
94            formatter.write_str("a map of entries")
95        }
96
97        fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
98        where
99            M: serde::de::MapAccess<'de>,
100        {
101            let mut entries: Vec<LWWMapEntry<K, V>> =
102                Vec::with_capacity(access.size_hint().unwrap_or(0));
103            while let Some((key, value)) = access.next_entry()? {
104                entries.push((key, value));
105            }
106            // Sort to maintain invariant
107            entries.sort_by(|a, b| a.0.cmp(&b.0));
108            Ok(entries)
109        }
110    }
111
112    deserializer.deserialize_map(EntriesVisitor(std::marker::PhantomData))
113}
114
115impl<K: Eq + Hash + Ord, V> Default for LWWMap<K, V> {
116    fn default() -> Self {
117        Self {
118            entries: Vec::new(),
119            vclock: VectorClock::new(),
120        }
121    }
122}
123
124impl<K: Eq + Hash + Ord, V> LWWMap<K, V> {
125    /// Creates a new, empty LWW-Map.
126    pub fn new() -> Self {
127        Self::default()
128    }
129}
130
131impl<K, V> LWWMap<K, V>
132where
133    K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
134    V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
135{
136    /// Inserts or updates a value for a specific key.
137    ///
138    /// The update is applied only if the new timestamp is higher than the current
139    /// one for that key, or if they are equal and the new node_id is lexicographically greater.
140    pub fn insert(&mut self, node_id: &str, key: K, value: V, timestamp: u64) {
141        let node_id_str = node_id.to_string();
142        
143        match self.entries.binary_search_by(|(k, _)| k.cmp(&key)) {
144            Ok(idx) => {
145                let (_, (val, ts, nid)) = &self.entries[idx];
146                let update = timestamp > *ts
147                    || (timestamp == *ts && node_id_str > *nid)
148                    || (timestamp == *ts
149                        && node_id_str == *nid
150                        && value > *val);
151                
152                if update {
153                    self.entries[idx] = (key, (value, timestamp, node_id_str));
154                    self.vclock.increment(node_id);
155                }
156            }
157            Err(idx) => {
158                self.entries.insert(idx, (key, (value, timestamp, node_id_str)));
159                self.vclock.increment(node_id);
160            }
161        }
162    }
163
164    /// Removes a key (and its value) from the map.
165    ///
166    /// Note: Standard LWW-Map removals usually require tombstones to be
167    /// commutative in all scenarios. This simple implementation clears
168    /// local state.
169    pub fn remove(&mut self, key: &K) {
170        if let Ok(idx) = self.entries.binary_search_by(|(k, _)| k.cmp(key)) {
171            self.entries.remove(idx);
172        }
173    }
174
175    /// Returns the value associated with the key, if any.
176    pub fn get(&self, key: &K) -> Option<&V> {
177        self.entries
178            .binary_search_by(|(k, _)| k.cmp(key))
179            .ok()
180            .map(|idx| &self.entries[idx].1.0)
181    }
182
183    /// Merges another LWW-Map into this one.
184    pub fn merge(&mut self, other: &Self) {
185        let mut result = Vec::with_capacity(self.entries.len() + other.entries.len());
186        let mut i = 0;
187        let mut j = 0;
188
189        while i < self.entries.len() && j < other.entries.len() {
190            let (k1, (v1, ts1, nid1)) = &self.entries[i];
191            let (k2, (v2, ts2, nid2)) = &other.entries[j];
192
193            match k1.cmp(k2) {
194                Ordering::Less => {
195                    result.push(self.entries[i].clone());
196                    i += 1;
197                }
198                Ordering::Greater => {
199                    result.push(other.entries[j].clone());
200                    j += 1;
201                }
202                Ordering::Equal => {
203                    // Conflict resolution
204                    let update = *ts2 > *ts1
205                        || (*ts2 == *ts1 && nid2 > nid1)
206                        || (*ts2 == *ts1
207                            && nid2 == nid1
208                            && v2 > v1);
209                    
210                    if update {
211                        result.push(other.entries[j].clone());
212                    } else {
213                        result.push(self.entries[i].clone());
214                    }
215                    i += 1;
216                    j += 1;
217                }
218            }
219        }
220
221        while i < self.entries.len() {
222            result.push(self.entries[i].clone());
223            i += 1;
224        }
225        while j < other.entries.len() {
226            result.push(other.entries[j].clone());
227            j += 1;
228        }
229
230        self.entries = result;
231        self.vclock.merge(&other.vclock);
232    }
233}
234
235// ============================================================================
236// Zero-Copy Reader
237// ============================================================================
238
239pub struct LWWMapReader<'a, K: Eq + Hash + Ord, V> {
240    bytes: &'a [u8],
241    _phantom: std::marker::PhantomData<(K, V)>,
242}
243
244impl<'a, K, V> LWWMapReader<'a, K, V>
245where
246    K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
247    V: Clone + Serialize + DeserializeOwned + Send + Sync + 'static,
248{
249    pub fn new(bytes: &'a [u8]) -> Self {
250        Self {
251            bytes,
252            _phantom: std::marker::PhantomData,
253        }
254    }
255
256    fn to_map(&self) -> Result<LWWMap<K, V>, CrdtError> {
257        let reader = serialize::read_message(self.bytes, ReaderOptions::new())
258            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
259        let lww_map = reader
260            .get_root::<lww_map_capnp::lww_map::Reader>()
261            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
262
263        let mut entries = Vec::new();
264        let entries_list = lww_map
265            .get_entries()
266            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
267
268        for entry in entries_list {
269            let key_bytes = entry
270                .get_key()
271                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
272            let key: K = bincode::deserialize(key_bytes)
273                .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
274
275            let value_bytes = entry
276                .get_value()
277                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
278            let value: V = bincode::deserialize(value_bytes)
279                .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
280
281            let timestamp = entry.get_timestamp();
282            let node_id = entry
283                .get_node_id()
284                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
285                .to_string()
286                .map_err(|e: std::str::Utf8Error| CrdtError::Deserialization(e.to_string()))?;
287
288            entries.push((key, (value, timestamp, node_id)));
289        }
290        // Sort to maintain invariant
291        entries.sort_by(|a, b| a.0.cmp(&b.0));
292
293        let vclock = if lww_map.has_vclock() {
294            let vc_bytes = lww_map
295                .get_vclock()
296                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
297            VectorClock::merge_from_readers(&[crate::vector_clock::VectorClockReader::new(
298                vc_bytes,
299            )])?
300        } else {
301            VectorClock::new()
302        };
303
304        Ok(LWWMap { entries, vclock })
305    }
306}
307
308impl<'a, K, V> CrdtReader<'a> for LWWMapReader<'a, K, V>
309where
310    K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
311    V: Clone + Serialize + DeserializeOwned + Send + Sync + 'static,
312{
313    fn is_empty(&self) -> Result<bool, CrdtError> {
314        Ok(self.to_map()?.entries.is_empty())
315    }
316}
317
318// ============================================================================
319// CRDT Trait Implementation
320// ============================================================================
321
322impl<K, V> Crdt for LWWMap<K, V>
323where
324    K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
325    V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
326{
327    type Reader<'a> = LWWMapReader<'a, K, V>;
328
329    fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
330        let mut result = LWWMap::new();
331        for reader in readers {
332            result.merge(&reader.to_map()?);
333        }
334        Ok(result)
335    }
336
337    fn to_capnp_bytes(&self) -> Vec<u8> {
338        let mut message = Builder::new(HeapAllocator::new());
339        {
340            let mut lww_map = message.init_root::<lww_map_capnp::lww_map::Builder>();
341            let mut entries = lww_map.reborrow().init_entries(self.entries.len() as u32);
342            for (idx, (key, (value, timestamp, node_id))) in self.entries.iter().enumerate() {
343                let mut entry = entries.reborrow().get(idx as u32);
344                let key_bytes = bincode::serialize(key).expect("LWWMap key serialization fail");
345                let value_bytes =
346                    bincode::serialize(value).expect("LWWMap value serialization fail");
347                entry.set_key(&key_bytes);
348                entry.set_value(&value_bytes);
349                entry.set_timestamp(*timestamp);
350                entry.set_node_id(node_id.as_str().into());
351            }
352            let vclock_bytes = self.vclock.to_capnp_bytes();
353            lww_map.set_vclock(&vclock_bytes);
354        }
355        let mut buf = Vec::new();
356        serialize::write_message(&mut buf, &message).expect("LWWMap serialization fail");
357        buf
358    }
359
360    fn is_empty(&self) -> bool {
361        self.entries.is_empty()
362    }
363
364    fn validate(&self) -> Result<(), CrdtError> {
365        Ok(())
366    }
367}