async-ordered-set

A TypeScript library implementing AsyncOrderedSet: a persistent, sorted set of fixed-size binary items, backed by a pluggable storage layer — in-memory, Node's filesystem, or the browser's Origin Private File System (OPFS).

Items never all live in memory at once. Every operation (insert, delete, slice, range queries, ...) reads and writes only the bytes it needs through the backend, using binary search and bulk block moves rather than loading the whole set. That's what makes it usable for large sets in constrained environments like a browser tab.

Installation

npm install async-ordered-set

Two entry points:

// Browser-safe: MemoryBackend, OpfsBackend, OpfsWorkerBackend
import { AsyncOrderedSet, MemoryBackend } from "async-ordered-set";

// Node-only: FsBackend
import { FsBackend } from "async-ordered-set/node";

Defining an item

Every item stored in an AsyncOrderedSet must be a fixed-size, ordered, binary value type. Implement two interfaces from async-ordered-set:

import { ComparisonResult } from "async-ordered-set";
import type { Comparable, Serializable } from "async-ordered-set";

class NumberItem implements Comparable<NumberItem>, Serializable {
  readonly byteLength = 4;

  constructor(readonly value: number) {}

  compareTo(other: NumberItem): ComparisonResult {
    if (this.value < other.value) return ComparisonResult.Less;
    if (this.value > other.value) return ComparisonResult.Greater;
    return ComparisonResult.Equal;
  }

  serialize(view: DataView, offset: number): void {
    view.setInt32(offset, this.value, true);
  }

  static deserialize(view: DataView, offset: number): NumberItem {
    return new NumberItem(view.getInt32(offset, true));
  }
}

• Comparable<T>.compareTo defines the sort order and identity — two items that compare Equal are treated as the same item (a later insert replaces the earlier one).
• Serializable writes the item into a fixed number of bytes (byteLength) at a given offset in a DataView. Every item in one set must serialize to the same byteLength — pass it once as itemByteLength when you create the set.
• deserialize is the inverse, supplied separately since it doesn't belong on an instance.

Creating a set

import { AsyncOrderedSet, MemoryBackend } from "async-ordered-set";

const set = await AsyncOrderedSet.create<NumberItem>({
  backend: new MemoryBackend(),
  itemByteLength: 4,
  deserialize: NumberItem.deserialize,
});

To reopen a set that was previously written to a backend (e.g. a file that survived a restart):

const reopened = await AsyncOrderedSet.open<NumberItem>({
  backend: await OpfsWorkerBackend.open("my-set.bin"), // a named file written earlier
  itemByteLength: 4,
  deserialize: NumberItem.deserialize,
});

Only the OPFS backends can reopen existing storage (OpfsBackend.open(name) / OpfsWorkerBackend.open(name), plus delete(name) to remove the file). MemoryBackend and FsBackend always start empty, so create() is the only way to get one.

Or, when you don't know yet whether the storage has been written to, openOrCreate() reopens an existing set and creates an empty one otherwise:

const set = await OrderedSet.openOrCreate<NumberItem>({
  backend: await OpfsWorkerBackend.open("my-set.bin"),
  itemByteLength: 4,
  deserialize: NumberItem.deserialize,
});

It only creates when the storage is genuinely untouched (its header region is all zero bytes). Storage holding data that isn't an OrderedSet still throws rather than being overwritten, and so do the two other failure cases below — openOrCreate() relaxes "nothing is there", nothing else.

open() throws if the backend doesn't contain a valid header, if itemByteLength doesn't match what was persisted, or if a previous mutation crashed mid-write and left the backend dirty — in that last case the backend must be discarded, not reopened.

Backends

All backends implement the StorageBackend interface and can be used interchangeably.

| Backend | Import | Environment | Notes | |---|---|---|---| | MemoryBackend | async-ordered-set | anywhere | Plain in-memory Uint8Array. Good default, and useful in tests. | | FsBackend | async-ordered-set/node | Node.js | A temp file on disk, via node:fs/promises. Always creates a fresh file — create() only. | | OpfsBackend | async-ordered-set | browser Worker | Origin Private File System via a synchronous access handle. Only usable inside a dedicated Worker (a browser API restriction, not a library choice). | | OpfsWorkerBackend | async-ordered-set | browser main thread | Runs OpfsBackend inside a lazily-created, shared Worker and talks to it over postMessage, so it can be constructed and used from the main thread. Pays messaging latency and a buffer copy per call in exchange for genuinely synchronous OPFS reads/writes under the hood. |

import { OpfsBackend } from "async-ordered-set"; // call from inside a Worker
const backend = await OpfsBackend.create();

import { OpfsWorkerBackend } from "async-ordered-set"; // call from the main thread
const backend2 = await OpfsWorkerBackend.create({ name: "my-set.bin" }); // omit `name` for a throwaway scratch file

Managing OPFS files

Both OPFS backends expose the same static file-management surface. Every backend file lives in one folder in the origin's private file system, and list() enumerates it:

await OpfsWorkerBackend.list();          // ["my-set.bin", ...] — sorted
await OpfsWorkerBackend.open("my-set.bin");
await OpfsWorkerBackend.delete("my-set.bin");

list() enumerates the folder without opening anything, so a returned name means only that the file exists — not that it holds a valid OrderedSet, and not that another tab or worker isn't holding an exclusive handle on it. It also includes scratch files from a create() with no name, for as long as one is open (close() deletes those by default).

delete() throws if the name doesn't exist, or if any backend anywhere still holds an open handle on the file — close that backend first.

Using the set

AsyncOrderedSet's async operations are automatically serialized in FIFO order — you can fire off multiple calls without awaiting each one individually, and they'll run one at a time in the order they were made.

await set.insert(new NumberItem(5));      // true: newly added
await set.insert(new NumberItem(5));      // false: replaced an equal item
await set.insertAll([
  new NumberItem(1),
  new NumberItem(9),
  new NumberItem(3),
]);                                        // returns how many were newly added

await set.has(new NumberItem(5));         // true
await set.delete(new NumberItem(5));      // true: removed
await set.deleteRange(new NumberItem(1), new NumberItem(9)); // [1, 9), returns count removed
await set.clear();                        // removes everything, returns count removed

set.size;                                 // number of items (sync)
set.front();                              // smallest item, or undefined (sync)
set.back();                               // largest item, or undefined (sync)

await set.count(new NumberItem(1), new NumberItem(9)); // items in [1, 9) — no item reads
await set.count(new NumberItem(1));       // from 1 through the back

await set.slice({ start: 0, count: 10 }); // items by logical index

const bounds = await set.findSlice({      // index bounds of a comparable range
  start: new NumberItem(1),
  end: new NumberItem(9),                 // omit for "through the back"
});                                       // { start, end } — end exclusive
await set.slice({                         // ...then read the items
  start: bounds.start,
  count: bounds.end - bounds.start,
});

for await (const item of set) {           // full ascending iteration
  console.log(item.value);
}

for await (const chunk of set.sliceGen(bounds)) {
  // lazy range iteration, a chunk of items at a time — stop early (`break`)
  // without reading the rest
}

set.sliceGen({                            // defaults to the whole set
  start: 0,
  end: set.size,
  order: "desc",                          // walk from `end` down to `start`
  chunkSize: 256,                         // items read per backend round trip
});

Both sliceGen and the plain for await iteration hold the operation lock until the generator is exhausted or closed, so a caller that stops early should break (or call return()) to let queued operations run.

insertAll is much cheaper than the equivalent loop of insert calls for large batches — it places items with a handful of bulk block moves instead of shifting the underlying storage once per item.

Reclaiming space

Storage capacity grows automatically as you insert, but — like Rust's Vec — it never shrinks on its own. After removing a large number of items, call compact() to shrink the backend back down to what's actually needed:

await set.deleteRange(new NumberItem(0), new NumberItem(1000));
await set.compact();

clear() is the equivalent for emptying the set entirely — it removes every item and compacts in one step, cheaper than deleteRange over the whole range followed by a separate compact() call:

await set.clear();

Error handling

Every failure the library raises deliberately is a subclass of OrderedSetError, so one instanceof check covers all of them. Each also carries a stable code string, for switching on the failure across a bundle boundary or in a structured log where class identity doesn't survive.

| Error | code | Raised when | |---|---|---| | InvalidItemByteLengthError | INVALID_ITEM_BYTE_LENGTH | itemByteLength isn't a positive integer. Carries itemByteLength. Nothing touched the backend. | | InvalidHeaderError | INVALID_HEADER | open() found no header this library wrote — uninitialized storage, or unrelated data. Nothing was modified. | | ItemByteLengthMismatchError | ITEM_BYTE_LENGTH_MISMATCH | The stored set's items are a different size than requested. Carries storedItemByteLength and expectedItemByteLength. | | IncompleteMutationError | INCOMPLETE_MUTATION | The header is still dirty: a previous mutation never finished. The backend must be discarded. | | UnusableOrderedSetError | UNUSABLE_SET | A mutation on this instance already failed, so it is permanently unusable. cause is the original failure. | | BackendError | BACKEND_FAILURE | A storage operation failed inside a backend and couldn't be propagated as-is — notably OpfsWorkerBackend, whose errors cross a postMessage hop. |

import { OrderedSetError, IncompleteMutationError } from "async-ordered-set";

try {
  set = await OrderedSet.open<NumberItem>(options);
} catch (err) {
  if (err instanceof IncompleteMutationError) {
    await OpfsWorkerBackend.delete("my-set.bin"); // unrecoverable — start over
  } else if (err instanceof OrderedSetError) {
    console.error(err.code, err.message);
  } else {
    throw err; // the storage medium itself failed
  }
}

Errors raised by a backend's underlying storage medium pass through unwrapped, so anything that isn't an OrderedSetError came from below the library.

If a mutation throws partway through (e.g. the backend's storage medium fails), the OrderedSet instance becomes permanently unusable — every subsequent call throws UnusableOrderedSetError, and the backend must be discarded rather than reopened, since it may have been left in an inconsistent state. Handle mutation errors as fatal for that set instance.

Writing a custom backend

Implement StorageBackend (from async-ordered-set) if you need a storage medium that isn't provided:

interface StorageBackend {
  readonly capacity: number;
  ensureCapacity(minBytes: number): Promise<void>; // grow to at least minBytes
  resize(newBytes: number): Promise<void>;         // set capacity to exactly newBytes
  read(offset: number, length: number): Promise<Uint8Array>;
  writeAt(offset: number, source: Uint8Array): Promise<void>;
  copyWithin(targetOffset: number, sourceOffset: number, length: number): Promise<void>;
}

read() must return a Uint8Array the caller owns outright: never a window onto the backend's own storage, and never reused by the backend afterwards.

See the implementations under src/backends/ for reference, and tests/test-utils/chunked-backend.ts for a deliberately non-contiguous backend used to catch code that wrongly assumes storage is one flat buffer.

Development

npm run test        # run tests (Node + browser)
npm run typecheck
npm run build
npm run bench        # in-process benchmarks
npm run bench:opfs   # OPFS-backed benchmarks (browser)