kona/src/org/gffs/cache/TimedOutLRUCache.java

   1 package org.gffs.cache;
   2
   3 /*
   4  * Copyright 2006 University of Virginia
   5  *
   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
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  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.
  14  */
  15
  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;
  21 import java.util.Set;
  22
  23 import org.apache.commons.logging.Log;
  24 import org.apache.commons.logging.LogFactory;
  25
  26 /**
  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.
  33  *
  34  * @author mmm2a
  35  *
  36  * @param <KeyType>
  37  * @param <DataType>
  38  */
  39 public class TimedOutLRUCache<KeyType, DataType>
  40 {
  41         static Log _logger = LogFactory.getLog(TimedOutLRUCache.class);
  42
  43         private HashMap<KeyType, RoleBasedCacheNode<KeyType, DataType>> _map;
  44         private LRUList<KeyType, DataType> _lruList;
  45         private TimeoutList<KeyType, DataType> _timeoutList;
  46
  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.
  52
  53         public TimedOutLRUCache(int maxElements, long defaultTimeoutMS, String cacheName)
  54         {
  55                 if (maxElements < 1)
  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");
  60
  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>();
  66         }
  67
  68         /**
  69          * returns the number of elements held in the cache currently.
  70          */
  71         public int size()
  72         {
  73                 return _map.size();
  74         }
  75
  76         /**
  77          * allows this cache to log when items are removed due to overloading or timing out.
  78          */
  79         public void setCacheEjectionLogging(boolean logRemovals)
  80         {
  81                 _logCacheEjection = logRemovals;
  82         }
  83
  84         public void activelyTimeoutElements(boolean activelyTimeout)
  85         {
  86                 synchronized (_map) {
  87                         if (_activeTimeoutThread == null) {
  88                                 if (activelyTimeout)
  89                                         startActiveTimeout();
  90                         } else {
  91                                 if (!activelyTimeout)
  92                                         stopActiveTimeout();
  93                         }
  94                 }
  95         }
  96
  97         public String debugPrefix()
  98         {
  99                 return _cacheName + ": ";
 100         }
 101
 102         public void put(KeyType key, DataType data, long timeoutMS)
 103         {
 104                 RoleBasedCacheNode<KeyType, DataType> newNode =
 105                         new RoleBasedCacheNode<KeyType, DataType>(key, data, new Date(System.currentTimeMillis() + timeoutMS));
 106
 107                 synchronized (_map) {
 108                         RoleBasedCacheNode<KeyType, DataType> oldNode = _map.remove(key);
 109                         if (oldNode != null) {
 110                                 _lruList.remove(oldNode);
 111                                 _timeoutList.remove(oldNode);
 112                         }
 113
 114                         if (_map.size() >= _maxElements)
 115                                 clearStale();
 116
 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());
 123                         }
 124
 125                         _map.put(key, newNode);
 126                         _lruList.insert(newNode);
 127                         _timeoutList.insert(newNode);
 128
 129                         _map.notify();
 130                 }
 131         }
 132
 133         public void put(KeyType key, DataType data)
 134         {
 135                 put(key, data, _defaultTimeoutMS);
 136         }
 137
 138         public int getMaximumElements()
 139         {
 140                 return _maxElements;
 141         }
 142
 143         /**
 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
 145          * updated.
 146          */
 147         public boolean refresh(KeyType key)
 148         {
 149                 synchronized (_map) {
 150                         RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
 151                         if (node == null)
 152                                 return false;
 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);
 160                         return true;
 161                 }
 162         }
 163
 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.
 167
 168         private Date _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
 169
 170         public DataType get(KeyType key)
 171         {
 172                 Date now = new Date();
 173
 174                 if (now.after(_nextDeepSizeCheck)) {
 175
 176                         /*
 177                          * hmmm: size check code below, not right yet.
 178                          *
 179                          * would be nice to break that output into k, m, g, etc.
 180                          *
 181                          * trying the deep footprint on 'this' is giving unrealistic very small sizes.
 182                          *
 183                          * also the deep size check is dying with a stack overflow during the large rns directory test, so we cannot use it yet.
 184                          */
 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);
 189                         // }
 190
 191                         _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
 192                 }
 193
 194                 synchronized (_map) {
 195                         RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
 196                         if (node == null)
 197                                 return null;
 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());
 203                                 _map.remove(key);
 204                                 _timeoutList.remove(node);
 205                                 return null;
 206                         }
 207                         // move the node to the end of the LRU list, since we just accessed it.
 208                         _lruList.insert(node);
 209                         return node.getData();
 210                 }
 211         }
 212
 213         public List<DataType> getAll()
 214         {
 215                 ArrayList<DataType> toReturn = new ArrayList<DataType>();
 216                 synchronized (_map) {
 217                         for (KeyType key : _map.keySet()) {
 218                                 toReturn.add(_map.get(key).getData());
 219                         }
 220                 }
 221                 return toReturn;
 222         }
 223
 224         public List<DataType> getAllReferenced(List<KeyType> references)
 225         {
 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());
 232                                 } else {
 233                                         _logger.error(debugPrefix() + "failed to locate referenced object in cache: " + key);
 234                                 }
 235                         }
 236                 }
 237                 return toReturn;
 238         }
 239
 240         public void clearStale()
 241         {
 242                 Date now = new Date();
 243
 244                 synchronized (_map) {
 245                         while (true) {
 246                                 RoleBasedCacheNode<KeyType, DataType> node = _timeoutList.peekFirst();
 247                                 if (node == null)
 248                                         break;
 249
 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);
 256                                 } else {
 257                                         break;
 258                                 }
 259                         }
 260                 }
 261         }
 262
 263         public void remove(KeyType key)
 264         {
 265                 synchronized (_map) {
 266                         RoleBasedCacheNode<KeyType, DataType> node = _map.remove(key);
 267                         if (node != null) {
 268                                 _lruList.remove(node);
 269                                 _timeoutList.remove(node);
 270                         }
 271                 }
 272         }
 273
 274         public Set<KeyType> keySet()
 275         {
 276                 synchronized (_map) {
 277                         return new HashSet<KeyType>(_map.keySet());
 278                 }
 279         }
 280
 281         public void clear()
 282         {
 283                 synchronized (_map) {
 284                         _map.clear();
 285                         _lruList.clear();
 286                         _timeoutList.clear();
 287                 }
 288         }
 289
 290         public void startActiveTimeout()
 291         {
 292                 _activeTimeoutThread = new Thread(new ActiveTimeoutWorker(), "Active Cache Timeout Thread");
 293                 _activeTimeoutThread.setDaemon(true);
 294                 _activeTimeoutThread.start();
 295         }
 296
 297         public void stopActiveTimeout()
 298         {
 299                 Thread tmp = _activeTimeoutThread;
 300                 _activeTimeoutThread = null;
 301                 synchronized (_map) {
 302                         _map.notify();
 303                 }
 304
 305                 try {
 306                         tmp.join();
 307                 } catch (InterruptedException cause) {
 308                 }
 309         }
 310
 311         private class ActiveTimeoutWorker implements Runnable
 312         {
 313                 public void run()
 314                 {
 315                         synchronized (_map) {
 316                                 while (_activeTimeoutThread != null) {
 317                                         try {
 318                                                 clearStale();
 319                                                 RoleBasedCacheNode<KeyType, DataType> firstNode = _timeoutList.peekFirst();
 320                                                 if (firstNode == null) {
 321                                                         _map.wait();
 322                                                 } else {
 323                                                         Date nextStale = firstNode.getInvalidationDate();
 324                                                         long timeout = nextStale.getTime() - System.currentTimeMillis();
 325                                                         if (timeout > 0) {
 326                                                                 _map.wait(timeout);
 327                                                         }
 328                                                 }
 329                                         } catch (InterruptedException ie) {
 330                                         }
 331                                 }
 332                         }
 333                 }
 334         }
 335 }