26 Merging operations

(Sep 2005)

Abstract

This paper investigates merging of operations in such a way that inclusion transformation and exclusion transform are still supported, making it useful for overcoming the inherent quadratic complexity of inclusion transforming two lists of operations.

Introduction

In order for operational transform to be successfully applied to configuration management, it is necessary to efficiently merge branches containing hundreds of check-ins. Unfortunately, inclusion transform of two branches containing n1 and n2 operations involves n1n2 transformations which is prohibitive.

This paper assumes that each branch can be compressed into a single, concise state difference, and the brute force IT of the two branches is equivalent to IT of the two state differences.

For a text document, a state difference is represented as a set of extractions followed by a set of insertions. Merging, IT and ET are all implemented in linear time using a left to right scan of the intervals (see [1] and [2]). However the merging algorithm in [1] is incompatible with subsequent inclusion transform in [2] because identity of insertions and deletions is lost. Furthermore [1] doesn't account for the q-position.

IT/ET has been solved for assignment operations [3]. This paper investigates merging of assignment operations.

Notational conventions

For state S and operation O, S' = S+O denotes the state obtained after executing O on state S. Operation O may only be executed on state S. Therefore we define statein(O) = S.

Let id(O) denote the site identifier of the site on which O was originally generated. It is assumed there is a total ordering on site identifiers.

Two operations O1, O2 are equivalent (written O1 ~ O2) if statein(O1) = statein(O2) = S and S+O1 = S+O2. Note that this doesn't imply that the operations are equal. For example, it is possible that id(O1)≠id(O2).

[O1 ... On] denotes the list of operations O1,...,On assumed to be contextually serialised - i.e. intended to be performed in the given order on some initial state S. S + [O1...On] denotes the state (((S+O1)+O2)+...+On). [] denotes an empty list.

It is convenient to let [X1, ..., Xn] represent the list which concatenates the Xi which can be any mixture of lists or individual operations. For example [L1, L2, O3] concatenates list L1, list L2 and operation O3 into a single linear list of operations.

Inclusion transform

Let O1 || O2 and statein(O1) = statein(O2) = S. Then we define O1' = IT(O1,O2) as being a transformed version of O1 that maintains the original intention of O1, whilst being executed in the document state following execution of O2. i.e. statein(O1') = S+O2. Therefore [O2 IT(O1,O2] is contextually serialised.

List properties of IT

Let L1, L2, L3 be lists of operations. We require the following three properties

  • LIT1

    IT([], []) = []

  • LIT2

    IT(L1, [L2 , L3]) = IT(IT(L1, L2), L3)

  • LIT3

    IT([L1, L2], L3) = [ IT(L1,L3) , IT(L2, IT(L3, L1)) ]

It can be shown that IT([], L) = [], and IT(L, []) = L.

These properties can be regarded as a definition of IT(L1, L2). Note that this definition appears to be ambiguous in the way in which a list is decomposed into smaller sub-lists. However, it turns out that the final result is independent of the order in which the lists are decomposed.

Transformation properties of IT

  • TP1

    S + [O1 IT(O2, O1)] = S + [ O2 IT(O1, O2) ]

  • TP2

    IT( IT( O3, O1), IT(O2, O1)) = IT( IT( O3, O2), IT(O1, O2))

Merging operations

Given contextually serialised operations [O1, O2], we define O1 ⊕ O2 as the merge of O1, O2 into a single composite operation. Therefore the properties above also apply to O1 ⊕ O2 as it it represents a single operation. For example IT([], O1 ⊕ O2) = [], and IT(O1 ⊕ O2, []) = O1 ⊕ O2

Note that for contextually serialised operations [O1, O2], O2 ⊕ O1 is undefined.

Lists of operations can't be directly merged. i.e. L1 ⊕ L2, L ⊕ O and O ⊕ L are undefined.

We require the following properties.

  • MP1

    (O1 ⊕ O2) ⊕ O3 = O1 ⊕ (O2 ⊕ O3)

    (associativity)

  • MP2

    S + [O1 O2] = S + (O1 ⊕ O2)

  • MP3

    IT(O1, O2 ⊕ O3) = IT(O1, [O2, O3])

  • MP4

    IT(O1 ⊕ O2, O3) = IT(O1,O3) ⊕ IT(O2, IT(O3, O1))

MP1 ensures we can merge operations in any order.

MP2 ensures that merging operations doesn't affect the final document state.

MP3 ensures that merging doesn't change the effect on an operation as it IT's past the merged operations.

MP4 ensures that when a list of operations is IT'd past an operation, merging can be performed before or after the IT.

Given list L, let ∑L represent the result of merging all operations in L into a single composite operation. The order in which adjacent operations are merged doesn't matter by property MP1 (associativity of ⊕). We define ∑[] = [] and ∑[O] = O.

Lemma 1: IT(L, O1 ⊕ O2) = IT(L, [O1, O2])
Proof: (by induction on n = |L|)
n=0: IT([], O1 ⊕ O2) = [] = IT([], [O1, O2])
n=1: Follows directly from MP3
n→n+1:
Let L' = [O,L]. Then IT(L', O1 ⊕ O2)
= IT( [O,L], O1 ⊕ O2)
= [ IT(O, O1 ⊕ O2) , IT(L, IT(O1 ⊕ O2, O)) ] (because of LIT3)
= [ IT(O, [O1,O2]) , IT(L, IT(O1 ⊕ O2, O)) ] (because of MP3)
= [ IT(O, [O1,O2]) , IT(L, IT(O1,O) ⊕ IT(O2, IT(O, O1)) ) ] (because of MP4)
= [ IT(O, [O1,O2]) , IT(L, [ IT(O1,O) , IT(O2, IT(O, O1)) ] ) ] (because of inductive step)
= [ IT(O, [O1,O2]) , IT(L, IT([O1,O2], O) ) ] (because of LIT3)
= IT([O,L], [O1,O2]) (because of LIT3)
= IT(L', [O1,O2])

Lemma 2: IT(L, [L1,O2,O3,L4]) = IT(L, [L1, O2 ⊕ O3, L4])
i.e. When IT'ing past a list, we can merge any adjacent operations in the list without affecting the result.
Proof:
IT(L, [L1,O2,O3,L4])
= IT( IT( IT(L, L1), [O2,O3] ), L4] ) (because of LIT2)
= IT( IT( IT(L, L1), O2 ⊕ O3), L4] ) (because of Lemma1)
= IT(L, [L1, O2 ⊕ O3, L4]) (because of LIT2)

By repeated application of this lemma we deduce that ∀L1, L2, IT(L1, ∑L2) = IT(L1, L2).

Lemma 3: IT(O1 ⊕ O2, L) = IT(O1,L) ⊕ IT(O2, IT(L, O1))
This is an extension to MP4.
Proof : (by induction on n = |L|)
n=0: IT(O1 ⊕ O2, []) = O1 ⊕ O2 = IT(O1,[]) ⊕ IT(O2, IT([], O1))
n=1: Follows directly from MP4
n→n+1:
Let L' = [O,L]. Then IT(O1 ⊕ O2, L')
= IT(O1 ⊕ O2, [O,L] )
= IT( IT(O1 ⊕ O2, O) , L ) (because of LIT2)
= IT( IT(O1,O) ⊕ IT(O2, IT(O, O1)) , L ) (because of MP4)
= IT(IT(O1,O),L) ⊕ IT( IT(O2, IT(O, O1)) , IT(L, IT(O1,O)) ) (because of inductive step)
= IT(O1, [O,L]) ⊕ IT(O2, [ IT(O, O1) , IT(L, IT(O1, O)) ] ) (because of LIT2)
= IT(O1, [O,L]) ⊕ IT(O2, IT([O,L], O1)) (because of LIT3)
= IT(O1,L') ⊕ IT(O2, IT(L', O1))

Lemma 4: IT(∑L1, L2) = ∑IT(L1, L2)
Proof : (by induction on n = |L1|)
n=0: IT(∑L1, L2) = IT(∑[], L2) = IT([], L2) = [] = ∑[] = ∑IT([], L2) = ∑IT(L1, L2)
n=1: IT(∑L1, L2) = IT(∑[O], L2) = IT(O, L2) = ∑IT([O], L2) = ∑IT(L1, L2)
n→n+1: Let L1' = [O,L1]. Then IT(∑L1', L2)
= IT(∑ [O,L1] , L2)
= IT(O ⊕ ∑L1 , L2)
= IT(O, L2) ⊕ IT(∑L1, IT(L2, O)) (because of Lemma 3)
= IT(O,L2) ⊕ ∑ IT(L1, IT(L2,O)) (because of inductive step)
= ∑ [ IT(O,L2) , IT(L1, IT(L2,O)) ]
= ∑ IT([O,L1] , L2)
= ∑ IT(L1', L2)

TODO: Need to show that merging is compatible with achieving convergence at all sites.

Merging in practice

In [2] and [3], a comparison of site identifiers (which are assumed to be in a total order) is required to break symmetry in certain cases of operational transform, to allow all sites to converge at quiescence. This shows that site identifiers will need to be stored when merging operations.

In [1], a multi-char insert/delete operation stores a set of extraction intervals and insertion intervals. Each interval stores a string, p-position and q-position. Consider that it also stores a site identifier. In practice a site identifier needs to be fairly large in order to support global uniqueness. For example, a 128 bit GUID is suitable for this purpose. For space efficiency a site could use a local map from a 32 bit identifier to the 128 bit GUID. Therefore the overhead per interval is insignificant.

Note that the generating sequence number of the operation is not needed for operational transform, so this value doesn't need to be stored in the operation.

The result is that merging is able to compress edits by a given user, but not between users. This will still allow good compression because users tend to localise their work. A useful side effect is that any state difference returned by a repository will have all the information about what user did what.

Assignment operations

Assignment operations make use of a q-position - because an assignment is regarded as an insertion in the effects document. So under merging it is necessary to keep track of what was inserted where in the effects document. Therefore to support merging an assignment operation needs to store a set of insertion intervals, located by their q-position. It doesn't seem necessary to store all the values to be inserted in the effects document, apart from left most insertion by the operation, because we are never actually interested in the effects document apart from the value at position 0, and of course correctly transforming q-positions.

Note that we expect ET to work correctly with merged operations, making it clear that q-positions of assignments must be transformed as though no merging had taken place.

Problem

Consider that we compress a list of string-wise delete/insert operations. We must support compression of causally dependent operations. Therefore it is possible that an operation O1 inserts characters that are subsequently deleted by an operation O2.

We have assumed that after merging all operations we end up with a single set of deletion intervals, following by a single set of insertion intervals. This representation makes it impossible to represent the characters that were inserted by O1 then deleted by O2, because the characters aren't available to be deleted in the initial document state. This suggests that merging can't satisfy properties MP3, MP4.

One possibility could be to represent operations as a set of insertions following by a set of deletions! Now there is no difficulty representing characters that are inserted then subsequently deleted. A downside is that this doesn't relate easily to a move operation - because it is strange to insert before extracting. Nevertheless, this approach is promising enough to investigate more fully.

Merging is achieved as follows : [I1 X1 I2 X2] → [I1 I2' X1' X2] → [I X]. The initial transpose is different than the current approach.

It should still be possible to transpose operations, and dual IT operations. The order in which the steps are performed is different. However, the existing functions should still work - it is simply a matter of calling them in a different order.

References

[1] David Barrett-Lennard. Log Compression Algorithm. July 2005.

[2] David Barrett-Lennard. Operational transform - Multi-char insert and delete operations. Aug 2005.

[3] David Barrett-Lennard. Operational transform - Assignment operations. Aug 2005.