async-ordered-set

A TypeScript library implementing OrderedSet: 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, OpfsMainBackend
import { OrderedSet, MemoryBackend } from "async-ordered-set";

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

Defining an item

Every item stored in an OrderedSet 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 { OrderedSet, MemoryBackend } from "async-ordered-set";

const set = await OrderedSet.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 OrderedSet.open<NumberItem>({
  backend: await FsBackend.open("my-set.bin"), // whichever backend you used
  itemByteLength: 4,
  deserialize: NumberItem.deserialize,
});

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. Fastest browser option, but only usable inside a dedicated Worker (a browser API restriction, not a library choice). | | OpfsMainBackend | async-ordered-set | browser main thread | OPFS via FileSystemFileHandle, usable outside a Worker. Slower than OpfsBackend since every write opens and closes its own writable stream — trades throughput for the guarantee that a read always sees every write that was awaited before it. |

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

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

Using the set

OrderedSet'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.slice({ start: 0, count: 10 }); // items by logical index
await set.findSlice({                     // items by comparable range
  start: new NumberItem(1),
  end: new NumberItem(9),                 // omit for "through the back"
});

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

for await (const item of set.findSliceGen({ start: new NumberItem(1) })) {
  // lazy range iteration — stop early (`break`) without reading the rest
}

await set.findSlice({                     // or findSliceGen — same options
  start: new NumberItem(1),
  end: new NumberItem(9),
  reversed: true,                         // walk from `end` down to `start`
  chunkSize: 256,                         // items read per backend round trip
});

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

If a mutation throws partway through (e.g. the backend's storage medium fails), the OrderedSet instance becomes permanently unusable — every subsequent call throws, 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
  readAt(offset: number, target: Uint8Array): Promise<void>;
  writeAt(offset: number, source: Uint8Array): Promise<void>;
  copyWithin(targetOffset: number, sourceOffset: number, length: number): Promise<void>;
}

See the implementations under src/backends/ for reference, and src/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)