A Break In The Program

For reasons outside of my control I will be unable to continue to post articles on this blog, and won't be able to post Wave related articles in general. I hope that at some point I will be able to do this again.

I am also considering creating a new blog on other computer science related topics and I will post the link as an update to this post if I do decide to do this.

Thank you to everyone that read my posts, I hope you found them useful. Sorry I won't be able to continue them at present.

Operational Transformation and Composition Issue

This is a rather long and involved post, so best to read when you have a little time to put in. I finished the last post saying that I was going to next post on the algorithm for composing multiple operations together, prior to doing that I wanted to finish writing and testing that part of the WaveNZ code. In doing this I found there was an issue with my composing of operations, which I will get to soon, but first I will present the then algorithm for composition.

    public static MutateDocument compose(@NotNull MutateDocument first, @NotNull MutateDocument second) {
        if (!first.getDocumentId().equals(second.getDocumentId())) {
            throw new CompositionException(
                "Document ID's for documents to compose don't match: first = " +
                first.getDocumentId() + " second = " + second.getDocumentId()
            );
        }

        MutateDocument composed = new MutateDocument(first.getDocumentId());
        Iterator<MutationOperation> firstIter = first.getMutationIterator();
        Iterator<MutationOperation> secondIter = second.getMutationIterator();
        MutationOperation firstMutation = null;
        MutationOperation secondMutation = null;

        while ((firstMutation != null || firstIter.hasNext()) && (secondMutation != null || secondIter.hasNext())) {
            if (firstMutation == null) firstMutation = firstIter.next();
            if (secondMutation == null) secondMutation = secondIter.next();

            while (firstMutation != null && firstMutation instanceof DeleteCharactersImpl) {
                composed.addMutation(firstMutation);
                firstMutation = firstIter.hasNext() ? firstIter.next() : null;
            }

            while (secondMutation != null && secondMutation instanceof CharactersImpl) {
                composed.addMutation(secondMutation);
                secondMutation = secondIter.hasNext() ? secondIter.next() : null;
            }

            if (firstMutation != null && secondMutation != null) {
                Pair<MutationOperation> firstParts = firstMutation.split(secondMutation.getLength());
                Pair<MutationOperation> secondParts = secondMutation.split(firstMutation.getLength());

                if (secondParts.getFirst() instanceof SkipImpl) {
                    composed.addMutation(firstParts.getFirst());
                }
                else if (firstParts.getFirst() instanceof SkipImpl) {
                    composed.addMutation(secondParts.getFirst());
                }

                firstMutation = firstParts.getSecond();
                secondMutation = secondParts.getSecond();
            }
        }

        if (firstMutation != null) composed.addMutation(firstMutation);
        while (firstIter.hasNext()) {
            composed.addMutation(firstIter.next());
        }

        if (secondMutation != null) composed.addMutation(secondMutation);
        while (secondIter.hasNext()) {
            composed.addMutation(secondIter.next());
        }

        return composed;
    }

Composition is actually rather easy. In order to compose two operations against each other we need to relate one mutation in the first operation against a mutation in the second operation, say:

• first mutation in operation 1 is skip(4)
• the first mutation in operation 2 is deleteCharacters(2)

In order for these operations to be comparable against each other we need to make the area of the document that they are acting apon equal. To do this we split the mutations to make them a common size, i.e. skip(4) -> skip(2), skip(2) and deleteCharacters(2) -> deleteCharacters(2), null. Now we can compose skip(2) with deleteCharacters(2), which would give us deleteCharacters(2). The mappings for composition are:

• deleteCharacters, nothing -> deleteCharacters
• nothing, characters -> characters
• skip, deleteCharacters -> deleteCharacters
• characters, skip -> characters
• characters, deleteCharacters -> nothing

The first two composition mappings are where there is an issue. Both a deleteCharacters in the first operation and a characters in the second operation have a zero length in the common document state (i.e. the document state after the first operation and before the second operation). So if we have two operations:

• deleteCharacters(2)
• characters("ab")

Then it could be equally correct to have either of the following for the composition:

• deleteCharacters(2), characters("ab")
• characters("ab"), deleteCharacters(2)

And each of them would end up with the document being in the same state.

The OT white paper by David Wang and Alex Mah states that the following are requirements of the composition function:

• the composition B.A has the property that (B.A)(d) = B(A(d))
• transform(A,X) = (A',X') and transform(B,X') = (B',X'') implies transform(B.A,X) = (B'.A',X'')
• transform(X,A) = (X',A') and transform(X',B) = (X'',B') implies transform(X,B.A) = (X'',B'.A')

The first requirement states that applying the composition of the two operations to the document must change the document in the same way as applying the first operation then the second. The next two state that transforming an operation against the composite of two operations must be the same as composing the transformed operations if each operation is transformed in turn. These requirements together also mean that it must make no difference to the outcome of the document whether composition is used to aid the transformation process or not.

In the example above both ways of composing the operations satisfies the first requirement, but either way of composing the operations has a reasonably simple scenario that shows that the the other requirements are broken. The examples below show two scenario's one that works when insertion of characters is performed first but not deletion, and one that works when deletion is performed first but not insertion.

Examples
In all cases the start document is: abcd

Scenario One:
Client:

• c1 = deleteCharacters(1)
• c2 = characters("y")

Server:

• s = characters("0")

Without Composition:
Client:

• abcd -> c1 -> bcd
• bcd -> c2 -> ybcd

Server:

• abcd -> s -> 0abcd

Transformations:

• c1' = skip(1), deleteCharacters(1)
• s' = characters("0")
• c2' = characters("y"), skip(1)
• s'' = skip(1), characters("0")

Client:

• ybcd -> s'' -> y0bcd

Server

• 0abcd -> c1' -> 0bcd
• 0bcd -> c2' -> y0bcd

Result Document: y0bcd

With Composition:
Client:
Delete characters as operation going to common document and insert characters as operation coming from common document both have a zero length along common document, therefore one takes precedence....

Delete First:

• c1.c2 = deleteCharacters(1), characters("y")
• abcd -> c1.c2 -> ybcd

Transformations:

• (c1.c2)' = skip(1), deleteCharacters(1), characters("y")
• s' = characters("0"), skip(1)

Results:

• ybcd -> s' -> 0ybcd
• 0abcd -> (c1.c2)' -> 0ybcd

Doesn't match the without composition result.

Insert First:

• c1.c2 = characters("y"), deleteCharacters(1)
• abcd -> c1.c2 -> ybcd

Transformations:

• (c1.c2)' = characters("y"), skip(1), deleteCharacters(1)
• s' = skip(1), characters("0")

Results:

• ybcd -> s' -> y0bcd
• 0abcd -> (c1.c2)' -> y0bcd

Matches the without composition result.

Scenario Two:
Client:

• c = skip(1), characters("x")

Server:

• s1 = deleteCharacters(1)
• s2 = characters("y")

Without Composition:
Client:

• abcd -> c -> axbcd

Server:

• abcd -> s1 -> bcd
• bcd -> s2 -> ybcd

Transformations:

• c' = characters("x")
• s1' = deleteCharacters(1)
• c'' = characters("x"), skip(1)
• s2' = skip(1), characters("y")

Client:

• axbcd -> s1' -> xbcd
• xbcd -> s2' -> xybcd

Server

• ybcd -> c'' -> xybcd

With Composition:
Client:
As insert first worked above do this here.
Insert First:

• s1.s2 = characters("y"), deleteCharacters(1)
• abcd -> s1.s2 -> ybcd

Transformations:

• c' = skip(1), characters("x")
• (s1.s2)' = characters("y"), deleteCharacters(1)

Results:

• axbcd -> (s1.s2)' -> yxbcd
• ybcd -> c' -> yxbcd

Doesn't match the without composition result.

Delete First:

• s1.s2 = deleteCharacters(1), characters("y")
• abcd -> s1.s2 -> ybcd

Transformations:

• c' = characters("x"), skip(1)
• (s1.s2)' = deleteCharacters(1), skip(1), characters("y")

Results:

• axbcd -> (s1.s2)' -> xybcd
• ybcd -> c' -> xybcd

Matches the without composition result.

Conclusion
For composition with the given mutation set (i.e. skip, characters, and deleteCharacters) we cannot give a fixed rule as to whether to put a deleteCharacters from operation one ahead or behind of a characters from operation two. This property comes out of the asymetry of the transformation process, i.e. that if party A inserts characters at position 10 and party B inserts characters at position 10 one of the two operations has to go first, one of the parties has to be dominant. Alex Mah has made a suggestion that there may be a requirement for a different composition function for the dominant party over the submissive party, and changing my composition algorithm to reflect this solves the above example, i.e. when composing client operations the delete goes first, and when composing the server operations the insert goes first. BUT another issue came up, i.e. the following test failed:

    @Test
    public void thirdFailureTest() {
        List<MutateDocument> firstOperations = new ArrayList<MutateDocument>();
        List<MutateDocument> secondOperations = new ArrayList<MutateDocument>();

        firstOperations.add(createMutateDocument( deleteCharacters(1), skip(5), deleteCharacters(8) ));
        firstOperations.add(createMutateDocument( skip(1), characters("yRunFmyJ"), deleteCharacters(10), characters("p") ));

        secondOperations.add(createMutateDocument( characters("wEvque5f"), skip(10), deleteCharacters(15) ));
        secondOperations.add(createMutateDocument( deleteCharacters(14), characters("HL") ));

        verifyCompositionAndTransformation(firstOperations, secondOperations);
    }

This test comes out of a random test generator, and I haven't boiled it down to a more simple example like the above ones.

So what I have been doing over the past few days is trying to figure out a way to get around this composition problem. At present I am trying a change of the mutation set and experimenting with only having a skip and a replaceCharacters(deleteCount, insertCharacters) mutation. At present it passes all my previous tests, the two examples above, and the test case above. It is still failing the randomly generated tests though.

Hopefully I will have some more results from this to report within the next few days.

Operational Transformation and Composition

This is the third in the series of posts on Operational Transformation. The first gives a brief overview of operational transformation, while the second gives an algorithmic solution (in Java) of how to transform operations. This post will explain what happens when one party deviates from the other party by more than one operation.

Take the following example:
Party A and Party B both have the same initial start document: "abcd"
Party A applies the following operation sets one after another without receiving any operations back from Party B:

• "abcd" -> skip(2), characters("x") -> "abxcd"
• "abxcd" -> skip(1), deleteCharacters(1) -> "axcd"
• "axcd" -> skip(1), characters("y"), skip(2), deleteCharacters(1), characters("z") -> "ayxcz"

Party B in the mean time does the following operation prior to receiving any of these operations from Party A:

• "abcd" -> deleteCharacters(3), skip(1), characters("0") -> "d0"

The diagram below describes the steps that are required to perform OT in this situation:

Transformation Steps

Step 1: Pre Transformation
The diagram shows a representation of the document state space. At the start point the document has content of "abcd". A1, A2, and A3 show the operations that Party A has applied to the document, moving it to "abxcd", "axcd", and finally "ayxcz". B shows the single operation that Party B has applied to the document moving it to "d0".

Step 2: Transform A1 & B
Transforming A1 against B using the algorithm described in my last post gives:

• A1' = characters("x") = ("d0" -> "xd0")
• B' = deleteCharacters(2), skip(1), deleteCharacters(1), skip(1), characters("0") = ("abxcd" -> xd0")

Step 3: Transform A2 & B'
For step 3 we have to use B' to transform A2 against since the start document for the A2 operation is the point where B' starts from and not B. This gives us:

• A2' = null = ("xd0" -> "xd0")
• B'' = deleteCharacters(1), skip(1), deleteCharacters(1), skip(1), characters("0") = ("axcd" -> "xd0")

Step 4: Transform A3 & B''
Same as the last step, giving us:

• A3' = characters("y"), skip(1), deleteCharacters(1), characters("z") = ("xd0" -> "yxz0")
• B''' = deleteCharacters(1), skip(1), skip(1), deleteCharacters(1), skip(1), characters("0") = ("ayxcz" -> "yxz0")

Composition
So where does composition help us? The diagram below (along with step 1 from above diagram) should help with the understanding:


Step 2: A1, A2, and A3 composed
Firstly we compose A1, A2 and A3 into a single operation, this is done firstly by composing A1.A2 then (A1.A2).A3. I will explain this further in the next post but the idea is that you again walk along the operations as they relate to a common document, in this case the document between the two operations, so we have:

• A1: skip(2), characters("x")
• A2: skip(1), deleteCharacters(1)
• A1.A2: skip(1), deleteCharacters(1), characters("x")
• A3: skip(1), characters("y"), skip(2), deleteCharacters(1), characters("z")
• A1.A2.A3: skip(1), deleteCharacters(1), characters("y"), characters("x"), skip(1), deleteCharacters(1), characters("z")

Step 3: A1.A2.A3 transformed against B
Now that we have a single operation for A1.A2.A3 we can transform this directly against B, giving us:

• (A1.A2.A3)' = characters("y"), characters("x"), deleteCharacters(1), characters("z") = ("d0" -> "yxz0")
• B' = deleteCharacters(1), skip(1), skip(1), deleteCharacters(1), skip(1), characters("0") = ("ayxcz" -> "yxz0")

Next post will be on the algorithm for composing multiple operations together, and hopefully for clearing up all the confusion I have caused with this one.

By the way for people who don't go to the blog site and just receive the RSS feed I have added my twitter account onto the site (@brycenz), also for anyone on the wavesandbox for a first time I have put this post up there as well at: Operational Transformation and Composition

Operational Transformation Algorithm

After yesterdays post Introduction to Operational Transformation I received some feedback from a reader saying they were left a little confused by the more complex example, hopefully this post will clear up the confusion and provide you with an understanding of how both parties come back to a common representation of the document.

Firstly I will present you with an algorithm, in Java, that for the subset of operations I have chosen (skip, characters, and deleteCharacters) will produce the transformed operations that each of the parties needs to apply to their documents to reproduce the intention of the other parties operations. Note that I have not covered off all error conditions here.

   public static Pair<MutateDocument> transformOperations(MutateDocument first, MutateDocument second) {
       if (!first.getDocumentId().equals(second.getDocumentId())) {
           throw new TransformationException(
               "Document ID's for documents to transform don't match: first = " +
               first.getDocumentId() + " second = " + second.getDocumentId()
           );
       }

       MutateDocument firstTransformed = new MutateDocument(first.getDocumentId());
       MutateDocument secondTransformed = new MutateDocument(second.getDocumentId());
       Iterator<Mutation> firstIter = first.getMutationIterator();
       Iterator<Mutation> secondIter = second.getMutationIterator();
       Mutation firstOperation = null;
       Mutation secondOperation = null;

       while((firstOperation != null || firstIter.hasNext()) && (secondOperation != null || secondIter.hasNext())) {
           if (firstOperation == null) firstOperation = firstIter.next();
           if (secondOperation == null) secondOperation = secondIter.next();

           Pair<Pair<Mutation>> parts = splitMutations(firstOperation, secondOperation);
           firstOperation = parts.getFirst().getSecond();
           secondOperation = parts.getSecond().getSecond();

           Pair<Mutation> transformed = transformMutations(parts.getFirst().getFirst(), parts.getSecond().getFirst());
           if (transformed.getFirst() != null) {
               firstTransformed.addMutation(transformed.getFirst());
           }
           if (transformed.getSecond() != null) {
               secondTransformed.addMutation(transformed.getSecond());
           }
       }

       while(firstOperation != null || firstIter.hasNext()) {
           if (firstOperation == null) firstOperation = firstIter.next();
           firstTransformed.addMutation(firstOperation);
           firstOperation = null;
       }

       while(secondOperation != null || secondIter.hasNext()) {
           if (secondOperation == null) secondOperation = secondIter.next();
           secondTransformed.addMutation(secondOperation);
           secondOperation = null;
       }

       return new Pair<MutateDocument>(firstTransformed, secondTransformed);
   }

The code above iterates through the operations in each of the operation lists (contained in the MutateDocument operations) splitting the operations so that each pair of operations to be transformed against each other are the same length (excepting insertion of characters which matches against no opposing operation). The split method on Operation does the following:

• if length for split >= length of this operation then return [this operation, null]
• if length for split = 0 then return [null, this operation]
• otherwise return [new operation 0-length, new operation length-end] - note that the operation having split called on it is not modified

The getLength method returns the length of the operation in relation to the original content, i.e. characters has a zero length. The rest of the method is just for cleaning up remaining operations which will only ever be in one of the two lists, and then returning the pair of transformed operation lists.

   private static Pair<Pair<Mutation>> splitMutations(Mutation first, Mutation second) {
       if (first instanceof Characters) {
           return new Pair<Pair<Mutation>>(
               new Pair<Mutation>(first, null),
               new Pair<Mutation>(null, second)
           );
       }
       else if (second instanceof Characters) {
           return new Pair<Pair<Mutation>>(
               new Pair<Mutation>(null, first),
               new Pair<Mutation>(second, null)
           );
       }
       else {
           return new Pair<Pair<Mutation>>(
               first.split(second.getLength()),
               second.split(first.getLength())
           );
       }
   }

The above code is how splitting is done, the insertion of characters has to be done outside of the split method for me at the moment, still thinking about how to bring this back in. Once the operations to be transformed against each other are calculated they are passed into the transformMutations method (below) and the results are added to the resulting transformed operations lists.

   private static Pair<Mutation> transformMutations(Mutation first, Mutation second) {
       // characters, nothing -> characters, skip
       if (first instanceof Characters) {
           return new Pair<Mutation>(first, new Skip(first.getLength()));
       }

       // nothing, characters -> skip, characters
       if (second instanceof Characters) {
           return new Pair<Mutation>(new Skip(second.getLength()), second);
       }

       // skip, skip -> skip, skip
       if (first instanceof Skip && second instanceof Skip) {
           return new Pair<Mutation>(first, second);
       }

       // delete, delete -> nothing, nothing
       if (first instanceof DeleteCharacters && second instanceof DeleteCharacters) {
           return new Pair<Mutation>(null, null);
       }

       // delete, skip -> delete, nothing
       if (first instanceof DeleteCharacters && second instanceof Skip) {
           return new Pair<Mutation>(first, null);
       }

       // skip, delete -> nothing, delete
       if (first instanceof Skip && second instanceof DeleteCharacters) {
           return new Pair<Mutation>(null, second);
       }

       return new Pair<Mutation>(null, null);
   }

The code above does the actual transformation of one operation against another operation. These are as follows:

• characters, null - the insert characters operation goes through unchanged into the transformed first operations, however a skip needs to be added into the transformed second operations since all later operations have to be moved by the number of characters in the insertion
• null, characters - as above
• skip, skip - same operation so both just get passed through
• delete, delete - neither party's content contains the related characters anymore so both these operations can be dropped
• delete, skip - the delete passes through, the characters that this skip was done against no longer exist in the other parties content so the skip is dropped
• skip, delete - as above

To recap on the operations in the previous post:

• Party A: characters("a "), skip(2), characters("c "), skip(2), deleteCharacters(4) => "a A c B E "
• Party B: characters("b "), skip(6), characters("d "), skip(2), deleteCharacters(2) => "b A B C d D "

Now running these through the algorithm above we get:
The insert is passed through for Party A, and a skip needs to be added into Party B's transformed operations so that when they are applied to Party A's document the insert goes after Party A's initial insert.

• Party A Transformed: characters("a ")
• Party B Transformed: skip(2)

As above but opposite.

• Party A Transformed: skip(2)
• Party B Transformed: characters("b ")

Both sets of operations have a common skip(2).

• Party A Transformed: skip(2)
• Party B Transformed: skip(2)

Like the above insert operations, but these characters get placed in the middle of Party B's skip operations (when the transformed operations from party A are applied to Party B).

• Party A Transformed: characters("c ")
• Party B Transformed: skip(2)

We are still going through Party B's skip(6) and are onto Party A's skip(2), the skip(6) has now been split into 3 lots of skip(2).

• Party A Transformed: skip(2)
• Party B Transformed: skip(2)

We have a skip(2) from Party B to match against a deleteCharacters(4), which means the deleteCharacters(4) gets broken down into 2 deleteCharacters(2), matching a delete against a skip gives us.

• Party A Transformed: deleteCharacters(2)
• Party B Transformed: null

Now we have a characters("d ") in Party B's stream.

• Party A Transformed: skip(2)
• Party B Transformed: characters("d ")

Again a skip(2) from Party B to match against the remainder of the deleteCharacters(4) (i.e. now deleteCharacters(2)).

• Party A Transformed: deleteCharacters(2)
• Party B Transformed: null

And then the final deleteCharacters(2) from Party B.

• Party A Transformed: null
• Party B Transformed: deleteCharacters(2)

Giving Us:

• Party A Transformed: characters("a "), skip(2), skip(2), characters("c "), skip(2), deleteCharacters(2), skip(2), deleteCharacters(2)
• Party B Transformed: skip(2), characters("b "), skip(2), skip(2), skip(2), characters("d "), deleteCharacters(2)

Applying Party A Transformed to Party B's current document gives us: "b A B C d D " => "a b A c B d "
And Party B Transformed to Party A's current document: "a A c B E " => "a b A c B d "

And thank goodness after writing that all out they match! I am not going to go into composition today as this is long enough. So the next post will be on composition and how it helps with OT.

Please note that in order to get this blog out tonight rather than waiting another day I had to miss out on writing unit tests for the code. This code is part of the wave federation server I am writing and in fact the only unit test this particular code has at the moment is the example used in this and last post, so if anyone is wanting to use this code go ahead, but be warned it is not thouroughly tested.

Introduction to Operational Transformation

Firstly I would like to acknowledge the time that a number of the Google Wave engineers have given to discuss their individual areas with me. It has been great being able to learn from the people involved in the creation of this amazing product. Thanks again to you all for your time and knowledge.

I am unsure what exposure you the reader have had to Operational Transformation (OT) in the past, if you are like me then prior to reading about the implementation of Google Wave you had zero knowledge of this area of computer science. OT is a technology for supporting concurrent editing of single shared document by a number of parties. OT provides for a way of transmitting the edits that one party is performing against the document to all other parties, but much more importantly it provides a way to fix issues that arise along the way from concurrent edits being performed.

For introducing OT I will be using a subset of the operations within Google Wave. The operation set is as follows:

• skip(count)
• characters(characters)
• deleteCharacters(count)

Simple example
Two parties share an initial document state of: "Test Document"

Parties A and B each concurrectly perform an edit of the document.

• Party A: skip(5), characters("This ") => "Test This Document"
• Party B: deleteCharacters(5) => "Document"

If each of these operations were passed directly to the other party and applied against their document state we would have the following:

• Party A: deleteCharacters(5) => "This Document"
• Party B: skip(5), characters("This ") => "DocumThis ent"

Obviously there is a problem here. This is where the fundamental aspect of OT comes into play, i.e. the transformation of an incoming operation in relation to the operations that have been performed locally. In the case above Party B has ended up with an incorrect resultant document state due to not transforming the incoming skip operation from Party A. It should be able to be seen how this could be very easily fixed though, i.e. if we take into account the deletion of 5 characters by Party B then result is:

• Party B: skip(0), characters("This ") => "This Document"

Party A has no requirement to modify the incoming operation from Party B since no changes were made on Party A's document that influence the result of applying the operation from Party B.

More Complex:
Two parties share an initial document state of: "A B C D E "

Parties A and B each concurrently perform an edit of the document.

• Party A: characters("a "), skip(2), characters("c "), skip(2), deleteCharacters(4) => "a A c B E "
• Party B: characters("b "), skip(6), characters("d "), skip(2), deleteCharacters(2) => "b A B C d D "

This example is more difficult to visualise and easily say what the correct result is. To help us visualise the transformation I will use a slightly adapted version of a form of diagram Alex Mah uses.

Diagram showing the original operations that Party A and Party B apply to their documents (blue showing insert, gray skip, and red delete). The original document is shown in the middle with the resulting document at Party A and Party B shown at top and bottom respectively.

Diagram showing the transformed operations that Party A applies (at top denoted by Party B'), and that Party B applies (at bottom denoted by Party A'). This brings both documents back into line with the result being the middle document. Of particular interest to note:

• Two inserts are at the same position at the beginning, on gets chosen to go first, this must be predefined so that both ends perform the same operation.
• The delete of 4 characters has been split into two deletes of 2 characters to allow for the insert of "d ".

Tomorrow I will provide an algorithmic way of creating the transformed operations Party A' and Party B', as well as discussing composition, and what happens when one side moves furthur away and how composition alleviates some performance issues in this case.