View Javadoc

1   /**
2    *  Copyright 2003-2006 Greg Luck
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  
17  package net.sf.ehcache.store;
18  
19  import net.sf.ehcache.Cache;
20  import net.sf.ehcache.Element;
21  import org.apache.commons.logging.Log;
22  import org.apache.commons.logging.LogFactory;
23  
24  import java.util.HashMap;
25  import java.util.Iterator;
26  import java.util.Random;
27  
28  /**
29   * Less Frequently Used (LFU) implementation of the memory store. Actually keeping track of the least used, then the
30   * second least and so on is very expensive, 3 or 4 orders of magnitude more expensive than the others policies. Costs are
31   * incurred on put, get and remove.
32   * <p/>
33   * Instead this implementation does not quarantee that
34   * the element removed will actually be the least used. Rather, it lets you make statements about confidence intervals
35   *  against the likelihood that an element is in some lowest percentile of the hit count distribution. Costs are only
36   * incurred on overflow when an element to be evicted must be selected.
37   * <p/>
38   * * For those with a statistical background the branch of stats which deals with this is hypothesis testing and
39   * the Student's T distribution. The higher your sample the greater confidence you can have in a hypothesis, in
40   * this case whether or not the "lowest" value lies in the bottom half or quarter of the distribution. Adding
41   * samples rapidly increases confidence but the return from extra sampling rapidly diminishes.
42   * <p/>
43   * Cost is not affected much by sample size, indicating it is probably the iteration that is causing most of the
44   * time. If we had access to the array backing Map, all would work very fast.
45   * <p/>
46   * A 99.99% confidence interval can be achieved that the "lowest" element is actually in the bottom quarter of the
47   * hit count distribution with a sample size of 30, which is the default.
48   *
49   * @author Greg Luck
50   * @version $Id: LfuMemoryStore.java 52 2006-04-24 14:50:03Z gregluck $
51   *          Warning: Testing of this store reveals some problems with it. Do not use. It may be removed.
52   */
53  public final class LfuMemoryStore extends MemoryStore {
54  
55      private static final Log LOG = LogFactory.getLog(LfuMemoryStore.class.getName());
56  
57      private static final int DEFAULT_SAMPLE_SIZE = 30;
58  
59      private final Random random = new Random();
60  
61      /**
62       * Constructor for the LfuMemoryStore object.
63       */
64      protected LfuMemoryStore(Cache cache, DiskStore diskStore) {
65          super(cache, diskStore);
66          map = new HashMap();
67      }
68  
69      /**
70       * Puts an element into the cache.
71       */
72      public final synchronized void doPut(Element elementJustAdded) {
73          if (isFull()) {
74              removeLfuElement(elementJustAdded);
75          }
76      }
77  
78  
79      private void removeLfuElement(Element elementJustAdded) {
80  
81          if (LOG.isTraceEnabled()) {
82              LOG.trace("Cache is full. Removing LFU element ...");
83          }
84  
85          // First element of the sorted list is the candidate for the removal
86          Element element = findRelativelyUnused(elementJustAdded);
87  
88          // If the element is expired remove
89          if (cache.isExpired(element)) {
90              remove(element.getObjectKey());
91              notifyExpiry(element);
92              return;
93          }
94  
95          evict(element);
96          remove(element.getObjectKey());
97      }
98  
99      /**
100      * Find a "relatively" unused element, but not the element just added.
101      */
102     final Element findRelativelyUnused(Element elementJustAdded) {
103         Element[] elements = sampleElements(calculateSampleSize());
104         return lowestElementFromArray(elements, elementJustAdded);
105     }
106 
107     private int calculateSampleSize() {
108         if (map.size() < DEFAULT_SAMPLE_SIZE) {
109             return map.size();
110         } else {
111             return DEFAULT_SAMPLE_SIZE;
112         }
113 
114     }
115 
116     /**
117      * Uses random numbers to sample the entire map.
118      *
119      * @param sampleSize how many samples to take
120      * @return an array of sampled elements
121      */
122     final Element[] sampleElements(int sampleSize) {
123         int[] offsets = generateRandomOffsets(sampleSize);
124         Element[] elements = new Element[sampleSize];
125         Iterator iterator = map.values().iterator();
126         for (int i = 0; i < sampleSize; i++) {
127             for (int j = 0; j < offsets[i]; j++) {
128                 iterator.next();
129             }
130             elements[i] = (Element) iterator.next();
131         }
132         return elements;
133     }
134 
135     private static Element lowestElementFromArray(Element[] elements, Element elementJustAdded) {
136         //edge condition when Memory Store configured to size 0
137         if (elements.length == 1) {
138             return elementJustAdded;
139         }
140         Element lowestElement = null;
141         for (int i = 0; i < elements.length; i++) {
142             Element element = elements[i];
143             if (lowestElement == null) {
144                 if (!element.equals(elementJustAdded)) {
145                     lowestElement = element;
146                 }
147             } else {
148                 if (element.getHitCount() < lowestElement.getHitCount() && !element.equals(elementJustAdded)) {
149                     lowestElement = element;
150                 }
151             }
152         }
153         return lowestElement;
154     }
155 
156     private int[] generateRandomOffsets(int sampleSize) {
157         int size = map.size();
158         int[] offsets = new int[sampleSize];
159         int maxOffset = size / sampleSize;
160         for (int i = 0; i < sampleSize; i++) {
161             offsets[i] = random.nextInt(maxOffset);
162         }
163         return offsets;
164     }
165 }
166 
167 
168 
169 
170