HomeSoftware Heritage

Use a Merkle discovery algorithm with archives


Use a Merkle discovery algorithm with archives

"Discovery" is the term used to find out the differences between two
Merkle graphs. Using such an algorithm is useful in that it drastically
reduces the amount of data that needs to be transferred.

This commit introduces an efficient but simple algorithm that is a good
starting point for improved performance: random sampling of directories,
the details of which are explained in the docstrings.

Mercurial uses a more sophisticated algorithm for its discovery, but it
is quite a bit more involved and would introduce too much complexity at
once. Also, the constraints for speed that Mercurial has (in the order
of milliseconds) don't apply as obviously to this context without
further investigation.



  • With a local postgresql storage (so no network overhead), a local tmpfs obstorage on a fast NVME SSD, all of which should make this improvement look less good than it will be in production
  • With a tarball of the linux kernel at commit d96d875ef5dd372f533059a44f98e92de9cf0d42 already loaded
  • Loading a tarball of 20 commits earlier (bf3f401db6cbe010095fe3d1e233a5fde54e8b78)
  • Only taking into account the loading (not the downloading of the tarball, or its decompression)


before: ~30s
after: ~17s

Reproduced 4 times.


AlphareAuthored on Sep 22 2022, 12:09 PM
AlpharePushed on Sep 26 2022, 5:39 PM
AlpharePushed on Sep 26 2022, 5:32 PM
Differential Revision
D8521: Use a Merkle discovery algorithm with archives
rDLDBASE26fe954bd9dc: golang: Fix imports ordering reported by isort
Build Status
Buildable 31764
Build 49700: test-and-buildJenkins console · Jenkins