How to write beWeeVee enabled software – Part 1

In the process of preparing the SDK for public consumption, I have been writing some stuff that may be of interest to understand how beWeeVee works under the hood.

Overview

The basis of the beWeeVee engine is an Operational Transformation that has been designed to work with standard .Net collections. Operational Transformation (OT) is a technology that allows a wide range of collaboration functions. In short it allows to synchronize shared copies of data structures achieving convergence, no matter how many processes are involved in modifying it at the same time. Typically OT Frameworks are composed of an OT function and a Concurrency Control algorithm that ensure Causality Preservation, Convergence and Intention Preservation (CCI Model).

BeWeeVee achieves synchronization of shared copies using an OT function that is formally proved to achieve convergence and intention preservation and a concurrency control protocol that allows to execute the operations performed over the copies in a P2P distributed system.

The concurrency control algorithm determine:

1. Which operation should be transformed against which causally ready operation,
2. The order of the transformations to be performed,

while the Transformation function define how different operations are transformed.

The basic idea is that given a linealizable data structure, you can signal beWeeVee of any Insert and Delete operation performed over a data structure allowing it to be modified by several parties without violating the CCI model. That frees you (the developer) of ensuring that the data structure of the parties are equal.

BeWeeVee provides a low level API that allows the developer to notify the concurrency control algorithm of the changes (Operations) that were performed externally to the data structure and the Operations that arrive from the external sites. There are 3 types of operations that the ConcurrencyController may know about:

- Insertion operations,
- Delete operations and
- Identity Operations.

The latter is for internal use and really it doesn’t have any use from the users point of view. On the other hand, Insertion and Deletions are the basic operations that in the end allows the shared copies to be synchronized.

BeWeeVee also provides a high level API that provides the ability to create synchronizable lists that perform all the signalling necessary by themselves. The ITextView and the IElementView<T> are those; they are optimized for random insertions and deletions and allows you to handle Text in the first, and any Serializable type in the latter. Other mapping mechanisms to handle non serializable types are also in place.

BeWeeVee supports discrete revisions but the Low Level API provided by this CTP is poised to be deprecated in favor of continuous snapshots and playback abilities. Playback is a feature that allows any party to start from a predefined moment in time and transform back and forth the data structure to see what was the state at any moment in time. The Playback feature API is not being released in this CTP but it is an intrinsic property of how beWeeVee solves the concurrency problem.

How Operations work.

The operations are the basis of the beWeeVee synchronization engine, and as such the building block of any application using the Operational Transformation Engine. For simplicity we are going to do an example based on text (the usual OT example), even though the approach is valid for other data structures, not just text.

Given a text document with a string “abc” replicated at two collaborating sites; and two concurrent operations generated by two users at collaborating sites 1 and 2, respectively. We get:

O1 = Insert[0, "z"] (to insert character “z” at position “0″)
O2 = Delete[2] (to delete the character at position “2″, note that in this case we are deleting “c”)

Now supposing the two operations are executed in the order of O1 and O2 (at site 1). If we execute O1 first, the document becomes “zabc”; when we execute O2 after O1 the operation Delete[2] would delete “b” instead of the generating site intention that was deleting “c”. Therefore O2 must be transformed against O1 to become: O2′ = Delete[3, "c"]. The end result is that the positional parameter is incremented due to the prior insertion of “z” in O1. When we execute O2′ on “zabc” we are deleting “c” and the document becomes “zab”. The OT transformation will adjust the positional parameter of an operation according to the intended effect of the generating site when presented with concurrent operations, so all sites converge and maintain consistency.

The ConcurrencyController’s Low Level API is responsible in beWeeVee of all the housekeeping necessary to perform the required transformations so the developer get notified of the correct operation to perform on the data structure. Luckily for the majority of developer beWeeVee already provides High Level API constructs for text and typed serializable objects lists. Even though creating your own is not that difficult either, full source code for the ITextView and IElementView<T> is provided as examples.

This is the end of Part 1, in the next we will explain what ITextView and IElementView<T> are and how to use it in a simple way.