Java > Open Source Codes > org > sape > carbon > services > cache > mru > AbstractMRUCache


1 /*
2  * The contents of this file are subject to the Sapient Public License
3  * Version 1.0 (the "License"); you may not use this file except in compliance
4  * with the License. You may obtain a copy of the License at
5  * http://carbon.sf.net/License.html.
6  *
7  * Software distributed under the License is distributed on an "AS IS" basis,
8  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
9  * the specific language governing rights and limitations under the License.
10  *
11  * The Original Code is The Carbon Component Framework.
12  *
13  * The Initial Developer of the Original Code is Sapient Corporation
14  *
15  * Copyright (C) 2003 Sapient Corporation. All Rights Reserved.
16  */
17
18 package org.sape.carbon.services.cache.mru;
19
20 import java.util.Collection ;
21 import java.util.Collections ;
22 import java.util.HashMap ;
23 import java.util.Iterator ;
24 import java.util.Map ;
25 import java.util.Set ;
26 import java.util.TreeSet ;
27
28 import org.sape.carbon.core.component.Component;
29 import org.sape.carbon.core.component.ComponentConfiguration;
30 import org.sape.carbon.core.component.lifecycle.Configurable;
31 import org.sape.carbon.core.component.lifecycle.Initializable;
32 import org.sape.carbon.core.config.InvalidConfigurationException;
33
34 import org.apache.commons.logging.Log;
35 import org.apache.commons.logging.LogFactory;
36
37
38 /**
39  * <p>Class which provides a generic "Most Recently Used" cache. The cache uses
40  * a dataloader to provide it with the capability to retrieve items to encache.
41  * Cached items are then retrieved from memory, while uncached items are
42  * retrieved from the dataloader and placed into the cache.</p>
43  *
44  * <p>The cache operates in what is known alternatly as a Most Recently Used
45  * (MRU) or Least Recently Used (LRU) manner. What this means is that the most
46  * recently requested items are kept in the cache, while the least recently used
47  * are cached only briefly, and tend to be fetched from the dataloader on each
48  * request. An MRU cache is very useful for data which it is even slightly
49  * expensive to retrieve, and which conforms to the 80/20 rule - 20% of the
50  * data is used 80% of the time.</p>
51  *
52  * <p>The internal implementation of the MRUCache uses a pair of Hashtables to
53  * store the cache information and a TreeSet to store the ordering of keys in
54  * order to know which objects should be removed from the cache as it fills up.
55  * As a result, most operations on the cache are guaranteed log(n), where n is
56  * the size of the cache.</p>
57  *
58  * <p>It should be noted that all methods on the MRUCache are synchronized, and
59  * that the underlying collections, which are occasionally exposed to the user
60  * through methods such as entrySet(), are also synchronized. The reason for
61  * this is the nature of an MRUCache. All write operations, and all read
62  * operations have the potential of modifying the cache - because reads may
63  * request items not found in the cache.</p>
64  *
65  * <p>It should further be noted that all keys to the cache must implement the
66  * java.lang.Comparable interface. This is already implemented by all primitive
67  * wrapper classes, as well as File, String, Date, BigInteger and BigDecimal,
68  * making implementations for custom classes trivial in most cases. The use
69  * of Comparable for keys is what allows guaranteed log(n) operations on the
70  * cache, while maintaining cache integrity.</p>
71  *
72  * <p>Elements stored in the cache, have an
73  * configurable expiration time. Reason being certain data might become stale
74  * after a period of time. You can say that I want elements only to exist
75  * in the cache for a certain period of time. For example, if you have a
76  * cache of stock quotes, you might want to mandate that stock quote information
77  * is only valuable if the quote data is less than 5 minutes old.</p>
78  *
79  * <p>This operation of expiring elements happens passively. The get
80  * method will determine if the data is stale, if so it will get a fresh
81  * element.</p>
82  *
83  * <p>The MRUCache makes use of the framework logging facilities to dump
84  * statistical information regarding the cache. Whenever the cache is cleared
85  * either manually, by calling clear(), or when refreshAll() is called by the
86  * cache manager, statistics are logged at DEBUG level.
87  * When a call to get(Object key) results in a cache miss
88  * statistics are logged at INFO level.
89  * This latter option should not be used in production as it severely degrades
90  * performance. When this level is not logged, no degredation is caused.</p>
91  *
92  * Copyright 2002 Sapient
93  * @see java.lang.Comparable
94  * @see java.util.TreeSet
95  * @since carbon 1.0
96  * @author Doug Voet, April 2002
97  * @version $Revision: 1.17 $($Author: ghinkl $ / $Date: 2003/07/03 18:47:48 $)
98  */
99 public abstract class AbstractMRUCache
100     implements MRUCache, Configurable, Initializable {
101
102     /** The handle to Apache-commons logger */
103     private Log log = LogFactory.getLog(this.getClass());
104
105     /** Holds the capacity of the cache. */
106     protected int capacity = 0;
107
108     /** Holds the expiration interval of objects in the cache. */
109     protected long expirationInterval = 0;
110
111     /** Map of values in the cache. */
112     protected Map map;
113
114     /**
115      * A ordered set by the KeyInfo allows this. Used hold the
116      * MRU information in order of last access.
117      */
118     protected TreeSet ordering;
119
120     /** Holds all of the keys in the cache. */
121     protected Map keyMap;
122
123     /** Holds the name of the configuration. */
124     protected String name;
125
126     /** Tracks the number of hits to the cache. */
127     protected long cacheHits = 0;
128
129     /** Tracks the number of misses to the cache. */
130     protected long cacheMisses = 0;
131
132     /** The default time out interval for MRUCache element expiration */
133     public static final long DEFAULT_ELEMENT_EXPIRATION_INTERVAL = -1;
134
135     /** The default time for MRUCache element expiration, if no iterval
136      * hava been selected */
137     public static final long MAX_EXPIRATION_TIME = Long.MAX_VALUE;
138
139     //////////////////////////////
140 // component lifecycle methods
141 //////////////////////////////
142
143     /**
144      * @see Configurable#configure(ComponentConfiguration)
145      */
146     public void configure(ComponentConfiguration configuration) {
147
148         MRUCacheConfiguration myConfig = (MRUCacheConfiguration) configuration;
149
150         if (myConfig.getCapacity() == null) {
151             throw new InvalidConfigurationException(
152                 this.getClass(), myConfig.getConfigurationName(),
153                 "Capacity",
154                 "Must be specified, not optional");
155         }
156
157         setCapacity(myConfig.getCapacity());
158         setExpirationInterval(myConfig.getExpirationInterval());
159
160         this.name = myConfig.getConfigurationName();
161
162         if (log.isInfoEnabled()) {
163             log.info("configuring cache with capacity " + capacity);
164         }
165     }
166
167     /**
168      * @see Initializable#initialize(org.sape.carbon.core.component.Component)
169      */
170     public void initialize(Component thisComponent) {
171         this.ordering = new TreeSet ();
172         this.map = new HashMap ();
173         this.keyMap = new HashMap ();
174     }
175
176
177     /**
178      * <p>Clears the cache in this implementation of the cache, allowing for
179      * periodic expiration of all data in the cache. All data in the cache is
180      * removed regardless of whether it has been in the cache since the last
181      * refresh, or it was just entered into the cache.</p>
182      */
183     public synchronized void refreshAll() {
184         this.clear();
185     }
186
187
188     /**
189      * <p>Removes all mappings from this cache. This entails removing everything
190      * from the map which forms the real cache, removing the entries from the
191      * keyMap, and removing all of the KeyInfo objects from the ordering.</p>
192      */
193     public synchronized void clear() {
194         double totalFetches = this.cacheHits + this.cacheMisses;
195         double hitRate = (double) this.cacheHits * 100 / totalFetches;
196
197         if (log.isInfoEnabled()) {
198             log.info("Current cache size is "
199                 + this.ordering.size()
200                 + ". Total fetches from cache: "
201                 + totalFetches
202                 + ". Cache hit rate: "
203                 + hitRate
204                 + "%.");
205         }
206         this.map.clear();
207         this.keyMap.clear();
208         this.ordering.clear();
209         this.cacheHits = 0;
210         this.cacheMisses = 0;
211     }
212
213
214     /**
215      * <p>For a given key value, return a boolean indicating if the cache
216      * contains a value for the key.</p>
217      *
218      * <p><strong>Note: </strong>This method does not check the key's
219      * expiration.</p>
220      *
221      * @param key key for the desired cache entry
222      * @return boolean true if the cache contains a mapping for
223      * the specified key
224      */
225     public synchronized boolean containsKey(Object key) {
226         return this.map.containsKey(key);
227     }
228
229
230     /**
231      * <p>Returns true if this cache maps one or more keys to the
232      * specified value.
233      * More formally, returns true if and only if this cache contains at least
234      * one mapping to a value v such that<br>
235      * (value==null ? v==null : value.equals(v)).
236      * This operation will require time linear in the cache size.</p>
237      *
238      * <p><strong>Note: </strong>This method does not check the key's
239      * expiration.</p>
240      *
241      * @param value value whose presence in this map is to be
242      * tested.
243      * @return boolean true if this map maps one or more
244      * keys to the specified value.
245      */
246     public synchronized boolean containsValue(Object value) {
247         return this.map.containsValue(value);
248     }
249
250
251     /**
252      * <p>Returns an unmodifable view of the mappings contained in this cache.
253      * Each
254      * element in the returned set is a Map.Entry.
255      *
256      * @return Set an unmodifable set of mappings in this cache
257      */
258     public synchronized Set entrySet() {
259         return Collections.unmodifiableSet(this.map.entrySet());
260     }
261
262
263     /**
264      * <p>Returns true if this map contains no key-value mappings.</p>
265      *
266      * @return boolean true if this map contains no
267      * key-value mappings
268      */
269     public synchronized boolean isEmpty() {
270         return this.map.isEmpty();
271     }
272
273
274     /**
275      * <p>Returns an unmodifable set of the keys of the cache.</p>
276      *
277      * <p><strong>Note: </strong>This method does not check the key's
278      * expiration.</p>
279      *
280      * @return Set The an unmodifable set of all
281      * keys in the cache.
282      */
283     public synchronized Set keySet() {
284         return Collections.unmodifiableSet(this.map.keySet());
285     }
286
287
288     /**
289      * <p>Put the Object value into the cache referenced by the Object key. This
290      * will cause older items to be flushed from the cache when the cache is
291      * operating at its capacity.</p>
292      *
293      * @param key The key for the entry.
294      * @param value The value for the entry.
295      *
296      * @return the previous entry that was stored for the given key or null
297      * if there was no previous entry
298      */
299     public synchronized Object put(Object key, Object value) {
300         Object previousEntry = null;
301         Object previousKey = null;
302         KeyInfo keyInfo = new KeyInfo(key, this.expirationInterval);
303
304         // Now add it to the ordering list, and if we nudged an
305 // element over our capacity limit, remove it!
306 previousEntry = this.map.put(key, value);
307         previousKey = this.keyMap.put(key, keyInfo);
308         if (previousKey != null) {
309             // Remove the old key
310 this.ordering.remove(previousKey);
311         }
312         
313         this.ordering.add(keyInfo);
314
315         if (this.ordering.size() > this.capacity) {
316             removeLast();
317         }
318
319         // Puts always return the previous value held under that key if there
320 // was one, otherwise null.
321 return previousEntry;
322     }
323
324     /**
325      * <p>Copies all of the mappings from the specified map to this cache.
326      * These mappings will replace any mappings that this cache had for any of
327      * the keys currently in the specified cache.</p>
328      *
329      * <p>Note that based upon the size limit of the cache, all mappings in the
330      * Map t may not be extent in the cache after this operation. All items
331      * will be put into the cache, but some may be flushed out as the least
332      * recently used before this operation completes.</p>
333      *
334      * @param t map of objects to place into this cache
335      */
336     public synchronized void putAll(Map t) {
337         Map.Entry entry = null;
338         Iterator entryIterator = t.entrySet().iterator();
339
340         // Iterator through calling this.put() instead of simply calling
341 // this.map.putAll() so that we keep to the capacity of the cache!
342 while (entryIterator.hasNext()) {
343             entry = (Map.Entry ) entryIterator.next();
344             this.put(entry.getKey(), entry.getValue());
345         }
346     }
347
348
349     /**
350      * <p>Removes the mapping for this key from this cache.</p>
351      *
352      * @param key the key remove the object for
353      * @return Object previous value associated with specified key,
354      * or null if there was no mapping for key.
355      */
356     public synchronized Object remove(Object key) {
357         Object value = null;
358
359         value = this.map.remove(key);
360         KeyInfo keyInfo = (KeyInfo) this.keyMap.remove(key);
361         this.ordering.remove(keyInfo);
362
363         return value;
364     }
365
366     /**
367      * <p>Returns the number of key-value mappings in this map. If the map
368      * contains more than Integer.MAX_VALUE elements, returns
369      * Integer.MAX_VALUE.</p>
370      *
371      * <p><strong>Note: </strong>This method does not check the key's
372      * expiration.</p>
373      *
374      * @return int The number of key-value mappings in this map.
375      */
376     public synchronized int size() {
377         return this.map.size();
378     }
379
380
381     /**
382      * <p>Returns a collection view of the values contained in this cache.</p>
383      *
384      * @return Collection an unmodifiable view of the
385      * values contained in this cache
386      */
387     public synchronized Collection values() {
388         return Collections.unmodifiableCollection(this.map.values());
389     }
390
391
392     /**
393      * Gets the number of hits to the cache.
394      *
395      * @return the number of hits to the cache
396      */
397     public Long getHits() {
398         return new Long (this.cacheHits);
399     }
400
401     /**
402      * Gets the number of misses to the cache.
403      *
404      * @return the number of misses to the cache
405      */
406     public Long getMisses() {
407         return new Long (this.cacheMisses);
408     }
409
410     /**
411      * Gets the hit percentage of the cache.
412      *
413      * @return the hit percentage of the cache
414      */
415     public Float getHitPercentage() {
416         return new Float ((1.0 * cacheHits) / (cacheHits + cacheMisses));
417     }
418
419     /**
420      * Gets the capacity of the cache.
421      *
422      * @return the capacity of the cache
423      */
424     public Integer getCapacity() {
425         return new Integer (this.capacity);
426     }
427
428     /**
429      * Sets the capacity of the cache.
430      *
431      * @param capacity the capacity of the cache
432      */
433     public synchronized void setCapacity(Integer capacity) {
434         this.capacity = capacity.intValue();
435         while (size() > this.capacity) {
436             removeLast();
437         }
438     }
439
440     /**
441      * Gets the current expiration interval of the cache.
442      *
443      * @return the expiration interval
444      */
445     public Long getExpirationInterval() {
446         return new Long (this.expirationInterval);
447     }
448
449     /**
450      * Sets the expiration interval for the cache.
451      *
452      * @param newInterval the new expiration interval
453      */
454     public void setExpirationInterval(Long newInterval) {
455         if (newInterval == null) {
456             this.expirationInterval = DEFAULT_ELEMENT_EXPIRATION_INTERVAL;
457         } else {
458             this.expirationInterval = newInterval.longValue();
459         }
460     }
461
462     /**
463      * Gets the size of the cache.
464      *
465      * @return the size of the cache
466      */
467     public Long getSize() {
468         return new Long (this.map.size());
469     }
470
471     /**
472      * Returns a string representation of the object included
473      * basic statistics like capacity, size, requests, total fetches,
474      * and hit rate.
475      *
476      * @return a string representation of the object
477      */
478     public String toString() {
479         double totalFetches = this.cacheHits + this.cacheMisses;
480         double hitRate = (double) this.cacheHits * 100 / totalFetches;
481
482         StringBuffer stringBuffer = new StringBuffer (256);
483
484         stringBuffer.append("MRUCache - name: [");
485         stringBuffer.append(this.name);
486         stringBuffer.append("] with capacity [");
487         stringBuffer.append(capacity);
488         stringBuffer.append("] size: [");
489         stringBuffer.append(this.ordering.size());
490         stringBuffer.append("] requests: [");
491         stringBuffer.append(totalFetches);
492         stringBuffer.append("] hit rate: [");
493         stringBuffer.append(hitRate);
494         stringBuffer.append("]%");
495
496         return stringBuffer.toString();
497     }
498
499     /**
500      * Refreshes the cache
501      *
502      * @see org.sape.carbon.services.scheduler.Schedulable#runScheduledTask()
503      */
504     public void runScheduledTask() {
505         refreshAll();
506     }
507
508
509     /**
510      * <p>This method retrieves an object from the internal maps and
511      * updates all of the normal key information. This will not however
512      * cause the dataloader to retrieve the value if it is not found.
513      * This has been done to allow the getMultiple interface to be able
514      * to pass a full list of not found values to the data loader.</p>
515      *
516      * @param key The key object with which to lookup the value
517      * @return an object from the internal map matching the key
518      */
519     protected synchronized Object getObject(Object key) {
520         // Synchronize looking up the value from the cache...
521 KeyInfo keyInfo = (KeyInfo) this.keyMap.get(key);
522
523         Object value = null;
524         // if we got a keyInfo, check to see if it has expired
525 if (keyInfo != null) {
526             // if expired, remove it from the cache
527 if (keyInfo.hasExpired()) {
528                 remove(keyInfo.getKey());
529             } else {
530                 // this means element was in the cache, update statistics
531 value = this.map.get(key);
532                 this.ordering.remove(keyInfo);
533                 keyInfo.updateAccessTime();
534                 this.ordering.add(keyInfo);
535                 this.cacheHits++;
536             }
537         }
538         return value;
539     }
540
541     /**
542      * <p>Removes the oldest item in this cache.</p>
543      */
544     protected synchronized void removeLast() {
545         KeyInfo keyInfo = (KeyInfo) this.ordering.first();
546         remove(keyInfo.getKey());
547     }
548
549
550
551     /**
552      * <p>Protected method used by the testHarness.</p>
553      * @return long number of hits
554      */
555     protected long getCacheHits() {
556         return this.cacheHits;
557     }
558
559
560     /**
561      * <p>Protected method used by the testHarness.</p>
562      * @return long number of misses
563      */
564     protected long getCacheMisses() {
565         return this.cacheMisses;
566     }
567
568
569 }
570
571
572 /**
573  * <p>Package visibility class used by the MRUCache to store a reference to the
574  * key object along with the last accessed time and expiration time for that
575  * key/value in milliseconds.</p>
576  *
577  * <p>Implements the java.lang.Comparable interface, to allow fast sorting of
578  * KeyInfo objects in a Collection - or in this case, a TreeSet. Comparision is
579  * based on the lastAccessedTime for the key (which is set by the MRUCache each
580  * time the key is passed into a call to get. If the lastAccessedTime of two
581  * KeyInfo objects is the same the compareTo method of the Comparable interface
582  * is invoked on the key object to determine the natural ordering.</p>
583  *
584  * Copyright 2000 Sapient
585  * @version $Revision: 1.17 $
586  *
587  * @author $Author: ghinkl $ $Date: 2003/07/03 18:47:48 $
588  */
589 class KeyInfo implements Comparable {
590     /** Internal variable to hold the key. */
591     private Object key = null;
592
593     /** Internal variable to hold the time this key was last accessed. */
594     private long lastAccessTime = 0;
595
596     /**
597      * Internal variable to hold the time when this key's element
598      * will expire
599      */
600     private long expirationTime = 0;
601
602     /**
603      * <p>Default constructor, which constructs a KeyInfo object from a key, and
604      * initialized the lastAccessTime to the current time.</p>
605      *
606      * @param key The object representing the key for this KeyInfo.
607      * @param expirationInterval duration of time of the element in
608      * milliseconds.
609      */
610     KeyInfo(Object key, long expirationInterval) {
611         this.key = key;
612         this.lastAccessTime = System.currentTimeMillis();
613
614         // if Expiration Interval has not been set, set expirationTime
615 // to Long.MAX_VALUE
616 if (expirationInterval
617                 == AbstractMRUCache.DEFAULT_ELEMENT_EXPIRATION_INTERVAL) {
618
619             this.expirationTime = AbstractMRUCache.MAX_EXPIRATION_TIME;
620         } else {
621             this.expirationTime = this.lastAccessTime + expirationInterval;
622         }
623
624     }
625
626     /**
627      * <p>Simple getter for the key held inside this KeyInfo object.</p>
628      *
629      * @return Object The key object held internally.
630      */
631     Object getKey() {
632         return this.key;
633     }
634
635     /**
636      * <p>Simple getter for the expirationTime held inside this KeyInfo
637      * object.</p>
638      *
639      * @return long The time in millis when this key should be
640      * expired
641      */
642     long getExpirationTime() {
643         return this.expirationTime;
644     }
645
646     /**
647      * <p>A simple method to determine whether or not the element has expired
648      *
649      * @return boolean true if the current system time >= the
650      * elements expiration time
651      */
652     boolean hasExpired() {
653         return (System.currentTimeMillis() >= this.expirationTime);
654     }
655
656
657     /**
658      * <p>Updates the lastAccessedTime of the KeyInfo, which is used to
659      * determine its natural ordering for the compareTo method.</p>
660      */
661     void updateAccessTime() {
662         this.lastAccessTime = System.currentTimeMillis();
663     }
664
665
666     /**
667      * Implementation of the compareTo method from the Comparable interface.
668      *
669      * This method performs a three level comparison.
670      * First, we compare lastAccess time,
671      * Secound, we compare expirationTime,
672      * and Last, we compare the keyInfo's key.
673      *
674      * Basically, this method will return -1 if this "is Older than"
675      * other. 1 if this "is Younger than"
676      * other. and 0 if they are the same.
677      *
678      * @param other Another KeyInfo object to compare this one to.
679      * @return int 0 if the objects contain the same key, hav
680      *
681      * @see java.lang.Comparable
682      */
683     public final int compareTo(final Object other) {
684         // Cast the other keyInfo object to a KeyInfo
685 KeyInfo otherKeyInfo = (KeyInfo) other;
686         int returnValue = 0;
687
688         // If the access times are the same, then consult the hashcodes of the
689 // keys contained inside the KeyInfos
690 if (this.lastAccessTime == otherKeyInfo.lastAccessTime) {
691             if (this.expirationTime == otherKeyInfo.expirationTime) {
692                 returnValue =
693                     ((Comparable ) this.key).compareTo(otherKeyInfo.key);
694
695             } else if (this.expirationTime > otherKeyInfo.expirationTime) {
696                 returnValue = 1;
697             } else {
698                 returnValue = -1;
699             }
700         } else if (this.lastAccessTime > otherKeyInfo.lastAccessTime) {
701             // If they access times are not the same, then the one with an
702 // earlier time is considered lower in the ordering (will come
703 // earlier in an ascending sort).
704 returnValue = 1;
705         } else {
706             returnValue = -1;
707         }
708
709         // Send the return value back to the caller
710 return returnValue;
711     }
712
713
714     /**
715      * <p>Checks if the KeyInfo objects are equal.</p>
716      *
717      * @param other The other object to check for equality.
718      * @return boolean True if the two objects are equal, false
719      * otherwise.
720      */
721     public final boolean equals(final Object other) {
722         return this.compareTo(other) == 0;
723     }
724
725     /**
726      * Returns a hash code value for the object based on the key.
727      *
728      * @return a hash code for the key.
729      */
730     public int hashCode() {
731         return this.key.hashCode();
732     }
733
734
735     /**
736      * <p>Overrides the toString() method to return the toString() of the key
737      * object, prints the lastAccessTime and expirationTime in milliseconds.</p>
738      *
739      * @return String a String representation of the KeyInfo object.
740      */
741     public String toString() {
742         return "Key: '" + this.key.toString()
743             + "', Last Access Time: " + this.lastAccessTime
744             + "', Expiration Time: " + this.expirationTime;
745     }
746 }
747
748
749

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags