Skip to content

tka: avoid quadratic filesystem scans - #20736

Open
terrorobe wants to merge 2 commits into
tailscale:mainfrom
terrorobe:terrorobe/tka-fs-index
Open

tka: avoid quadratic filesystem scans#20736
terrorobe wants to merge 2 commits into
tailscale:mainfrom
terrorobe:terrorobe/tka-fs-index

Conversation

@terrorobe

Copy link
Copy Markdown

Since #17567, FS.ChildAUMs derives child relationships by scanning and decoding every active AUM file. This avoids reading child metadata from a soft-deleted parent. However, authority reconstruction and compaction invoke ChildAUMs repeatedly during graph traversal, making filesystem work quadratic in the number of AUMs.

Instrumenting Open with an 824-AUM production store recorded 826 full scans and 680,624 decoded entries. The operation took 118.5 seconds using Tailscale 1.98.9 on a managed macOS host with Microsoft Defender. Because Open runs while LocalBackend.mu is held, the delay stalled event subscribers and triggered the 45-second RequestStatus watchdog.

This change builds an active-AUM hash index and a parent-to-child hash index in a single filesystem scan. Heads, ChildAUMs, and AllAUMs use the indexes to avoid further full-store scans. AUM values returned to callers are still decoded from disk on demand, preserving the filesystem store's existing value-isolation behavior. The cache retains one hash entry and approximately one parent-to-child edge per active AUM; it does not retain decoded AUM contents.

The indexes belong to a single FS instance. Mutations made through that instance—including commits, purges, and RemoveAll—invalidate them. Known callers and the related storage design assume one owner per node-local directory. If callers share a directory between FS instances or modify it directly, graph changes are not reflected in an instance's indexes until they are invalidated or the instance is reopened. The filesystem remains the durable source of truth, and the disk format and compaction retention behavior remain unchanged.

The benchmark materializes a valid 825-AUM authority in an FS store. On the affected macOS host, the unpatched benchmark took 124.36 seconds. This is within 5% of the 118.5 seconds measured with the production AUM data. AUM generation and filesystem writes occur before the timer starts. Each timed iteration creates a fresh FS over the existing records, so it includes index construction but does not reuse an index from an earlier iteration.

Synthetic 825-AUM benchmark results:

Platform Before After Speedup
macOS arm64, APFS with Microsoft Defender 124.36 s 4.09 s 30×
Linux amd64, ext3 5.871 s 34.24 ms 171×
Linux amd64, tmpfs 5.468 s 18.46 ms 296×

On Linux/ext3, cumulative Go heap allocation per Open drops from 1.98 GB to 8.78 MB, and the number of heap allocations drops from 20.8 million to about 80,800. These are benchmark B/op and allocs/op values, not retained heap or bytes read from disk. The Linux results show the quadratic cost without Defender, while the affected-host process samples are consistent with Defender amplifying the filesystem overhead.

Tests cover rebuilding the indexes after a commit, invalidating them during RemoveAll, preserving them during an empty purge, concurrent initialization, and independent returned AUM values. The temporary-file test now exercises the initial scan, and the shared Chonk tests continue to exercise purge after index construction.

Fixes #20735

Related to #17566

Comment thread tka/tailchonk.go Outdated
@bradfitz
bradfitz requested a review from alexwlchan August 5, 2026 00:01
@bradfitz

bradfitz commented Aug 5, 2026

Copy link
Copy Markdown
Member

This is a draft PR. Is it waiting for something before it's not a draft?

Since tailscale#17567, FS.ChildAUMs scans and decodes every active AUM file.
Authority reconstruction and compaction call it repeatedly, making
filesystem work quadratic in the number of AUMs.

Build per-FS indexes of active AUM hashes and parent-to-child
relationships in one scan. Use the indexes for graph queries while
continuing to decode returned AUM values from disk. Invalidate the
indexes after mutations, but retain them for empty purges.

An 825-AUM benchmark improves from 124 seconds to 4 seconds on macOS
with Defender and from 5.9 seconds to 34 milliseconds on Linux ext3.

RELNOTE: Avoid Tailnet Lock startup failures with large authority histories.

Fixes tailscale#20735

Change-Id: I088136bc2e9d1b6bfdecb223c069d42400c9f63d
Signed-off-by: Michael Renner <[email protected]>
Change-Id: I540018f9b31c41e11cfb8273137dc5bf6ac7bf91
@terrorobe
terrorobe force-pushed the terrorobe/tka-fs-index branch from 9806832 to 9eaabae Compare August 5, 2026 14:58
@terrorobe

Copy link
Copy Markdown
Author

This is a draft PR. Is it waiting for something before it's not a draft?

Mainly if the suggested caching behavior and changes in contract are ok for potential out of tree users of the code.

If there are no concerns on your end we can move ahead.

@terrorobe
terrorobe marked this pull request as ready for review August 5, 2026 15:02
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

tka: filesystem authority reconstruction is quadratic in AUM count

2 participants