Merge lp:~mwhudson/loggerhead/persist-_rev_info into lp:~mwhudson/loggerhead/less-stupid-whole-history-redundancy

[Michael Hudson-Doyle]

[Paul Hummer (rockstar)]

Thanks for documenting the whole history data structures.

review: Approve

[Matt Nordhoff (mnordhoff)]

It's not a big deal, but could somebody make this merge request... go
away? This branch wasn't merged into
less-stupid-whole-history-redundancy, but it *was* merged into
lp:loggerhead, so for all intents and purposes it's been dealt with. But
this request is still open, so it's still listed on the merge request
summary page.
--

=== modified file 'loggerhead/apps/branch.py'
--- loggerhead/apps/branch.py	2009-04-07 18:29:10 +0000
+++ loggerhead/apps/branch.py	2009-04-24 10:23:44 +0000
@@ -38,27 +38,31 @@
         self.branch_link = branch_link  # Currently only used in Launchpad
         self.log = logging.getLogger('loggerhead.%s' % friendly_name)
         if graph_cache is None:
-            graph_cache = bzrlib.lru_cache.LRUCache()
+            graph_cache = bzrlib.lru_cache.LRUCache(10)
         self.graph_cache = graph_cache
         self.is_root = is_root
         self.served_url = served_url
         self.use_cdn = use_cdn
 
     def get_history(self):
-        _history = History(self.branch, self.graph_cache)
+        file_cache = None
+        revinfo_disk_cache = None
         cache_path = self._config.get('cachepath', None)
         if cache_path is not None:
             # Only import the cache if we're going to use it.
             # This makes sqlite optional
             try:
-                from loggerhead.changecache import FileChangeCache
+                from loggerhead.changecache import (
+                    FileChangeCache, RevInfoDiskCache)
             except ImportError:
                 self.log.debug("Couldn't load python-sqlite,"
                                " continuing without using a cache")
             else:
-                _history.use_file_cache(
-                    FileChangeCache(_history, cache_path))
-        return _history
+                file_cache = FileChangeCache(cache_path)
+                revinfo_disk_cache = RevInfoDiskCache(cache_path)
+        return History(
+            self.branch, self.graph_cache, file_cache=file_cache,
+            revinfo_disk_cache=revinfo_disk_cache, cache_key=self.friendly_name)
 
     def url(self, *args, **kw):
         if isinstance(args[0], list):

=== modified file 'loggerhead/apps/filesystem.py'
--- loggerhead/apps/filesystem.py	2009-04-23 23:39:18 +0000
+++ loggerhead/apps/filesystem.py	2009-04-24 10:23:44 +0000
@@ -71,7 +71,7 @@
 class BranchesFromFileSystemRoot(object):
 
     def __init__(self, folder, config):
-        self.graph_cache = lru_cache.LRUCache()
+        self.graph_cache = lru_cache.LRUCache(10)
         self.folder = folder
         self._config = config
 
@@ -94,7 +94,7 @@
 class UserBranchesFromFileSystemRoot(object):
 
     def __init__(self, folder, config):
-        self.graph_cache = lru_cache.LRUCache()
+        self.graph_cache = lru_cache.LRUCache(10)
         self.folder = folder
         self._config = config
         self.trunk_dir = config.get_option('trunk_dir')

=== modified file 'loggerhead/changecache.py'
--- loggerhead/changecache.py	2009-03-19 21:01:11 +0000
+++ loggerhead/changecache.py	2009-04-24 10:30:15 +0000
@@ -27,8 +27,10 @@
 """
 
 import cPickle
+import marshal
 import os
 import tempfile
+import zlib
 
 try:
     from sqlite3 import dbapi2
@@ -38,16 +40,25 @@
 # We take an optimistic approach to concurrency here: we might do work twice
 # in the case of races, but not crash or corrupt data.
 
+def safe_init_db(filename, init_sql):
+    # To avoid races around creating the database, we create the db in
+    # a temporary file and rename it into the ultimate location.
+    fd, temp_path = tempfile.mkstemp(dir=os.path.dirname(filename))
+    con = dbapi2.connect(temp_path)
+    cur = con.cursor()
+    cur.execute(init_sql)
+    con.commit()
+    con.close()
+    os.rename(temp_path, filename)
+
 class FakeShelf(object):
 
     def __init__(self, filename):
         create_table = not os.path.exists(filename)
         if create_table:
-            # To avoid races around creating the database, we create the db in
-            # a temporary file and rename it into the ultimate location.
-            fd, path = tempfile.mkstemp(dir=os.path.dirname(filename))
-            self._create_table(path)
-            os.rename(path, filename)
+            safe_init_db(
+                filename, "create table RevisionData "
+                "(revid binary primary key, data binary)")
         self.connection = dbapi2.connect(filename)
         self.cursor = self.connection.cursor()
 
@@ -89,8 +100,7 @@
 
 class FileChangeCache(object):
 
-    def __init__(self, history, cache_path):
-        self.history = history
+    def __init__(self, cache_path):
 
         if not os.path.exists(cache_path):
             os.mkdir(cache_path)
@@ -104,3 +114,44 @@
             changes = self.history.get_file_changes_uncached(entry)
             cache.add(entry.revid, changes)
         return changes
+
+
+class RevInfoDiskCache(object):
+    """Like `RevInfoMemoryCache` but backed in a sqlite DB."""
+
+    def __init__(self, cache_path):
+        if not os.path.exists(cache_path):
+            os.mkdir(cache_path)
+        filename = os.path.join(cache_path, 'revinfo.sql')
+        create_table = not os.path.exists(filename)
+        if create_table:
+            safe_init_db(
+                filename, "create table Data "
+                "(key binary primary key, revid binary, data binary)")
+        self.connection = dbapi2.connect(filename)
+        self.cursor = self.connection.cursor()
+
+    def get(self, key, revid):
+        self.cursor.execute(
+            "select revid, data from data where key = ?", (dbapi2.Binary(key),))
+        row = self.cursor.fetchone()
+        if row is None:
+            return None
+        elif str(row[0]) != revid:
+            return None
+        else:
+            return marshal.loads(zlib.decompress(row[1]))
+
+    def set(self, key, revid, data):
+        try:
+            self.cursor.execute(
+                'delete from data where key = ?', (dbapi2.Binary(key), ))
+            blob = zlib.compress(marshal.dumps(data))
+            self.cursor.execute(
+                "insert into data (key, revid, data) values (?, ?, ?)",
+                map(dbapi2.Binary, [key, revid, blob]))
+            self.connection.commit()
+        except dbapi2.IntegrityError:
+            # If another thread or process attempted to set the same key, we
+            # don't care too much -- it's only a cache after all!
+            pass

=== modified file 'loggerhead/history.py'
--- loggerhead/history.py	2009-04-24 03:44:30 +0000
+++ loggerhead/history.py	2009-04-24 10:30:15 +0000
@@ -31,6 +31,7 @@
 import bisect
 import datetime
 import logging
+import marshal
 import re
 import textwrap
 import threading
@@ -47,6 +48,7 @@
 import bzrlib.delta
 import bzrlib.diff
 import bzrlib.errors
+import bzrlib.lru_cache
 import bzrlib.progress
 import bzrlib.revision
 import bzrlib.textfile
@@ -177,6 +179,43 @@
                 file_id=file_id))
 
 
+class RevInfoMemoryCache(object):
+    """A store that validates values against the revids they were stored with.
+
+    We use a unique key for each branch.
+
+    The reason for not just using the revid as the key is so that when a new
+    value is provided for a branch, we replace the old value used for the
+    branch.
+
+    There is another implementation of the same interface in
+    loggerhead.changecache.RevInfoDiskCache.
+    """
+
+    def __init__(self, cache):
+        self._cache = cache
+
+    def get(self, key, revid):
+        """Return the data associated with `key`, subject to a revid check.
+
+        If a value was stored under `key`, with the same revid, return it.
+        Otherwise return None.
+        """
+        cached = self._cache.get(key)
+        if cached is None:
+            return None
+        stored_revid, data = cached
+        if revid == stored_revid:
+            return data
+        else:
+            return None
+
+    def set(self, key, revid, data):
+        """Store `data` under `key`, to be checked against `revid` on get().
+        """
+        self._cache[key] = (revid, data)
+
+
 class History (object):
     """Decorate a branch to provide information for rendering.
 
@@ -185,13 +224,76 @@
     around it, serve the request, throw the History object away, unlock the
     branch and throw it away.
 
-    :ivar _file_change_cache: xx
+    :ivar _file_change_cache: An object that caches information about the
+        files that changed between two revisions.
+    :ivar _rev_info: A list of information about revisions.  This is by far
+        the most cryptic data structure in loggerhead.  At the top level, it
+        is a list of 3-tuples [(merge-info, where-merged, parents)].
+        `merge-info` is (seq, revid, merge_depth, revno_str, end_of_merge) --
+        like a merged sorted list, but the revno is stringified.
+        `where-merged` is a tuple of revisions that have this revision as a
+        non-lefthand parent.  Finally, `parents` is just the usual list of
+        parents of this revision.
+    :ivar _rev_indices: A dictionary mapping each revision id to the index of
+        the information about it in _rev_info.
+    :ivar _full_history: A list of all revision ids in the ancestry of the
+        branch, in merge-sorted order.  This is a bit silly, and shouldn't
+        really be stored on the instance...
+    :ivar _revno_revid: A dictionary mapping stringified revnos to revision
+        ids.
     """
 
-    def __init__(self, branch, whole_history_data_cache):
+    def _load_whole_history_data(self, caches, cache_key):
+        """Set the attributes relating to the whole history of the branch.
+
+        :param caches: a list of caches with interfaces like
+            `RevInfoMemoryCache` and be ordered from fastest to slowest.
+        :param cache_key: the key to use with the caches.
+        """
+        self._rev_indices = None
+        self._rev_info = None
+
+        missed_caches = []
+        def update_missed_caches():
+            for cache in missed_caches:
+                cache.set(cache_key, self.last_revid, self._rev_info)
+        for cache in caches:
+            data = cache.get(cache_key, self.last_revid)
+            if data is not None:
+                self._rev_info = data
+                update_missed_caches()
+                break
+            else:
+                missed_caches.append(cache)
+        else:
+            whole_history_data = compute_whole_history_data(self._branch)
+            self._rev_info, self._rev_indices = whole_history_data
+            update_missed_caches()
+
+        if self._rev_indices is not None:
+            self._full_history = []
+            self._revno_revid = {}
+            for ((_, revid, _, revno_str, _), _, _) in self._rev_info:
+                self._revno_revid[revno_str] = revid
+                self._full_history.append(revid)
+        else:
+            self._full_history = []
+            self._revno_revid = {}
+            self._rev_indices = {}
+            for ((seq, revid, _, revno_str, _), _, _) in self._rev_info:
+                self._rev_indices[revid] = seq
+                self._revno_revid[revno_str] = revid
+                self._full_history.append(revid)
+
+    def __init__(self, branch, whole_history_data_cache, file_cache=None,
+                 revinfo_disk_cache=None, cache_key=None):
         assert branch.is_locked(), (
             "Can only construct a History object with a read-locked branch.")
-        self._file_change_cache = None
+        if file_cache is not None:
+            self._file_change_cache = file_cache
+            file_cache.history = self
+        else:
+            self._file_change_cache = None
         self._branch = branch
         self._inventory_cache = {}
         self._branch_nick = self._branch.get_config().get_nickname()
@@ -199,28 +301,10 @@
 
         self.last_revid = branch.last_revision()
 
-        cached_whole_history_data = whole_history_data_cache.get(self.last_revid)
-        if cached_whole_history_data is None:
-            whole_history_data = compute_whole_history_data(branch)
-            (self._rev_info, self._rev_indices) = whole_history_data
-            whole_history_data_cache[self.last_revid] = whole_history_data[0]
-            self._full_history = []
-            self._revno_revid = {}
-            for ((_, revid, _, revno_str, _), _, _) in self._rev_info:
-                self._revno_revid[revno_str] = revid
-                self._full_history.append(revid)
-        else:
-            self._rev_info = cached_whole_history_data
-            self._full_history = []
-            self._revno_revid = {}
-            self._rev_indices = {}
-            for ((seq, revid, _, revno_str, _), _, _) in self._rev_info:
-                self._rev_indices[revid] = seq
-                self._revno_revid[revno_str] = revid
-                self._full_history.append(revid)
-
-    def use_file_cache(self, cache):
-        self._file_change_cache = cache
+        caches = [RevInfoMemoryCache(whole_history_data_cache)]
+        if revinfo_disk_cache:
+            caches.append(revinfo_disk_cache)
+        self._load_whole_history_data(caches, cache_key)
 
     @property
     def has_revisions(self):

=== modified file 'loggerhead/wholehistory.py'
--- loggerhead/wholehistory.py	2009-04-24 03:12:28 +0000
+++ loggerhead/wholehistory.py	2009-04-24 10:30:15 +0000
@@ -37,6 +37,10 @@
 
 
 def compute_whole_history_data(branch):
+    """Compute _rev_info and _rev_indices for a branch.
+
+    See History.__doc__ for what these data structures mean.
+    """
     z = time.time()
 
     last_revid = branch.last_revision()