( )⚙ D1208 basepack: add a lru cache for the pack files

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1208

basepack: add a lru cache for the pack files
ClosedPublic

Authored by singhsrb on Oct 23 2017, 3:15 PM.
Tags
None
Subscribers
durham

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGXf5784ad7d9e9: basepack: add a lru cache for the pack files
Summary

To speed up pack lookups (especially when there are lots of packs), we
should maintain an lru ordering of the packs and perform searches in that
order, since it's likely the next entry we search for will be in the same pack
file as the last entry we searched for. This commit achieves the same.

Test Plan
  • Ran all the tests.
  • Created ~2k pack files in a large repo.
    • Time taken without the cache:
      • hg update b while at a: ~18 minutes.
      • hg update a while at b: ~23 seconds.
    • Time taken with the cache:
      • hg update b while at a: ~14 seconds.
      • hg update a while at b: ~9 seconds.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

singhsrb created this revision.Oct 23 2017, 3:15 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptOct 23 2017, 3:15 PM
singhsrb added a comment.EditedOct 23 2017, 3:18 PM

I have verified that the cache behaves as expected. I will add more tests for the caching anyways. I wanted to put this out so that there are some eyes on it before I go too far.

Please see D1220 for some idea of how I tested the improvements due to the cache.

singhsrb edited the test plan for this revision. (Show Details)Oct 23 2017, 3:20 PM
durham requested changes to this revision.Oct 23 2017, 10:44 PM
durham added a subscriber: durham.
durham added inline comments.
remotefilelog/basepack.py
105

Why not put the default value on the basepackstore instead of putting the same value on both derived types?

129

Why do we need the notion of a path in this class? I would kinda expect this class to just have an add(pack) and __iter__ functions? No need to implement the rest of the apis if we never use them. Then this could just be named self._packs and the member on basepackstore could go back to being self.packs?

130

If the reason for making _pathtopack a dictionary was because lrucachedict is a dictionary, you can just make lrucachedict a dictionary of pack->True

167

This sort could still save on the initial lookup right? Seems like a reasonable win for such a small amount of code.

This revision now requires changes to proceed.Oct 23 2017, 10:44 PM
singhsrb planned changes to this revision.Oct 23 2017, 11:41 PM

@durham I am assuming you are good with the overall approach. I will make the appropriate fixes.

remotefilelog/basepack.py
105

The value happens to be the same but in general, I wanted the child classes to decide on the default size. Or, at least have the option of overriding the default in the child classes.

129

I considered this and then was pretty much lazy because I had already written the code based on the dict. Wanted to get the idea out there more than get it out perfectly :). I will fix this!

130

Sure!

167

I remember I put this TODO here because the caching I added doesn't use the most recent files anyways (and I wanted to bring that to attention of the reviewers) and it seemed to not make too much of a difference. I have a better idea to actually load the cache with the most recent entries instead of a cold start.

singhsrb updated this revision to Diff 3077.Oct 24 2017, 2:04 AM
singhsrb added inline comments.Oct 24 2017, 2:06 AM
remotefilelog/basepack.py
243–244

Hmm, the _getavailablepackfiles returns the most recent packs but conversion to set here can possibly throw away that information. We can probably also refactor/fix this code.

durham requested changes to this revision.Oct 26 2017, 4:12 PM

Sorry for the late review. I think it looks good, but it just needs a test.

remotefilelog/basepack.py
47

You can still put this on the basepackstore class, so subclasses can override it if they want.

129

I'd probably avoid nesting the classes. Just make this a top level class. Nested classes introduce some possible confusion around scope and what the inner class has access to.

141

Generally I would check if self._lastpack is not None: instead of relying on the default handler. A pack implementation might implement something like len which python would then use to check if the pack was empty here, which could be expensive.

170

This pattern is pretty clever!

This revision now requires changes to proceed.Oct 26 2017, 4:12 PM
durham accepted this revision.Oct 26 2017, 4:13 PM

Ah I see the test is another diff. Probably worth fixing some of the comments, but accepting so you're not blocked after.

This revision is now accepted and ready to land.Oct 26 2017, 4:13 PM
singhsrb updated this revision to Diff 3157.Oct 30 2017, 2:09 PM
singhsrb marked 2 inline comments as done.Oct 30 2017, 2:13 PM

The test is still pending but I guess this is in a good shape now.

remotefilelog/basepack.py
141

Neat! I wasn't aware so much can happen under the hood. Will keep this in mind for future!

singhsrb updated this revision to Diff 3300.Nov 6 2017, 6:35 PM
singhsrb planned changes to this revision.Nov 7 2017, 12:13 PM
singhsrb added inline comments.
tests/remotefilelog-datapack.py
305

This loop is unnecessary. I might have a better way to test this.

singhsrb updated this revision to Diff 3322.Nov 7 2017, 2:10 PM
This revision is now accepted and ready to land.Nov 7 2017, 2:10 PM
singhsrb requested review of this revision.Nov 7 2017, 2:12 PM

The test still needs to be reviewed.

singhsrb updated this revision to Diff 3323.Nov 7 2017, 2:15 PM
singhsrb updated this revision to Diff 3324.
durham added inline comments.Nov 7 2017, 7:59 PM
tests/remotefilelog-datapack.py
296

It's a bit confusing to call this packs since it's actually a bunch of revisions. I was pretty confused about why 'pack.index' worked below. Maybe rename this 'deltachains' or something?

durham accepted this revision.Nov 7 2017, 8:09 PM
This revision is now accepted and ready to land.Nov 7 2017, 8:09 PM
singhsrb updated this revision to Diff 3329.Nov 7 2017, 8:24 PM
singhsrb marked an inline comment as done.Nov 7 2017, 8:27 PM
Closed by commit rFBHGXf5784ad7d9e9: basepack: add a lru cache for the pack files (authored by singhsrb). · Explain WhyNov 8 2017, 6:28 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3355

remotefilelog/basepack.py

SMALLFANOUTCUTOFF = 2**16 / 8 SMALLFANOUTCUTOFF = 2**16 / 8
# The amount of time to wait between checking for new packs. This prevents an # The amount of time to wait between checking for new packs. This prevents an
# exception when data is moved to a new pack after the process has already # exception when data is moved to a new pack after the process has already
# loaded the pack list. # loaded the pack list.
REFRESHRATE = 0.1 REFRESHRATE = 0.1
if pycompat.isposix: if pycompat.isposix:
# With glibc 2.7+ the 'e' flag uses O_CLOEXEC when opening. # With glibc 2.7+ the 'e' flag uses O_CLOEXEC when opening.
durhamUnsubmitted
Done

You can still put this on the basepackstore class, so subclasses can override it if they want.

durham: You can still put this on the basepackstore class, so subclasses can override it if they want.
# The 'e' flag will be ignored on older versions of glibc. # The 'e' flag will be ignored on older versions of glibc.
PACKOPENMODE = 'rbe' PACKOPENMODE = 'rbe'
else: else:
PACKOPENMODE = 'rb' PACKOPENMODE = 'rb'
class _cachebackedpacks(object):
def __init__(self, packs, cachesize):
self._packs = set(packs)
self._lrucache = util.lrucachedict(cachesize)
self._lastpack = None
# Avoid cold start of the cache by populating the most recent packs
# in the cache.
for i in reversed(range(min(cachesize, len(packs)))):
self._movetofront(packs[i])
def _movetofront(self, pack):
# This effectively makes pack the first entry in the cache.
self._lrucache[pack] = True
def _registerlastpackusage(self):
if self._lastpack is not None:
self._movetofront(self._lastpack)
self._lastpack = None
def add(self, pack):
self._registerlastpackusage()
# This method will mostly be called when packs are not in cache.
# Therefore, adding pack to the cache.
self._movetofront(pack)
self._packs.add(pack)
def __iter__(self):
self._registerlastpackusage()
# Cache iteration is based on LRU.
for pack in self._lrucache:
self._lastpack = pack
yield pack
cachedpacks = set(pack for pack in self._lrucache)
# Yield for paths not in the cache.
for pack in self._packs - cachedpacks:
self._lastpack = pack
yield pack
# Data not found in any pack.
self._lastpack = None
class basepackstore(object): class basepackstore(object):
# Default cache size limit for the pack files.
DEFAULTCACHESIZE = 100
def __init__(self, ui, path): def __init__(self, ui, path):
self.ui = ui self.ui = ui
self.path = path self.path = path
self.packs = []
durhamUnsubmitted
Not Done

Why not put the default value on the basepackstore instead of putting the same value on both derived types?

durham: Why not put the default value on the basepackstore instead of putting the same value on both…
singhsrbAuthorUnsubmitted
Not Done

The value happens to be the same but in general, I wanted the child classes to decide on the default size. Or, at least have the option of overriding the default in the child classes.

singhsrb: The value happens to be the same but in general, I wanted the child classes to decide on the…
# lastrefesh is 0 so we'll immediately check for new packs on the first # lastrefesh is 0 so we'll immediately check for new packs on the first
# failure. # failure.
self.lastrefresh = 0 self.lastrefresh = 0
packs = []
for filepath, __, __ in self._getavailablepackfilessorted(): for filepath, __, __ in self._getavailablepackfilessorted():
try: try:
pack = self.getpack(filepath) pack = self.getpack(filepath)
except Exception as ex: except Exception as ex:
# An exception may be thrown if the pack file is corrupted # An exception may be thrown if the pack file is corrupted
# somehow. Log a warning but keep going in this case, just # somehow. Log a warning but keep going in this case, just
# skipping this pack file. # skipping this pack file.
# #
# If this is an ENOENT error then don't even bother logging. # If this is an ENOENT error then don't even bother logging.
# Someone could have removed the file since we retrieved the # Someone could have removed the file since we retrieved the
# list of paths. # list of paths.
if getattr(ex, 'errno', None) != errno.ENOENT: if getattr(ex, 'errno', None) != errno.ENOENT:
ui.warn(_('unable to load pack %s: %s\n') % (filepath, ex)) ui.warn(_('unable to load pack %s: %s\n') % (filepath, ex))
continue continue
self.packs.append(pack) packs.append(pack)
self.packs = _cachebackedpacks(packs, self.DEFAULTCACHESIZE)
def _getavailablepackfiles(self): def _getavailablepackfiles(self):
durhamUnsubmitted
Not Done

Why do we need the notion of a path in this class? I would kinda expect this class to just have an add(pack) and __iter__ functions? No need to implement the rest of the apis if we never use them. Then this could just be named self._packs and the member on basepackstore could go back to being self.packs?

durham: Why do we need the notion of a path in this class? I would kinda expect this class to just…
singhsrbAuthorUnsubmitted
Not Done

I considered this and then was pretty much lazy because I had already written the code based on the dict. Wanted to get the idea out there more than get it out perfectly :). I will fix this!

singhsrb: I considered this and then was pretty much lazy because I had already written the code based on…
durhamUnsubmitted
Done

I'd probably avoid nesting the classes. Just make this a top level class. Nested classes introduce some possible confusion around scope and what the inner class has access to.

durham: I'd probably avoid nesting the classes. Just make this a top level class. Nested classes…
"""For each pack file (a index/data file combo), yields: """For each pack file (a index/data file combo), yields:
durhamUnsubmitted
Not Done

If the reason for making _pathtopack a dictionary was because lrucachedict is a dictionary, you can just make lrucachedict a dictionary of pack->True

durham: If the reason for making _pathtopack a dictionary was because lrucachedict is a dictionary, you…
singhsrbAuthorUnsubmitted
Not Done

Sure!

singhsrb: Sure!
(full path without extension, mtime, size) (full path without extension, mtime, size)
mtime will be the mtime of the index/data file (whichever is newer) mtime will be the mtime of the index/data file (whichever is newer)
size is the combined size of index/data file size is the combined size of index/data file
""" """
indexsuffixlen = len(self.INDEXSUFFIX) indexsuffixlen = len(self.INDEXSUFFIX)
packsuffixlen = len(self.PACKSUFFIX) packsuffixlen = len(self.PACKSUFFIX)
ids = set() ids = set()
sizes = defaultdict(lambda: 0) sizes = defaultdict(lambda: 0)
mtimes = defaultdict(lambda: []) mtimes = defaultdict(lambda: [])
durhamUnsubmitted
Not Done

Generally I would check if self._lastpack is not None: instead of relying on the default handler. A pack implementation might implement something like len which python would then use to check if the pack was empty here, which could be expensive.

durham: Generally I would check `if self._lastpack is not None:` instead of relying on the default…
singhsrbAuthorUnsubmitted
Not Done

Neat! I wasn't aware so much can happen under the hood. Will keep this in mind for future!

singhsrb: Neat! I wasn't aware so much can happen under the hood. Will keep this in mind for future!
try: try:
for filename, size, stat in osutil.listdir(self.path, stat=True): for filename, size, stat in osutil.listdir(self.path, stat=True):
id = None id = None
if filename[-indexsuffixlen:] == self.INDEXSUFFIX: if filename[-indexsuffixlen:] == self.INDEXSUFFIX:
id = filename[:-indexsuffixlen] id = filename[:-indexsuffixlen]
elif filename[-packsuffixlen:] == self.PACKSUFFIX: elif filename[-packsuffixlen:] == self.PACKSUFFIX:
id = filename[:-packsuffixlen] id = filename[:-packsuffixlen]
else: else:
ids.add(id) ids.add(id)
except OSError as ex: except OSError as ex:
if ex.errno != errno.ENOENT: if ex.errno != errno.ENOENT:
raise raise
def _getavailablepackfilessorted(self): def _getavailablepackfilessorted(self):
"""Like `_getavailablepackfiles`, but also sorts the files by mtime, """Like `_getavailablepackfiles`, but also sorts the files by mtime,
yielding newest files first. yielding newest files first.
durhamUnsubmitted
Not Done

This sort could still save on the initial lookup right? Seems like a reasonable win for such a small amount of code.

durham: This sort could still save on the initial lookup right? Seems like a reasonable win for such a…
singhsrbAuthorUnsubmitted
Not Done

I remember I put this TODO here because the caching I added doesn't use the most recent files anyways (and I wanted to bring that to attention of the reviewers) and it seemed to not make too much of a difference. I have a better idea to actually load the cache with the most recent entries instead of a cold start.

singhsrb: I remember I put this TODO here because the caching I added doesn't use the most recent files…
This is desirable, since it is more likely newer packfiles have more This is desirable, since it is more likely newer packfiles have more
desirable data. desirable data.
durhamUnsubmitted
Not Done

This pattern is pretty clever!

durham: This pattern is pretty clever!
""" """
files = [] files = []
for path, mtime, size in self._getavailablepackfiles(): for path, mtime, size in self._getavailablepackfiles():
files.append((mtime, size, path)) files.append((mtime, size, path))
files = sorted(files, reverse=True) files = sorted(files, reverse=True)
for mtime, size, path in files: for mtime, size, path in files:
yield path, mtime, size yield path, mtime, size
def getpack(self, path): def getpack(self, path):
raise NotImplemented() raise NotImplemented()
def getmissing(self, keys): def getmissing(self, keys):
missing = keys missing = keys
for pack in self.packs: for pack in self.packs:
missing = pack.getmissing(missing) missing = pack.getmissing(missing)
# Ensures better performance of the cache by keeping the most
# recently accessed pack at the beginning in subsequent iterations.
if not missing:
return missing
if missing: if missing:
for pack in self.refresh(): for pack in self.refresh():
missing = pack.getmissing(missing) missing = pack.getmissing(missing)
return missing return missing
def markledger(self, ledger): def markledger(self, ledger):
for pack in self.packs: for pack in self.packs:
# If we experience a lot of misses (like in the case of getmissing() on # If we experience a lot of misses (like in the case of getmissing() on
# new objects), let's only actually check disk for new stuff every once # new objects), let's only actually check disk for new stuff every once
# in a while. Generally this code path should only ever matter when a # in a while. Generally this code path should only ever matter when a
# repack is going on in the background, and that should be pretty rare # repack is going on in the background, and that should be pretty rare
# to have that happen twice in quick succession. # to have that happen twice in quick succession.
newpacks = [] newpacks = []
if now > self.lastrefresh + REFRESHRATE: if now > self.lastrefresh + REFRESHRATE:
self.lastrefresh = now self.lastrefresh = now
previous = set(p.path for p in self.packs) previous = set(p.path for p in self.packs)
for filepath, __, __ in self._getavailablepackfilessorted(): for filepath, __, __ in self._getavailablepackfilessorted():
singhsrbAuthorUnsubmitted
Not Done

Hmm, the _getavailablepackfiles returns the most recent packs but conversion to set here can possibly throw away that information. We can probably also refactor/fix this code.

singhsrb: Hmm, the `_getavailablepackfiles` returns the most recent packs but conversion to set here can…
if filepath not in previous: if filepath not in previous:
newpacks.append(self.getpack(filepath)) newpack = self.getpack(filepath)
self.packs.extend(newpacks) newpacks.append(newpack)
self.packs.add(newpack)
return newpacks return newpacks
class versionmixin(object): class versionmixin(object):
# Mix-in for classes with multiple supported versions # Mix-in for classes with multiple supported versions
VERSION = None VERSION = None
SUPPORTED_VERSIONS = [0] SUPPORTED_VERSIONS = [0]

tests/remotefilelog-datapack.py

import silenttestrunner import silenttestrunner
# Load the local remotefilelog, not the system one # Load the local remotefilelog, not the system one
sys.path[0:0] = [os.path.join(os.path.dirname(__file__), '..')] sys.path[0:0] = [os.path.join(os.path.dirname(__file__), '..')]
from remotefilelog.datapack import ( from remotefilelog.datapack import (
datapack, datapack,
datapackstore,
fastdatapack, fastdatapack,
mutabledatapack, mutabledatapack,
) )
from remotefilelog.basepack import ( from remotefilelog.basepack import (
SMALLFANOUTCUTOFF, SMALLFANOUTCUTOFF,
SMALLFANOUTPREFIX, SMALLFANOUTPREFIX,
LARGEFANOUTPREFIX, LARGEFANOUTPREFIX,
) )
pack = self.createPack(revisions) pack = self.createPack(revisions)
if self.paramsavailable: if self.paramsavailable:
self.assertEquals(pack.params.fanoutprefix, LARGEFANOUTPREFIX) self.assertEquals(pack.params.fanoutprefix, LARGEFANOUTPREFIX)
for (filename, node), content in blobs.iteritems(): for (filename, node), content in blobs.iteritems():
actualcontent = pack.getdeltachain(filename, node)[0][4] actualcontent = pack.getdeltachain(filename, node)[0][4]
self.assertEquals(actualcontent, content) self.assertEquals(actualcontent, content)
def testPacksCache(self):
"""Test that we remember the most recent packs while fetching the delta
chain."""
packdir = self.makeTempDir()
deltachains = []
# Ensures that we are not keeping everything in the cache.
numpacks = datapackstore.DEFAULTCACHESIZE * 2
revisionsperpack = 100
for i in range(numpacks):
chain = []
revision = (str(i), self.getFakeHash(), nullid, "content")
for _ in range(revisionsperpack):
chain.append(revision)
revision = (
str(i),
self.getFakeHash(),
revision[1],
self.getFakeHash()
)
self.createPack(chain, packdir)
deltachains.append(chain)
durhamUnsubmitted
Done

It's a bit confusing to call this packs since it's actually a bunch of revisions. I was pretty confused about why 'pack.index' worked below. Maybe rename this 'deltachains' or something?

durham: It's a bit confusing to call this `packs` since it's actually a bunch of revisions. I was…
store = datapackstore(mercurial.ui.ui(), packdir)
random.shuffle(deltachains)
for randomchain in deltachains:
revision = random.choice(randomchain)
chain = store.getdeltachain(revision[0], revision[1])
mostrecentpack = next(iter(store.packs), None)
singhsrbAuthorUnsubmitted
Not Done

This loop is unnecessary. I might have a better way to test this.

singhsrb: This loop is unnecessary. I might have a better way to test this.
self.assertEquals(
mostrecentpack.getdeltachain(revision[0], revision[1]),
chain
)
self.assertEquals(randomchain.index(revision) + 1, len(chain))
# perf test off by default since it's slow # perf test off by default since it's slow
def _testIndexPerf(self): def _testIndexPerf(self):
random.seed(0) random.seed(0)
print "Multi-get perf test" print "Multi-get perf test"
packsizes = [ packsizes = [
100, 100,
10000, 10000,
100000, 100000,