15.7 Bag Operations

(30 Aug 2005)

Abstract

This paper provides a solution to the operational transform of bag operations.

Introduction

The document state is assumed to be a "bag" over some element type T. A bag is like a set except that repeats are allowed. The repeated elements are indistinguishable from one another. An analogy is a bag of marbles which can hold a number of marbles of a given colour.

T is a value type, and is assumed to support an equality comparison operator. In this paper we study the operational transform of the following operations

  • ins(v) - insert value v into the bag. This operation can always be generated, irrespective of whether the value v is already present in the bag.
  • del(v) - delete value v from the bag. It is assumed that value v can be found in the bag when this operation is generated.

We need convergence at quiescence even though operations are executed in different orders at different sites. Specifically we require properties TP1 and TP2 [1].

Properties required to achieve convergence

TP1

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

TP2

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

Discussion

In the following cases, let O1, O2 be concurrent operations that are performed on the same document state S.

ins(v1) and ins(v2) commute

Let operation O1 insert value v1, and let O2 insert value v2. Irrespective of what is already in the bag, and whether v1=v2, O1 and O2 commute and therefore nothing needs to be done under IT.

ins(v1) and del(v2) commute

Let operation O1 insert value v1, and let O2 delete value v2. Irrespective of whether v1 = v2, we can assume v2 exists in the bag in state S, and these operations commute so nothing needs to be done under IT.

del(v1) and del(v2) commute when v1 ≠ v2

Let operation O1 delete value v1, and let O2 delete value v2. Assuming v1 ≠ v2 we can assume these values exist independently in the bag, and these operations commute so nothing needs to be done under IT.

Concurrent del(v) operations conflict

The only difficult case is where O1 and O2 both delete value v. If there are two or more instances of value v in the bag then we could allow both these operations to be applied. Otherwise it will be necessary to disable under IT. For simplicity we choose to always disable under IT, as though the two users were fighting over removal of the same instance even though there were more than one available.

It is necessary to only allow an enabled delete operation to cause another delete operation to become disabled.

Solution

Let an operation contain the following fields 

struct BagOp
{
    bool ins;
    int dc;
    T v;
};
Field Description
ins Boolean flag to indicate whether this is an insert or delete operation
dc Disable count, only relevant to a delete operation. Initialised to zero when the operation is first generated.
v Value to be inserted or deleted

The following C++ code shows the implementation of IT/ET 


void IT(BagOp& O1, const BagOp& O2)
{
    if (!O2.ins && !O1.ins && O1.v == O2.v && O2.dc == 0) ++O1.dc;
}

void ET(BagOp& O1, const BagOp& O2)
{
    if (!O2.ins && !O1.ins && O1.v == O2.v && O2.dc == 0) --O1.dc;
}

Future work

For performance this solution should be extended to support operations that insert or delete multiple elements at once. This also allows for operations to be closed under merging. Furthermore it will be possible to compress merged operations by eliminating elements that are inserted then deleted by the operation. Compression can also discard disabled delete operations.

Tests

Simulation of multiple sites

Each simulation creates between two and nine sites, all starting with the same database of bag fields. The state at each site is represented by: 

using VectorTime = std::vector<int>;  // Indexed by SiteId

struct Site
{
    SiteId id;
    Database database;
    VectorTime time;
    std::vector<BagOp> history;
};

The vector time records how many operations originating at each site have been applied. The history contains every local or received operation applied at the site, in a causally valid linear order.

Generating an operation

A randomly selected site generates an operation against its current state. The operation selects a random bag field and either inserts a random value or deletes a randomly selected occurrence already present in that bag. It is applied locally, appended to the site's history, and recorded in the site's vector time.

Sending an operation

To send an operation, the simulation selects the first operation in the sender's history that the receiver has not applied. The preceding operations in the sender's history define its causal context. The receiver performs the Factorise step described in 8 Operational Transform Control Algorithms, using Transpose to rearrange its history into a prefix containing that context and a suffix containing operations concurrent with the incoming operation. It then applies IT to the incoming operation for each operation in the concurrent suffix before applying it to the receiver's database. This exercises IT, ET and Transpose as operations arrive in different causally valid orders.

Checking convergence

Simulation events randomly generate an operation, send one operation between two sites, or fully synchronise a pair of sites. A synchronised pair must have equal vector times and equal databases, including the multiplicity of every value in every bag. After the final event, all outstanding operations are exchanged and the same comparison is made across all sites.

After every event, the test also checks that the number of operations in each site's history equals the sum of its vector-time components and that no operation has a negative disable count.

Results

A total of 30,000 simulations of 500 events each completed without a convergence failure.

Browse the test files.

References

  1. David Barrett-Lennard, Operational Transform — Control Algorithm, August 2005.

Possible repository representation

A repository needs to retain the check-in history and calculate the state of a bag at any given vector time. One possible representation records the operation that inserted each occurrence of a value, together with every operation known to have deleted that occurrence: 

struct Entry
{
    OpId insertOpId;
    std::vector<OpId> deleteOpIds;
};

std::map<T, std::list<Entry>> entries;

The map contains one list for each value of T. Each Entry represents a distinct occurrence of that value, which is important because equal values in a bag can have a multiplicity greater than one.

To calculate the bag at vector time v, the repository iterates over the map and then over the entries for each value. An entry contributes one occurrence of its value when its insertion is included in v and none of its deletions is included in v. The number of contributing entries is the multiplicity of that value in the bag.

A check-in updates this representation as follows:

  • An insertion appends a new Entry to the list for the inserted value.
  • A deletion appends its OpId to deleteOpIds of the leftmost entry that is present in the context of the check-in.

Selecting the leftmost eligible entry gives a deterministic identity to an otherwise indistinguishable occurrence. This representation agrees with the IT/ET policy above: concurrent deletions of the same value address the same occurrence, so only one remains enabled.