Improve the cache subsystem

[Remy Blank]

#9866 got me thinking about the cache subsystem, and there are at least two issues that could be improved:

• CachedProperty currently uses instance.__class__ to determine the module and class names. This is not correct when a component is subclassed, as seems to be the case e.g. in Agilo. This means that a cached property defined in an abstract base component, and inherited by sub-components, will have a different id in every subclass, and hence invalidating in one subclass will not invalidate the cached value in the other subclasses.

• Using a string identifier as a property id in the database was a pretty silly idea in retrospect. An integer hash of the identifier would be more space and time-efficient. Collisions are not an issue, as the only effect would be to invalidate slightly more than necessary.

The first issue is a bug, so I would like to fix it in 0.12-stable. The solution for the first item is to use the class where the property is defined to determine the module and class names.

The second is an enhancement that requires a DB upgrade, so I will implement it on trunk.

[Remy Blank]

The first issue is fixed in [10342] and [10343], by walking the class MRO to find the class where a property is defined.

[Remy Blank]

Change the cache table primary key to int.

[Remy Blank]

9870-int-cache-id-r10344.patch​ modifies the cache subsystem to use a hash of the property id in the cache table. It includes a DB upgrade to version 27.

[Christian Boos]

Well, the trouble with integer ids is maybe a lack of "readability" of the database content, at least for debugging.

Which makes me think we could add some debug commands to trac-admin, like here a trac-admin debug cache-ids that would list in clear text the cache identifiers and their generation info.

[Remy Blank]

Sure, but the cache table is not meant to be read (at least once the caching subsystem works correctly). Adding a debug command to trac-admin may be a good idea, but due to the id being a hash, there's no direct mapping back to the identifier. We would have to go through all components and find the descriptors. And this still wouldn't give us the cached attributes for non-Component classes (e.g. CachedRepository).

[Christian Boos]

Replying to rblank:

Sure, but the cache table is not meant to be read (at least once the caching subsystem works correctly)

Well, we thought it did work well for a while ;-) And even if it did, there can always be regressions, or plugin or local modifications which interfere, etc. All things that make having a quick look at the cache table useful for troubleshooting, just like we did in #9866.

there's no direct mapping back to the identifier. We would have to go through all components and find the descriptors. And this still wouldn't give us the cached attributes for non-Component classes (e.g. CachedRepository).

Right, I supposed we could somehow get easily a list of all the keys. But as it's not the case, then I think the trade-off between the proposed optimization and the loss of clarity is not in favor of the change. We already have an index for the id column for the performance part, and for the size, well, we'll never have that many different keys to weight as much as one version of a medium sized wiki page ;-)

[Remy Blank]

Replying to cboos:

We already have an index for the id column for the performance part, and for the size, well, we'll never have that many different keys to weight as much as one version of a medium sized wiki page ;-)

I haven't done any performance measurements yet, but I can't imagine a string comparison being as fast as an integer comparison, neither in Python code, nor in the database.

And the cache is all about speed, so I'd be ready to sacrifice a bit of clarity for speed. We do lack unit tests for the cache subsystem, so this should be improved as well.

Right, I supposed we could somehow get easily a list of all the keys. But as it's not the case, then I think the trade-off between the proposed optimization and the loss of clarity is not in favor of the change.

I might have been a bit to fast on that point. I have an idea how we can get the keys from the hashes. Actually, I have even two ideas how to get them. Let me try that.

[Christian Boos]

Replying to rblank:

I haven't done any performance measurements yet, but I can't imagine a string comparison being as fast as an integer comparison, neither in Python code, nor in the database.

And the cache is all about speed, so I'd be ready to sacrifice a bit of clarity for speed.

Ok, I did some timings, using an int is indeed about twice as fast as using text, at least for SQLite.

$ python cache_timings.py -r 1000 -t text
CREATE TABLE cache ( id text , generation int )
0.00494199991226

$ python cache_timings.py -r 1000 -t int
CREATE TABLE cache ( id int , generation int )
0.00275899982452

$ python cache_timings.py -r 1000 -t int --index
CREATE TABLE cache ( id int primary key, generation int )
0.00266400003433

$ python cache_timings.py -r 1000 -t text --index
CREATE TABLE cache ( id text primary key, generation int )
0.00402200007439

The timings above correspond mainly to the time spent executing the statement, if we also do fetch + print, the difference remains significant:

$ python cache_timings.py -r 1000 -t int --index -v > /dev/null
0.0091930000782
$ python cache_timings.py -r 1000 -t int --index -v > /dev/null
0.00841799998283
$ python cache_timings.py -r 1000 -t text --index -v > /dev/null
0.0170399999619
$ python cache_timings.py -r 1000 -t text --index -v > /dev/null
0.0155539999008

[Christian Boos]

simple timing program for various kind of cache table

[Christian Boos]

What about using an int index as you suggested (the hash of the property id) and store that property id for readability? (re: comment:5)

Not sure it's still high prio, nor needed for 0.13, I let you decide on that.

[Remy Blank]

Replying to cboos:

What about using an int index as you suggested (the hash of the property id) and store that property id for readability? (re: comment:5)

I already have a patch that does exactly that, but it requires a somewhat "hackish" implementation. I'll give it one more try and post the results here.

[Remy Blank]

Store cache id strings in the database.

[Remy Blank]

9870-int-cache-id-r10551.patch​ stores the cache id strings in the database as well, by keeping a global dict of hash-to-string (that's the hack I mentioned in comment:9). It also adds a trac-admin $ENV debug cache list command to view the content of the cache table.

Good enough? I'm not sure the debug command is actually needed, as a SELECT * FROM cache; also does the trick. Probably not.

[Christian Boos]

Replying to rblank:

9870-int-cache-id-r10551.patch​ stores the cache id strings in the database as well, by keeping a global dict of hash-to-string (that's the hack I mentioned in comment:9). It also adds a trac-admin $ENV debug cache list command to view the content of the cache table.

What's wrong with the builtin hash? Ok, it returns a signed 32 bits value but if this is really a problem we could do abs(hash(id)).

Good enough? I'm not sure the debug command is actually needed, as a SELECT * FROM cache; also does the trick. Probably not.

Well, the debug command would have been useful in case the SQL content alone wouldn't be self-explained, so I think we don't need it.

But what we should do is detect hash collisions (thanks to your _ids dict) and crash and burn if there's one ;-)

[Remy Blank]

Replying to cboos:

What's wrong with the builtin hash? Ok, it returns a signed 32 bits value but if this is really a problem we could do abs(hash(id)).

The signed value is not a problem. The reason I re-implemented the hash function is that there's no guarantee that the built-in hash() will return the same value for the same string in different versions of Python. The hash function doesn't have to be very fast, as it is only used during startup.

But what we should do is detect hash collisions (thanks to your _ids dict) and crash and burn if there's one ;-)

You mean, using the set_or_raise_if_already_present() method of dict? :)

[Christian Boos]

Replying to rblank:

Replying to cboos:

What's wrong with the builtin hash? Ok, it returns a signed 32 bits value but if this is really a problem we could do abs(hash(id)).

The signed value is not a problem. The reason I re-implemented the hash function is that there's no guarantee that the built-in hash() will return the same value for the same string in different versions of Python. The hash function doesn't have to be very fast, as it is only used during startup.

I see. But the last significant change in that code was done in … ​1996 ;-)

But what we should do is detect hash collisions (thanks to your _ids dict) and crash and burn if there's one ;-)

You mean, using the set_or_raise_if_already_present() method of dict? :)

Either when inserting in the dict, or when we do the select after the update, we could also get the name in addition to the generation and check at that point. But I just realized that a collision just means that the invalidation of a key will also invalidate the other… we're not going to miss notifications if I'm right, so this doesn't deserve more than a warning.

[Remy Blank]

Replying to cboos:

I see. But the last significant change in that code was done in … ​1996 ;-)

Yeah, I know, I'm paranoid :) Also, I just found out that hash() returns a 64-bit value on a 64-bit OS, so it's inherently non-portable.

Either when inserting in the dict, or when we do the select after the update, we could also get the name in addition to the generation and check at that point. But I just realized that a collision just means that the invalidation of a key will also invalidate the other… we're not going to miss notifications if I'm right, so this doesn't deserve more than a warning.

Heh, I really thought you were joking. Yes, your analysis is correct.

[Remy Blank]

Should I wait for the 0.13beta release to be close to apply this, or should I just go ahead? It requires a DB upgrade.

[Christian Boos]

No, please just go ahead, then we'll see if there's any issue with the upgrade prior to making the beta release, which is always a good thing ;-)

Be sure to warn about this upgrade in all the relevant places (i.e. 0.13, TracDev/ReleaseNotes and 0.13/TracUpgrade.

[Remy Blank]

Refactored patch applied in [10581]. I separated the CachedSingletonProperty and CachedProperty descriptors, as they are used in different contexts. This doesn't change anything for users of the cache subsystem. Also, is is now simpler to specify the property key for non-singleton classes.

The upgrade is now mentioned in the relevant documentation.

[Christian Boos]

I started to document the module in r10584 (see ​apidoc:api/trac_cache).

Replying to rblank:

Refactored patch applied in [10581]. I separated the CachedSingletonProperty and CachedProperty descriptors, as they are used in different contexts.

The change is good, however I think the docstrings can be improved. If I have trouble to understand the code which I helped (a bit) to develop, maybe other people would appreciate some extra hints ;-)

I feel a bit uneasy with the term singleton, as we don't use it elsewhere in Trac. I understand why we don't talk of Components here, but I think making clear that we're talking about a "per Environment singleton" would be better.

Suggested doc changes:

cache.py

@@ -51 +51 @@
 
     
 class CachedSingletonProperty(CachedPropertyBase):
-    """Cached property descriptor for singleton classes"""
+    """Cached property descriptor for classes behaving as singletons
+    in the scope of one `~trac.env.Environment` instance.
+
+    This means there will be no more than one cache to monitor in the
+    database for this kind of cache. Therefore, using only "static"
+    information for the key is enough. For the same reason it is also
+    safe to store the corresponding id as a property of the descriptor
+    instance.
+    """
     
     def __get__(self, instance, owner):
         if instance is None:
@@ -71 +79 @@
 
 
 class CachedProperty(CachedPropertyBase):
-    """Cached property descriptor"""
+    """Cached property descriptor for classes having potentially
+    multiple instances associated to a single `~trac.env.Environment`
+    instance.
+
+    As we'll have potentiall many different caches to monitor for this
+    kind of cache, the key needs to be augmented by a string unique to
+    each instance of the owner class.  As the resulting id will be
+    different for each instance of the owner class, we can't store it
+    as a property of the descriptor class, so we store it back in the
+    attribute used for augmenting the key (``key_attr``).
+    """
     
     def __init__(self, retriever, key_attr):
         super(CachedProperty, self).__init__(retriever)
@@ -103 +121 @@
     `CacheManager`. Invalidating the cache for this value is done by
     ``del``\ eting the attribute.
     
-    Note that the cache validity is maintained using a table in the
-    database.  Cache invalidation is performed within a transaction
-    block, and can be nested within another transaction block.
+    Note that the cache validity is maintained using the `cache` table
+    in the database.  Cache invalidation is performed within a
+    transaction block, and can be nested within another transaction
+    block.
     
-    The key used to identify the attribute in the database is
-    constructed from the names of the containing module, class and
-    retriever method. If the decorator is used in non-signleton
-    (typically non-`Component`) objects, an string specifying the name
-    of an attribute containing a string unique to the instance must be
-    passed to the decorator. This value will be appended to the key
-    constructed from module, class and method name::
+    When the decorator is used in a class for which instances behave
+    as singletons within the scope of a given `~trac.env.Environment`
+    (typically `~trac.core.Component` classes), the key used to
+    identify the attribute in the database is constructed from the
+    names of the containing module, class and retriever method::
 
+        class SomeComponent(object):
+            def __init__(self):
+                self._all_things = None
+
+            @cached
+            def all_things(self):
+                self._all_things = {}
+                ...
+
+    Otherwise, when the decorator is used in non-"singleton" objects,
+    a string specifying the name of an attribute containing a string
+    unique to the instance must be passed to the decorator. This value
+    will be appended to the key constructed from module, class and
+    method name::
+
         class SomeClass(object):
             def __init__(self, env, name):
                 self.env = env
@@ -125 +157 @@
             def metadata(self):
                 ...
 
-    Note that the key attribute is overwritten with a hash of the key on first
-    access, so it should not be used for any other purpose.
+    Note that in this case the key attribute is overwritten with a
+    hash of the key on first access, so it should not be used for any
+    other purpose.
     
-    This decorator requires that the object on which it is used has an `env`
-    attribute containing the application `Environment`.
+    In either case, this decorator requires that the object on which
+    it is used has an ``env`` attribute containing the application
+    `~trac.env.Environment`.
 
     .. versionchanged:: 0.13 
-
         The data retrieval method used to be called with a single
         argument ``db`` containing a reference to a database
         connection.  This is the same connection that can be retrieved

[Christian Boos]

Plus some further code simplification for the descriptor classes:

trac/cache.py

@@ -41 +41 @@
         self.retriever = retriever
         self.__doc__ = retriever.__doc__
 
+    def __get__(self, instance, owner):
+        if instance is None:
+            return self
+        return CacheManager(instance.env).get(
+            self.make_id(instance, owner), self.retriever, instance)
+
+    def __delete__(self, instance):
+        CacheManager(instance.env).invalidate(
+            self.make_id(instance, instance.__class__))
+
     def make_key(self, cls):
         attr = self.retriever.__name__
         for base in cls.mro():
@@ -61 +71 @@
     instance.
     """
 
-    def __get__(self, instance, owner):
-        if instance is None:
-            return self
+    def make_id(self, instance, owner):
         try:
             id = self.id
         except AttributeError:
             id = self.id = key_to_id(self.make_key(owner))
-        return CacheManager(instance.env).get(id, self.retriever, instance)
+        return id
 
-    def __delete__(self, instance):
-        try:
-            id = self.id
-        except AttributeError:
-            id = self.id = key_to_id(self.make_key(instance.__class__))
-        CacheManager(instance.env).invalidate(id)
-
-
 class CachedProperty(CachedPropertyBase):
     """Cached property descriptor for classes having potentially
     multiple instances associated to a single `~trac.env.Environment`
@@ -94 +94 @@
     def __init__(self, retriever, key_attr):
         super(CachedProperty, self).__init__(retriever)
         self.key_attr = key_attr
-
-    def __get__(self, instance, owner):
-        if instance is None:
-            return self
+
+    def make_id(self, instance, owner):
         id = getattr(instance, self.key_attr)
         if isinstance(id, str):
             id = key_to_id(self.make_key(owner) + ':' + id)
             setattr(instance, self.key_attr, id)
-        return CacheManager(instance.env).get(id, self.retriever, instance)
-
-    def __delete__(self, instance):
-        id = getattr(instance, self.key_attr)
-        if isinstance(id, str):
-            id = key_to_id(self.make_key(instance.__class__) + ':' + id)
-            setattr(instance, self.key_attr, id)
-        CacheManager(instance.env).invalidate(id)
+        return id
 
 
 def cached(fn_or_attr=None):

[Remy Blank]

The changes look great, except for the example in the singleton case. I wouldn't show an _all_things attribute, as it's unnecessary. You just need to return a value from the method, and it will be cached in the CacheManager. A more useful example could be:

class WikiSystem(Component):
    @cached
    def pages(self):
        return set(name for name, in
                   self.env.db_query("SELECT DISTINCT name FROM wiki"))

I didn't document CachedSingletonProperty and CachedProperty, as they actually aren't part of the public API. Only the cached() function is needed. But your descriptions are fine, so please go ahead.

[Remy Blank]

Replying to cboos:

Plus some further code simplification for the descriptor classes:

I prefer the current version, even though there is some code duplication. The way I have written it makes the common case as short as possible. That was actually the whole purpose of separating CachedSingletonProperty from CachedProperty, so re-combining __get__() and __delete__() is a step backwards for me.

Then again, the performance impact is probably negligible. If you prefer the simpler version, I can probably make it even simpler by re-combining them into a single CachedProperty.

[Christian Boos]

Doc updated in r10585.

No, separating them is good, it makes it immediately obvious we have two kind of descriptors. I was myself not fully convinced about my change seeing that CachedSingletonProperty.make_id() had to carry the superfluous instance parameter. But the kind of duplication I'm after was already present in the original code as well, so let me have another try:

trac/cache.py

@@ -64 +64 @@
     def __get__(self, instance, owner):
         if instance is None:
             return self
+        return CacheManager(instance.env).get(self.make_id(owner),
+                                              self.retriever, instance)
+
+    def __delete__(self, instance):
+        CacheManager(instance.env).invalidate(self.make_id(instance.__class__))
+
+    def make_id(self, owner):
         try:
             id = self.id
         except AttributeError:
             id = self.id = key_to_id(self.make_key(owner))
-        return CacheManager(instance.env).get(id, self.retriever, instance)
+        return id
 
-    def __delete__(self, instance):
-        try:
-            id = self.id
-        except AttributeError:
-            id = self.id = key_to_id(self.make_key(instance.__class__))
-        CacheManager(instance.env).invalidate(id)
-
-
 class CachedProperty(CachedPropertyBase):
     """Cached property descriptor for classes having potentially
     multiple instances associated to a single `~trac.env.Environment`
@@ -94 +93 @@
     def __init__(self, retriever, key_attr):
         super(CachedProperty, self).__init__(retriever)
         self.key_attr = key_attr
-
+
     def __get__(self, instance, owner):
         if instance is None:
             return self
+        return CacheManager(instance.env).get(self.make_id(instance, owner),
+                                              self.retriever, instance)
+
+    def __delete__(self, instance):
+        CacheManager(instance.env).invalidate(self.make_id(instance,
+                                                           instance.__class__))
+
+    def make_id(self, instance, owner):
         id = getattr(instance, self.key_attr)
         if isinstance(id, str):
             id = key_to_id(self.make_key(owner) + ':' + id)
             setattr(instance, self.key_attr, id)
-        return CacheManager(instance.env).get(id, self.retriever, instance)
-
-    def __delete__(self, instance):
-        id = getattr(instance, self.key_attr)
-        if isinstance(id, str):
-            id = key_to_id(self.make_key(instance.__class__) + ':' + id)
-            setattr(instance, self.key_attr, id)
-        CacheManager(instance.env).invalidate(id)
+        return id
 
 
 def cached(fn_or_attr=None):

It's a neutral change (+18/-18), but the "complex" parts are not duplicated so I find it easier to understand and maintain.