GitHub - thomaswelter/yjs: Shared data types for building collaborative software

A CRDT framework with a powerful abstraction of shared data

Yjs is a CRDT implementation that exposes its internal data structure as shared types. Shared types are common data types like Map or Array with superpowers: changes are automatically distributed to other peers and merged without merge conflicts.

Yjs is network agnostic (p2p!), supports many existing rich text editors, offline editing, version snapshots, undo/redo and shared cursors. It scales well with an unlimited number of users and is well suited for even large documents.

Demos: https://github.com/yjs/yjs-demos
Discuss: https://discuss.yjs.dev
Benchmark Yjs vs. Automerge: https://github.com/dmonad/crdt-benchmarks
Podcast "Yjs Deep Dive into real time collaborative editing solutions":
Podcast "Google Docs-style editing in Gutenberg with the YJS framework":

👷‍♀️ If you are looking for professional (paid) support to build collaborative or distributed applications ping us at yjs@tag1consulting.com. Otherwise you can find help on our discussion board.

Who is using Yjs

Serenity Notes End-to-end encrypted collaborative notes app.
Relm A collaborative gameworld for teamwork and community. 🌟
Input A collaborative note taking app. 🌟
Room.sh A meeting application with integrated collaborative drawing, editing, and coding tools. ⭐
https://coronavirustechhandbook.com/ A collaborative wiki that is edited by thousands of different people to work on a rapid and sophisticated response to the coronavirus outbreak and subsequent impacts. ⭐
Nimbus Note A note-taking app designed by Nimbus Web.
JoeDocs An open collaborative wiki.
Pluxbox RadioManager A web-based app to collaboratively organize radio broadcasts.
Cattaz A wiki that can run custom applications in the wiki pages.
Alldone A next-gen project management and collaboration platform.

Overview

This repository contains a collection of shared types that can be observed for changes and manipulated concurrently. Network functionality and two-way-bindings are implemented in separate modules.

Bindings

Name	Cursors	Binding	Demo
ProseMirror	✔	y-prosemirror	demo
Quill	✔	y-quill	demo
CodeMirror	✔	y-codemirror	demo
Monaco	✔	y-monaco	demo
Slate	✔	slate-yjs	demo
valtio		valtio-yjs	demo

Providers

Setting up the communication between clients, managing awareness information, and storing shared data for offline usage is quite a hassle. Providers manage all that for you and are the perfect starting point for your collaborative app.

y-webrtc: Propagates document updates peer-to-peer using WebRTC. The peers exchange signaling data over signaling servers. Publically available signaling servers are available. Communication over the signaling servers can be encrypted by providing a shared secret, keeping the connection information and the shared document private.
y-websocket: A module that contains a simple websocket backend and a websocket client that connects to that backend. The backend can be extended to persist updates in a leveldb database.
y-indexeddb: Efficiently persists document updates to the browsers indexeddb database. The document is immediately available and only diffs need to be synced through the network provider.
y-dat: [WIP] Write document updates efficiently to the dat network using multifeed. Each client has an append-only log of CRDT local updates (hypercore). Multifeed manages and sync hypercores and y-dat listens to changes and applies them to the Yjs document.

Getting Started

Install Yjs and a provider with your favorite package manager:

npm i yjs y-websocket

Start the y-websocket server:

PORT=1234 node ./node_modules/y-websocket/bin/server.js

Example: Observe types

const yarray = doc.getArray('my-array')
yarray.observe(event => {
  console.log('yarray was modified')
})
// every time a local or remote client modifies yarray, the observer is called
yarray.insert(0, ['val']) // => "yarray was modified"

Example: Nest types

Remember, shared types are just plain old data types. The only limitation is that a shared type must exist only once in the shared document.

const ymap = doc.getMap('map')
const foodArray = new Y.Array()
foodArray.insert(0, ['apple', 'banana'])
ymap.set('food', foodArray)
ymap.get('food') === foodArray // => true
ymap.set('fruit', foodArray) // => Error! foodArray is already defined

Now you understand how types are defined on a shared document. Next you can jump to the demo repository or continue reading the API docs.

Example: Using and combining providers

Any of the Yjs providers can be combined with each other. So you can sync data over different network technologies.

In most cases you want to use a network provider (like y-websocket or y-webrtc) in combination with a persistence provider (y-indexeddb in the browser). Persistence allows you to load the document faster and to persist data that is created while offline.

For the sake of this demo we combine two different network providers with a persistence provider.

import * as Y from 'yjs'
import { WebrtcProvider } from 'y-webrtc'
import { WebsocketProvider } from 'y-websocket'
import { IndexeddbPersistence } from 'y-indexeddb'

const ydoc = new Y.Doc()

// this allows you to instantly get the (cached) documents data
const indexeddbProvider = new IndexeddbPersistence('count-demo', ydoc)
indexeddbProvider.whenSynced.then(() => {
  console.log('loaded data from indexed db')
})

// Sync clients with the y-webrtc provider.
const webrtcProvider = new WebrtcProvider('count-demo', ydoc)

// Sync clients with the y-websocket provider
const websocketProvider = new WebsocketProvider(
  'wss://demos.yjs.dev', 'count-demo', ydoc
)

// array of numbers which produce a sum
const yarray = ydoc.getArray('count')

// observe changes of the sum
yarray.observe(event => {
  // print updates when the data changes
  console.log('new sum: ' + yarray.toArray().reduce((a,b) => a + b))
})

// add 1 to the sum
yarray.push([1]) // => "new sum: 1"

API

import * as Y from 'yjs'

Shared Types

Y.Array

A shareable Array-like type that supports efficient insert/delete of elements at any position. Internally it uses a linked list of Arrays that is split when necessary.

const yarray = new Y.Array()

parent:Y.AbstractType|null

Insert content at index. Note that content is an array of elements. I.e. array.insert(0, [1]) splices the list and inserts 1 at position 0.

delete(index:number, length:number)

get(index:number)

Retrieve a range of content

length:number

map(function(T, number, YArray):M):Array<M>

Copies the content of this YArray to a new Array.

Copies the content of this YArray to a new Array. It transforms all child types to JSON using their toJSON method.

[Symbol.Iterator]

Returns an YArray Iterator that contains the values for each index in the array.

for (let value of yarray) { .. }

observe(function(YArrayEvent, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns.

unobserve(function(YArrayEvent, Transaction):void)

Removes an observe event listener from this type.

observeDeep(function(Array<YEvent>, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type or any of its children is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns. The event listener receives all Events created by itself or any of its children.

unobserveDeep(function(Array<YEvent>, Transaction):void)

Removes an observeDeep event listener from this type.

Y.Map

A shareable Map type.

const ymap = new Y.Map()

parent:Y.AbstractType|null

size: number

Total number of key/value pairs.

delete(key:string)

has(key:string):boolean

get(index:number)

clear()

Removes all elements from this YMap.

clone():Y.Map

Clone this type into a fresh Yjs type.

Copies the [key,value] pairs of this YMap to a new Object.It transforms all child types to JSON using their toJSON method.

Execute the provided function once for every key-value pair.

[Symbol.Iterator]

Returns an Iterator of [key, value] pairs.

for (let [key, value] of ymap) { .. }

entries()

Returns an Iterator of [key, value] pairs.

values()

Returns an Iterator of all values.

keys()

Returns an Iterator of all keys.

observe(function(YMapEvent, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns.

unobserve(function(YMapEvent, Transaction):void)

Removes an observe event listener from this type.

observeDeep(function(Array<YEvent>, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type or any of its children is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns. The event listener receives all Events created by itself or any of its children.

unobserveDeep(function(Array<YEvent>, Transaction):void)

Removes an observeDeep event listener from this type.

Y.Text

A shareable type that is optimized for shared editing on text. It allows to assign properties to ranges in the text. This makes it possible to implement rich-text bindings to this type.

This type can also be transformed to the delta format. Similarly the YTextEvents compute changes as deltas.

const ytext = new Y.Text()

parent:Y.AbstractType|null

insert(index:number, content:string, [formattingAttributes:Object<string,string>])

Insert a string at index and assign formatting attributes to it.

ytext.insert(0, 'bold text', { bold: true })

delete(index:number, length:number)

format(index:number, length:number, formattingAttributes:Object<string,string>)

Assign formatting attributes to a range in the text

applyDelta(delta: Delta, opts:Object<string,any>)

See Quill Delta Can set options for preventing remove ending newLines, default is true.

ytext.applyDelta(delta, { sanitize: false })

length:number

toString():string

Transforms this type, without formatting options, into a string.

toJSON():string

See toString

toDelta():Delta

Transforms this type to a Quill Delta

observe(function(YTextEvent, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns.

unobserve(function(YTextEvent, Transaction):void)

Removes an observe event listener from this type.

observeDeep(function(Array<YEvent>, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type or any of its children is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns. The event listener receives all Events created by itself or any of its children.

unobserveDeep(function(Array<YEvent>, Transaction):void)

Removes an observeDeep event listener from this type.

Y.XmlFragment

A container that holds an Array of Y.XmlElements.

const yxml = new Y.XmlFragment()

parent:Y.AbstractType|null

firstChild:Y.XmlElement|Y.XmlText|null

insert(index:number, content:Array<Y.XmlElement|Y.XmlText>)

delete(index:number, length:number)

get(index:number)

slice(start:number, end:number):Array<Y.XmlElement|Y.XmlText>

Retrieve a range of content

length:number

clone():Y.XmlFragment

Clone this type into a fresh Yjs type.

toArray():Array<Y.XmlElement|Y.XmlText>

Copies the children to a new Array.

toDOM():DocumentFragment

Transforms this type and all children to new DOM elements.

toString():string

Get the XML serialization of all descendants.

toJSON():string

See toString.

createTreeWalker(filter: function(AbstractType<any>):boolean):Iterable

Create an Iterable that walks through the children.

observe(function(YXmlEvent, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns.

unobserve(function(YXmlEvent, Transaction):void)

Removes an observe event listener from this type.

observeDeep(function(Array<YEvent>, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type or any of its children is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns. The event listener receives all Events created by itself or any of its children.

unobserveDeep(function(Array<YEvent>, Transaction):void)

Removes an observeDeep event listener from this type.

Y.XmlElement

A shareable type that represents an XML Element. It has a nodeName, attributes, and a list of children. But it makes no effort to validate its content and be actually XML compliant.

const yxml = new Y.XmlElement()

parent:Y.AbstractType|null

firstChild:Y.XmlElement|Y.XmlText|null

nextSibling:Y.XmlElement|Y.XmlText|null

prevSibling:Y.XmlElement|Y.XmlText|null

insert(index:number, content:Array<Y.XmlElement|Y.XmlText>)

delete(index:number, length:number)

get(index:number)

length:number

setAttribute(attributeName:string, attributeValue:string)

removeAttribute(attributeName:string)

getAttribute(attributeName:string):string

getAttributes():Object<string,string>

get(i:number):Y.XmlElement|Y.XmlText

Retrieve the i-th element.

slice(start:number, end:number):Array<Y.XmlElement|Y.XmlText>

Retrieve a range of content

clone():Y.XmlElement

Clone this type into a fresh Yjs type.

toArray():Array<Y.XmlElement|Y.XmlText>

Copies the children to a new Array.

toDOM():Element

Transforms this type and all children to a new DOM element.

toString():string

Get the XML serialization of all descendants.

toJSON():string

See toString.

observe(function(YXmlEvent, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns.

unobserve(function(YXmlEvent, Transaction):void)

Removes an observe event listener from this type.

observeDeep(function(Array<YEvent>, Transaction):void)

Adds an event listener to this type that will be called synchronously every time this type or any of its children is modified. In the case this type is modified in the event listener, the event listener will be called again after the current event listener returns. The event listener receives all Events created by itself or any of its children.

unobserveDeep(function(Array<YEvent>, Transaction):void)

Removes an observeDeep event listener from this type.

Y.Doc

const doc = new Y.Doc()

clientID

A unique id that identifies this client. (readonly)

gc

Whether garbage collection is enabled on this doc instance. Set `doc.gc = false` in order to disable gc and be able to restore old content. See https://github.com/yjs/yjs#yjs-crdt-algorithm for more information about gc in Yjs.

transact(function(Transaction):void [, origin:any])

Every change on the shared document happens in a transaction. Observer calls and the update event are called after each transaction. You should bundle changes into a single transaction to reduce the amount of event calls. I.e. doc.transact(() => { yarray.insert(..); ymap.set(..) }) triggers a single change event.
You can specify an optional origin parameter that is stored on transaction.origin and on('update', (update, origin) => ..).

toJSON():any

Deprecated: It is recommended to call toJSON directly on the shared types. Converts the entire document into a js object, recursively traversing each yjs type. Doesn't log types that have not been defined (using ydoc.getType(..)).

get(string, Y.[TypeClass]):[Type]

Define a shared type.

getArray(string):Y.Array

Define a shared Y.Array type. Is equivalent to y.get(string, Y.Array).

getMap(string):Y.Map

Define a shared Y.Map type. Is equivalent to y.get(string, Y.Map).

getXmlFragment(string):Y.XmlFragment

Define a shared Y.XmlFragment type. Is equivalent to y.get(string, Y.XmlFragment).

on(string, function)

Register an event listener on the shared type

off(string, function)

Unregister an event listener from the shared type

Y.Doc Events

on('update', function(updateMessage:Uint8Array, origin:any, Y.Doc):void)

Listen to document updates. Document updates must be transmitted to all other peers. You can apply document updates in any order and multiple times.

on('beforeTransaction', function(Y.Transaction, Y.Doc):void)

Emitted before each transaction.

on('afterTransaction', function(Y.Transaction, Y.Doc):void)

Emitted after each transaction.

on('beforeAllTransactions', function(Y.Doc):void)

Transactions can be nested (e.g. when an event within a transaction calls another transaction). Emitted before the first transaction.

on('afterAllTransactions', function(Y.Doc, Array<Y.Transaction>):void)

Emitted after the last transaction is cleaned up.

Document Updates

Changes on the shared document are encoded into document updates. Document updates are commutative and idempotent. This means that they can be applied in any order and multiple times.

Example: Listen to update events and apply them on remote client

const doc1 = new Y.Doc()
const doc2 = new Y.Doc()

doc1.on('update', update => {
  Y.applyUpdate(doc2, update)
})

doc2.on('update', update => {
  Y.applyUpdate(doc1, update)
})

// All changes are also applied to the other document
doc1.getArray('myarray').insert(0, ['Hello doc2, you got this?'])
doc2.getArray('myarray').get(0) // => 'Hello doc2, you got this?'

Yjs internally maintains a state vector that denotes the next expected clock from each client. In a different interpretation it holds the number of structs created by each client. When two clients sync, you can either exchange the complete document structure or only the differences by sending the state vector to compute the differences.

Example: Sync two clients by exchanging the complete document structure

const state1 = Y.encodeStateAsUpdate(ydoc1)
const state2 = Y.encodeStateAsUpdate(ydoc2)
Y.applyUpdate(ydoc1, state2)
Y.applyUpdate(ydoc2, state1)

Example: Sync two clients by computing the differences

This example shows how to sync two clients with the minimal amount of exchanged data by computing only the differences using the state vector of the remote client. Syncing clients using the state vector requires another roundtrip, but can save a lot of bandwidth.

const stateVector1 = Y.encodeStateVector(ydoc1)
const stateVector2 = Y.encodeStateVector(ydoc2)
const diff1 = Y.encodeStateAsUpdate(ydoc1, stateVector2)
const diff2 = Y.encodeStateAsUpdate(ydoc2, stateVector1)
Y.applyUpdate(ydoc1, diff2)
Y.applyUpdate(ydoc2, diff1)

Example: Syncing clients without loading the Y.Doc

It is possible to sync clients and compute delta updates without loading the Yjs document to memory. Yjs exposes an API to compute the differences directly on the binary document updates.

// encode the current state as a binary buffer
let currentState1 = Y.encodeStateAsUpdate(ydoc1)
let currentState2 = Y.encodeStateAsUpdate(ydoc2)
// now we can continue syncing clients using state vectors without using the Y.Doc
ydoc1.destroy()
ydoc2.destroy()

const stateVector1 = Y.encodeStateVectorFromUpdate(currentState1)
const stateVector2 = Y.encodeStateVectorFromUpdate(currentState2)
const diff1 = Y.diffUpdate(currentState1, stateVector2)
const diff2 = Y.diffUpdate(currentState2, stateVector1)

// sync clients
currentState1 = Y.mergeUpdates([currentState1, diff2])
currentState1 = Y.mergeUpdates([currentState1, diff1])

Y.applyUpdate(Y.Doc, update:Uint8Array, [transactionOrigin:any])

Apply a document update on the shared document. Optionally you can specify transactionOrigin that will be stored on transaction.origin and ydoc.on('update', (update, origin) => ..).

Y.encodeStateAsUpdate(Y.Doc, [encodedTargetStateVector:Uint8Array]):Uint8Array

Encode the document state as a single update message that can be applied on the remote document. Optionally specify the target state vector to only write the differences to the update message.

Y.encodeStateVector(Y.Doc):Uint8Array

Computes the state vector and encodes it into an Uint8Array.

Y.mergeUpdates(Array<Uint8Array>)

Merge several document updates into a single document update while removing duplicate information. The merged document update is always smaller than the separate updates because of the compressed encoding.

Y.encodeStateVectorFromUpdate(Uint8Array): Uint8Array

Computes the state vector from a document update and encodes it into an Uint8Array.

Y.diffUpdate(update: Uint8Array, stateVector: Uint8Array): Uint8Array

Encode the missing differences to another update message. This function works similarly to Y.encodeStateAsUpdate(ydoc, stateVector) but works on updates instead.

Relative Positions

Example: Transform to RelativePosition and back

const relPos = Y.createRelativePositionFromTypeIndex(ytext, 2)
const pos = Y.createAbsolutePositionFromRelativePosition(relPos, doc)
pos.type === ytext // => true
pos.index === 2 // => true

Example: Send relative position to remote client (json)

const relPos = Y.createRelativePositionFromTypeIndex(ytext, 2)
const encodedRelPos = JSON.stringify(relPos)
// send encodedRelPos to remote client..
const parsedRelPos = JSON.parse(encodedRelPos)
const pos = Y.createAbsolutePositionFromRelativePosition(parsedRelPos, remoteDoc)
pos.type === remoteytext // => true
pos.index === 2 // => true

Example: Send relative position to remote client (Uint8Array)

const relPos = Y.createRelativePositionFromTypeIndex(ytext, 2)
const encodedRelPos = Y.encodeRelativePosition(relPos)
// send encodedRelPos to remote client..
const parsedRelPos = Y.decodeRelativePosition(encodedRelPos)
const pos = Y.createAbsolutePositionFromRelativePosition(parsedRelPos, remoteDoc)
pos.type === remoteytext // => true
pos.index === 2 // => true

Y.createRelativePositionFromTypeIndex(Uint8Array|Y.Type, number)

Y.createAbsolutePositionFromRelativePosition(RelativePosition, Y.Doc)

Y.encodeRelativePosition(RelativePosition):Uint8Array

Y.decodeRelativePosition(Uint8Array):RelativePosition

Y.UndoManager

Yjs ships with an Undo/Redo manager for selective undo/redo of changes on a Yjs type. The changes can be optionally scoped to transaction origins.

const ytext = doc.getText('text')
const undoManager = new Y.UndoManager(ytext)

ytext.insert(0, 'abc')
undoManager.undo()
ytext.toString() // => ''
undoManager.redo()
ytext.toString() // => 'abc'

constructor(scope:Y.AbstractType|Array<Y.AbstractType> [, {captureTimeout:number,trackedOrigins:Set<any>,deleteFilter:function(item):boolean}])

Accepts either single type as scope or an array of types.

undo()

redo()

stopCapturing()

on('stack-item-added', { stackItem: { meta: Map<any,any> }, type: 'undo' | 'redo' })

Register an event that is called when a StackItem is added to the undo- or the redo-stack.

on('stack-item-popped', { stackItem: { meta: Map<any,any> }, type: 'undo' | 'redo' })

Register an event that is called when a StackItem is popped from the undo- or the redo-stack.

Example: Stop Capturing

UndoManager merges Undo-StackItems if they are created within time-gap smaller than options.captureTimeout. Call um.stopCapturing() so that the next StackItem won't be merged.

// without stopCapturing
ytext.insert(0, 'a')
ytext.insert(1, 'b')
undoManager.undo()
ytext.toString() // => '' (note that 'ab' was removed)
// with stopCapturing
ytext.insert(0, 'a')
undoManager.stopCapturing()
ytext.insert(0, 'b')
undoManager.undo()
ytext.toString() // => 'a' (note that only 'b' was removed)

Example: Specify tracked origins

Every change on the shared document has an origin. If no origin was specified, it defaults to null. By specifying trackedOrigins you can selectively specify which changes should be tracked by UndoManager. The UndoManager instance is always added to trackedOrigins.

class CustomBinding {}

const ytext = doc.getText('text')
const undoManager = new Y.UndoManager(ytext, {
  trackedOrigins: new Set([42, CustomBinding])
})

ytext.insert(0, 'abc')
undoManager.undo()
ytext.toString() // => 'abc' (does not track because origin `null` and not part
                 //           of `trackedTransactionOrigins`)
ytext.delete(0, 3) // revert change

doc.transact(() => {
  ytext.insert(0, 'abc')
}, 42)
undoManager.undo()
ytext.toString() // => '' (tracked because origin is an instance of `trackedTransactionorigins`)

doc.transact(() => {
  ytext.insert(0, 'abc')
}, 41)
undoManager.undo()
ytext.toString() // => '' (not tracked because 41 is not an instance of
                 //        `trackedTransactionorigins`)
ytext.delete(0, 3) // revert change

doc.transact(() => {
  ytext.insert(0, 'abc')
}, new CustomBinding())
undoManager.undo()
ytext.toString() // => '' (tracked because origin is a `CustomBinding` and
                 //        `CustomBinding` is in `trackedTransactionorigins`)

Example: Add additional information to the StackItems

When undoing or redoing a previous action, it is often expected to restore additional meta information like the cursor location or the view on the document. You can assign meta-information to Undo-/Redo-StackItems.

const ytext = doc.getText('text')
const undoManager = new Y.UndoManager(ytext, {
  trackedOrigins: new Set([42, CustomBinding])
})

undoManager.on('stack-item-added', event => {
  // save the current cursor location on the stack-item
  event.stackItem.meta.set('cursor-location', getRelativeCursorLocation())
})

undoManager.on('stack-item-popped', event => {
  // restore the current cursor location on the stack-item
  restoreCursorLocation(event.stackItem.meta.get('cursor-location'))
})

Yjs CRDT Algorithm

Conflict-free replicated data types (CRDT) for collaborative editing are an alternative approach to operational transformation (OT). A very simple differenciation between the two approaches is that OT attempts to transform index positions to ensure convergence (all clients end up with the same content), while CRDTs use mathematical models that usually do not involve index transformations, like linked lists. OT is currently the de-facto standard for shared editing on text. OT approaches that support shared editing without a central source of truth (a central server) require too much bookkeeping to be viable in practice. CRDTs are better suited for distributed systems, provide additional guarantees that the document can be synced with remote clients, and do not require a central source of truth.

Yjs implements a modified version of the algorithm described in this paper. This article explains a simple optimization on the CRDT model and gives more insight about the performance characteristics in Yjs. More information about the specific implementation is available in INTERNALS.md and in this walkthrough of the Yjs codebase.

CRDTs that suitable for shared text editing suffer from the fact that they only grow in size. There are CRDTs that do not grow in size, but they do not have the characteristics that are benificial for shared text editing (like intention preservation). Yjs implements many improvements to the original algorithm that diminish the trade-off that the document only grows in size. We can't garbage collect deleted structs (tombstones) while ensuring a unique order of the structs. But we can 1. merge preceeding structs into a single struct to reduce the amount of meta information, 2. we can delete content from the struct if it is deleted, and 3. we can garbage collect tombstones if we don't care about the order of the structs anymore (e.g. if the parent was deleted).

Examples:

If a user inserts elements in sequence, the struct will be merged into a single struct. E.g. text.insert(0, 'a'), text.insert(1, 'b'); is first represented as two structs ([{id: {client, clock: 0}, content: 'a'}, {id: {client, clock: 1}, content: 'b'}) and then merged into a single struct: [{id: {client, clock: 0}, content: 'ab'}].
When a struct that contains content (e.g. ItemString) is deleted, the struct will be replaced with an ItemDeleted that does not contain content anymore.
When a type is deleted, all child elements are transformed to GC structs. A GC struct only denotes the existence of a struct and that it is deleted. GC structs can always be merged with other GC structs if the id's are adjacent.

Especially when working on structured content (e.g. shared editing on ProseMirror), these improvements yield very good results when benchmarking random document edits. In practice they show even better results, because users usually edit text in sequence, resulting in structs that can easily be merged. The benchmarks show that even in the worst case scenario that a user edits text from right to left, Yjs achieves good performance even for huge documents.

State Vector

Yjs has the ability to exchange only the differences when syncing two clients. We use lamport timestamps to identify structs and to track in which order a client created them. Each struct has an struct.id = { client: number, clock: number} that uniquely identifies a struct. We define the next expected clock by each client as the state vector. This data structure is similar to the version vectors data structure. But we use state vectors only to describe the state of the local document, so we can compute the missing struct of the remote client. We do not use it to track causality.

License and Author

Yjs and all related projects are MIT licensed.

Yjs is based on my research as a student at the RWTH i5. Now I am working on Yjs in my spare time.

Fund this project by donating on GitHub Sponsors or hiring me as a contractor for your collaborative app.

Name		Name	Last commit message	Last commit date
Latest commit History 1,469 Commits
.circleci		.circleci
.github/workflows		.github/workflows
src		src
tests		tests
.gitignore		.gitignore
.jsdoc.json		.jsdoc.json
.markdownlint.json		.markdownlint.json
INTERNALS.md		INTERNALS.md
LICENSE		LICENSE
README.md		README.md
package-lock.json		package-lock.json
package.json		package.json
rollup.config.js		rollup.config.js
sponsor-y.js		sponsor-y.js
test.html		test.html
tsconfig.json		tsconfig.json

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Sponsors

Who is using Yjs

Table of Contents

Overview

Bindings

Providers

Getting Started

Example: Observe types

Example: Nest types

Example: Using and combining providers

API

Shared Types

Y.Doc

Y.Doc Events

Document Updates

Example: Listen to update events and apply them on remote client

Example: Sync two clients by exchanging the complete document structure

Example: Sync two clients by computing the differences

Example: Syncing clients without loading the Y.Doc

Relative Positions

Example: Transform to RelativePosition and back

Example: Send relative position to remote client (json)

Example: Send relative position to remote client (Uint8Array)

Y.UndoManager

Example: Stop Capturing

Example: Specify tracked origins

Example: Add additional information to the StackItems

Yjs CRDT Algorithm

State Vector

License and Author

About

Releases

Packages

Languages

License

thomaswelter/yjs

Folders and files

Latest commit

History

Repository files navigation

Sponsors

Who is using Yjs

Table of Contents

Overview

Bindings

Providers

Getting Started

Example: Observe types

Example: Nest types

Example: Using and combining providers

API

Shared Types

Y.Doc

Y.Doc Events

Document Updates

Example: Listen to update events and apply them on remote client

Example: Sync two clients by exchanging the complete document structure

Example: Sync two clients by computing the differences

Example: Syncing clients without loading the Y.Doc

Relative Positions

Example: Transform to RelativePosition and back

Example: Send relative position to remote client (json)

Example: Send relative position to remote client (Uint8Array)

Y.UndoManager

Example: Stop Capturing

Example: Specify tracked origins

Example: Add additional information to the StackItems

Yjs CRDT Algorithm

State Vector

License and Author

About

Resources

License

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages