cache eviction policy is too eager?

2005-07-14
2013-06-03
  • Bryan Thompson
    Bryan Thompson
    2005-07-14

    Hello,

    It seems to me that the cache eviction policy is too eager.  As it stands in the default configuration the CacheRecordManager coordinates with the MRU CachePolicy to evict the least recently used object from the cache once the cache is full.  However, if there is a hard reference to this object held by the application, then the data associated with the cache is still in memory.  Hence the only savings is that the cache hashtable size is kept to a maximum value.  (Side note, it looks like the Hashtable should be initialized to the configured maximum cache size to avoid sporatic delays as the hash table grows in capacity.)

    Further, there appear to be three layers of cache in play.  The CacheRecordManager has its private CacheEntry objects, which are what it inserts into the MRU CachePolicy (and hence into the Hashtable).  However, the MRU class has its own private CacheEntry class which adds the prior and next links used by that CachePolicy.  Finally, there is the actual application object - a reference to this is held by the CacheRecordManager's CacheEntry object.

    Each call to CacheRecordManager.update() is required to test against the cache.  It seems that an application could drammatically improve update performance by coordinating with the cache entry, e.g., by hold a hard reference to the cache entry.  This would obviate the need to test for a cache hit in update altogether since the application object would directly hold the reference to the cache data.  Another way to do this is to have the application object optionally implement a cache entry interface.  If that interface is implemented, then we can avoid cache tests for in-memory objects.

    Finally, cache eviction is only reasonable when the application object is finalizable.  As I noted before, if there is a hard reference to the application object then evicting the object from cache appears to do nothing (other than force a sync to disk).

    I see that there is code in CacheRecordManager.update() to place the application object back into the cache so that the live object is always used in preference to the object on disk, which ensures that we never get more than one reference to a persistent application object with the same recid.  If we used a protocol to perform cache eviction only when the application object was finalized, then we could drop this since there would never be an opportunity to update an object that was not already in the cache.

    Thoughts?

    -bryan

     
    • Alex Boisvert
      Alex Boisvert
      2005-07-15

      Bryan,

      I see where you're coming from.  The best cache management policy is usually a function of the type of application/usage.

      It seems to me that what you're looking for is a cache policy that would use weak references.   This type of cache would keep track of the objects you have in memory and lower the cost of updating the LRU structures for every access.

      What do you think?

      alex

       
      • Kevin Day
        Kevin Day
        2005-07-18

        If anyone does decide to pursue this, I have a WeakValueHashMap that I put together a few years ago for a similar purpose.  It's been in use for about 3 or 4 years now, so the kinks or pretty much worked out.

        In terms of optimization, there may be some tuning opportunities in determining when to flush references (right now I do it every time an object is inserted - it may be better to have a configurable load factor and only purge every XXX puts...)

        Here's the code:

        package com.trumpetinc.util;

        import java.util.Collection;
        import java.util.HashMap;
        import java.util.*;
        import java.lang.ref.*;

        /**
        * @version     1.0
        * @author      Kevin Day (Trumpet, Inc.)
        */
        public class WeakValueHashMap extends HashMap {
            private static final long serialVersionUID = 3977303234983573560L;

            ReferenceQueue refQ = new ReferenceQueue();
            HashMap reverseMap = new HashMap();
           
            /**
             * Constructor for WeakValueHashMap.
             * @param initialCapacity
             * @param loadFactor
             */
            public WeakValueHashMap(int initialCapacity, float loadFactor) {
                super(initialCapacity, loadFactor);
            }

            /**
             * Constructor for WeakValueHashMap.
             * @param initialCapacity
             */
            public WeakValueHashMap(int initialCapacity) {
                super(initialCapacity);
            }

            /**
             * Constructor for WeakValueHashMap.
             */
            public WeakValueHashMap() {
                super();
            }

            /**
             * Constructor for WeakValueHashMap.
             * @param m
             */
            public WeakValueHashMap(Map m) {
                super(m);
            }

            /*
             * @see Map#get(Object)
             */
            public synchronized Object get(Object key) {
                clearUnreferencedValues();
                   
                Reference val = (Reference)super.get(key);
                Object oval = val != null ? val.get() : null;
                return oval;
            }

            public synchronized void clearUnreferencedValues(){
                Object val = null;
                val=refQ.poll();
                while (val != null){
                    Object key = reverseMap.remove(val);
        //System.out.println(this + " is removing " + key);           
                    this.remove(key);
                    val = refQ.poll();
                }
            }

            /**
             * Puts the specified value into the Map.  Ensures that the value
             * is a weak reference.  Note that it is not possible to store
             * WeakReferences themselves into this Map - they will be dereferenced
             * during get().
             * If an attempt is made to store a null value as the value (or if a
             * Reference is passed in that returns null from it's get() method)
             * The key and value will NOT be added to the map, and null will be
             * returned.
             * @see Map#put(Object, Object)
             */
            public synchronized Object put(Object key, Object value) {
                clearUnreferencedValues();
                Reference nextRef = null;
                if (value instanceof Reference)
                    value = ((Reference)value).get();
                if (value != null){
                    nextRef = new WeakReference(value, refQ);
                    reverseMap.put(nextRef, key);
                    return super.put(key, nextRef);
                } else {
                    return null;
                }
            }

            /**
             * Returns a collection containing the values contained within
             * this map.  This collection is a snapshot of the map at the time
             * the method is called.
             * @see Map#values()
             */
            public synchronized Collection values() {
                Collection snapshot = new ArrayList(size());
                Object val = null;
                for (Iterator it = super.values().iterator(); it.hasNext();) {
                    Reference ref = (Reference) it.next();
                    val = ref.get();
                    if (val != null)
                        snapshot.add(val);
                }
                return snapshot;
            }

            /*
             * @see Map#containsKey(Object)
             */
            public synchronized boolean containsKey(Object key) {
                return get(key) != null;
            }

        }

         
        • Bryan Thompson
          Bryan Thompson
          2005-07-28

          Kevin,

          If it is Ok with you, I would like to pursue this and create another CachePolicy implementation that uses the WeakValueHashMap and contribute the result back into the jdbm project, e.g., as a files within the jdbm.helper package and a patch to the record manager initialization so that the policy may be configured easily.

          The contract for this policy would be that objects remain in cache until they are no longer in use.  As a consequence, the cache size can grow without limit, though I would expect that a reasonable upper bound would be observed in practice.

          Right now I see two problems with the default jdbm MRU cache policy:  (1) cache eviction is too eager, since objects are evicted from the cache once it reaches its initial capacity; and (2) since objects may be evicted eagerly from the cache, it is possible to have a runtime object for some persistent record, have it flushed from the cache, and then have a second runtime object for the same persistent data created since the original runtime object is no longer in the cache, even though it still exists and is in use by the application.

          The latter is a BIG problem for our application since it breaks the guarentee that there is never more than one runtime object for a given persistent object.  That guarentee is what allows us to use java reference tests, e.g., x == y, to test whether two persistent objects are the same.  This problem does not show up, of course, until you reach capacity on the cache.

          Thanks,

          -bryan

           
          • Kevin Day
            Kevin Day
            2005-07-28

            I'm glad to hear that you are pursuing this.  It's definitely been on my mind as well.  Please let me know if you'd like to exchange design ideas, etc...

            Some thoughts:

            1.  It will probably be a good idea to combine the MRU with the weak reference.  Caching is often extremely useful, even if an object would technically have been removed by the GC.

            I've been thinking about the best way to do this - I'm thinking something along the lines of a two level cache.  MRU is the top level, weak reference is the next.

            When an object is evicted from the MRU, it gets added to the WR cache.  If an object is pulled from cache, it gets added to the top of the MRU, regardless of whether it was pulled from the MRU or the WR.

            2.  Because the objects in the cache are actually the BTree pages, which, in turn, hold references to their value objects, a WR cache implemented at the record manager level may not behave as expected.  It is quite possible for the BTreePage to be evicted from cache while you still maintain a reference to a value object.

            I havne't spent enough time thinking about the correct solution here... you don't really want to hold a reference to the Btreepage in the value object.

            If the BTree didn't contain objects, but instead contained recid values that were used to load from the record manager, then a WR cache would work properly - but you will wind up with poor disk performance (see the other thread in the forum about NIO implementations for a discussion on why this would be).

            It almost seems like we need to cache value objects in the BTree itself instead of in the record manager.

            During restore of a primary BTree page, if would look the primary key up in the BTree's object cache prior to deserialization of a given object.

            This is some really rough thinking right now - I just want to make sure that the entire problem is considered before we start writing code :-)

            I'm eager to hear your thoughts on the above!

            - K

             
            • Bryan Thompson
              Bryan Thompson
              2005-07-28

              Kevin,

              I was also thinking that an MRU policy would still be useful, but I was thinking to migrate the objects to the MRU cache when they were evicted from the WR cache.  MRU cache objects would be "inserted" on eviction from the WRU and roll off the end of the MRU cache if they are not fetched before too many evications of other objects go by.  This almost sounds like a ring-buffer for the MRU cache.  I'm not sure which design (if either) is "right", but your point is well taken.  There may (or may not - this is an empirical question and is probably application specific) be a bias for fetches against persistent objects that had have already been fetched even after the JVM collects the corresponding runtime objects.

              One thing that I have been playing with in our application objects is a small local MRU cache for references resolved from that object.  A similar MRU cache could be placed in front of a btree for application objects resolved against that btree.  This is something that I am planning to do within our object manager for certain well-used btrees.  There is no reason why this could not be done for any btree.  In fact, it still makes sense when the btree would resolve a recid against the record manager since you can just cache the object that would be resolved rather than the recid of that object.

              I tend to hold a reference to well-used btrees rather than letting them get collected.  I could see wrapping a BTree with a cache policy, much like the recman, but perhaps with an optional "Resolver" interface that could be used to cache objects that are being indirected through the btree.

              Also, there are two things that bother me about the MRU cache policy: (1) the hashtable should be initialized to its capacity; and (2) we are coining Long objects all over the place since the Hashtable requires an object (rather than a primitive long) for its key.  It would be nice to get rid of that object allocation overhead.

              -bryan

               
              • Kevin Day
                Kevin Day
                2005-07-28

                I don't think you want to have the WRQ in front.  Remember, when you add the object to the MRU, it will get a reference, but it will no longer be in the WRQ.  When the MRU evicts the object, you will be in danger of violating your A1==A2 requirement.

                Per your comment on holding the reference to the BTree - the BTree does not hold references to the value objects.  The BTreePage holds the reference, and the page is *not* referenced by the BTree itself.

                Per your comment on the current MRU implementation (with hashtable):

                In terms of maxing the capacity up front:  Sure - that's always a good idea with this kind of thing.  But it won't make much difference.  I suspect that the hash table will be at it's final size within a few minutes of running...

                With respect to your comment on Long vs long:  It does seem to be a bit of a performance drain to be continuously creating and destroying Long objects...  I believe that the Jakarta project has a sub-project that has implementations of HashMap that use long's as keys - it may be worth thinking about.

                That said, remember that the key in the BTreePage is already going to be a Long - so the object is already created, really.  The optimization may be better performed by overriding the recmanager methods that accept long so they also accept Long.  That way, the record manager could re-use the Long object that is already created by the BTreePage...

                Just something to think about.

                I don't think it would be a good idea to try to make the BTree implementation use native longs as keys - the existing design is way too elegant - so you are going to have Long objects floating around anyway...  optimizing the cachemanager hashtable to use native longs may not make much of a difference.

                I've actually been thinking quite a bit about a slightly improved BTree implementation.  In my app (and I think this would be an appropriate strategy for many apps), I differentiate between primary key BTrees and secondary key BTrees.

                If we added WRQ caching to the primary BTree implementation, and leave the MRU processing the record manager, I think it might make for a very elegant solution.  In fact, it gives the behavior you described above, without any of the potential pitfuls I described (unless I'm missing something :-)  )

                The object wouldn't come up for eviction untill the BTreePage that references it is evicted from the MRU, so you still effectively get MRU caching behavior.

                The BTreePage would then check it's parent BTree to see if a given key is in the WRQ before performing deserialization.  If it is in the WRQ, it retrieves it and adds it to it's internal list.  If it is not in the WRQ, it creates a new one, then adds it to the WRQ.

                Some other features that would be extremely nice that I'm thinking about:

                1.  A key-aware serializer.  This would add an extra method to the serializer interface, overloading the deserialize() method so it accepts the key in addition to the byte array.  This would allow the deserialize method to populate the created object with data from the key, instead of having to store the key inside the byte array itself (which is just a silly waste of disk space).

                2.  index triggers - I haven't thought this one through all the way, but it would be insanely cool if a BTree could be configured with listeners that get told when a value is being added or removed.  This could be used to keep a primary key BTree in sync with several scondary key BTrees, without having to manually code for every situation.

                The listeners should have an opportunity to approve the change with one callback, then execute the change on a second callback.  The approval is to give a secondary index an opportunity to "just say no" if a key violation would occur.

                I have a bunch of code that keeps indexes consistent, but it feels like I've written the same code over and over again for each business object, and I'm sure that there must be a way to factor out at least some of the behavior.

                3.  Encryption - there is no reason the BTreePage serializer couldn't encrypt it's contents.  I'd be inclined to use a low level implementation (such as Bouncy Castle) instead of the Java CAPI, so it will continue to work with older JVMs, and you won't have the junk overhead of the Java Cryptography API.

                Whew - it looks like I've got my hands full :-)

                - K

                 
                • Bryan Thompson
                  Bryan Thompson
                  2005-07-29

                  Kevin,

                  I'll respond in more detail later.  For the moment two things:

                  - I would like to proceed by small changes initially.

                  - Maybe we should take this to a telcon to talk about what we want.  I think that we are actually pretty well aligned and that speaking directly might clear things up.

                  - I am currently working on a jdbm-related project and I can devote some time to feature improvement during the course of that effort.

                  Also, for the current jdbm maintainers:  I would be happy to do a 1.0 release of jdbm since that seems to be stalled.  I would do this as a rc1 first to verify things and then a 1.0 in a few weeks.  This would be a feature freeze release.  I've done source forge releases before, so this should not be too difficult.  This might also make it easier to start thinking in terms of 2.0 feature development.

                  -bryan

                   
                • Bryan Thompson
                  Bryan Thompson
                  2005-07-29

                  Kevin,

                  The reason that I mentioned holding a reference to the btree was that if you do this, then it is easy to wrap the btree with an object (vs BPage) cache.  This works even if you need to indirect through a recid to an object globally stored in the recman vs in the value[] on the BPage.

                  I've done this sort of index trigger thing in our framework in which the primary data structure is a distributed linked list.  I have it slated to do a varient in which the primary data structure is a clustered index - just like your "primary key index" and in which the secondary indices are value indices.  This is all open source already, but there may be aspects that could be re-factored into jdbm.

                  A related feature would be an Iterator (or modified TupleBrowser) for the BTree that supports concurrent modification, i.e., it registers a transient listener for the BTree and updates its state accordingly when there is a change to the state of the BTree that would effect the traversal ordering.  This is something that I need to solve anyway for our application.  Unlike the iterator/tuple browser, secondary indices would need to register persistent listeners.

                  -bryan

                   
                  • Kevin Day
                    Kevin Day
                    2005-07-29

                    OK - now that I think about it, this is exactly what I do.  I have a BTree factory that caches the top level tree object when it is loaded for the first time.  What I don't do is store the reference to the tree in the value objects created inside the tree - I always grab the trees from the factory when I need them.  That is nitty-gritty detail that probably doesn't matter much.

                    Of course, you are correct that you need to hold references to the BTree in my WRQ strategy.  Otherwise, you could wind up with 2 BTree objects holding different copies of what should be the same object.

                    In terms of loading directly from the record manager, I'm not convinced yet that this is an appropriate strategy for most implementations.  I originally had my app configured to do exactly this, but the performance was terrible. 

                    This may imply that the underlying record manager has some performance problems.  In fact, I'm going to start another thread with my thinking on that...

                    Your idea of a "change safe" tuple browser is definitely good.  I've been able to refactor my code so I don't need that capability in my current application, but there really is no good reason to not have it (outside of the fact that it requires digging into some really low level stuff in the BTree implementation, and will probably require a heck of a lot of testing to ensure that it works properly as the BTree reorganizes itself as records are added and removed...).

                    The interface for this type of browsing that I've always found most useful from a top level application perspective is to be able to choose a particular index, then be able to walk that index forward or backwards (or search for a particular element in the index), making changes as you go.

                    Just had a thought:  If we are using a WRQ, then it should be possible to not have to store the recid in the value object at all.  If the object is going to be deleted, it can be looked up in the WRQ and the recid can be obtained that way.  That may make JDBM significantly more like a transparent object database...

                    Anyway - all of this is still in the very early "noodling around" phase.  I think it's worth continuing the conversation until we start to hone in on the "best" way to do this...

                    Cheers!

                    - K