fugue

Fractional indexing without conflicts - based on Fugue. 998 bytes (minified and brotlied) and no dependencies.

Fractional indexing is a technique to create an ordering that can be used for Realtime Editing of Ordered Sequences.

Heavily based on position-strings with added support for keys that were previously created by other libraries (e.g. fractional-indexing).

Motivation

Traditional fractional indexing libraries typically use deterministic algorithms to generate positions between two points. This works well in single-user scenarios, but it causes conflicts in distributed systems when multiple users insert items at the same position simultaneously.

For example, if two users try to insert between keys a0 and a2, a deterministic algorithm would generate the same new position (e.g., a1) for both users, causing a conflict. Also, with non-deterministic algorithms in collaborative text applications, when two users concurrently insert text at the same position, these algorithms interleave the inserted text passages, resulting in unreadable content.

Fugue solves this problem by using unique client IDs, ensuring that simultaneous insertions from different clients create distinct, non-interleaving keys. This enables truly conflict-free collaborative editing without requiring any coordination between clients.

Installation

1npm install fugue
2# or
3yarn add fugue
4# or
5pnpm add fugue

Usage

First, create an instance of Fugue. You need to pass in a clientID, which is a unique identifier for the client.

The clientID should be a string that is "unique enough for the application". This means that it should be unique given how many users will be simultaneously creating positions. In practice, this can be quite small (e.g. nanoid(6)).

Client

On the client size, create a Fugue instance with a unique client ID:

1import { Fugue } from 'fugue';
2
3// created once in the runtime (this would be a short, unique ID for the client)
4// this should be chosen as having enough entropy to be unique across all clients
5// it is a good idea to reuse client IDs when possible
6export const fugue = new Fugue('client1');

Generate positions between two points using between. Pass null for start/end to generate positions at the beginning/end:

1import { fugue } from "./fugue";
2
3const first = fugue.first(); // "client1.B" - equivalent to `between(null, null)`
4
5// Insert after first
6const second = fugue.after(first); // "client1.D" - equivalent to `between(first, null)`
7
8// Insert after second
9const third = fugue.after(second); // "client1.F" - equivalent to `between(second, null)`
10
11// Insert before first
12const zeroth = fugue.before(first); // "client1.A0B" - equivalent to `between(null, first)`
13
14// Insert between second and third (midpoint)
15const secondAndHalf = fugue.between(second, third); // "client1.D0B"

The biggest benefit of using fugue over other fractional indexing libraries is that multiple independent clients can create keys simultaneously and they will not overlap:

1import { Fugue } from 'fugue'
2
3// first client
4const fugue1 = new Fugue('client1');
5// second client
6const fugue2 = new Fugue('client2');
7
8// create some initial starting first and last 
9const first = fugue1.first(); // "client1.B"
10const last = fugue1.after(initialFirst); // "client1.D"
11
12// simulating these happening in parallel (e.g. across multiple independent clients)
13const middle1 = fugue1.between(first, last); // "client1.B0B"
14const middle2 = fugue2.between(first, last); // "client1.B,client2.B"
15
16// these eventually grow to e.g.: client0.B0A0B0aH0B,client1.D,client2.B,client3.L,client4.B,client5.D,client6.B,client7.B,client10.B,client23.B,client35.B,client36.B

Server

When implementing Fugue on a server, you can create a single Fugue instance with a static client ID (e.g. "server") and share it across your server runtime. This approach works well when:

1. You need to generate position keys from server-side logic.
2. Your server operations are coordinated (e.g. through database transactions).

Note: if you are using a sync engine with "server authority" like Zero, you can instead lean on the property that Fugue is deterministic for a given client ID. This means that in your client-side code, you can optimistically generate a position with the given client ID. Then, on the server, you create a Fugue instance with the same client ID, and generate a position again. If your client is up-to-date, this will be the same position. If it's not, the server will overwrite the position with the correct value for the client ID.

1import { Fugue } from 'fugue';
2
3// Create once and export for use throughout the server
4export const fugue = new Fugue('server');
5
6async function insertItemBetween(listId, beforeItemId, afterItemId, itemData) {
7  // Always use transactions to coordinate between servers
8  return await db.transaction(async (tx) => {
9    // If beforeItemId and afterItemId are provided, get their positions
10    let beforePosition = null;
11    let afterPosition = null;
12    
13    // get the position for the before item
14    const beforeItem = beforeItemId
15      ? await tx
16          .select({ position: items.position })
17          .from(items)
18          .where(and(eq(items.id, beforeItemId), eq(items.listId, listId)))
19          .get()
20      : null;
21    
22    if (beforeItem) beforePosition = beforeItem.position;
23    
24    // get the position for the after item
25    const afterItem = afterItemId
26      ? await tx
27          .select({ position: items.position })
28          .from(items)
29          .where(and(eq(items.id, afterItemId), eq(items.listId, listId)))
30          .get()
31      : null;
32    
33    if (afterItem) afterPosition = afterItem.position;
34    
35    // Generate a position between the two
36    const position = fugue.between(beforePosition, afterPosition);
37    
38    // Insert the new item with the generated position
39    await tx.insert(items).values({
40      listId,
41      position,
42      ...itemData,
43    });
44  });
45}

Features

• Generates unique, ordered keys for inserting items between other items.
  • Keys are global, immutable, grow logarithmically, and non-interleaving.
• Compatible with positions from other fractional indexing libraries.
• Written in TypeScript with zero dependencies.

License

Unlicense

Attributions

Thanks to pgte for the NPM package name and Matthew Weidner for Fugue and position-strings.