X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=kona%2Fsrc%2Forg%2Fgffs%2Fcache%2FTimedOutLRUCache.java;fp=kona%2Fsrc%2Forg%2Fgffs%2Fcache%2FTimedOutLRUCache.java;h=43dbc44d0fc4bfba63d897c539db7125f792b38e;hb=7b39f7e279005c8466ef508220a532ce2aa4abf8;hp=0000000000000000000000000000000000000000;hpb=3fbd372b35b15a19fb171d5ae34294ff7b1e6485;p=feisty_meow.git diff --git a/kona/src/org/gffs/cache/TimedOutLRUCache.java b/kona/src/org/gffs/cache/TimedOutLRUCache.java new file mode 100644 index 00000000..43dbc44d --- /dev/null +++ b/kona/src/org/gffs/cache/TimedOutLRUCache.java @@ -0,0 +1,335 @@ +package org.gffs.cache; + +/* + * Copyright 2006 University of Virginia + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may + * obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions + * and limitations under the License. + */ + +import java.util.ArrayList; +import java.util.Date; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; + +/** + * This cache attempt to efficiently handle cached items that may time out after a certain period of time. It does this by maintaining 3 + * separate data structures. The first is a HashMap which allows for quick access to the cached data based off of the key. The second is a + * linked list which maintains the LRU property of the items. The third is a list ordered by timeout so that items that have timed out can be + * identified quickly (i.e., a straight traversal of this list). All data structures share the exact same data node (not equivalent, but + * identical instances of the node class). This means that once a node is identified through any of the means indicated (key, LRU property, + * timeout property), the node for all three data structures has been identified and does not need to be looked up in the others. + * + * @author mmm2a + * + * @param + * @param + */ +public class TimedOutLRUCache +{ + static Log _logger = LogFactory.getLog(TimedOutLRUCache.class); + + private HashMap> _map; + private LRUList _lruList; + private TimeoutList _timeoutList; + + private int _maxElements; + private long _defaultTimeoutMS; + private Thread _activeTimeoutThread = null; + private boolean _logCacheEjection = false; + public String _cacheName = null; // the name for this cache. + + public TimedOutLRUCache(int maxElements, long defaultTimeoutMS, String cacheName) + { + if (maxElements < 1) + throw new IllegalArgumentException("\"maxElements\" must be greater than 0."); + _cacheName = cacheName; + if (_cacheName == null) + throw new IllegalArgumentException("must provide a non-null cache name"); + + _maxElements = maxElements; + _defaultTimeoutMS = defaultTimeoutMS; + _map = new HashMap>(_maxElements); + _lruList = new LRUList(); + _timeoutList = new TimeoutList(); + } + + /** + * returns the number of elements held in the cache currently. + */ + public int size() + { + return _map.size(); + } + + /** + * allows this cache to log when items are removed due to overloading or timing out. + */ + public void setCacheEjectionLogging(boolean logRemovals) + { + _logCacheEjection = logRemovals; + } + + public void activelyTimeoutElements(boolean activelyTimeout) + { + synchronized (_map) { + if (_activeTimeoutThread == null) { + if (activelyTimeout) + startActiveTimeout(); + } else { + if (!activelyTimeout) + stopActiveTimeout(); + } + } + } + + public String debugPrefix() + { + return _cacheName + ": "; + } + + public void put(KeyType key, DataType data, long timeoutMS) + { + RoleBasedCacheNode newNode = + new RoleBasedCacheNode(key, data, new Date(System.currentTimeMillis() + timeoutMS)); + + synchronized (_map) { + RoleBasedCacheNode oldNode = _map.remove(key); + if (oldNode != null) { + _lruList.remove(oldNode); + _timeoutList.remove(oldNode); + } + + if (_map.size() >= _maxElements) + clearStale(); + + while (_map.size() >= _maxElements) { + RoleBasedCacheNode node = _lruList.removeFirst(); + if (_logCacheEjection && _logger.isDebugEnabled()) + _logger.debug(debugPrefix() + "overloaded cache: removing cached item with key: " + node.getKey()); + _timeoutList.remove(node); + _map.remove(node.getKey()); + } + + _map.put(key, newNode); + _lruList.insert(newNode); + _timeoutList.insert(newNode); + + _map.notify(); + } + } + + public void put(KeyType key, DataType data) + { + put(key, data, _defaultTimeoutMS); + } + + public int getMaximumElements() + { + return _maxElements; + } + + /** + * tickles the object so that it won't expire for another default expiration period. true is returned if the object was there and got + * updated. + */ + public boolean refresh(KeyType key) + { + synchronized (_map) { + RoleBasedCacheNode node = _map.get(key); + if (node == null) + return false; + _lruList.remove(node); + node.setInvalidationDate(_defaultTimeoutMS); + // move the node to the end of the LRU list, since we just accessed it. + _lruList.insert(node); + // also fix its position in the timeout list. + _timeoutList.remove(node); + _timeoutList.insert(node); + return true; + } + } + + // hmmm: highly experimental memory analysis code here! + // private final long CHECK_INTERVAL = 1000 * 60; // one minute interval between deep checks currently. + private final long CHECK_INTERVAL = 1000 * 10;// hmmm: way too fast interval, being used for debugging. + + private Date _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL); + + public DataType get(KeyType key) + { + Date now = new Date(); + + if (now.after(_nextDeepSizeCheck)) { + + /* + * hmmm: size check code below, not right yet. + * + * would be nice to break that output into k, m, g, etc. + * + * trying the deep footprint on 'this' is giving unrealistic very small sizes. + * + * also the deep size check is dying with a stack overflow during the large rns directory test, so we cannot use it yet. + */ + // if (_logger.isDebugEnabled()) { + // long sizeUsed = MemoryFootprint.getDeepFootprint(_map) + MemoryFootprint.getDeepFootprint(_lruList) + // + MemoryFootprint.getDeepFootprint(_timeoutList); + // _logger.debug(SizeOf.humanReadable(sizeUsed) + " consumed by "+ _cacheName); + // } + + _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL); + } + + synchronized (_map) { + RoleBasedCacheNode node = _map.get(key); + if (node == null) + return null; + _lruList.remove(node); + if (node.getInvalidationDate().before(now)) { + // this entry has become stale. + if (_logCacheEjection && _logger.isDebugEnabled()) + _logger.debug(debugPrefix() + "timed-out entry in get: removing cached item with key: " + node.getKey()); + _map.remove(key); + _timeoutList.remove(node); + return null; + } + // move the node to the end of the LRU list, since we just accessed it. + _lruList.insert(node); + return node.getData(); + } + } + + public List getAll() + { + ArrayList toReturn = new ArrayList(); + synchronized (_map) { + for (KeyType key : _map.keySet()) { + toReturn.add(_map.get(key).getData()); + } + } + return toReturn; + } + + public List getAllReferenced(List references) + { + ArrayList toReturn = new ArrayList(); + synchronized (_map) { + for (KeyType key : references) { + //// for (KeyType key : _map.keySet()) { + if (_map.containsKey(key)) { + toReturn.add(_map.get(key).getData()); + } else { + _logger.error(debugPrefix() + "failed to locate referenced object in cache: " + key); + } + } + } + return toReturn; + } + + public void clearStale() + { + Date now = new Date(); + + synchronized (_map) { + while (true) { + RoleBasedCacheNode node = _timeoutList.peekFirst(); + if (node == null) + break; + + if (node.getInvalidationDate().compareTo(now) <= 0) { + if (_logCacheEjection && _logger.isDebugEnabled()) + _logger.debug(debugPrefix() + "removing timed-out node: " + node.getKey()); + _map.remove(node.getKey()); + _timeoutList.removeFirst(); + _lruList.remove(node); + } else { + break; + } + } + } + } + + public void remove(KeyType key) + { + synchronized (_map) { + RoleBasedCacheNode node = _map.remove(key); + if (node != null) { + _lruList.remove(node); + _timeoutList.remove(node); + } + } + } + + public Set keySet() + { + synchronized (_map) { + return new HashSet(_map.keySet()); + } + } + + public void clear() + { + synchronized (_map) { + _map.clear(); + _lruList.clear(); + _timeoutList.clear(); + } + } + + public void startActiveTimeout() + { + _activeTimeoutThread = new Thread(new ActiveTimeoutWorker(), "Active Cache Timeout Thread"); + _activeTimeoutThread.setDaemon(true); + _activeTimeoutThread.start(); + } + + public void stopActiveTimeout() + { + Thread tmp = _activeTimeoutThread; + _activeTimeoutThread = null; + synchronized (_map) { + _map.notify(); + } + + try { + tmp.join(); + } catch (InterruptedException cause) { + } + } + + private class ActiveTimeoutWorker implements Runnable + { + public void run() + { + synchronized (_map) { + while (_activeTimeoutThread != null) { + try { + clearStale(); + RoleBasedCacheNode firstNode = _timeoutList.peekFirst(); + if (firstNode == null) { + _map.wait(); + } else { + Date nextStale = firstNode.getInvalidationDate(); + long timeout = nextStale.getTime() - System.currentTimeMillis(); + if (timeout > 0) { + _map.wait(timeout); + } + } + } catch (InterruptedException ie) { + } + } + } + } + } +} \ No newline at end of file