[ZODB-Dev] ZODB cache reimplementation

[Toby Dickenson]

On Thursday 24 January 2002 11:07 pm, you wrote:
>Toby Dickenson wrote:
>> I mentioned several weeks ago that I was planning to try changing
>> cPickleCache to use a LRU policy in deciding which objects to
>> ghostify, and stricter limits on the total size of the cache....
>
>I'm glad you brought this up. I've been meaning to get back
>with you on this. :)
>
>> Reviewing cPickleCache before starting work on this I have encountered
>> an aspect of its implementation that I didnt previously know about:
>> Normally cPickleCache is used to store instances of persistent
>> classes. However, cPickleCache contains some code to support the value
>> being a class itself (rather than a class instance).
>>
>> Whats that all about?
>
>It's about supporting persistent classes.
>
>> Is that capability used by anyone?
>
>Absolutely. It's used by ZClasses.

Urgh. Thats a different kind of voodoo that I havent looked at. I suspect my 
first implementation will not support that. 

> Note that we will
>have more freedom,  with Python 2.2 to use them in a more
>uniform way, so we may be able to get rid of the distinction
>in the cache code.
>
>Have you looked at the experiment I did in the Zope 3 branch
>using weak references?  There are a number of things I
>think we should do:

Not yet, but I will do.

>- Use weak references so that removal from the cache
>  is automatic. Use a customn weak reference implementation
>  to reduce memory consumption

I am currently undecided between two implementations. Variant A is very 
similar to what you describe below.

Variant B does not use weak references. This adds implementation simplicity, 
which is its main advantage. I dont see a clear advantage to automatically 
removing an object just because it has no references. Of course objects with 
no references are likely to remain unused, and the LRU rule will then remove 
them.

Variant B adds a small memory overhead. We want to keep the garbage 
collection to a single pass through the LRU list (and probably not the whole 
list too). That means that on ghostifying an object in the middle of the 
list, we may remove the last (last but one, including the dict) reference 
count of a previously scanned object. However, it will not be deallocated 
until a subsequent scan.

This may also add a performance overhead, if it means we have to check more 
objects in each scan.

>- Use your idea of a doubly linked list, with recently
>  used objects at one end.

A mammoth hacking session yesterday has producted a first prototype of this 
scheme. So far things look good. My benchmark is a test script which, under 
the old scheme, would use unbounded memory unless I added many calls to the 
incremental garbage collector through my application logic. Under the LRU 
scheme it runs using a constant 23M.

I hope to have something suitable for sharing later today, or monday.

Also, an unexpected advantage of this is that we avoid a call to time() on 
every attribute access. I think this may be the reason that some 
non-memory-intensive parts of my benchmark are showing a speedup too (on 
linux 2.4)

>- Separate the active objects from the ghosts, since we no longer,
>  with weak references, need to scan the ghosts.

yes, that is the advantage of weak references. ghosts take care of themselves.


>I imagine that this is close to what you've been thinking of.

Very close to my variant A.


>The cache has a dictionary that contains references to intermediate
> reference objects. The reference objects have references to the cache and
> to persistent objects. A persistent object is obtained from the cache
> through the cache reference.
>
>A reference object will be in one of two linked lists in the cache, one for
> ghosts and one for active objects.  The reference moves between lists when
> the persistent object changes states. List counts are also maintained for
> use by the cache management software. When an object is accessed, it is
> moved to back of the active list.

Some observations:

Does the persistent object have a reference to its intermediate object? In my 
scheme I had assumed not. List pointers are therefore stored in the 
persistent object, not the intermediate, meaning one less indirection on 
every attribute access (which I assume to be a common operation). My other 
reason for doing it the other way is so I can share more implementation with 
my Variant B, which does not use intermediate objects.

I dont think any scheme needs a list for ghosts. Why do they need to be 
ordered?

> When the cache does GC, it scans the
> active list from the front for objects to be removed.  Normally, any object
> it finds may be removed, unless is is locked. An object is locked when it
> is accessed from C. Perhaps there should be a separate locked list.

Ive never used that locking mechanism, but the examples I have to work from 
(BTrees) only lock briefly. I am expecting the GC scanning to encounter few 
locked objects even if they are kept in the active list.

>The cache reference is essentially a weak reference to the object. It does
>not increase the persistent object's reference count. When a persistent
> object is deallocated, it (in it's dealloc):
>
>  - Removes (zeros) it's reference from the reference object,
>
>  - Removes the reference object from whatever list it's in,
>
>  - Removes itself from the cache's data mapping by deleting the
>    key with the objects object id.
>
>It's awfully tempting to combine the reference object with the persistent
>object to avoid the malloc and Python object overhead and the object
> pointer. There's some  risk that somehow the deletion of the object from
> the cache's data mapping could fail on deallocation, which would lead to a
> memory error of some kind later.

It would be nicer to play fair with the Dictionary implementation, and allow 
him to keep a reference count on his referent. If malloc overhead is 
significant then we can keep a free list. Overhead should be small since we 
expect the total number of these objects to be constant (if the cache manager 
is doing its job properly).

>I think it might be a good idea to discuss this verbally. Is there a good
>time for me to call you?

Timezone-wise I am located in the UK. Maybe next week after I have published 
this first implementation.

>Are you going to Python 10 by any chance?

Unfortuantely no.