31 Vector<T> operations

Per field HB suffixes

We can achieve some benefit by recording the HB suffix on a per-field basis, as follows

When a remote operation is to be transformed against the HB suffix we deal with each field independently. For a given field we transpose and pop according to the execution context of the remote operation. Then we perform the dualIT against the contextually serialised sequence of operations for a given field in the normal way.

This approach can lead to a dramatic reduction in the CPU load when remote operations and/or local operations work are distributed over a number of different fields. Of course there is no benefit when there is substantial work on a single vector<T> field to be merged.

17.2 Merging a list of operations

Let O1,O2 be contextually serialized. Let O1 have n1 insertion intervals and O2 have n2 insertion intervals on a given vector<T> field. The merge O1 ⊕ O2 involves a linear scan through both sets of intervals. We estimate the cost as O(n1+n2).

Consider a list L = [O1, O2, …, On] of n contextually serialized operations where each operation contains a single insertion interval into a given vector<T> field. Let this list be merged to become M = ∑L as follows 


Operation M;	// M is initially empty
for each Oi in L
    M = M ⊕ Oi;

If none of the intervals can be coalesced then the merge results in n intervals, and yet the cost is (0+1)+(1+1)+(2+1)+(3+1)+…+(n-1+1) = n(n+1)/2 which is O(n­2).

A better strategy is to tend towards merging roughly equal sized lists, in the manner of merge sort. For example:

At each level of the tree the total number of insertion intervals to be processed is the same – ie O(n). The height of the tree is O(log n). Therefore the effort to merge the list is O(n log n).

17.3 Does merging improve performance of DualIT?

Let L1, L2 be lists of contextually serialised operations where each operation contains a single insertion interval. The dualIT transforms every operation in L1 with every operation in L2, so the algorithm is O(|L1||L2|).

Consider that L1 is merged into a single operation denoted by ∑L1, and we are unlucky in that none of the intervals are adjacent (and managed to coalesce).

Then the dualIT of ∑L1 and L2 is still O(|L1||L2|) - ie merging only one of the lists hasn’t eliminated the quadratic complexity!

Now consider that we dualIT after merging both lists into single operations:

Now the cost is O((|L1|+ |L2|) – a great improvement.

17.4 Efficient R-factorization

Let M be a composite operation and v be a causally valid vector time satisfying

vin(M) ≤ v ≤ vout(M).

We want to efficiently calculate the R-factor of M with respect to v, which is denoted by

Rf(M,v) = ∑[v,vout(M))

First let’s limit ourselves to insertion operations on a single vector<T> field. Then M records a list of insertion elements (which we henceforth call “insertion intervals”) ordered by q position. Note that the q positions are in post insertion coordinates. Each interval records

  • the (s,t) associated with the original operation that generated the insertion of this string
  • the q position
  • the string being inserted at this q position

Claim: Rf(M,v) is obtained from M by simply removing every insertion interval with (s,t) satisfying t < v(s). There is no need to split or merge intervals, and no need to adjust q-positions!

Justification for not adjusting q positions: The intervals of Rf(M,v) are expressed in post creation intervals which corresponds to the state associated with vout(Rf(M,v)). The intervals of M are expressed in the state associated with vout(M). But vout (Rf(M,v)) = vout(M) so q positions don’t require adjustment.

Now consider Create+Delete operations on a vector<T> field. The deletion intervals are ordered by q-position and also expressed in post-creation coordinates relative to vout(M). Therefore, again we find there is no need to adjust q positions when we remove deletion intervals with (s,t) satisfying t < v(s).

17.5 Efficient L-factorization

Let M be a composite operation and v be a causally valid vector time satisfying

vin(M) ≤ v ≤ vout(M).

We want to efficiently calculate the Lfactor of M with respect to v, which is denoted by

Lf(M,v) = ∑[ vin(M),v)

Claim: The insertion intervals of Lf(M,v) are found by

  1. Removing intervals with (s,t) satisfying t ≥ v(s)
  2. Shifting remaining q-positions to the left according to the total size of all intervals to the left that have been removed up to that point.

This suggests that the algorithm will use a left to right scan, calculating a negative offset to be applied to q-positions.

17.6 Merging the transient HB suffix

It is only worth merging the HB suffix into a single operation if the remote operations tend to have multiple insertion intervals, or else batches of remote operations are merged in order to avoid dualIT against lists of operations where each operation only contains about one insertion interval.

Compressing a batch of remote operations into a single operation seems like a good idea, although it is not clear how to recover the individual remote operations that were processed in a batch as a single merged UniOperation.

17.7 The equivalent of transpose and pop on a merged HB suffix

We need to be able to evolve the HB suffix over time (ie to remove operations from the merged suffix).

Consider that a remote operation Or is received with execution context v. In other words, the input state on which Or is meant to be executed is the same state that arises when applying exactly the operations in 𝜒(v). Note therefore that v must be causally valid vector time v satisfying v ≤ hv, where hv denotes the vector time defining the current content of the entire HB.

The equivalent of a transpose and pop simply involves the calculation of the R-factor of the HB-suffix with respect to the execution context of the next remote operation Or to be transformed against the HB-suffix.

The efficient calculation of an R-factor has been described above.

17.7.1 t-chains

Consider that for each site id, insertion intervals for a given vector<T> field are backward chained by decreasing t coordinate, independently of their ordering by q position (which is unrelated). For the given vector<T> field, a map keyed by siteid provides a pointer to the interval for that siteid with the largest t coord. Each interval stores a pointer to the interval with the next smallest t coord, or a NULL pointer to terminate the chain.

A given interval has uniquely defined (s,t), and therefore takes part in exactly one chain. The data structure for the interval can store a pointer to the next interval in the chain.

As additional intervals are merged into the operation, it is always the case that the new intervals have the largest t for given s, and therefore can be added to the chain without any need to scan through the intervals.

It is in fact possible to either forward chain or backward chain or both. To support forward chaining the map should additionally record a pointer to the interval with the smallest t coord for each siteid.

There can be many different intervals on the same vector<T> field with the same (s,t). For example an operation can insert at multiple places when it is first generated, or intervals can split under IT. We only require that the chain monotone increase with respect to t-coordinate. [Note that monotone increase means non-decreasing].

Forward chaining allows for an efficient means of iterating through all intervals inside 𝜒(v) for a given v. ie to find all intervals satisfying i.t < v(i.s).

Backward chaining allows for an efficient means of iterating through all intervals outside 𝜒(v) for a given v. ie to find all intervals satisfying i.t ≥ v(i.s).

17.7.2 t-chains across many fields

When there are many fields it can be very expensive to find all intervals inside 𝜒(v) or outside 𝜒(v), even with forward or backward chaining. The problem is that in practice a large proportion of the fields may have no intervals that are applicable to the result set.

Rather than store a map for each vector<T> field, consider instead that there is a single map for the entire UniOperation defined as map<SiteId,set<Element>> where Element is defined as follows 


struct Element
{
    FieldId fid;
    Interval* first;
    Interval* last;
};

A given element records the pointers to the first and last intervals in a t-chain for a given vector<T> field. Elements are only added to the set when the chain is non-empty. Therefore these pointers are never NULL.

An even more efficient approach is to chain across all vector<T> fields. However that requires the intervals to be self-describing (in the sense of being able to retrieve their associated FieldId). This can be achieved by making all intervals for a given FieldId hold a pointer to a variable that records the FieldId.

17.7.3 Potential approach: Recording entire HB as a single UniOperation

Can the whole HB be recorded as a single UniOperation, in such a way that it supports the requirements of sending local operations as well as transforming and accumulating remote operations?

Note that for the entire HB, the q positions are stored in post-insertion coordinates, and do not require adjustment as we consider session specific HB suffixes (that depend on the remote operation’s execution context). Any given vector time v allows us to immediately see the entire HB as separated into prefix and suffix simply by testing whether each interval is inside 𝜒(v). This leads to the idea of implementing a version of dualIT that is passed the vector time v so that it implicitly only transforms against the appropriate suffix of the HB.

The question then arises as to how to support efficient sending of operations, and how to avoid complete scans over all intervals in the HB all the time. Both of these seem related to the idea to filter the intervals based on a vector time.

Chaining of intervals by t coordinate would appear to be useful here, but it is not clear exactly how it would work. Chaining helps to define the subset of the intervals that are applicable. However to perform a dual IT they must be processed in order of q position.

Any clever indexing system would probably have a detrimental effect on the write performance of the system – because there is more persistent state that needs to be written to disk. Therefore this proposal is rejected.

NOTE: It is possible that this is the only approach that can avoid the quadratic complexity, in which case it trumps any I/O considerations!

17.7.4 Can an operation fit into memory?

Not if we follow this approach! An interactive session may involve operations that add huge amounts of data – including images and large amounts of text copied from the clipboard. After merging a single UniOperation may become too large to fit into memory. We therefore expect it to be broken up effectively using prefs somehow. This means that only parts of it need be marked as dirty as it changes.

We assume that LRU memory caching solves the problem of I/O performance.

17.7.5 Efficient representation of operations

Currently a UniOperation is stored as a single object in the PersistStore. Instead it is proposed that the maps keyed by FieldId are based on persistent B+Trees. This allows an operation to apply changes to millions of fields, yet indexing by FieldId is efficient – which is needed for OT.

Note that there can be substantial efficiency gains to B+Trees that are optimized to deal with keys that tend to have large common prefixes. There is a concept of sharing prefixes in the tree structure, reducing the storage requirements and reducing the time for key comparisons. These techniques are described in the literature on B+Trees.

17.7.6 On the fly compression of the HB

An interactive session could conceivably go on for days, with a dozen users, generating hundreds of thousands of operations. Compression of the HB is important for space efficiency and for allowing latecomers to enter the interactive session efficiently. It is also important for supporting updates from the ceda repository.

Note that lossy compression is quite different from merging of operations. The latter may have very little impact on the size taken up by the operations. By contrast compression throws away historical information about who performed the edits and when. It is particularly significant for assignment operations (where compression simply records the one and only dominating assignment on a given field). Note as well that insertions that were subsequently deleted are removed during compression.

During an interactive session there is a concept of a vector time vc broadcast to all parties, indicating the set of operations that can be compressed. It is assumed that these operations will no longer take part in OT during the session.

Consider that the HB is recorded in two parts. A HB-prefix which is compressed, and a HB-suffix which is merged but uncompressed. It is assumed that the uncompressed part is small enough to fit into memory. Therefore algorithms that depend on efficient random access are possible.

It is assumed that any remote operation Or received by the site has an execution context that contains the HB-prefix. Therefore there is no need to IT any part of the HB-prefix past Or.

Each time vc advances, it is necessary to remove intervals i from HB-suffix satisfying i.t < vc(i.s) and add them into HB-prefix. The removal requires negative offsets to be applied to the intervals to exclude the insertions by the remaining operations (that are outside 𝜒(vc)) in the HB-suffix.

17.7.7 Sending operations

The conventional approach is to send operations in the tail of the linear HB that are not currently present on the remote site. Instead we need an effective mechanism that works directly with the persistent HB-prefix and HB-suffix.

A latecomer won’t even have the HB-prefix (or its HB-prefix is too far out of date). In that case the first step is to transmit the entire HB-prefix. Fortunately it is compressed so that should be reasonably efficient. However how do we deal with an extended shared read lock? It would seem useful to use MVCC!

There is also the need to send all the operations in the HB-suffix that are not present on the remote site. This is easiest if we again have access to a fixed snapshot of the HB-suffix, giving us time to send everything in 𝜒(hv)\𝜒(v) where vector time v is the intersection of hv with our best estimate of what’s currently present on the remote site. Note that trying to send less than that (ie 𝜒(v’)\𝜒(v) for some vector time v’ < hv) introduces the need to ET operations before they are sent! This seems a backward step because the remote site would eventually need to IT them again.

Note that the merging efforts by one site may contribute greatly to a reduction in merging effort by other sites – in a far superior fashion to an approach where linear HB’s are sent. Consider the following example:

Conventionally S3 would have to IT O1 past O2 when it receives O1 from S1. However if S1 happens to sends O1 after receiving O2’ then it is able to send it in the form O1’ – ie in the context of having performed O2, eliminating the need for transformation on S3!

17.7.7.1 Finding the operations to be sent

We always send a single UniOperation that represents everything in 𝜒(hv)\𝜒(v) for an appropriate vector time v. Note therefore that the sender naturally sends batches of operations merged into single operations. This is exactly what’s needed to avoid the quadratic complexity problem.

The UniOperation is obtained from the HB-Suffix simply by filtering intervals with given (s,t) depending on whether t < v(s). This can be done efficiently using the backward chains. ie for a given field we have a map keyed by SiteId that points at the interval with largest t. We following the backward chain, decrementing t while t < v(s). This is very efficient.

To avoid holding a shared read lock for too long we make a copy of the UniOperation to be sent in memory. This is subsequently sent in the background without a lock on the containing PSpace.

17.7.8 Transforming a received batch of operations

Let Or represent the merge of a batch of received operations. The set of operations in Or is given by 𝜒(v2)\𝜒(v1) for two given vector times v1,v2 satisfying v1 ≤ v2. v1 represents the execution context of Or.

The sender should have ensured that nothing in the execution context of Or is missing on the receiver. In other words v1 is an underestimate of hv

v1 ≤ hv

The set containment relationships can be depicted in the following Venn diagram:

The receiver of Or may find that some of these operations are already present. ie

𝜒(hv) ⋂ (𝜒(v2)\𝜒(v1)) = (𝜒(hv) ⋂ 𝜒(v2)) \ 𝜒(v1) ≠ ∅

Therefore it is possible that only a subset of Or should be applied. This subset is characterized as

𝜒(v2) \ 𝜒(hv)

Consider that we pretend we cannot see any of the intervals in Or inside 𝜒(hv), and at the same time pretend that the execution context of Or is hv ⋂ v2 instead of v1. Since intervals in Or are expressed in post insertion coords in the context of all of 𝜒(v2 ) we find that there is no change to the q positions when we pretend the execution context is larger.

So pretending that Or is in fact representing the set of operations in 𝜒(v2) \ 𝜒(hv) and having execution context hv ⋂ v2 makes it clear that it is straightforward to merge Or into the HB.

However is it efficient? We seem to need to transform against the entire HB-suffix which could be expensive. In addition we seem to need to test every interval for whether it’s inside a vector time extent, and that can be substantially more expensive than the actual IT. In fact in the worse case 𝜒(hv)\𝜒(v2) = ∅ so there should be nothing to do, and yet we iterate through every interval in the HB-suffix.

This is quite nasty because it means there is a significant CPU load even though a given pair of sites are in sync with each other.

It’s difficult to see how to make this efficient without introducing the concept of a per-session transient HB-suffix.

17.7.9 Using both persistent as well as transient HB suffixes

Consider that we don’t store a linear HB, but instead persist one HB-prefix and HB-suffix for the site (ie working set), and in addition each session with a given peer stores a single transient HB-suffix.

On a given site, for each session there is a dedicated thread to process incoming operations and another thread to send outgoing operations. Consider that these share the same transient HB-suffix. Note therefore that there tends to be contention for the transient HB-suffix, but not for the persistent HB in the PSpace.

It can be assumed that a transient HB-suffix always contains a subset of the operations in a persistent HB-suffix.

A transient HB suffix works as follows

  • It is initially calculated from the persistent HB-suffix for a given vector time which represents an underestimate of the remote site’s hv. Backward chaining in the persistent HB-suffix is very useful to make this efficient.
  • When a merged batch Or is received, intervals in the transient HB-suffix that are inside the execution context of Or are removed. This can be done efficiently using forward chaining on the transient HB-suffix.
  • Applying a merged batch of remote operations Or involves 1) removal of intervals within Or that are already present in the local HB, then 2) merging in the normal way without needing to test whether intervals are contained inside vector time extents.
  • The session records a vector time rhv that indicates the set of operations that are known to have already been sent through the message queue to the remote site. The sender thread uses backward chaining to quickly find the operations in the HB suffix that are outside c(rhv), and therefore need to be sent to the remote computer. rhv is then updated to ensure the same intervals are never sent again.

17.7.10 Incremental compression

Definition: Given operation O, let C(O) denote the result of compressing operation O. This has the effect of

  • Removing all (s,t) related information
  • Coalescing intervals where possible
  • Removing redundancy such as insertions that were subsequently deleted, or redundant move operations.

Note that removing redundancy will impact the correctness of the PtoQ maps. Therefore for now we will ignore this complicating issue and disallow redundancy removal.

Let O1, O2 be contextually serialized operations. An incremental compression algorithm concerns the calculation of C( [O1O2]) from C(O1) and O2. We could break this into two parts

  • From O2 calculate C(O2)
  • From C(O1), C(O2) calculate C( [O1O2])
17.7.10.1 Compression of a single UniOperation

Let’s consider the special case of pure insertion operations on a single vector<T> field. We can scan left to right removing the (s,t) information. This may allow for many of the intervals to coalesce.

For a Create-Delete operation, we can similarly coalesce adjacent delete intervals. Furthermore we could also introduce the concept of a separate list of intervals that represent creation of deleted characters! These come from the intersection of the creation and deletion intervals. In theory this could be used to back-out redundant changes to the PtoQ maps.

Note that factoring out the intersection of creations and deletions should make it even more likely that we can subsequently coalesce creation and deletion intervals. ie it may be quite important to achieve decent compression.

17.7.10.2 Merging of compressed operations

Let C(O1) and C(O2) be contextually serialized, compressed operations. We want to calculate C([O1 O2 ]).

Given [C1 D1 C2 D2] we can easily transpose the middle two to give [C1 C2 D1’ D2]. It is then straightforward to merge C1 and C2. C1 insertions positions must be shifted to the right to include the effect of insertions by C2. In addition adjacent intervals are coalesced.

Of course these algorithms have all been written before. However there are some small differences – such as the idea to ignore (s,t) when looking for opportunities to coalesce intervals. We can actually get code reuse if we first apply the same (s,t) to all intervals.

17.7.11 Transient HB suffix

A linear HB that only grows at the end is well suited for high transaction throughput – because new operations only need to be appended to the end, and this is well suited to a Log Structured Store (LSS). Furthermore, sending of operations basically involves asynchronously playing the tail of the HB which tends to be cached in memory and in any case will exhibit good clustering properties on disk – because the HB is read in the same order it is written.

Therefore we prefer the technique of a transient representation of the HB suffix – probably one for each session.

17.7.12 Potential approach: sharing a transient HB suffix across all sessions

If we share the same HB suffix across all sessions then we need a version of dualIT that works with a given vector time. However it must be remembered that the test i.t < v(i.s) is comparatively expensive (ie compared to the interval comparisons performed by IT). In practice when the system is under heavy load we expect that operations will be sent in batches with slowly changing execution contexts. Therefore it can be quite useful to perform the filtering as rarely as possible. That means don’t try to share a transient HB suffix across multiple sessions – ie this proposal is rejected.