Cache


1   /**
2    * $RCSfile: Cache.java,v $
3    * $Revision: 1.2 $
4    * $Date: 2004/10/21 07:28:12 $
5    *
6    * Copyright (C) 2004 Jive Software. All rights reserved.
7    *
8    * This software is published under the terms of the GNU Public License (GPL),
9    * a copy of which is included in this distribution.
10   */
11  
12  package org.jivesoftware.util;
13  
14  import java.io.IOException  ;
15  import java.io.ObjectOutputStream  ;
16  import java.io.OutputStream  ;
17  import java.util.*;
18  
19  /**
20   * Default, non-distributed implementation of the Cache interface.
21   * The algorithm for cache is as follows: a HashMap is maintained for fast
22   * object lookup. Two linked lists are maintained: one keeps objects in the
23   * order they are accessed from cache, the other keeps objects in the order
24   * they were originally added to cache. When objects are added to cache, they
25   * are first wrapped by a CacheObject which maintains the following pieces
26   * of information:<ul>
27   *
28   * <li> The size of the object (in bytes).
29   * <li> A pointer to the node in the linked list that maintains accessed
30   * order for the object. Keeping a reference to the node lets us avoid
31   * linear scans of the linked list.
32   * <li> A pointer to the node in the linked list that maintains the age
33   * of the object in cache. Keeping a reference to the node lets us avoid
34   * linear scans of the linked list.</ul><p>
35   *
36   * To get an object from cache, a hash lookup is performed to get a reference
37   * to the CacheObject that wraps the real object we are looking for.
38   * The object is subsequently moved to the front of the accessed linked list
39   * and any necessary cache cleanups are performed. Cache deletion and expiration
40   * is performed as needed.
41   *
42   * @author Matt Tucker
43   */
44  public class Cache {
45  
46      /**
47       * The map the keys and values are stored in.
48       */
49      protected Map map;
50  
51      /**
52       * Linked list to maintain order that cache objects are accessed
53       * in, most used to least used.
54       */
55      protected org.jivesoftware.util.LinkedList lastAccessedList;
56  
57      /**
58       * Linked list to maintain time that cache objects were initially added
59       * to the cache, most recently added to oldest added.
60       */
61      protected LinkedList ageList;
62  
63      /**
64       * Maximum size in bytes that the cache can grow to.
65       */
66      private int maxCacheSize;
67  
68      /**
69       * Maintains the current size of the cache in bytes.
70       */
71      private int cacheSize = 0;
72  
73      /**
74       * Maximum length of time objects can exist in cache before expiring.
75       */
76      protected long maxLifetime;
77  
78      /**
79       * Maintain the number of cache hits and misses. A cache hit occurs every
80       * time the get method is called and the cache contains the requested
81       * object. A cache miss represents the opposite occurence.<p>
82       *
83       * Keeping track of cache hits and misses lets one measure how efficient
84       * the cache is; the higher the percentage of hits, the more efficient.
85       */
86      protected long cacheHits, cacheMisses = 0L;
87  
88      /**
89       * The name of the cache.
90       */
91      private String   name;
92  
93      /**
94       * Create a new cache and specify the maximum size of for the cache in
95       * bytes, and the maximum lifetime of objects.
96       *
97       * @param name a name for the cache.
98       * @param maxSize the maximum size of the cache in bytes. -1 means the cache
99       *      has no max size.
100      * @param maxLifetime the maximum amount of time objects can exist in
101      *      cache before being deleted. -1 means objects never expire.
102      */
103     public Cache(String   name, int maxSize, long maxLifetime) {
104         this.name = name;
105         this.maxCacheSize = maxSize;
106         this.maxLifetime = maxLifetime;
107 
108         // Our primary data structure is a HashMap. The default capacity of 11
109         // is too small in almost all cases, so we set it bigger.
110         map = new HashMap(103);
111 
112         lastAccessedList = new LinkedList();
113         ageList = new LinkedList();
114     }
115 
116     public synchronized Object   put(Object   key, Object   value) {
117         // Delete an old entry if it exists.
118         remove(key);
119 
120         int objectSize = calculateSize(value);
121 
122         // If the object is bigger than the entire cache, simply don't add it.
123         if (maxCacheSize > 0 && objectSize > maxCacheSize * .90) {
124             Log.warn("Cache: " + name + " -- object with key " + key +
125                     " is too large to fit in cache. Size is " + objectSize);
126             return value;
127         }
128         cacheSize += objectSize;
129         CacheObject cacheObject = new CacheObject(value, objectSize);
130         map.put(key, cacheObject);
131         // Make an entry into the cache order list.
132         LinkedListNode lastAccessedNode = lastAccessedList.addFirst(key);
133         // Store the cache order list entry so that we can get back to it
134         // during later lookups.
135         cacheObject.lastAccessedListNode = lastAccessedNode;
136         // Add the object to the age list
137         LinkedListNode ageNode = ageList.addFirst(key);
138         // We make an explicit call to currentTimeMillis() so that total accuracy
139         // of lifetime calculations is better than one second.
140         ageNode.timestamp = System.currentTimeMillis();
141         cacheObject.ageListNode = ageNode;
142 
143         // If cache is too full, remove least used cache entries until it is
144         // not too full.
145         cullCache();
146 
147         return value;
148     }
149 
150     public synchronized Object   get(Object   key) {
151         // First, clear all entries that have been in cache longer than the
152         // maximum defined age.
153         deleteExpiredEntries();
154 
155         CacheObject cacheObject = (CacheObject)map.get(key);
156         if (cacheObject == null) {
157             // The object didn't exist in cache, so increment cache misses.
158             cacheMisses++;
159             return null;
160         }
161 
162         // The object exists in cache, so increment cache hits. Also, increment
163         // the object's read count.
164         cacheHits++;
165         cacheObject.readCount++;
166 
167         // Remove the object from it's current place in the cache order list,
168         // and re-insert it at the front of the list.
169         cacheObject.lastAccessedListNode.remove();
170         lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
171 
172         return cacheObject.object;
173     }
174 
175     public synchronized Object   remove(Object   key) {
176         CacheObject cacheObject = (CacheObject)map.get(key);
177         // If the object is not in cache, stop trying to remove it.
178         if (cacheObject == null) {
179             return null;
180         }
181         // remove from the hash map
182         map.remove(key);
183         // remove from the cache order list
184         cacheObject.lastAccessedListNode.remove();
185         cacheObject.ageListNode.remove();
186         // remove references to linked list nodes
187         cacheObject.ageListNode = null;
188         cacheObject.lastAccessedListNode = null;
189         // removed the object, so subtract its size from the total.
190         cacheSize -= cacheObject.size;
191         return cacheObject.object;
192     }
193 
194     public synchronized void clear() {
195         Object  [] keys = map.keySet().toArray();
196         for (int i = 0; i < keys.length; i++) {
197             remove(keys[i]);
198         }
199 
200         // Now, reset all containers.
201         map.clear();
202         lastAccessedList.clear();
203         lastAccessedList = new LinkedList();
204         ageList.clear();
205         ageList = new LinkedList();
206 
207         cacheSize = 0;
208         cacheHits = 0;
209         cacheMisses = 0;
210     }
211 
212     public int size() {
213         // First, clear all entries that have been in cache longer than the
214         // maximum defined age.
215         deleteExpiredEntries();
216 
217         return map.size();
218     }
219 
220     public boolean isEmpty() {
221         // First, clear all entries that have been in cache longer than the
222         // maximum defined age.
223         deleteExpiredEntries();
224 
225         return map.isEmpty();
226     }
227 
228     public Collection values() {
229         // First, clear all entries that have been in cache longer than the
230         // maximum defined age.
231         deleteExpiredEntries();
232 
233         Object  [] cacheObjects = map.values().toArray();
234         Object  [] values = new Object  [cacheObjects.length];
235         for (int i = 0; i < cacheObjects.length; i++) {
236             values[i] = ((CacheObject)cacheObjects[i]).object;
237         }
238         return Collections.unmodifiableList(Arrays.asList(values));
239     }
240 
241     public boolean containsKey(Object   key) {
242         // First, clear all entries that have been in cache longer than the
243         // maximum defined age.
244         deleteExpiredEntries();
245 
246         return map.containsKey(key);
247     }
248 
249     public void putAll(Map map) {
250         for (Iterator i = map.keySet().iterator(); i.hasNext();) {
251             Object   key = i.next();
252             Object   value = map.get(key);
253             put(key, value);
254         }
255     }
256 
257     public boolean containsValue(Object   value) {
258         // First, clear all entries that have been in cache longer than the
259         // maximum defined age.
260         deleteExpiredEntries();
261 
262         int objectSize = calculateSize(value);
263         CacheObject cacheObject = new CacheObject(value, objectSize);
264         return map.containsValue(cacheObject);
265     }
266 
267     public Set entrySet() {
268         // First, clear all entries that have been in cache longer than the
269         // maximum defined age.
270         deleteExpiredEntries();
271 
272         return Collections.unmodifiableSet(map.entrySet());
273     }
274 
275     public Set keySet() {
276         // First, clear all entries that have been in cache longer than the
277         // maximum defined age.
278         deleteExpiredEntries();
279 
280         return Collections.unmodifiableSet(map.keySet());
281     }
282 
283     /**
284      * Returns the name of this cache. The name is completely arbitrary
285      * and used only for display to administrators.
286      *
287      * @return the name of this cache.
288      */
289     public String   getName() {
290         return name;
291     }
292 
293     /**
294      * Returns the number of cache hits. A cache hit occurs every
295      * time the get method is called and the cache contains the requested
296      * object.<p>
297      *
298      * Keeping track of cache hits and misses lets one measure how efficient
299      * the cache is; the higher the percentage of hits, the more efficient.
300      *
301      * @return the number of cache hits.
302      */
303     public long getCacheHits() {
304         return cacheHits;
305     }
306 
307     /**
308      * Returns the number of cache misses. A cache miss occurs every
309      * time the get method is called and the cache does not contain the
310      * requested object.<p>
311      *
312      * Keeping track of cache hits and misses lets one measure how efficient
313      * the cache is; the higher the percentage of hits, the more efficient.
314      *
315      * @return the number of cache hits.
316      */
317     public long getCacheMisses() {
318         return cacheMisses;
319     }
320 
321     /**
322      * Returns the size of the cache contents in bytes. This value is only a
323      * rough approximation, so cache users should expect that actual VM
324      * memory used by the cache could be significantly higher than the value
325      * reported by this method.
326      *
327      * @return the size of the cache contents in bytes.
328      */
329     public int getCacheSize() {
330         return cacheSize;
331     }
332 
333     /**
334      * Returns the maximum size of the cache (in bytes). If the cache grows larger
335      * than the max size, the least frequently used items will be removed. If
336      * the max cache size is set to -1, there is no size limit.
337      *
338      * @return the maximum size of the cache (-1 indicates unlimited max size).
339      */
340     public int getMaxCacheSize() {
341         return maxCacheSize;
342     }
343 
344     /**
345      * Sets the maximum size of the cache. If the cache grows larger
346      * than the max size, the least frequently used items will be removed. If
347      * the max cache size is set to -1, there is no size limit.
348      *
349      * @param maxCacheSize the maximum size of this cache (-1 indicates unlimited max size).
350      */
351     public void setMaxCacheSize(int maxCacheSize) {
352         this.maxCacheSize = maxCacheSize;
353         // It's possible that the new max size is smaller than our current cache
354         // size. If so, we need to delete infrequently used items.
355         cullCache();
356     }
357 
358     /**
359      * Returns the maximum number of milleseconds that any object can live
360      * in cache. Once the specified number of milleseconds passes, the object
361      * will be automatically expried from cache. If the max lifetime is set
362      * to -1, then objects never expire.
363      *
364      * @return the maximum number of milleseconds before objects are expired.
365      */
366     public long getMaxLifetime() {
367         return maxLifetime;
368     }
369 
370     /**
371      * Sets the maximum number of milleseconds that any object can live
372      * in cache. Once the specified number of milleseconds passes, the object
373      * will be automatically expried from cache. If the max lifetime is set
374      * to -1, then objects never expire.
375      *
376      * @param maxLifetime the maximum number of milleseconds before objects are expired.
377      */
378     public void setMaxLifetime(long maxLifetime) {
379         this.maxLifetime = maxLifetime;
380     }
381 
382     /**
383      * Returns the size of an object in bytes. Determining size by serialization
384      * is only used as a last resort.
385      *
386      * @return the size of an object in bytes.
387      */
388     private int calculateSize(Object   object) {
389         // If the object is Cacheable, ask it its size.
390         if (object instanceof Cacheable) {
391             return ((Cacheable)object).getCachedSize();
392         }
393         // Check for other common types of objects put into cache.
394         else if (object instanceof Long  ) {
395             return CacheSizes.sizeOfLong();
396         }
397         else if (object instanceof Integer  ) {
398             return CacheSizes.sizeOfObject() + CacheSizes.sizeOfInt();
399         }
400         else if (object instanceof Boolean  ) {
401             return CacheSizes.sizeOfObject() + CacheSizes.sizeOfBoolean();
402         }
403         else if (object instanceof long[]) {
404             long[] array = (long[])object;
405             return CacheSizes.sizeOfObject() + array.length * CacheSizes.sizeOfLong();
406         }
407         // Default behavior -- serialize the object to determine its size.
408         else {
409             int size = 1;
410             try {
411                 // Default to serializing the object out to determine size.
412                 NullOutputStream out = new NullOutputStream();
413                 ObjectOutputStream   outObj = new ObjectOutputStream  (out);
414                 outObj.writeObject(object);
415                 size = out.size();
416             }
417             catch (IOException   ioe) {
418                 Log.error(ioe);
419             }
420             return size;
421         }
422     }
423 
424     /**
425      * Clears all entries out of cache where the entries are older than the
426      * maximum defined age.
427      */
428     protected void deleteExpiredEntries() {
429         // Check if expiration is turned on.
430         if (maxLifetime <= 0) {
431             return;
432         }
433 
434         // Remove all old entries. To do this, we remove objects from the end
435         // of the linked list until they are no longer too old. We get to avoid
436         // any hash lookups or looking at any more objects than is strictly
437         // neccessary.
438         LinkedListNode node = ageList.getLast();
439         // If there are no entries in the age list, return.
440         if (node == null) {
441             return;
442         }
443 
444         // Determine the expireTime, which is the moment in time that elements
445         // should expire from cache. Then, we can do an easy to check to see
446         // if the expire time is greater than the expire time.
447         long expireTime = System.currentTimeMillis() - maxLifetime;
448 
449         while (expireTime > node.timestamp) {
450             // Remove the object
451             remove(node.object);
452 
453             // Get the next node.
454             node = ageList.getLast();
455             // If there are no more entries in the age list, return.
456             if (node == null) {
457                 return;
458             }
459         }
460     }
461 
462     /**
463      * Removes objects from cache if the cache is too full. "Too full" is
464      * defined as within 3% of the maximum cache size. Whenever the cache is
465      * is too big, the least frequently used elements are deleted until the
466      * cache is at least 10% empty.
467      */
468     protected final void cullCache() {
469         // Check if a max cache size is defined.
470         if (maxCacheSize < 0) {
471             return;
472         }
473 
474         // See if the cache size is within 3% of being too big. If so, clean out
475         // cache until it's 10% free.
476         if (cacheSize >= maxCacheSize * .97) {
477             // First, delete any old entries to see how much memory that frees.
478             deleteExpiredEntries();
479             int desiredSize = (int)(maxCacheSize * .90);
480             while (cacheSize > desiredSize) {
481                 // Get the key and invoke the remove method on it.
482                 remove(lastAccessedList.getLast().object);
483             }
484         }
485     }
486 
487     /**
488      * Wrapper for all objects put into cache. It's primary purpose is to maintain
489      * references to the linked lists that maintain the creation time of the object
490      * and the ordering of the most used objects.
491      */
492     private static class CacheObject {
493 
494         /**
495          * Underlying object wrapped by the CacheObject.
496          */
497         public Object   object;
498 
499         /**
500          * The size of the Cacheable object. The size of the Cacheable
501          * object is only computed once when it is added to the cache. This makes
502          * the assumption that once objects are added to cache, they are mostly
503          * read-only and that their size does not change significantly over time.
504          */
505         public int size;
506 
507         /**
508          * A reference to the node in the cache order list. We keep the reference
509          * here to avoid linear scans of the list. Every time the object is
510          * accessed, the node is removed from its current spot in the list and
511          * moved to the front.
512          */
513         public LinkedListNode lastAccessedListNode;
514 
515         /**
516          * A reference to the node in the age order list. We keep the reference
517          * here to avoid linear scans of the list. The reference is used if the
518          * object has to be deleted from the list.
519          */
520         public LinkedListNode ageListNode;
521 
522         /**
523          * A count of the number of times the object has been read from cache.
524          */
525         public int readCount = 0;
526 
527         /**
528          * Creates a new cache object wrapper. The size of the Cacheable object
529          * must be passed in in order to prevent another possibly expensive
530          * lookup by querying the object itself for its size.<p>
531          *
532          * @param object the underlying Object to wrap.
533          * @param size   the size of the Cachable object in bytes.
534          */
535         public CacheObject(Object   object, int size) {
536             this.object = object;
537             this.size = size;
538         }
539     }
540 
541     /**
542      * An extension of OutputStream that does nothing but calculate the number
543      * of bytes written through it.
544      */
545     private static class NullOutputStream extends OutputStream   {
546 
547         int size = 0;
548 
549         public void write(int b) throws IOException   {
550             size++;
551         }
552 
553         public void write(byte[] b) throws IOException   {
554             size += b.length;
555         }
556 
557         public void write(byte[] b, int off, int len) {
558             size += len;
559         }
560 
561         /**
562          * Returns the number of bytes written out through the stream.
563          *
564          * @return the number of bytes written to the stream.
565          */
566         public int size() {
567             return size;
568         }
569     }
570 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags