Add structural sharing to Onyx’s cache #86181
Description
Coming from https://expensify.slack.com/archives/C05LX9D6E07/p1774003187586689
Proposal: Add structural sharing to Onyx's cache
Background: Onyx stores all application state in a flat key-value cache (storageMap). Keys that share a common prefix (e.g., report_1, report_2, …, report_5000) form "collections". Many components subscribe to entire collections via useOnyx('report_'), which triggers the internal getCollectionData() method to assemble all members into a single object. Components can also subscribe to individual keys.
Today, getCollectionData() returns {...cachedCollection} — a defensive shallow copy — on every call. This is O(n) per call, where n is the number of collection members. useOnyx mitigates this with shallowEqual to avoid unnecessary re-renders, but shallowEqual itself is O(n) — it must iterate all collection members to confirm nothing changed. For a collection with 5,000 reports, every getSnapshot() call pays O(5,000) for the spread plus O(5,000) for the shallow comparison, even when nothing changed.
The same pattern repeats deeper in the pipeline. OnyxCache.merge() rebuilds the entire storageMap via spread (this.storageMap = {...fastMerge(this.storageMap, data)}) even when only one key changed — O(total_keys) per write. OnyxCache.hasValueChanged() runs deepEqual() on every write — O(depth × breadth) per check. OnyxUtils.keysChanged() scans all subscribers linearly and uses deepEqual() per member to decide which subscribers to notify.
Problem: When components are subscribed to many Onyx keys and heavy collections with hundreds or thousands of records, if any single key is updated, then the entire storageMap is rebuilt via spread, collections are re-assembled from scratch, and O(n) equality checks run across all subscribers — blocking the main thread for hundreds of milliseconds.
Solution: Introduce structural sharing across Onyx's cache, merge, and notification layers so that unchanged data keeps the same object reference, making the cost proportional to the change rather than the total store size.
For collections: replace the mutable collectionData (which returned {...spread} copies) with immutable (Object.freeze()'d) snapshots that are only rebuilt when a member actually changes. The snapshot is rebuilt once per write (O(members)), not once per subscriber. Every subscriber receives the same frozen reference. When nothing in a collection changed, the reference is identical to the previous one, so a simple === check is sufficient — replacing O(n) shallowEqual with O(1).
For writes: replace the full storageMap spread with per-key merges, and make fastMerge/removeNestedNullValues reference-stable so unchanged values keep the same reference.
For notifications: replace linear subscriber scans and deepEqual comparisons with indexed lookups and === reference checks.
Measured results
Sentry performance metrics (real user scenarios):
Ryan's account (5,000+ reports), Offline Mode, Web:
ManualAppStartup: 7,357 ms → 6,592 ms (-10.4%)ManualNavigateToInboxTab: 1,297 ms → 1,205 ms (-7.1%)ManualNavigateToReports: 965 ms → 787 ms (-18.4%)ManualOpenReport: 906 ms → 664 ms (-26.7%)
Heavy Co-Pilot account, Web:
ManualAppStartup: 7,891 ms → 7,027 ms (-11.0%)ManualNavigateToInboxTab: 1,617 ms → 1,533 ms (-5.2%)ManualNavigateToReports: 1,401 ms → 1,068 ms (-23.8%)ManualOpenReport: 1,252 ms → 993 ms (-20.7%)
Here's a suggested plan to split the implementation into five incremental PRs, each self-contained and independently reviewable:
PR 1: Centralized key utilities with bidirectional indexes
Key-related functions are currently scattered across OnyxUtils and OnyxCache, and collection key lookups require O(C) linear scans over all collection keys. This PR extracts them into a new OnyxKeys module with two pre-computed maps:
memberToCollectionKeyMap: member key → collection key (O(1) reverse lookup)collectionToMembersMap: collection key → Set of member keys (O(1) forward lookup)
Both maps are maintained incrementally as keys are added/removed from cache. The forward lookup is essential for PR 3's snapshot rebuild — it allows iterating only the members of the affected collection instead of scanning all keys. Pure refactor — no behavioral change.
PR 2: Reference-stable fastMerge and removeNestedNullValues
Make fastMerge() and removeNestedNullValues() reference-stable: when no properties actually change during a merge, return the original object reference instead of a new copy. Track hasChanged through the merge recursion and return the original target when false. This is what enables downstream === checks to detect no-ops.
PR 3: Frozen collection snapshots with lazy rebuild and per-key merge
Replace the mutable collectionData (which returned {...spread} copies) with collectionSnapshots — a Map of Object.freeze()'d snapshots. When a member key is written (via set(), merge(), or drop()), its parent collection is marked dirty in a dirtyCollections Set. The frozen snapshot is only rebuilt on the next read (getCollectionData()), not on every write.
rebuildCollectionSnapshot() iterates only the members of the affected collection (using the indexed forward lookup from PR 1), creates a new frozen object, and compares each member reference against the previous snapshot. If nothing actually changed, the old snapshot reference is reused — this is what makes useOnyx's === check work.
Additionally, replace the O(total_keys) storageMap spread in merge() with a per-key loop. Keys whose merged result is === to the existing value (enabled by PR 2) are skipped entirely.
PR 4: Reference equality in notification and subscription paths
Replace the O(total_subscribers) linear scan in keysChanged() with indexed lookups via onyxKeyToSubscriptionIDs. Replace deepEqual() comparisons with === reference checks — safe because frozen snapshots and reference-stable fastMerge guarantee stable references for unchanged values.
In useOnyx, replace the two-path equality check (shallowEqual for non-selector, === for selector) with pure === for all paths. Non-selector values have stable references from frozen snapshots; selector values already have stable references from the memoized selector's internal deepEqual.
PR 5: Batched multiSetWithRetry notifications
Group collection members by their parent collection key and call keysChanged() once per collection instead of keyChanged() per individual key. Non-collection keys still get individual notifications.