001: /*
002: Copyright 2004 Philip Jacob <phil@whirlycott.com>
003: Seth Fitzsimmons <seth@note.amherst.edu>
004:
005: Licensed under the Apache License, Version 2.0 (the "License");
006: you may not use this file except in compliance with the License.
007: You may obtain a copy of the License at
008:
009: http://www.apache.org/licenses/LICENSE-2.0
010:
011: Unless required by applicable law or agreed to in writing, software
012: distributed under the License is distributed on an "AS IS" BASIS,
013: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: See the License for the specific language governing permissions and
015: limitations under the License.
016: */
017:
018: package com.whirlycott.cache;
019:
020: import java.util.Arrays;
021: import java.util.Iterator;
022: import java.util.LinkedList;
023: import java.util.List;
024: import java.util.Map;
025: import java.util.Map.Entry;
026: import java.util.concurrent.ConcurrentHashMap;
027: import java.util.concurrent.atomic.AtomicBoolean;
028:
029: import org.apache.commons.logging.Log;
030: import org.apache.commons.logging.LogFactory;
031:
032: import com.whirlycott.cache.policy.ExpirationTimePredicate;
033:
034: /**
035: * Owns the cache tuning thread and provides housekeeping facilities for ManagedCache implementations. One
036: * CacheDecorator is created for each Cache named in the whirlycache.xml configuration file.
037: *
038: * @author Phil Jacob
039: */
040: public class CacheDecorator<K, V> implements Runnable, Cache<K, V>,
041: CacheDecoratorMBean {
042:
043: /**
044: * Logger
045: */
046: private static final Log log = LogFactory
047: .getLog(CacheDecorator.class);
048:
049: /**
050: * This is the memory size for the adaptive caching in implementations that support it.
051: */
052: //TODO - make this a percentage of the max size or something...?
053: private int adaptiveMemorySize = 5000;
054:
055: /**
056: * Overflow buffer for the adaptive array.
057: */
058: private static final int ADAPTIVE_MEMORY_SIZE_OVERFLOW = 512;
059:
060: /**
061: * The counter for our current position in the adaptive result array.
062: */
063: private volatile int adaptiveResultCounter = 0;
064:
065: /**
066: * The current time (accurate to sleepTime ms).
067: */
068: private volatile long currentTime = System.currentTimeMillis();
069:
070: /**
071: * The array that holds the adaptive results.
072: */
073: private volatile int adaptiveResults[];
074:
075: /**
076: * This is the cache we're managing.
077: */
078: private volatile ManagedCache<K, Item<V>> managedCache;
079:
080: /**
081: * The soft limit of the max number of items that can be put in the cache.
082: */
083: private int maxSize;
084:
085: /**
086: * Name of this cache
087: */
088: private final String name;
089:
090: /**
091: * The policy used during maintenance.
092: */
093: private final CacheMaintenancePolicy<K, Item<V>> policy;
094:
095: /**
096: * We keep all of the stats in the recordkeeper.
097: */
098: private final RecordKeeper recordKeeper = new RecordKeeper();
099:
100: private final AtomicBoolean requestStop = new AtomicBoolean(false);
101:
102: /**
103: * Constructor for a CacheDecorator.
104: *
105: * @param _managedCache
106: * @param _configuration
107: * @param policy
108: */
109: public CacheDecorator(final ManagedCache<K, Item<V>> _managedCache,
110: final CacheConfiguration _configuration,
111: final CacheMaintenancePolicy<K, Item<V>> policy) {
112:
113: name = _configuration.getName();
114:
115: if (null == name) {
116: throw new IllegalArgumentException(
117: Messages
118: .getString("CacheDecorator.cache_config_cannot_be_null")); //$NON-NLS-1$
119: }
120:
121: if (null == policy) {
122: throw new IllegalArgumentException(
123: Messages
124: .getString("CacheDecorator.policies_cannot_be_null")); //$NON-NLS-1$
125: }
126:
127: this .policy = policy;
128:
129: //Adaptive size plus the buffer (to prevent ArrayIndexOutOfBoundsExceptions)s
130: adaptiveResults = new int[adaptiveMemorySize
131: + ADAPTIVE_MEMORY_SIZE_OVERFLOW];
132:
133: //This is the cache which we are managing.
134: managedCache = _managedCache;
135:
136: //Do some configuration.
137: configure(_configuration);
138: }
139:
140: /**
141: * Clears the cache.
142: */
143: public void clear() {
144: log.info(Messages.getString("CacheDecorator.clearing_cache")); //$NON-NLS-1$
145: managedCache.clear();
146: Arrays.fill(adaptiveResults, 0);
147: }
148:
149: /**
150: * Configures the Cache being decorated.
151: */
152: protected void configure(final CacheConfiguration configuration) {
153: //Set up the max size.
154: maxSize = configuration.getMaxSize();
155: }
156:
157: /**
158: * Looks at the last 'n' queries to determine whether the Cache should turn on optimizations for a mostly-read
159: * environment (if the underlying implementation of ManagedCache supports this).
160: *
161: * @param _value varies depending on whether this was a read, write, or removal.
162: */
163: protected void doAdaptiveAccounting(final int _value) {
164: //We only care about the last 'n' adaptiveResults.
165: final int currentCounter = adaptiveResultCounter;
166: if (currentCounter >= adaptiveMemorySize) {
167: adaptiveResultCounter = 0;
168: adaptiveResults[0] = _value;
169: } else {
170: adaptiveResults[currentCounter] = _value;
171: adaptiveResultCounter++;
172: }
173: }
174:
175: /**
176: * @return Returns the adaptiveMemorySize.
177: */
178: protected int getAdaptiveMemorySize() {
179: return adaptiveMemorySize;
180: }
181:
182: /**
183: * Calculates the adaptive hit rate for this cache.
184: *
185: * @return adaptive hit ratio.
186: */
187: public float getAdaptiveRatio() {
188: final int copy[] = new int[adaptiveMemorySize];
189: System.arraycopy(adaptiveResults, 0, copy, 0,
190: adaptiveMemorySize);
191: int positives = 0;
192: for (int value : copy) {
193: if (value == 1) {
194: positives++;
195: }
196: }
197: //log.info("Positives: " + positives + "; Total: " + adaptiveMemorySize);
198: return (float) positives / (float) adaptiveMemorySize;
199: }
200:
201: /**
202: * Returns an efficiency report string for this cache.
203: *
204: * @return efficiency report for this cache.
205: */
206: public String getEfficiencyReport() {
207: return Messages.getCompoundString(
208: "CacheDecorator.efficiency_report", name, managedCache
209: .size(), recordKeeper.getTotalOperations(),
210: recordKeeper.getHits(), getAdaptiveRatio(),
211: getTotalHitrate());
212: }
213:
214: /**
215: * Get the maximum size of the cache.
216: *
217: * @return Returns the maxSize.
218: */
219: protected int getMaxSize() {
220: return maxSize;
221: }
222:
223: /**
224: * @return Returns the policy in use for managing this cache.
225: */
226: protected CacheMaintenancePolicy getPolicy() {
227: return policy;
228: }
229:
230: /**
231: * Returns the total hitrate since this Cache was started.
232: *
233: * @return Total hitrate.
234: */
235: public float getTotalHitrate() {
236: return new Long(recordKeeper.getHits()).floatValue()
237: / new Long(recordKeeper.getTotalOperations())
238: .floatValue();
239: }
240:
241: //TODO public Object remove(final Cacheable _key) {
242: // final Object o = internalRemove(_key);
243: // _key.onRemove(o);
244: // return o;
245: // }
246:
247: /**
248: * Removes an Object from the Cache and returns the removed Object.
249: *
250: * @param _key key associated with object to remove.
251: */
252: public V remove(final K _key) {
253: return internalRemove(_key);
254: }
255:
256: /**
257: * An internal remove operation.
258: *
259: * @param _key
260: *
261: * @return removed item
262: */
263: protected V internalRemove(final K _key) {
264: recordKeeper.incrementTotalOperations();
265:
266: if (_key != null) {
267: final Item<V> cachedItem = managedCache.remove(_key);
268:
269: //The compiler will optimize this.
270: doAdaptiveAccounting(0);
271:
272: return null == cachedItem ? null : cachedItem.getItem();
273: } else {
274: return null;
275: }
276: }
277:
278: //TODO public Object retrieve(final Cacheable _key) {
279: // final Object o = internalRetrieve(_key);
280: // _key.onRetrieve(o);
281: // return o;
282: // }
283:
284: protected V internalRetrieve(final K _key) {
285: //Record a read.
286: doAdaptiveAccounting(1);
287:
288: //Increment the number of totalQuestions.
289: recordKeeper.incrementTotalOperations();
290:
291: //Set up the return value
292: final Item<V> cachedItem = managedCache.get(_key);
293: if (cachedItem != null) {
294:
295: //Bump the numbers.
296: cachedItem.setUsed(recordKeeper.getTotalOperations());
297: cachedItem.incrementCount();
298:
299: //Increment the adaptive algorithm and the hitcounter.
300: final V retval = cachedItem.getItem();
301: if (retval != null) {
302: recordKeeper.incrementHits();
303: }
304:
305: return retval;
306: } else {
307: //Found nothing inside the cache.
308: return null;
309: }
310: }
311:
312: /**
313: * Gets an Object from the Cache.
314: */
315: public V retrieve(final K _key) {
316: return internalRetrieve(_key);
317: }
318:
319: public void run() {
320: recordKeeper.calculateQueriesPerSecond();
321:
322: logStatistics();
323:
324: // updates the cache's notion of the "current time"
325: currentTime = System.currentTimeMillis();
326:
327: recordKeeper.startTuneCycle();
328:
329: // expire Items in need of expiration
330: expireItems();
331:
332: //Perform tuning and maintenance.
333: policy.performMaintenance(managedCache, maxSize);
334:
335: if (log.isDebugEnabled()) {
336: log.debug(Messages
337: .getString("CacheDecorator.cache_tuning_complete")); //$NON-NLS-1$
338: }
339: }
340:
341: /**
342: * Log some cache usage data depending on some conditions.
343: */
344: protected void logStatistics() {
345: if (log.isDebugEnabled()) {
346: log.debug(Messages.getCompoundString(
347: "CacheDecorator.query_rate", name,
348: getQueriesPerSecond()));
349: }
350:
351: //Print the efficiency report
352: if (log.isInfoEnabled()) {
353: log.info(getEfficiencyReport());
354: }
355: }
356:
357: public long getQueriesPerSecond() {
358: return recordKeeper.getQueriesPerSecond();
359: }
360:
361: /**
362: * Shut down this cache.
363: */
364: public void dispose() {
365: if (log.isDebugEnabled()) {
366: log.debug(Messages
367: .getString("CacheDecorator.shutting_down_cache")
368: + name);
369: }
370:
371: log.info(getEfficiencyReport());
372: recordKeeper.reset();
373: requestStop.set(true);
374: }
375:
376: /**
377: * Returns the number of items in the Cache.
378: *
379: * @return number of items in the cache.
380: */
381: public int size() {
382: recordKeeper.incrementTotalOperations();
383:
384: return managedCache.size();
385: }
386:
387: public int getSize() {
388: return managedCache.size();
389: }
390:
391: //TODO public void store(final Cacheable key, final Object value) {
392: // internalStore(key, value, -1L);
393: // key.onStore(value);
394: // }
395: /**
396: * Store an object in the cache.
397: */
398: public void store(final K _key, final V _value) {
399: internalStore(_key, _value, -1L);
400: }
401:
402: public void store(final K _key, final V _value,
403: final long _expiresAfter) {
404: internalStore(_key, _value, _expiresAfter);
405: }
406:
407: /**
408: * All stores go through this.
409: *
410: * @param _key
411: * @param _value
412: * @param _expiresAfter specified in milliseconds
413: */
414: protected void internalStore(final K _key, final V _value,
415: final long _expiresAfter) {
416: recordKeeper.incrementTotalOperations();
417:
418: if (_key != null && _value != null) {
419: final Item<V> cachedValue = new Item<V>(_value,
420: currentTime, _expiresAfter);
421: managedCache.put(_key, cachedValue);
422:
423: doAdaptiveAccounting(0);
424: }
425: }
426:
427: /**
428: * Expires Items in need of expiration.
429: */
430: protected void expireItems() {
431: //Sort the entries in the cache.
432: final List<Map.Entry<K, Item<V>>> entries = new LinkedList<Entry<K, Item<V>>>(
433: new ConcurrentHashMap<K, Item<V>>(managedCache)
434: .entrySet());
435:
436: ExpirationTimePredicate predicate = new ExpirationTimePredicate(
437: currentTime);
438:
439: for (Iterator it = entries.iterator(); it.hasNext();) {
440: if (!predicate.evaluate(it.next())) {
441: it.remove();
442: }
443: }
444:
445: if (log.isDebugEnabled()) {
446: log.debug(Messages.getCompoundString(
447: "CacheDecorator.expiration_count", entries.size()));
448: }
449:
450: for (Entry<K, Item<V>> entry : entries) {
451: if (entry != null) {
452: //log.trace("Removing: " + entry.getKey());
453: managedCache.remove(entry.getKey());
454: }
455: }
456: }
457:
458: }
|