1 package org.gffs.cache;
4 * Copyright 2006 University of Virginia
6 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may
7 * obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions
13 * and limitations under the License.
16 import java.util.ArrayList;
17 import java.util.Date;
18 import java.util.HashMap;
19 import java.util.HashSet;
20 import java.util.List;
23 import org.apache.commons.logging.Log;
24 import org.apache.commons.logging.LogFactory;
27 * This cache attempt to efficiently handle cached items that may time out after a certain period of time. It does this by maintaining 3
28 * 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
29 * 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
30 * identified quickly (i.e., a straight traversal of this list). All data structures share the exact same data node (not equivalent, but
31 * identical instances of the node class). This means that once a node is identified through any of the means indicated (key, LRU property,
32 * timeout property), the node for all three data structures has been identified and does not need to be looked up in the others.
39 public class TimedOutLRUCache<KeyType, DataType>
41 static Log _logger = LogFactory.getLog(TimedOutLRUCache.class);
43 private HashMap<KeyType, RoleBasedCacheNode<KeyType, DataType>> _map;
44 private LRUList<KeyType, DataType> _lruList;
45 private TimeoutList<KeyType, DataType> _timeoutList;
47 private int _maxElements;
48 private long _defaultTimeoutMS;
49 private Thread _activeTimeoutThread = null;
50 private boolean _logCacheEjection = false;
51 public String _cacheName = null; // the name for this cache.
53 public TimedOutLRUCache(int maxElements, long defaultTimeoutMS, String cacheName)
56 throw new IllegalArgumentException("\"maxElements\" must be greater than 0.");
57 _cacheName = cacheName;
58 if (_cacheName == null)
59 throw new IllegalArgumentException("must provide a non-null cache name");
61 _maxElements = maxElements;
62 _defaultTimeoutMS = defaultTimeoutMS;
63 _map = new HashMap<KeyType, RoleBasedCacheNode<KeyType, DataType>>(_maxElements);
64 _lruList = new LRUList<KeyType, DataType>();
65 _timeoutList = new TimeoutList<KeyType, DataType>();
69 * returns the number of elements held in the cache currently.
77 * allows this cache to log when items are removed due to overloading or timing out.
79 public void setCacheEjectionLogging(boolean logRemovals)
81 _logCacheEjection = logRemovals;
84 public void activelyTimeoutElements(boolean activelyTimeout)
87 if (_activeTimeoutThread == null) {
97 public String debugPrefix()
99 return _cacheName + ": ";
102 public void put(KeyType key, DataType data, long timeoutMS)
104 RoleBasedCacheNode<KeyType, DataType> newNode =
105 new RoleBasedCacheNode<KeyType, DataType>(key, data, new Date(System.currentTimeMillis() + timeoutMS));
107 synchronized (_map) {
108 RoleBasedCacheNode<KeyType, DataType> oldNode = _map.remove(key);
109 if (oldNode != null) {
110 _lruList.remove(oldNode);
111 _timeoutList.remove(oldNode);
114 if (_map.size() >= _maxElements)
117 while (_map.size() >= _maxElements) {
118 RoleBasedCacheNode<KeyType, DataType> node = _lruList.removeFirst();
119 if (_logCacheEjection && _logger.isDebugEnabled())
120 _logger.debug(debugPrefix() + "overloaded cache: removing cached item with key: " + node.getKey());
121 _timeoutList.remove(node);
122 _map.remove(node.getKey());
125 _map.put(key, newNode);
126 _lruList.insert(newNode);
127 _timeoutList.insert(newNode);
133 public void put(KeyType key, DataType data)
135 put(key, data, _defaultTimeoutMS);
138 public int getMaximumElements()
144 * tickles the object so that it won't expire for another default expiration period. true is returned if the object was there and got
147 public boolean refresh(KeyType key)
149 synchronized (_map) {
150 RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
153 _lruList.remove(node);
154 node.setInvalidationDate(_defaultTimeoutMS);
155 // move the node to the end of the LRU list, since we just accessed it.
156 _lruList.insert(node);
157 // also fix its position in the timeout list.
158 _timeoutList.remove(node);
159 _timeoutList.insert(node);
164 // hmmm: highly experimental memory analysis code here!
165 // private final long CHECK_INTERVAL = 1000 * 60; // one minute interval between deep checks currently.
166 private final long CHECK_INTERVAL = 1000 * 10;// hmmm: way too fast interval, being used for debugging.
168 private Date _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
170 public DataType get(KeyType key)
172 Date now = new Date();
174 if (now.after(_nextDeepSizeCheck)) {
177 * hmmm: size check code below, not right yet.
179 * would be nice to break that output into k, m, g, etc.
181 * trying the deep footprint on 'this' is giving unrealistic very small sizes.
183 * also the deep size check is dying with a stack overflow during the large rns directory test, so we cannot use it yet.
185 // if (_logger.isDebugEnabled()) {
186 // long sizeUsed = MemoryFootprint.getDeepFootprint(_map) + MemoryFootprint.getDeepFootprint(_lruList)
187 // + MemoryFootprint.getDeepFootprint(_timeoutList);
188 // _logger.debug(SizeOf.humanReadable(sizeUsed) + " consumed by "+ _cacheName);
191 _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
194 synchronized (_map) {
195 RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
198 _lruList.remove(node);
199 if (node.getInvalidationDate().before(now)) {
200 // this entry has become stale.
201 if (_logCacheEjection && _logger.isDebugEnabled())
202 _logger.debug(debugPrefix() + "timed-out entry in get: removing cached item with key: " + node.getKey());
204 _timeoutList.remove(node);
207 // move the node to the end of the LRU list, since we just accessed it.
208 _lruList.insert(node);
209 return node.getData();
213 public List<DataType> getAll()
215 ArrayList<DataType> toReturn = new ArrayList<DataType>();
216 synchronized (_map) {
217 for (KeyType key : _map.keySet()) {
218 toReturn.add(_map.get(key).getData());
224 public List<DataType> getAllReferenced(List<KeyType> references)
226 ArrayList<DataType> toReturn = new ArrayList<DataType>();
227 synchronized (_map) {
228 for (KeyType key : references) {
229 //// for (KeyType key : _map.keySet()) {
230 if (_map.containsKey(key)) {
231 toReturn.add(_map.get(key).getData());
233 _logger.error(debugPrefix() + "failed to locate referenced object in cache: " + key);
240 public void clearStale()
242 Date now = new Date();
244 synchronized (_map) {
246 RoleBasedCacheNode<KeyType, DataType> node = _timeoutList.peekFirst();
250 if (node.getInvalidationDate().compareTo(now) <= 0) {
251 if (_logCacheEjection && _logger.isDebugEnabled())
252 _logger.debug(debugPrefix() + "removing timed-out node: " + node.getKey());
253 _map.remove(node.getKey());
254 _timeoutList.removeFirst();
255 _lruList.remove(node);
263 public void remove(KeyType key)
265 synchronized (_map) {
266 RoleBasedCacheNode<KeyType, DataType> node = _map.remove(key);
268 _lruList.remove(node);
269 _timeoutList.remove(node);
274 public Set<KeyType> keySet()
276 synchronized (_map) {
277 return new HashSet<KeyType>(_map.keySet());
283 synchronized (_map) {
286 _timeoutList.clear();
290 public void startActiveTimeout()
292 _activeTimeoutThread = new Thread(new ActiveTimeoutWorker(), "Active Cache Timeout Thread");
293 _activeTimeoutThread.setDaemon(true);
294 _activeTimeoutThread.start();
297 public void stopActiveTimeout()
299 Thread tmp = _activeTimeoutThread;
300 _activeTimeoutThread = null;
301 synchronized (_map) {
307 } catch (InterruptedException cause) {
311 private class ActiveTimeoutWorker implements Runnable
315 synchronized (_map) {
316 while (_activeTimeoutThread != null) {
319 RoleBasedCacheNode<KeyType, DataType> firstNode = _timeoutList.peekFirst();
320 if (firstNode == null) {
323 Date nextStale = firstNode.getInvalidationDate();
324 long timeout = nextStale.getTime() - System.currentTimeMillis();
329 } catch (InterruptedException ie) {