1 /**
2 * Copyright 2003-2007 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.Ehcache;
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
27 /**
28 * Less Frequently Used (LFU) implementation of the memory store. Actually keeping track of the least used, then the
29 * second least and so on is very expensive, 3 or 4 orders of magnitude more expensive than the others policies. Costs are
30 * incurred on put, get and remove.
31 * <p/>
32 * Instead this implementation does not quarantee that
33 * the element removed will actually be the least used. Rather, it lets you make statements about confidence intervals
34 * against the likelihood that an element is in some lowest percentile of the hit count distribution. Costs are only
35 * incurred on overflow when an element to be evicted must be selected.
36 * <p/>
37 * For those with a statistical background the branch of stats which deals with this is hypothesis testing and
38 * the Student's T distribution. The higher your sample the greater confidence you can have in a hypothesis, in
39 * this case whether or not the "lowest" value lies in the bottom half or quarter of the distribution. Adding
40 * samples rapidly increases confidence but the return from extra sampling rapidly diminishes.
41 * <p/>
42 * Cost is not affected much by sample size, indicating it is probably the iteration that is causing most of the
43 * time. If we had access to the array backing Map, all would work very fast.
44 * <p/>
45 * A 99.99% confidence interval can be achieved that the "lowest" element is actually in the bottom quarter of the
46 * hit count distribution with a sample size of 30, which is the default.
47 *
48 * @author Greg Luck
49 * @version $Id: LfuMemoryStore.java 512 2007-07-10 09:18:45Z gregluck $
50 */
51 public class LfuMemoryStore extends MemoryStore {
52
53 private static final Log LOG = LogFactory.getLog(LfuMemoryStore.class.getName());
54
55 /**
56 * Constructor for the LfuMemoryStore object.
57 */
58 protected LfuMemoryStore(Ehcache cache, Store diskStore) {
59 super(cache, diskStore);
60 map = new HashMap();
61 }
62
63 /**
64 * Puts an element into the cache.
65 */
66 public final synchronized void doPut(Element elementJustAdded) {
67 if (isFull()) {
68 removeLfuElement(elementJustAdded);
69 }
70 }
71
72
73 private void removeLfuElement(Element elementJustAdded) {
74
75 if (LOG.isTraceEnabled()) {
76 LOG.trace("Cache is full. Removing LFU element ...");
77 }
78
79 // First element of the sorted list is the candidate for the removal
80 Element element = findRelativelyUnused(elementJustAdded);
81
82 // If the element is expired remove
83 if (element.isExpired()) {
84 remove(element.getObjectKey());
85 notifyExpiry(element);
86 return;
87 }
88
89 evict(element);
90 remove(element.getObjectKey());
91 }
92
93 /**
94 * Find a "relatively" unused element, but not the element just added.
95 */
96 final Element findRelativelyUnused(Element elementJustAdded) {
97 LfuPolicy.Metadata[] elements = sampleElements(map.size());
98 LfuPolicy.Metadata metadata = LfuPolicy.leastHit(elements, new ElementMetadata(elementJustAdded));
99 return (Element) map.get(metadata.getKey());
100 }
101
102 /**
103 * Uses random numbers to sample the entire map.
104 *
105 * @return an array of sampled elements
106 */
107 LfuPolicy.Metadata[] sampleElements(int size) {
108 int[] offsets = LfuPolicy.generateRandomSample(size);
109 ElementMetadata[] elements = new ElementMetadata[offsets.length];
110 Iterator iterator = map.values().iterator();
111 for (int i = 0; i < offsets.length; i++) {
112 for (int j = 0; j < offsets[i]; j++) {
113 iterator.next();
114 }
115 elements[i] = new ElementMetadata((Element) iterator.next());
116 }
117 return elements;
118 }
119
120
121 /**
122 * A Metadata wrapper for Element
123 */
124 private class ElementMetadata implements LfuPolicy.Metadata {
125
126 private Element element;
127
128 public ElementMetadata(Element element) {
129 this.element = element;
130 }
131
132
133 /**
134 * @return the key of this object
135 */
136 public Object getKey() {
137 return element.getKey();
138 }
139
140 /**
141 * @return the hit count for the element
142 */
143 public long getHitCount() {
144 return element.getHitCount();
145 }
146
147
148 /**
149 * Hashcode implementation
150 */
151 public int hashCode() {
152 if (element != null) {
153 return element.getKey().hashCode();
154 } else {
155 return 0;
156 }
157 }
158
159 /**
160 * Delegates to {@link Element#equals(Object)}
161 */
162 public boolean equals(Object object) {
163 if (object != null && object instanceof LfuPolicy.Metadata) {
164 LfuPolicy.Metadata metadata = (LfuPolicy.Metadata) object;
165 return this.getKey().equals(metadata.getKey());
166 } else {
167 return false;
168 }
169 }
170 }
171
172 }
173
174
175
176
177