tka: avoid quadratic filesystem scans - #20736
Open
terrorobe wants to merge 2 commits into
Open
Conversation
bradfitz
reviewed
Aug 5, 2026
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
force-pushed
the
terrorobe/tka-fs-index
branch
from
August 5, 2026 14:58
9806832 to
9eaabae
Compare
Author
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
marked this pull request as ready for review
August 5, 2026 15:02
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Since #17567,
FS.ChildAUMsderives 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 invokeChildAUMsrepeatedly during graph traversal, making filesystem work quadratic in the number of AUMs.Instrumenting
Openwith 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. BecauseOpenruns whileLocalBackend.muis held, the delay stalled event subscribers and triggered the 45-secondRequestStatuswatchdog.This change builds an active-AUM hash index and a parent-to-child hash index in a single filesystem scan.
Heads,ChildAUMs, andAllAUMsuse 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
FSinstance. Mutations made through that instance—including commits, purges, andRemoveAll—invalidate them. Known callers and the related storage design assume one owner per node-local directory. If callers share a directory betweenFSinstances 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
FSstore. 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 freshFSover the existing records, so it includes index construction but does not reuse an index from an earlier iteration.Synthetic 825-AUM benchmark results:
On Linux/ext3, cumulative Go heap allocation per
Opendrops 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 benchmarkB/opandallocs/opvalues, 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