Positions:�An Astraction for Distributed Ordering

Matthew Weidner

IFIP WG2.16

3/7/2024 @ CMU

Implementing a Text Editor

What abstraction / data structure?

• Obvious idea: An array of chars�(or optimized equivalent).
• Mental model is a map [index -> char].

0 1 2 3 4 5 6 7 8 9 …

[ B i k e r o u t e … ]

Implementing a Text Editor

Note that insertions & deletions “shift” the array indices of later chars.

0 1 2 3 4 5 6 7 8 9 …

[ B i k e r o u t e … ]

0 1 2 3 4 5 6 7 8 9 …

[ E - B i k e r o u … ]

Text Editor Features

Comments / Annotations?

Or the trail on the other river bank

{

from: 40,

to: 49,

comment: “Or ...”

}

Text Editor Features

History / Blame?

{

op: “insert”,

index: 23,

chars: “my house”

}

{

op: “delete”,

index: 23,

chars: “my house”

}

{

op: “insert”,

index: 23,

chars: “CMU”

}

Text Editor Features

Collaborative Editing?

Transforming Indices

You’re going to spend a lot of effort transforming array indices to account for other insertions & deletions.

• Shift comment/annotation endpoints
• Interpret indices in historical ops
• Adapt collaborators’ ops to your current state

Can you avoid this effort by using a better abstraction?

Talk thesis: Yes - positions.

Positions

Def. A position is an ID for a text character that is:

1. Immutable - does not “shift” like an array index.
2. Globally unique, even during collaborative editing.
3. Totally ordered - you can ask “p < q?” for any positions p, q.

​

​

[ B i k e r o u t e … ]

pos670bn

pos19Nk8

pos88LjJ

pos82uHH

pos76N32

pos12fhi

pos1fIjl

pos6098j

pos4J38n

pos4UjUj

​

​

[ E - B i k e r o u … ]

pos670bn

pos19Nk8

pos88LjJ

pos82uHH

pos76N32

pos12fhi

pos1fIjl

pos6098j

pos338Je

posAjb9n

Def. A position is an ID for a text character that is:

• Immutable - does not “shift” like an array index.
• Globally unique, even during collaborative editing.
• Totally ordered - you can ask “p < q?” for any positions p, q.

Example for intuition: Real numbers. (Not an actual solution.)

​

​

[ B i k e r o u t e … ]

0.1

0.2

0.25

0.3

0.375

0.5

0.9

0.99

0.995

0.9975

​

​

[ E - B i k e r o u … ]

0.075

0.05

0.1

0.2

0.25

0.3

0.375

0.5

0.9

0.99

Text Editing with Positions

You can model a text document as a map [position -> char].

• Insert a char: Create a new position p between its neighbors’ positions, and call text.set(p, char).
• Delete a char: Look up its position p and call text.delete(p).

Unlike with an array, other entries are unchanged!

In practice, you’ll usually use an ordered map that lets you do [position <-> index] conversions, for interacting with traditional index-based code (e.g. the renderer).

Text Editor Features - with Positions

Comments / Annotations?

Or the trail on the other river bank

{

from: pos5bjI6,

to: pos9KNo7,

comment: “Or ...”

}

Or the trail on the other river bank

Text Editor Features - with Positions

History / Blame?

By correlating positions, you can easily:

1. Show which op inserted each character (blame view).
2. Show an exact diff between two states - no guessing.
3. Select a subset of operations and view the resulting state - e.g., revert some changes without losing subsequent work.

{

op: “insert”,

pos: [pos33bnK,...],

chars: “my house”

}

{

op: “delete”,

pos: [pos33bnK,...],

chars: “my house”

}

{

op: “insert”,

pos: [pos34Ijo,...],

chars: “CMU”

}

Text Editor Features - with Positions

Collaborative Editing?

Each user stores the map of current (position, char) pairs and the set of deleted positions.

When you insert/delete, broadcast a message like shown.

Recipients update their state in the obvious way. Same messages => same state, regardless of message latency (even if P2P!).

{

op: “insert”,

pos: pos2b8il,

chars: “E”

}

{

op: “delete”,

pos: pos7789c

}

General Lists

Besides text, positions are useful in many GUI lists where insert, delete, & move are primary operations.

1. Ingredients list in a recipe
2. Powerpoint filmstrip
3. Spreadsheet rows, columns

E.g. spreadsheet formula refs (“3C”): if you store row/column positions instead of “3” and “C”, the formula will adjust automatically when row 2 is deleted.

Research Context

Research Context

Positions come from work on collaborative text editing ca. 2008-24.

Specifically Conflict-free Replicated Data Types (CRDTs) for text:�data structure with operations insert(index, char) and delete(index), s.t. each operation mutates the local state immediately and also broadcasts a message to collaborators.

Collaborators must eventually end up in the same state, regardless of message latency, reordering, or duplication (eventual consistency).

Several text CRDTs are built around positions like I described. Technical meat is in generating the positions.

What’s New?

Text CRDT papers & libraries provide a collaborative text data structure API - not direct access to positions.

• E.g. Yjs (popular web lib): You can store a position and query its index later, but you can’t make your own list from (position, value) pairs.

So using existing libraries, I’d be hard-pressed to implement:

1. A history view where users can revert prior operations.
2. Suggested changes to a text that are stored outside the main text.
3. Cherry-picking across branches in a version control system.
4. …

Position-Centered APIs

I am working on position-centered APIs so that I can eventually tackle these “hard” tasks.

• position-strings: Implements positions as lexicographically-ordered strings. E.g. for database “ORDER BY” column.
• Actual users!
• list-positions (alpha): Provides positions plus a List (ordered map) to hold them. You can manipulate List however you like - it’s an ordinary local data structure with no CRDT baggage.
• Aiming for state-of-the-art collaborative text performance.

An Algorithm for Positions

An Algorithm for Positions (1)

Idea 1: Real numbers (fractional indexing).

✅️ Immutable

✅️ Totally ordered

✅️ Dense - avg(p, q) creates a new position between p & q, for insertion

​

​

[ E - B i k e r o u … ]

0.075

0.05

0.1

0.2

0.25

0.3

0.375

0.5

0.9

0.99

❌️ Not globally unique: concurrent insertions at same place => duplicate positions.

An Algorithm for Positions (1.5)

Instead of real numbers, think of paths in a binary tree.

Dense b/c you can always create a leaf node between nodes p & q.

E

B

i

k

e

r

-

E-Bike r…

0

1

1

1

1

0

0

1

❌️ Still not globally unique.

An Algorithm for Positions (2)

Idea 2: Tree where each node has a unique ID. Position = path in the tree.

✅️ Globally unique

✅️ Immutable

✅️ Totally ordered (w/ tiebreaker)

✅️ Dense - even after concurrent insertions (bd -> bcd)

This works. Martin Kleppmann & I named its text CRDT “Fugue”.�https://arxiv.org/abs/2305.00583

a

b

d

c

e

f

ID:root

ID:bn389

ID:U8No7

ID:3jbcI

ID:qfsfG

ID:TY7bJ

ID:vIHp3

Text: abcdef

An Algorithm for Positions (2)

⚠️ Practical issues:

1. Sequential insertions (common case) -> long paths.
2. Ordered map needs to store one tree node per char.

B

i

k

e

r

Standard trick (ropes, piece tables, opt CRDTs):�Store each run of sequential insertions as a single node.

An Algorithm for Positions (3)

Standard trick (ropes, piece tables, opt CRDTs):�Store each run of sequential insertions as a single node.

ID:U8No7

ID:3jbcI

ID:root

0 1 2 3 …

ID:bn389

0 1 2 3 …

0 1 2 3 …

(bn389, 0) < (U8No7, 0) < (U8No7, 1) < …�< (bn389, 1) < (bn389, 2) < (3jbcI, 0) < …

You can compactly store a map [position -> char] as

{� bn389: “abcde”,� U8No7: “YYY”,� 3jbcI: “ZZ”�}

Text is “aYYYbcZZde”.

Challenge: Metadata Management

Metadata Management

When you reference a position over the network (or in storage), it’s easiest to send the whole path to the root.

But this is often redundant. E.g., when collaborating over TCP, suffices:

• When you create a position, send its node ID & parent info.
• To reference the position later, just send its node ID.

I call this problem metadata management: the sort order on node IDs depends on some metadata (their ancestors in the tree), which you need to “manage” so that collaborators can understand each other.

Metadata Management

​

Existing papers & libraries take one of the easy ways out:

1. Position = whole path, or
2. Position = node ID, and force programmers to ensure that metadata is delivered beforehand (e.g. via causal broadcast).

It seems like there should be “happy mediums”. E.g. when you serialize an object, your program could automatically attach the metadata for enclosed positions, minus what your recipient already knows.

As a PL outsider, this sounds similar to issues RE: serializing closures or distributed GC. Can support for positions at the language level (instead of API level) help here?

Summary

​

• A position is an ID for a text character that is immutable, globally unique, and totally ordered.
• I argue that positions are a simpler abstraction than array indices, for features like annotations, operation histories, and collaborative editing (their current use, via CRDTs).
• You can implement positions as a tree where each node has a unique ID and a “run” of sequential positions.
• Referring to a position without its all of its metadata (= tree path) allows smarter network & storage usage, but creates challenges reminiscent of distributed closures/GC.

github.com/mweidner037/list-positions