/*! * Copyright (c) Microsoft Corporation and contributors. All rights reserved. * Licensed under the MIT License. */ import { bufferToString, createEmitter, stringToBuffer } from "@fluid-internal/client-utils"; import type { ITelemetryBaseLogger, Listenable } from "@fluidframework/core-interfaces"; import { assert } from "@fluidframework/core-utils/internal"; import type { TelemetryLoggerExt } from "@fluidframework/telemetry-utils/internal"; import { LoggingError, createChildLogger, extractTelemetryLoggerExt, } from "@fluidframework/telemetry-utils/internal"; // eslint-disable-next-line import-x/no-internal-modules -- Needed to avoid specialized /internal ITelemetryLoggerExt import type { ITelemetryLoggerExt } from "@fluidframework/telemetry-utils/legacy"; import { FinalSpace } from "./finalSpace.js"; import { type FinalCompressedId, type LocalCompressedId, type NumericUuid, isFinalId, } from "./identifiers.js"; import { type Index, readBoolean, readNumber, readNumericUuid, writeBoolean, writeNumber, writeNumericUuid, } from "./persistanceUtilities.js"; import { SessionSpaceNormalizer } from "./sessionSpaceNormalizer.js"; import { type IdCluster, Session, Sessions, getAlignedFinal, getAlignedLocal, lastFinalizedFinal, lastFinalizedLocal, } from "./sessions.js"; import type { ShardToken, IIdCompressor, IIdCompressorCore, IdCreationRange, OpSpaceCompressedId, SerializedIdCompressor, SerializedIdCompressorWithNoSession, SerializedIdCompressorWithOngoingSession, SessionId, SessionSpaceCompressedId, StableId, ShardSynchronizationToken, SerializedIdCompressorShard, ParentShardSynchronizationToken, IdCompressorEvents, } from "./types/index.js"; import { SerializationVersion } from "./types/index.js"; import { createSessionId, genCountFromLocalId, localIdFromGenCount, numericUuidFromStableId, offsetNumericUuid, stableIdFromNumericUuid, subtractNumericUuids, } from "./utilities.js"; function rangeFinalizationError(expectedStart: number, actualStart: number): LoggingError { return new LoggingError("Ranges finalized out of order", { expectedStart, actualStart, }); } const MAX_STRIDE_LENGTH = 1000000; /** * Validates the generation count in a shard synchronization token. * * @param localGenCount - The number of positions filled, including backfilled positions. * @throws {@link TypeError} if the count is not a nonnegative safe integer. */ function validateShardGenerationCount(localGenCount: number): void { if (!Number.isSafeInteger(localGenCount) || localGenCount < 0) { throw new TypeError("Invalid shard synchronization token generation count."); } } /** * See {@link IIdCompressor} and {@link IIdCompressorCore} */ export class IdCompressor implements IIdCompressor, IIdCompressorCore { private readonly eventEmitter = createEmitter(); public readonly events: Listenable = this.eventEmitter; /** * Max allowed initial cluster size. */ public static readonly maxClusterSize = 2 ** 20; // #region Local state public readonly localSessionId: SessionId; private readonly localSession: Session; private readonly normalizer = new SessionSpaceNormalizer(); // The number of IDs generated by the local session private localGenCount = 0; /** * The sharding state of this compressor, if it has been sharded or is a shard itself. * When defined, this compressor operates in "sharding mode" where: * - IDs are generated using stride-based allocation (no eager finals) * - The normalizer backfills all IDs in each stride cycle * - Normal operation resumes when all children are disposed */ private shardingState?: | { /** * Current stride - used when this compressor has active children. * Changes each time shard() is called. */ currentStride: number; /** * Original stride - the stride this compressor was created with. * Used when this compressor has no children (is a leaf). * IMMUTABLE after creation. */ originalStride: number; /** * Set of unique child shard IDs (UUIDs) currently active. * Each child is assigned a UUID when created via shard(). * Safe across serialization/deserialization cycles. */ activeChildIds: Set; /** * This compressor's unique shard ID within its parent (if it's a child). * Undefined for root compressors. * Assigned by parent when creating this shard. */ shardId?: SessionId; } | undefined; // #endregion // #region Final state /** * The gen count to be annotated on the range returned by the next call to `takeNextCreationRange`. * This is advanced to `localGenCount` + 1 each time it is called. * On the other hand, when `resetUnfinalizedCreationRange` is called, * this is moved back to the start of the unfinalized range, to ensure those IDs are included in the next range. */ private nextRangeBaseGenCount = 1; private readonly sessions = new Sessions(); private readonly finalSpace = new FinalSpace(); // #endregion // #region Ephemeral state /** * Roughly equates to a minimum of 1M sessions before we start allocating 64 bit IDs. * Eventually, this can be adjusted dynamically to have cluster reservation policies that * optimize the number of eager finals. * It is not readonly as it is accessed by tests for clear-box testing. */ // eslint-disable-next-line @typescript-eslint/prefer-readonly private nextRequestedClusterSize: number = 512; // The number of local IDs generated since the last telemetry was sent. private telemetryLocalIdCount = 0; // The number of eager final IDs generated since the last telemetry was sent. private telemetryEagerFinalIdCount = 0; // The ongoing ghost session, if one exists. private ongoingGhostSession?: { cluster?: IdCluster; ghostSessionId: SessionId } | undefined; // #endregion public constructor( localSessionIdOrDeserialized: SessionId | Sessions, private readonly logger: TelemetryLoggerExt | undefined, /** * The version this compressor will write out. * This applies to both `serialize` and creation range functions. * This number also determines what features are available (e.g. sharding support starts at V3). */ private readonly writeVersion: SerializationVersion, ) { if (typeof localSessionIdOrDeserialized === "string") { this.localSessionId = localSessionIdOrDeserialized; this.localSession = this.sessions.getOrCreate(localSessionIdOrDeserialized); } else { // Deserialize case this.sessions = localSessionIdOrDeserialized; // As policy, the first session is always the local session. Preserve this invariant // during deserialization. const firstSession = localSessionIdOrDeserialized.sessions().next(); assert(!firstSession.done, 0x754 /* First session must be present. */); this.localSession = firstSession.value; this.localSessionId = stableIdFromNumericUuid( this.localSession.sessionUuid, ) as SessionId; } } public generateCompressedId(): SessionSpaceCompressedId { // This ghost session code inside this block should not be changed without a version bump (it is performed at a consensus point) if (this.ongoingGhostSession) { if (this.ongoingGhostSession.cluster === undefined) { this.ongoingGhostSession.cluster = this.addEmptyCluster( this.sessions.getOrCreate(this.ongoingGhostSession.ghostSessionId), 1, ); } else { this.ongoingGhostSession.cluster.capacity++; } this.ongoingGhostSession.cluster.count++; return lastFinalizedFinal( this.ongoingGhostSession.cluster, ) as unknown as SessionSpaceCompressedId; } // In sharding mode, always generate local IDs with stride-based allocation. // Eager finals are disabled because shards backfill IDs not in their stride cycle. // If another shard generated them as eager finals, ingesting IDs from another shard // would fail depending on timing. if (this.shardingState !== undefined) { this.telemetryLocalIdCount++; const { currentStride } = this.shardingState; this.normalizer.addLocalRange(this.localGenCount + 1, currentStride); this.localGenCount += currentStride; return localIdFromGenCount(this.localGenCount); } // Normal ID generation this.localGenCount++; const lastCluster = this.localSession.getLastCluster(); if (lastCluster === undefined) { this.telemetryLocalIdCount++; return this.generateNextLocalId(); } // If there exists a cluster of final IDs already claimed by the local session that still has room in it, // it is known prior to range sequencing what a local ID's corresponding final ID will be. // In this case, it is safe to return the final ID immediately. This is guaranteed to be safe because // any op that the local session sends that contains one of those final IDs are guaranteed to arrive to // collaborators *after* the one containing the creation range. const clusterOffset = this.localGenCount - genCountFromLocalId(lastCluster.baseLocalId); if (lastCluster.capacity > clusterOffset) { this.telemetryEagerFinalIdCount++; // Space in the cluster: eager final return ((lastCluster.baseFinalId as number) + clusterOffset) as SessionSpaceCompressedId; } // No space in the cluster, return next local this.telemetryLocalIdCount++; return this.generateNextLocalId(); } public generateDocumentUniqueId(): | (SessionSpaceCompressedId & OpSpaceCompressedId) | StableId { const id = this.generateCompressedId(); return isFinalId(id) ? id : this.decompress(id); } /** * Starts a ghost session. Only exposed for test purposes (this class is not exported from the package). * @param ghostSessionId - The session ID to start the ghost session with. */ public startGhostSession(ghostSessionId: SessionId): void { assert(!this.ongoingGhostSession, 0x8fe /* Ghost session already in progress. */); this.ongoingGhostSession = { ghostSessionId }; } public beginGhostSession(ghostSessionId: SessionId, ghostSessionCallback: () => void): void { if (this.shardingState) { throw new Error("Cannot start a ghost session while sharded."); } this.startGhostSession(ghostSessionId); try { ghostSessionCallback(); } finally { this.ongoingGhostSession = undefined; } } public shard(newShardCount: number): SerializedIdCompressorShard[] { if (!Number.isSafeInteger(newShardCount) || newShardCount <= 0) { throw new Error("Shard count must be a positive safe integer"); } if (this.ongoingGhostSession) { throw new Error("Cannot shard during ghost session"); } if (this.writeVersion < SerializationVersion.V3) { throw new Error( `Sharding requires document version ${SerializationVersion.V3} or higher, but this document is version ${this.writeVersion}`, ); } const currentStride = this.shardingState?.currentStride ?? 1; const newStride = currentStride * (newShardCount + 1); // ID usage is exponential in stride count. Limit to practical size to avoid overflow. if (newStride > MAX_STRIDE_LENGTH) { throw new Error("Sharding limit reached."); } assert(Number.isSafeInteger(newStride), 0xd52 /* Shard stride must be a safe integer */); if (this.shardingState === undefined) { // First time sharding - initialize state this.shardingState = { currentStride: newStride, originalStride: 1, activeChildIds: new Set(), }; } else { this.shardingState.currentStride = newStride; } // Cache to avoid repeating per child const serialized = this.serialize(true); const { localGenCount: parentGenCount } = this; const shards: SerializedIdCompressorShard[] = []; // Children are positioned at consecutive positions within the parents current stride cycle // e.g. if parent owns the "evens" space (-2, -4, -6, ...) and is sharded into 3 (two children) // while at -8, then the child shards will start at -10 and -12 with a stride of 6 for (let i = 1; i <= newShardCount; i++) { const childShardId = createSessionId(); this.shardingState.activeChildIds.add(childShardId); const childLocalGenCount = parentGenCount + i * currentStride; // This code results in a double roundtrip, but is probably plenty fast enough for scenarios that need sharding, // as they necessarily have process boundaries to deal with. // If this ever became an issue we can implement a fast clone of compressors const child = deserializeIdCompressor(serialized, this.writeVersion) as IdCompressor; const genCountJump = childLocalGenCount - parentGenCount; assert( child.localGenCount === parentGenCount && genCountJump > 0, 0xd53 /* Child offsets incorrectly calculated. */, ); child.normalizer.addLocalRange(child.localGenCount + 1, genCountJump); child.localGenCount = childLocalGenCount; child.shardingState = { currentStride: newStride, originalStride: newStride, activeChildIds: new Set(), shardId: childShardId, }; shards.push({ serialized: child.serialize(true), syncToken: child.makeShardToken(false), }); } return shards; } public synchronizeWithShard(syncToken: ShardSynchronizationToken): void { const isNowLeaf = this.synchronizeChild(syncToken); // A disposal token additionally reclaims the child's ID space. If reclaiming the last child // returns this compressor to a leaf and it is the root (originalStride === 1), exit sharding mode. if (syncToken.disposed) { assert(this.shardingState !== undefined, 0xd54 /* Must be sharded */); if (isNowLeaf && this.shardingState.originalStride === 1) { this.shardingState = undefined; } } } public getChildShardSyncToken( childToken: ShardSynchronizationToken, ): ParentShardSynchronizationToken { if (!this.shardingState?.activeChildIds.has(childToken.shardId)) { throw new Error("Cannot get a synchronization token for an inactive child shard."); } const token: ParentShardSynchronizationToken = { type: "parentIdSpaceShardSyncToken", shardId: childToken.shardId, localGenCount: this.localGenCount, }; return token; } public synchronizeWithParent(token: ParentShardSynchronizationToken): void { const state = this.shardingState; if ( token.type !== "parentIdSpaceShardSyncToken" || state?.shardId === undefined || state.shardId !== token.shardId ) { throw new Error("Invalid parent synchronization token for this child shard."); } validateShardGenerationCount(token.localGenCount); if (token.localGenCount <= this.localGenCount) { // A child can already be ahead through its own allocations. Its local range // then includes the parent's IDs through this generation count. return; } this.backfillToNextStridePosition(token.localGenCount, state.currentStride); } /** * Adds IDs through the next position in this shard's stride after the given generation count. */ private backfillToNextStridePosition(targetGenCount: number, stride: number): void { if (targetGenCount <= this.localGenCount) { return; } const count = Math.ceil((targetGenCount - this.localGenCount + 1) / stride) * stride; const nextGenCount = this.localGenCount + count; if (!Number.isSafeInteger(nextGenCount)) { throw new TypeError("Shard progress exceeds the supported ID space."); } this.normalizer.addLocalRange(this.localGenCount + 1, count); this.localGenCount = nextGenCount; } private synchronizeChild(syncToken: ShardToken): boolean { const childDisposed = syncToken.disposed; if (this.writeVersion < SerializationVersion.V3) { throw new Error( `Sharding requires document version ${SerializationVersion.V3} or higher, but this document is version ${this.writeVersion}`, ); } if (this.shardingState === undefined) { throw new Error("Must be in sharding mode."); } const childShardId = syncToken.shardId; const { activeChildIds, originalStride } = this.shardingState; // Verify this child belongs to us if (!activeChildIds.has(childShardId)) { throw new Error( `Cannot synchronize with child with ID ${childShardId}: not in active children set`, ); } validateShardGenerationCount(syncToken.localGenCount); // A last-child disposal realigns on the original stride. Backfill before changing // membership so invalid progress cannot accidentally reclaim the child. const isLeaf = childDisposed && activeChildIds.size === 1; this.backfillToNextStridePosition( syncToken.localGenCount, isLeaf ? originalStride : this.shardingState.currentStride, ); // A plain synchronization leaves the child active so it can keep generating IDs. if (childDisposed) { activeChildIds.delete(childShardId); if (isLeaf) { this.shardingState.currentStride = originalStride; } } return isLeaf; } public disposeShard(): ShardSynchronizationToken | undefined { if (this.shardingState === undefined) { return undefined; } else { if (this.shardingState.activeChildIds.size > 0) { throw new Error("Cannot dispose a shard with active children."); } } // A disposal token is a sync token that additionally signals reclamation of this shard's ID space. const token = this.makeShardToken(true); // Make this compressor unusable by replacing all methods with throwing stubs // This is a one-time mutation that avoids runtime checks in every method makeCompressorUnusable(this); return token; } public getShardSyncToken(): ShardSynchronizationToken | undefined { if (this.shardingState === undefined) { return undefined; } return this.makeShardToken(false); } /** * Builds a token describing this shard's current progress. * @param disposed - Whether the token also signals disposal (reclamation of this shard's ID space). */ private makeShardToken(disposed: boolean): ShardSynchronizationToken { assert(this.shardingState !== undefined, 0xd55 /* Compressor is not sharded. */); // Root cannot produce a token (shardId is undefined for root) if (this.shardingState.shardId === undefined) { throw new Error( "Cannot get a token for a root compressor - only shards can be disposed", ); } const token: ShardToken = { localGenCount: this.localGenCount, shardId: this.shardingState.shardId, disposed, }; return token as unknown as ShardSynchronizationToken; } private generateNextLocalId(): LocalCompressedId { // Must tell the normalizer that we generated a local ID this.normalizer.addLocalRange(this.localGenCount, 1); return localIdFromGenCount(this.localGenCount); } public takeNextCreationRange(): IdCreationRange { // Child (non-root) shards must not submit their own creation ranges. All shards in a shard tree share a // single session, and only the root shard is responsible for finalizing that session's IDs with the server. // A child's generated IDs are reconciled with the root via shard synchronization tokens (see // synchronizeWithShard / disposeShard), not by independently sending ranges, which would overlap and // conflict with the root's ranges for the shared session. if (this.shardingState?.shardId !== undefined) { throw new Error("Cannot take a creation range from a non-root shard."); } assert( !this.ongoingGhostSession, 0x8a6 /* IdCompressor should not be operated normally when in a ghost session */, ); const count = this.localGenCount - (this.nextRangeBaseGenCount - 1); if (count === 0) { return { sessionId: this.localSessionId, }; } const range: IdCreationRange = { sessionId: this.localSessionId, ids: { firstGenCount: this.nextRangeBaseGenCount, count, requestedClusterSize: this.nextRequestedClusterSize, localIdRanges: this.normalizer.getRangesBetween( this.nextRangeBaseGenCount, this.localGenCount, ), }, }; return this.updateToRange(range); } public takeUnfinalizedCreationRange(): IdCreationRange { this.resetUnfinalizedCreationRange(); return this.takeNextCreationRange(); } public resetUnfinalizedCreationRange(): void { assert( !this.ongoingGhostSession, 0xcec /* IdCompressor should not be operated normally when in a ghost session */, ); const lastLocalCluster = this.localSession.getLastCluster(); this.nextRangeBaseGenCount = lastLocalCluster === undefined ? 1 : genCountFromLocalId( (lastLocalCluster.baseLocalId - lastLocalCluster.count) as LocalCompressedId, ); } private updateToRange(range: IdCreationRange): IdCreationRange { this.nextRangeBaseGenCount = this.localGenCount + 1; return IdCompressor.assertValidRange(range); } private static assertValidRange(range: IdCreationRange): IdCreationRange { if (range.ids === undefined) { return range; } const { count, requestedClusterSize } = range.ids; assert(count > 0, 0x755 /* Malformed ID Range. */); assert(requestedClusterSize > 0, 0x876 /* Clusters must have a positive capacity. */); assert( requestedClusterSize <= IdCompressor.maxClusterSize, 0x877 /* Clusters must not exceed max cluster size. */, ); return range; } public finalizeCreationRange(range: IdCreationRange): void { assert( !this.ongoingGhostSession, 0x8a7 /* IdCompressor should not be operated normally when in a ghost session */, ); // Check if the range has IDs if (range.ids === undefined) { return; } IdCompressor.assertValidRange(range); const { sessionId, ids } = range; const { count, firstGenCount, requestedClusterSize } = ids; const session = this.sessions.getOrCreate(sessionId); const isLocal = session === this.localSession; const rangeBaseLocal = localIdFromGenCount(firstGenCount); let lastCluster = session.getLastCluster(); if (lastCluster === undefined) { // This is the first cluster in the session space if (rangeBaseLocal !== -1) { throw rangeFinalizationError(-1, rangeBaseLocal); } lastCluster = this.addEmptyCluster(session, requestedClusterSize + count); if (isLocal) { this.logger?.sendTelemetryEvent({ eventName: "RuntimeIdCompressor:FirstCluster", sessionId: this.localSessionId, }); } } const remainingCapacity = lastCluster.capacity - lastCluster.count; if (lastCluster.baseLocalId - lastCluster.count !== rangeBaseLocal) { throw rangeFinalizationError( lastCluster.baseLocalId - lastCluster.count, rangeBaseLocal, ); } if (remainingCapacity >= count) { // The current range fits in the existing cluster lastCluster.count += count; } else { const overflow = count - remainingCapacity; const newClaimedFinalCount = overflow + requestedClusterSize; if (lastCluster === this.finalSpace.getLastCluster()) { // The last cluster in the sessions chain is the last cluster globally, so it can be expanded. lastCluster.capacity += newClaimedFinalCount; lastCluster.count += count; assert( !this.sessions.clusterCollides(lastCluster), 0x756 /* Cluster collision detected. */, ); if (isLocal) { this.logger?.sendTelemetryEvent({ eventName: "RuntimeIdCompressor:ClusterExpansion", sessionId: this.localSessionId, previousCapacity: lastCluster.capacity - newClaimedFinalCount, newCapacity: lastCluster.capacity, overflow, }); } } else { // The last cluster in the sessions chain is *not* the last cluster globally. Fill and overflow to new. lastCluster.count = lastCluster.capacity; const newCluster = this.addEmptyCluster(session, newClaimedFinalCount); newCluster.count += overflow; if (isLocal) { this.logger?.sendTelemetryEvent({ eventName: "RuntimeIdCompressor:NewCluster", sessionId: this.localSessionId, }); } } } if (isLocal) { this.logger?.sendTelemetryEvent({ eventName: "RuntimeIdCompressor:IdCompressorStatus", eagerFinalIdCount: this.telemetryEagerFinalIdCount, localIdCount: this.telemetryLocalIdCount, sessionId: this.localSessionId, }); this.telemetryEagerFinalIdCount = 0; this.telemetryLocalIdCount = 0; } assert(!session.isEmpty(), 0x757 /* Empty sessions should not be created. */); this.eventEmitter.emit("rangeFinalized", range); } private addEmptyCluster(session: Session, capacity: number): IdCluster { assert( !this.ongoingGhostSession?.cluster, 0x8a8 /* IdCompressor should not be operated normally when in a ghost session */, ); const newCluster = session.addNewCluster( this.finalSpace.getAllocatedIdLimit(), capacity, 0, ); assert( !this.sessions.clusterCollides(newCluster), 0x758 /* Cluster collision detected. */, ); this.finalSpace.addCluster(newCluster); return newCluster; } public normalizeToOpSpace(id: SessionSpaceCompressedId): OpSpaceCompressedId { if (isFinalId(id)) { return id; } else { const local = id as unknown as LocalCompressedId; if (!this.normalizer.contains(local)) { throw new Error("Invalid ID to normalize."); } const finalForm = this.localSession.tryConvertToFinal(local, true); return finalForm === undefined ? (local as unknown as OpSpaceCompressedId) : (finalForm as OpSpaceCompressedId); } } public tryNormalizeToSessionSpaceWithoutSession( id: OpSpaceCompressedId, ): SessionSpaceCompressedId | undefined { if (isFinalId(id)) { const containingCluster = this.localSession.getClusterByAllocatedFinal(id); if (containingCluster === undefined) { // Does not exist in local cluster chain if (id >= this.finalSpace.getFinalizedIdLimit()) { throw new Error("Unknown op space ID."); } return id as unknown as SessionSpaceCompressedId; } else { const alignedLocal = getAlignedLocal(containingCluster, id); if (this.normalizer.contains(alignedLocal)) { return alignedLocal; } else { if (genCountFromLocalId(alignedLocal) > this.localGenCount) { // The ID is not valid in this compressor. It is either from a future version of this compressor, or another compressor. // Since IDs from other compressors often are valid in this one, but uncompress incorrectly, // we cannot rely on this function (tryNormalizeToSessionSpaceWithoutSession) to validate that the IDs are from the same compressor. // Since such validation can not be robust, this "try" function is explicitly documented not to be allowed to be used for this case. // Therefore, as documented in the API docs for this function, calls can not rely on a specific output in this case, // and therefore the document behavior of throwing makes the most sense (helps catch bugs). throw new Error("Unknown op space ID."); } return id as unknown as SessionSpaceCompressedId; } } } else { return undefined; } } public normalizeToSessionSpace( id: OpSpaceCompressedId, originSessionId: SessionId, ): SessionSpaceCompressedId { const normalizedWithoutSession = this.tryNormalizeToSessionSpaceWithoutSession(id); if (normalizedWithoutSession === undefined) { const localToNormalize = id as unknown as LocalCompressedId; if (originSessionId === this.localSessionId) { if (this.normalizer.contains(localToNormalize)) { return localToNormalize; } else { // We never generated this local ID, so fail throw new Error("Unknown op space ID."); } } else { // LocalId from a remote session const remoteSession = this.sessions.get(originSessionId); if (remoteSession === undefined) { throw new Error("No IDs have ever been finalized by the supplied session."); } const correspondingFinal = remoteSession.tryConvertToFinal(localToNormalize, false); if (correspondingFinal === undefined) { throw new Error("Unknown op space ID."); } return correspondingFinal as unknown as SessionSpaceCompressedId; } } else { return normalizedWithoutSession; } } public decompress(id: SessionSpaceCompressedId): StableId { if (isFinalId(id)) { const containingCluster = Session.getContainingCluster(id, this.finalSpace.clusters); if (containingCluster === undefined) { throw new Error("Unknown ID"); } const alignedLocal = getAlignedLocal(containingCluster, id); const alignedGenCount = genCountFromLocalId(alignedLocal); const lastFinalizedGenCount = genCountFromLocalId(lastFinalizedLocal(containingCluster)); if (alignedGenCount > lastFinalizedGenCount) { // should be an eager final id generated by the local session if (containingCluster.session === this.localSession) { assert(!this.normalizer.contains(alignedLocal), 0x759 /* Normalizer out of sync. */); } else { throw new Error("Unknown ID"); } } return stableIdFromNumericUuid( offsetNumericUuid(containingCluster.session.sessionUuid, alignedGenCount - 1), ); } else { const localToDecompress = id as unknown as LocalCompressedId; if (!this.normalizer.contains(localToDecompress)) { throw new Error("Unknown ID"); } return stableIdFromNumericUuid( offsetNumericUuid( this.localSession.sessionUuid, genCountFromLocalId(localToDecompress) - 1, ), ); } } public recompress(uncompressed: StableId): SessionSpaceCompressedId { const recompressed = this.tryRecompress(uncompressed); if (recompressed === undefined) { throw new Error("Could not recompress."); } return recompressed; } public tryRecompress(uncompressed: StableId): SessionSpaceCompressedId | undefined { const match = this.sessions.getContainingCluster(uncompressed); if (match === undefined) { const numericUncompressed = numericUuidFromStableId(uncompressed); const offset = subtractNumericUuids(numericUncompressed, this.localSession.sessionUuid); if (offset < Number.MAX_SAFE_INTEGER) { const genCountEquivalent = Number(offset) + 1; const localEquivalent = localIdFromGenCount(genCountEquivalent); if (this.normalizer.contains(localEquivalent)) { return localEquivalent; } } return undefined; } else { const [containingCluster, alignedLocal] = match; if (containingCluster.session === this.localSession) { // Local session if (this.normalizer.contains(alignedLocal)) { return alignedLocal; } else { assert( genCountFromLocalId(alignedLocal) <= this.localGenCount, 0x75a /* Clusters out of sync. */, ); // Id is an eager final return getAlignedFinal(containingCluster, alignedLocal) as | SessionSpaceCompressedId | undefined; } } else { // Not the local session return genCountFromLocalId(alignedLocal) >= lastFinalizedLocal(containingCluster) ? (getAlignedFinal(containingCluster, alignedLocal) as | SessionSpaceCompressedId | undefined) : undefined; } } } public serialize(withSession: true): SerializedIdCompressorWithOngoingSession; public serialize(withSession: false): SerializedIdCompressorWithNoSession; public serialize(hasLocalState: boolean): SerializedIdCompressor { assert( !this.ongoingGhostSession, 0x8a9 /* IdCompressor should not be operated normally when in a ghost session */, ); const { normalizer, finalSpace, sessions, localGenCount, logger, nextRangeBaseGenCount } = this; const sessionIndexMap = new Map(); let sessionIndex = 0; for (const session of sessions.sessions()) { // Filter empty sessions to prevent them accumulating in the serialized state if (!session.isEmpty() || hasLocalState) { sessionIndexMap.set(session, sessionIndex); sessionIndex++; } } const sizeOfUuid = 2; const shardingStateSize = hasLocalState && this.writeVersion >= SerializationVersion.V3 ? this.shardingState === undefined ? 1 // Boolean: no sharding state : 1 + // Boolean: has sharding state 2 + // Numbers: currentStride, originalStride (Float64) 1 + // Number: activeChildIds count (Float64) this.shardingState.activeChildIds.size * sizeOfUuid + // UUIDs: each is 128-bit 1 + // Boolean: hasShardId (this.shardingState.shardId === undefined ? 0 : sizeOfUuid) // UUID: 128-bit if present : 0; const localStateSize = hasLocalState ? 1 + // generated ID count 1 + // next range base genCount 1 + // count of normalizer pairs normalizer.idRanges.size * 2 + // pairs shardingStateSize // sharding state if present : 0; // Layout size, in 8 byte increments const totalSize = 1 + // version 1 + // hasLocalState 1 + // session count 1 + // cluster count sessionIndexMap.size * sizeOfUuid + // session IDs finalSpace.clusters.length * 3 + // clusters: (sessionIndex, capacity, count)[] localStateSize; // local state, if present const serializedFloat = new Float64Array(totalSize); const serializedUint = new BigUint64Array(serializedFloat.buffer); let index = 0; index = writeNumber(serializedFloat, index, this.writeVersion); index = writeBoolean(serializedFloat, index, hasLocalState); index = writeNumber(serializedFloat, index, sessionIndexMap.size); index = writeNumber(serializedFloat, index, finalSpace.clusters.length); for (const [session] of sessionIndexMap.entries()) { index = writeNumericUuid(serializedUint, index, session.sessionUuid); } for (const cluster of finalSpace.clusters) { index = writeNumber( serializedFloat, index, sessionIndexMap.get(cluster.session) as number, ); index = writeNumber(serializedFloat, index, cluster.capacity); index = writeNumber(serializedFloat, index, cluster.count); } if (hasLocalState) { index = writeNumber(serializedFloat, index, localGenCount); index = writeNumber(serializedFloat, index, nextRangeBaseGenCount); index = writeNumber(serializedFloat, index, normalizer.idRanges.size); for (const [leadingGenCount, count] of normalizer.idRanges.entries()) { index = writeNumber(serializedFloat, index, leadingGenCount); index = writeNumber(serializedFloat, index, count); } // Write sharding state (version 3+) if (this.writeVersion >= SerializationVersion.V3) { index = writeBoolean(serializedFloat, index, this.shardingState !== undefined); if (this.shardingState !== undefined) { index = writeNumber(serializedFloat, index, this.shardingState.currentStride); index = writeNumber(serializedFloat, index, this.shardingState.originalStride); // Write activeChildIds Set as count + array of NumericUuids index = writeNumber(serializedFloat, index, this.shardingState.activeChildIds.size); for (const childId of this.shardingState.activeChildIds) { index = writeNumericUuid(serializedUint, index, numericUuidFromStableId(childId)); } // Write shardId (optional) index = writeBoolean( serializedFloat, index, this.shardingState.shardId !== undefined, ); if (this.shardingState.shardId !== undefined) { index = writeNumericUuid( serializedUint, index, numericUuidFromStableId(this.shardingState.shardId), ); } } } } assert(index === totalSize, 0x75b /* Serialized size was incorrectly calculated. */); logger?.sendTelemetryEvent({ eventName: "RuntimeIdCompressor:SerializedIdCompressorSize", size: serializedFloat.byteLength, clusterCount: finalSpace.clusters.length, sessionCount: sessionIndexMap.size, }); return bufferToString(serializedFloat.buffer, "base64") as SerializedIdCompressor; } public static deserialize( params: | { serialized: SerializedIdCompressorWithOngoingSession; requestedWriteVersion: SerializationVersion; logger?: TelemetryLoggerExt | undefined; newSessionId?: never; } | { serialized: SerializedIdCompressorWithNoSession; newSessionId: SessionId; requestedWriteVersion: SerializationVersion; logger?: TelemetryLoggerExt | undefined; }, ): IdCompressor { const { serialized, newSessionId: sessionId, logger, requestedWriteVersion } = params; const buffer = stringToBuffer(serialized, "base64"); const index: Index = { index: 0, bufferFloat: new Float64Array(buffer), bufferUint: new BigUint64Array(buffer), }; const serializedVersion = readNumber(index) as SerializationVersion; // If requested version is < the serialized version, we must write the version serialized // to avoid losing data. const writeVersion = Math.max( requestedWriteVersion, serializedVersion, ) as SerializationVersion; switch (serializedVersion) { case 2: case 3: { break; } default: { if (serializedVersion === 1) { throw new Error("IdCompressor version 1.0 is no longer supported."); } throw new Error("Unknown IdCompressor serialized version."); } } const hasLocalState = readBoolean(index); const sessionCount = readNumber(index); const clusterCount = readNumber(index); // Sessions let sessionOffset = 0; const sessions: [NumericUuid, Session][] = []; if (hasLocalState) { assert( sessionId === undefined, 0x75e /* Local state should not exist in serialized form. */, ); } else { // If !hasLocalState, there won't be a serialized local session ID so insert one at the beginning assert(sessionId !== undefined, 0x75d /* Local session ID is undefined. */); const localSessionNumeric = numericUuidFromStableId(sessionId); sessions.push([localSessionNumeric, new Session(localSessionNumeric)]); sessionOffset = 1; } for (let i = 0; i < sessionCount; i++) { const numeric = readNumericUuid(index); sessions.push([numeric, new Session(numeric)]); } const compressor = new IdCompressor(new Sessions(sessions), logger, writeVersion); // Clusters let baseFinalId = 0; for (let i = 0; i < clusterCount; i++) { const sessionIndex = readNumber(index); const sessionArray = sessions[sessionIndex + sessionOffset]; assert( sessionArray !== undefined, 0x9d8 /* sessionArray is undefined in IdCompressor.deserialize2_0 */, ); const session = sessionArray[1]; const capacity = readNumber(index); const count = readNumber(index); const cluster = session.addNewCluster(baseFinalId as FinalCompressedId, capacity, count); compressor.finalSpace.addCluster(cluster); baseFinalId += capacity; } // Local state if (hasLocalState) { compressor.localGenCount = readNumber(index); compressor.nextRangeBaseGenCount = readNumber(index); const normalizerCount = readNumber(index); for (let i = 0; i < normalizerCount; i++) { compressor.normalizer.addLocalRange(readNumber(index), readNumber(index)); } // Sharding state (version 3+) if (serializedVersion >= 3) { const hasShardingState = readBoolean(index); if (hasShardingState) { const currentStride = readNumber(index); const originalStride = readNumber(index); // Read activeChildIds Set const activeChildCount = readNumber(index); const activeChildIds = new Set(); for (let i = 0; i < activeChildCount; i++) { const childIdNumeric = readNumericUuid(index); // Safe cast: these were serialized as SessionIds activeChildIds.add(stableIdFromNumericUuid(childIdNumeric) as SessionId); } // Read shardId (optional) const hasShardId = readBoolean(index); const shardId: SessionId | undefined = hasShardId ? (stableIdFromNumericUuid(readNumericUuid(index)) as SessionId) : undefined; // Build sharding state object, conditionally including shardId compressor.shardingState = { currentStride, originalStride, activeChildIds, ...(shardId !== undefined && { shardId }), }; } } } assert( index.index === index.bufferFloat.length, 0x75f /* Failed to read entire serialized compressor. */, ); return compressor; } public equals(other: IdCompressor, includeLocalState: boolean): boolean { if ( includeLocalState && (this.localSessionId !== other.localSessionId || !this.localSession.equals(other.localSession) || !this.normalizer.equals(other.normalizer) || this.nextRangeBaseGenCount !== other.nextRangeBaseGenCount || this.localGenCount !== other.localGenCount) ) { return false; } // Shard ownership affects future local ID allocation, even when the generated IDs match. // It is not part of finalized state, so ignore it when comparing only that state. if (includeLocalState) { const state = this.shardingState; const otherState = other.shardingState; if (state === undefined || otherState === undefined) { // Two unsharded compressors match here; a sharded and an unsharded compressor do not. if (state !== otherState) { return false; } } else { if ( state.currentStride !== otherState.currentStride || state.originalStride !== otherState.originalStride || state.shardId !== otherState.shardId || state.activeChildIds.size !== otherState.activeChildIds.size ) { return false; } // Child ownership is an unordered set. Equal sizes and membership imply equal sets, // regardless of insertion order or whether the state was deserialized. for (const childId of state.activeChildIds) { if (!otherState.activeChildIds.has(childId)) { return false; } } } } return ( this.sessions.equals(other.sessions, includeLocalState) && this.finalSpace.equals(other.finalSpace) ); } } /** * Create a new {@link IIdCompressor}. * @param writeVersion - The version the compressor will write when serializing. Use SerializationVersion.V2 for base format, or SerializationVersion.V3 for sharding support. * @param logger - Optional telemetry logger. * @internal */ export function createIdCompressor( writeVersion: SerializationVersion, logger?: ITelemetryBaseLogger, ): IIdCompressor & IIdCompressorCore; /** * Create a new {@link IIdCompressor}. * @param sessionId - The seed ID for the compressor. * @param writeVersion - The version the compressor will write when serializing. Use SerializationVersion.V2 for base format, or SerializationVersion.V3 for sharding support. * @param logger - Optional telemetry logger. * @internal */ export function createIdCompressor( sessionId: SessionId, writeVersion: SerializationVersion, logger?: ITelemetryBaseLogger, ): IIdCompressor & IIdCompressorCore; export function createIdCompressor( sessionIdOrDocumentVersion: SessionId | SerializationVersion, writeVersionOrLogger?: SerializationVersion | ITelemetryBaseLogger, loggerOrUndefined?: ITelemetryBaseLogger, ): IIdCompressor & IIdCompressorCore { let localSessionId: SessionId; let writeVersion: SerializationVersion; let logger: ITelemetryBaseLogger | undefined; if (typeof sessionIdOrDocumentVersion === "string") { // Called with sessionId, writeVersion, logger? localSessionId = sessionIdOrDocumentVersion; writeVersion = writeVersionOrLogger as SerializationVersion; logger = loggerOrUndefined; } else { // Called with writeVersion, logger? localSessionId = createSessionId(); writeVersion = sessionIdOrDocumentVersion; logger = writeVersionOrLogger as ITelemetryBaseLogger | undefined; } const compressor = new IdCompressor( localSessionId, logger === undefined ? undefined : createChildLogger({ logger }), writeVersion, ); return compressor; } /** * Deserializes the supplied state into an ID compressor. * @param serialized - The serialized compressor state with an ongoing session. * @param writeVersion - The version the compressor will write when serializing. This determines what features are available (e.g., V3 enables sharding support). * @param logger - Optional telemetry logger. * @internal */ export function deserializeIdCompressor( serialized: SerializedIdCompressorWithOngoingSession, writeVersion: SerializationVersion, logger?: ITelemetryLoggerExt, ): IIdCompressor & IIdCompressorCore; /** * Deserializes the supplied state into an ID compressor. * @param serialized - The serialized compressor state without a session. * @param newSessionId - The session ID to use for the deserialized compressor. * @param writeVersion - The version the compressor will write when serializing. This determines what features are available (e.g., V3 enables sharding support). * @param logger - Optional telemetry logger. * @internal */ export function deserializeIdCompressor( serialized: SerializedIdCompressorWithNoSession, newSessionId: SessionId, writeVersion: SerializationVersion, logger?: ITelemetryLoggerExt, ): IIdCompressor & IIdCompressorCore; export function deserializeIdCompressor( serialized: SerializedIdCompressor | SerializedIdCompressorWithNoSession, sessionIdOrDocumentVersion: SessionId | SerializationVersion, writeVersionOrLogger?: SerializationVersion | ITelemetryLoggerExt, loggerOrUndefined?: ITelemetryLoggerExt, ): IIdCompressor & IIdCompressorCore { if (typeof sessionIdOrDocumentVersion === "string") { // Called with (serialized, sessionId, writeVersion, logger?) return IdCompressor.deserialize({ serialized: serialized as SerializedIdCompressorWithNoSession, logger: extractTelemetryLoggerExt<{ PossiblyUndefined: true }>(loggerOrUndefined), newSessionId: sessionIdOrDocumentVersion, requestedWriteVersion: writeVersionOrLogger as SerializationVersion, }); } assert( loggerOrUndefined === undefined, 0xc2d /* logger would be in sessionIdOrLogger in this codepath */, ); // Called with (serialized, writeVersion, logger?) return IdCompressor.deserialize({ serialized: serialized as SerializedIdCompressorWithOngoingSession, logger: extractTelemetryLoggerExt<{ PossiblyUndefined: true }>( writeVersionOrLogger as ITelemetryLoggerExt | undefined, ), requestedWriteVersion: sessionIdOrDocumentVersion, }); } /** * Throws an error indicating the compressor has been disposed. */ const throwDisposed = (): never => { throw new Error( "This compressor has been disposed via disposeShard() and can no longer be used.", ); }; /** * Makes an IdCompressor instance unusable by replacing all its methods with functions that throw. * This is called once when disposeShard() is invoked to make the compressor permanently unusable. * @param compressor - The compressor instance to make unusable */ function makeCompressorUnusable(compressor: IdCompressor): void { // Get all method names from the prototype (where class methods live) const proto = Object.getPrototypeOf(compressor) as object; for (const key of Reflect.ownKeys(proto)) { if (key !== "constructor" && typeof Reflect.get(proto, key) === "function") { // Shadow the method only on this instance so other compressors remain usable. // Omitting `enumerable` keeps new overrides non-enumerable, like class methods. // Reflection supports string and symbol keys without adding an index signature. Object.defineProperty(compressor, key, { value: throwDisposed, configurable: true, writable: true, }); } } } /** * Serializes an ID compressor. * @param compressor - The compressor to serialize. * @param withSession - If true, the serialized state will include local session * state (for stashing). If false, only finalized state is included (for summaries). * @internal */ export function serializeIdCompressor( compressor: IIdCompressor, withSession: true, ): SerializedIdCompressorWithOngoingSession; /** * Serializes an ID compressor. * @param compressor - The compressor to serialize. * @param withSession - If true, the serialized state will include local session * state (for stashing). If false, only finalized state is included (for summaries). * @internal */ export function serializeIdCompressor( compressor: IIdCompressor, withSession: false, ): SerializedIdCompressorWithNoSession; export function serializeIdCompressor( compressor: IIdCompressor, withSession: boolean, ): SerializedIdCompressorWithOngoingSession | SerializedIdCompressorWithNoSession { const core = toIdCompressorWithCore(compressor); return withSession ? core.serialize(true) : core.serialize(false); } /** * Casts an {@link IIdCompressor} to include {@link IIdCompressorCore}. * * @remarks * Compressors returned by `createIdCompressor` and `deserializeIdCompressor` * always implement both {@link IIdCompressor} and {@link IIdCompressorCore}, but their * public return type is narrowed to {@link IIdCompressor}. Internal consumers that * need access to core compressor operations (serialization, range management, etc.) * use this function to recover the {@link IIdCompressorCore} surface. * * @param compressor - A compressor created by `createIdCompressor` or * `deserializeIdCompressor`. * @returns The same compressor, typed to include {@link IIdCompressorCore}. * @internal */ export function toIdCompressorWithCore( compressor: IIdCompressor, ): IIdCompressor & IIdCompressorCore { assert( "serialize" in compressor, 0xced /* Expected compressor to implement IIdCompressorCore */, ); return compressor as IIdCompressor & IIdCompressorCore; }