4 ms·
Operational transformation very useful, but it has some drawbacks if you want to do more complicated things with text. Most OT implementations can only get one
by ggreer 12y ago
Operational transformation very useful, but it has some drawbacks if you want to do more complicated things with text. Most OT implementations can only get one step out of sync with the server. Client complexity goes way up if you want to do more than that. Also, transformations can only be simple inserts and deletes. These two limitations combine to make it difficult or impossible to search-and-replace, re-indent, or sort lines alphabetically. To do arbitrary transformations of text (or anything) collaboratively, you need different algorithms. Neil Fraser has written extensively on this topic, and suggests an alternative sync strategy.[1]
Disclosure: I'm one of the founders of Floobits[2]. Since native text editors let you do all kinds of crazy stuff with text, we use an algorithm similar to the one described by Neil Fraser.
1. https://neil.fraser.name/writing/sync/ https://neil.fraser.name/writing/sync/
2. https://floobits.com/ https://floobits.com/
- saurik 12y agoI have never heard of an OT implementation with the limitation you state (only being able to keep a single difference), as OT is designed to make that easy to solve: the client can take each new operation it is making and append it to a "difference" buffer, and then transform the difference buffer (which moves contents in its workin copy) by the results from the server when the server acks it's transform. It then can immediately flush this buffer to the server as a new synchronization request. This reuses the exact same logic as any other transform, so it adds almost no code to the client. As for the limitation that OT only supports inserts and deletes: OT supports anything that can be transformed. If you build an operation "indent area" and then provide a way to partially order that operation against all the other operations (such as "range operation, sort by first position, reverse second, and break ties by operation") you can transform it by moving the position boundaries for inserts and deletes, and when it applies and itself creates a ton of spaces in its interior, that is how it transforms the rest of the operations in the queue. Wave had a number of interesting transforms designed to help it edit structured documents.
- domagoj412 12y agoCan you explain in more detail how OT limits search & replace for example? I dont see a problem because in our implemetation, text replacement is just anouther insert/delete operation... Or am I missing something?