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:

* underlying stable sorting concept * stablerange itself

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

• PullBundleCache

CategoryDeveloper CategoryNewFeatures