Introduction to Loro’s Wealthy Textual content CRDT – Loro

This text presents the wealthy textual content CRDT algorithm applied in Loro, complying with Peritext (opens in a new tab)‘s standards for seamless wealthy textual content collaboration. Moreover, it may be constructed on high of any Record CRDT algorithms and switch them into wealthy textual content CRDTs.

If CRDTs are new to you, our article What are CRDTs gives a short introduction.

Background

Loro is based on the Replayable Event Graph (REG) algorithm proposed by Seph Light, however this algorithm can not combine the unique model of Peritext. This motivates us to create a brand new wealthy textual content algorithm. It’s unbiased of the particular Record CRDTs, thus working properly with REG, and is developed on high of them to ascertain a wealthy textual content CRDT.

Earlier than diving into the algorithm of Loro’s wealthy textual content CRDT, I might wish to briefly introduce REG and Peritext, and why Peritext can’t be used on REG.

Brief Introduction to Replayable Event Graph

Seph Gentle (opens in a new tab), the writer of Replayable Occasion Graph, is presently engaged on the paper, and it is extremely anticipated.

REG is a novel CRDT algorithm that mixes the strengths of each OT and CRDTs. It has the distributed nature of CRDT that allows P2P collaboration and information possession. Furthermore, it achieves minimal overhead in eventualities devoid of concurrent edits, just like OT.

Whether or not in real-time collaboration or multi-end synchronization, a directed acyclic graph (DAG) kinds over the historical past of those parallel edits, just like Git’s historical past. The REG algorithm data the historical past of person edits on the DAG.

In contrast to typical CRDTs, REG can file simply the unique description of operations, not the metadata of CRDTs. As an illustration, in textual content modifying eventualities, the RGA algorithm (opens in a new tab) wants the op ID and Lamport timestamp (opens in a new tab) of the character to the left to find out the insertion level. Yjs (opens in a new tab)/Fugue, nevertheless, requires the op ID of each the left and proper characters at insertion. In distinction, REG simplifies this by solely recording the index on the time of insertion. Loro, which makes use of Fugue (opens in a new tab) upon REG, inherits these benefits.

An index shouldn’t be a secure place descriptor, because the index of an operation will be affected by different operations. For instance, if you happen to spotlight content material from index=x to index=y, and concurrently somebody inserts n characters at index=n the place n<x, then your highlighted vary ought to shift to cowl from x+n to y+n. However REG can decide the precise place of this index by replaying historical past. Thus, it might probably reconstruct the corresponding CRDT construction by replaying historical past.

Reconstructing historical past might sound time-consuming, however REG can backtrack just some. When merging updates from distant sources, it solely must replay operations parallel to the distant replace, reconstructing the native CRDTs to calculate the diff after making use of distant operations to the present doc.

The REG algorithm excels with its quick native replace speeds and eradicate issues about tombstone assortment in CRDTs.As an illustration, if an operation has been synchronized throughout all endpoints, no new operations will happen concurrently with it, permitting it to be safely faraway from the historical past.

Transient Introduction to Peritext

Peritext (opens in a new tab) was proposed by Geoffrey Litt et al. It is the primary paper to debate wealthy textual content CRDTs. It may well merge concurrent edits in wealthy textual content format whereas preserving users’ intent as much as possible (opens in a new tab). Its main focus is merging the codecs and annotations of wealthy textual content content material, comparable to daring, italic, and feedback. It was applied in Automerge (opens in a new tab) and crdt-richtext (opens in a new tab).

💡 The precise definition of person intent within the context of concurrent wealthy textual content modifying cannot be clearly defined in just a few phrases. It is best understood by explicit examples.

Peritext is designed to unravel a few important challenges:

Firstly, it addresses the anticipated issues arising from conflicting model edits. As an illustration, contemplate a textual content instance, “The fast fox jumped.” If Consumer A highlights “The fast” in daring and Consumer B highlights “fast fox jumped,” the best merge ought to lead to the complete sentence, “The fast fox jumped,” being daring. Nevertheless, current algorithms may not meet this expectation, leading to both “The fast fox” or “The” and “jumped” being daring as a substitute.

Moreover, Peritext manages conflicts between model and textual content edits. In the identical instance, if Consumer A highlights “The fast” in daring, however Consumer B adjustments the textual content to “The quick fox jumped,” the best merge ought to lead to “The quick” being daring.

What’s extra, Peritext takes into consideration completely different expectations for increasing kinds. For instance, if you happen to sort after a daring textual content, you’ll sometimes need the brand new textual content to proceed being daring. Nevertheless, if you happen to’re typing after a hyperlink or a remark, you possible would not need the brand new enter to change into a part of the hyperlink or remark.

Why Unique Peritext Cannot Be Instantly Used with REG

On the one hand, Peritext’s algorithm expresses style ranges through character OpIDs (opens in a new tab). With out replaying historical past, CRDTs primarily based on REG can not decide the particular positions corresponding to those OpIDs.

Alternatively, it is not possible to mannequin Peritext on REG by replaying. It’s because REG’s “native backtracking suffices” depends on the algorithm satisfying “the identical operation will produce the identical impact, whatever the present state,” which Peritext doesn’t adhere to. For instance, when inserting the character “x” at place p, whether or not “x” is daring depends upon “whether or not p is surrounded by daring” and “whether the tombstones at p contain boundaries of bold and other styles (opens in a new tab).”

Loro’s Wealthy Textual content CRDT

Algorithm

• The op ID of the style operation
• The style’s key-value pair
• The style’s Lamport timestamp (opens in a new tab)
• Type enlargement habits: Determines whether or not newly inserted textual content earlier than or after the model boundaries ought to inherit the model.

The strategy to find out a personality’s model is as follows:

• Discover all model anchor pairs that embrace the character, the place every pair is created by the identical model operation
• Mixture pairs based on the important thing. There could also be a number of model pairs with the identical key however completely different values. In such instances, the worth with the best Lamport timestamp is chosen (if Lamport timestamps are equal, then use the peer ID to interrupt the tie)

Opposite to Yjs’s method of using control characters (opens in a new tab) for wealthy textual content, our algorithm pairs begin and finish anchors once they originate from the identical model operation. This strategy precisely handles the next eventualities:

These particular management characters should not uncovered to the person; every management character is successfully of zero size from the person’s perspective. Our information construction helps varied strategies of measuring textual content size for indexing textual content content material. Apart from Unicode, UTF-16, and UTF-8, we additionally measure our wealthy textual content size in Entity size. It treats every model anchor as an entity with a size of 1 and measures plain textual content in Unicode size.

Native Habits

Behavior When Inserting Text at Style Boundaries

Rule 1 should be prioritized over rules 2 and 3 to prevent the accidental creation of a new style (opens in a new tab).

The present technique first scans ahead to seek out the final place satisfying guidelines 1 and a couple of.

Then, it scans backward to seek out the primary place satisfying rule 3.

Merging Distant Updates

Loro treats style anchors as a special element and handles them using the same List CRDT for resolving concurrent conflicts. The logic related to rich text is independent of the particular List CRDT. Therefore, this algorithm can rely on any List CRDT algorithm for merging remote operations. Loro utilizes the Fugue (opens in a new tab) Record CRDT algorithm.

When new model anchors are inserted by distant updates, new kinds are added; if outdated model anchors are deleted, the corresponding outdated kinds are eliminated.

Robust Eventual Consistency

Criteria in Peritext

The Peritext paper (opens in a new tab) specifies the intent-preserving merge habits for wealthy textual content inline format. Loro’s wealthy textual content algorithm efficiently passes all take a look at instances outlined therein.

1. Concurrent Formatting and Insertion

2. Overlapping Formatting

Like Peritext, we model unbolding by adding a new style with the key bold and the value null.
The final value of each style key on each character is determined by the style with the greatest Lamport (opens in a new tab) timestamp that features the character. Thus, it simply helps this case.

See Also

How does one patch KDE2 beneath FreeBSD?

3. Textual content Insertion at Span Boundaries

4. Styles that Support Overlapping

We represent the rich text using Quill’s Delta (opens in a new tab) format.

[
	{ insert: 'Gandalf', attributes: { bold: true } },
	{ insert: ' the ' },
	{ insert: 'Grey', attributes: { color: '#cccccc' } }
]

Nevertheless, it can not deal with instances with a number of values assigned to the identical key. So, it is a headache to deal with the kinds that help overlapping.

For instance, within the above case, the textual content “fox” is commented on by each Alice and Bob. We will not characterize it with Quill’s Delta format immediately.
So the doable workaround contains:

Flip the attribute worth into an inventory

[
  { insert: "The ", attributes: { comment: [{ ...commentA }] } },
  {
    insert: "fox",
    attributes: { remark: [{ ...commentA }, { ...commentB }] },
  },
  { insert: " jumped", attributes: { remark: [{ ...commentB }] } },
]

Use op ID that creates the op as the important thing of the attribute

[
  { insert: "The ", attributes: { "id:0@A": { key: "comment", ...commentA } } },
  {
    insert: "fox",
    attributes: {
      "id:0@A": { key: "comment", ...commentA },
      "id:0@B": { key: "comment", ...commentB },
    },
  },
  {
    insert: " jumped",
    attributes: { "id:0@B": { key: "comment", ...commentA } },
  },
]

However each require particular behaviors for each CRDT lib and for software code, that are painful to work with.

Lastly, we discovered that the optimum strategy to characterize an overlappable model was to make use of <key>: as a prefix and permit customers to assign a singular suffix to create a definite model key.
This technique simplifies the CRDTs library code, because it does not require dealing with particular instances.
It successfully addresses eventualities the place a number of feedback overlap and can be user-friendly for software coding.

[
	{ insert: "The ", attributes: { "comment:alice": "Hi" } },
	{
		insert: "fox",
		attributes: { "comment:alice": "Hi", "comment:bob": "Jump" },
	},
	{ insert: " jumped", attributes: { "comment:bob": "Jump" } },
]

Following is the instance code in Loro:

const doc = new Loro();
doc.configTextStyle({
	remark: { broaden: "none", }
})
const textual content = doc.getText("textual content");
textual content.insert(0, "The fox jumped.");
textual content.mark({ begin: 0, finish: 7 }, "remark:alice", "Hello");
textual content.mark({ begin: 4, finish: 14 }, "remark:bob", "Leap");
anticipate(textual content.toDelta()).toStrictEqual([
	{
		insert: "The ", attributes: { "comment:alice": "Hi" },
	},
	{
		insert: "fox", 
		attributes: { 
			"comment:alice": "Hi", 
			"comment:bob": "Jump" 
		},
	},
	{
		insert: " jumped", attributes: { "comment:bob": "Jump" },
	},
	{
		insert: ".",
	}
])

Implementation of Loro’s Wealthy Textual content Algorithm

Architecture of Loro

For more details, see the documentation on DocState and OpLog (opens in a new tab).

Implementation of Loro’s Wealthy Textual content CRDT

For rich text, Loro reuses the same DiffCalculator as Loro List, based on the Fugue (opens in a new tab) algorithm. Consequently, the first logic associated to wealthy textual content is concentrated in DocState. This contains expressing kinds, inserting new characters, and representing a number of index codecs.

Within the illustration of wealthy textual content state, we distinguish between the info construction ContentTree, which expresses the textual content (together with model anchors), and StyleRangeMap, which expresses kinds.

Each constructions are constructed on B+Bushes.

ContentTree is accountable for environment friendly textual content discovering, insertion, and deletion. It may well index particular insertion/deletion positions utilizing Unicode/UTF-8/UTF-16/Entity index. It doesn’t retailer what particular model every textual content phase ought to have.

We constructed the next B+Tree construction primarily based on our generic-btree library (opens in a new tab) to specific textual content in reminiscence:

• Every inside node within the B+Tree shops the Unicode char size, UTF-16 size, UTF-8 size, and Entity size of its subtree. The Entity size considers the size of fashion anchors as 1, in any other case 0.
• The leaf nodes of the B+Tree are textual content or model anchors.

StyleRangeMap is accountable for environment friendly updating/querying of fashion ranges.

Within the StyleRangeMap B+Tree expressing kinds:

• Every inside node shops the entity size of its subtree.
• Every leaf node shops the gathering of fashion info for the corresponding vary and its `entity size.

Separating the textual content ContentTree and magnificence StyleRangeMap into two constructions goals for higher efficiency optimization. On wealthy textual content, model info is usually not plentiful and tends to have good continuity, comparable to a number of paragraphs having the identical format, which will be expressed with a single leaf node. Nevertheless, our construction for storing textual content is unsuitable for leaf nodes with giant content material, as conversion time between completely different encoding codecs would change into excessively lengthy.

When a person inserts a brand new character at Unicode index = i, the next happens:

• Discover the place at Unicode index = i in ContentTree.
• Examine if there are any adjoining model anchors at this place. If not, immediately insert.
• If there are, resolve whether or not to insert to the left or proper of the corresponding model anchor primarily based on its sort and properties. If there are a number of such model anchors, insert them based on the earlier part on “Behavior When Inserting Text at Style Boundaries”.

Testing

How to Use

const doc = new Loro();
doc.configTextStyle({
	bold: {
		expand: "after",
	},
	comment: {
		expand: "none",
		overlap: true
	},
	link: {
		expand: "none"
	}
});
 
const text = doc.getText("text");
text.insert(0, "Hello world!");
text.mark({ start: 0, end: 5 }, "bold", true);
expect(text.toDelta()).toStrictEqual([
	{
		insert: "Hello",
		attributes: { bold: true },
	}, 
	{
		insert: " world!",
	}
] as Delta<string>[]);
 
text.insert(5, "!");
expect(text.toDelta()).toStrictEqual([
	{
	    insert: "Hello!",
	    attributes: { bold: true },
	}, {
	    insert: " world!",
	}
] as Delta<string>[]);

Summary

This article presents Loro’s rich text algorithm design and implementation. Its correctness is readily demonstrable. It can be built upon any existing List CRDT algorithm. It allows Loro to support rich text collaboration using REG and Fugue (opens in a new tab), combining the strengths of a number of CRDT algorithms.

We’re repeatedly refining its design and actively looking for design companions. We’re open to all types of suggestions and constructive criticism. Ought to you’ve gotten any proposals for collaboration, please attain out to zx@loro.dev