19.14 Tests
Simulation of multiple sites
Each simulation creates between two and nine sites, all starting with identical effects documents. It generates operations, exchanges them between sites in causally valid orders, and checks that sites converge to identical states.
State maintained at each site
using SiteId = int;
using VectorTime = std::vector<int>; // Indexed by SiteId
struct Site
{
SiteId id;
EffectsDocumentSet documents;
VectorTime time;
std::vector<Operation> history;
};
The id identifies the site. documents is its current application state.
time has one component per site and records how many operations originating at each site
have been applied locally. history is a linear buffer containing every local or received operation
applied at the site, in a causally valid linear order. Thus the simulation does not give a site a
branching history or history DAG.
After every event, the simulation checks that the size of history equals the sum of the
vector-time components and that every stored operation is structurally valid.
Generation of a random operation
An Operation is defined in
19.2 Operations:
struct Operation
{
OpId opid;
std::map<DocId, DocIntervals> documents;
};
To generate an operation, the simulation selects a random site and constructs between one and four
atomic Operation values against that site's current documents. Each contains one
multi-character create, delete or move interval. A move within a document contributes an insertion
and an extraction entry to that document. A move between documents contributes an extraction entry
to the source document and an insertion entry to the destination document; both entries refer to
the same move interval. The atomic operations are applied successively to a temporary document
state and combined into one composite Operation using Merge. As a separate
check of Merge, applying the composite
operation to the original state must produce exactly the same effects documents as applying the
atomic operations in sequence. The composite operation is then applied at the site, appended to its
history, and the site's own vector-time component is incremented.
Sending a random operation
To perform a one-way exchange, the simulation:
- Selects a random sender and a different random receiver.
- Scans the sender's history from the beginning and selects the first operation that has not been applied at the receiver, as indicated by the receiver's vector time. The operations preceding it in the sender's history form its causal context. Selecting the first unapplied operation ensures that every operation in its causal context has already been applied at the receiver.
- Performs the Factorise step described in 8 Operational Transform Control Algorithms: it transposes operations in the receiver's history until the causal context forms a prefix and the operations concurrent with the incoming operation form a suffix.
- Inclusion-transforms the incoming operation through each operation in the concurrent suffix.
- Applies the transformed operation to the receiver's effects documents, appends it to the receiver's history, and increments the vector-time component for its originating site.
This is a simplified approach suitable for testing: the concurrent suffix is obtained from the
site's complete history whenever an operation is received. In a real system, each site would retain
transient state for each message-stream connection to a peer. That state would include a list of
operations representing the history-buffer suffix for the stream. When the connection is
established, each endpoint receives from its peer a vector time describing the operations applied at
that peer. The endpoint copies a tail of its persistent history buffer, factorises the copy with
respect to the received vector time, and pops the resulting prefix. What remains initialises the
transient suffix for that message stream; the persistent history buffer is unchanged. Thereafter the
suffix is maintained incrementally. The received operation and the retained suffix are processed
using DualIT, transforming the received operation for application after the suffix while
also updating the suffix to account for the received operation. Local operations are appended to the
suffix as they are generated. The complete history therefore does not need to be factorised for
every received operation.
Checking convergence of a pair
The simulation selects a random pair of distinct sites and exchanges operations in both directions until no further send is possible. It then requires the two vector times to be equal and compares their complete sets of effects documents. The comparison includes both character values and their present or deleted state. A difference in either the sets of applied operations or the resulting document state is a convergence failure.
Simulation events
Each event in a simulation is randomly selected from three kinds:
- Generate (50%): generate and apply an operation at a random site.
- Send (40%): send one operation from a random sender to a different random receiver.
- Synchronise and check (10%): select a random pair of sites, exchange operations in both directions until they are synchronised, and then check their convergence.
After the requested number of events, all remaining operations are exchanged between all sites and convergence is checked globally.
Results
A total of 3,000 simulations of 300 events each completed without a convergence failure. The number and variety of operations, sites and exchange orders provide very high confidence in the correctness of the algorithms exercised by this simulation.