Realtime collaborative text editing is a field, that has been extensively researched and developed in a Conflict-free Replicated Data Types communities. No wonder: it's the most widely used application of CRDTs in practice.
While we're still in the early days of CRDTs (I believe), but when you take a look at the actual products, most of them nowadays use algorithms like YATA, RGA or Fugue, which all share many things in common.
Fractional Indexes dropped out of favour when it comes to text editing. There were few reasons for that, but most important ones:
- The basic implementation of fractional index suffers from interleaving problem (characters typed by different people in the same place would mix with each other).
- Fractional index itself is a byte string. Stamping every single character with a metadata many times its size is simply not feasible.
We already discussed the solution for interleaving problem. Today we'll cover the second one: we're going to build a block-wise fractional index - using block split/merge semantics similar to how Yjs operates. This will allow us to reduce metadata overhead to a point where it can actually be used in practical projects.
Implementation
What are we going to discuss here is the JavaScript implementation. You can actually try it out:
Peer A
sid = 1 0 pendingPeer B
sid = 2 0 pendingWe'll focus on distinctive points of our approach. A core of our data structure is a sorted map of entries (implemented as JavaScript array with custom binary search algorithm). Each entry has:
keywhich is Fractional Key itself implemented asUint32Array. Just like in the non-interleaving LSeq blog post, array will contain pairs of two UInt32 values: session ID and sequence number to help us avoid interleaving. Read linked post for more explanation.valuewhich is a string representing fragment of consecutive text.deletedflag used to mark tombstones. While Fractional Indexes have other ways to represent deletions, tombstones are quite good approach for rich text editing, since they give us features like versioning and text diffs for free.
Fractional Index generation
First let's cover how to generate fractional index keys.
Important distinction from usual approach is that our goal is not to insert a single element, but a series of adjacent characters. In order to be able to insert in-between any two given characters, each one of them must be uniquely identifiable.
Take a following example: peerB.insert(1, 'Bob') - we want to insert 3-character string at position 1. Let's assume that we already have existing string and character at position 0 has key A:0, while existing position 1 holds A:1. Using non-interleaving algorithm and stick-to-left key generation strategy, we could make following entries:
A:0/B:0=BA:0/B:1=oA:0/B:2=b
That's one way to write them. Alternatively, we could represent them with a single key+block: A:0/B:0 = Bob with an implicit assumption that this entry holds keys A:0/B:0..2 - last segment's sequence number + character count of the string. That's what we're going to do here.
First we need to find neighbours for the key we're going to generate:
function neighbors(items, i) {
for (let index = 0; i >= 0 && index < items.length; index++) {
const e = items[index]
if (e.deleted) continue; // skip over tombstones
if (i < e.value.length)
return [index, i] // i remainder may be inside of a block
i -= e.value.length
}
return [-1, 0] // not found
}
Function above returns a pair of numbers: index of of a right neighbour and offset within that neighbour if the text index we're looking for can be found inside of the block.
The if (e.deleted) continue; line is useful optimisation worth a bit of explanation: assume that position i exists in between existing entries, but since we only count alive entries, the same position could cover one or more tombstoned entries. Question: should we insert new entry before or after the tombstoned entry?
The answer here is always after tombstone. Why? Imagine 3 entries taking part in that decision:
A:1..6=helloA:7..11=world(tombstoned)B:1=!
If we decide to insert key between hello and world that means inserting between A:6 and A:7 which always leads to producing a longer key (eg. A:6/A:1). We want to avoid going into deeper keys whenever possible. Inserting it after worldgives a chance to keep the key flat if insert was made by the same peer (eg. A:12). If any of the keys A:1..6 will also be deleted in the future, we can also try to merge them with existing tombstoned entry, reducing total number of required entries.
Now, if we want to create a key, we first need to find a first available segment in-between two fractional keys, that can hold string of given length:
/**
* @param {Uint32Array} lo is lower bound Fractional Key
* @param {Uint32Array} hi is upper bound Fractional Key
* @param {number} sid is current peer's session ID (UInt32)
*/
function findNext(lo, hi, sid) {
const key = []
for (let i = 0; true; i += 2) { // we iterate through segments in pairs
let minSeq = 0 // the smallest available sequence number in current segment
if (i < lo.length) {
const loSid = lo[i] // sequence number of lower bound segment
if (loSid === sid) {
minSeq = lo[i+1] + 1
} else if (loSid > sid) {
minSeq = -1
}
if (minSeq >= 0) {
// `free` says how many elements can be fit at current segment
// level before reaching upper key boundary
let free = 4294967295 - minSeq // MAX UInt32
if (hi && hi.length > i) {
const hiSid = hi[i] // session ID of upper bound segment
if (hiSid === sid) {
free = Math.max(0, hi[i+1] - minSeq - 1)
} else if (hiSid < sid) {
free = 0
}
}
if (free > 0) {
// we have free space, write last segment and return new key
key.push(sid) // session ID
key.push(minSeq) // sequence number
return [Uint32Array.from(key), free]
}
}
// copy segment of lower bound fractional key
key.push(loSid) // session ID
key.push(lo[i+1]) // sequence number
} else if (hi && hi.length > i) {
const hiSid = hi[i]
// push next segment and make sure it's not above upper bound key
if (hiSid <= sid) {
key.push(0) // session ID
key.push(0) // sequence number
} else {
key.push(sid) // session ID
key.push(0) // sequence number
return [Uint32Array.from(key), MAX_FREE]
}
} else {
key.push(sid) // session ID
key.push(0) // sequence number
return [Uint32Array.from(key), MAX_FREE]
}
}
throw Error('unreachable')
}
A function above is responsible of building a fractional key, which lexical order is between its upper (hi) and lower (lo) neighbours and returns it together with a number of consecutive keys that could be created by simply incrementing the sequence number of its last index. As long as this number is lower than number of characters in text we want to insert, we're good to go.
While 2^32 should be enough, since we don't recycle the sequence number when they're deleted, there is a slight risk of running out of keys. What do we do? We turn that function into sequence generator:
function* createKeys(left, right, length, sid) {
left = left ? left : Uint32Array.from([0,0])
while (length > 0) {
const [key, free] = findNext(left, right, sid)
const len = Math.min(free, length)
length -= len
if (length > 0) {
// continue right after the last key of this chunk
left = Uint32Array.from(key)
left[left.length - 1] += (len - 1)
}
yield [key, len]
}
}
This function will generate new fractional keys for a long as it's needed to accommodate all of the characters from a string with given length. In most cases it means a single one.
Split entries
Once we know how to generate fractional keys, inserting new elements becomes easy: we chunk the incoming text assigned key and max available free space and insert it at its lexical position.
The only caveat here is that we don't do a simple binary search - we need to find insert position while taking into account that this position may existing inside of previously inserted block, splitting it to make a new space in the process:
/**
* @param {Array<({key: Uint32Array, value: string, deleted: boolean})>} items
* @param {number} i insert position (counted as UTF-16 text chars offset)
*/
function split(items, at) {
let left = 0
let right = items.length - 1
// a modified binary search
while (left <= right) {
const mid = Math.floor((left + right) / 2)
const e = items[mid]
const cmp = compare(e, at)
if (cmp === 0) {
const last = e.key.length - 1
const off = at[last] - e.key[last] + (at.length > e.key.length ? 1 : 0)
if (off > 0 && off < e.value.length) {
// `at` is inside of current entry -> split it
const n = {
key: offset(e.key, off),
value: e.value.slice(off),
deleted: e.deleted
}
items.splice(mid + 1, 0, n)
e.value = e.value.slice(0, off)
return mid + 1
} else {
return mid
}
} else if (cmp < 0) {
left = mid + 1 // search right
} else {
right = mid - 1 // search left
}
}
return left // where the key should be inserted
}
function offset(key, off) {
const n = Uin32Array.from(key) // copy key
n[n.length - 1] += off // shift last segment of key by given offset
return n
}
While the binary search with split addition is pretty straightforward, the thing worth to notice is compare function used to compare current entry against given fractional key:
function compare(entry, key) {
const a = entry.key
// compare all pairs except the last one
for (let i = 0; i < a.length - 1; i++) {
const ai = a[i]
const bi = i < key.length ? key[i] : 0
if (ai < bi) return -1
if (ai > bi) return 1
}
if (a.length > key.length) {
return 1 // key is strict prefix of an entry
} else {
const ai = a[a.length - 1]
const bi = key[a.length - 1]
if (bi < ai) return 1
const end = ai + entry.value.length
if (a.length === key.length) return bi < end ? 0 : -1 // key is within entry
return bi < end - 1 ? 0 : -1 // deeper key right after bi
}
}
Above, we include not only entry's head but also all implicit keys - inferred from entry's value.length and return equals (0) if the compared key exists within the entry.
Split is also used during deletion, since we might need to split existing block into parts if we want to delete a fragment of the text. We also may need to iterate through multiple entries in order to cover the deleted range:
class NilText {
applyRemove({key, length}) {
const at = split(this.items, key)
const last = key.length - 1
const end = key[last] + length
let i = at
while (i < this.items.length) {
const e = this.items[i]
if (sharedPrefix(e.key, key) < last) break; // left the key range
if (e.key.length > key.length) {
i++ // concurrent insert nested inside of the range: keep it
continue
}
if (e.key.length < key.length || e.key[last] >= end)
break; // past the end of the range
const tail = e.key[last] + e.value.length
if (tail <= end) {
this.items[i].deleted = true // entry fully in deleted range
} else {
// entry partially in deleted range: split it
const off = e.value.length - (tail - end)
const newKey = offset(e.key, off)
const n = {
key: e.key,
value: e.value.slice(0, off),
deleted: true
}
this.items.splice(i, 0, n)
e.key = newKey
e.value = e.value.slice(off)
break
}
i++
}
// try merge all entries in deleted range
for (; i >= at - 1; i--) merge(this.items, i)
}
}
Merge entries
Now, once we know how split is done, it would be nice if we're also able to merge entries together. It's especially important for typing: when you type text, you're effectively insert characters one by one. If we cannot merge them together, we didn't really addressed elephant in the room.
Now, the merge itself is trivial, but it can only happen in certain situations:
- Both entries are of the same type: either alive or tombstoned.
- Entries are adjacent: keys are equal, and the last segment of right one is strict follow up to the left one + left's length. Example:
left=A:0/A:1..2andright=A:0/A:3..5
function merge(items, i) {
if (i < 0 || i >= items.length - 1)
return;
const left = items[i]
const right = items[i+1]
if (left.deleted === right.deleted && adjacent(left.key, right.key, left.value.length)) {
left.value += right.value
items.splice(i+1, 1) // remove merged entry
return true
} else {
return false
}
}
function adjacent(a, b, len) {
if (a.length !== b.length)
return false
let i = 0
for (; i < a.length - 2; i++) {
if (a[i] !== b[i]) return false
}
// both segments belong to the same session and their sequence numbers
// are just a's text chunk length away from each other
return a[i] === b[i] && a[i+1] + len === b[i+1]
}
Block-wise fractional indexes have slightly better merge semantics than i.e. Yjs YATA algorithm, thanks too looser merge requirements. Since Yjs sequence number is monotonically increasing, once you insert anything off existing position, then come back to previous cursor position and continue typing, you can no longer merge older and never chunks (because its clock has progressed in between). Here, we can merge entries as long as the session ID stays the same and there's enough space at a given segment level.
What's left?
There are few other optimisations we could cover. Many of them stem from the fact that our Fractional Index is just a regular ordered key-value sequence:
- This structure could be very easily implemented to work entirely of-disk, via LMDB, RocksDB or other key-value store, giving us persistence for free
- We didn't discuss serialization, but since it's common for the entry to share the fractional key prefix with its predecessor we could simply write it as such. Basically encode length of the key + number of segments shared with previous one + the suffix that's different between the two. In fact, we could combine that with pt. 1, since key-prefix compression is natively supported by RocksDB.
- Since keys are independent of each other and don't form dependencies, it makes things like quotations and partial/range replication trivial.
- Our index lookup currently performs sequential scan, but implementing it with other data structures such as Rope could make it much faster.
If you're interested more in the proof of concept implementation, you can read the source of this page - it's been used in demo you saw.
Comments