How do CRDTs work?

CRDT stands for Conflict-free Replicated Data Type. It is a type of data structure that can be replicated across multiple nodes in a distributed system, while ensuring that there are no conflicts between the replicas. CRDTs are designed to work in an environment where there is no centralized coordination or consensus mechanism.

In CRDTs, every replica has its own copy of the data structure, and each replica is allowed to make changes to its own copy. When two replicas come into contact with each other, they exchange information about the changes they have made. If there are any conflicts between the changes, the CRDT algorithm resolves them automatically, without requiring any coordination between the replicas.

Here is an example of how to use Yjs, a CRDT library, to create a collaborative text editor:

javascript
// Load Yjs and connect to a shared document
const ydoc = new Y.Doc()
const provider = new WebsocketProvider('ws://localhost:1234', 'my-room', ydoc)

// Create a shared text type
const ytext = ydoc.getText('shared-text')

// Bind the text type to a textarea element
const textarea = document.createElement('textarea')
document.body.appendChild(textarea)
Y.bindTextarea(ytext, textarea)

// Listen for changes to the text
ytext.observe(event => {
  console.log('Text changed:', ytext.toString())
})

In this example, we create a Y.Doc object and connect to a shared document using a WebsocketProvider. We then create a shared text type and bind it to a textarea element on the page. Finally, we listen for changes to the text and log them to the console.

Whenever a user types into the textarea, Yjs automatically replicates the changes across all connected clients. If two users make conflicting changes, Yjs resolves the conflicts automatically using its CRDT algorithm.

How does CRDT resolve conflicts?

CRDTs resolve conflicts by ensuring that every replica converges to the same state, even in the presence of concurrent updates. There are two main types of CRDTs: operation-based and state-based.

In state-based CRDTs, each replica maintains a copy of the entire state of the data structure. When two replicas come into contact with each other, they exchange their entire states. If there are any conflicts between the states, the CRDT algorithm merges the states together in a deterministic way. This ensures that all replicas converge to the same state.

Both operation-based and state-based CRDTs are designed to be eventually consistent, meaning that all replicas will eventually converge to the same state, even if there are temporary inconsistencies. This makes them well-suited for use in distributed systems where there is no centralized coordination or consensus mechanism.

Yjs is a state-based CRDT. In Yjs, each replica maintains a copy of the entire state of the data structure. When two replicas come into contact with each other, they exchange their entire states. If there are any conflicts between the states, the Yjs algorithm merges the states together in a deterministic way. This ensures that all replicas converge to the same state.

Yjs uses a data structure called a "shared type" to represent the state of the document. Yjs provides several shared types, including Y.Array, Y.Map, and Y.Text. These shared types can be used to represent different types of data structures, such as arrays, maps, and text documents.

Yjs also provides bindings for several user interface elements, such as textareas and contenteditable elements. These bindings ensure that changes made by the user are automatically propagated to all connected replicas, and that conflicts are resolved automatically using the Yjs algorithm.