KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jboss > cache > eviction > BaseEvictionAlgorithm


1 /*
2  * JBoss, the OpenSource J2EE webOS
3  *
4  * Distributable under LGPL license.
5  * See terms of license at gnu.org.
6  */
7 package org.jboss.cache.eviction;
8
9 import org.apache.commons.logging.Log;
10 import org.apache.commons.logging.LogFactory;
11 import org.jboss.cache.Fqn;
12 import org.jboss.cache.Region;
13 import org.jboss.cache.lock.TimeoutException;
14
15 import java.util.concurrent.BlockingQueue JavaDoc;
16 import java.util.concurrent.LinkedBlockingQueue JavaDoc;
17 import java.util.concurrent.TimeUnit JavaDoc;
18
19 /**
20  * Abstract Event Processing Eviction Algorithm.
21  * This class is used to implement basic event processing for Eviction Algorithms.
22  * To extend this abstract class to make an Eviction Algorithm, implement the
23  * abstract methods and a policy.
24  *
25  * @author Daniel Huang - dhuang@jboss.org 10/2005
26  * @version $Revision: 1.19 $
27  */
28 public abstract class BaseEvictionAlgorithm implements EvictionAlgorithm
29 {
30    private static final Log log = LogFactory.getLog(BaseEvictionAlgorithm.class);
31
32    /**
33     * Mapped region.
34     */
35    protected Region region;
36
37    /**
38     * Contains Fqn instances.
39     */
40    protected BlockingQueue JavaDoc recycleQueue;
41
42    /**
43     * Contains NodeEntry instances.
44     */
45    protected EvictionQueue evictionQueue;
46
47    /**
48     * This method will create an EvictionQueue implementation and prepare it for use.
49     *
50     * @param region MarshRegion to setup an eviction queue for.
51     * @return The created EvictionQueue to be used as the eviction queue for this algorithm.
52     * @throws EvictionException
53     * @see EvictionQueue
54     */
55    protected abstract EvictionQueue setupEvictionQueue(Region region) throws EvictionException;
56
57    /**
58     * This method will check whether the given node should be evicted or not.
59     *
60     * @param ne NodeEntry to test eviction for.
61     * @return True if the given node should be evicted. False if the given node should not be evicted.
62     */
63    protected abstract boolean shouldEvictNode(NodeEntry ne);
64
65    protected BaseEvictionAlgorithm()
66    {
67       recycleQueue = new LinkedBlockingQueue JavaDoc(500000);
68    }
69
70    protected void initialize(Region region) throws EvictionException
71    {
72       if (region == null)
73          throw new IllegalArgumentException JavaDoc("region");
74       this.region = region;
75       evictionQueue = setupEvictionQueue(region);
76       log.debug("initialized: " + this);
77    }
78
79    /**
80     * Process the given region.
81     * <p/>
82     * Eviction Processing encompasses the following:
83     * <p/>
84     * - Add/Remove/Visit Nodes
85     * - Prune according to Eviction Algorithm
86     * - Empty/Retry the recycle queue of previously evicted but locked (during actual cache eviction) nodes.
87     *
88     * @param region Cache region to process for eviction.
89     * @throws EvictionException
90     */
91    public void process(Region region) throws EvictionException
92    {
93       if (this.region == null)
94       {
95          this.initialize(region);
96       }
97
98       if (log.isTraceEnabled())
99       {
100          log.trace("process(): region: " + region.getFqn());
101       }
102
103       this.processQueues(region);
104       this.emptyRecycleQueue();
105       this.prune();
106    }
107
108    public void resetEvictionQueue(Region region)
109    {
110    }
111
112    /**
113     * Get the underlying EvictionQueue implementation.
114     *
115     * @return the EvictionQueue used by this algorithm
116     * @see EvictionQueue
117     */
118    public EvictionQueue getEvictionQueue()
119    {
120       return this.evictionQueue;
121    }
122
123    /**
124     * Event processing for Evict/Add/Visiting of nodes.
125     * <p/>
126     * - On AddEvents a new element is added into the eviction queue
127     * - On RemoveEvents, the removed element is removed from the eviction queue.
128     * - On VisitEvents, the visited node has its eviction statistics updated (idleTime, numberOfNodeVisists, etc..)
129     *
130     * @param region Cache region to process for eviction.
131     * @throws EvictionException
132     */
133    protected void processQueues(Region region) throws EvictionException
134    {
135       EvictedEventNode node;
136       int count = 0;
137       while ((node = region.takeLastEventNode()) != null)
138       {
139          Fqn fqn = node.getFqn();
140
141          count++;
142          switch (node.getEventType())
143          {
144             case ADD_NODE_EVENT:
145                this.processAddedNodes(fqn,
146                        node.getElementDifference(),
147                        node.isResetElementCount());
148                break;
149             case REMOVE_NODE_EVENT:
150                this.processRemovedNodes(fqn);
151                break;
152             case VISIT_NODE_EVENT:
153                this.processVisitedNodes(fqn);
154                break;
155             case ADD_ELEMENT_EVENT:
156                this.processAddedElement(fqn);
157                break;
158             case REMOVE_ELEMENT_EVENT:
159                this.processRemovedElement(fqn);
160                break;
161             case MARK_IN_USE_EVENT:
162                this.processMarkInUseNodes(fqn, node.getInUseTimeout());
163                break;
164             case UNMARK_USE_EVENT:
165                this.processUnmarkInUseNodes(fqn);
166                break;
167             default:
168                throw new RuntimeException JavaDoc("Illegal Eviction Event type " + node.getEventType());
169          }
170       }
171
172       if (log.isTraceEnabled())
173       {
174          log.trace("processed " + count + " node events in region: " + region.getFqn());
175       }
176
177    }
178
179    protected void evict(NodeEntry ne)
180    {
181 // NodeEntry ne = evictionQueue.getNodeEntry(fqn);
182 if (ne != null)
183       {
184          evictionQueue.removeNodeEntry(ne);
185          if (!this.evictCacheNode(ne.getFqn()))
186          {
187             try
188             {
189                recycleQueue.put(ne.getFqn());
190             }
191             catch (InterruptedException JavaDoc e)
192             {
193                log.debug("InterruptedException", e);
194             }
195          }
196       }
197    }
198
199    /**
200     * Evict a node from cache.
201     *
202     * @param fqn node corresponds to this fqn
203     * @return True if successful
204     */
205    protected boolean evictCacheNode(Fqn fqn)
206    {
207       if (log.isTraceEnabled())
208       {
209          log.trace("Attempting to evict cache node with fqn of " + fqn);
210       }
211       EvictionPolicy policy = region.getEvictionPolicy();
212       // Do an eviction of this node
213
214       try
215       {
216          policy.evict(fqn);
217       }
218       catch (Exception JavaDoc e)
219       {
220          if (e instanceof TimeoutException)
221          {
222             log.warn("eviction of " + fqn + " timed out. Will retry later.");
223             return false;
224          }
225          e.printStackTrace();
226          return false;
227       }
228
229       if (log.isTraceEnabled())
230       {
231          log.trace("Eviction of cache node with fqn of " + fqn + " successful");
232       }
233
234       return true;
235    }
236
237    protected void processMarkInUseNodes(Fqn fqn, long inUseTimeout) throws EvictionException
238    {
239       if (log.isTraceEnabled())
240       {
241          log.trace("Marking node " + fqn + " as in use with a usage timeout of " + inUseTimeout);
242       }
243
244       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
245       if (ne != null)
246       {
247          ne.setCurrentlyInUse(true, inUseTimeout);
248       }
249    }
250
251    protected void processUnmarkInUseNodes(Fqn fqn) throws EvictionException
252    {
253       if (log.isTraceEnabled())
254       {
255          log.trace("Unmarking node " + fqn + " as in use");
256       }
257
258       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
259       if (ne != null)
260       {
261          ne.setCurrentlyInUse(false, 0);
262       }
263    }
264
265    protected void processAddedNodes(Fqn fqn, int numAddedElements, boolean resetElementCount) throws EvictionException
266    {
267       if (log.isTraceEnabled())
268       {
269          log.trace("Adding node " + fqn + " with " + numAddedElements + " elements to eviction queue");
270       }
271
272       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
273       if (ne != null)
274       {
275          ne.setModifiedTimeStamp(System.currentTimeMillis());
276          ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
277          if (resetElementCount)
278          {
279             ne.setNumberOfElements(numAddedElements);
280          }
281          else
282          {
283             ne.setNumberOfElements(ne.getNumberOfElements() + numAddedElements);
284          }
285          return;
286       }
287
288       long stamp = System.currentTimeMillis();
289       ne = new NodeEntry(fqn);
290       ne.setModifiedTimeStamp(stamp);
291       ne.setNumberOfNodeVisits(1);
292       ne.setNumberOfElements(numAddedElements);
293       // add it to the node map and eviction queue
294 if (evictionQueue.containsNodeEntry(ne))
295       {
296          if (log.isTraceEnabled())
297          {
298             log.trace("Queue already contains " + ne.getFqn() + " processing it as visited");
299          }
300          this.processVisitedNodes(ne.getFqn());
301          return;
302       }
303
304       evictionQueue.addNodeEntry(ne);
305
306       if (log.isTraceEnabled())
307       {
308          log.trace(ne.getFqn() + " added successfully to eviction queue");
309       }
310    }
311
312    /**
313     * Remove a node from cache.
314     * <p/>
315     * This method will remove the node from the eviction queue as well as
316     * evict the node from cache.
317     * <p/>
318     * If a node cannot be removed from cache, this method will remove it from the eviction queue
319     * and place the element into the recycleQueue. Each node in the recycle queue will get retried until
320     * proper cache eviction has taken place.
321     * <p/>
322     * Because EvictionQueues are collections, when iterating them from an iterator, use iterator.remove()
323     * to avoid ConcurrentModificationExceptions. Use the boolean parameter to indicate the calling context.
324     *
325     * @param fqn FQN of the removed node
326     * @throws EvictionException
327     */
328    protected void processRemovedNodes(Fqn fqn) throws EvictionException
329    {
330       if (log.isTraceEnabled())
331       {
332          log.trace("Removing node " + fqn + " from eviction queue and attempting eviction");
333       }
334
335       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
336       if (ne != null)
337       {
338          evictionQueue.removeNodeEntry(ne);
339       }
340       else
341       {
342          if (log.isDebugEnabled())
343          {
344             log.debug("processRemoveNodes(): Can't find node associated with fqn: " + fqn
345                     + "Could have been evicted earlier. Will just continue.");
346          }
347          return;
348       }
349
350       if (log.isTraceEnabled())
351       {
352          log.trace(fqn + " removed from eviction queue");
353       }
354    }
355
356    /**
357     * Visit a node in cache.
358     * <p/>
359     * This method will update the numVisits and modifiedTimestamp properties of the Node.
360     * These properties are used as statistics to determine eviction (LRU, LFU, MRU, etc..)
361     * <p/>
362     * *Note* that this method updates Node Entries by reference and does not put them back
363     * into the queue. For some sorted collections, a remove, and a re-add is required to
364     * maintain the sorted order of the elements.
365     *
366     * @param fqn FQN of the visited node.
367     * @throws EvictionException
368     */
369    protected void processVisitedNodes(Fqn fqn) throws EvictionException
370    {
371       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
372       if (ne == null)
373       {
374          if (log.isDebugEnabled())
375          {
376             log.debug("Visiting node that was not added to eviction queues. Assuming that it has 1 element.");
377          }
378          this.processAddedNodes(fqn, 1, false);
379          return;
380       }
381       // note this method will visit and modify the node statistics by reference!
382 // if a collection is only guaranteed sort order by adding to the collection,
383 // this implementation will not guarantee sort order.
384 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
385       ne.setModifiedTimeStamp(System.currentTimeMillis());
386    }
387
388    protected void processRemovedElement(Fqn fqn) throws EvictionException
389    {
390       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
391
392       if (ne == null)
393       {
394          if (log.isDebugEnabled())
395          {
396             log.debug("Removing element from " + fqn + " but eviction queue does not contain this node. " +
397                     "Ignoring removeElement event.");
398          }
399          return;
400       }
401
402       ne.setNumberOfElements(ne.getNumberOfElements() - 1);
403       // also treat it as a node visit.
404 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
405       ne.setModifiedTimeStamp(System.currentTimeMillis());
406    }
407
408    protected void processAddedElement(Fqn fqn) throws EvictionException
409    {
410       NodeEntry ne = evictionQueue.getNodeEntry(fqn);
411       if (ne == null)
412       {
413          if (log.isDebugEnabled())
414          {
415             log.debug("Adding element " + fqn + " for a node that doesn't exist yet. Process as an add.");
416          }
417          this.processAddedNodes(fqn, 1, false);
418          return;
419       }
420
421       ne.setNumberOfElements(ne.getNumberOfElements() + 1);
422
423       // also treat it as a node visit.
424 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
425       ne.setModifiedTimeStamp(System.currentTimeMillis());
426    }
427
428
429    /**
430     * Empty the Recycle Queue.
431     * <p/>
432     * This method will go through the recycle queue and retry to evict the nodes from cache.
433     *
434     * @throws EvictionException
435     */
436    protected void emptyRecycleQueue() throws EvictionException
437    {
438       while (true)
439       {
440          Fqn fqn;
441
442          try
443          {
444             //fqn = (Fqn) recycleQueue.take();
445 fqn = (Fqn) recycleQueue.poll(0, TimeUnit.SECONDS);
446          }
447          catch (InterruptedException JavaDoc e)
448          {
449             e.printStackTrace();
450             break;
451          }
452
453          if (fqn == null)
454          {
455             if (log.isTraceEnabled())
456             {
457                log.trace("Recycle queue is empty");
458             }
459             break;
460          }
461
462          if (log.isTraceEnabled())
463          {
464             log.trace("emptying recycle bin. Evict node " + fqn);
465          }
466
467          // Still doesn't work
468 if (!evictCacheNode(fqn))
469          {
470             try
471             {
472                recycleQueue.put(fqn);
473             }
474             catch (InterruptedException JavaDoc e)
475             {
476                e.printStackTrace();
477             }
478             break;
479          }
480       }
481    }
482
483    protected boolean isNodeInUseAndNotTimedOut(NodeEntry ne)
484    {
485       if (ne.isCurrentlyInUse())
486       {
487          if (ne.getInUseTimeoutTimestamp() == 0)
488          {
489             return true;
490          }
491
492          if (System.currentTimeMillis() < ne.getInUseTimeoutTimestamp())
493          {
494             return true;
495          }
496       }
497       return false;
498    }
499
500
501    protected void prune() throws EvictionException
502    {
503       NodeEntry entry;
504       while ((entry = evictionQueue.getFirstNodeEntry()) != null)
505       {
506          if (this.shouldEvictNode(entry))
507          {
508             this.evict(entry);
509          }
510          else
511          {
512             break;
513          }
514       }
515    }
516
517    /**
518     * Returns debug information.
519     */
520    public String JavaDoc toString()
521    {
522       return super.toString() +
523               " reqion=" + region.getFqn() +
524               " recycle=" + recycleQueue.size() +
525               " evict=" + evictionQueue.getNumberOfNodes();
526    }
527
528 }
529
Popular Tags