CRDTs – simple yet powerful tools for managing state update

During my weekend research, I was exploring CRDTs (Conflict-Free Replicated Data Types). The basic CRDTs are easy to understand yet quite powerful, as they allow updates to be applied to an object from various sources.

Imagine having an element on a website that multiple people can update simultaneously.

You can adopt different approaches, such as:

• • Grow-only CRDT
• • Last-Write-Wins Register (LWWR)
• • Two-Phase Set (2P-Set)

Let me go through these approaches and provide an example for each.

1. Grow-Only CRDT

This is the simplest CRDT. It only supports adding elements, so if people are submitting information to our object, we would keep adding elements without removing any.

Properties:

• • Can only add elements, never remove them
• • Provides strong eventual consistency
• • Simple to implement and merge
• • Ideal for append-only logs or collecting unique identifiers

Example Implementation:

class GSet {
    constructor() {
        this.values = new Set();
    }

    add(value) {
        this.values.add(value);
    }

    merge(otherGSet) {
        for (const value of otherGSet.values) {
            this.values.add(value);
        }
    }

    getValues() {
        return Array.from(this.values);
    }

    has(value) {
        return this.values.has(value);
    }

    getState() {
        return Array.from(this.values);
    }

    setState(state) {
        this.values = new Set(state);
    }
}

2. Last-Write-Wins Register (LWWR)

This CRDT is more complex because it uses timestamps to track and determine the most recent update. If there’s a newer update, it replaces the older one.

Properties:

• • Stores a single value with a timestamp
• • Later timestamps always win during merges
• • Suitable for storing single values that need to be updated
• • Relies on system timestamps

Example Implementation:

class LWWRegister {
    constructor(initialValue = null) {
        this.value = initialValue;
        this.timestamp = Date.now();
    }

    set(newValue) {
        const newTimestamp = Date.now();
        this.value = newValue;
        this.timestamp = newTimestamp;
    }

    get() {
        return this.value;
    }

    merge(otherLWW) {
        if (otherLWW.timestamp > this.timestamp) {
            this.value = otherLWW.value;
            this.timestamp = otherLWW.timestamp;
        }
    }

    getState() {
        return {
            value: this.value,
            timestamp: this.timestamp,
        };
    }

    setState(state) {
        this.value = state.value;
        this.timestamp = state.timestamp;
    }
}

Note: In production, since system clocks may diverge, consider using logical clocks to track the last write.

3. Two-Phase Set (2P-Set)

A 2P-Set combines two sets: an add set and a remove set. When a value is added, it is stored in the add set. When removed, it is added to the remove set. Once removed, an element cannot be re-added.

Properties:

• • Combines two G-Sets: one for additions and one for removals
• • Supports adding and removing elements
• • Once removed, an element cannot be re-added
• • Useful for scenarios needing removal but not re-addition

Example Implementation:

class TwoPSet {
    constructor() {
        this.addSet = new GSet();
        this.removeSet = new GSet();
    }

    add(value) {
        this.addSet.add(value);
    }

    remove(value) {
        if (this.addSet.has(value)) {
            this.removeSet.add(value);
        }
    }

    getValues() {
        return this.addSet.getValues().filter(value => !this.removeSet.has(value));
    }

    merge(other2PSet) {
        this.addSet.merge(other2PSet.addSet);
        this.removeSet.merge(other2PSet.removeSet);
    }

    has(value) {
        return this.addSet.has(value) && !this.removeSet.has(value);
    }

    getState() {
        return {
            addSet: this.addSet.getState(),
            removeSet: this.removeSet.getState(),
        };
    }

    setState(state) {
        this.addSet.setState(state.addSet);
        this.removeSet.setState(state.removeSet);
    }
}

Putting It All Together

Here’s an example that demonstrates these CRDTs in action:

const example = () => {
    // G-Set example
    console.log('=== G-Set Example ===');
    const gset1 = new GSet();
    const gset2 = new GSet();

    gset1.add('a');
    gset2.add('b');
    gset1.merge(gset2);
    console.log('G-Set values:', gset1.getValues()); // ['a', 'b']

    // LWW-Register example
    console.log('\n=== LWW-Register Example ===');
    const lww1 = new LWWRegister('initial');
    const lww2 = new LWWRegister('initial');

    lww1.set('value1');
    setTimeout(() => {
        lww2.set('value2');
        lww1.merge(lww2);
        console.log('LWW final value:', lww1.get()); // 'value2'
    }, 100);

    // 2P-Set example
    console.log('\n=== 2P-Set Example ===');
    const tpset1 = new TwoPSet();
    const tpset2 = new TwoPSet();

    tpset1.add('a');
    tpset1.add('b');
    tpset2.add('b');
    tpset2.add('c');
    tpset2.remove('b');

    tpset1.merge(tpset2);
    console.log('2P-Set values:', tpset1.getValues()); // ['a', 'c']
};

example();

Thank you for taking the time to explore these examples! Let me know if you’d like more details or additional implementations.

Image credit : Photo by Johannes Plenio: https://www.pexels.com/photo/selective-focus-photography-of-two-men-builder-figurines-1445324/