Cache


1   /**
2    * $RCSfile: Cache.java,v $
3    * $Revision: 1.3 $
4    * $Date: 2006/01/07 00:21:06 $
5    *
6    * Copyright (C) 2000 CoolServlets.com. All rights reserved.
7    *
8    * ===================================================================
9    * The Apache Software License, Version 1.1
10   *
11   * Redistribution and use in source and binary forms, with or without
12   * modification, are permitted provided that the following conditions
13   * are met:
14   *
15   * 1. Redistributions of source code must retain the above copyright
16   *    notice, this list of conditions and the following disclaimer.
17   *
18   * 2. Redistributions in binary form must reproduce the above copyright
19   *    notice, this list of conditions and the following disclaimer in
20   *    the documentation and/or other materials provided with the
21   *    distribution.
22   *
23   * 3. The end-user documentation included with the redistribution,
24   *    if any, must include the following acknowledgment:
25   *       "This product includes software developed by
26   *        CoolServlets.com (http://www.Yasna.com)."
27   *    Alternately, this acknowledgment may appear in the software itself,
28   *    if and wherever such third-party acknowledgments normally appear.
29   *
30   * 4. The names "Jive" and "CoolServlets.com" must not be used to
31   *    endorse or promote products derived from this software without
32   *    prior written permission. For written permission, please
33   *    contact webmaster@Yasna.com.
34   *
35   * 5. Products derived from this software may not be called "Jive",
36   *    nor may "Jive" appear in their name, without prior written
37   *    permission of CoolServlets.com.
38   *
39   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
40   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
41   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
42   * DISCLAIMED.  IN NO EVENT SHALL COOLSERVLETS.COM OR
43   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
45   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
46   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
47   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
48   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
49   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50   * SUCH DAMAGE.
51   * ====================================================================
52   *
53   * This software consists of voluntary contributions made by many
54   * individuals on behalf of CoolServlets.com. For more information
55   * on CoolServlets.com, please see <http://www.Yasna.com>.
56   */
57  
58  package com.Yasna.util;
59  
60  import java.util.*;
61  import com.Yasna.util.LinkedList;
62  
63  /**
64   * General purpose cache implementation. It stores objects associated with
65   * unique keys in memory for fast access. All objects added to the cache must
66   * implement the Cacheable interface, which requires objects to know their
67   * size in memory. This restrictions allows the cache to never grow larger
68   * than a specified amount.<p>
69   *
70   * If the cache does grow too large, objects will be removed such that those
71   * that are accessed least frequently are removed first. Because expiration
72   * happens automatically, the cache makes <b>no</b> gaurantee as to how long
73   * an object will remain in cache after it is put in. The cache will return
74   * null if the requested object is not found.<p>
75   *
76   * Optionally, a maximum lifetime for all objects can be specified. In that
77   * case, objects will be deleted from cache after that amount of time, even
78   * if they are frequently accessed. This feature is useful if objects put in
79   * cache represent data that should be periodically refreshed; for example,
80   * information from a database.<p>
81   *
82   * Cache is optimized for fast data access. The getObject() method has 0(n)
83   * performance regardless of cache size. The other cache operations also
84   * perform quite fast.<p>
85   *
86   * Cache objects are thread safe.<p>
87   *
88   * The algorithm for cache is as follows: a HashMap is maintained for fast
89   * object lookup. Two linked lists are maintained: one keeps objects in the
90   * order they are accessed from cache, the other keeps objects in the order
91   * they were originally added to cache. When objects are added to cache, they
92   * are first wrapped by a CacheObject which maintains the following pieces
93   * of information:<ul>
94   *    <li> The size of the object (in bytes).
95   *    <li> A pointer to the node in the linked list that maintains accessed
96   *         order for the object. Keeping a reference to the node lets us avoid
97   *         linear scans of the linked list.
98   *    <li> A pointer to the node in the linked list that maintains the age
99   *         of the object in cache. Keeping a reference to the node lets us avoid
100  *         linear scans of the linked list.</ul>
101  *
102  * To get an object from cache, a hash lookup is performed to get a reference
103  * to the CacheObject that wraps the real object we are looking for.
104  * The object is subsequently moved to the front of the accessed linked list
105  * and any necessary cache cleanups are performed. Cache deletion and expiration
106  * is performed as needed.
107  *
108  * @see Cacheable
109  */
110 public class Cache implements Cacheable {
111 
112     /**
113      * One of the major potential bottlenecks of the cache is performing
114      * System.currentTimeMillis() for every cache get operation. Instead,
115      * we maintain a global timestamp that gets updated once a second. This
116      * means that cache expirations can be no more than one second accurate.
117      */
118     protected static long currentTime = System.currentTimeMillis();
119 
120     /**
121      * A cache timer updates the current time once a second in a seperate
122      * thread.
123      */
124     protected static CacheTimer timer = new CacheTimer(1000L);
125 
126     /**
127      * Maintains the hash of cached objects. Hashing provides the best
128      * performance for fast lookups.
129      */
130     protected HashMap cachedObjectsHash;
131 
132     /**
133      * Linked list to maintain order that cache objects are accessed
134      * in, most used to least used.
135      */
136     protected LinkedList lastAccessedList;
137 
138     /**
139      * Linked list to maintain time that cache objects were initially added
140      * to the cache, most recently added to oldest added.
141      */
142     protected LinkedList ageList;
143 
144    /**
145     * Maximum size in bytes that the cache can grow to. Default
146     * maximum size is 128 K.
147     */
148     protected int maxSize =  128 * 1024;
149 
150     /**
151      * Maintains the current size of the cache in bytes.
152      */
153     protected int size = 0;
154 
155     /**
156      * Maximum length of time objects can exist in cache before expiring.
157      * Default is that objects have no maximum lifetime.
158      */
159     protected long maxLifetime = -1;
160 
161     /**
162      * Maintain the number of cache hits and misses. A cache hit occurs every
163      * time the get method is called and the cache contains the requested
164      * object. A cache miss represents the opposite occurence.<p>
165      *
166      * Keeping track of cache hits and misses lets one measure how efficient
167      * the cache is; the higher the percentage of hits, the more efficient.
168      */
169     protected long cacheHits, cacheMisses = 0L;
170 
171     /**
172      * Create a new cache with default values. Default cache size is 128K with
173      * no maximum lifetime.
174      */
175     public Cache() {
176         //Our primary data structure is a hash map. The default capacity of 11
177         //is too small in almost all cases, so we set it bigger.
178         cachedObjectsHash = new HashMap(103);
179 
180         lastAccessedList = new LinkedList();
181         ageList = new LinkedList();
182     }
183 
184     /**
185      * Create a new cache and specify the maximum size for the cache in bytes.
186      * Items added to the cache will have no maximum lifetime.
187      *
188      * @param maxSize the maximum size of the cache in bytes.
189      */
190     public Cache(int maxSize) {
191         this();
192         this.maxSize = maxSize;
193     }
194 
195     /**
196      * Create a new cache and specify the maximum lifetime of objects. The
197      * time should be specified in milleseconds. The minimum lifetime of any
198      * cache object is 1000 milleseconds (1 second). Additionally, cache
199      * expirations have a 1000 millesecond resolution, which means that all
200      * objects are guaranteed to be expired within 1000 milliseconds of their
201      * maximum lifetime.
202      *
203      * @param maxLifetime the maximum amount of time objects can exist in
204      *    cache before being deleted.
205      */
206     public Cache(long maxLifetime) {
207         this();
208         this.maxLifetime = maxLifetime;
209     }
210 
211     /**
212      * Create a new cache and specify the maximum size of for the cache in
213      * bytes, and the maximum lifetime of objects.
214      *
215      * @param maxSize the maximum size of the cache in bytes.
216      * @param maxLifetime the maximum amount of time objects can exist in
217      *    cache before being deleted.
218      */
219     public Cache(int maxSize, long maxLifetime) {
220         this();
221         this.maxSize = maxSize;
222         this.maxLifetime = maxLifetime;
223     }
224 
225     /**
226      * Returns the current size of the cache in bytes.
227      *
228      * @return the size of the cache in bytes.
229      */
230     public int getSize() {
231         return size;
232     }
233 
234     /**
235      * Returns the maximum size of the cache in bytes. If the cache grows too
236      * large, the least frequently used items will automatically be deleted so
237      * that the cache size doesn't exceed the maximum.
238      *
239      * @return the maximum size of the cache in bytes.
240      */
241     public int getMaxSize() {
242         return maxSize;
243     }
244 
245     /**
246      * Sets the maximum size of the cache in bytes. If the cache grows too
247      * large, the least frequently used items will automatically be deleted so
248      * that the cache size doesn't exceed the maximum.
249      *
250      * @param maxSize the maximum size of the cache in bytes.
251      */
252     public void setMaxSize(int maxSize) {
253         this.maxSize = maxSize;
254         //It's possible that the new max size is smaller than our current cache
255         //size. If so, we need to delete infrequently used items.
256         cullCache();
257     }
258 
259     /**
260      * Returns the number of objects in the cache.
261      *
262      * @return the number of objects in the cache.
263      */
264     public synchronized int getNumElements() {
265         return cachedObjectsHash.size();
266     }
267 
268     /**
269      * Adds a new Cacheable object to the cache. The key must be unique.
270      *
271      * @param key a unique key for the object being put into cache.
272      * @param object the Cacheable object to put into cache.
273      */
274     public synchronized void add(Object   key, Cacheable object) {
275         //DEBUG
276         //System.err.println("Adding object with key " + key + " to hash " + this);
277 
278         //Don't add an object with the same key multiple times.
279         if (cachedObjectsHash.containsKey(key)) {
280             return;
281         }
282         int objectSize = object.getSize();
283         //If the object is bigger than the entire cache, simply don't add it.
284         if (objectSize > maxSize * .90) {
285             return;
286         }
287         size += objectSize;
288         CacheObject cacheObject = new CacheObject(object, objectSize);
289         cachedObjectsHash.put(key, cacheObject);
290         //Make an entry into the cache order list.
291         LinkedListNode lastAccessedNode = lastAccessedList.addFirst(key);
292         //Store the cache order list entry so that we can get back to it
293         //during later lookups.
294         cacheObject.lastAccessedListNode = lastAccessedNode;
295         //Add the object to the age list
296         LinkedListNode ageNode = ageList.addFirst(key);
297         //We make an explicit call to currentTimeMillis() so that total accuracy
298         //of lifetime calculations is better than one second.
299         ageNode.timestamp = System.currentTimeMillis();
300         cacheObject.ageListNode = ageNode;
301 
302         //If cache is too full, remove least used cache entries until it is
303         //not too full.
304         cullCache();
305     }
306 
307     /**
308      * Gets an object from cache. This method will return null under two
309      * conditions:<ul>
310      *    <li>The object referenced by the key was never added to cache.
311      *    <li>The object referenced by the key has expired from cache.</ul>
312      *
313      * @param key the unique key of the object to get.
314      * @return the Cacheable object corresponding to unique key.
315      */
316     public synchronized Cacheable get(Object   key) {
317         //First, clear all entries that have been in cache longer than the
318         //maximum defined age.
319         deleteExpiredEntries();
320 
321         CacheObject cacheObject = (CacheObject)cachedObjectsHash.get(key);
322         if (cacheObject == null) {
323             //The object didn't exist in cache, so increment cache misses.
324             cacheMisses++;
325             return null;
326         }
327 
328         //The object exists in cache, so increment cache hits.
329         cacheHits++;
330 
331         //Remove the object from it's current place in the cache order list,
332         //and re-insert it at the front of the list.
333         cacheObject.lastAccessedListNode.remove();
334         lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
335 
336         return cacheObject.object;
337     }
338 
339     /**
340      * Removes an object from cache.
341      *
342      * @param key the unique key of the object to remove.
343      */
344     public synchronized void remove(Object   key) {
345         //DEBUG
346         //System.err.println("Removing object with key: " + key + " from hash " + this);
347 
348         CacheObject cacheObject = (CacheObject)cachedObjectsHash.get(key);
349         //If the object is not in cache, stop trying to remove it.
350         if (cacheObject == null) {
351             return;
352         }
353         //remove from the hash map
354         cachedObjectsHash.remove(key);
355         //remove from the cache order list
356         cacheObject.lastAccessedListNode.remove();
357         cacheObject.ageListNode.remove();
358         //remove references to linked list nodes
359         cacheObject.ageListNode = null;
360         cacheObject.lastAccessedListNode = null;
361         //removed the object, so subtract its size from the total.
362         size -= cacheObject.size;
363     }
364 
365     /**
366      * Clears the cache of all objects. The size of the cache is reset to 0.
367      */
368     public synchronized void clear() {
369         //DEBUG
370         //System.err.println("Clearing cache " + this);
371 
372         Object   [] keys = cachedObjectsHash.keySet().toArray();
373         for (int i=0; i<keys.length; i++) {
374             remove(keys[i]);
375         }
376 
377         //Now, reset all containers.
378         cachedObjectsHash.clear();
379         cachedObjectsHash = new HashMap(103);
380         lastAccessedList.clear();
381         lastAccessedList = new LinkedList();
382         ageList.clear();
383         ageList = new LinkedList();
384 
385         size = 0;
386         cacheHits = 0;
387         cacheMisses = 0;
388     }
389 
390     /**
391      * Returns a collection view of the values contained in the cache.
392      * The Collection is unmodifiable to prevent cache integrity issues.
393      *
394      * @return a Collection of the cache entries.
395      */
396     public Collection values() {
397         return Collections.unmodifiableCollection(cachedObjectsHash.values());
398     }
399 
400     /**
401      * Returns the number of cache hits. A cache hit occurs every
402      * time the get method is called and the cache contains the requested
403      * object.<p>
404      *
405      * Keeping track of cache hits and misses lets one measure how efficient
406      * the cache is; the higher the percentage of hits, the more efficient.
407      *
408      * @return the number of cache hits.
409      */
410     public long getCacheHits() {
411         return cacheHits;
412     }
413 
414     /**
415      * Returns the number of cache misses. A cache miss occurs every
416      * time the get method is called and the cache does not contain the
417      * requested object.<p>
418      *
419      * Keeping track of cache hits and misses lets one measure how efficient
420      * the cache is; the higher the percentage of hits, the more efficient.
421      *
422      * @return the number of cache hits.
423      */
424     public long getCacheMisses() {
425         return cacheMisses;
426     }
427 
428     /**
429      * Clears all entries out of cache where the entries are older than the
430      * maximum defined age.
431      */
432     private final void deleteExpiredEntries() {
433         //Check if expiration is turned on.
434         if (maxLifetime <= 0) {
435             return;
436         }
437 
438         //Remove all old entries. To do this, we remove objects from the end
439         //of the linked list until they are no longer too old. We get to avoid
440         //any hash lookups or looking at any more objects than is strictly
441         //neccessary.
442         LinkedListNode node = ageList.getLast();
443         //If there are no entries in the age list, return.
444         if (node == null) {
445             return;
446         }
447 
448         //Determine the expireTime, which is the moment in time that elements
449         //should expire from cache. Then, we can do an easy to check to see
450         //if the expire time is greater than the expire time.
451         long expireTime = currentTime - maxLifetime;
452 
453         while(expireTime > node.timestamp) {
454             //DEBUG
455             //System.err.println("Object with key " + node.object + " expired.");
456 
457             //Remove the object
458             remove(node.object);
459 
460             //Get the next node.
461             node = ageList.getLast();
462             //If there are no more entries in the age list, return.
463             if (node == null) {
464                 return;
465             }
466         }
467     }
468 
469     /**
470      * Removes objects from cache if the cache is too full. "Too full" is
471      * defined as within 3% of the maximum cache size. Whenever the cache is
472      * is too big, the least frequently used elements are deleted until the
473      * cache is at least 10% empty.
474      */
475     private final void cullCache() {
476         //See if the cache size is within 3% of being too big. If so, clean out
477         //cache until it's 10% free.
478         if (size >= maxSize * .97) {
479             //First, delete any old entries to see how much memory that frees.
480             deleteExpiredEntries();
481             int desiredSize = (int)(maxSize * .90);
482             while (size > desiredSize) {
483                 //Get the key and invoke the remove method on it.
484                 remove(lastAccessedList.getLast().object);
485             }
486         }
487     }
488 }
489 
490
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags