Operational Transformation (OT) is the most widely used algorithm for merging changes to the same file from two simultaneous users. It is used as a base for Google Docs and countless other real-time text editing programs.

There are only a few open-source implementations of OT, though, which means that we as developers are a lot more limited. The most popular choice is ot.js, which is designed to run in the browser and Node.JS. Unfortunately, it is limited in the sense that the documents being edited are stored in the memory of the server process, so ot.js will not work out of the box across server restarts or with a clustered server setup.

In this blog post, I explain an approach to using OT through Redis, the popular high-performance server-side key-value store, including an implementation of OT in Redis's scripting language, Lua. The methods illustrated here are used in practice by thousands of Octave Online users every day.

Background: How ot.js Works

In ot.js, every change made by a user corresponds to a list of operations. That list of operations is designed to transform a base string into the new string. There are three types of operations: insert, delete, and retain. When reconciling the list of operations, OT creates a new, empty string, and prepares to read in the base string with a "caret" at the first character. When it reads an operation, it does the following:

  1. delete (negative integer): Some number of characters at the caret are deleted. The caret is moved forward that many characters without copying.
  2. retain (positive integer): Some number of characters at the caret are retained. The caret is moved forward the corresponding number of characters, which each character copied into the new string.
  3. insert (string): A string of text is inserted. The inserted string is appended to the new string. The caret in the base string is not moved.

As an example, suppose we started with the string, Hello, world!, and let's suppose that our list of operations was:

{ 7, "Earth", -5, 1}

We start with an empty string. The first operation says, "keep the first 7 characters". We move the caret ahead 7 places, and our new string becomes Hello,.

The second operation says, "insert 'earth' at the current location". The caret stays in place, and our new string becomes Hello, Earth.

The third operation says, "remove the next 5 characters". The caret moves ahead, and our new string remains the same.

The fourth operation says, "keep the next character". The caret, which, in case you haven't been keeping track, is pointing to the exclamation mark, is moved ahead one more character, and the exclamation mark is copied into the new string, making Hello, Earth!. Since this was the last operation, we are now finished.

Where things get interesting is when two people change the document at the same time. How to you merge their changes together? The way that ot.js handles this is by associating a "document version" with each operations list. If two operations lists A and B reference the same document version, then ot.js performs some math to efficiently transform list B to reference the document version after list A would have been applied, giving it the name operational transformation. The magic behind the transformation is beyond the scope of this post, but it's rather easy to understand if you read through the source code.

Redis Architecture Overview

You have two users, Alice and Bob, editing a text file together. Alice is in New York, and is connected to a datacenter in US-East. Bob is in Paris, and is connected to a datacenter in Europe. Each datacenter is running a copy of your server application. However, both copies of the application query the same Redis database.

When Alice makes a change to the file, her change gets sent to the US-East datacenter, which is promptly forwarded to the Redis database. Redis performs the OT magic to merge Alice's change with any changes Bob may have recently made. Then, Redis broadcasts Alice's transformed change to the Europe datacenter, which forwards it to Bob.

The Code

I'm going to assume that you have ot.js set up on the client side and attached to some sort of text editor, either a bare textarea or something more sophisticated like an ACE Editor. I'm also going to assume that you are transmitting operations over some sort of socket connection to your server on ot.js's "sendOperation" callback.

In this example, I present Node.JS code, but your server doesn't need to be running Node.JS; it could be anything (Tornado, PHP, Rails, …) as long as it supports Redis and some way to quickly send messages back and forth to the client.

Below is a function that should be run on the server whenever a user makes a change to the document. It calls a pseudo-function called "runRedisScript", which should perform an "EVAL" operation on the Redis server. You could use redis-scripto, for example, to manage your Redis scripts.

function onOtChange(docId, opsJson, revision) {
	runRedisScript(
		4,
		"ot:" + docId + ":ops",
		"ot:" + docId + ":doc",
		"ot:" + docId + ":cnt",
		"ot:" + docId + ":sub",
		opsJson,
		revision
	);
};

So, what we're doing is to run our Redis script (which I will show you soon). It uses four channels:

  1. ops: A List containing JSON strings of every operation performed on the document.
  2. doc: An up-to-date copy of the document, useful if you need to persist the document across sessions.
  3. cnt: The latest revision number.
  4. sub: A channel for Redis pub-sub notifications of new operations against the document.

Here is the code for the Redis script that will be run.

local ops = cjson.decode(ARGV[1])
local rev = tonumber(ARGV[2])
local ops_key = KEYS[1]
local doc_key = KEYS[2]
local sub_key = KEYS[3]
local cnt_key = KEYS[4]

-- Load any concurrent operations from the cache
local concurrent = redis.call("LRANGE", ops_key, rev, -1)

-- Transform the new operation against all the concurrent operations
if concurrent then
	for i,cops in pairs(concurrent) do
		ops = transform(ops, cjson.decode(cops))
	end
end

-- Save the operation
redis.call("RPUSH", ops_key, cjson.encode(ops))
redis.call("INCR", cnt_key)

-- Load and apply to the document
local doc = redis.call("GET", doc_key)
if type(doc)=="boolean" then doc="" end
doc = apply(doc, ops)
redis.call("SET", doc_key, doc)

-- Publish to the subscribe channel
redis.call("PUBLISH", sub_key, cjson.encode(ops))

First, we read the arguments. Then we load the concurrent operations lists from the ops key. Then we perform the OT magic. Then we save the new operation into the ops key, update the other keys, and publish the operation to the sub channel.

Where is the implementation of transform and apply, you ask? You can find it in my Gist in the file ot.lua.

Back in Node.JS, now, all we need to do is broadcast the operation to all clients. We can make a Redis client to subscribe to the "sub" channel, and whenever something comes through that channel, we broadcast it through all the websocket connections. When the operation gets to the client, we can apply it to the document by calling ot.js's "applyServer" command (or, if applicable, "serverAck" on the client that first produced the operation).

Caveat: UTF-8 Support

For the most part, my ot.lua is transcribing from ot.js. However, one thing that I discovered through that process is that Lua has really crappy support for unicode! Lua, which only knows about single-byte characters, would do ugly things like split multibyte characters in half. To solve this problem, I had to include some UTF-8 code that is capable of correctly calculating string length and substrings.

Caveat: Expiring Keys

In addition to the transform and apply operations, my Gist also contains the rest of the Lua code from this post, with the bonus feature of supporting ops lists that expire after a certain amount of time. This helps keep the amount of data stored in Redis is constant over time. When running the scripts, you should pass in additional arguments corresponding to the number of seconds to keep operations alive in the cache. A couple of minutes should be more than enough time.

Conclusion

I hope that this approach to using a Redis cache as an Operational Transformation server proves useful. OT sounds scary, but it really isn't.

If you like this post, let me know by commenting below!