The Basics of Operational Transformation

Introduction

Operational transformation (OT) is a technique for resolving a wide variety of conflicts in collaborative editing systems, including read-write conflicts, merge conflicts and write-write conflicts. It works by transforming the operations of one user to make them compatible with the operations of another user. This allows users to work on the same document simultaneously without causing conflicts.

In a multi-user concurrent system handling updates from all the users can be a difficult task. This is because multiple users may be trying to update the same data at the same time. This can lead to conflicts, and the system must decide which change to keep.

Some synchronization strategies are used to keep the local copies of users updated after every change.

• Event passing is a synchronization strategy where changes are propagated to all users as soon as they are made.
• Differential sync is a synchronization strategy where only the changes that have been made since the last synchronization are propagated to all users.

But even then, the problem still exists. What if User 2 makes a change to something that doesn't exist in User 1's copy?

Even with synchronization strategies, there is still a potential for conflicts to occur. This is because synchronization strategies can only resolve conflicts that occur between changes that have already been made. If User 2 makes a change to something that does not exist in User 1's copy, then there is no way for the synchronization strategy to resolve the conflict.

This is where Operational Transformation comes to play. More on this later.

Conflicts in Concurrent Systems.

If you use Git/GitHub, you're probably familiar with conflicts and how irritating they can be. Conflicts occur when two or more users make changes to the same file at the same time. This can lead to problems such as data corruption or lost changes.

In a concurrent system, conflicts can occur at a atomic level because every change is propagated across the system instantly.

There are three main types of conflicts that can occur in concurrent systems:

• Read-write conflicts: This type of conflict occurs when two users try to read and write to the same data at the same time. This can lead to the system displaying different versions of the data to different users.
• Write-write conflicts: This type of conflict occurs when two users try to write to the same data at the same time. This can lead to the system overwriting one user's changes with the changes of another user.
• Merge conflicts: This type of conflict occurs when two users make different changes to the same data. This can lead to the system displaying a merge conflict, which is a message that asks the user to resolve the conflict manually.

Operational Transformation for Conflict Resolution

How Operational Transformation Works

The basic idea of Operational transformation is to represent each operation as a function that takes a state of the document as input and produces a new state of the document as output. For example, an operation to insert the word "boink" into a document could be represented as the function f(state) = state + "boink".

When two users make conflicting changes to a document, OT can be used to transform the operations of one user to make them compatible with the operations of the other user. This is done by applying a composition of the two functions to the state of the document. For example let doc="sudo", if one user inserts the word "boink" into doc and the other user deletes the word "sudo", OT can be used to transform the operations of the first user to produce the text "boink"

The general formula for OT is as follows:

OT(f, g, state) = f(g(state))

where:

• f is the function representing the operations of the first user.
• g is the function representing the operations of the second user.
• state is the state of the document.

The Operation Function:

The Operation function is a generic function that can be used to represent a single operation on a document. The function takes three arguments:

• The type of the operation, which can be either "insert", "delete" etc.
• The text that is being inserted or deleted, if applicable.
• The index at which the text is being inserted or deleted, if applicable.

The function could also take additional arguments, such as the timestamp of the operation or the user who made the operation.

The Operation function returns a new object that represents the operation.

This can be used to represent a wide variety of operations on a document. For example, the function can be used to represent the insertion of a new text, the deletion of an existing text, the modification of an existing text, and the movement of a text within a document.

It is a powerful tool that can be used to simplify and optimize sequences of operations on a document. By representing the operations as objects, the Transformation function can easily compare the two operations and return a new object that represents the combined effect

type Operation struct {
    operation_type string
    text           string
    index          int
}

func operation(operation_type string, text string, index int) Operation {
    return Operation{
        operation_type: operation_type,
        text:           text,
        index:          index,
    }
}

This is a very basic implementation of Operation function.

The Transformation Function:

The transformation functions take two operation objects as input and return a new operation object that is the result of transforming the first operation against the second operation. The transformation function is responsible for ensuring that the transformed operation has the correct effect and maintains document consistency.

The transformation function works by first checking if the two operations are contradictory. If they are, the function returns a new operation that represents the negation of the two operations.

For example, if the two operations are an insertion of the text "A" and a deletion of the text "A", the transformation function would return a new operation that represents a deletion of the text "A".

If the two operations are not contradictory, the function simply returns a new operation that represents the combined effect of the two operations.

For example, if the two operations are an insertion of the text "A" and an insertion of the text "B", the transformation function would return a new operation that represents an insertion of the text "AB".

Here are two cases of these transformation ->

• When insert and delete operation are applied at the same index.

func transform_insertion_against_deletion(op1, op2 Operation) Operation {
    if op1.text == op2.text {
        return Operation{"delete", ""}
    } else {
        return op1
    }
}

Insertion against deletion is an operation that is used to simplify and optimize sequences of operations on a document. The function takes two operations as input, one insertion operation and one deletion operation. The function then returns a new operation that represents the combined effect of the two operations.

• When two concurrent user insert at the same index

func transform_insertion_against_insertion(op1, op2 Operation) Operation {
    if op1.text == op2.text {
        return Operation{"insert", op1.text, op1.index}
    } else {
        return Operation{"insert", op1.text + op2.text, op1.index}
    }
}

Insertion against insertion is an operation that merges two insertions into a single insertion.

The combined effect of the two insertions depends on the text that is being inserted. If the two insertions are of the same text, then the combined effect is that the text is inserted once at the index of the first insertion. If the two insertions are of different text, then the combined effect is that the two texts are concatenated at the index of the first insertion.

Strategies Involved In Transformation

Time-based and Priority-based Transformation

• Time-based transformation is a strategy for resolving conflicts that is based on the time at which the operations were applied. In time-based transformation, the operations that were applied earlier are given priority over the operations that were applied later. This means that if two users make conflicting changes to a document, the changes that were applied earlier will be kept and the changes that were applied later will be discarded.

• Priority-based transformation is a strategy for resolving conflicts that is based on the priority of the users who made the operations. In priority-based transformation, the operations that were made by users with higher priority are given priority over the operations that were made by users with lower priority. This means that if two users make conflicting changes to a document, the changes that were made by the user with higher priority will be kept and the changes that were made by the user with lower priority will be discarded.

Other Strategies for Resolving Conflicts

• Merge-based transformation is a strategy for resolving conflicts that merges the conflicting operations into a single operation. This can be done by combining the text that was inserted by the two operations, or by combining the changes that were made to the document by the two operations.

• Undo-based transformation is a strategy for resolving conflicts that undoes the conflicting operations. This can be done by undoing the changes that were made by the first operation, or by undoing the changes that were made by the second operation.

Client-Server Split in Operational Transformation

In operational transformation, operations and transformations can occur on both the client and server sides. The specific implementation of this depends on the specific application.

In general, operations are created on the client side and sent to the server. The server then applies the operations to the document and sends the transformed document back to the client. The client then applies the transformed document to its local copy of the document.

Transformations can also occur on the client side. For example, if a client receives an operation that it does not understand, it may need to transform the operation before applying it to the document.

The choice of which side to perform operations and transformations depends on a number of factors, including:

• The type of operation: Some operations, such as insertion and deletion, can be performed on both the client and server sides. Other operations, such as merging or splitting, may need to be performed on the server side.

• The security requirements of the application: If the application requires high security, then it may be desirable to perform operations and transformations on the server side. This can prevent users from modifying the document in ways that are not allowed.

• Performance and availability of resources: The performance and availability of resources are important factors to consider when implementing operational transformation. The client-server split must be carefully implemented to avoid performance problems.
  If too many operations are performed on the server side, it can overload the server and cause performance problems for all users. Similarly, if transformations are handled on the client side and the client does not have enough resources available, users may experience performance problems. The client must have enough resources to perform the transformations in a timely manner, or the data might become inconsistent.

Conclusion

In this blog post, we have discussed the basics of operational transformation. We have seen how operational transformation can be used to resolve conflicts in collaborative editing applications. We have also discussed the different strategies that can be used to resolve conflicts, and the factors to consider when implementing operational transformation.

I hope this has been informative. If you have any questions, please feel free to leave a comment below.

Thank you for reading!

Comments

[EchoGlobal]

You're absolutely right - managing updates in a multi-user concurrent system can be quite challenging. Your advice is spot-on.