## page was renamed from stablerangecache
#pragma section-numbers 2

<<Include(A:dev)>>

= 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

== 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...

== Detailed description ==

Please read associated documentation in the experimental code:

 * [[https://www.mercurial-scm.org/repo/evolve/file/tip/hgext3rd/evolve/stablesort.py|underlying stable sorting concept]]
 * [[https://www.mercurial-scm.org/repo/evolve/file/tip/hgext3rd/evolve/stablerange.py|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")

== 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
 * {X} efficient cache storage in core (space and access time)
 * {X} fast algorithms implementation in core

== See Also ==

 * CEDObsmarkersExchange
 * PullBundleCachePlan

----
CategoryDeveloper CategoryNewFeatures