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
86 Element element = findRelativelyUnused(elementJustAdded);
87
88
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
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