{"thread":{"id":"66189","subject":"[RFC] check_connected: toward incoming-proportional cost","startedAt":"2026-08-18T12:31:23Z","lastAt":"2026-08-18T12:31:23Z","messageCount":1,"participants":["Kristofer Karlsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"550746","messageId":"CAL71e4Nf=-zCrfN7ghEVGq11irajJhtdxYZgKe0Ycux0qs1ZvQ@mail.gmail.com","threadId":"66189","inReplyTo":null,"subject":"[RFC] check_connected: toward incoming-proportional cost","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-08-18T12:31:09Z","receivedAt":"2026-08-18T12:31:23Z","isPatch":false,"body":"Hi!\n\nThe connectivity check (check_connected()) used by both fetch\nand receive-pack (and a few other call sites) can be expensive\nfor repositories with many refs or large active trees, and I\nthink that is worth optimizing.  I have a couple of ideas for\nhow to approach that, but before I start sending patches I\nwant to discuss the high-level need and align on the direction.\n\nThis follows up on Patrick Steinhardt's 2021 series [1], which\nexplored a faster connectivity check.  I found that thread\nafter independently trying a similar approach (and the thread\nwas helpful for making me pivot away from it).\n\nMy key takeaway from that discussion was that making the\ncheck faster would be useful, but we need to preserve the\nconnectivity invariant, and I think I found a way to\nachieve that.\n\nA few definitions I will use throughout:\n\n  Trusted object (in the context of connectivity check):\n    an object whose complete transitive closure is known to\n    be present for the purposes of the connectivity check.\n    For an object with traversed references, this requires\n    those referenced objects to be trusted.  Objects\n    reachable from current tips are implicitly trusted by\n    the existing connectivity invariant.\n\n  Boundary commit: a trusted commit at the edge between\n    already-trusted and newly introduced history.  More\n    precisely, a trusted commit reached while walking\n    parents from an incoming tip, where the adjacent\n    commit toward the incoming tip is not itself reachable\n    from any current tip.\n\n\nProblem statement\n-----------------\n\nThe current implementation delegates to a rev-list\nsubprocess:\n\n    rev-list --objects --stdin --not --all --quiet\n\nfeeding the incoming tips on stdin.  This reuses the existing\ntraversal machinery, which is nice, but it performs work that\ndepends on the existing repository size rather than the size\nof the incoming set.\n\nThe rev-list operation can be modeled as two steps.\n\n  1. Find the set of boundary commits, using graph traversal\n     seeded by all current tips and all the incoming tips.\n\n     The cost here comes both from the number of current tips\n     and the overall graph distance from the seeds to the\n     boundary.  As Patrick noted in the previous thread, this\n     becomes very slow with 880k refs.\n\n  2. Verify the objects reachable through the trees of the\n     incoming commits.  This is implemented by first walking\n     the complete tree closure of the boundary commits,\n     marking all visited objects as trusted (UNINTERESTING\n     in the rev-list semantics).  This ensures that walking\n     the tree closure of the incoming commits can be pruned\n     efficiently and thus becomes cheaper.\n\n     The cost here is the initial marking, which effectively\n     visits all active objects.\n\nSince the cost is approximately proportional to both the\nnumber of local tips and the size of the active object tree,\nit can slow down local fetch operations and server-side\nreceive-pack -- and I have observed this being one of the\nbottlenecks for servers with very frequent pushes.\n\nThe recent --skip-connectivity-check addition [2] lets server\noperators bypass the check entirely when they have external\nvalidation, which suggests the cost is a meaningful pain point\nfor some server operators.\n\nIdeally the connectivity check should be proportional to only\nthe incoming set.  I am not sure if we can fully reach that\nfor all scenarios, but it is possible for simple cases such\nas:\n\n  * pushing new commits on top of an existing branch\n  * force-pushing new commits that have been rebased on a\n    more recent origin/master.\n\nIf we manage to optimize the check for most scenarios, we can\nreduce the overall load on git servers even if edge cases will\nstill exist.\n\nThe two steps (finding the boundary, and verifying commit\ntrees) have independent scaling problems and I believe they\ncan be optimized mostly independently.\n\nI start with step 2 because it seems like the simplest one to\nreason about, and I also need it to simplify the solution for\nthe other problem (step 1).\n\n\nProposal for opportunistic trusted-tree discovery (for step 2)\n--------------------------------------------------------------\n\nThe current implementation eagerly walks the tree closure of\nthe boundary commits and marks the visited objects as trusted\nbefore verifying the incoming commits.  Instead, I propose\nmaintaining a cache of trusted objects while verifying the\nincoming commits.  A cached object does not need to be\nverified again; for a tree, this also lets us prune its\nentire closure.\n\nThe cache is populated in two ways with different goals:\n\nFirst, every object verified during the walk is cached, so\nwe never need to verify the same object twice.\n\nSecond, we can introduce a heuristic for opportunistically\npopulating the cache based on doing a parallel tree walk\nagainst trusted parent commits.\n\nIgnoring details like missing entries and type-changing paths,\nthe core idea is roughly:\n\n    global trusted_objects = {}\n    def visit_tree(candidate_tree, parent_trees):\n      for parent_tree in parent_trees:\n        for (_, obj) in entries(parent_tree):\n          trusted_objects += obj\n      for (name, obj) in candidate_tree:\n        if obj in trusted_objects: continue\n        if obj is a tree:\n          parent_subtrees = parent_trees.map(_.get(name))\n          visit_tree(obj, parent_subtrees)\n        // verify obj itself\n        trusted_objects += obj\n\nThis heuristic prunes verification to roughly the changed\nentries, as long as there are no cross-directory moves.  If\nthere are moves, such subtrees would be verified instead of\nskipped -- we may lose some pruning opportunities, but that\naffects performance rather than correctness.\n\nThis heuristic relies on parent-before-child processing\norder: all parents must already be known to be trusted before\nprocessing the child, otherwise entries from the parent side\ncannot safely be added to the cache.\n\n\nProposal for finding the boundary (step 1)\n------------------------------------------\n\nThis part is harder, but I think there are approaches that can\nspeed up the common case.\n\nThe simplest option: seed the traversal with a small set of\nlikely-useful refs (the old values of the refs being updated,\npossibly together with a few other likely tips) and a bounded\nwalk budget.  If every ancestry path from each incoming tip\nreaches a trusted commit within the budget, the boundary is\nclosed and we are done.  Otherwise fall back to --not --all\nas today.  This should cover many common push workflows and\nis straightforward to reason about.\n\nIf this finds a solution, it is not necessarily minimal.\nWalking from other refs could tighten the boundary, but this\nis still valid for correctness.  A non-minimal boundary means\nmore candidate commits to verify, but with opportunistic\ndiscovery (Proposal 1) that extra work is typically cheap --\nthose commits share most of their trees with their parents.\n\nA more ambitious follow-up could interleave lazy iteration of\nthe refs with the graph walk, rather than enumerating all refs\nup front.  Each newly loaded ref adds its tip to a shared\npriority queue, and the walk budget is charged globally\nregardless of which ref's ancestry is being explored.  Refs\nwould ideally be loaded in an order likely to close the\nboundary quickly, with a fallback to full ref enumeration if\nthe budget runs out.\n\nOne possible ordering mechanism would be a user-configured\npriority list of ref prefixes, though I have not explored that\nenough to argue for it yet.  The point is mostly that I think\nthis is solvable, but I do not know exactly what the best\nsolution would look like.\n\nFor the prototype I used the simple option, but I am less\nsure that hard-coding that heuristic is the right upstream\ninterface, and I would be happy to either flesh out the\nfollow-up idea or hopefully arrive at an even better approach\nthrough the discussion here.\n\n\nPreliminary results\n-------------------\n\nIt's too early for proper benchmarks, but I think it's useful\nto get a sense of what is possible.  My local prototype for\nboth proposals speeds up the connectivity check for a large\nrepository (3M commits, 200K refs, ~600K tree and blob\nobjects reachable from the boundary).  Numbers are\nintentionally rounded to one significant digit since this is\nnot scientific, purely intended as guidance for knowing if\nit's worth exploring further.\n\n  5-commit push, 45 changed files:\n\n  Current (rev-list --not --all):               1     s\n  Opportunistic discovery + bounded traversal:  0.03  s\n\n  1-commit push, trivial change:\n\n  Current (rev-list --not --all):               1     s\n  Opportunistic discovery + bounded traversal:  0.007 s\n\n\nOn this workload, the opportunistic discovery is much less\nimpactful than the boundary walk, but it is included here\nbecause I never attempted to combine the existing rev-list\n--objects mechanism with the new boundary search.\n\nThe bounded traversal (seeded with the old branch value)\navoids loading the full ref set, and opportunistic discovery\nreduces the object verification: around 100 objects walked\ninstead of the full 600 000 tree and blob objects.\n\n\nOther approaches considered\n---------------------------\n\nI also explored using commit-graph membership as evidence of\npast trust: if a commit is in the commit-graph and in the odb,\ntreat it as trusted and stop the walk there.  I initially\nhoped that GC's treatment of reachable closures might make\nthis safe as well.  However, it turns out to still\nbe hard to reason about what it means for an object to exist\nin the odb -- it may still exist in a pack that is retained\nbecause other objects inside are reachable.\n\nI gave up on that approach for now, but I am honestly not\ncertain if it's fully a dead end or not.\n\nFeedback requested\n------------------\n\nI am primarily interested in feedback on whether this problem\nis worth solving and if the proposed solution is going in the\nright direction, but any useful insights or gotchas that break\nthe idea are of course appreciated.\n\nI tried to keep this as high-level as possible and avoided\ndiscussing some of the edge cases -- some of my earlier\nemail drafts were much too long and it was a struggle to\ncondense it. That said, I included an appendix to present\nhow my prototype handles those cases if anyone is curious.\n\nThanks,\nKristofer\n\n\nAppendix: special cases\n-----------------------\n\nNon-commit tips: tags are peeled iteratively until reaching\na non-tag object.  Blob tips are verified for existence by\nthe peel step itself.  Tree tips get full closure verification\n(no parent diff, since there is no parent commit to diff\nagainst).  This is correct but not optimized -- and tree tips\nare uncommon in practice (I think).\n\nShallow clones: when a temporary shallow file is in effect,\nthe listed commits are treated as roots with no parents.\nTheir trees get full closure verification rather than a\nparent diff.  The parent-diff heuristic only applies above\nthe shallow boundary, which is where incoming commits are in\npractice.\n\nDeepening fetches: the entire deepened ancestry becomes\ncandidates, so there is no small incoming set to optimize\nfor.  The implementation falls back to the current rev-list\npath to avoid the memory overhead of tracking millions of\ncandidate commits in-process.  This could be optimized later\nif needed.\n\nPromisor remotes: the existing fast path that checks whether\nall wanted tips are present in promisor packs runs first,\nunchanged.  If that fast path does not cover all tips, the\noptimized verification path accepts any missing object\n(tree, blob, or tag target) that is a promisor object,\nmatching the --exclude-promisor-objects semantics.\n\nReplace objects: the optimized path assumes the physical\ncommit graph is acyclic.  Replace objects can violate that, so\nthe implementation falls back to the current rev-list path\nwhen any replace objects are configured.\n\n\n[1] https://lore.kernel.org/git/cover.1621451532.git.ps@pks.im/\n    (Speed up connectivity checks via quarantine dir,\n    Patrick Steinhardt, 2021)\n[2] https://lore.kernel.org/git/20250507030249.4802-1-jltobler@gmail.com/\n    (builtin/receive-pack: introduce option to skip connectivity checks,\n    Justin Tobler, 2025)\n"}]}