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