18.1 Multi-character CDM operations

20 February 2008

Introduction

In this paper we provide an algorithm for operational transform on multi-character CDM operations on text documents. It extends the work from [1] which only concerned single character operations.

CDM = Create, Delete, Move

To support multi-characters we use half open intervals to efficiently represent ranges of characters to be created, deleted or moved.

Information preserving merging

In this implementation we are interested in support for merging of operations that is information preserving. Basically this means that the merge of operations is compatible with IT and ET. Nevertheless we still refer to merging as providing log compression - the hope being that half open intervals will coalesce where possible, reducing the storage requirements and subsequent processing time.

From [2] we have the following:

Given contextually serialised operations [O₁, O₂], we define O₁ ⊕ O₂ as the merge of O₁, O₂ into a single composite operation.

We require the following properties

MP1

(O₁ ⊕ O₂) ⊕ O₃ = O₁ ⊕ (O₂ ⊕ O₃)   (associativity)

MP2

S + [O₁ O₂] = S + (O₁ ⊕ O₂)

MP3

IT(O₁, O₂ ⊕ O₃) = IT(O₁, [O₂, O₃])

MP4

IT(O₁ ⊕ O₂, O₃) = IT(O₁,O₃) ⊕ IT(O₂, IT(O₃, O₁))

Aliasing extraction intervals

In order to support information preserving closure under merging of concurrent operations we allow for multiple extraction intervals to alias the same characters in an effects document.

In the interests of a well understood declarative meaning, we assume that characters can only be aliased at the post-operation locations. Therefore there will never be aliasing with the extraction of an enabled move operation (because the characters are really somewhere else).

Merging of chaining move ops

Let D_a, D_b, D_c refer to three different locations for a contiguous range of characters in the effects document.

Let O₁ move from D_a to D_b, and O₂ from D_b to D_c. Then O₁ ⊕ O₂ moves directly from D_a to D_c.

Our approach is to still think of O₁ ⊕ O₂ as two distinct moves (as before), except there is no sense in which its internal representation can be regarded as a time ordered sequence of moves. Basically this means that the extraction of O₂ must be ET'd backward past the move performed by O₁. The result is that both of the moves alias the same extraction location D_a.

Extraction intervals must support aliasing

Aliased extraction intervals aren't particularly pleasant for an implementation. So it's worth establishing that they cannot be avoided.

Let O₁,O₂,O₃ all move the same character to different locations with O₁ || O₂ || O₃ and O₁.id < O₂.id < O₃.id.

Let O₃' = IT(O₃,O₂). Consider that we merge [O₂,O₃'] into a single operation and transform past O₁. Then we expect that we will have two disabled extraction intervals that each track to the destination position of O₁.

Conclusion : Merging requires that we support aliasing of extraction intervals.

Deletes must be in post creation coordinates

Let the initial state S consist of a single character 'a' in the effects document, marked as present and not deleted.

On state S, we apply O₁ = insert 'b' at q = 0, to yield the following state

On this state we apply O₂ = delete 'b' at q = 0, to yield the following state

This example shows that in order to support merging of operations we must use post insertion coordinates for the deletion O₂ in order for it to be able to reference the character inserted by O₁.

Extractions must be in post creation coordinates

Let the initial state S consist of a single character 'a' in the effects document, marked as present.

On state S, we apply O₁ = insert 'b' at q = 0, to yield the following state

On this state we apply O₂ = move b at q = 0 to q = 2, to yield the following state

This example shows that in order to support merging of operations we must use post insertion coordinates for the extraction by O₂ in order for it to be able to reference the character inserted by O₁.

Declarative rule on extraction positions

When we merge operations we can have chains of moves - e.g. suppose we have the sequence of operations [O₁ O₂ O₃] where O₁ → O₂ and O₂ → O₃. O₁ moves a character, and this character is in turn moved by O₂, which in turn is moved by O₃.

Under merging (i.e. O₁ ⊕ O₂ ⊕ O₃) we need to specify what happens to the extraction intervals.

There are two different concepts of character identity, defined as follows

Aliasing of extraction intervals means that a single operation O may need to reference a given w-character more than once.

Rule: Let operation O be performed on state S. Let w be a given w-character. w may be involved in multiple moves or deletes. It is required that all extraction positions are associated with a well defined e-character x(S,w). This is defined as follows

if w ∈ W(S) then    x(S,w) = echar(S,w)
else                x(S,w) = ecreate(w)

Implementation of CDM operations

A CDM operation records the following double linked lists on each text field of each object

1. Creation intervals
2. Delete intervals
3. Move insertions
4. Move extractions

The implementation requires that every interval be non-empty.

These linked lists are homogenous, allowing the implementation to avoid run time polymorphism or discriminated unions.

Creations

The following depicts a double linked list of creation intervals recorded on a single text field. The intervals are ordered by q-position.

Creation intervals never overlap in q-coordinate.

Each creation interval records the following information

• The (s,t) associated with the operation that generated the creation
• The string being created
• The q-position for where to insert the string.

It is important to understand that an original generated operation can perform arbitrary many creations, deletions and moves, and under merging with other operations, we end up with linked lists of intervals with a mixture of (s,t) values. Hence the information for a single operation can be interspersed with other operations under merging.

The creation q-positions are expressed in post-creation coordinates. Conceptually this means we are specifying their final q-positions after the creations have all been applied (but before the moves). In practice this means we can apply the operation by simply iterating forwards through the linked list inserting the intervals as we go, knowing that each interval's q-position accounts for all the intervals that have already been inserted on its left.

Deletions

Deletion intervals are also stored in a double linked list ordered by q-position. However unlike creations, deletion intervals can overlap (alias). This corresponds to the case where multiple users have concurrently deleted the same text. The implementation splits intervals as required so that aliased intervals are always exactly equal in size. i.e. we require that the next interval either perfectly overlaps with the previous interval or else be further to the right, without any overlap.

Each deletion interval records the following information

• The (s,t) associated with the operation that generated the deletion
• The string being deleted
• The q-position for where to delete the string.

In the implementation aliasing intervals are ordered by site identifier. Therefore the deletion intervals are totally ordered.

The deletions are expressed in post-creation coordinates.

During OT it may be necessary to split delete intervals. The following figure depicts the result after splitting.

Moves

A move represents both an extraction from one text field as well as an insertion into another. Therefore a move interval takes part in two double linked lists at the same time! In the following diagram a single move interval stores four pointers prevX, nextX, prevI, nextI, in order to take part in a double linked list of extractions (shown along the top of the figure), as well as a double linked list of insertions (shown along the bottom of the figure). Each of these double linked lists is in q-position order.

Each text field records a double linked list of extractions and a double linked list of insertions. A given move interval can take part as an extraction on one field and an insertion in an entirely different field. i.e. we are able to model moves between different text fields (in different objects). Of course this representation allows for moves within a single text field or between different text fields in the same object.

Each move interval records the following information

• (s,t) of the operation that generated the move
• e coordinate (used to pick a unique winner amongst competing moves)
• insertion q-position
• extraction q-position
• the value of the string being moved.

Moves extractions and insertions are expressed in post-creation, post-move-insertion, pre-move-presence coordinates.

Like creation intervals, move insertion intervals are strictly ordered by q-position without any overlap. i.e. they are not able to alias.

Move extraction intervals are able to alias in the same manner as deletion intervals. For example

As for deletion intervals, we require that the next interval either perfectly overlaps with the previous interval or else be further to the right, without any overlap.

The aliasing extraction intervals (which have the same q-coordinate) are ordered by e-coordinate. Note that e-coordinates will always be distinct so the ordering on all the extraction intervals is uniquely defined.

It must be kept in mind that each of the above extraction intervals independently takes part in a linked list of move insertions. As a result, splitting a move interval is a little tricky. It is necessary to split all the other move intervals that it aliases with as an extraction, and account for the fact that each interval takes part in two linked lists at the same time.

Ordering aliasing move extractions by e coordinate

Consider that we need to dual IT operations O₁, O₂ where both operations have performed around 100 moves of the same text interval.

The dual IT of extractions against extractions needs to perform the following

if (O2.e < O1.e || O2.e == O1.e && O2.id < O1.id) ++O1.e; else ++O2.e;

to transform e coordinates (used to select a unique winner amongst all competing move operations).

In this scenario there would be 100 x 100 = 10000 combinations to compare. A linear version of the algorithm involves sorting the competing moves by e-position and using an accumulating shift in the e-position, reducing time complexity to 100 + 100 = 200 - a significant saving.

The extractions of competing moves are sorted by e-position. Furthermore they are expressed in post insertion coordinates in the hypothetical effects document associated with e-positions. Repeated e-coordinates should be impossible. The following is an example

    [-----)      [--------) e=0        [--)        [-----)
                 [--------) e=3                    [-----)
                 [--------) e=5                    [-----)
                 [--------) e=6
                 [--------) e=20

Thinking in terms of post insertion e-coordinates is very powerful - it uniquely forces certain behaviour when merging operations. For example suppose O₁ → O₂ and we have chaining moves. Then when we merge to get O₁ ⊕ O₂, we will need to 1) track O₂'s source position back to O₁'s source position (so all competing moves are collected together) and 2) bump O₁'s e-position to allow for the insertion to the left by O₂ (which is deemed to dominate O₁). So we see that merging can cause e-positions to be adjusted for causally dependent operations!

Applying an operation

Applying an operation is performed in four phases

1. Apply creations. This involves insertion of characters that are marked as present but not deleted.
2. Apply deletions. This involves setting the deleted status (if not set already)
3. Apply move insertions. This involves inserting characters that are marked as present if and only if the interval has e = 0, and the deleted status is false.
4. Apply move extractions. For each interval that has e = 0, we mark the source character as no longer present, and move the deleted status.

Merging

[O1 O2] = [ I1  X1       I2   X2 ]

        = [ I1  I2       X1'  X2 ]   X1' = IT(X1,I2)
                                      (shift X1 to right to account for insertions by I2)

        = [     I2'      X1'  X2 ]   I1' = IT(I1,I2)
              I1'                     (shift I1 to right to account for insertions by I2)

        = [     I2'      X1'     ]   X2' = (O1.type == MOVE && X2 == I1') ? X1' : X2
              I1'      X2'             (track X2 to X1' for overlaps with I1')

        = [ I X ]                       I = merge(I1',I2'), X = merge(X1',X2')

All q-positions in the merged result [I X] will be expressed in the coordinate system associated with performing all insertions - i.e. both I₁ and I₂. I₂ and X₂ are already expressed in this coordinate system and therefore don't need to be shifted.

Both I₁ and X₁ are expressed in post I₁ coordinates and therefore require shifting to account for the insertions by I₂.

Let O₁ be performed on state S. Then [I X] will also be performed on state S. Therefore any e-char referenced by X₁ doesn't require adjustment (tracking). However X₂ may possibly require tracking - in those cases where X₂ matches an e-char inserted by a move by O₁.

We test X₂ against I₁' not I₁ so they are in the same coordinate system (i.e. post I₁ and I₂).

We track X₂ to X₁' not X₁ because it is necessary to account for the insertions I₂.

Repository

The repository is characterised by storing all operations from when the effects documents were initially empty. This allows the intervals to avoid the need to store q-positions. Instead, q-positions (and p-positions) of intervals are thought of as a function of a given vector time.

Consider what x(S,w) reduces to when S is the initial state of the system where all effects documents are empty.

if w ∈ W(S) then    x(S,w) = echar(S,w)
else                x(S,w) = ecreate(w)

becomes

x(S,w) = ecreate(w)

i.e. it suggests that move intervals should always reference the original insertion position of a given w-char.

In that light, consider the following model

// abstract base
struct Insert
{
    SiteId s;
    int t;
    Insert* prevI;
    Insert* nextI;
};

struct Create : public Insert
{
    String str;
    set<pair<SiteId,int> > deleted;
    Move* firstX;      // can be NULL if no moves have been performed
};

struct Move : public Insert
{
    Create* srcCreate;
    Move* prevX;
    Move* nextX;
};

There are two types of insertion interval : creation and move. Both represent an insertion of an interval into a particular effects document. An insertion interval stores pointers prevI, nextI in order to take part in the double linked list of insertion intervals in a total ordering (by q-position) within a given effects document.

Effects     firstI          nextI
document ------------>[move)-->--[ create )-->--[move)-->--[   move     )-->--[ create )-->--0
               0 --<--      --<--    \ \ --<--        --<--              --<--
                            prevI     \ \
                                       \ \
                                       _\| \     srcCreate
                               firstX    \ \-------<-------------<-----------
                                          \    |             |              |
                                           \   |             |              |
                                            \ |     nextX    |              |
                                          [ move )-->--[ move )-->--[ move )-->-- 0
                                   0 --<--          --<--         --<--
                                                    prevX

Only a creation interval needs to store the string of characters being inserted. A move interval can quickly find its associated string because it stores a pointer 'srcCreate' directly to the unique creation interval that originally inserted the string being moved.

Pure deletions are handled by recording their (s,t) in a set within the creation interval that originally inserted the string. Deletions take precedence over moves (i.e. a string marked as deleted is deleted regardless of where it is moved).

All moves for a given string form a single double linked list using pointers Move::prevX and Move::nextX. Create::firstX points at the head of the linked list. The moves are ordered by e-position. Therefore it can be assumed that for a given vector time v, we can traverse the linked list in order and the first interval with t < v(s) represents the real location of the string at vector time v. If no Move satisfies t < v(s) then the string is assumed to reside at the creation position. In particular this is the case if there are no moves and firstX = NULL.

Calculating suffix/prefix of an operation for a given vector time

The idea is to avoid the whole idea of a history buffer and instead record all changes that have been made in a session in a single growing operation. Latecomers can be brought up to date very efficiently by sending them the operation.

If a client goes down and reconnects during a collaboration it should be possible to use the received vector time to decompose an operation O into two pieces O₁,O₂ such that O ~ [O₁ O₂], and O₁ is in the context of the vector time, and O₂ represents all the operations that need to be sent to the site. This allows the site to be brought up to date very efficiently. It also provides the "suffix" which is used to transform incoming operations during the normal processing of a collaborative session. Decomposition of the suffix is needed as operations are received that have an increasing context (i.e. associated vector time).

Implementation notes

Let an operation store a double linked list of move/create intervals. We certainly need polymorphism in this list.

The fact that moves will always reference ecreate(w) or echar(S,w) means that it is easy to execute a move operation without it actually storing the string. i.e. only Create intervals need to store the string.

To reduce the needs for polymorphism it is assumed that deletes are stored separately to moves. During IT, deletes and moves must be independently shifted right as required.

More radical again

Consider that creates and moves are not stored in the same double linked list!

O ──▶ linked list of creates
     linked list of moves
     linked list of deletes

Let creates be in post-creation coordinates. Let moves/deletes be in post-create+move coordinates

This eliminates the need for polymorphic intervals. They are CDM operations (Create-Move-Delete)

Advantages of this approach

• it is more likely that adjacent creates/moves or deletes can merge.
• more space efficient - there is no redundant state, and no type indicator
• serialisation doesn't need dynamic creation
• algorithms are more readable
• algorithms are hard-coded against specific types so they're faster
• string is only stored by create intervals
• Specialisation to not supporting moves is trivialised.

Tests

The algorithm was tested by simulating between two and nine sites making randomly generated multi-character create, delete and move operations across multiple documents and exchanging operations in arbitrary causally valid orders. Generated operations combined between one and four atomic operations using the merge algorithm. Convergence was checked repeatedly between sites during each simulation and across all sites after every operation had been exchanged. Sites were required to agree on every effects document in full.

A total of 3,000 simulations of 300 events each completed without a convergence failure. The number and variety of operations, sites and exchange orders covered by this testing provide very high confidence in the correctness of the algorithm.

Browse the test files.

References

1. David Barrett-Lennard, Operational Transform — Single-Character Move, Insert and Delete Operations, April 2007.
2. David Barrett-Lennard, Operational Transform — Merging Operations, September 2005.

Source code

The surviving MultiCharCDMOp implementation contains the interval representation, application, transformation, transposition, merging, serialization, and randomized-test support described by this paper. Browse the source files.

Source

View the archived PDF.