View Javadoc

1   package org.apache.jcs.engine.memory.lru;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *   http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import java.io.IOException;
23  import java.io.Serializable;
24  import java.util.ArrayList;
25  import java.util.Iterator;
26  import java.util.Map;
27  import java.util.NoSuchElementException;
28  
29  import org.apache.commons.logging.Log;
30  import org.apache.commons.logging.LogFactory;
31  import org.apache.jcs.engine.CacheConstants;
32  import org.apache.jcs.engine.CacheElement;
33  import org.apache.jcs.engine.behavior.ICacheElement;
34  import org.apache.jcs.engine.control.CompositeCache;
35  import org.apache.jcs.engine.control.group.GroupAttrName;
36  import org.apache.jcs.engine.control.group.GroupId;
37  import org.apache.jcs.engine.memory.AbstractMemoryCache;
38  import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
39  import org.apache.jcs.engine.stats.StatElement;
40  import org.apache.jcs.engine.stats.Stats;
41  import org.apache.jcs.engine.stats.behavior.IStatElement;
42  import org.apache.jcs.engine.stats.behavior.IStats;
43  import org.apache.jcs.utils.struct.DoubleLinkedList;
44  
45  /***
46   * A fast reference management system. The least recently used items move to the end of the list and
47   * get spooled to disk if the cache hub is configured to use a disk cache. Most of the cache
48   * bottelnecks are in IO. There are no io bottlenecks here, it's all about processing power.
49   * <p>
50   * Even though there are only a few adjustments necessary to maintain the double linked list, we
51   * might want to find a more efficient memory manager for large cache regions.
52   * <p>
53   * The LRUMemoryCache is most efficient when the first element is selected. The smaller the region,
54   * the better the chance that this will be the case. < .04 ms per put, p3 866, 1/10 of that per get
55   * <p>
56   * @version $Id: LRUMemoryCache.java 536904 2007-05-10 16:03:42Z tv $
57   */
58  public class LRUMemoryCache
59      extends AbstractMemoryCache
60  {
61      /*** Don't change */
62      private static final long serialVersionUID = 6403738094136424201L;
63  
64      /*** The logger. */
65      private final static Log log = LogFactory.getLog( LRUMemoryCache.class );
66  
67      /*** thread-safe double linked list for lru */
68      private DoubleLinkedList list;
69  
70      /*** number of hits */
71      private int hitCnt = 0;
72  
73      /*** number of misses */
74      private int missCnt = 0;
75  
76      /*** number of puts */
77      private int putCnt = 0;
78  
79      /***
80       * For post reflection creation initialization.
81       * <p>
82       * @param hub
83       */
84      public synchronized void initialize( CompositeCache hub )
85      {
86          super.initialize( hub );
87          list = new DoubleLinkedList();
88          log.info( "initialized LRUMemoryCache for " + cacheName );
89      }
90  
91      /***
92       * Puts an item to the cache. Removes any pre-existing entries of the same key from the linked
93       * list and adds this one first.
94       * <p>
95       * If the max size is reached, an element will be put to disk.
96       * <p>
97       * @param ce The cache element, or entry wrapper
98       * @exception IOException
99       */
100     public void update( ICacheElement ce )
101         throws IOException
102     {
103         putCnt++;
104 
105         // Asynchronously create a MemoryElement
106 
107         ce.getElementAttributes().setLastAccessTimeNow();
108         MemoryElementDescriptor old = null;
109         synchronized ( this )
110         {
111             // TODO address double synchronization of addFirst, use write lock
112             addFirst( ce );
113             // this must be synchronized
114             old = (MemoryElementDescriptor) map.put( ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey(), list
115                 .getFirst() );
116             // If the node was the same as an existing node, remove it.
117             if ( old != null && ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey().equals( old.ce.getKey() ) )
118             {
119                 list.remove( old );
120             }
121         }
122 
123         int size = map.size();
124         // If the element limit is reached, we need to spool
125 
126         if ( size < this.cattr.getMaxObjects() )
127         {
128             return;
129         }
130 
131         if ( log.isDebugEnabled() )
132         {
133             log.debug( "In memory limit reached, spooling" );
134         }
135 
136         // Write the last 'chunkSize' items to disk.
137         int chunkSizeCorrected = Math.min( size, chunkSize );
138 
139         if ( log.isDebugEnabled() )
140         {
141             log.debug( "About to spool to disk cache, map size: " + size + ", max objects: "
142                 + this.cattr.getMaxObjects() + ", items to spool: " + chunkSizeCorrected );
143         }
144 
145         // The spool will put them in a disk event queue, so there is no
146         // need to pre-queue the queuing. This would be a bit wasteful
147         // and wouldn't save much time in this synchronous call.
148 
149         for ( int i = 0; i < chunkSizeCorrected; i++ )
150         {
151             spoolLastElement();
152         }
153 
154         if ( log.isDebugEnabled() )
155         {
156             log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() );
157         }
158 
159     }
160 
161     /***
162      * This spools the last element in the LRU, if one exists.
163      * <p>
164      * @return ICacheElement if there was a last element, else null.
165      * @throws Error
166      */
167     protected ICacheElement spoolLastElement()
168         throws Error
169     {
170         ICacheElement toSpool = null;
171         synchronized ( this )
172         {
173             if ( list.getLast() != null )
174             {
175                 toSpool = ( (MemoryElementDescriptor) list.getLast() ).ce;
176                 if ( toSpool != null )
177                 {
178                     cache.spoolToDisk( ( (MemoryElementDescriptor) list.getLast() ).ce );
179                     if ( !map.containsKey( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) )
180                     {
181                         log.error( "update: map does not contain key: "
182                             + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
183                         verifyCache();
184                     }
185                     if ( map.remove( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) == null )
186                     {
187                         log.warn( "update: remove failed for key: "
188                             + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
189                         verifyCache();
190                     }
191                 }
192                 else
193                 {
194                     throw new Error( "update: last.ce is null!" );
195                 }
196                 list.removeLast();
197             }
198             else
199             {
200                 verifyCache();
201                 throw new Error( "update: last is null!" );
202             }
203 
204             // If this is out of the sync block it can detect a mismatch
205             // where there is none.
206             if ( map.size() != dumpCacheSize() )
207             {
208                 log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = "
209                     + dumpCacheSize() );
210             }
211         }
212         return toSpool;
213     }
214 
215     /***
216      * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction
217      * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently
218      * used items. These will be spooled to disk if a disk auxiliary is available.
219      * <p>
220      * @param numberToFree
221      * @return the number that were removed. if you ask to free 5, but there are only 3, you will
222      *         get 3.
223      * @throws IOException
224      */
225     public int freeElements( int numberToFree )
226         throws IOException
227     {
228         int freed = 0;
229         for ( ; freed < numberToFree; freed++ )
230         {
231             ICacheElement element = spoolLastElement();
232             if ( element == null )
233             {
234                 break;
235             }
236         }
237         return freed;
238     }
239 
240     /***
241      * Get an item from the cache without affecting its last access time or position.
242      * <p>
243      * @param key Identifies item to find
244      * @return Element matching key if found, or null
245      * @exception IOException
246      */
247     public ICacheElement getQuiet( Serializable key )
248         throws IOException
249     {
250         ICacheElement ce = null;
251 
252         MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
253         if ( me != null )
254         {
255             if ( log.isDebugEnabled() )
256             {
257                 log.debug( cacheName + ": LRUMemoryCache quiet hit for " + key );
258             }
259 
260             ce = me.ce;
261         }
262         else if ( log.isDebugEnabled() )
263         {
264             log.debug( cacheName + ": LRUMemoryCache quiet miss for " + key );
265         }
266 
267         return ce;
268     }
269 
270     /***
271      * Get an item from the cache
272      * <p>
273      * @param key Identifies item to find
274      * @return ICacheElement if found, else null
275      * @exception IOException
276      */
277     public synchronized ICacheElement get( Serializable key )
278         throws IOException
279     {
280         ICacheElement ce = null;
281 
282         if ( log.isDebugEnabled() )
283         {
284             log.debug( "getting item from cache " + cacheName + " for key " + key );
285         }
286 
287         MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
288 
289         if ( me != null )
290         {
291             hitCnt++;
292             if ( log.isDebugEnabled() )
293             {
294                 log.debug( cacheName + ": LRUMemoryCache hit for " + key );
295             }
296 
297             ce = me.ce;
298 
299             ce.getElementAttributes().setLastAccessTimeNow();
300             list.makeFirst( me );
301         }
302         else
303         {
304             missCnt++;
305             if ( log.isDebugEnabled() )
306             {
307                 log.debug( cacheName + ": LRUMemoryCache miss for " + key );
308             }
309         }
310 
311         verifyCache();
312         return ce;
313     }
314 
315     /***
316      * Removes an item from the cache. This method handles hierarchical removal. If the key is a
317      * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys
318      * starting with the argument String will be removed.
319      * <p>
320      * @param key
321      * @return true if the removal was successful
322      * @exception IOException
323      */
324     public synchronized boolean remove( Serializable key )
325         throws IOException
326     {
327         if ( log.isDebugEnabled() )
328         {
329             log.debug( "removing item for key: " + key );
330         }
331 
332         boolean removed = false;
333 
334         // handle partial removal
335         if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) )
336         {
337             // remove all keys of the same name hierarchy.
338             synchronized ( map )
339             {
340                 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
341                 {
342                     Map.Entry entry = (Map.Entry) itr.next();
343                     Object k = entry.getKey();
344 
345                     if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) )
346                     {
347                         list.remove( (MemoryElementDescriptor) entry.getValue() );
348 
349                         itr.remove();
350 
351                         removed = true;
352                     }
353                 }
354             }
355         }
356         else if ( key instanceof GroupId )
357         {
358             // remove all keys of the same name hierarchy.
359             synchronized ( map )
360             {
361                 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
362                 {
363                     Map.Entry entry = (Map.Entry) itr.next();
364                     Object k = entry.getKey();
365 
366                     if ( k instanceof GroupAttrName && ( (GroupAttrName) k ).groupId.equals( key ) )
367                     {
368                         itr.remove();
369 
370                         list.remove( (MemoryElementDescriptor) entry.getValue() );
371 
372                         removed = true;
373                     }
374                 }
375             }
376         }
377         else
378         {
379             // remove single item.
380             MemoryElementDescriptor me = (MemoryElementDescriptor) map.remove( key );
381 
382             if ( me != null )
383             {
384                 list.remove( me );
385                 removed = true;
386             }
387         }
388 
389         return removed;
390     }
391 
392     /***
393      * Remove all of the elements from both the Map and the linked list implementation. Overrides
394      * base class.
395      * <p>
396      * @throws IOException
397      */
398     public synchronized void removeAll()
399         throws IOException
400     {
401         map.clear();
402         list.removeAll();
403     }
404 
405     // --------------------------- iteration mehods (iteration helpers)
406     /***
407      * iteration aid
408      */
409     public class IteratorWrapper
410         implements Iterator
411     {
412         // private final Log log = LogFactory.getLog( LRUMemoryCache.class );
413 
414         private final Iterator i;
415 
416         private IteratorWrapper( Map m )
417         {
418             i = m.entrySet().iterator();
419         }
420 
421         public boolean hasNext()
422         {
423             return i.hasNext();
424         }
425 
426         public Object next()
427         {
428             return new MapEntryWrapper( (Map.Entry) i.next() );
429         }
430 
431         public void remove()
432         {
433             i.remove();
434         }
435 
436         public boolean equals( Object o )
437         {
438             return i.equals( o );
439         }
440 
441         public int hashCode()
442         {
443             return i.hashCode();
444         }
445     }
446 
447     /***
448      * @author Aaron Smuts
449      */
450     public class MapEntryWrapper
451         implements Map.Entry
452     {
453         private final Map.Entry e;
454 
455         private MapEntryWrapper( Map.Entry e )
456         {
457             this.e = e;
458         }
459 
460         public boolean equals( Object o )
461         {
462             return e.equals( o );
463         }
464 
465         public Object getKey()
466         {
467             return e.getKey();
468         }
469 
470         public Object getValue()
471         {
472             return ( (MemoryElementDescriptor) e.getValue() ).ce;
473         }
474 
475         public int hashCode()
476         {
477             return e.hashCode();
478         }
479 
480         public Object setValue( Object value )
481         {
482             throw new UnsupportedOperationException( "Use normal cache methods"
483                 + " to alter the contents of the cache." );
484         }
485     }
486 
487     /***
488      * Gets the iterator attribute of the LRUMemoryCache object
489      * <p>
490      * @return The iterator value
491      */
492     public Iterator getIterator()
493     {
494         return new IteratorWrapper( map );
495     }
496 
497     /***
498      * Get an Array of the keys for all elements in the memory cache
499      * @return An Object[]
500      */
501     public Object[] getKeyArray()
502     {
503         // need a better locking strategy here.
504         synchronized ( this )
505         {
506             // may need to lock to map here?
507             return map.keySet().toArray();
508         }
509     }
510 
511     // --------------------------- internal methods (linked list implementation)
512     /***
513      * Adds a new node to the end of the link list. Currently not used.
514      * <p>
515      * @param ce The feature to be added to the Last
516      */
517     protected void addLast( CacheElement ce )
518     {
519         MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
520         list.addLast( me );
521         verifyCache( ce.getKey() );
522     }
523 
524     /***
525      * Adds a new node to the start of the link list.
526      * <p>
527      * @param ce The feature to be added to the First
528      */
529     private synchronized void addFirst( ICacheElement ce )
530     {
531 
532         MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
533         list.addFirst( me );
534         return;
535     }
536 
537     // ---------------------------------------------------------- debug methods
538 
539     /***
540      * Dump the cache map for debugging.
541      */
542     public void dumpMap()
543     {
544         log.debug( "dumpingMap" );
545         for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
546         {
547             Map.Entry e = (Map.Entry) itr.next();
548             MemoryElementDescriptor me = (MemoryElementDescriptor) e.getValue();
549             log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.ce.getVal() );
550         }
551     }
552 
553     /***
554      * Dump the cache entries from first to list for debugging.
555      */
556     public void dumpCacheEntries()
557     {
558         log.debug( "dumpingCacheEntries" );
559         for ( MemoryElementDescriptor me = (MemoryElementDescriptor) list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next )
560         {
561             log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() );
562         }
563     }
564 
565     /***
566      * Returns the size of the list.
567      * <p>
568      * @return the number of items in the map.
569      */
570     private int dumpCacheSize()
571     {
572         return list.size();
573     }
574 
575     /***
576      * Checks to see if all the items that should be in the cache are. Checks consistency between
577      * List and map.
578      */
579     private void verifyCache()
580     {
581         if ( !log.isDebugEnabled() )
582         {
583             return;
584         }
585 
586         boolean found = false;
587         log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains "
588             + dumpCacheSize() + " elements" );
589         log.debug( "verifycache: checking linked list by key " );
590         for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
591         {
592             Object key = li.ce.getKey();
593             if ( !map.containsKey( key ) )
594             {
595                 log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() );
596                 log.error( "li.hashcode=" + li.ce.getKey().hashCode() );
597                 log.error( "key class=" + key.getClass() );
598                 log.error( "key hashcode=" + key.hashCode() );
599                 log.error( "key toString=" + key.toString() );
600                 if ( key instanceof GroupAttrName )
601                 {
602                     GroupAttrName name = (GroupAttrName) key;
603                     log.error( "GroupID hashcode=" + name.groupId.hashCode() );
604                     log.error( "GroupID.class=" + name.groupId.getClass() );
605                     log.error( "AttrName hashcode=" + name.attrName.hashCode() );
606                     log.error( "AttrName.class=" + name.attrName.getClass() );
607                 }
608                 dumpMap();
609             }
610             else if ( map.get( li.ce.getKey() ) == null )
611             {
612                 log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: "
613                     + li.ce.getKey() );
614             }
615         }
616 
617         log.debug( "verifycache: checking linked list by value " );
618         for ( MemoryElementDescriptor li3 = (MemoryElementDescriptor) list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next )
619         {
620             if ( map.containsValue( li3 ) == false )
621             {
622                 log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 );
623                 dumpMap();
624             }
625         }
626 
627         log.debug( "verifycache: checking via keysets!" );
628         for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); )
629         {
630             found = false;
631             Serializable val = null;
632             try
633             {
634                 val = (Serializable) itr2.next();
635             }
636             catch ( NoSuchElementException nse )
637             {
638                 log.error( "verifycache: no such element exception" );
639             }
640 
641             for ( MemoryElementDescriptor li2 = (MemoryElementDescriptor) list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next )
642             {
643                 if ( val.equals( li2.ce.getKey() ) )
644                 {
645                     found = true;
646                     break;
647                 }
648             }
649             if ( !found )
650             {
651                 log.error( "verifycache[" + cacheName + "]: key not found in list : " + val );
652                 dumpCacheEntries();
653                 if ( map.containsKey( val ) )
654                 {
655                     log.error( "verifycache: map contains key" );
656                 }
657                 else
658                 {
659                     log.error( "verifycache: map does NOT contain key, what the HECK!" );
660                 }
661             }
662         }
663     }
664 
665     /***
666      * Logs an error if an element that should be in the cache is not.
667      * <p>
668      * @param key
669      */
670     private void verifyCache( Serializable key )
671     {
672         if ( !log.isDebugEnabled() )
673         {
674             return;
675         }
676 
677         boolean found = false;
678 
679         // go through the linked list looking for the key
680         for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
681         {
682             if ( li.ce.getKey() == key )
683             {
684                 found = true;
685                 log.debug( "verifycache(key) key match: " + key );
686                 break;
687             }
688         }
689         if ( !found )
690         {
691             log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key );
692         }
693     }
694 
695     /***
696      * This returns semi-structured information on the memory cache, such as the size, put count,
697      * hit count, and miss count.
698      * <p>
699      * @see org.apache.jcs.engine.memory.MemoryCache#getStatistics()
700      */
701     public synchronized IStats getStatistics()
702     {
703         IStats stats = new Stats();
704         stats.setTypeName( "LRU Memory Cache" );
705 
706         ArrayList elems = new ArrayList();
707 
708         IStatElement se = null;
709 
710         se = new StatElement();
711         se.setName( "List Size" );
712         se.setData( "" + list.size() );
713         elems.add( se );
714 
715         se = new StatElement();
716         se.setName( "Map Size" );
717         se.setData( "" + map.size() );
718         elems.add( se );
719 
720         se = new StatElement();
721         se.setName( "Put Count" );
722         se.setData( "" + putCnt );
723         elems.add( se );
724 
725         se = new StatElement();
726         se.setName( "Hit Count" );
727         se.setData( "" + hitCnt );
728         elems.add( se );
729 
730         se = new StatElement();
731         se.setName( "Miss Count" );
732         se.setData( "" + missCnt );
733         elems.add( se );
734 
735         // get an array and put them in the Stats object
736         IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
737         stats.setStatElements( ses );
738 
739         // int rate = ((hitCnt + missCnt) * 100) / (hitCnt * 100) * 100;
740         // buf.append("\n Hit Rate = " + rate + " %" );
741 
742         return stats;
743     }
744 }