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.Element;
20  import net.sf.ehcache.MemoryStoreTester;
21  import net.sf.ehcache.StopWatch;
22  import net.sf.ehcache.AbstractCacheTest;
23  import org.apache.commons.logging.Log;
24  import org.apache.commons.logging.LogFactory;
25  
26  import java.io.IOException;
27  import java.util.Date;
28  import java.util.HashMap;
29  import java.util.Iterator;
30  import java.util.Map;
31  import java.util.Random;
32  
33  /**
34   * Test class for LfuMemoryStore
35   * <p/>
36   * @author <a href="ssuravarapu@users.sourceforge.net">Surya Suravarapu</a>
37   * @version $Id: LfuMemoryStoreTest.java 28 2006-04-15 05:12:32Z gregluck $
38   */
39  public class LfuMemoryStoreTest extends MemoryStoreTester {
40  
41      private static final Log LOG = LogFactory.getLog(LfuMemoryStoreTest.class.getName());
42  
43      /**
44       * setup test
45       */
46      protected void setUp() throws Exception {
47          super.setUp();
48          createMemoryStore(MemoryStoreEvictionPolicy.LFU);
49      }
50  
51  
52      /**
53       * Tests the put by reading the config file
54       */
55      public void testPutFromConfig() throws Exception {
56          createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
57          putTest();
58      }
59  
60      /**
61       * Tests the put by reading the config file
62       */
63      public void testPutFromConfigZeroMemoryStore() throws Exception {
64          createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache2");
65          Element element = new Element("1", "value");
66          store.put(element);
67          assertNull(store.get("1"));
68      }
69  
70      /**
71       * Tests the remove() method by using the parameters specified in the config file
72       */
73      public void testRemoveFromConfig() throws Exception {
74          createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
75          removeTest();
76      }
77  
78      /**
79       * Benchmark to test speed.
80       * This takes a little longer for LFU than the others.
81       * Takes about 7400ms
82       */
83      public void testBenchmarkPutGetSurya() throws Exception {
84          benchmarkPutGetSuryaTest(9000);
85      }
86  
87      /**
88       * Tests the LFU policy
89       */
90      public void testLfuPolicy() throws Exception {
91          createMemoryStore(MemoryStoreEvictionPolicy.LFU, 4);
92          lfuPolicyTest();
93      }
94  
95      /**
96       * Tests the LFU policy by using the parameters specified in the config file
97       */
98      public void testLfuPolicyFromConfig() throws Exception {
99          createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
100         lfuPolicyTest();
101     }
102 
103 
104     private void lfuPolicyTest() throws IOException {
105         //Make sure that the store is empty to start with
106         assertEquals(0, store.getSize());
107 
108         // Populate the store till the max limit
109         Element element = new Element("key1", "value1");
110         store.put(element);
111         assertEquals(1, store.getSize());
112 
113         element = new Element("key2", "value2");
114         store.put(element);
115         assertEquals(2, store.getSize());
116 
117         element = new Element("key3", "value3");
118         store.put(element);
119         assertEquals(3, store.getSize());
120 
121         element = new Element("key4", "value4");
122         store.put(element);
123         assertEquals(4, store.getSize());
124 
125         //Now access the elements to boost the hits count
126         store.get("key1");
127         store.get("key1");
128         store.get("key3");
129         store.get("key3");
130         store.get("key3");
131         store.get("key4");
132 
133         //Create a new element and put in the store so as to force the policy
134         element = new Element("key5", "value5");
135         store.put(element);
136 
137         assertEquals(4, store.getSize());
138         //The element with key "key2" is the LFU element so should be removed
139         assertNull(store.get("key2"));
140 
141         // Make some more accesses
142         store.get("key5");
143         store.get("key5");
144 
145         // Insert another element to force the policy
146         element = new Element("key6", "value6");
147         store.put(element);
148         assertEquals(4, store.getSize());
149         assertNull(store.get("key4"));
150     }
151 
152     /**
153      * Benchmark to test speed.
154      * new sampling LFU 417ms
155      */
156     public void testBenchmarkPutGetRemove() throws Exception {
157         super.testBenchmarkPutGetRemove();
158     }
159 
160 
161     /**
162      * Multi-thread read, put and removeAll test.
163      * This checks for memory leaks
164      * using the removeAll which was the known cause of memory leaks with LruMemoryStore in JCS
165      * new sampling LFU has no leaks
166      */
167     public void testMemoryLeak() throws Exception {
168         super.testMemoryLeak();
169     }
170 
171     /**
172      * Benchmark to test speed.
173      * new sampling LFU 132ms
174      */
175     public void testBenchmarkPutGet() throws Exception {
176         super.testBenchmarkPutGet();
177     }
178 
179     /**
180      * Tests how random the java.util.Map iteration is by measuring the differences in iterate order.
181      * <p/>
182      * If iterate was ordered in either insert or reverse insert order the mean difference would be 1.
183      * Using Random gives a mean difference of 343.
184      * The observed value is 175 but always 175 for a key set of 500 because it always iterates in the same order,
185      * just not an obvious order.
186      * <p/>
187      * Conclusion: Unable to use the iterator as a pseudorandom selector.
188      */
189     public void testRandomnessOfIterator() {
190         int mean = 0;
191         int absoluteDifferences = 0;
192         int lastReading = 0;
193         Map map = new HashMap();
194         for (int i = 1; i <= 500; i++) {
195             mean += i;
196             map.put("" + i, " ");
197         }
198         mean = mean / 500;
199         for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {
200             String string = (String) iterator.next();
201             int thisReading = Integer.parseInt(string);
202             absoluteDifferences += Math.abs(lastReading - thisReading);
203             lastReading = thisReading;
204         }
205         LOG.info("Mean difference through iteration: " + absoluteDifferences / 500);
206 
207         //Random selection without replacement
208         Random random = new Random();
209         while (map.size() != 0) {
210             int thisReading = random.nextInt(501);
211             Object o = map.remove("" + thisReading);
212             if (o == null) {
213                 continue;
214             }
215             absoluteDifferences += Math.abs(lastReading - thisReading);
216             lastReading = thisReading;
217         }
218         LOG.info("Mean difference with random selection without replacement : " + absoluteDifferences / 500);
219         LOG.info("Mean of range 1 - 500 : " + mean);
220 
221     }
222 
223 
224     /**
225      * Check nothing breaks and that we get the right number of samples
226      *
227      * @throws IOException
228      */
229     public void testSampling() throws IOException {
230         createMemoryStore(MemoryStoreEvictionPolicy.LFU, 1000);
231         Element[] elements = null;
232         for (int i = 0; i < 10; i++) {
233             store.put(new Element("" + i, new Date()));
234             elements = ((LfuMemoryStore) store).sampleElements(i + 1);
235         }
236 
237         for (int i = 10; i < 2000; i++) {
238             store.put(new Element("" + i, new Date()));
239             elements = ((LfuMemoryStore) store).sampleElements(10);
240             assertEquals(10, elements.length);
241         }
242     }
243 
244 
245     /**
246      * Check we get reasonable results for 2000 entries where entry 0 is accessed once increasing to entry 1999 accessed
247      * 2000 times.
248      * <p/>
249      * 1 to 5000 population, with hit counts ranging from 1 to 500, not selecting lowest half. 5000 tests
250      * S  Cost  No
251      * 7        38 99.24% confidence
252      * 8        27 99.46% confidence
253      * 9        10
254      * 10 11300 4  99.92% confidence
255      * 12       2
256      * 20 11428 0  99.99% confidence
257      * <p/>
258      * 1 to 5000 population, with hit counts ranging from 1 to 500, not selecting lowest quarter. 5000 tests
259      * S        No
260      * 10       291 94.18% confidence
261      * 20       15
262      * 30 11536 1 99.99% confidence
263      * <p/>
264      * For those with a statistical background the branch of stats which deals with this is hypothesis testing and
265      * the Student's T distribution. The higher your sample the greater confidence you can have in a hypothesis, in
266      * this case whether or not the "lowest" value lies in the bottom half or quarter of the distribution. Adding
267      * samples rapidly increases confidence but the return from extra sampling rapidly diminishes.
268      * <p/>
269      * Cost is not affected much by sample size. Profiling shows that it is the iteration that is causing most of the
270      * time. If we had access to the array backing Map, all would work very fast. Still, it is fast enough.
271      * <p/>
272      * A 99.99% confidence interval can be achieved that the "lowest" element is actually in the bottom quarter of the
273      * hit count distribution.
274      * @throws IOException
275      */
276     public void testLowest() throws IOException {
277         createMemoryStore(MemoryStoreEvictionPolicy.LFU, 5000);
278         Element element = null;
279         Element newElement = null;
280         for (int i = 0; i < 10; i++) {
281             newElement = new Element("" + i, new Date());
282             store.put(newElement);
283             int j;
284             for (j = 0; j <= i; j++) {
285                 store.get("" + i);
286             }
287             if (i > 0) {
288                 element = ((LfuMemoryStore) store).findRelativelyUnused(newElement);
289                 assertTrue(!element.equals(newElement));
290                 assertTrue(element.getHitCount() < 2);
291             }
292         }
293 
294         int lowestQuarterNotIdentified = 0;
295 
296         long findTime = 0;
297         StopWatch stopWatch = new StopWatch();
298         for (int i = 10; i < 5000; i++) {
299             store.put(new Element("" + i, new Date()));
300             int j;
301             int maximumHitCount = 0;
302             for (j = 0; j <= i; j += 10) {
303                 store.get("" + i);
304                 maximumHitCount++;
305             }
306 
307             stopWatch.getElapsedTime();
308             element = ((LfuMemoryStore) store).findRelativelyUnused(newElement);
309             findTime  += stopWatch.getElapsedTime();
310             long lowest = element.getHitCount();
311             long bottomQuarter = (Math.round(maximumHitCount / 4.0) + 1);
312             assertTrue(!element.equals(newElement));
313             if (lowest > bottomQuarter) {
314                 lowestQuarterNotIdentified++;
315                 //LOG.info(i + " " + maximumHitCount + " " + element);
316             }
317         }
318         LOG.info("Find time: " + findTime);
319         assertTrue(findTime < 1500);
320         LOG.info("Selections not in lowest quartile: " + lowestQuarterNotIdentified);
321         assertTrue(lowestQuarterNotIdentified < 3);
322 
323     }
324 
325 }