db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kahat...@apache.org
Subject svn commit: r601680 - in /db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache: BackgroundCleaner.java ClockPolicy.java ConcurrentCache.java ReplacementPolicy.java
Date Thu, 06 Dec 2007 10:13:57 GMT
Author: kahatlen
Date: Thu Dec  6 02:13:57 2007
New Revision: 601680

URL: http://svn.apache.org/viewvc?rev=601680&view=rev
Log:
DERBY-2911 (partial) Implement a buffer manager using java.util.concurrent classes

Add functionality to shrink the cache when it has grown bigger than
its specified maximum size.

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/BackgroundCleaner.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ReplacementPolicy.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/BackgroundCleaner.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/BackgroundCleaner.java?rev=601680&r1=601679&r2=601680&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/BackgroundCleaner.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/BackgroundCleaner.java
Thu Dec  6 02:13:57 2007
@@ -54,6 +54,12 @@
     /** A queue of cache entries that need to be cleaned. */
     private final ArrayBlockingQueue<CacheEntry> queue;
 
+    /**
+     * Flag which tells whether the cleaner should try to shrink the cache
+     * the next time it wakes up.
+     */
+    private volatile boolean shrink;
+
     /** The cache manager owning this cleaner. */
     private final ConcurrentCache cacheManager;
 
@@ -83,7 +89,7 @@
      * <code>false</code> if the background cleaner can't clean the entry (its
      * queue is full)
      */
-    boolean scheduleWork(CacheEntry entry) {
+    boolean scheduleClean(CacheEntry entry) {
         final boolean queued = queue.offer(entry);
         if (queued) {
             requestService();
@@ -92,6 +98,15 @@
     }
 
     /**
+     * Request that the cleaner tries to shrink the cache the next time it
+     * wakes up.
+     */
+    void scheduleShrink() {
+        shrink = true;
+        requestService();
+    }
+
+    /**
      * Notify the daemon service that the cleaner needs to be serviced.
      */
     private void requestService() {
@@ -126,12 +141,20 @@
     public int performWork(ContextManager context) throws StandardException {
         // allow others to schedule more work
         scheduled.set(false);
+
+        // First, try to shrink the cache if requested.
+        if (shrink) {
+            shrink = false;
+            cacheManager.getReplacementPolicy().doShrink();
+        }
+
+        // See if there are objects waiting to be cleaned.
         CacheEntry e = queue.poll();
         if (e != null) {
             try {
                 cacheManager.cleanEntry(e);
             } finally {
-                if (!queue.isEmpty()) {
+                if (!queue.isEmpty() || shrink) {
                     // We have more work in the queue. Request service again.
                     requestService();
                 }

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java?rev=601680&r1=601679&r2=601680&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
Thu Dec  6 02:13:57 2007
@@ -22,6 +22,7 @@
 package org.apache.derby.impl.services.cache;
 
 import java.util.ArrayList;
+import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicInteger;
 import org.apache.derby.iapi.error.StandardException;
 import org.apache.derby.iapi.services.cache.Cacheable;
@@ -96,6 +97,13 @@
     private final AtomicInteger freeEntries = new AtomicInteger();
 
     /**
+     * Tells whether there currently is a thread in the <code>doShrink()</code>
+     * or <code>trimToSize()</code> methods. If this variable is
+     * <code>true</code> a call to any one of those methods will be a no-op.
+     */
+    private final AtomicBoolean isShrinking = new AtomicBoolean();
+
+    /**
      * Create a new <code>ClockPolicy</code> instance.
      *
      * @param cacheManager the cache manager that requests this policy
@@ -117,26 +125,35 @@
      */
     public Callback insertEntry(CacheEntry entry) throws StandardException {
 
-        final boolean isFull;
+        final int size;
         synchronized (clock) {
-            if (clock.size() < maxSize) {
+            size = clock.size();
+            if (size < maxSize) {
                 if (freeEntries.get() == 0) {
                     // We have not reached the maximum size yet, and there's no
                     // free entry to reuse. Make room by growing.
                     return grow(entry);
                 }
-                // The cache is not full, but there are free entries that can
-                // be reused.
-                isFull = false;
+            }
+        }
+
+        if (size > maxSize) {
+            // Maximum size is exceeded. Shrink the clock in the background
+            // cleaner, if we have one; otherwise, shrink it in the current
+            // thread.
+            BackgroundCleaner cleaner = cacheManager.getBackgroundCleaner();
+            if (cleaner != null) {
+                cleaner.scheduleShrink();
             } else {
-                // The cache is full, so we'll need to rotate the clock hand
-                // and evict an object.
-                isFull = true;
+                doShrink();
             }
         }
 
-        // rotate clock hand (look at up to 20% of the cache)
-        Holder h = rotateClock(entry, (float) 0.2, isFull);
+        // Rotate the clock hand (look at up to 20% of the cache) and try to
+        // find free space for the entry. Only allow evictions if the cache
+        // has reached its maximum size. Otherwise, we only look for invalid
+        // entries and rather grow the cache than evict valid entries.
+        Holder h = rotateClock(entry, (float) 0.2, size >= maxSize);
         if (h != null) {
             return h;
         }
@@ -181,6 +198,14 @@
          */
         private Cacheable freedCacheable;
 
+        /**
+         * Flag which tells whether this holder has been evicted from the
+         * clock. If it has been evicted, it can't be reused when a new entry
+         * is inserted. Only the owner of this holder's monitor is allowed to
+         * access this variable.
+         */
+        private boolean evicted;
+
         Holder(CacheEntry e) {
             entry = e;
             e.setCallback(this);
@@ -218,10 +243,11 @@
          * @param e the entry to associate the holder with (it must be locked
          * by the current thread)
          * @return <code>true</code> if the holder has been associated with the
-         * specified entry, <code>false</code> if someone else has taken it
+         * specified entry, <code>false</code> if someone else has taken it or
+         * the holder has been evicted from the clock
          */
         synchronized boolean takeIfFree(CacheEntry e) {
-            if (entry == null) {
+            if (entry == null && !evicted) {
                 // the holder is free - take it!
                 int free = freeEntries.decrementAndGet();
                 if (SanityManager.DEBUG) {
@@ -260,6 +286,49 @@
             e.setCacheable(entry.getCacheable());
             entry = e;
         }
+
+        /**
+         * Evict this holder from the clock if it is not associated with an
+         * entry.
+         *
+         * @return <code>true</code> if the holder was successfully evicted,
+         * <code>false</code> otherwise
+         */
+        synchronized boolean evictIfFree() {
+            if (entry == null && !evicted) {
+                int free = freeEntries.decrementAndGet();
+                if (SanityManager.DEBUG) {
+                    SanityManager.ASSERT(
+                        free >= 0, "freeEntries is negative: " + free);
+                }
+                evicted = true;
+                return true;
+            }
+            return false;
+        }
+
+        /**
+         * Mark this holder as evicted from the clock, effectively preventing
+         * reuse of the holder. Calling thread must have locked the holder's
+         * entry.
+         */
+        synchronized void setEvicted() {
+            if (SanityManager.DEBUG) {
+                SanityManager.ASSERT(!evicted, "Already evicted");
+            }
+            evicted = true;
+            entry = null;
+        }
+
+        /**
+         * Check whether this holder has been evicted from the clock.
+         *
+         * @return <code>true</code> if it has been evicted, <code>false</code>
+         * otherwise
+         */
+        synchronized boolean isEvicted() {
+            return evicted;
+        }
     }
 
     /**
@@ -370,7 +439,10 @@
                 if (SanityManager.DEBUG) {
                     // At this point the entry must be valid. Otherwise, it
                     // would have been removed from the Holder.
-                    SanityManager.ASSERT(e.isValid());
+                    SanityManager.ASSERT(e.isValid(),
+                            "Holder contains invalid entry");
+                    SanityManager.ASSERT(!h.isEvicted(),
+                            "Trying to reuse an evicted holder");
                 }
 
                 if (e.isKept()) {
@@ -397,7 +469,7 @@
 
                 // Ask the background cleaner to clean the entry.
                 BackgroundCleaner cleaner = cacheManager.getBackgroundCleaner();
-                if (cleaner != null && cleaner.scheduleWork(e)) {
+                if (cleaner != null && cleaner.scheduleClean(e)) {
                     // Successfully scheduled the clean operation. Move on to
                     // the next entry.
                     continue;
@@ -420,5 +492,249 @@
         }
 
         return null;
+    }
+
+    /**
+     * Remove the holder at the given clock position.
+     *
+     * @param pos position of the holder
+     * @param h the holder to remove
+     */
+    private void removeHolder(int pos, Holder h) {
+        synchronized (clock) {
+            Holder removed = clock.remove(pos);
+            if (SanityManager.DEBUG) {
+                SanityManager.ASSERT(removed == h, "Wrong Holder removed");
+            }
+        }
+    }
+
+    /**
+     * Try to shrink the clock if it's larger than its maximum size.
+     */
+    public void doShrink() {
+        // If we're already performing a shrink, ignore this request. We'll get
+        // a new call later by someone else if the current shrink operation is
+        // not enough.
+        if (isShrinking.compareAndSet(false, true)) {
+            try {
+                if (shrinkMe()) {
+                    // the clock shrunk, try to trim it too
+                    trimMe();
+                }
+            } finally {
+                isShrinking.set(false);
+            }
+        }
+    }
+
+    /**
+     * Try to reduce the size of the clock as much as possible by removing
+     * invalid entries. In most cases, this method will do nothing.
+     *
+     * @see #trimMe()
+     */
+    public void trimToSize() {
+        // ignore this request if we're already performing trim or shrink
+        if (isShrinking.compareAndSet(false, true)) {
+            try {
+                trimMe();
+            } finally {
+                isShrinking.set(false);
+            }
+        }
+    }
+
+    /**
+     * Perform the shrinking of the clock. This method should only be called
+     * by a single thread at a time, and should not be called concurrently
+     * with <code>trimMe()</code>.
+     *
+     * @return <code>true</code> if the
+     */
+    private boolean shrinkMe() {
+
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(isShrinking.get(),
+                    "Called shrinkMe() without ensuring exclusive access");
+        }
+
+        // Look at 10% of the cache to find candidates for shrinking
+        int maxLooks = Math.max(1, maxSize / 10);
+
+        // Since we don't scan the entire cache, start at the clock hand so
+        // that we don't always scan the first 10% of the cache.
+        int pos;
+        synchronized (clock) {
+            pos = hand;
+        }
+
+        boolean shrunk = false;
+
+        while (maxLooks-- > 0) {
+
+            final Holder h;
+            final int size;
+
+            // The index of the holder we're looking at. Since no one else than
+            // us can remove elements from the clock while we're in this
+            // method, and new elements will be added at the end of the list,
+            // the index for a holder does not change until we remove it.
+            final int index;
+
+            synchronized (clock) {
+                size = clock.size();
+                if (pos >= size) {
+                    pos = 0;
+                }
+                index = pos++;
+                h = clock.get(index);
+            }
+
+            // No need to shrink if the size isn't greater than maxSize.
+            if (size <= maxSize) {
+                break;
+            }
+
+            final CacheEntry e = h.getEntry();
+
+            if (e == null) {
+                // The holder does not hold an entry. Try to remove it.
+                if (h.evictIfFree()) {
+                    removeHolder(index, h);
+                    shrunk = true;
+                    // move position back because of the removal so that we
+                    // don't skip one clock element
+                    pos = index;
+                }
+                // Either the holder was evicted, or someone else took it
+                // before we could evict it. In either case, we should move on
+                // to the next holder.
+                continue;
+            }
+
+            e.lock();
+            try {
+                if (h.getEntry() != e) {
+                    // Entry got evicted before we got the lock. Move on.
+                    continue;
+                }
+
+                if (SanityManager.DEBUG) {
+                    // At this point the entry must be valid. Otherwise, it
+                    // would have been removed from the Holder.
+                    SanityManager.ASSERT(e.isValid(),
+                            "Holder contains invalid entry");
+                    SanityManager.ASSERT(!h.isEvicted(),
+                            "Trying to evict already evicted holder");
+                }
+
+                if (e.isKept() || h.recentlyUsed) {
+                    // Don't evict entries currently in use or recently used.
+                    continue;
+                }
+
+                final Cacheable c = e.getCacheable();
+                if (c.isDirty()) {
+                    // Don't evict dirty entries.
+                    continue;
+                }
+
+                // mark as evicted to prevent reuse
+                h.setEvicted();
+
+                // remove from cache manager
+                cacheManager.evictEntry(c.getIdentity());
+
+                // remove from clock
+                removeHolder(index, h);
+
+                // move position back because of the removal so that we don't
+                // skip one clock element
+                pos = index;
+
+                shrunk = true;
+
+            } finally {
+                e.unlock();
+            }
+        }
+
+        return shrunk;
+    }
+
+    /**
+     * The number of times <code>trimMe()</code> has been called since the last
+     * time <code>trimMe()</code> tried to do some real work. This variable is
+     * used by <code>trimMe()</code> to decide whether it's about time to
+     * actually do something.
+     */
+    private int trimRequests;
+
+    /**
+     * Perform the trimming of the clock. This method should only be called by
+     * a single thread at a time, and should not be called concurrently with
+     * <code>shrinkMe()</code>.
+     *
+     * This method will not do anything unless it has been called a substantial
+     * number of times. Also, it won't do anything if less than 25% of the
+     * clock entries are unused.
+     */
+    private void trimMe() {
+
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(isShrinking.get(),
+                    "Called trimMe() without ensuring exclusive access");
+        }
+
+        // Only trim the clock occasionally, as it's an expensive operation.
+        if (++trimRequests < maxSize / 8) {
+            return;
+        }
+        trimRequests = 0;
+
+        // Get the current size of the clock.
+        final int size;
+        synchronized (clock) {
+            size = clock.size();
+        }
+
+        // no need to trim a small clock
+        if (size < 32) {
+            return;
+        }
+
+        final int unused = freeEntries.get();
+
+        if (unused < size / 4) {
+            // don't trim unless more than 25% of the entries are unused
+            return;
+        }
+
+        // We still want 10% unused entries as a pool for new objects.
+        final int minUnused = (size - unused) / 10;
+
+        // Search for unused entries from the end since it's cheaper to remove
+        // elements near the end of an ArrayList. Since no one else can shrink
+        // the cache while we are in this method, we know that the size of the
+        // clock still must be the same as or greater than the size variable,
+        // so it's OK to search from position (size-1).
+        for (int i = size - 1; i >= 0 && freeEntries.get() > minUnused; i--)
{
+            final Holder h;
+            synchronized (clock) {
+                h = clock.get(i);
+            }
+            // Index will be stable since no one else is allowed to remove
+            // elements from the list, and new elements will be appended at the
+            // end of the list.
+            if (h.evictIfFree()) {
+                removeHolder(i, h);
+            }
+        }
+
+        // Finally, trim the underlying array.
+        synchronized (clock) {
+            clock.trimToSize();
+        }
     }
 }

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java?rev=601680&r1=601679&r2=601680&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java
Thu Dec  6 02:13:57 2007
@@ -93,6 +93,15 @@
     }
 
     /**
+     * Return the <code>ReplacementPolicy</code> instance for this cache.
+     *
+     * @return replacement policy
+     */
+    ReplacementPolicy getReplacementPolicy() {
+        return replacementPolicy;
+    }
+
+    /**
      * Get the entry associated with the specified key from the cache. If the
      * entry does not exist, insert an empty one and return it. The returned
      * entry is always locked for exclusive access by the current thread, but
@@ -500,6 +509,7 @@
      * Remove all objects that are not kept and not dirty.
      */
     public void ageOut() {
+        boolean shrunk = false;
         for (CacheEntry entry : cache.values()) {
             entry.lock();
             try {
@@ -510,12 +520,16 @@
                     // to remove it. If c is dirty, we can't remove it yet.
                     if (c != null && !c.isDirty()) {
                         removeEntry(c.getIdentity());
+                        shrunk = true;
                     }
                 }
             } finally {
                 entry.unlock();
             }
         }
+        if (shrunk) {
+            replacementPolicy.trimToSize();
+        }
     }
 
     /**
@@ -561,6 +575,7 @@
      */
     public boolean discard(Matchable partialKey) {
         boolean allRemoved = true;
+        boolean shrunk = false;
         for (CacheEntry entry : cache.values()) {
             entry.lock();
             try {
@@ -579,9 +594,13 @@
                     continue;
                 }
                 removeEntry(c.getIdentity());
+                shrunk = true;
             } finally {
                 entry.unlock();
             }
+        }
+        if (shrunk) {
+            replacementPolicy.trimToSize();
         }
         return allRemoved;
     }

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ReplacementPolicy.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ReplacementPolicy.java?rev=601680&r1=601679&r2=601680&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ReplacementPolicy.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ReplacementPolicy.java
Thu Dec  6 02:13:57 2007
@@ -47,6 +47,21 @@
     Callback insertEntry(CacheEntry entry) throws StandardException;
 
     /**
+     * Try to shrink the cache if it has exceeded its maximum size. It is not
+     * guaranteed that the cache will actually shrink.
+     */
+    void doShrink();
+
+    /**
+     * Try to reduce the size of the cache as much as possible by removing
+     * invalid entries. Depending on the underlying data structure, this might
+     * be a very expensive operation. The implementations are therefore allowed
+     * to ignore calls to this method when they think the cost outweighs the
+     * benefit.
+     */
+    void trimToSize();
+
+    /**
      * The interface for the callback objects that <code>ConcurrentCache</code>
      * uses to notify the replacement algorithm about events such as look-ups
      * and removals. Each <code>Callback</code> object is associated with a



Mime
View raw message