This discussion explores advanced strategies for managing very large and deep directories within version control systems like Jujutsu (jj), drawing on experiences from Google and Meta. The core problem is the performance degradation and high storage cost associated with traditional tree objects in repositories containing directories with hundreds of thousands of files. Two primary solutions are debated: "polytrees" (probabilistic B-trees), which flatten the entire repository file list and use content-defined chunking to create a balanced, fixed-depth tree; and "prefix trees," which split directory listings into sharded subtrees when they exceed a size threshold.
The conversation covers the trade-offs of each approach, including hashing compatibility with Git, performance edge cases like cascading changes in polytrees, and threshold "thrashing" in prefix trees. The implementation of such a system in jj would necessitate a new, non-Git-compatible object type and a major overhaul of the core data model. The discussion also touches upon the user experience implications for sparse checkouts and lazy-loading backends that these optimizations would enable.
Addressing Performance in Repositories with Large Directories
0:00 - The Problem with Large Directories: At companies like Google, single directories can contain hundreds of thousands of entries (e.g., a user experiments directory). The corresponding tree objects become very large (e.g., 10+ MB), making operations like reading, diffing, and storing them slow and expensive.
1:18 - Solution 1: Polytrees (Probabilistic B-trees): A proposed solution is to abandon the one-tree-per-directory model. Instead, represent all files in the repository as a single flat list, which is then sliced into smaller chunks using a content-defined hashing algorithm. This creates a balanced tree with a predictable, shallow depth, solving issues with both very large and very deep directories.
4:46 - Solution 2: Prefix Trees: An alternative approach is to use sharded prefix trees. This method transforms a directory's file listing into a prefix tree and then splits nodes into separate objects once they grow beyond a certain size threshold.
5:54 - Prefix Tree vs. Polytree Trade-offs: The prefix tree approach maintains a more direct mapping to the traditional directory structure, which can be advantageous. However, polytrees may offer a more perfectly balanced distribution. A key downside of polytrees is the risk of "tail latencies," where a small change can cause a large cascade of re-chunking.
7:58 - Deterministic Hashing is Key: A critical property for these systems is deterministic hashing—the same repository state must always produce the same hash. To maintain this, a prefix tree system would accept the rare computational cost of "thrashing" (repeatedly splitting and merging) when a directory hovers around the size threshold, rather than introducing hysteresis that would make hashes path-dependent.
15:51 - Major Implementation Change for Jujutsu (jj): Integrating either solution would be a significant overhaul of jj's core data model. It would require a new object type, would not be compatible with the standard Git backend, and would likely be implemented as an opt-in feature for specific scalable backends.
17:16 - User Experience in a Lazy-Loaded World: These optimizations enable handling repositories that are too large to fit on a local disk, relying on sparse checkouts and lazy fetching. This introduces new UX challenges, such as how the system should behave when parts of a directory are inaccessible due to being offline.
20:35 - Interaction with Sparse Profiles: The behavior of commands like ls in a partially checked-out large directory is discussed. The consensus is that sparse profiles should still be the source of truth for the user, meaning jj would hide files that are present in a local shard but not requested by the user's sparse checkout pattern.
22:53 - Risk of Backend Divergence: A concern is raised that if these advanced tree structures are only used in specialized, scalable backends, developers working primarily with the Git backend might accidentally write code (e.g., full tree traversals) that is inefficient or incorrect on the more complex backends.