caching pull - stable partitioning of bundle requests
Boris FELD
boris.feld at octobus.net
Wed Sep 26 18:13:13 UTC 2018
Hi everyone,
Pulling from a server involves expensive server-side computation that we
wish to cache. However, since the client can pull any arbitrary set of
revision, grouping and dispatching the data to be cached is ahard problem.
When we implemented the new discovery for obsolescence markers, we
developed a "stablerange" method to build an efficient way to slice the
changesets graph into ranges. In addition to solving the obsolescence
markers discovery problem, this "stablerange" principle seemed to be
useful for more usages, in particular,the caching of pulls.
Right now, with the current pull bundle implementation, here is how it
work: you manually create and manually declare bundles containing either
all changesets (that could also be used for clone bundles) or more
specific ones. When the client request some changesets, the server
searches a bundle containing the needed range and send it. This often
involves more than the requested data. The client needs to filter out
the extraneous data. Then the client does a discovery to catch any
missing changesets from the bundle. If the server doesn't find a valid
pull bundle, a normal discovery is done.The manual bundle managements is
suboptimal, the search for appropriate bundles has a bad complexity and
the extra roundtrip and discovery adds extra slowness.
This weekend, we build a "simple" prototype that use "stablerange" to
slice changegroup request in "getbundle" into multiple bundlesthat can
be reused from one pull to another. That slicing happens as part of a
normal pull, during the getbundle call and after the normal discovery
happens. There are no needs for an extra discovery and getbundle call
after it.
With this"stablerange"based strategy,we start from the set of requested
changesets to generate a set of "standard" range covering all of them.
This slicing has a good algorithmic complexity that depends on the size
of the selected "missing" set of changesets. So the associated cost of
will scale well with the size of the associated pull. In addition, we no
longer have to do an expensive search into a list existing bundles. This
helps to scale small pulls and increase the number of bundles we can
cache, as the time we spend selecting bundle no longer depends on the
numbers of cached ones. Since we can exactly cover the client request,
we also no longer need to issue anextra pull roundtrip after the cache
retrieval.
That slicing focus on producing ranges that:
* Have a high chance to be reusable in a pull selecting similar
changesets,
* Gather most of the changesets in large bundles.
This caching strategy inherits the nice "stablerange" properties
regarding repository growth
* When a few changesets are appended to a repository, only a few
ranges haveto be added.
* The overall number of ranges (and associated bundles) to create to
represent all possible ranges has anO(N log(N)) complexity.
For example, here are the 15 ranges selected for a full clone of
mozilla-central:
* |262114 changesets|
* |30 changesets|
* |65536 changesets|
* |32741 changesets|
* |20 changesets|
* |7 changesets|
* |8192 changesets|
* |243 changesets|
* |13 changesets|
* |114 changesets|
* |14 changesets|
* |32 changesets|
* |16 changesets|
* |8 changesets|
* |1 changesets|
*
If we only clone a subset of the repository, the larger ranges get
reused (hg clone --rev -5000):
* |262114 changesets found in caches|
* |30 changesets found in caches|
* |65536 changesets found in caches|
* |32741 changesets found in caches|
* |20 changesets found in caches|
* |7 changesets found in caches|
* |2048 changesets found|
* |1024 changesets found|
* |482 changesets found|
* |30 changesets found|
* |32 changesets found|
* |1 changesets found|
* |7 changesets found|
* |4 changesets found|
* |2 changesets found|
* |1 changesets found|
As you can see, the larger ranges of this second pull are common with
the previous pull, allowing to reuse cached bundles.
The prototype is available in a small "pullbundle" extension. It focuses
on the slicing itself and we did not implement anything fancy for the
cache storage and delivery. We simply store generated bundle on disk and
we read it from disk when it is needed again. Others, like Joerg
Sonnenberger or Gregory Szorc, are already working on the "cache
delivery" problem.
We are getting good result our of that prototypes when testing it on
clones of mozilla-central and netbsd-src. See "Example Result" section
for detail.
The prototype is up and running on our hgweb "mirror" instance
https://mirror.octobus.net/.
The extension comes with a small debug command that produces statistic
of the ranges that multiple random pulls would use.
The "stablerange" implementation currently still[1] live in the evolve
extensions, so we put the extensions in the same repository for
simplicity as "pullbundle". This is not ideal but was a simple solution
in the time we could dedicate. This extension is not part of any
official release yet. To test it you have to install it from the
repository for now: https://www.mercurial-scm.org/repo/evolve/#default
The extension's code is here:
https://www.mercurial-scm.org/repo/evolve/file/tip/hgext3rd/pullbundle.py
The prototype performance is not stellar, but good enough to give useful
result in a reasonable amount of time. A production-grade implementation
of stablerange algorithm and storage will fix that. There is also room
for improvement progression in the algorithm themselves, multiple
sub-problem can be improved. We started having regular meeting with
University researcher working on graph theory, they are interested in
the problem space.
[1] The stablerange principle has been validating in the field and is
ready to get upstreamed.
Example results.
The extensions comewith a command to simulate multiple pullsof a random
set of revisions (from a larger set of revision we define). This starts
with a cold cache for simplicity.
Mozilla Central
We gathering 100 sample pulls within 20443 revisions
* Median pull size: 18 338
* Median number of changegroup used: 132 changegroups.
* Median changeset not cached: 88
* Median ratio of changeset already in the cache: 99.5%
The number of different ranges staysunder control as expected:
* Total changeset served: 1 817 955
* Total changeset cache hit ratio: 96% (from a cold cache)
* Distinct range cached: 12 983, Most of them very small (90% ≤ 32
changesets)
* A small number of (larger) ranges get most of the cache hit.
Providing the smaller range from cache might not be a good tradeoff. If
we skip using the cache for smaller ranges we still get interesting results:
Only caching range containing 256 changeset or more:
* Median pull size: 18 940
* Median number of changegroup used: 12
* Median changeset not cached: 1 949
* Median ratio of changeset already in the cache: 90%
* Total changeset served: 1 850 243
* Total changeset cache hit ratio: 87%
* Distinct range cached: 1 150
Another way to reduce the number of server bundle would be to do some
"over serving": using bundle containing some common changesets.
(See the end of the email for full details)
netbsd
This time, we issues more random pull (1000) within a set a bit smaller
set of 10 000 changesets.
This resulted in smaller pulls, that also show good results:
* Median pull size: 1673
* Median number of changegroup used: 51
* Median changeset not cached: 50
* Median ratio of changeset already in the cache: 99%
* Total changeset served: 1601087
* Total changeset cache hit ratio: 96%
* Distinct range cached: 51751
Trying the same 256+ changesets limit on caching, we see a stronger
impact. Probably because of the smaller pulls:
* Median pull size: 1592
* Median number of changegroup used: 2
* Median changeset not cached: 663
* Median ratio of changeset already in the cache: 46%
* Total changeset served: 1 554 227
* Total changeset cache hit ratio: 56%
* Distinct range cached: 1 914
(See the end of the email for full details)
pypy
pypy testing was done using 1 000 pulls within 16687 changesets.
* Median pull size: 11375
* Median number of changegroup used: 1206
* Median changeset not cached: 12
* Median ratio of changeset already in the cache: 100%
* Total changeset served: 11 167 863
* Total changeset cache hit ratio: 99%
* Distinct range cached: 1 139 537
Installing the 256+ changeset limits give less good results. This is
probably the result of a shallower pull space and the amount of merge in
the pypy repository. The pypy repository is significantly more branchy
than the other ones, there issome known way we could improve stablerange
partitioning in this cases (to produce larger ranges).
* Median pull size: 11457
* Median number of changegroup used: 9
* Median changeset not cached: 7276
* Median ratio of changeset already in the cache: 37%
* Total changeset served: 11211093
* Total changeset cache hit ratio: 36%
* Distinct range cached: 8964
Full details:
mozilla central, 100 pull in 20553 revisions, no limit
   mozilla-central> hg debugpullbundlecacheoverlap --count 100 -- 'tip~10000:'
   gathering 100 sample pulls within 20443 revisions
   pull size:
     min: 13176
     10%: 16425
     25%: 17344
     50%: 18338
     75%: 19192
     90%: 19719
     95%: 19902
     max: 20272
   non-cached changesets:
     min: 4
     10%: 10
     25%: 24
     50%: 88
     75%: 237
     90%: 956
     95%: 3152
     max: 17440
   ratio of cached changesets:
     min: 0.0
     10%: 0.947941624918
     25%: 0.987343800064
     50%: 0.995036297078
     75%: 0.998774313882
     90%: 0.999421798208
     95%: 0.999634750848
     max: 0.999795354548
   bundle count:
     min: 74
     10%: 99
     25%: 113
     50%: 132
     75%: 146
     90%: 158
     95%: 169
     max: 186
   ratio of cached bundles:
     min: 0.0
     10%: 0.685082872928
     25%: 0.810810810811
     50%: 0.911392405063
     75%: 0.953020134228
     90%: 0.974683544304
     95%: 0.98125
     max: 0.993377483444
   changesets served:
     total:     1817955
     from cache: 1752642 (96%)
     bundle:      12983
   size of cached bundles:
     min: 1
     10%: 1
     25%: 2
     50%: 4
     75%: 9
     90%: 32
     95%: 64
     max: 8165
   hit on cached bundles:
     min: 1
     10%: 1
     25%: 1
     50%: 2
     75%: 4
     90%: 14
     95%: 20
     max: 100
mozilla central, 100 pull in 20443 revision, only caching ranges
of 256 changeset and above
mozilla-central > hg debugpullbundlecacheoverlap --count 100 --min-cache=256 -- 'tip~10000:'
gathering 100 sample pulls within 20443 revisions
not caching ranges smaller than 256 changesets
pull size:
min: 14060
10%: 16910
25%: 17923
50%: 18940
75%: 19471
90%: 19884
95%: 20029
max: 20309
non-cached changesets:
min: 973
10%: 1398
25%: 1707
50%: 1949
75%: 2246
90%: 2590
95%: 3448
max: 19551
ratio of cached changesets:
min: 0.0
10%: 0.839908649729
25%: 0.884512085944
50%: 0.897293365889
75%: 0.91018907563
90%: 0.926944971537
95%: 0.935139218649
max: 0.946839315959
bundle count:
min: 4
10%: 10
25%: 11
50%: 12
75%: 12
90%: 13
95%: 15
max: 16
ratio of cached bundles:
min: 0.0
10%: 0.909090909091
25%: 1.0
50%: 1.0
75%: 1.0
90%: 1.0
95%: 1.0
max: 1.0
changesets served:
total: 1850243
from cache: 1617379 (87%)
bundle: 1150
size of cached bundles:
min: 256
10%: 256
25%: 256
50%: 512
75%: 1024
90%: 1024
95%: 1024
max: 8165
hit on cached bundles:
min: 1
10%: 1
25%: 1
50%: 7
75%: 44
90%: 44
95%: 59
max: 98
netbsd-src 1000 pull within 10000 revisions:
netbsd-src > hg debugpullbundlecacheoverlap --count 1000 -- '-10000:'
gathering 1000 sample pulls within 10000 revisions
pull size:
min: 10
10%: 339
25%: 865
50%: 1673
75%: 2330
90%: 2752
95%: 2893
max: 3466
non-cached changesets:
min: 0
10%: 3
25%: 7
50%: 16
75%: 50
90%: 137
95%: 239
max: 2787
ratio of cached changesets:
min: 0.0
10%: 0.781553398058
25%: 0.940663176265
50%: 0.987631184408
75%: 0.996178830722
90%: 0.99843688941
95%: 0.998939554613
max: 1.0
bundle count:
min: 10
10%: 28
25%: 37
50%: 51
75%: 65
90%: 78
95%: 88
max: 121
ratio of cached bundles:
min: 0.0
10%: 0.446808510638
25%: 0.673076923077
50%: 0.826086956522
75%: 0.901639344262
90%: 0.942857142857
95%: 0.96
max: 1.0
changesets served:
total: 1601087
from cache: 1539491 (96%)
bundle: 51751
size of cached bundles:
min: 1
10%: 1
25%: 1
50%: 1
75%: 4
90%: 8
95%: 16
max: 2048
hit on cached bundles:
min: 1
10%: 1
25%: 1
50%: 2
75%: 3
90%: 8
95%: 13
max: 291
netbsd-src 1000 pull within 10000 revisions, not caching range
smaller than 256:
netbsd-src > hg debugpullbundlecacheoverlap --count 1000 --min-cache=256 -- '-10000:'
gathering 1000 sample pulls within 10000 revisions
not caching ranges smaller than 256 changesets
pull size:
min: 10
10%: 329
25%: 813
50%: 1592
75%: 2271
90%: 2745
95%: 2922
max: 3719
non-cached changesets:
min: 10
10%: 265
25%: 440
50%: 663
75%: 911
90%: 1111
95%: 1229
max: 2852
ratio of cached changesets:
min: 0.0
10%: 0.0
25%: 0.136752136752
50%: 0.461261261261
75%: 0.686327077748
90%: 0.792263056093
95%: 0.829552819183
max: 0.959700093721
bundle count:
min: 0
10%: 0
25%: 1
50%: 2
75%: 3
90%: 4
95%: 4
max: 6
ratio of cached bundles:
min: 0.0
10%: 1.0
25%: 1.0
50%: 1.0
75%: 1.0
90%: 1.0
95%: 1.0
max: 1.0
changesets served:
total: 1554227
from cache: 871680 (56%)
bundle: 1914
size of cached bundles:
min: 256
10%: 256
25%: 256
50%: 256
75%: 512
90%: 512
95%: 512
max: 2048
hit on cached bundles:
min: 2
10%: 3
25%: 7
50%: 61
75%: 113
90%: 113
95%: 117
max: 267
pypy 1000 pulls within 16687 changesets:
pypy > time hg debugpullbundlecacheoverlap --count 1000 -- 'tip~2000:'
gathering 1000 sample pulls within 16687 revisions
pull size:
min: 5835
10%: 9165
25%: 10323
50%: 11375
75%: 12248
90%: 12904
95%: 13181
max: 14221
non-cached changesets:
min: 0
10%: 1
25%: 4
50%: 12
75%: 39
90%: 142
95%: 453
max: 12046
ratio of cached changesets:
min: 0.0
10%: 0.986539780521
25%: 0.99640167364
50%: 0.99889963059
75%: 0.99964598637
90%: 0.999911496593
95%: 1.0
max: 1.0
bundle count:
min: 183
10%: 762
25%: 1045
50%: 1206
75%: 1308
90%: 1387
95%: 1427
max: 1631
ratio of cached bundles:
min: 0.0
10%: 0.972310126582
25%: 0.990171990172
50%: 0.995529061103
75%: 0.997882851094
90%: 0.999203821656
95%: 1.0
max: 1.0
changesets served:
total: 11167863
from cache: 11060195 (99%)
bundle: 1139537
size of cached bundles:
min: 1
10%: 1
25%: 1
50%: 2
75%: 4
90%: 15
95%: 30
max: 2041
hit on cached bundles:
min: 1
10%: 1
25%: 1
50%: 3
75%: 20
90%: 245
95%: 848
max: 999
pypy 1000 pulls within 16687 changesets:, caching above 256
changesets only:
|
   time hg debugpullbundlecacheoverlap --count 1000 --min-cache=256 --
'tip~2000:'
   gathering 1000 sample pulls within 16687 revisions
     not caching ranges smaller than 256 changesets
   pull size:
     min: 3629
     10%: 9075
     25%: 10278
     50%: 11457
     75%: 12325
     90%: 12961
     95%: 13245
     max: 14330
   non-cached changesets:
     min: 2605
     10%: 5885
     25%: 6619
     50%: 7276
     75%: 7813
     90%: 8319
     95%: 8577
     max: 11815
   ratio of cached changesets:
     min: 0.0
     10%: 0.296190172981
     25%: 0.344310129221
     50%: 0.368110984417
     75%: 0.391840607211
     90%: 0.417344173442
     95%: 0.445362934971
     max: 0.544580009385
   bundle count:
     min: 1
     10%: 7
     25%: 8
     50%: 9
     75%: 10
     90%: 11
     95%: 11
     max: 12
   ratio of cached bundles:
     min: 0.0
     10%: 1.0
     25%: 1.0
     50%: 1.0
     75%: 1.0
     90%: 1.0
     95%: 1.0
     max: 1.0
   changesets served:
     total:     11211093
     from cache: 4066703 (36%)
     bundle:       8964
   size of cached bundles:
     min: 256
     10%: 256
     25%: 256
     50%: 468
     75%: 510
     90%: 1019
     95%: 512
     max: 1916
   hit on cached bundles:
     min: 1
     10%: 1
     25%: 3
     50%: 13
     75%: 63
     90%: 823
     95%: 153
     max: 958|
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20180926/c7ff9c32/attachment.html>
More information about the Mercurial-devel
mailing list