Struct garage_table::crdt::LWW

pub struct LWW<T> { /* fields omitted */ }

Last Write Win (LWW)

An LWW CRDT associates a timestamp with a value, in order to implement a time-based reconciliation rule: the most recent write wins. For completeness, the LWW reconciliation rule must also be defined for two LWW CRDTs with the same timestamp but different values.

In our case, we add the constraint that the value that is wrapped inside the LWW CRDT must itself be a CRDT: in the case when the timestamp does not allow us to decide on which value to keep, the merge rule of the inner CRDT is applied on the wrapped values. (Note that all types that implement the Ord trait get a default CRDT implemetnation that keeps the maximum value. This enables us to use LWW directly with primitive data types such as numbers or strings. It is generally desirable in this case to never explicitly produce LWW values with the same timestamp but different inner values, as the rule to keep the maximum value isn’t generally the desired semantics.)

As multiple computers clocks are always desynchronized, when operations are close enough, it is equivalent to take one copy and drop the other one.

Given that clocks are not too desynchronized, this assumption is enough for most cases, as there is few chance that two humans coordonate themself faster than the time difference between two NTP servers.

As a more concret example, let’s suppose you want to upload a file with the same key (path) in the same bucket at the very same time. For each request, the file will be timestamped by the receiving server and may differ from what you observed with your atomic clock!

This scheme is used by AWS S3 or Soundcloud and often without knowing in entreprise when reconciliating databases with ad-hoc scripts.

Implementations

impl<T> LWW<T> where
    T: CRDT, 

pub fn new(value: T) -> Self

Creates a new CRDT

CRDT’s internal timestamp is set with current node’s clock.

pub fn migrate_from_raw(ts: u64, value: T) -> Self

Build a new CRDT from a previous non-compatible one

Compared to new, the CRDT’s timestamp is not set to now but must be set to the previous, non-compatible, CRDT’s timestamp.

pub fn update(&mut self, new_value: T)

Update the LWW CRDT while keeping some causal ordering.

The timestamp of the LWW CRDT is updated to be the current node’s clock at time of update, or the previous timestamp + 1 if that’s bigger, so that the new timestamp is always strictly larger than the previous one. This ensures that merging the update with the old value will result in keeping the updated value.

pub fn get(&self) -> &T

Get the CRDT value

pub fn get_mut(&mut self) -> &mut T

Get a mutable reference to the CRDT’s value

This is usefull to mutate the inside value without changing the LWW timestamp. When such mutation is done, the merge between two LWW values is done using the inner CRDT’s merge operation. This is usefull in the case where the inner CRDT is a large data type, such as a map, and we only want to change a single item in the map. To do this, we can produce a “CRDT delta”, i.e. a LWW that contains only the modification. This delta consists in a LWW with the same timestamp, and the map inside only contains the updated value. The advantage of such a delta is that it is much smaller than the whole map.

Avoid using this if the inner data type is a primitive type such as a number or a string, as you will then rely on the merge function defined on Ord types by keeping the maximum of both values.

Trait Implementations

impl<T> CRDT for LWW<T> where
    T: Clone + CRDT, 

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

Merge the two datastructures according to the CRDT rules. self is modified to contain the merged CRDT value. other is not modified.

impl<T: Clone> Clone for LWW<T>

fn clone(&self) -> LWW<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for LWW<T>

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

Formats the value using the given formatter.

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

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

Deserialize this value from the given Serde deserializer.

impl<T: PartialEq> PartialEq<LWW<T>> for LWW<T>

fn eq(&self, other: &LWW<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &LWW<T>) -> bool

This method tests for !=.

impl<T> Serialize for LWW<T> where
    T: Serialize, 

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

Serialize this value into the given Serde serializer.

impl<T> StructuralPartialEq for LWW<T>