28 History of the ceda-core implementation

The implementation of operational transformation in ceda-core changed substantially as the research developed. The earliest preserved vector-field implementation used a physical vector together with a P-to-Q map, while changes were represented by a temporally ordered linear history buffer. Later implementations left the application vector in its ordinary representation and recorded the information about changes separately, arranged primarily in spatial order. This chapter places those changes alongside the corresponding chapters of this document and explains which history is preserved in Subversion and Git.

2001–2002: the initial OT implementation

Development of operational transformation in CEDA began in 2001. By May 2002, it included OperationDesc and a persistent HistoryBuffer.

The 2002 HistoryBuffer stored a linear list of persistent command objects in separately persistent pages. OperationDesc identified an operation by client and client sequence number and recorded its server sequence number. The code implemented inclusion and exclusion transformation, together with LIT and LET over ranges of the history. It discussed dOPT and GOT, and provided both GOT integration and an undo/do/redo method for inserting remotely generated operations. This was a client/server replicated-store design in which the server maintained the growing history and exchanged operations with clients.

2003: vector time and a retained history suffix

During 2003, CalculateSuffix and VectorTime appear, followed by DualIT in August. The early control algorithm, described in 8 Operational Transform Control Algorithms, treated the history buffer as a contextually serialised list of operations. Each operation had a causal context identified by vector time. To receive an operation, a site factorised a copy of a tail of its history into a causal prefix and a concurrent suffix, popped the prefix, and transformed the received operation against the remaining suffix. A live connection could retain that suffix as transient per-peer state and update both it and received operations using DualIT.

The later implementation represented the persistent history as an OpVector, appended executed operations to it, and represented a transient suffix as a std::deque<Operation*>. This is the literal list representation of a history-buffer suffix used by the early control algorithm.

7 February 2005: change from CVS to SVN

CEDA changed from CVS to SVN on 7 February 2005.

20 September 2007: creation of the replacement SVN repository

The replacement SVN repository was created on 20 September 2007. Its imported source tree replaced the earlier repository history with a new initial state.

Paired representation of a vector field

The initial state contains a complete example of the early vector-field representation. The logical vector was indexed in q-coordinates and included the positions of elements that were absent or deleted. The physical vector stored only elements that existed and was indexed in p-coordinates. A companion PtoQMap recorded the relationship between those coordinate systems:

class VectorField
{
private:
    // Indexed by p-position
    VectorOfByte m_buffer;

    PtoQMap m_ptoq;
};

The accompanying source describes a reflected vector<T> field as two stored vectors: one for the physical elements and another for the P-to-Q mapping. In this implementation, PtoQMap used a run-length encoding of whether each q-position contained an existing element. Inserts and erasures updated both m_buffer and m_ptoq.

The same SVN revision contains the linear HistoryBuf. Its CalculateSuffix() method copied a tail of the persistent history, transposed adjacent operations until the copy had a causal prefix and concurrent suffix, deleted the prefix, and returned the remaining list. The early physical representation of objects and the early temporal representation of changes therefore appear together in the source.

February 2008: multi-character CDM operations

19 Multi-character CDM operations was written in February 2008. It defines multi-character create, delete and move operations over effects documents and gives the application, transformation, transposition and merge algorithms. Its p- and q-coordinate systems correspond directly to the paired VectorField/PtoQMap implementation recorded in SVN.

The tests in 19.14 Tests use the control model then available: each site retains a linear history and factorises it when an operation is received. The operation algorithms are the subject of 19 Multi-character CDM operations; the test harness is not an implementation of the later composite history-buffer representation.

October 2008: generalising the history-buffer suffix

21 Efficient HB Suffix was written in October 2008. It generalises the idea of taking a suffix of a linear list. A history buffer can instead be represented as a composite operation, and factorisation operators such as RFactor can extract the required logical suffix without requiring the composite operation to be stored in temporal list order.

This changes the representation of changes rather than merely providing a faster list operation. For vector fields, insertions, deletions and related intervals can be grouped by field and maintained in spatial order. Operation identifiers and vector times retain causal information, while the data structure no longer has to reproduce the temporal order in which every atomic operation arrived. Merge, factorisation and transformation operate directly on the composite representation.

13 August 2009: composite operations enter ceda-core

SVN revision 672, dated 13 August 2009, records the production transition explicitly:

Use macro USE_COMPOSITE_OPS to enable/disable composite operations approach.

The revision says that cxOperation was being converted to composite operations and used conditional compilation so the old and new implementations could coexist. Subsequent revisions in August 2009 added operations for obtaining and applying deltas, R-factor calculations, merge code, and maps of vector-operation intervals. This is the implementation path arising from the research in 21 Efficient HB Suffix.

The transition was staged. Introduction of a composite, spatially organised history did not immediately remove the paired physical representation of every vector field. For example, SVN revision 678 of 19 August 2009 still added a method to VectorField, and revision 680 of 20 August still extended PtoQMap. The representation of changes and the representation of the application field evolved independently for a period.

9 April 2010: P-to-Q data becomes a tombstone interval set

SVN revision 940, dated 9 April 2010, largely rewrote PtoQMap. The earlier vector of (dp,dq) run lengths was replaced by an interval set representing tombstones. The class continued to translate between physical and effects coordinates, but its stored information had become explicitly spatial: a set of deleted q-intervals.

This is an intermediate point in the history. The application field could still use P-to-Q translation, while the persistent description of changes was moving toward the separate composite structures introduced in 2009.

2007–2014: SVN history

The replacement SVN repository continues through revision 2028, dated 28 November 2014. Its history runs from the linear-history and paired-vector implementation through the introduction of composite operations.

The SVN history also establishes an evidential boundary. It shows that the transition began in 2009 and that parts of the old physical representation continued afterwards, but the currently available analysis has not identified a single SVN revision at which every use of the paired vector-field representation disappeared.

26 August 2018: change from SVN to Git

The ceda-core Git repository begins on 26 August 2018. The source tree was imported from SVN as a snapshot; the preceding SVN revisions were not imported as Git commits. Consequently, ordinary Git history cannot answer questions about the 2007–2014 implementation. Those questions must be answered from the preserved SVN repository.

By the 2018 Git snapshot, vector-operation state was represented separately from the application vectors. The working set contained structures such as VectorInsertions, VectorDeletions and VectorInsertionsAndDeletions, held in maps keyed by FieldId. Their linked interval sets were scanned and transformed in spatial order. This is the concrete descendant of the approach in 21 Efficient HB Suffix.

A class named PtoQMap still appears in the imported source, including under the alias VectorTombstones. Its presence must not be confused with the older object representation in which every vector<T> field was stored as a pair of vectors. In the later code it records tombstone information used by operation and delta processing; it is separate from the ordinary application vector.

13 April 2019: factoring OT into the header-only cxOT library

On 13 April 2019, cxOT was created as a pure C++ header library for OT algorithms. Before this change, the production OT implementation was embedded in cxOperation, where it was coupled to working sets, persistence, delta transfer and other database machinery. The new library separated the generic algorithms and data structures from those services. Because its implementations were templated and defined in headers, applications could specialise and use them without linking to a separate cxOT binary.

The factoring established a clear boundary. cxOT defines reusable concepts such as operation identifiers, vector time, vector domains, spatially ordered insertion and deletion intervals, transformation, merge and factorisation. It does not need to know how CEDA stores objects, identifies fields, manages transactions, persists a working set or transports deltas between peers. Those responsibilities remain in cxOperation, which instantiates and applies the generic OT structures to CEDA database fields.

The code factored into cxOT included:

• TOpid and TVectorTime for operation identifiers and vector times;
• TVDom and TSun for vector domains and SUN values;
• FrontLinkedList for spatially ordered operation intervals;
• TVectorInsertionInterval and TVectorDeletionInterval for individual vector-operation intervals;
• TVectorInsertions, TVectorDeletions and TVectorInsertionsAndDeletions for composite vector operations and their transformation, merge and factorisation algorithms; and
• TPToQMap and TSimplePToQMap for generic P-to-Q mapping.

The corresponding code in cxOperation was converted to instantiate these templates and combine them with persistent objects, field identifiers, working-set state and delta processing.

The header-only design also made the algorithms independent of one concrete representation. A client can supply the required value, identifier, coordinate and storage types through templates, while the compiler specialises the algorithms without a virtual interface or binary-library boundary. This made cxOT suitable both for production use by cxOperation and for focused tests of the mathematical algorithms.

P-to-Q translation was retained in cxOT as a useful generic algorithmic component; this does not mean that the old paired object-field representation returned. Earlier CEDA OT research and implementation had lived in projects such as cxOperation and OpTransTest, so it should not be described as cxOT before this factoring.

2021: consolidation of the later representation

In December 2021, vector transformation and delta application were reorganised around cxOT and DatabaseVectorField. The latter accesses an ordinary reflected VectorOfByte application field, while insertion and deletion intervals remain in separate OT structures. This makes the architectural separation particularly clear:

application objects              operation state
-------------------              ---------------
ordinary vector fields           intervals grouped by FieldId
current physical elements        insertion/deletion and causal metadata
application representation       spatial composite representation

Relationship between the implementation eras and this document

The history explains why both kinds of representation appear in this document. 19 Multi-character CDM operations records the operation model and test strategy used with linear histories and explicit p/q field coordinates. 21 Efficient HB Suffix is later work that removes the requirement to store the history as a temporal list and leads to the composite, spatially organised change representation seen in modern ceda-core. The later approach builds on the earlier operation algebra; it does not make the earlier algorithms historically or mathematically irrelevant.