Operational Transformation

Operational Transformation (OT) [] allows user edits to be performed on a local database without latency, and changes (called operations) are sent and merged asynchronously without the need for distributed transactions.

OT allows operations to be applied in different orders at different sites. In the following picture site A generates an operation O₁ and concurrently site B generates an operation O₂. These operations are applied immediately on the database where they are generated.

Each operation is sent to the peer where it is transformed in such a way that it can be applied in a new context and yet preserves the original intention of the operation. So the two sites execute the operations in different orders and yet they reach the same final state. This is called convergence.

Some people call this eventual consistency, but the term "consistent" means different things to different people, and therefore this term should probably be avoided. For example, instead of referring to convergence of replicas, it might concern:

• whether the system defines a single version of truth at all times
• whether a single database satisfies integrity constraints
• whether the distributed system satisfies integrity constraints
• whether the data is accurate
• whether the operations on each object are linearisable
• whether the transactions on each database are serialisable
• whether distributed transactions on all the databases are serialisable
• whether the set of observable outputs of the system grows monotonically and independently of the order in which the inputs are processed (confluent)

OT provides a basis for multi-master (also called update-anywhere-anytime) replication.

Merge is always defined

An important idea is that the merge of concurrent operations is always defined, so it never fails. In this particular sense there is no concept of merge conflicts.

Instead, CEDA promotes a different and superior way to deal with conflicts between users, based on an approach of indirectly defining very strong integrity constraints.

The idea is to use a base representation which is unconstrained, allowing conflicts to be represented, and therefore allowing merge results to record conflicts between users.

The Jigsaw derived representation provides an example of how Operational Transformation can be used on an unconstrained base representation and yet a derived representation imposes constraints (in this case on the relative positions of the jigsaw pieces).

In some cases it's appropriate for the system to resolve conflicts automatically. For example this happens with assignments and insertions into a list at the same position.

OT on Text

The CEDA merge algorithms allow for arbitrary merging of changes to text.

The result is of a merge is always defined, and it is always the union of all the insertions minus the union of all the deletions. The relative order of the inserted characters is always maintained when merging operations.

OT on many variables

The data is represented in a hierarchical manner using sets, tuples, maps, arrays and objects. The operations are typically very fine grained and target the leaf variables which tend to be simple data types. The leaf variables are assumed to be independently updatable.

A list of of keys identifies a leaf variable which is the target of the update. See mapped values.

The lattice of database states

The database states that preserve causality form a mathematical structure called a lattice.

Primer on Operational Transformation

This primer on Operational Transformation may be of interest to those wanting to know more about the underlying theory.

OT allows for an interesting idea: selective undo.