jump to navigation

My approach to operational transformation February 17, 2012

Posted by olvidadorio in Programming.
trackback

I just published a project of mine: snucode, a collaborative real-time text editor with syntax highlighting. (Check out the source at github)

The whole approach is rather simple and vanilla, except for the method of operational transformation I chose to control concurrent edits to a file:

I assign a unique id and a floating point number between 0 and 1 to every character in a document, such that ordering the characters by those points yields the document in its original sequence.

Adding a new character between two others now simply amounts to inserting it somewhere between the neighbors’ respective positions. In this manner no shifting indexes or clocks must be handled.

The problem that this helps solve is the following: One user (let’s call him Bert) is editing the file at index 23, whereas another user (Nancy) is editing around index 42. Bert hits a key, editing the document, and 30 miliseconds later Nancy hits the delete key, removing one character from the document. Both Bert and Nancy’s edits now reach the server. It now has to figure out which key Nancy actually deleted. Since Bert’s edit happened before Nancy’s the naive assumption would be that she actually deleted the character at (old index) 22, after having been shifted once over by Bert’s edit (which however hadn’t yet reached Nancy’s client). So in order to mitigate this situation the server need not only know the exact state of every client, it also constantly has to struggle with different connection speeds and the like to establish the correct sequence.

Using my technique, prioritizing edits is a non-issue, all edits are assumed as factual statements about a position, independently of the order in which they are submitted. The only pathological case appears if two users are concurrently editing the same spot (which is problematic anyway), this pathological case is mitigated by introducing some random jitter to submitted characters’ positions.

However, you may have already noticed that inserting characters in my fashion can suffer from an entirely different problem: Insufficient floating point precision. If I always insert my character in the exact middle between its two adjacents I get my very own uncomfortable version of Zeno’s paradox, with distance between values getting arbitrarily small rather quickly (0.5, 0.75, 0.875 …).

The first approach to mitigate this that I’ve implemented is to acknowledge the fact that text is usually typed from one direction to another (e.g. latin script from left to right). So I try to insert new characters closer to their left than their right neighbor (not smack-dab in the middle).

Another approach would be an unfortunately slightly more complex handoff-process in which all clients and the server agree on a point in the future, at which all clients concurrently create a new version of the ordering placements, according to a cannonical method (i.e. evenly distributed between 0 and 1). All edits that were performed before that point in time are included in that canonical re-scaling, all thereafter are inserted by the clients into the new order, according to the above method. Problems may arise in case some edits performed before that point arrive late, after re-assigning, which necessitates all clients to re-assign afresh for every late edit (and in the worst case re-assign places for consecutive edits).

I bet there’s a correct name for this technique of ordering concurrent inserts to a sorted collection, but I haven’t found it yet. I also haven’t seen anyone apply this technique to OT, but if you have, please let me know!

About these ads

Comments»

1. Nic - February 19, 2012

Is this approach fundamentally different to how google Wave did it?

2. olvidadorio - February 19, 2012

As far as I understand, it is fundamentally different. According to [1], GW manages a “state space” and addresses characters by their index, instead of ID (I think?).. In order to keep this tractable they then have to constrain the client so as to only push new changes whenever the server acknowledges receipt of the current client state.

It sounds like a lot more work.

[1] http://www.waveprotocol.org/whitepapers/operational-transform

3. Nic - February 19, 2012

It almost seems there could be a benchmark test to test the performance of collaborative real-time text editors. The benchmark would have a couple of client processes who would all edit the same document in different (maybe stochastic) scenarios (you already mentioned two in the article). the test score is how few consisteny errors come about.

4. Tim Baumann - March 31, 2013

I’m sorry to say that your suspicion that this approach to collaborative editing has already been invented is right: it’s called commutative replicated data types (or CRDT for short) [1]. The main idea is concurrent operations should be commutative. That is, if two users make changes to a document at the same time, then they can exchange their diffs, apply them (without transforming them) and arrive at the same state. WOOT [2] and Treedoc [3] are two (academic/experimental) implementations of this scheme. Like snucode, they are based on the concept of referring to positions in a document not by the index but by a kind of unique identifier. Treedoc does this by representing the document as a binary tree where the identifier of a character is the path in the binary tree. While this solves the problem of limited fixed-point precision, it doesn’t deal with concurrent insertions at the same position and can result in long identifiers.

[1] http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf
[2] http://hal.inria.fr/inria-00071240/en/
[3] http://hal.inria.fr/docs/00/44/59/75/PDF/icdcs09-treedoc.pdf


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: