diff --git a/remotefilelog/basestore.py b/remotefilelog/basestore.py
--- a/remotefilelog/basestore.py
+++ b/remotefilelog/basestore.py
@@ -383,9 +383,36 @@
 
 class baseunionstore(object):
     def __init__(self, *args, **kwargs):
-        pass
+        # If one of the functions that iterates all of the stores is about to
+        # throw a KeyError, try this many times with a full refresh between
+        # attempts. A repack operation may have moved data from one store to
+        # another while we were running.
+        self.numattempts = kwargs.get('numretries', 0) + 1
+        # If not-None, call this function on every retry and if the attempts are
+        # exhausted.
+        self.retrylog = kwargs.get('retrylog', None)
 
     def markforrefresh(self):
         for store in self.stores:
             if util.safehasattr(store, 'markforrefresh'):
                 store.markforrefresh()
+
+    @staticmethod
+    def retriable(fn):
+        def noop(*args):
+            pass
+        def wrapped(self, *args, **kwargs):
+            retrylog = self.retrylog or noop
+            funcname = fn.__name__
+            for i in xrange(self.numattempts):
+                if i > 0:
+                    retrylog('re-attempting (n=%d) %s\n' % (i, funcname))
+                    self.markforrefresh()
+                try:
+                    return fn(self, *args, **kwargs)
+                except KeyError:
+                    pass
+            # retries exhausted
+            retrylog('retries exhausted in %s, raising KeyError\n' % funcname)
+            raise
+        return wrapped
diff --git a/remotefilelog/contentstore.py b/remotefilelog/contentstore.py
--- a/remotefilelog/contentstore.py
+++ b/remotefilelog/contentstore.py
@@ -64,6 +64,7 @@
 
         return text
 
+    @basestore.baseunionstore.retriable
     def getdelta(self, name, node):
         """Return the single delta entry for the given name/node pair.
         """
@@ -99,6 +100,7 @@
 
         return chain
 
+    @basestore.baseunionstore.retriable
     def getmeta(self, name, node):
         """Returns the metadata dict for given node."""
         for store in self.stores:
@@ -112,6 +114,7 @@
         metrics = [s.getmetrics() for s in self.stores]
         return shallowutil.sumdicts(*metrics)
 
+    @basestore.baseunionstore.retriable
     def _getpartialchain(self, name, node):
         """Returns a partial delta chain for the given name/node pair.
 
diff --git a/remotefilelog/metadatastore.py b/remotefilelog/metadatastore.py
--- a/remotefilelog/metadatastore.py
+++ b/remotefilelog/metadatastore.py
@@ -69,6 +69,7 @@
         # TODO: ancestors should probably be (name, node) -> (value)
         return ancestors
 
+    @basestore.baseunionstore.retriable
     def _getpartialancestors(self, name, node, known=None):
         for store in self.stores:
             try:
@@ -78,6 +79,7 @@
 
         raise KeyError((name, hex(node)))
 
+    @basestore.baseunionstore.retriable
     def getnodeinfo(self, name, node):
         for store in self.stores:
             try: