Home

Awesome

JSON Operational Transformation (JOT)

By Joshua Tauberer https://razor.occams.info.

August 2013.

License: GPL v3 http://choosealicense.com/licenses/gpl-v3/

This module implements operational transformation (OT) on a JSON data model, written in JavaScript for use either in node.js or browsers.

While most collaborative editing models operate on plain text documents with operations like insert and delete on strings, the document model in JOT is JSON --- i.e. the value space of null, booleans, numbers, strings, arrays, and objects (key-value pairs with string keys). JOT includes the basic insert/delete operations on strings but adds many other operations that make JOT useful for tracking changes to any sort of data that can be encoded in JSON.

Basically, this is the core of real time simultaneous editing, like Etherpad, but for structured data rather than just plain text. Since everything can be represented in JSON, this provides plain text collaboration functionality and much more.

This is a work in progress. There is no UI or collaboration framework here.

Why JOT?

Introduction

The core problem addressed by operational transformation libraries like JOT is merging edits made simultaneously, i.e. asynchronously, by two or more users, and the handling of potential conflicts that arise when multiple users edit the same part of the document.

To illustrate the problem, imagine two users open the following JSON document:

{ "title": "Hello World!", "count": 10 }

Each user now has a copy of this document in their local memory. The first user modfies their copy by changing the title and incrementing the count:

{ "title": "It's a Small World!", "count": 20 }

At the same time, the second user changes their copy of the document by changing Hello World! to Hello, Small World! also incrementing the count by 5, yielding:

{ "title": "Hello, Small World!", "count": 15 }

Structured representation of changes

In order to merge these changes, there needs to be a structured representation of the changes. In the flat land of plain text, you are probably used to diffs and patches as structured representations of changes --- e.g. at lines 5 through 10, replace with new content. In JOT, it is up to the library user to form structured representations of changes using JOT's classes. The changes in the example above are constructed as:

var user1 = new jot.LIST([
	new jot.APPLY("title", new jot.SPLICE(0, 5, "It's a Small")),
	new jot.APPLY("count", new jot.MATH("add", 10))
]);

var user2 = new jot.LIST([
	new jot.APPLY("title", new jot.SPLICE(5, 1, ", Small ")),
	new jot.APPLY("count", new jot.MATH('add', 5))
]);

In other words, user 1 makes a change to the title property by replacing the 5 characters starting at position 0 with It's a Small and increments the count property by 10. User 2 makes a change to the title property by replacing the 1 character at position 5, i.e. the first space, with , Small and increments the count property by 5.

These changes cannot yet be combined. If they were applied in order we would get a corrupted document because the character positions that user 2's operation referred to are shifted once user 1's changes are applied. After applying user 1's changes, we have the document:

{ title: "It's a Small World!", count: 20 }

But then if we apply user 2's changes, which say to replace the character at position 5, we would get:

{ title: "It's , Small  Small World!", count: 25 }

That's not what user 2 intended. The second user's changes must be "transformed" to take into account the changes to the document made by the first user before they can be applied.

Transformation

JOT provides an algorithm to transform the structured representation of changes so that simultaneous changes can be combined sequentially.

Continuing the example, we desire to transform the second user's changes so that they can be applied in sequence after the first user's changes.

Instead of

... new jot.APPLY("title", new jot.SPLICE(5, 1, ", Small "))  ...

we want the second user's changes to look like

... new jot.APPLY("title", new jot.SPLICE(12, 1, ", Small "))  ...

Note how the character index has changed. These changes now can be applied after the first user's changes and achieve the intent of user 2's change.

JOT provides a rebase function on operation objects that can make this transformation. (The transformation is named after git's rebase.) The rebase function transforms the operation and yields a new operation that should be applied instead, taking as an argument the operations executed by another user concurrently that have already applied to the document:

user2 = user2.rebase(user1)

These changes can now be merged using compose:

var all_changes = user1.compose(user2);

and then applied to the base document:

document = all_changes.apply(document)

after which the base document will include both user's changes:

{ title: "It's a Small, Small World!", count: 25 }

It would also have been possible to rebase user1 and then compose the operations in the other order, for the exact same result.

See example.js for the complete example.

Compared to other OT libraries

Operational transformation libraries often operate only over strings. JOT has those operations too. For instance, start with the document:

Hello world!

Two simultaneous changes might be:

User 1: REPLACE CHARS 0-4 WITH "Brave new"

User 2: REPLACE CHARS 11-11 WITH "."

To merge these changes, the second user's changes must be rebased to:

User 2: REPLACE CHARS 15-15 WITH "."

JOT's rebase algorithm can handle this case too:

// Construct operations
var document = "Hello world!";
var user1 = new jot.SPLICE(0, 5, "Brave new");
var user2 = new jot.SPLICE(11, 1, ".");

// Rebase user 2
user2 = user2.rebase(user1, { document: document })

// user2 now holds:
// new jot.SPLICE(15, 1, ".")

// Merge
user1.compose(user2).apply(document);
> 'Brave new world.'

Unlike most collaborative editing models where there are only operations like insert and delete that apply to strings, the document model in JOT is JSON --- i.e. the value space of null, booleans, numbers, strings, arrays, and objects (key-value pairs with string keys). Operations are provided that manipulate all of these data types. This makes JOT useful when tracking changes to data, rather than simply to plain text.

Installation

The code is written for the node.js platform and can also be used client-side in modern browsers.

First install node, then install this package:

npm install git+https://github.com/joshdata/jot.git

In a node script, import the library:

var jot = require("jot");

To build the library for browsers, run:

npm install -g browserify
browserify browser_example/browserfy_root.js -d -o dist/jot.js

Then use the library in your HTML page (see the example for details):

<html>
	<body>
		<script src="jot.js"></script>
		<script>
			// see the example below, but skip the 'require' line
		</script>
	</body>
</html>

Operations

The operations in JOT are instantiated as new jot.OPERATION(arguments). The available operations are...

General operations

Operations on booleans and numbers

Operations on strings and arrays

The same operation is used for both strings and arrays:

SPLICE is the only operation you need for basic plain text concurrent editing. JOT includes the entire text editing model in the SPLICE operations plus it adds new operations for non-string data structures!

(Note that internally SPLICE and ATINDEX are sub-cases of an internal PATCH operation that maintains an ordered list of edits to a string or array.)

Operations on objects

Operations that affect document structure

Methods

Instance Methods

Each operation object provides the following instance methods:

Global Methods

The jot library itself offers several global methods:

Conflictless Rebase

What makes JOT useful is that each operation knows how to "rebase" itself against every other operation. This is the "transformation" part of operational transformation, and it's what you do when you have two concurrent edits that need to be merged.

The rebase operation guarantees that any two operations can be combined in any order and result in the same document. In other words, rebase satisfies the constraints A ○ (B/A) == B ○ (A/B) and C / (A○B) == (C/A) / B, where is compose and / is rebase.

Rebase conflicts

In general, not all rebases are possible in a way that preserves the logical intent of each change. This is what results in a merge conflict in source code control software like git. The conflict indicates where two operations could not be merged without losing the logical intent of the changes and intervention by a human is necessary. rebase will return null in these cases.

For example, two MATH operations with different operators will conflict because the order that these operations apply is significant:

> new jot.MATH("add", 1)
    .rebase( new jot.MATH("mult", 2) )
null

(10 + 1) * 2 = 22 but (10 * 2) + 1 == 21. A vanilla rebase will return null in this case to signal that human intervention is needed to choose which operation should apply first.

Using conflictless rebase

However, JOT provides a way to guarantee that rebase will return some operation, so that a merge conflict cannot occur. We call this "conflictless" rebase. The result of a conflictless rebase comes close to preserving the logical intent of the operations by choosing one operation over the other or choosing an order that the operations will apply in.

To get a conflictless rebase, pass a second options argument to rebase with the document option set to the content of the document prior to both operations applying:

> new jot.MATH("add", 1)
    .rebase( new jot.MATH("mult", 2),
             { document: 10 } )
<values.SET 22>

The rebase returns a valid operation now, in this case telling us that to add 1 after the multiplication has applied, we should simply set the result to 22 instead of adding 1. In other words, the rebase has chosen the order where multiplication goes second.

Rebasing the other way around yields a consistent operation:

> new jot.MATH("mult", 2)
    .rebase( new jot.MATH("add", 1),
             { document: 10 } )
<values.MATH mult:2>

In other words, if we're multing by 2 after the addition has applied, we should continue to multiply by 2. That's the same order as rebase chose above.

Development and Testing

Run code coverage tests with npm test or:

npm test -- --coverage-report=html

Notes

Thanks to @konklone for some inspiration and the first pull request.

Similar work: ShareDB, ottypes/json0, Apache Wave (formerly Google Wave), Substance Operator (defunct).