Note:
This page is primarily intended for developers of Mercurial.
Stable Range
Status: experiment done - waiting on core implementation
Main proponents: Pierre-YvesDavid
Stable range provide a standard way to slice the history DAG into a small number of range
1. Goal
Stable-ranges get useful when some logic needs a recursive way to slice the history of a repository in smaller and smaller group of revisions. Here is example of such use cases:
bundle caching:
- With an easy way to slice any subsets of history into stable-ranges, we can cache a small number of bundles covering these ranges and reuse them for other pull operations. Even if the pull operation have different boudaries.
metadata discovery:
- With a simple way to recursively look at smaller and smaller ranges, an algorithm can do fine-grained discovery of area of history where some mutable metadata differ from one repository to another. Such meta data can be obsolescence markers, CI status, lightweight stag, etc...
2. Detailed description
Please read associated documentation in the experimental code:
The experiment show it has the right scaling property. We have been able to use it in production for the two projected usecase.
The documentation constains idea for a more final form of data storage. The final size you be < 1% of the current sqlite storage size.
In short we need to store the following data for each revision:
depth len(::R)
the first merge max(merge() and ::R)
- a set of "jumps" used for stable sort (for merge only)
- the subranges for the standard R-headed ranges
(A scientific paper is also in the writing, link to the draft to be shared "shortly")
3. Roadmap
having a stable sorting algorithm - having a stable range algorithm
- experimental implementation
- test experimental implementation for obsmarkers discovery
- test experimental implementation for bundle caching
efficient cache storage in core (space and access time) - fast algorithms implementation in core
4. See Also
- CEDObsmarkersExchange