@peoplesgrocers/lseq

TypeScript implementation of the L-SEQ algorithm for fractional indexing and list CRDTs.

The library handles edge cases that break other more naive implementations of fractional indexing. With this library you can always insert before the first item or after the last item, indefinitely.

This is exactly what you need to build realtime collaborative apps with ordering for lists or trees of items. Users can reorder or insert at arbitrary positions but in practice people really like moving items to the top or end of a list. So don't crash accept random crashes from other libraries when Alice moves yet another element to the front of the list.

Installation

npm install @peoplesgrocers/lseq

Usage

import { LSEQ } from '@peoplesgrocers/lseq';

const lseq = new LSEQ();

const first = lseq.alloc(null, null);
const second = lseq.alloc(first, null);
const between = lseq.alloc(first, second);

// String comparison gives correct order
[second, first, between].sort();  // [first, between, second]

API

new LSEQ(random?: () => number)

Create an allocator. Accepts an optional random function for deterministic testing.

lseq.alloc(before: string | null, after: string | null): string

Allocate a key between before and after.

• lseq.alloc(null, null) — first key in an empty list
• lseq.alloc(null, first) — insert at head
• lseq.alloc(last, null) — insert at tail
• lseq.alloc(a, b) — insert between a and b

compareLSEQ(a: string, b: string): number

Compare two keys. Returns -1, 0, or 1.

EvenSpacingIterator

Generate evenly-spaced keys for bulk initialization:

import { EvenSpacingIterator } from '@peoplesgrocers/lseq';

const { k, iterator } = EvenSpacingIterator.create(1000);
const keys = [];
for (const position of iterator) {
  keys.push(EvenSpacingIterator.positionToKey(k, position));
}

Design

Keys are base-64 encoded strings using the base64 url-safe alphabet -0-9A-Z_a-z. There is a compact binary representation inside. Reasonablt efficient and no serialization issues with JSON, databases, or URLs.

Standard string comparison produces correct ordering. Keys work in SQL ORDER BY, database indexes, and any language with string sorting.

Cross-language support

I wrote matching implementations for Rust, Golang, and Python; validated against a shared conformance test suite with fuzzing. If your backend isn't TypeScript, you can still allocate and work with these keys natively. This makes LSEQ a reasonable building block for your application's data model.

References

• LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing (Nédelec et al., 2013)

License

AGPL-3.0