OT: Operational Transformation

Operational Transformation” gives a good introduction while “OTFAQ: Operational Transformation Frequently Asked Questions and Answers” (snapshot) is a really detailed and comprehensive set of FAQs. The author, Prof. Chengzheng Sun, seems prolific in this field.

I can understand it is the technology that supports collaboration in Google Docs, but I didn’t know it did the same for Google Wave, a very audacious real-time collaboration framework, which debuted with much fanfare in 2009, but later fizzled out and got “retired.” The core of then open-sourced Apache Wave was regrouped and lives on as SwellRT. ShareDB: Realtime database backend based on Operational Transformation (OT), formerly known as Share.js, was created by Joseph Gentle, a former Google Wave engineer.

This is not technically significant, but I think “causality preservation” is a misnomer, if it only means the preservation of the happened-before relationship as defined by Lamport’s clock because it does not necessarily signify causation in the normal parlance.

The OT operations normally specify locations in text as the character index from the top. When operations from a remote editor are merged, these locations may need adjusting; hence the need for transformation. If the use of Emacs is assumed, though, can this be mitigated by taking advantage of its built-in markers? Markers are character indices, except that they get automatically adjusted if any of previous text is deleted or inserted (Incidentally, though it is not for OT, CRDT.el is an Emacs package for collaborative editing based on CRDT).

Quill, a Javascript library for rich text editors uses Delta standalone JS library, which can be used outside Quill. “It is suitable for Operational Transform.” “Don’t be confused by its name Delta—Deltas represents both documents and changes to documents. If you think of Deltas as the instructions from going from one document to another, the way Deltas represent a document is by expressing the instructions starting from an empty document.”

“A Delta is made up of an Array of Operations, which describe changes to a document. They can be an insertdelete or retain. Note operations do not take an index. They always describe the change at the current index. Use retains to “keep” or “skip” certain parts of the document.” (emphasis added) The design rationale for Delta is spelled out in “Designing the Delta Format – Quill.”

Delta is also used in Yjs, although Yjs is CRDT-based. Despite the claim that Delta is good for OT, it is designed to eliminate the need for explicitly specifying the location (character index in case of a string) for each operation may have rendered itself a good candidate for CRDT as well.

In the past, I wrote the following articles that touched upon OT (without me really understanding what OT was):

OT: Operational Transformation」への3件のフィードバック

  1. ピンバック: Quill Delta | あくまで暫定措置としてのブログ
  2. ピンバック: Neovim: An Ambitious Extensible and Customizable Text Editor | あくまで暫定措置としてのブログ
  3. ピンバック: Xi and Xray | あくまで暫定措置としてのブログ



WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください