Skip to main content

crdt_data_types/
lww_set.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_set_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-Set: A Last-Write-Wins Set CRDT.
14///
15/// An LWW-Set (Last-Write-Wins Set) stores elements where each element's
16/// presence is determined by the latest timestamp associated with an add
17/// or remove operation. It resolves conflicts between concurrent additions
18/// and removals by choosing the operation with the highest timestamp.
19///
20/// # Key Properties
21///
22/// - **Add/Remove Sets**: Maintains separate sets for additions and removals, each with timestamps.
23/// - **LWW Resolution**: An element is present if its addition timestamp is greater than its removal timestamp.
24/// - **Bias**: Typically biased towards addition in case of timestamp ties (configurable, but usually Add-Wins).
25///
26/// # Algebraic Properties
27///
28/// - **Commutativity**: Yes.
29/// - **Associativity**: Yes.
30/// - **Idempotence**: Yes.
31///
32/// # Example
33///
34/// ```
35/// use crdt_data_types::LWWSet;
36///
37/// let mut set = LWWSet::new();
38/// set.insert("node_a", "apple".to_string(), 100);
39/// set.remove("node_b", "apple".to_string(), 50); // Older removal
40///
41/// assert!(set.contains(&"apple".to_string())); // Addition wins (100 > 50)
42/// ```
43#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
44#[serde(bound(
45    serialize = "T: Serialize",
46    deserialize = "T: DeserializeOwned + Eq + Hash + Ord"
47))]
48pub struct LWWSet<T: Eq + Hash + Ord> {
49    /// Tracks addition timestamps: element -> (timestamp, node_id).
50    #[serde(serialize_with = "serialize_lww_map", deserialize_with = "deserialize_lww_map")]
51    pub add_set: Vec<(T, (u64, String))>,
52    /// Tracks removal timestamps: element -> (timestamp, node_id).
53    #[serde(serialize_with = "serialize_lww_map", deserialize_with = "deserialize_lww_map")]
54    pub remove_set: Vec<(T, (u64, String))>,
55    /// Vector clock representing the causal history of the set.
56    #[serde(default)]
57    pub vclock: VectorClock,
58}
59
60fn serialize_lww_map<S, T>(
61    elements: &Vec<(T, (u64, String))>,
62    serializer: S,
63) -> Result<S::Ok, S::Error>
64where
65    S: serde::Serializer,
66    T: Serialize,
67{
68    use serde::ser::SerializeMap;
69    let mut map = serializer.serialize_map(Some(elements.len()))?;
70    for (k, v) in elements {
71        map.serialize_entry(k, v)?;
72    }
73    map.end()
74}
75
76type LWWSetEntry<T> = (T, (u64, String));
77
78fn deserialize_lww_map<'de, D, T>(deserializer: D) -> Result<Vec<LWWSetEntry<T>>, D::Error>
79where
80    D: serde::Deserializer<'de>,
81    T: DeserializeOwned + Eq + Hash + Ord,
82{
83    struct LWWMapVisitor<T>(std::marker::PhantomData<T>);
84
85    impl<'de, T> serde::de::Visitor<'de> for LWWMapVisitor<T>
86    where
87        T: DeserializeOwned + Eq + Hash + Ord,
88    {
89        type Value = Vec<LWWSetEntry<T>>;
90
91        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
92            formatter.write_str("a map of elements to timestamps")
93        }
94
95        fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
96        where
97            M: serde::de::MapAccess<'de>,
98        {
99            let mut elements: Vec<LWWSetEntry<T>> =
100                Vec::with_capacity(access.size_hint().unwrap_or(0));
101            while let Some((key, value)) = access.next_entry()? {
102                elements.push((key, value));
103            }
104            // Sort to maintain invariant
105            elements.sort_by(|a, b| a.0.cmp(&b.0));
106            Ok(elements)
107        }
108    }
109
110    deserializer.deserialize_map(LWWMapVisitor(std::marker::PhantomData))
111}
112
113impl<T: Eq + Hash + Ord> Default for LWWSet<T> {
114    fn default() -> Self {
115        Self {
116            add_set: Vec::new(),
117            remove_set: Vec::new(),
118            vclock: VectorClock::new(),
119        }
120    }
121}
122
123impl<T: Eq + Hash + Ord> LWWSet<T> {
124    /// Creates a new, empty LWW-Set.
125    pub fn new() -> Self {
126        Self::default()
127    }
128}
129
130impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> LWWSet<T> {
131    /// Adds an element to the set with a specific timestamp.
132    pub fn insert(&mut self, node_id: &str, element: T, timestamp: u64) {
133        let node_id_str = node_id.to_string();
134        match self.add_set.binary_search_by(|(e, _)| e.cmp(&element)) {
135            Ok(idx) => {
136                let (_, (ts, nid)) = &self.add_set[idx];
137                if timestamp > *ts || (timestamp == *ts && node_id_str > *nid) {
138                    self.add_set[idx] = (element, (timestamp, node_id_str));
139                    self.vclock.increment(node_id);
140                }
141            }
142            Err(idx) => {
143                self.add_set.insert(idx, (element, (timestamp, node_id_str)));
144                self.vclock.increment(node_id);
145            }
146        }
147    }
148
149    /// Removes an element from the set by adding a tombstone with a specific timestamp.
150    pub fn remove(&mut self, node_id: &str, element: T, timestamp: u64) {
151        let node_id_str = node_id.to_string();
152        match self.remove_set.binary_search_by(|(e, _)| e.cmp(&element)) {
153            Ok(idx) => {
154                let (_, (ts, nid)) = &self.remove_set[idx];
155                if timestamp > *ts || (timestamp == *ts && node_id_str > *nid) {
156                    self.remove_set[idx] = (element, (timestamp, node_id_str));
157                    self.vclock.increment(node_id);
158                }
159            }
160            Err(idx) => {
161                self.remove_set.insert(idx, (element, (timestamp, node_id_str)));
162                self.vclock.increment(node_id);
163            }
164        }
165    }
166
167    /// Returns true if the set contains the specified element.
168    ///
169    /// An element is present if its latest add timestamp is strictly greater
170    /// than its latest remove timestamp (or if no removal exists).
171    pub fn contains(&self, element: &T) -> bool {
172        let add_entry = self
173            .add_set
174            .binary_search_by(|(e, _)| e.cmp(element))
175            .map(|idx| &self.add_set[idx].1)
176            .ok();
177        
178        let remove_entry = self
179            .remove_set
180            .binary_search_by(|(e, _)| e.cmp(element))
181            .map(|idx| &self.remove_set[idx].1)
182            .ok();
183
184        match (add_entry, remove_entry) {
185            (Some((a_ts, a_id)), Some((r_ts, r_id))) => {
186                *a_ts > *r_ts || (*a_ts == *r_ts && a_id > r_id)
187            }
188            (Some(_), None) => true,
189            _ => false,
190        }
191    }
192
193    /// Iterator over the elements currently in the set.
194    pub fn iter(&self) -> impl Iterator<Item = &T> {
195        self.add_set.iter().filter_map(move |(e, _)| {
196            if self.contains(e) {
197                Some(e)
198            } else {
199                None
200            }
201        })
202    }
203
204    /// Merges another LWW-Set into this one.
205    pub fn merge(&mut self, other: &Self) {
206        self.add_set = Self::merge_vecs(&self.add_set, &other.add_set);
207        self.remove_set = Self::merge_vecs(&self.remove_set, &other.remove_set);
208        self.vclock.merge(&other.vclock);
209    }
210
211    fn merge_vecs(
212        left: &[(T, (u64, String))],
213        right: &[(T, (u64, String))],
214    ) -> Vec<(T, (u64, String))> {
215        let mut result = Vec::with_capacity(left.len() + right.len());
216        let mut i = 0;
217        let mut j = 0;
218
219        while i < left.len() && j < right.len() {
220            let (k1, (ts1, id1)) = &left[i];
221            let (k2, (ts2, id2)) = &right[j];
222
223            match k1.cmp(k2) {
224                Ordering::Less => {
225                    result.push((k1.clone(), (*ts1, id1.clone())));
226                    i += 1;
227                }
228                Ordering::Greater => {
229                    result.push((k2.clone(), (*ts2, id2.clone())));
230                    j += 1;
231                }
232                Ordering::Equal => {
233                    // Both have the element, keep the one with higher timestamp/id
234                    if *ts1 > *ts2 || (*ts1 == *ts2 && id1 > id2) {
235                        result.push((k1.clone(), (*ts1, id1.clone())));
236                    } else {
237                        result.push((k2.clone(), (*ts2, id2.clone())));
238                    }
239                    i += 1;
240                    j += 1;
241                }
242            }
243        }
244
245        while i < left.len() {
246            result.push(left[i].clone());
247            i += 1;
248        }
249        while j < right.len() {
250            result.push(right[j].clone());
251            j += 1;
252        }
253
254        result
255    }
256}
257
258// ============================================================================
259// Zero-Copy Reader
260// ============================================================================
261
262pub struct LWWSetReader<'a, T: Eq + Hash + Ord> {
263    bytes: &'a [u8],
264    _phantom: std::marker::PhantomData<T>,
265}
266
267impl<'a, T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static>
268    LWWSetReader<'a, T>
269{
270    pub fn new(bytes: &'a [u8]) -> Self {
271        Self {
272            bytes,
273            _phantom: std::marker::PhantomData,
274        }
275    }
276
277    fn to_set(&self) -> Result<LWWSet<T>, CrdtError> {
278        let reader = serialize::read_message(self.bytes, ReaderOptions::new())
279            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
280        let lww_set = reader
281            .get_root::<lww_set_capnp::lww_set::Reader>()
282            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
283
284        let mut add_set = Vec::new();
285        let adds = lww_set
286            .get_add_set()
287            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
288        for entry in adds {
289            let entry: lww_set_capnp::lww_set::entry::Reader = entry;
290            let element: T = bincode::deserialize(
291                entry
292                    .get_element()
293                    .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?,
294            )
295            .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
296            add_set.push((
297                element,
298                (
299                    entry.get_timestamp(),
300                    entry
301                        .get_node_id()
302                        .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
303                        .to_string()
304                        .map_err(|e: std::str::Utf8Error| {
305                            CrdtError::Deserialization(e.to_string())
306                        })?,
307                ),
308            ));
309        }
310        // Sort to maintain invariant
311        add_set.sort_by(|a, b| a.0.cmp(&b.0));
312
313        let mut remove_set = Vec::new();
314        let removes = lww_set
315            .get_remove_set()
316            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
317        for entry in removes {
318            let entry: lww_set_capnp::lww_set::entry::Reader = entry;
319            let element: T = bincode::deserialize(
320                entry
321                    .get_element()
322                    .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?,
323            )
324            .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
325            remove_set.push((
326                element,
327                (
328                    entry.get_timestamp(),
329                    entry
330                        .get_node_id()
331                        .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
332                        .to_string()
333                        .map_err(|e: std::str::Utf8Error| {
334                            CrdtError::Deserialization(e.to_string())
335                        })?,
336                ),
337            ));
338        }
339        // Sort to maintain invariant
340        remove_set.sort_by(|a, b| a.0.cmp(&b.0));
341
342        let vclock = if lww_set.has_vclock() {
343            let vc_bytes = lww_set
344                .get_vclock()
345                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
346            VectorClock::merge_from_readers(&[crate::vector_clock::VectorClockReader::new(
347                vc_bytes,
348            )])?
349        } else {
350            VectorClock::new()
351        };
352
353        Ok(LWWSet {
354            add_set,
355            remove_set,
356            vclock,
357        })
358    }
359}
360
361impl<'a, T> CrdtReader<'a> for LWWSetReader<'a, T>
362where
363    T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
364{
365    fn is_empty(&self) -> Result<bool, CrdtError> {
366        Ok(self.to_set()?.add_set.is_empty())
367    }
368}
369
370// ============================================================================
371// CRDT Trait Implementation
372// ============================================================================
373
374impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> Crdt
375    for LWWSet<T>
376{
377    type Reader<'a> = LWWSetReader<'a, T>;
378
379    fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
380        let mut result = LWWSet::new();
381        for reader in readers {
382            result.merge(&reader.to_set()?);
383        }
384        Ok(result)
385    }
386
387    fn to_capnp_bytes(&self) -> Vec<u8> {
388        let mut message = Builder::new(HeapAllocator::new());
389        {
390            let mut lww_set = message.init_root::<lww_set_capnp::lww_set::Builder>();
391
392            let mut adds = lww_set.reborrow().init_add_set(self.add_set.len() as u32);
393            for (idx, (element, (timestamp, node_id))) in self.add_set.iter().enumerate() {
394                let mut entry = adds.reborrow().get(idx as u32);
395                let bytes = bincode::serialize(element).expect("LWWSet element serialization fail");
396                entry.set_element(&bytes);
397                entry.set_timestamp(*timestamp);
398                entry.set_node_id(node_id.as_str().into());
399            }
400
401            let mut removes = lww_set
402                .reborrow()
403                .init_remove_set(self.remove_set.len() as u32);
404            for (idx, (element, (timestamp, node_id))) in self.remove_set.iter().enumerate() {
405                let mut entry = removes.reborrow().get(idx as u32);
406                let bytes = bincode::serialize(element).expect("LWWSet element serialization fail");
407                entry.set_element(&bytes);
408                entry.set_timestamp(*timestamp);
409                entry.set_node_id(node_id.as_str().into());
410            }
411
412            let vclock_bytes = self.vclock.to_capnp_bytes();
413            lww_set.set_vclock(&vclock_bytes);
414        }
415        let mut buf = Vec::new();
416        serialize::write_message(&mut buf, &message).expect("LWWSet serialization fail");
417        buf
418    }
419
420    fn is_empty(&self) -> bool {
421        self.add_set.is_empty()
422    }
423
424    fn validate(&self) -> Result<(), CrdtError> {
425        Ok(())
426    }
427}