View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.io.hfile;
20  
21  import static org.junit.Assert.assertEquals;
22  import static org.junit.Assert.assertTrue;
23  
24  import java.nio.ByteBuffer;
25  import java.util.Random;
26  
27  import org.apache.hadoop.hbase.testclassification.SmallTests;
28  import org.apache.hadoop.hbase.io.HeapSize;
29  import org.apache.hadoop.hbase.io.hfile.LruBlockCache.EvictionThread;
30  import org.apache.hadoop.hbase.util.ClassSize;
31  import org.junit.Test;
32  import org.junit.experimental.categories.Category;
33  
34  /**
35   * Tests the concurrent LruBlockCache.<p>
36   *
37   * Tests will ensure it grows and shrinks in size properly,
38   * evictions run when they're supposed to and do what they should,
39   * and that cached blocks are accessible when expected to be.
40   */
41  @Category(SmallTests.class)
42  public class TestLruBlockCache {
43  
44  
45    @Test
46    public void testBackgroundEvictionThread() throws Exception {
47      long maxSize = 100000;
48      int numBlocks = 9;
49      long blockSize = calculateBlockSizeDefault(maxSize, numBlocks);
50      assertTrue("calculateBlockSize appears broken.", blockSize * numBlocks <= maxSize);
51  
52      LruBlockCache cache = new LruBlockCache(maxSize,blockSize);
53      EvictionThread evictionThread = cache.getEvictionThread();
54      assertTrue(evictionThread != null);
55  
56      CachedItem[] blocks = generateFixedBlocks(numBlocks + 1, blockSize, "block");
57  
58      // Make sure eviction thread has entered run method
59      while (!evictionThread.isEnteringRun()) {
60        Thread.sleep(1);
61      }
62  
63      // Add all the blocks
64      for (CachedItem block : blocks) {
65        cache.cacheBlock(block.cacheKey, block);
66      }
67  
68      // wait until at least one eviction has run
69      int n = 0;
70      while(cache.getStats().getEvictionCount() == 0) {
71        Thread.sleep(200);
72        assertTrue("Eviction never happened.", n++ < 20);
73      }
74  
75      // let cache stabilize
76      // On some systems, the cache will run multiple evictions before it attains
77      // steady-state. For instance, after populating the cache with 10 blocks,
78      // the first eviction evicts a single block and then a second eviction
79      // evicts another. I think this is due to the delta between minSize and
80      // acceptableSize, combined with variance between object overhead on
81      // different environments.
82      n = 0;
83      for (long prevCnt = 0 /* < number of blocks added */,
84                curCnt = cache.getBlockCount();
85          prevCnt != curCnt; prevCnt = curCnt, curCnt = cache.getBlockCount()) {
86        Thread.sleep(200);
87        assertTrue("Cache never stabilized.", n++ < 20);
88      }
89  
90      long evictionCount = cache.getStats().getEvictionCount();
91      assertTrue(evictionCount >= 1);
92      System.out.println("Background Evictions run: " + evictionCount);
93    }
94  
95    @Test
96    public void testCacheSimple() throws Exception {
97  
98      long maxSize = 1000000;
99      long blockSize = calculateBlockSizeDefault(maxSize, 101);
100 
101     LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
102 
103     CachedItem [] blocks = generateRandomBlocks(100, blockSize);
104 
105     long expectedCacheSize = cache.heapSize();
106 
107     // Confirm empty
108     for (CachedItem block : blocks) {
109       assertTrue(cache.getBlock(block.cacheKey, true, false, true) == null);
110     }
111 
112     // Add blocks
113     for (CachedItem block : blocks) {
114       cache.cacheBlock(block.cacheKey, block);
115       expectedCacheSize += block.cacheBlockHeapSize();
116     }
117 
118     // Verify correctly calculated cache heap size
119     assertEquals(expectedCacheSize, cache.heapSize());
120 
121     // Check if all blocks are properly cached and retrieved
122     for (CachedItem block : blocks) {
123       HeapSize buf = cache.getBlock(block.cacheKey, true, false, true);
124       assertTrue(buf != null);
125       assertEquals(buf.heapSize(), block.heapSize());
126     }
127 
128     // Re-add same blocks and ensure nothing has changed
129     long expectedBlockCount = cache.getBlockCount();
130     for (CachedItem block : blocks) {
131       cache.cacheBlock(block.cacheKey, block);
132     }
133     assertEquals(
134             "Cache should ignore cache requests for blocks already in cache",
135             expectedBlockCount, cache.getBlockCount());
136     
137     // Verify correctly calculated cache heap size
138     assertEquals(expectedCacheSize, cache.heapSize());
139 
140     // Check if all blocks are properly cached and retrieved
141     for (CachedItem block : blocks) {
142       HeapSize buf = cache.getBlock(block.cacheKey, true, false, true);
143       assertTrue(buf != null);
144       assertEquals(buf.heapSize(), block.heapSize());
145     }
146 
147     // Expect no evictions
148     assertEquals(0, cache.getStats().getEvictionCount());
149     Thread t = new LruBlockCache.StatisticsThread(cache);
150     t.start();
151     t.join();
152   }
153 
154   @Test
155   public void testCacheEvictionSimple() throws Exception {
156 
157     long maxSize = 100000;
158     long blockSize = calculateBlockSizeDefault(maxSize, 10);
159 
160     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
161 
162     CachedItem [] blocks = generateFixedBlocks(10, blockSize, "block");
163 
164     long expectedCacheSize = cache.heapSize();
165 
166     // Add all the blocks
167     for (CachedItem block : blocks) {
168       cache.cacheBlock(block.cacheKey, block);
169       expectedCacheSize += block.cacheBlockHeapSize();
170     }
171 
172     // A single eviction run should have occurred
173     assertEquals(1, cache.getStats().getEvictionCount());
174 
175     // Our expected size overruns acceptable limit
176     assertTrue(expectedCacheSize >
177       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
178 
179     // But the cache did not grow beyond max
180     assertTrue(cache.heapSize() < maxSize);
181 
182     // And is still below the acceptable limit
183     assertTrue(cache.heapSize() <
184         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
185 
186     // All blocks except block 0  should be in the cache
187     assertTrue(cache.getBlock(blocks[0].cacheKey, true, false, true) == null);
188     for(int i=1;i<blocks.length;i++) {
189       assertEquals(cache.getBlock(blocks[i].cacheKey, true, false, true),
190           blocks[i]);
191     }
192   }
193 
194   @Test
195   public void testCacheEvictionTwoPriorities() throws Exception {
196 
197     long maxSize = 100000;
198     long blockSize = calculateBlockSizeDefault(maxSize, 10);
199 
200     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
201 
202     CachedItem [] singleBlocks = generateFixedBlocks(5, 10000, "single");
203     CachedItem [] multiBlocks = generateFixedBlocks(5, 10000, "multi");
204 
205     long expectedCacheSize = cache.heapSize();
206 
207     // Add and get the multi blocks
208     for (CachedItem block : multiBlocks) {
209       cache.cacheBlock(block.cacheKey, block);
210       expectedCacheSize += block.cacheBlockHeapSize();
211       assertEquals(cache.getBlock(block.cacheKey, true, false, true), block);
212     }
213 
214     // Add the single blocks (no get)
215     for (CachedItem block : singleBlocks) {
216       cache.cacheBlock(block.cacheKey, block);
217       expectedCacheSize += block.heapSize();
218     }
219 
220     // A single eviction run should have occurred
221     assertEquals(cache.getStats().getEvictionCount(), 1);
222 
223     // We expect two entries evicted
224     assertEquals(cache.getStats().getEvictedCount(), 2);
225 
226     // Our expected size overruns acceptable limit
227     assertTrue(expectedCacheSize >
228       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
229 
230     // But the cache did not grow beyond max
231     assertTrue(cache.heapSize() <= maxSize);
232 
233     // And is now below the acceptable limit
234     assertTrue(cache.heapSize() <=
235         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
236 
237     // We expect fairness across the two priorities.
238     // This test makes multi go barely over its limit, in-memory
239     // empty, and the rest in single.  Two single evictions and
240     // one multi eviction expected.
241     assertTrue(cache.getBlock(singleBlocks[0].cacheKey, true, false, true) == null);
242     assertTrue(cache.getBlock(multiBlocks[0].cacheKey, true, false, true) == null);
243 
244     // And all others to be cached
245     for(int i=1;i<4;i++) {
246       assertEquals(cache.getBlock(singleBlocks[i].cacheKey, true, false, true),
247           singleBlocks[i]);
248       assertEquals(cache.getBlock(multiBlocks[i].cacheKey, true, false, true),
249           multiBlocks[i]);
250     }
251   }
252 
253   @Test
254   public void testCacheEvictionThreePriorities() throws Exception {
255 
256     long maxSize = 100000;
257     long blockSize = calculateBlockSize(maxSize, 10);
258 
259     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
260         (int)Math.ceil(1.2*maxSize/blockSize),
261         LruBlockCache.DEFAULT_LOAD_FACTOR,
262         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
263         0.98f, // min
264         0.99f, // acceptable
265         0.33f, // single
266         0.33f, // multi
267         0.34f, // memory
268         false);
269 
270     CachedItem [] singleBlocks = generateFixedBlocks(5, blockSize, "single");
271     CachedItem [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
272     CachedItem [] memoryBlocks = generateFixedBlocks(5, blockSize, "memory");
273 
274     long expectedCacheSize = cache.heapSize();
275 
276     // Add 3 blocks from each priority
277     for(int i=0;i<3;i++) {
278 
279       // Just add single blocks
280       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
281       expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
282 
283       // Add and get multi blocks
284       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
285       expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
286       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
287 
288       // Add memory blocks as such
289       cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true, false);
290       expectedCacheSize += memoryBlocks[i].cacheBlockHeapSize();
291 
292     }
293 
294     // Do not expect any evictions yet
295     assertEquals(0, cache.getStats().getEvictionCount());
296 
297     // Verify cache size
298     assertEquals(expectedCacheSize, cache.heapSize());
299 
300     // Insert a single block, oldest single should be evicted
301     cache.cacheBlock(singleBlocks[3].cacheKey, singleBlocks[3]);
302 
303     // Single eviction, one thing evicted
304     assertEquals(1, cache.getStats().getEvictionCount());
305     assertEquals(1, cache.getStats().getEvictedCount());
306 
307     // Verify oldest single block is the one evicted
308     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
309 
310     // Change the oldest remaining single block to a multi
311     cache.getBlock(singleBlocks[1].cacheKey, true, false, true);
312 
313     // Insert another single block
314     cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
315 
316     // Two evictions, two evicted.
317     assertEquals(2, cache.getStats().getEvictionCount());
318     assertEquals(2, cache.getStats().getEvictedCount());
319 
320     // Oldest multi block should be evicted now
321     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
322 
323     // Insert another memory block
324     cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true, false);
325 
326     // Three evictions, three evicted.
327     assertEquals(3, cache.getStats().getEvictionCount());
328     assertEquals(3, cache.getStats().getEvictedCount());
329 
330     // Oldest memory block should be evicted now
331     assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
332 
333     // Add a block that is twice as big (should force two evictions)
334     CachedItem [] bigBlocks = generateFixedBlocks(3, blockSize*3, "big");
335     cache.cacheBlock(bigBlocks[0].cacheKey, bigBlocks[0]);
336 
337     // Four evictions, six evicted (inserted block 3X size, expect +3 evicted)
338     assertEquals(4, cache.getStats().getEvictionCount());
339     assertEquals(6, cache.getStats().getEvictedCount());
340 
341     // Expect three remaining singles to be evicted
342     assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
343     assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
344     assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
345 
346     // Make the big block a multi block
347     cache.getBlock(bigBlocks[0].cacheKey, true, false, true);
348 
349     // Cache another single big block
350     cache.cacheBlock(bigBlocks[1].cacheKey, bigBlocks[1]);
351 
352     // Five evictions, nine evicted (3 new)
353     assertEquals(5, cache.getStats().getEvictionCount());
354     assertEquals(9, cache.getStats().getEvictedCount());
355 
356     // Expect three remaining multis to be evicted
357     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
358     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
359     assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
360 
361     // Cache a big memory block
362     cache.cacheBlock(bigBlocks[2].cacheKey, bigBlocks[2], true, false);
363 
364     // Six evictions, twelve evicted (3 new)
365     assertEquals(6, cache.getStats().getEvictionCount());
366     assertEquals(12, cache.getStats().getEvictedCount());
367 
368     // Expect three remaining in-memory to be evicted
369     assertEquals(null, cache.getBlock(memoryBlocks[1].cacheKey, true, false, true));
370     assertEquals(null, cache.getBlock(memoryBlocks[2].cacheKey, true, false, true));
371     assertEquals(null, cache.getBlock(memoryBlocks[3].cacheKey, true, false, true));
372   }
373 
374   @Test
375   public void testCacheEvictionInMemoryForceMode() throws Exception {
376     long maxSize = 100000;
377     long blockSize = calculateBlockSize(maxSize, 10);
378 
379     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
380         (int)Math.ceil(1.2*maxSize/blockSize),
381         LruBlockCache.DEFAULT_LOAD_FACTOR,
382         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
383         0.98f, // min
384         0.99f, // acceptable
385         0.2f, // single
386         0.3f, // multi
387         0.5f, // memory
388         true);
389 
390     CachedItem [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
391     CachedItem [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
392     CachedItem [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
393 
394     long expectedCacheSize = cache.heapSize();
395 
396     // 0. Add 5 single blocks and 4 multi blocks to make cache full, si:mu:me = 5:4:0
397     for(int i = 0; i < 4; i++) {
398       // Just add single blocks
399       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
400       expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
401       // Add and get multi blocks
402       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
403       expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
404       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
405     }
406     // 5th single block
407     cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
408     expectedCacheSize += singleBlocks[4].cacheBlockHeapSize();
409     // Do not expect any evictions yet
410     assertEquals(0, cache.getStats().getEvictionCount());
411     // Verify cache size
412     assertEquals(expectedCacheSize, cache.heapSize());
413 
414     // 1. Insert a memory block, oldest single should be evicted, si:mu:me = 4:4:1
415     cache.cacheBlock(memoryBlocks[0].cacheKey, memoryBlocks[0], true, false);
416     // Single eviction, one block evicted
417     assertEquals(1, cache.getStats().getEvictionCount());
418     assertEquals(1, cache.getStats().getEvictedCount());
419     // Verify oldest single block (index = 0) is the one evicted
420     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
421 
422     // 2. Insert another memory block, another single evicted, si:mu:me = 3:4:2
423     cache.cacheBlock(memoryBlocks[1].cacheKey, memoryBlocks[1], true, false);
424     // Two evictions, two evicted.
425     assertEquals(2, cache.getStats().getEvictionCount());
426     assertEquals(2, cache.getStats().getEvictedCount());
427     // Current oldest single block (index = 1) should be evicted now
428     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
429 
430     // 3. Insert 4 memory blocks, 2 single and 2 multi evicted, si:mu:me = 1:2:6
431     cache.cacheBlock(memoryBlocks[2].cacheKey, memoryBlocks[2], true, false);
432     cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true, false);
433     cache.cacheBlock(memoryBlocks[4].cacheKey, memoryBlocks[4], true, false);
434     cache.cacheBlock(memoryBlocks[5].cacheKey, memoryBlocks[5], true, false);
435     // Three evictions, three evicted.
436     assertEquals(6, cache.getStats().getEvictionCount());
437     assertEquals(6, cache.getStats().getEvictedCount());
438     // two oldest single blocks and two oldest multi blocks evicted
439     assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
440     assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
441     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
442     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
443 
444     // 4. Insert 3 memory blocks, the remaining 1 single and 2 multi evicted
445     // si:mu:me = 0:0:9
446     cache.cacheBlock(memoryBlocks[6].cacheKey, memoryBlocks[6], true, false);
447     cache.cacheBlock(memoryBlocks[7].cacheKey, memoryBlocks[7], true, false);
448     cache.cacheBlock(memoryBlocks[8].cacheKey, memoryBlocks[8], true, false);
449     // Three evictions, three evicted.
450     assertEquals(9, cache.getStats().getEvictionCount());
451     assertEquals(9, cache.getStats().getEvictedCount());
452     // one oldest single block and two oldest multi blocks evicted
453     assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
454     assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
455     assertEquals(null, cache.getBlock(multiBlocks[3].cacheKey, true, false, true));
456 
457     // 5. Insert one memory block, the oldest memory evicted
458     // si:mu:me = 0:0:9
459     cache.cacheBlock(memoryBlocks[9].cacheKey, memoryBlocks[9], true, false);
460     // one eviction, one evicted.
461     assertEquals(10, cache.getStats().getEvictionCount());
462     assertEquals(10, cache.getStats().getEvictedCount());
463     // oldest memory block evicted
464     assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
465 
466     // 6. Insert one new single block, itself evicted immediately since
467     //    all blocks in cache are memory-type which have higher priority
468     // si:mu:me = 0:0:9 (no change)
469     cache.cacheBlock(singleBlocks[9].cacheKey, singleBlocks[9]);
470     // one eviction, one evicted.
471     assertEquals(11, cache.getStats().getEvictionCount());
472     assertEquals(11, cache.getStats().getEvictedCount());
473     // the single block just cached now evicted (can't evict memory)
474     assertEquals(null, cache.getBlock(singleBlocks[9].cacheKey, true, false, true));
475   }
476 
477   // test scan resistance
478   @Test
479   public void testScanResistance() throws Exception {
480 
481     long maxSize = 100000;
482     long blockSize = calculateBlockSize(maxSize, 10);
483 
484     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
485         (int)Math.ceil(1.2*maxSize/blockSize),
486         LruBlockCache.DEFAULT_LOAD_FACTOR,
487         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
488         0.66f, // min
489         0.99f, // acceptable
490         0.33f, // single
491         0.33f, // multi
492         0.34f, // memory
493         false);
494 
495     CachedItem [] singleBlocks = generateFixedBlocks(20, blockSize, "single");
496     CachedItem [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
497 
498     // Add 5 multi blocks
499     for (CachedItem block : multiBlocks) {
500       cache.cacheBlock(block.cacheKey, block);
501       cache.getBlock(block.cacheKey, true, false, true);
502     }
503 
504     // Add 5 single blocks
505     for(int i=0;i<5;i++) {
506       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
507     }
508 
509     // An eviction ran
510     assertEquals(1, cache.getStats().getEvictionCount());
511 
512     // To drop down to 2/3 capacity, we'll need to evict 4 blocks
513     assertEquals(4, cache.getStats().getEvictedCount());
514 
515     // Should have been taken off equally from single and multi
516     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
517     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
518     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
519     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
520 
521     // Let's keep "scanning" by adding single blocks.  From here on we only
522     // expect evictions from the single bucket.
523 
524     // Every time we reach 10 total blocks (every 4 inserts) we get 4 single
525     // blocks evicted.  Inserting 13 blocks should yield 3 more evictions and
526     // 12 more evicted.
527 
528     for(int i=5;i<18;i++) {
529       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
530     }
531 
532     // 4 total evictions, 16 total evicted
533     assertEquals(4, cache.getStats().getEvictionCount());
534     assertEquals(16, cache.getStats().getEvictedCount());
535 
536     // Should now have 7 total blocks
537     assertEquals(7, cache.getBlockCount());
538 
539   }
540 
541   // test setMaxSize
542   @Test
543   public void testResizeBlockCache() throws Exception {
544 
545     long maxSize = 300000;
546     long blockSize = calculateBlockSize(maxSize, 31);
547 
548     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
549         (int)Math.ceil(1.2*maxSize/blockSize),
550         LruBlockCache.DEFAULT_LOAD_FACTOR,
551         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
552         0.98f, // min
553         0.99f, // acceptable
554         0.33f, // single
555         0.33f, // multi
556         0.34f, // memory
557         false);
558 
559     CachedItem [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
560     CachedItem [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
561     CachedItem [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
562 
563     // Add all blocks from all priorities
564     for(int i=0;i<10;i++) {
565 
566       // Just add single blocks
567       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
568 
569       // Add and get multi blocks
570       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
571       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
572 
573       // Add memory blocks as such
574       cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true, false);
575     }
576 
577     // Do not expect any evictions yet
578     assertEquals(0, cache.getStats().getEvictionCount());
579 
580     // Resize to half capacity plus an extra block (otherwise we evict an extra)
581     cache.setMaxSize((long)(maxSize * 0.5f));
582 
583     // Should have run a single eviction
584     assertEquals(1, cache.getStats().getEvictionCount());
585 
586     // And we expect 1/2 of the blocks to be evicted
587     assertEquals(15, cache.getStats().getEvictedCount());
588 
589     // And the oldest 5 blocks from each category should be gone
590     for(int i=0;i<5;i++) {
591       assertEquals(null, cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
592       assertEquals(null, cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
593       assertEquals(null, cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
594     }
595 
596     // And the newest 5 blocks should still be accessible
597     for(int i=5;i<10;i++) {
598       assertEquals(singleBlocks[i], cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
599       assertEquals(multiBlocks[i], cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
600       assertEquals(memoryBlocks[i], cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
601     }
602   }
603 
604   // test metricsPastNPeriods
605   @Test
606   public void testPastNPeriodsMetrics() throws Exception {
607    double delta = 0.01;
608 
609     // 3 total periods
610     CacheStats stats = new CacheStats("test", 3);
611 
612     // No accesses, should be 0
613     stats.rollMetricsPeriod();
614     assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
615     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
616 
617     // period 1, 1 hit caching, 1 hit non-caching, 2 miss non-caching
618     // should be (2/4)=0.5 and (1/1)=1
619     stats.hit(false, true, BlockType.DATA);
620     stats.hit(true, true, BlockType.DATA);
621     stats.miss(false, false, BlockType.DATA);
622     stats.miss(false, false, BlockType.DATA);
623     stats.rollMetricsPeriod();
624     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
625     assertEquals(1.0, stats.getHitCachingRatioPastNPeriods(), delta);
626 
627     // period 2, 1 miss caching, 3 miss non-caching
628     // should be (2/8)=0.25 and (1/2)=0.5
629     stats.miss(true, false, BlockType.DATA);
630     stats.miss(false, false, BlockType.DATA);
631     stats.miss(false, false, BlockType.DATA);
632     stats.miss(false, false, BlockType.DATA);
633     stats.rollMetricsPeriod();
634     assertEquals(0.25, stats.getHitRatioPastNPeriods(), delta);
635     assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
636 
637     // period 3, 2 hits of each type
638     // should be (6/12)=0.5 and (3/4)=0.75
639     stats.hit(false, true, BlockType.DATA);
640     stats.hit(true, true, BlockType.DATA);
641     stats.hit(false, true, BlockType.DATA);
642     stats.hit(true, true, BlockType.DATA);
643     stats.rollMetricsPeriod();
644     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
645     assertEquals(0.75, stats.getHitCachingRatioPastNPeriods(), delta);
646 
647     // period 4, evict period 1, two caching misses
648     // should be (4/10)=0.4 and (2/5)=0.4
649     stats.miss(true, false, BlockType.DATA);
650     stats.miss(true, false, BlockType.DATA);
651     stats.rollMetricsPeriod();
652     assertEquals(0.4, stats.getHitRatioPastNPeriods(), delta);
653     assertEquals(0.4, stats.getHitCachingRatioPastNPeriods(), delta);
654 
655     // period 5, evict period 2, 2 caching misses, 2 non-caching hit
656     // should be (6/10)=0.6 and (2/6)=1/3
657     stats.miss(true, false, BlockType.DATA);
658     stats.miss(true, false, BlockType.DATA);
659     stats.hit(false, true, BlockType.DATA);
660     stats.hit(false, true, BlockType.DATA);
661     stats.rollMetricsPeriod();
662     assertEquals(0.6, stats.getHitRatioPastNPeriods(), delta);
663     assertEquals((double)1/3, stats.getHitCachingRatioPastNPeriods(), delta);
664 
665     // period 6, evict period 3
666     // should be (2/6)=1/3 and (0/4)=0
667     stats.rollMetricsPeriod();
668     assertEquals((double)1/3, stats.getHitRatioPastNPeriods(), delta);
669     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
670 
671     // period 7, evict period 4
672     // should be (2/4)=0.5 and (0/2)=0
673     stats.rollMetricsPeriod();
674     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
675     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
676 
677     // period 8, evict period 5
678     // should be 0 and 0
679     stats.rollMetricsPeriod();
680     assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
681     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
682 
683     // period 9, one of each
684     // should be (2/4)=0.5 and (1/2)=0.5
685     stats.miss(true, false, BlockType.DATA);
686     stats.miss(false, false, BlockType.DATA);
687     stats.hit(true, true, BlockType.DATA);
688     stats.hit(false, true, BlockType.DATA);
689     stats.rollMetricsPeriod();
690     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
691     assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
692   }
693 
694   private CachedItem [] generateFixedBlocks(int numBlocks, int size, String pfx) {
695     CachedItem [] blocks = new CachedItem[numBlocks];
696     for(int i=0;i<numBlocks;i++) {
697       blocks[i] = new CachedItem(pfx + i, size);
698     }
699     return blocks;
700   }
701 
702   private CachedItem [] generateFixedBlocks(int numBlocks, long size, String pfx) {
703     return generateFixedBlocks(numBlocks, (int)size, pfx);
704   }
705 
706   private CachedItem [] generateRandomBlocks(int numBlocks, long maxSize) {
707     CachedItem [] blocks = new CachedItem[numBlocks];
708     Random r = new Random();
709     for(int i=0;i<numBlocks;i++) {
710       blocks[i] = new CachedItem("block" + i, r.nextInt((int)maxSize)+1);
711     }
712     return blocks;
713   }
714 
715   private long calculateBlockSize(long maxSize, int numBlocks) {
716     long roughBlockSize = maxSize / numBlocks;
717     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
718     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
719         ClassSize.CONCURRENT_HASHMAP +
720         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
721         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
722     long negateBlockSize = (long)(totalOverhead/numEntries);
723     negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
724     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*0.99f));
725   }
726 
727   private long calculateBlockSizeDefault(long maxSize, int numBlocks) {
728     long roughBlockSize = maxSize / numBlocks;
729     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
730     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
731         ClassSize.CONCURRENT_HASHMAP +
732         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
733         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
734     long negateBlockSize = totalOverhead / numEntries;
735     negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
736     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*
737         LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
738   }
739 
740   private static class CachedItem implements Cacheable {
741     BlockCacheKey cacheKey;
742     int size;
743 
744     CachedItem(String blockName, int size) {
745       this.cacheKey = new BlockCacheKey(blockName, 0);
746       this.size = size;
747     }
748 
749     /** The size of this item reported to the block cache layer */
750     @Override
751     public long heapSize() {
752       return ClassSize.align(size);
753     }
754 
755     /** Size of the cache block holding this item. Used for verification. */
756     public long cacheBlockHeapSize() {
757       return LruCachedBlock.PER_BLOCK_OVERHEAD
758           + ClassSize.align(cacheKey.heapSize())
759           + ClassSize.align(size);
760     }
761 
762     @Override
763     public int getSerializedLength() {
764       return 0;
765     }
766 
767     @Override
768     public CacheableDeserializer<Cacheable> getDeserializer() {
769       return null;
770     }
771 
772     @Override
773     public void serialize(ByteBuffer destination) {
774     }
775     
776     @Override
777     public BlockType getBlockType() {
778       return BlockType.DATA;
779     }
780 
781   }
782 
783 }
784