jump to navigation

My approach to operational transformation February 17, 2012

Posted by olvidadorio in Programming.

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!