"Position Strings" for Collaborative Lists and Text

Matthew Weidner | Apr 13th, 2023
Home | RSS Feed
Keywords: position-strings, collaborative text editing, CRDTs, fractional indexing, Fugue

I recently published a new TypeScript library on npm: position-strings.

You can read the docs there for full info, but basically, it provides “position strings” for use in collaborative lists or text strings. Each position string points to a specific list element (or text character), and the list order is given by the lexicographic order on position strings.

For example, a collaborative text editor using the library could represent the text "Hello world" as:

[
  { position: "r95sU223.B", char: 'H' },
  { position: "r95sU223.D", char: 'e' },
  { position: "r95sU223.F", char: 'l' },
  { position: "r95sU223.H", char: 'l' },
  { position: "r95sU223.J", char: 'o' },
  { position: "r95sU223.N", char: ' ' },
  { position: "r95sU223.N,Y2FsVQbt.B", char: 'w' },
  { position: "r95sU223.N,Y2FsVQbt.D", char: 'o' },
  { position: "r95sU223.N,Y2FsVQbt.F", char: 'r' },
  { position: "r95sU223.N,Y2FsVQbt.H", char: 'l' },
  { position: "r95sU223.N,Y2FsVQbt.J", char: 'd' }
]

Here the array is sorted lexicographically by position. (The funny-looking substrings "r95sU223" and "Y2FsVQbt" are random IDs, used to ensure uniqueness when multiple users type concurrently.)

When the user types ',' between "Hello " and "world", the text editor will ask the library for a new position string in between the positions of ' ' and 'w':

// At the start of the app:
import { PositionSource } from "position-strings";
const source = new PositionSource();

// When the user types between ' ' @ "r95sU223.N" and 'w' @ "r95sU223.N,Y2FsVQbt.B":
const newPos = source.createBetween("r95sU223.N", "r95sU223.N,Y2FsVQbt.B");
// newPos is "r95sU223.J,bLBGHJmO.B", which is indeed between:
// "r95sU223.N" < "r95sU223.J,bLBGHJmO.B" < "r95sU223.N,Y2FsVQbt.B".

The text editor then adds { position: newPos, char: ',' } to its array in sorted order. It also broadcasts this object to collaborators, who add it to their own arrays. Likewise, when the user deletes a character, the text editor broadcasts the deleted position and all collaborators delete its list entry.

Position-strings implements the hard part of a list CRDT, with a minimal, lightweight API. Unlike most CRDT implementations, position-strings doesn’t “own” the list state or store extra metadata¹; instead, you are free to store the positions and chars (or list values) wherever you like. For example, you could store each { position, char } as a row in a cloud-synced database like Firebase Realtime DB - I provide an example app that implements collaborative text editing this way.

You can also think of position-strings like fractional indexing, but with a few extra features: global uniqueness, non-interleaving, and slower (logarithmic) length growth in sequences.

The catch is that a list/text CRDT using position-strings will have more storage and network overhead than a dedicated data structure like Y.Array. In my benchmarks, the position strings are typically 10-100 characters long, so you’ll have at least 10-100 bytes of storage overhead per list element/text character. This is fine for short documents and simple apps, but could be a problem for fancier uses.

Under the hood, position-strings uses an optimized version of Fugue’s string implementation. You can read about the full algorithm here.

⭐️ I'm on the market for a software engineering job post-PhD.

Home • Matthew Weidner • PhD student at CMU CSD • mweidner037@gmail.com • @MatthewWeidner3 • LinkedIn • GitHub