A library which generates small number representations of arbitrary non-colliding Version 4 UUIDs (stable IDs) across multiple sessions in a network. This scheme enables a distributed application to utilize the global uniqueness guarantees of UUIDs while maintaining the performance advantages of small integers.
The distributed ID allocation scheme allows clients to use, store, and reference small numbers that map to UUIDs. The primary benefits are improved memory efficiency and reduced storage size, as well as improved runtime performance when used as keys in collections or other data structures in place of UUIDs.
The scheme requires a total order for ID allocation, so the allocator is designed to work within a service that provides centralized total order broadcast.
A session can be thought of as a unique identifier for a single allocator. Even if an allocator is taken offline, serialized to disk, and rehydrated back, it's considered the same session if it has the same session ID.
The set of IDs generated by all Sessions contributing to the same distributed collection (e.g. an individual collaborative document). Uniqueness of allocated IDs is limited to the document context, and IDs are not portable between documents.
New IDs are generated via synchronous API on the allocator. The API returns a small number representation of the UUID with the following guarantees:
The allocation scheme separates the small-number IDs into two "spaces":
Each of these spaces is represented by a discrete type. This allows for the direct encoding of an ID's uniqueness guarantees without contextual ambiguity. An ID can be "normalized" from one space to the other with sychronous call.
Allocated IDs can be delivered to application authors for use in place of V4 UUIDs, with the following considerations:
Expose only session space IDs to application authors. This means that application developers don't need to manage multiple ID spaces or worry about converting IDs between session space and op space. This simplifies the data management process and reduces the chances of errors or inconsistencies.
Use op space IDs for serialized forms, such as sending information over the wire or storing it in a file. Op space IDs are in their final form if possible, which imparts a performance benefit by reducing normalization work when a client receives a network operation or rehydrates an allocator.
When serializing op space IDs, annotate the entire context (e.g., file or network operation) with the session ID. This is necessary because not all IDs in op space are in their final form. Any non-finalized IDs will still be in their session space form, unique only within that specific session. Annotating the entire context with the session ID ensures that recipients of the serialized data can correctly interpret and process the non-finalized IDs.
The allocator generates UUIDs in non-random ways to reduce entropy, optimizing storage of data. A session begins with a random UUID, and subsequent IDs are allocated sequentially. UUIDs generated with this strategy are less likely to collide than fully random UUIDs, and this fact can be leveraged to compact the on-disk and in-memory representations of the allocator.
UUID generation is O(1).
The sequential allocation approach allows the system to implement a clustering scheme.
As allocators across the network create IDs, they reserve blocks of positive ID space (clusters) for that allocator. The positive integer space is sharded across different clients, and session space IDs are mapped into these clusters.
Clusters are efficient to store, requiring only two integers: the base positive integer in the cluster and the count of reserved IDs in that cluster.
Normalization is O(logn) in the number of IDs created by the originating session, as it requires a simple binary search on the clusters owned by that session.
This library consists of three components:
distributed-id-allocator) containing the core allocator logic and data structures, as well as the full API surfacewasm-id-allocator) which adapts the core allocator API into a form optimized for interop between JavaScript and WebAssembly (via WASM Bindgen)typescript-id-allocator) which adapts the WASM API into an idiomatic and type-safe TypeScript API, with key interop performance optimizationsThis version of the allocator is a rewrite of a prior version in the Microsoft Fluid Framework, which was implemented fully in TypeScript. This effort aimed to move the core allocator from TypeScript to Rust for increased low-level control and leveraging of zero cost abstraction.
Performance comparison of this allocator and the preexisting TypeScript allocator shows appreciable improvement across most operation types (including all hotpath operations). This is achieved even with the overhead of the TypeScript <-> WASM interop boundary.
The decision to separate the core allocator as a standalone crate, separate from the WASM interop logic, was made to enable idiomatic interface with the allocator API from both JavaScript and Rust.
As a secondary benefit this also enables the core crate to be published separately for use in Rust-only codebases without the need for the wasm and typescript packages as overhead.
To build the Rust workspace, run cargo build from the rust-wasm-id-allocator folder.
We use Tarpaulin to measure code coverage. The following are the coverage results as of the time of this writing:
91.52% coverage, 788/861 lines covered
In order to build, you must have wasm-snip installed (cargo install wasm-snip).
npm run build from the typescript-id-allocator folder.npm run build:bench from the typescript-id-allocator folder.npm run build:release from the typescript-id-allocator folder.