Operational Transformation: The Key to Real-Time Collaborative Document Editing

5 min readJan 9, 2025

Ever wondered how multiple minds can seamlessly edit the same document in real-time without stepping on each other’s toes? Discover the magic behind it: Operational Transformation.

Real-time collaboration is a very common feature in documents these days. The real puppet master behind it is Operational Transformation.

The Challenge of Collaborative Editing:

One way of implementing collaborative editing is by using the concept of a mutex lock.
A mutex is a lock that we set before using a shared resource and release after using it. When the lock is set, no other thread can access the locked region of code. However, this won’t let users make changes at the same time. The second user will have to wait for the first user to complete their modifications. This scenario is frustrating, as we would like to make changes instantaneously.

So, we have two main issues here:

Concurrency:
Concurrency control is important because it allows multiple users to edit a document simultaneously without interfering with each other.

Latency:
Users are able to edit the same document at the same time, and changes are reflected in the document in real time. Latency might bring the possibility of version conflicts.

A Synchronous Editing Example:

Let’s take an example and see how synchronous operations in a document will look:

Let’s go through the above diagram.

User1 performs operation o1 on site1, and User2 performs operation o2 on site2. From the user’s perspective, both operations are happening at the same time.

The initial state:
"abc"

User1 deletes "c" at position 2.
User2 inserts "x" at position 1, which is before "b."

Scenario 1: o1 runs first

o1 deletes "c", updating the document to "ab."
Then o2 inserts "x" at position 1 before "b," updating the document to "axb."

Scenario 2: o2 runs first

o2 inserts "x" at position 1, updating the document to "axbc."
Then o1 deletes at position 2. In "axbc," "b" is at position 2, so it deletes "b," updating the document to "axc."

Now, we have two results and no way of knowing which is correct. This was an example with only two users; in an ideal scenario with multiple users, this approach would definitely not work.

Enter Operational Transformation:

This is where Operational Transformation (OT) does its magic. The intuition behind OT is to transform the operation before execution. In the above case, o1 will be transformed to o1' before execution.

Illustrating OT with an Example:

Initial State = “abc”

o1 = del(2) (delete the character at position 2)
o2 = ins(“x”, 1) (insert character “x” at position 1)

These operations are generated by two users at collaborating sites 1 and 2, respectively.

Suppose the two operations are executed in the order of o2 and then o1 (at site 2). After executing o2, the document becomes "axbc." To execute o1 after o2, o1 must be transformed against o2 to become:
o1' = del(3), with its positional parameter incremented by one due to the insertion of character "x" by o2.
Executing o1' on "axbc" deletes the correct character "c," and the document becomes "xab."

Formula for Operational Transformation:

T(a, b) = (a′, b′), where b′(a) = a′(b)

Explanation:

a and b are two concurrent operations on a shared document.
T(a, b) is the transformation function that takes operations (a, b) and returns a new pair (a′, b′).
a′ and b′ are the transformed versions of operations a and b.
The notation b′(a) means “apply the transformed operation b′ after operation a.”
Similarly, a′(b) means “apply the transformed operation a′ after operation b.”
The core idea of OT is transforming concurrent operations so they can be applied in any order while achieving the same final result.

How OT Operates:

Every change or modification is an event in the document that moves back and forth among the collaborators.

Transformation of the Operations:
When two users make changes to the same document at the same time on different devices, a transform function steps in. It takes both operations and adjusts them to apply one after the other. This adjustment ensures that the original intention of each change is preserved, even when the operations happen concurrently.

Basic Approach of OT:

Local operations are executed immediately:
When a user changes the document, those changes are applied instantly.
Local response time is insensitive to network latencies:
Regardless of delays in communication from other sites, there is no delay in executing any operation locally.
Unconstrained interaction and high concurrency:
Multiple users can interact with documents simultaneously, making concurrent changes.
Each site maintains an operation log:
Every active client records all operations it has performed or received so that future operations can be coordinated and transformed.
Remote operations are transformed against all concurrent operations in the log before execution:
Before applying changes from another user, the system transforms those operations against its local history of concurrent edits, ensuring consistency and preserving intentions.
The final result is independent of the execution order of concurrent operations:
Regardless of the order in which concurrent operations are applied, the system guarantees that all users will eventually see the same final document state.

This is the most basic layout of how Operational Transformation achieves real-time collaboration with high concurrency and a consistent final document state, regardless of the complex, simultaneous edits happening across the globe.

Reference:

Wikipedia on Operational Transformation Wikipedia’s article on Operational Transformation turned out to be — it stands out as an exceptionally informative resource.
Check out this YouTube video for a comprehensive explanation of OT algorithms and their history: Watch here.

About the Author

Poonam Tomar is a budding Software Engineer with 2 years of hands-on experience in software development. She has delved into diverse projects throughout her journey, displaying a keen aptitude for unraveling intricate challenges. Her passion for continuous learning shines through as she embraces various facets of the field, including problem-solving, web development, and an insightful grasp of architectural analysis.

About CodeStax.Ai

At CodeStax.AI, we stand at the nexus of innovation and enterprise solutions. We offer technology partnerships that empower businesses to drive efficiency, innovation, and growth, harnessing the transformative power of no-code platforms and advanced AI integrations.

But what is the real magic? It’s our tech tribe behind the scenes. If you have a knack for innovation and a passion for redefining the norm, we have the perfect tech playground for you. CodeStax. Ai offers more than a job — it’s a journey into the very heart of what’s next. Join us and be part of the revolution that’s redefining the enterprise tech landscape.