Crate cola

source ·
Expand description

cola is a Conflict-free Replicated Data Type (CRDT) for real-time collaborative editing of plain text documents.

CRDTs can be roughly divided into two categories: state-based and operation-based. cola falls in the latter category.

The basic idea behind an Operation-based CRDT – also known as a Commutative Replicated Data Type or CmRDT – is to design the core data structure and the operations applied to it in such a way that they commute, so that the order in which they’re applied at each peer doesn’t matter.

Commutativity makes the final state of the data structure only a function of its initial state and the set of operations applied to it, but not of the order in which they were applied. This ensures that once all peers have received all operations from all other peers they’re guaranteed to converge to the same final state.

In cola, the core data structure which represents the state of the document at each peer is the Replica, and the operations which the peers exchange to communicate their local edits are Insertions and Deletions.

If you’re new to this crate, reading the documentations of the Replica struct and its methods would be a good place to start.

For a deeper dive into cola’s design and implementation you can check out this blog post.

Example usage

use std::ops::Range;

use cola::{Deletion, Replica, ReplicaId};

struct Document {
    buffer: String,
    crdt: Replica,
}

struct Insertion {
    text: String,
    crdt: cola::Insertion,
}

impl Document {
    fn new<S: Into<String>>(text: S, replica_id: ReplicaId) -> Self {
        let buffer = text.into();
        let crdt = Replica::new(replica_id, buffer.len());
        Document { buffer, crdt }
    }

    fn fork(&self, new_replica_id: ReplicaId) -> Self {
        let crdt = self.crdt.fork(new_replica_id);
        Document { buffer: self.buffer.clone(), crdt }
    }

    fn insert<S: Into<String>>(
        &mut self,
        insert_at: usize,
        text: S,
    ) -> Insertion {
        let text = text.into();
        self.buffer.insert_str(insert_at, &text);
        let insertion = self.crdt.inserted(insert_at, text.len());
        Insertion { text, crdt: insertion }
    }

    fn delete(&mut self, range: Range<usize>) -> Deletion {
        self.buffer.replace_range(range.clone(), "");
        self.crdt.deleted(range)
    }

    fn integrate_insertion(&mut self, insertion: Insertion) {
        if let Some(offset) =
            self.crdt.integrate_insertion(&insertion.crdt)
        {
            self.buffer.insert_str(offset, &insertion.text);
        }
    }

    fn integrate_deletion(&mut self, deletion: Deletion) {
        let ranges = self.crdt.integrate_deletion(&deletion);
        for range in ranges.into_iter().rev() {
            self.buffer.replace_range(range, "");
        }
    }
}

fn main() {
    let mut peer_1 = Document::new("Hello, world", 1);
    let mut peer_2 = peer_1.fork(2);

    let delete_comma = peer_1.delete(5..6);
    let insert_exclamation = peer_2.insert(12, "!");

    peer_1.integrate_insertion(insert_exclamation);
    peer_2.integrate_deletion(delete_comma);

    assert_eq!(peer_1.buffer, "Hello world!");
    assert_eq!(peer_2.buffer, "Hello world!");
}

Feature flags

Structs

Enums

Type Aliases

  • Length
    The length of a piece of text according to some user-defined metric.
  • ProtocolVersion
    The version of the protocol cola uses to represent EncodedReplicas and CrdtEdits.
  • ReplicaId
    A unique identifier for a Replica.