RFC: bitmap storage for precursors and phases

Gregory Szorc gregory.szorc at gmail.com
Mon Feb 13 22:28:37 EST 2017



> On Feb 10, 2017, at 10:33, Stanislau Hlebik <stash at fb.com> wrote:
> 
> Last year Durham sent a proposal for bitmap storage for computehidden() https://www.mercurial-scm.org/pipermail/mercurial-devel/2016-September/087860.html.
>  
> It got a few useful comments, two most important comments:
> Use bitmaps for lower-level data structures, for example, bitmap for public commits and bitmap for commits that are affected by obsolescence markers
> Add cache validation checks
>  
> This is a new RFC that addresses these issues.
> In the code, there is a cache only for precursors. Later I'm planning to add cache for public commits.
> Cache validation key was added. It can be any key. For precursorcache I've chosen obsstore file size and mtime and cache validation key. For phasecache we can use hash of sorted phaseroots file since this file is usually small. 

Until there is a better supported mechanism for storing "draft pushes" in an external store (Facebook's inifinitepush extension may fulfill this), Mozilla's "Try" and code review repos need to scale to >100,000 heads / phase roots. So a hash of phaseroots may not scale. (Of course, one solution to this problem would be inverting phases storage to be head based instead of root based. That doesn't solve problem if you have 100k public heads and 100k draft heads. Scaling is hard.)

>  
> In a few places, I decided to delete cache entirely:
> Caches are blown up if we receive obsmarkers via bundle2 or exchange._pullobsolete(). This is not necessary since cache won't be valid on the next run anyway because obsstore size and/or mtime was changed. We can change it.
> Obsstore can store markers for node that are not present in the repo. Since bitmap is basically a dict from rev to boolean it can't store markers for revisions that are not in the repo. It doesn't cause issues unless missing node is received from bundle or during pull. In this case precursorcache doesn't recognize it as obsoleted. To fix it cache is deleted during changegroup.apply() if we receive a node that is in obsstore.successors dict.
> Similar thing in bundlerepo - new obsoleted nodes may have been added, let's just not use precursorcache in bundlerepo.
>  
>  
> The code is here: https://bitbucket.org/stashlebik/hg/commits/branch/hiddenbitmaps
> It's not super clean yet, but all tests pass (except maybe for commit/code checks).
> Please look and let me know what you think!
>  
>  
> Thanks,
> Stas
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20170213/8d6a975e/attachment.html>


More information about the Mercurial-devel mailing list