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

npm install fugue
# or
yarn add fugue
# or
pnpm 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:

import { Fugue } from 'fugue';

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

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

import { fugue } from "./fugue";

const first = fugue.createBetween(null, null); // "client1.B"

// Insert after first
const second = fugue.createBetween(first, null); // "client1.D"

// Insert after second
const third = fugue.createBetween(second, null); // "client1.F"

// Insert before first
const zeroth = fugue.createBetween(null, first); // "client1.A0B"

// Insert between second and third (midpoint)
const secondAndHalf = fugue.createBetween(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:

import { Fugue } from 'fugue'

// first client
const fugue1 = new Fugue('client1');
// second client
const fugue2 = new Fugue('client2');

// create some initial starting first and last 
const first = fugue1.createBetween(null, null); // "client1.B"
const last = fugue1.createBetween(initialFirst, null); // "client1.D"

// simulating these happening in parallel (e.g. across multiple independent clients)
const middle1 = fugue1.createBetween(first, last); // "client1.B0B"
const middle2 = fugue2.createBetween(first, last); // "client1.B,client2.B"

// 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).

import { Fugue } from 'fugue';

// Create once and export for use throughout the server
export const fugue = new Fugue('server');

async function insertItemBetween(listId, beforeItemId, afterItemId, itemData) {
  // Always use transactions to coordinate between servers
  return await db.transaction(async (tx) => {
    // If beforeItemId and afterItemId are provided, get their positions
    let beforePosition = null;
    let afterPosition = null;
    
    // get the position for the before item
    const beforeItem = beforeItemId
      ? await tx
          .select({ position: items.position })
          .from(items)
          .where(and(eq(items.id, beforeItemId), eq(items.listId, listId)))
          .get()
      : null;
    
    if (beforeItem) beforePosition = beforeItem.position;
    
    // get the position for the after item
    const afterItem = afterItemId
      ? await tx
          .select({ position: items.position })
          .from(items)
          .where(and(eq(items.id, afterItemId), eq(items.listId, listId)))
          .get()
      : null;
    
    if (afterItem) afterPosition = afterItem.position;
    
    // Generate a position between the two
    const position = fugue.createBetween(beforePosition, afterPosition);
    
    // Insert the new item with the generated position
    await tx.insert(items).values({
      listId,
      position,
      ...itemData,
    });
  });
}

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.