As we're approaching the new major version of Yjs (v14), there are few breaking changes worth talking about. While most of them concern the API, a binary format itself remains stable (so don't be afraid, your document state will still be parseable). But let's cover a major breaking change on that front.
As part of Yjs version upgrade, the decision was made to stop supporting a move feature. I've written and discussed this feature myself in the past. But what the move was all about?
The essence of move operation was to allow users concurrently modify the order of elements in a collaborative array. One could think, that this could be simply achieved by a combination of remove/insert operations, but there's a catch: in a CRDT setting this could result in a concurrent conflict when the same element is removed from one position (X) and then reinserted in two different ones (eg. Y and Z). Since conflict resolution wouldn't know about the semantics, we could end up with the same element present at two different locations (Y and Z). Even worse: if our element was another Y-collection, we couldn't maintain lifetime tracking of it, meaning that concurrent edits to that collections would also be lost on delete.
So, if a dedicated move operation was so great, why don't just keep it? The thing is, Yjs internals are using iterator pattern heavily almost everywhere, and move affects it, introducing a new layer of complexity that bleeds throughout the entire codebase. On the other hand, the move feature - while quite interesting as a problem - is scarcely used by most of the users.
Building move semantics
So, how can we achieve move semantics using existing primitives? Below, we'll present a pattern which can achieve it without using a dedicated built-in mechanism.
Our target here is a XmlFragment, but the same can be done through yjs v14 new YType collection (since it's capable of holding both indexed elements and maps). It's also more grounded in reality: originally editors like y-prosemirror represented editor area as XmlFragment, while the individual paragraphs would be represented as a list of XmlElements inside of it. With this, we could ie. implement shuffling paragraphs around without loosing their concurrent edits.
The core of our algorithm is fractional index. It was presented on this blog on several occasions (1, 2), so feel free to read these posts for more in-depth explanation. The point is that it allows us to build (byte)strings which lexical order matches their insert order (given their neighbouring sequences). It's simple and works well in concurrent scenarios.
// chars used by fractional index
const CHARS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
export const fractionalIndex = (prev, next) => {
let i = 0;
const lower = prev || '';
const higher = next || '';
let result = '';
for (; i < lower.length || i < higher.length; i++) {
const lowerIdx = i < lower.length ? CHARS.indexOf(lower[i]) : 0;
const higherIdx = i < higher.length ? CHARS.indexOf(higher[i]) : CHARS.length;
if (higherIdx > lowerIdx + 1) {
// there's enough space in between lower and higher chars
// to fit a new unique element. We pick a midpoint here, so that
// we leave enough space on either end. This way continuous prepending
// shouldn't allocate new extra character for each operation.
result += CHARS[Math.floor((lowerIdx + higherIdx) / 2)]
return result;
} else {
result += CHARS[lowerIdx]
}
}
result += CHARS[CHARS.length / 2];
return result;
}
Now, let's create a convenient wrapper around collection, which elements we want to reorder.
import * as Y from 'yjs';
class Reorderable {
constructor(fragment) {
this._fragment = fragment // CRDT collection
this._isDirty = false // marker used to trigger refresh
this._items = [] // collection elements in their final order
// observe collection ie. in case if it was modified by remote update
this._fragment.observeDeep((events) => {
for (const e of events) {
if (e.keys.has('ord') || e.changes.added.size > 0 || e.changes.deleted.size > 0 ) {
// collection was modified and _items needs to be refreshed
this._isDirty = true
break;
}
}
})
}
get items() {
if (this._isDirty) {
this._refresh()
}
return this._items
}
_refresh() {
this._items = this._fragment.toArray()
this._items.sort(compareNodes)
this._isDirty = false;
}
}
function compareNodes(a, b) {
const ordA: string = a.getAttribute('ord') || ''
const ordB: string = b.getAttribute('ord') || ''
return ordA < ordB ? -1 : ordA > ordB ? 1 : 0
}
The code above keeps quite simple structure. We keep around the y-collection of y-collections (XML nodes in this case). Each child node holds an ord attribute, which contains a fractional index string used to order elements. As we mentioned, fractional indexes have structure which has the same ordering as their insert ordering. This is what keeps their position correct.
For inserting an element, it's not enough to just put it at expected index. We also need to supply a fractional index that matches expected position:
class Reorderable {
insert(index, item) {
Y.transact(this._fragment.doc, () => {
const findex = this._createFractionalIndex(index)
this._fragment.insert(index, [item])
item.setAttribute('ord', findex)
})
}
delete(index) {
const deletedItem = this.items[index]
// we need to find original index of a deleted element on the unsorted array
let originalOrder = this._fragment.toArray()
let originalIndex = originalOrder.indexOf(deletedItem)
this._fragment.delete(originalIndex)
}
_createFractionalIndex(i) {
const items = this.items;
const prev = (i == 0 ? null : items[i - 1].getAttribute('ord').split(':')[0]);
const next = (i == items.length ? null : items[i].getAttribute('ord').split(':')[0])
return fractionalIndex(prev, next) + ':' + this._fragment.doc.clientID
}
}
You can see that code above doesn't just create fractional index, but also stitches it with current document's clientID. That's because it's possible that two different clients could produce two identical fractional indexes. Therefore, we add their own unique IDs to guarantee uniqueness.
Finally, as for the move operation itself: it's basically a manner of updating the ord attribute with a new fractional index matching the destination position.
class Reorderable {
move(source, destination) {
if (source === destination) return;
const item = this.items[source]
const findex = this._createFractionalIndex(destination)
this._isDirty = true
item.setAttribute('ord', findex)
}
}
How is that resistant to the issues we mentioned before? Unlike the delete/insert, here we're updating the same CRDT entry, and recompute the final position afterwards. Since maps will have their entries resolved into a single consistent value each time, we don't risk having two phantom inserts appearing. There's also no lifetime issues, since we're not deleting/reinserting the XML node, we're just changing its attribute.
Summary
Using fractional indexes is a cheap and simple trick, that can be used for conflict-free reordering quite well. It's also pretty universal. Here we presented it in combination with Yjs, even though the library itself doesn't natively offer support for fractional indexing or LSeq CRDTs. But nothing stands in your way to use it together with different CRDT libraries.
Comments