db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Db-derby Wiki] Update of "DerbyLruCacheManager" by GokulSoundararajan
Date Fri, 21 Jul 2006 22:43:03 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Db-derby Wiki" for change notification.

The following page has been changed by GokulSoundararajan:

   1. '''CLOCK-Pro: an effective improvement of the CLOCK replacement''' - Song Jiang, Feng
Chen, and Xiaodong Zhang [http://www.cs.wm.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf
  == Status/Updates ==
+ === July 21, 2006 ===
+ It's been a long month. I have been trying to figure out how to separate the replacement
policy from the actual {{{CacheManager}}} design and I think I finally have the answer. What
I did was to maintain the cache's metadata separately in accordance to the replacement policy
(an instantiation of an replacement policy is called a ''replacement policy engine''). Whenever
a page is faulted in, we update the engine saying that a page was faulted in. If the engine
is full, then it will remove a page according to the replacement policy. When the {{{CacheManager}}}
wants to do an eviction, it asks the policy engine for ''eviction candidates'' (this is similar
for {{{performWork()}}} as well). From this list, the {{{CacheManager}}} checks each and evicts
the best one that satisfies the {{{CacheManager's}}} constraints like not being kept and not
being dirty.
+ There is some overhead in this approach. On every cache access, we have to update the engine
as well. If the ''engine'' is well implemented, then the overhead is minimized. The second
potential problem is that the engine might have evicted an item which the cache hasn't evicted
(maybe it was kept earlier). Since the engine doesn't have this item, it won't recommend the
item for removal again. This can be fixed by making 
+ {{{ performWork() }}}
+ periodically ask the engine the eviction status of an item by going through the holders
list. This can be adaptive by only running when we are above the {{{maximumSize}}} by some
+ The Replacement Policy is implemented based on this interface:
+ {{{
+ public interface ReplacementPolicy {
+         /* Record cache accesses inside the engine */
+         public void access(Object key, String params);
+         /* Given an item, it returns how evictable this item is
+           * 1.0 => very sure
+           * 0.0 => unsure
+           */
+         public double evictionConfidence(Object key);
+         /* Return a sorted list of evictable items
+          * index(0) => most evictable
+          * index(inf) => least evictable
+          */
+         public Object[] evictableItems(int numOfItems);
+ }
+ }}}
  === June 20, 2006 ===

View raw message