Fragment

The Fragment mechanism is an advanced server-side feature designed to optimize the handling of snapshots for large documents. By splitting snapshots into multiple smaller pieces (Fragments), the server only processes the relevant parts, avoiding frequent reads and writes of the entire snapshots, thereby improving performance. This document introduces the design, implementation, and usage of Fragments.

Why Fragments are Needed

For large documents (such as workbooks or complex data structures), reading and writing the entire snapshot for each apply op operation leads to high I/O overhead and performance bottlenecks.

Without Fragments, the server-side process for handling operations is as follows:

Read the entire snapshot from the database.
Apply the operation to modify the data.
Write the complete snapshot back to the database.

The Fragment mechanism significantly reduces resource consumption by storing and manipulating snapshots in segments:

Splits the snapshot into independent fragments (e.g., one fragment per worksheet).
Loads and updates only the relevant fragments during operations.
Merges fragments on demand to return a complete snapshot.

Design

Taking a workbook as an example, assume the snapshot structure is as follows:

interface IWorkbookSnapshot {
  activeSheetId: string;
  sheets: IWorksheetSnapshot[];
}
interface IWorksheetSnapshot {
  sheetId: string;
  dataTable: { [row: number]: { [col: number]: { value: string } } };
}

Supported operation types:

setCellValue: Modify a cell value.
addWorksheet: Add a worksheet.
removeWorksheet: Remove a worksheet.

Fragmentation Example

A workbook snapshot:

{
  activeSheetId: 'sheet1',
  sheets: [
    { sheetId: 'sheet1', dataTable: { 0: { 0: { value: 'Hello' } } } },
    { sheetId: 'sheet2', dataTable: { 0: { 0: { value: 'World' } } } }
  ]
}

Can be split into the following fragments:

Fragment Name	Fragment Data
workbook	{ activeSheetId: 'sheet1' }
sheet_sheet1	{ sheetId: 'sheet1', dataTable: { 0: { 0: { value: 'Hello' } } } }
sheet_sheet2	{ sheetId: 'sheet2', dataTable: { 0: { 0: { value: 'World' } } } }

OT Type Support

The Fragment mechanism is implemented by extending the server-side OT type (OT_Type), adding the following methods:

Method	Description
`createFragments(data: S): ISnapshotFragments;`	Creates multiple fragments from the initial data, returning `ISnapshotFragments`.
`applyFragments(request: ISnapshotFragmentsRequest, op: T): Promise<void>;`	Applies an operation to a fragmented snapshot, using `ISnapshotFragmentsRequest` to manipulate fragments.
`composeFragments(fragments: ISnapshotFragments): S;`	Merges fragments into a complete snapshot.

type=info
When using Fragments, above methods must be implemented. The create and apply methods can be omitted.

Workflow

Create Document: Call createFragments method to split the snapshot into fragments and store them in the database.
Applying Operations:
- Receive the operation (op) and use applyFragments with ISnapshotFragmentsRequest to manipulate the relevant fragments.
- Update only the affected fragments (e.g., modifying a cell updates only the corresponding worksheet).
Client Requests Snapshot: Call composeFragments to merge the fragments and return a complete snapshot to the client.

type=warning
Server-Specific: Fragments are implemented only on the server side, the client still uses the complete snapshot.
OT Type Consistency: The client and server must share the same uri and transform.

Comparison of OT Types Without and With Fragments

The following compares the implementation of OT types without and with Fragments, based on the workbook example:

The implementation without fragment OT type:

const workbook_ot_type: OT_Type = {
    uri: 'workbook-ot-type',
    create: (data: IWorkbookSnapshot) => data,
    apply: (data: IWorkbookSnapshot, op: IOp) => {
        if (op.type === 'addWorksheet') {
            data.sheets.push(op.sheetSnapshot);
        } else if (op.type === 'removeWorksheet') {
            data.sheets = data.sheets.filter(sheet => sheet.sheetId !== op.sheetId);
        } else if (op.type === 'setCellValue') {
            const sheetSnapshot = data.sheets.find(sheet => sheet.sheetId === op.sheetId);
            sheetSnapshot.dataTable[op.row][op.col].value = op.value;
        }
        return data;
    },
    transform: (op1, op2, side) => {
        // Handle conflicts
        return op1;
    }
}

The implementation with fragment OT type:

const workbook_ot_type = {
    uri: 'workbook-ot-type',
    createFragment: (data: IWorkbookSnapshot) => {
        const fragments = {};

        // Create a fragment for each worksheet
        for (const sheet of data.sheets) {
            const sheetFragmentName = 'sheet_' + sheet.sheetId;
            fragments[sheetFragmentName] = sheet.dataTable;
        }

        // Create the rest of the workbook as a fragment
        fragments['workbook'] = { ...data, sheets: undefined };
        return fragments;
    },
    applyFragments: async (request: ISnapshotFragmentsRequest, op) => {
        if (op.type === 'createSheet') {
            request.createFragment(op.sheetId, op.sheetSnapshot);
        } else if (op.type === 'deleteSheet') {
            request.deleteFragment(op.sheetId);
        } else if (op.type === 'setCellValue') {
            const sheetSnapshot = await request.getFragment(op.sheetId) as IWorksheetSnapshot;
            sheetSnapshot.dataTable[op.row][op.col].value = op.value;
            request.updateFragment(op.sheetId, sheetSnapshot);
        }
    },
    composeFragments: (fragments: ISnapshotFragments) => {
        const data = JSON.parse(JSON.stringify(fragments['workbook'])) as IWorkbookSnapshot;

        // Merge fragments of all worksheets
        for (const fragmentName in fragments) {
            if (fragmentName.startsWith('sheet_')) {
                data.sheets.push(fragments[fragmentName] as IWorksheetSnapshot);
            }
        }

        return data;
    },
    transform: (op1, op2, side) => {
        // Handle conflicts
        return op1;
    }
};

Feature	Without Fragment OT Type	With Fragment OT Type
Workflow	Requires reading and writing the entire snapshot when applying an op	Only reads and writes the relevant fragments when applying an op.
Performance	Lower performance for large documents, high I/O overhead.	Higher performance for large documents, processes only small fragments, reducing I/O overhead.
Complexity	Simple implementation, only needs to handle the complete snapshot.	Complex implementation, requires managing fragmentation and merging logic.
Applicable Scenarios	Small documents or low-concurrency scenarios.	Large documents or high-concurrency scenarios.

API

/**
 * Defines the interface for customizing operational transformation (OT) behavior in collaboration.
 * @template S The type of snapshot data.
 * @template T The type of op data.
 */
export interface OT_Type<S = unknown, T = unknown> {
    /**
     * The URI identifying the document type.
     */
    uri: string;
    /**
     * Creates initial snapshot data from provided data.
     * @param {S} data - The initial snapshot data.
     * @returns {S} The created snapshot data.
     */
    create?(data: S): S;
    /**
     * Generates snapshot fragments from snapshot data.
     * @param {S} data - The snapshot data.
     * @returns {ISnapshotFragments} The generated snapshot fragments.
     */
    createFragments?(data: S): ISnapshotFragments;
    /**
     * Composes snapshot data from snapshot fragments.
     * @param {ISnapshotFragments} fragments - The snapshot fragments.
     * @returns {S} The composed snapshot data.
     */
    composeFragments?(fragments: ISnapshotFragments): S;
    /**
     * Transforms an operation to resolve conflicts with another operation.
     * @param {T} op1 - The operation to transform.
     * @param {T} op2 - The operation serving as the basis for transformation.
     * @param {'left' | 'right'} side - Indicates which operation arrived at the server later.
     * @returns {T} The transformed operation.
     */
    transform(op1: T, op2: T, side: 'left' | 'right'): T;
    /**
     * Applies an operation to snapshot data.
     * @param {S} snapshot - The current snapshot data.
     * @param {T} op - The operation to apply.
     * @returns {S} The updated snapshot data.
     */
    apply?(snapshot: S, op: T): S;
    /**
     * Applies an operation to snapshot fragments asynchronously.
     * @param {ISnapshotFragmentsRequest} request - The request containing snapshot fragments.
     * @param {T} op - The operation to apply.
     * @returns {Promise<void>} A promise that resolves when the operation is applied.
     */
    applyFragments?(request: ISnapshotFragmentsRequest, op: T): Promise<void>;
}

export type ISnapshotFragments<S = unknown> = { [key: string]: S };

export interface ISnapshotFragmentsRequest<S = unknown> {
    getFragment(id: string): Promise<S | undefined>;
    createFragment(id: string, data: S): void;
    updateFragment(id: string, data: S): void;
    deleteFragment(id: string): void;
}