Repository files navigation

A CRDT framework with a powerful abstraction of shared data

Yjs is aCRDT implementation that exposes its internaldata structure asshared types. Shared types are common data types likeMaporArray with superpowers: changes are automatically distributed to otherpeers and merged without merge conflicts.

Yjs isnetwork agnostic (p2p!), supports many existingrich texteditors,offline editing,version snapshots,undo/redo andshared cursors. It scales well with an unlimited number of users and is wellsuited for even large documents.

• Demos:https://github.com/yjs/yjs-demos
• Discuss:https://discuss.yjs.dev
• Chat:Gitter |Discord
• 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 support, pleaseconsider supporting this project via a "support contract" onGitHub Sponsors. I will attend your issuesquicker and we can discuss questions and problems in regular video conferences.Otherwise you can find help on our communitydiscussion board.

Please contribute to the project financially - especially if your company relieson Yjs.

• Support Contract with the Maintainer -By contributing financially to the open-source Yjs project, you can receiveprofessional support directly from the author. This includes the opportunity forweekly video calls to discuss your specific challenges.
• Synergy Codes - Specializing inconsulting and developing real-time collaborative editing solutions for visualapps, Synergy Codes focuses on interactive diagrams, complex graphs, charts, andvarious data visualization types. Their expertise empowers developers to buildengaging and interactive visual experiences leveraging the power of Yjs. Seetheir work in action atVisual CollaborationShowcase.

• AFFiNE A local-first, privacy-first, open sourceknowledge base. 🌟
• Huly - Open Source All-in-One Project Management Platform 🌟
• Cargo Site builder for designers and artists 🌟
• Gitbook Knowledge management for technical teams 🌟
• Evernote Note-taking app 🌟
• Lessonspace Enterprise platform for virtualclassrooms and online training 🌟
• Ellipsus - Collaborative writing app for storytelling etc.Supports versioning, change attribution, and "blame". A solution for the wholepublishing process (also selling) ⭐
• Dynaboard Build web apps collaboratively. ⭐
• Relm A collaborative gameworld for teamwork andcommunity. ⭐
• Room.sh A meeting application with integratedcollaborative drawing, editing, and coding tools. ⭐
• Nimbus Note A note-taking app designed byNimbus Web. ⭐
• Pluxbox RadioManager A web-based app tocollaboratively organize radio broadcasts. ⭐
• modyfi - Modyfi is the design platform built formultidisciplinary designers. Design, generate, animate, and more — withoutswitching between apps. ⭐
• Sana A learning platform with collaborative textediting powered by Yjs.
• Serenity Notes End-to-end encryptedcollaborative notes app.
• PRSM Collaborative mind-mapping and system visualisation.(source)
• Alldone A next-gen project management andcollaboration platform.
• Living Spec A modern way for product teams to collaborate.
• Slidebeamer Presentation app.
• BlockSurvey End-to-end encryption for your forms/surveys.
• Skiff Private, decentralized workspace.
• JupyterLab Collaborative computational Notebooks
• JupyterCad Extension toJupyterLab that enables collaborative editing of 3d FreeCAD Models.
• Hyperquery A collaborative data workspace forsharing analyses, documentation, spreadsheets, and dashboards.
• Nosgestesclimat The french carbonfootprint calculator has a group P2P mode based on yjs
• oorja.io Online meeting spaces extensible withcollaborative apps, end-to-end encrypted.
• LegendKeeper Collaborative campaign planner andworldbuilding app for tabletop RPGs.
• IllumiDesk Build courses and content with A.I.
• btw Open-source Medium alternative
• AWS SageMaker Tools for building MachineLearning Models
• linear Streamline issues, projects, and product roadmaps.
• btw - Personal website builder
• AWS SageMaker - Machine Learning Service
• Arkiter - Live interview software
• Appflowy - They use Yrs
• Multi.app - Multiplayer app sharing: Point, draw and editin shared apps as if they're on your computer. They are using Yrs.
• AppMaster A No-Code platform for creatingproduction-ready applications with source code generation.
• Synthesia - Collaborative Video Editor
• thinkdeli - A fast and simple notes app powered by AI
• ourboard - A collaborative whiteboardapplication
• Ellie.ai - Data Product Design and Collaboration
• GoPeer - Collaborative tutoring
• screen.garden - Collaborative backend for PKM apps.
• NextCloud - Content Collaboration Platform
• keystatic - git-based CMS
• QDAcity - Collaborative qualitative data analysis platform
• Kanbert - Project management software
• Eclipse Theia - A cloud & desktopIDE that runs in the browser.
• ScienHub - Collaborative LaTeX editor in the browser.
• Open Collaboration Tools - Collaborativeediting for your IDE or custom editor
• Typst - Compose, edit, and automate technical documents

• Overview
  • Bindings
  • Providers
  • Tooling
  • Ports
• Getting Started
• API
  • Shared Types
  • Y.Doc
  • Document Updates
  • Relative Positions
  • Y.UndoManager
• Yjs CRDT Algorithm
• License and Author

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

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

This list of providers is incomplete. Please open PRs to add your providers tothis list!

y-websocket

A module that contains a simple websocket backend and a websocket client thatconnects to that backend.y-redis,y-sweet,ypy-websocket andHocuspocus (see below) are alternativebackends to y-websocket.

y-webrtc

Propagates document updates peer-to-peer using WebRTC. The peers exchangesignaling data over signaling servers. Publicly available signaling serversare available. Communication over the signaling servers can be encrypted byproviding a shared secret, keeping the connection information and the shareddocument private.

@liveblocks/yjs 🌟

Liveblocks Yjs provides a fullyhosted WebSocket infrastructure and persisted data store for Yjsdocuments. No configuration or maintenance is required. It also featuresYjs webhook events, REST API to read and update Yjs documents, and abrowser DevTools extension.

y-sweet ⭐

A standalone yjs server with persistence to S3 or filesystem. They offer acloud service as well.

Hocuspocus ⭐

A standalone extensible yjs server with sqlite persistence, webhooks, auth and more.

@superviz/yjs

SuperViz Yjs Provider comes with a secure, scalable real-time infrastructure for Yjs documents, fully compatible with a set of real-time collaboration components offered by SuperViz. This solution ensures synchronization, offline editing, and real-time updates, enabling multiple users to collaborate effectively within shared workspaces.

PartyKit

Cloud service for building multiplayer apps.

y-libp2p

Useslibp2p to propagate updates viaGossipSub.Also includes a peer-sync mechanism to catch up on missed updates.

y-dat

[WIP] Write document updates efficiently to the dat network usingmultifeed. Each client hasan append-only log of CRDT local updates (hypercore). Multifeed manages and synchypercores and y-dat listens to changes and applies them to the Yjs document.

Matrix-CRDT

UseMatrix as an off-the-shelf backend forYjs by using theMatrixProvider.Use Matrix as transport and storage of Yjs updates, so you can focus buildingyour client app and Matrix can provide powerful features like Authentication,Authorization, Federation, hosting (self-hosting or SaaS) and even End-to-EndEncryption (E2EE).

yrb-actioncable

An ActionCable companion for Yjs clients. There is a fittingredis extension as well.

ypy-websocket

Websocket backend, written in Python.

Tinybase

The reactive data store for local-first apps. They support multiple CRDTs and different network technologies.

y-webxdc

Provider for sharing data inwebxdc chat apps.

secsync

An architecture to relay end-to-end encrypted CRDTs over a central service.

y-indexeddb

Efficiently persists document updates to the browsers indexeddb database.The document is immediately available and only diffs need to be synced through thenetwork provider.

y-mongodb-provider

Adds persistent storage to a server with MongoDB. Can be used with they-websocket provider.

y-fire

A database and connection provider for Yjs based on Firestore.

y-op-sqlite

Persist YJS updates in your React Native app usingop-sqlite , the fastest SQLite library for React Native.

y-postgresql

Provides persistent storage for a web server using PostgreSQL and is easily compatible with y-websocket.

• y-sweet debugger
• liveblocks devtools
• Yjs inspector

There are several Yjs-compatible ports to other programming languages.

• y-octo - Rust implementation byAFFiNE
• y-crdt - Rust implementation with multiplelanguage bindings to other languages
  • yrs - Rust interface
  • ypy - Python binding
  • yrb - Ruby binding
  • yswift - Swift binding
  • yffi - C-FFI
  • ywasm - WASM binding
  • y_ex - Elixir bindings
• ycs - .Net compatible C# implementation.

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.cjs

import*asYfrom'yjs';constdoc=newY.Doc();constyarray=doc.getArray('my-array')yarray.observe(event=>{console.log('yarray was modified')})// every time a local or remote client modifies yarray, the observer is calledyarray.insert(0,['val'])// => "yarray was modified"

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

constymap=doc.getMap('map')constfoodArray=newY.Array()foodArray.insert(0,['apple','banana'])ymap.set('food',foodArray)ymap.get('food')===foodArray// => trueymap.set('fruit',foodArray)// => Error! foodArray is already defined

Now you understand how types are defined on a shared document. Next you can jumpto thedemo repository or continue readingthe API docs.

Any of the Yjs providers can be combined with each other. So you can sync dataover 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 iscreated while offline.

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

import*asYfrom'yjs'import{WebrtcProvider}from'y-webrtc'import{WebsocketProvider}from'y-websocket'import{IndexeddbPersistence}from'y-indexeddb'constydoc=newY.Doc()// this allows you to instantly get the (cached) documents dataconstindexeddbProvider=newIndexeddbPersistence('count-demo',ydoc)indexeddbProvider.whenSynced.then(()=>{console.log('loaded data from indexed db')})// Sync clients with the y-webrtc provider.constwebrtcProvider=newWebrtcProvider('count-demo',ydoc)// Sync clients with the y-websocket providerconstwebsocketProvider=newWebsocketProvider('wss://demos.yjs.dev','count-demo',ydoc)// array of numbers which produce a sumconstyarray=ydoc.getArray('count')// observe changes of the sumyarray.observe(event=>{// print updates when the data changesconsole.log('new sum: '+yarray.toArray().reduce((a,b)=>a+b))})// add 1 to the sumyarray.push([1])// => "new sum: 1"

import*asYfrom'yjs'

const yarray = new Y.Array()

const ymap = new Y.Map()

const ytext = new Y.Text()

const yxml = new Y.XmlFragment()

const yxml = new Y.XmlElement()

constdoc=newY.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. Seehttps://github.com/yjs/yjs#yjs-crdt-algorithmfor more information about gc in Yjs.

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

Every change on the shared document happens in a transaction. Observer calls andtheupdate event are called after each transaction. You shouldbundle changes into a single transaction to reduce the amount of eventcalls. I.e.doc.transact(() => { yarray.insert(..); ymap.set(..) })triggers a single change event.
You can specify an optionaloriginparameter that is stored ontransaction.origin andon('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 yjstype. Doesn't log types that have not been defined (usingydoc.getType(..)).

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

Define a shared type.

getArray(string):Y.Array

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

getMap(string):Y.Map

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

getText(string):Y.Text

Define a shared Y.Text type. Is equivalent toy.get(string, Y.Text).

getXmlElement(string, string):Y.XmlElement

Define a shared Y.XmlElement type. Is equivalent toy.get(string, Y.XmlElement).

getXmlFragment(string):Y.XmlFragment

Define a shared Y.XmlFragment type. Is equivalent toy.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

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

Listen to document updates. Document updates must be transmitted to all otherpeers. You can apply document updates in any order and multiple times. Use `updateV2`to receive V2 events.

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 anothertransaction). Emitted before the first transaction.

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

Emitted after the last transaction is cleaned up.

Changes on the shared document are encoded intodocument updates. Documentupdates arecommutative andidempotent. This means that they can be appliedin any order and multiple times.

constdoc1=newY.Doc()constdoc2=newY.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 documentdoc1.getArray('myarray').insert(0,['Hello doc2, you got this?'])doc2.getArray('myarray').get(0)// => 'Hello doc2, you got this?'

Yjs internally maintains astate vector that denotes the nextexpected clock from each client. In a different interpretation it holds thenumber of structs created by each client. When two clients sync, you can eitherexchange the complete document structure or only the differences by sending thestate vector to compute the differences.

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

This example shows how to sync two clients with the minimal amount of exchangeddata by computing only the differences using the state vector of the remoteclient. Syncing clients using the state vector requires another roundtrip, butcan save a lot of bandwidth.

conststateVector1=Y.encodeStateVector(ydoc1)conststateVector2=Y.encodeStateVector(ydoc2)constdiff1=Y.encodeStateAsUpdate(ydoc1,stateVector2)constdiff2=Y.encodeStateAsUpdate(ydoc2,stateVector1)Y.applyUpdate(ydoc1,diff2)Y.applyUpdate(ydoc2,diff1)

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

// encode the current state as a binary bufferletcurrentState1=Y.encodeStateAsUpdate(ydoc1)letcurrentState2=Y.encodeStateAsUpdate(ydoc2)// now we can continue syncing clients using state vectors without using the Y.Docydoc1.destroy()ydoc2.destroy()conststateVector1=Y.encodeStateVectorFromUpdate(currentState1)conststateVector2=Y.encodeStateVectorFromUpdate(currentState2)constdiff1=Y.diffUpdate(currentState1,stateVector2)constdiff2=Y.diffUpdate(currentState2,stateVector1)// sync clientscurrentState1=Y.mergeUpdates([currentState1,diff2])currentState2=Y.mergeUpdates([currentState2,diff1])

If one of your users runs into a weird bug (e.g. the rich-text editor throwserror messages), then you don't have to request the full document from youruser. Instead, they can obfuscate the document (i.e. replace the content withmeaningless generated content) before sending it to you. Note that someone mightstill deduce the type of content by looking at the general structure of thedocument. But this is much better than requesting the original document.

Obfuscated updates contain all the CRDT-related data that is required formerging. So it is safe to merge obfuscated updates.

constydoc=newY.Doc()// perform some changes..ydoc.getText().insert(0,'hello world')constupdate=Y.encodeStateAsUpdate(ydoc)// the below update contains scrambled dataconstobfuscatedUpdate=Y.obfuscateUpdate(update)constydoc2=newY.Doc()Y.applyUpdate(ydoc2,obfuscatedUpdate)ydoc2.getText().toString()// => "00000000000"

Yjs implements two update formats. By default you are using the V1 update format.You can opt-in into the V2 update format which provides much better compression.It is not yet used by all providers. However, you can already use it ifyou are building your own provider. All below functions are available with thesuffix "V2". E.g.Y.applyUpdate ⇒Y.applyUpdateV2. Also when listening to updatesyou need to specifically need listen for V2 events e.g.yDoc.on('updateV2', …).We also support conversion functions between both formats:Y.convertUpdateFormatV1ToV2 &Y.convertUpdateFormatV2ToV1.

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

Apply a document update on the shared document. Optionally you can specifytransactionOrigin that will be stored ontransaction.originandydoc.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 theremote document. Optionally specify the target state vector to only write thedifferences 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 removingduplicate information. The merged document update is always smaller thanthe 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 workssimilarly toY.encodeStateAsUpdate(ydoc, stateVector) but workson updates instead.

convertUpdateFormatV1ToV2

Convert V1 update format to the V2 update format.

convertUpdateFormatV2ToV1

Convert V2 update format to the V1 update format.

When working with collaborative documents, we often need to work with positions.Positions may represent cursor locations, selection ranges, or even assign acomment to a range of text. Normal index-positions (expressed as integers) arenot convenient to use because the index-range is invalidated as soon as a remotechange manipulates the document. Relative positions give you a powerful API toexpress positions.

A relative position is fixated to an element in the shared document and is notaffected by remote changes. I.e. given the document"a|c", the relativeposition is attached toc. When a remote user modifies the document byinserting a character before the cursor, the cursor will stay attached to thecharacterc.insert(1, 'x')("a|c") = "ax|c". When the relative position isset to the end of the document, it will stay attached to the end of thedocument.

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

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

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

Y.createRelativePositionFromTypeIndex(type:Uint8Array|Y.Type, index: number[, assoc=0])

Create a relative position fixated to the i-th element in any sequence-likeshared type (ifassoc >= 0). By default, the position associateswith the character that comes after the specified index position. Ifassoc < 0, then the relative position associates with the characterbefore the specified index position.

Y.createAbsolutePositionFromRelativePosition(RelativePosition, Y.Doc):{ type: Y.AbstractType, index: number, assoc: number } | null

Create an absolute position from a relative position. If the relative positioncannot be referenced, or the type is deleted, then the result is null.

Y.encodeRelativePosition(RelativePosition):Uint8Array

Encode a relative position to an Uint8Array. Binary data is the preferredencoding format for document updates. If you prefer JSON encoding, you cansimply JSON.stringify / JSON.parse the relative position instead.

Y.decodeRelativePosition(Uint8Array):RelativePosition

Decode a binary-encoded relative position to a RelativePosition object.

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

constytext=doc.getText('text')constundoManager=newY.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 aStackItem is added to theundo- or the redo-stack.

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

Register an event that is called when an existingStackItem is updated.This happens when two changes happen within a "captureInterval".

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

Register an event that is called when aStackItem is popped fromthe undo- or the redo-stack.

on('stack-cleared', { undoStackCleared: boolean, redoStackCleared: boolean })

Register an event that is called when the undo- and/or the redo-stack is cleared.

UndoManager merges Undo-StackItems if they are created within time-gapsmaller thanoptions.captureTimeout. Callum.stopCapturing() so that the nextStackItem won't be merged.

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

Every change on the shared document has an origin. If no origin was specified,it defaults tonull. By specifyingtrackedOrigins you canselectively specify which changes should be tracked byUndoManager. TheUndoManager instance is always added totrackedOrigins.

classCustomBinding{}constytext=doc.getText('text')constundoManager=newY.UndoManager(ytext,{trackedOrigins:newSet([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 changedoc.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()// => 'abc' (not tracked because 41 is not an instance of//        `trackedTransactionorigins`)ytext.delete(0,3)// revert changedoc.transact(()=>{ytext.insert(0,'abc')},newCustomBinding())undoManager.undo()ytext.toString()// => '' (tracked because origin is a `CustomBinding` and//        `CustomBinding` is in `trackedTransactionorigins`)

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

constytext=doc.getText('text')constundoManager=newY.UndoManager(ytext,{trackedOrigins:newSet([42,CustomBinding])})undoManager.on('stack-item-added',event=>{// save the current cursor location on the stack-itemevent.stackItem.meta.set('cursor-location',getRelativeCursorLocation())})undoManager.on('stack-item-popped',event=>{// restore the current cursor location on the stack-itemrestoreCursorLocation(event.stackItem.meta.get('cursor-location'))})

Conflict-free replicated data types (CRDT) for collaborative editing are analternative approach tooperational transformation (OT). A very simpledifferentiation between the two approaches is that OT attempts to transformindex positions to ensure convergence (all clients end up with the samecontent), while CRDTs use mathematical models that usually do not involve indextransformations, like linked lists. OT is currently the de-facto standard forshared editing on text. OT approaches that support shared editing without acentral source of truth (a central server) require too much bookkeeping to beviable in practice. CRDTs are better suited for distributed systems, provideadditional guarantees that the document can be synced with remote clients, anddo not require a central source of truth.

Yjs implements a modified version of the algorithm described inthispaper.Thisarticleexplains a simple optimization on the CRDT model andgives more insight about the performance characteristics in Yjs.More information about the specific implementation is available inINTERNALS.md and inthis walkthrough of the Yjs codebase.

CRDTs that are suitable for shared text editing suffer from the fact that theyonly grow in size. There are CRDTs that do not grow in size, but they do nothave the characteristics that are beneficial for shared text editing (likeintention preservation). Yjs implements many improvements to the originalalgorithm that diminish the trade-off that the document only grows in size. Wecan't garbage collect deleted structs (tombstones) while ensuring a uniqueorder of the structs. But we can 1. merge preceding structs into a singlestruct to reduce the amount of meta information, 2. we can delete content fromthe struct if it is deleted, and 3. we can garbage collect tombstones if wedon't care about the order of the structs anymore (e.g. if the parent wasdeleted).

Examples:

1. If a user inserts elements in sequence, the struct will be merged into asingle struct. E.g.text.insert(0, 'a'), text.insert(1, 'b'); isfirst represented as two structs ([{id: {client, clock: 0}, content: 'a'}, {id: {client, clock: 1}, content: 'b'}) and then merged into a singlestruct:[{id: {client, clock: 0}, content: 'ab'}].
2. When a struct that contains content (e.g.ItemString) is deleted, thestruct will be replaced with anItemDeleted that does not contain contentanymore.
3. When a type is deleted, all child elements are transformed toGC structs. AGC struct only denotes the existence of a struct and that it is deleted.GC structs can always be merged with otherGC structs if the id's areadjacent.

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

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 aclient created them. Each struct has anstruct.id = { client: number, clock: number} that uniquely identifies a struct. We define the next expectedclockby each client as thestate vector. This data structure is similar to theversion vectors data structure.But we use state vectors only to describe the state of the local document, so wecan compute the missing struct of the remote client. We do not use it to trackcausality.

Yjs and all related projects areMIT licensed.

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

Fund this project by donating onGitHub Sponsorsor hiringme as a contractor for your collaborativeapp.