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.io.HeapSize;
28  import org.apache.hadoop.hbase.io.hfile.LruBlockCache.EvictionThread;
29  import org.apache.hadoop.hbase.testclassification.SmallTests;
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     // Verify correctly calculated cache heap size
129     assertEquals(expectedCacheSize, cache.heapSize());
130 
131     // Check if all blocks are properly cached and retrieved
132     for (CachedItem block : blocks) {
133       HeapSize buf = cache.getBlock(block.cacheKey, true, false, true);
134       assertTrue(buf != null);
135       assertEquals(buf.heapSize(), block.heapSize());
136     }
137 
138     // Expect no evictions
139     assertEquals(0, cache.getStats().getEvictionCount());
140     Thread t = new LruBlockCache.StatisticsThread(cache);
141     t.start();
142     t.join();
143   }
144 
145   @Test
146   public void testCacheEvictionSimple() throws Exception {
147 
148     long maxSize = 100000;
149     long blockSize = calculateBlockSizeDefault(maxSize, 10);
150 
151     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
152 
153     CachedItem [] blocks = generateFixedBlocks(10, blockSize, "block");
154 
155     long expectedCacheSize = cache.heapSize();
156 
157     // Add all the blocks
158     for (CachedItem block : blocks) {
159       cache.cacheBlock(block.cacheKey, block);
160       expectedCacheSize += block.cacheBlockHeapSize();
161     }
162 
163     // A single eviction run should have occurred
164     assertEquals(1, cache.getStats().getEvictionCount());
165 
166     // Our expected size overruns acceptable limit
167     assertTrue(expectedCacheSize >
168       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
169 
170     // But the cache did not grow beyond max
171     assertTrue(cache.heapSize() < maxSize);
172 
173     // And is still below the acceptable limit
174     assertTrue(cache.heapSize() <
175         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
176 
177     // All blocks except block 0  should be in the cache
178     assertTrue(cache.getBlock(blocks[0].cacheKey, true, false, true) == null);
179     for(int i=1;i<blocks.length;i++) {
180       assertEquals(cache.getBlock(blocks[i].cacheKey, true, false, true),
181           blocks[i]);
182     }
183   }
184 
185   @Test
186   public void testCacheEvictionTwoPriorities() throws Exception {
187 
188     long maxSize = 100000;
189     long blockSize = calculateBlockSizeDefault(maxSize, 10);
190 
191     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
192 
193     CachedItem [] singleBlocks = generateFixedBlocks(5, 10000, "single");
194     CachedItem [] multiBlocks = generateFixedBlocks(5, 10000, "multi");
195 
196     long expectedCacheSize = cache.heapSize();
197 
198     // Add and get the multi blocks
199     for (CachedItem block : multiBlocks) {
200       cache.cacheBlock(block.cacheKey, block);
201       expectedCacheSize += block.cacheBlockHeapSize();
202       assertEquals(cache.getBlock(block.cacheKey, true, false, true), block);
203     }
204 
205     // Add the single blocks (no get)
206     for (CachedItem block : singleBlocks) {
207       cache.cacheBlock(block.cacheKey, block);
208       expectedCacheSize += block.heapSize();
209     }
210 
211     // A single eviction run should have occurred
212     assertEquals(cache.getStats().getEvictionCount(), 1);
213 
214     // We expect two entries evicted
215     assertEquals(cache.getStats().getEvictedCount(), 2);
216 
217     // Our expected size overruns acceptable limit
218     assertTrue(expectedCacheSize >
219       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
220 
221     // But the cache did not grow beyond max
222     assertTrue(cache.heapSize() <= maxSize);
223 
224     // And is now below the acceptable limit
225     assertTrue(cache.heapSize() <=
226         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
227 
228     // We expect fairness across the two priorities.
229     // This test makes multi go barely over its limit, in-memory
230     // empty, and the rest in single.  Two single evictions and
231     // one multi eviction expected.
232     assertTrue(cache.getBlock(singleBlocks[0].cacheKey, true, false, true) == null);
233     assertTrue(cache.getBlock(multiBlocks[0].cacheKey, true, false, true) == null);
234 
235     // And all others to be cached
236     for(int i=1;i<4;i++) {
237       assertEquals(cache.getBlock(singleBlocks[i].cacheKey, true, false, true),
238           singleBlocks[i]);
239       assertEquals(cache.getBlock(multiBlocks[i].cacheKey, true, false, true),
240           multiBlocks[i]);
241     }
242   }
243 
244   @Test
245   public void testCacheEvictionThreePriorities() throws Exception {
246 
247     long maxSize = 100000;
248     long blockSize = calculateBlockSize(maxSize, 10);
249 
250     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
251         (int)Math.ceil(1.2*maxSize/blockSize),
252         LruBlockCache.DEFAULT_LOAD_FACTOR,
253         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
254         0.98f, // min
255         0.99f, // acceptable
256         0.33f, // single
257         0.33f, // multi
258         0.34f, // memory
259         false);
260 
261     CachedItem [] singleBlocks = generateFixedBlocks(5, blockSize, "single");
262     CachedItem [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
263     CachedItem [] memoryBlocks = generateFixedBlocks(5, blockSize, "memory");
264 
265     long expectedCacheSize = cache.heapSize();
266 
267     // Add 3 blocks from each priority
268     for(int i=0;i<3;i++) {
269 
270       // Just add single blocks
271       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
272       expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
273 
274       // Add and get multi blocks
275       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
276       expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
277       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
278 
279       // Add memory blocks as such
280       cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true);
281       expectedCacheSize += memoryBlocks[i].cacheBlockHeapSize();
282 
283     }
284 
285     // Do not expect any evictions yet
286     assertEquals(0, cache.getStats().getEvictionCount());
287 
288     // Verify cache size
289     assertEquals(expectedCacheSize, cache.heapSize());
290 
291     // Insert a single block, oldest single should be evicted
292     cache.cacheBlock(singleBlocks[3].cacheKey, singleBlocks[3]);
293 
294     // Single eviction, one thing evicted
295     assertEquals(1, cache.getStats().getEvictionCount());
296     assertEquals(1, cache.getStats().getEvictedCount());
297 
298     // Verify oldest single block is the one evicted
299     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
300 
301     // Change the oldest remaining single block to a multi
302     cache.getBlock(singleBlocks[1].cacheKey, true, false, true);
303 
304     // Insert another single block
305     cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
306 
307     // Two evictions, two evicted.
308     assertEquals(2, cache.getStats().getEvictionCount());
309     assertEquals(2, cache.getStats().getEvictedCount());
310 
311     // Oldest multi block should be evicted now
312     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
313 
314     // Insert another memory block
315     cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true);
316 
317     // Three evictions, three evicted.
318     assertEquals(3, cache.getStats().getEvictionCount());
319     assertEquals(3, cache.getStats().getEvictedCount());
320 
321     // Oldest memory block should be evicted now
322     assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
323 
324     // Add a block that is twice as big (should force two evictions)
325     CachedItem [] bigBlocks = generateFixedBlocks(3, blockSize*3, "big");
326     cache.cacheBlock(bigBlocks[0].cacheKey, bigBlocks[0]);
327 
328     // Four evictions, six evicted (inserted block 3X size, expect +3 evicted)
329     assertEquals(4, cache.getStats().getEvictionCount());
330     assertEquals(6, cache.getStats().getEvictedCount());
331 
332     // Expect three remaining singles to be evicted
333     assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
334     assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
335     assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
336 
337     // Make the big block a multi block
338     cache.getBlock(bigBlocks[0].cacheKey, true, false, true);
339 
340     // Cache another single big block
341     cache.cacheBlock(bigBlocks[1].cacheKey, bigBlocks[1]);
342 
343     // Five evictions, nine evicted (3 new)
344     assertEquals(5, cache.getStats().getEvictionCount());
345     assertEquals(9, cache.getStats().getEvictedCount());
346 
347     // Expect three remaining multis to be evicted
348     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
349     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
350     assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
351 
352     // Cache a big memory block
353     cache.cacheBlock(bigBlocks[2].cacheKey, bigBlocks[2], true);
354 
355     // Six evictions, twelve evicted (3 new)
356     assertEquals(6, cache.getStats().getEvictionCount());
357     assertEquals(12, cache.getStats().getEvictedCount());
358 
359     // Expect three remaining in-memory to be evicted
360     assertEquals(null, cache.getBlock(memoryBlocks[1].cacheKey, true, false, true));
361     assertEquals(null, cache.getBlock(memoryBlocks[2].cacheKey, true, false, true));
362     assertEquals(null, cache.getBlock(memoryBlocks[3].cacheKey, true, false, true));
363   }
364 
365   @Test
366   public void testCacheEvictionInMemoryForceMode() throws Exception {
367     long maxSize = 100000;
368     long blockSize = calculateBlockSize(maxSize, 10);
369 
370     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
371         (int)Math.ceil(1.2*maxSize/blockSize),
372         LruBlockCache.DEFAULT_LOAD_FACTOR,
373         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
374         0.98f, // min
375         0.99f, // acceptable
376         0.2f, // single
377         0.3f, // multi
378         0.5f, // memory
379         true);
380 
381     CachedItem [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
382     CachedItem [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
383     CachedItem [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
384 
385     long expectedCacheSize = cache.heapSize();
386 
387     // 0. Add 5 single blocks and 4 multi blocks to make cache full, si:mu:me = 5:4:0
388     for(int i = 0; i < 4; i++) {
389       // Just add single blocks
390       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
391       expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
392       // Add and get multi blocks
393       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
394       expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
395       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
396     }
397     // 5th single block
398     cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
399     expectedCacheSize += singleBlocks[4].cacheBlockHeapSize();
400     // Do not expect any evictions yet
401     assertEquals(0, cache.getStats().getEvictionCount());
402     // Verify cache size
403     assertEquals(expectedCacheSize, cache.heapSize());
404 
405     // 1. Insert a memory block, oldest single should be evicted, si:mu:me = 4:4:1
406     cache.cacheBlock(memoryBlocks[0].cacheKey, memoryBlocks[0], true);
407     // Single eviction, one block evicted
408     assertEquals(1, cache.getStats().getEvictionCount());
409     assertEquals(1, cache.getStats().getEvictedCount());
410     // Verify oldest single block (index = 0) is the one evicted
411     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
412 
413     // 2. Insert another memory block, another single evicted, si:mu:me = 3:4:2
414     cache.cacheBlock(memoryBlocks[1].cacheKey, memoryBlocks[1], true);
415     // Two evictions, two evicted.
416     assertEquals(2, cache.getStats().getEvictionCount());
417     assertEquals(2, cache.getStats().getEvictedCount());
418     // Current oldest single block (index = 1) should be evicted now
419     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
420 
421     // 3. Insert 4 memory blocks, 2 single and 2 multi evicted, si:mu:me = 1:2:6
422     cache.cacheBlock(memoryBlocks[2].cacheKey, memoryBlocks[2], true);
423     cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true);
424     cache.cacheBlock(memoryBlocks[4].cacheKey, memoryBlocks[4], true);
425     cache.cacheBlock(memoryBlocks[5].cacheKey, memoryBlocks[5], true);
426     // Three evictions, three evicted.
427     assertEquals(6, cache.getStats().getEvictionCount());
428     assertEquals(6, cache.getStats().getEvictedCount());
429     // two oldest single blocks and two oldest multi blocks evicted
430     assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
431     assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
432     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
433     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
434 
435     // 4. Insert 3 memory blocks, the remaining 1 single and 2 multi evicted
436     // si:mu:me = 0:0:9
437     cache.cacheBlock(memoryBlocks[6].cacheKey, memoryBlocks[6], true);
438     cache.cacheBlock(memoryBlocks[7].cacheKey, memoryBlocks[7], true);
439     cache.cacheBlock(memoryBlocks[8].cacheKey, memoryBlocks[8], true);
440     // Three evictions, three evicted.
441     assertEquals(9, cache.getStats().getEvictionCount());
442     assertEquals(9, cache.getStats().getEvictedCount());
443     // one oldest single block and two oldest multi blocks evicted
444     assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
445     assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
446     assertEquals(null, cache.getBlock(multiBlocks[3].cacheKey, true, false, true));
447 
448     // 5. Insert one memory block, the oldest memory evicted
449     // si:mu:me = 0:0:9
450     cache.cacheBlock(memoryBlocks[9].cacheKey, memoryBlocks[9], true);
451     // one eviction, one evicted.
452     assertEquals(10, cache.getStats().getEvictionCount());
453     assertEquals(10, cache.getStats().getEvictedCount());
454     // oldest memory block evicted
455     assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
456 
457     // 6. Insert one new single block, itself evicted immediately since
458     //    all blocks in cache are memory-type which have higher priority
459     // si:mu:me = 0:0:9 (no change)
460     cache.cacheBlock(singleBlocks[9].cacheKey, singleBlocks[9]);
461     // one eviction, one evicted.
462     assertEquals(11, cache.getStats().getEvictionCount());
463     assertEquals(11, cache.getStats().getEvictedCount());
464     // the single block just cached now evicted (can't evict memory)
465     assertEquals(null, cache.getBlock(singleBlocks[9].cacheKey, true, false, true));
466   }
467 
468   // test scan resistance
469   @Test
470   public void testScanResistance() throws Exception {
471 
472     long maxSize = 100000;
473     long blockSize = calculateBlockSize(maxSize, 10);
474 
475     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
476         (int)Math.ceil(1.2*maxSize/blockSize),
477         LruBlockCache.DEFAULT_LOAD_FACTOR,
478         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
479         0.66f, // min
480         0.99f, // acceptable
481         0.33f, // single
482         0.33f, // multi
483         0.34f, // memory
484         false);
485 
486     CachedItem [] singleBlocks = generateFixedBlocks(20, blockSize, "single");
487     CachedItem [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
488 
489     // Add 5 multi blocks
490     for (CachedItem block : multiBlocks) {
491       cache.cacheBlock(block.cacheKey, block);
492       cache.getBlock(block.cacheKey, true, false, true);
493     }
494 
495     // Add 5 single blocks
496     for(int i=0;i<5;i++) {
497       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
498     }
499 
500     // An eviction ran
501     assertEquals(1, cache.getStats().getEvictionCount());
502 
503     // To drop down to 2/3 capacity, we'll need to evict 4 blocks
504     assertEquals(4, cache.getStats().getEvictedCount());
505 
506     // Should have been taken off equally from single and multi
507     assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
508     assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
509     assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
510     assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
511 
512     // Let's keep "scanning" by adding single blocks.  From here on we only
513     // expect evictions from the single bucket.
514 
515     // Every time we reach 10 total blocks (every 4 inserts) we get 4 single
516     // blocks evicted.  Inserting 13 blocks should yield 3 more evictions and
517     // 12 more evicted.
518 
519     for(int i=5;i<18;i++) {
520       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
521     }
522 
523     // 4 total evictions, 16 total evicted
524     assertEquals(4, cache.getStats().getEvictionCount());
525     assertEquals(16, cache.getStats().getEvictedCount());
526 
527     // Should now have 7 total blocks
528     assertEquals(7, cache.getBlockCount());
529 
530   }
531 
532   // test setMaxSize
533   @Test
534   public void testResizeBlockCache() throws Exception {
535 
536     long maxSize = 300000;
537     long blockSize = calculateBlockSize(maxSize, 31);
538 
539     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
540         (int)Math.ceil(1.2*maxSize/blockSize),
541         LruBlockCache.DEFAULT_LOAD_FACTOR,
542         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
543         0.98f, // min
544         0.99f, // acceptable
545         0.33f, // single
546         0.33f, // multi
547         0.34f, // memory
548         false);
549 
550     CachedItem [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
551     CachedItem [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
552     CachedItem [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
553 
554     // Add all blocks from all priorities
555     for(int i=0;i<10;i++) {
556 
557       // Just add single blocks
558       cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
559 
560       // Add and get multi blocks
561       cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
562       cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
563 
564       // Add memory blocks as such
565       cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true);
566     }
567 
568     // Do not expect any evictions yet
569     assertEquals(0, cache.getStats().getEvictionCount());
570 
571     // Resize to half capacity plus an extra block (otherwise we evict an extra)
572     cache.setMaxSize((long)(maxSize * 0.5f));
573 
574     // Should have run a single eviction
575     assertEquals(1, cache.getStats().getEvictionCount());
576 
577     // And we expect 1/2 of the blocks to be evicted
578     assertEquals(15, cache.getStats().getEvictedCount());
579 
580     // And the oldest 5 blocks from each category should be gone
581     for(int i=0;i<5;i++) {
582       assertEquals(null, cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
583       assertEquals(null, cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
584       assertEquals(null, cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
585     }
586 
587     // And the newest 5 blocks should still be accessible
588     for(int i=5;i<10;i++) {
589       assertEquals(singleBlocks[i], cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
590       assertEquals(multiBlocks[i], cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
591       assertEquals(memoryBlocks[i], cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
592     }
593   }
594 
595   // test metricsPastNPeriods
596   @Test
597   public void testPastNPeriodsMetrics() throws Exception {
598    double delta = 0.01;
599 
600     // 3 total periods
601     CacheStats stats = new CacheStats(3);
602 
603     // No accesses, should be 0
604     stats.rollMetricsPeriod();
605     assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
606     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
607 
608     // period 1, 1 hit caching, 1 hit non-caching, 2 miss non-caching
609     // should be (2/4)=0.5 and (1/1)=1
610     stats.hit(false);
611     stats.hit(true);
612     stats.miss(false);
613     stats.miss(false);
614     stats.rollMetricsPeriod();
615     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
616     assertEquals(1.0, stats.getHitCachingRatioPastNPeriods(), delta);
617 
618     // period 2, 1 miss caching, 3 miss non-caching
619     // should be (2/8)=0.25 and (1/2)=0.5
620     stats.miss(true);
621     stats.miss(false);
622     stats.miss(false);
623     stats.miss(false);
624     stats.rollMetricsPeriod();
625     assertEquals(0.25, stats.getHitRatioPastNPeriods(), delta);
626     assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
627 
628     // period 3, 2 hits of each type
629     // should be (6/12)=0.5 and (3/4)=0.75
630     stats.hit(false);
631     stats.hit(true);
632     stats.hit(false);
633     stats.hit(true);
634     stats.rollMetricsPeriod();
635     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
636     assertEquals(0.75, stats.getHitCachingRatioPastNPeriods(), delta);
637 
638     // period 4, evict period 1, two caching misses
639     // should be (4/10)=0.4 and (2/5)=0.4
640     stats.miss(true);
641     stats.miss(true);
642     stats.rollMetricsPeriod();
643     assertEquals(0.4, stats.getHitRatioPastNPeriods(), delta);
644     assertEquals(0.4, stats.getHitCachingRatioPastNPeriods(), delta);
645 
646     // period 5, evict period 2, 2 caching misses, 2 non-caching hit
647     // should be (6/10)=0.6 and (2/6)=1/3
648     stats.miss(true);
649     stats.miss(true);
650     stats.hit(false);
651     stats.hit(false);
652     stats.rollMetricsPeriod();
653     assertEquals(0.6, stats.getHitRatioPastNPeriods(), delta);
654     assertEquals((double)1/3, stats.getHitCachingRatioPastNPeriods(), delta);
655 
656     // period 6, evict period 3
657     // should be (2/6)=1/3 and (0/4)=0
658     stats.rollMetricsPeriod();
659     assertEquals((double)1/3, stats.getHitRatioPastNPeriods(), delta);
660     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
661 
662     // period 7, evict period 4
663     // should be (2/4)=0.5 and (0/2)=0
664     stats.rollMetricsPeriod();
665     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
666     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
667 
668     // period 8, evict period 5
669     // should be 0 and 0
670     stats.rollMetricsPeriod();
671     assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
672     assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
673 
674     // period 9, one of each
675     // should be (2/4)=0.5 and (1/2)=0.5
676     stats.miss(true);
677     stats.miss(false);
678     stats.hit(true);
679     stats.hit(false);
680     stats.rollMetricsPeriod();
681     assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
682     assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
683   }
684 
685   private CachedItem [] generateFixedBlocks(int numBlocks, int size, String pfx) {
686     CachedItem [] blocks = new CachedItem[numBlocks];
687     for(int i=0;i<numBlocks;i++) {
688       blocks[i] = new CachedItem(pfx + i, size);
689     }
690     return blocks;
691   }
692 
693   private CachedItem [] generateFixedBlocks(int numBlocks, long size, String pfx) {
694     return generateFixedBlocks(numBlocks, (int)size, pfx);
695   }
696 
697   private CachedItem [] generateRandomBlocks(int numBlocks, long maxSize) {
698     CachedItem [] blocks = new CachedItem[numBlocks];
699     Random r = new Random();
700     for(int i=0;i<numBlocks;i++) {
701       blocks[i] = new CachedItem("block" + i, r.nextInt((int)maxSize)+1);
702     }
703     return blocks;
704   }
705 
706   private long calculateBlockSize(long maxSize, int numBlocks) {
707     long roughBlockSize = maxSize / numBlocks;
708     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
709     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
710         ClassSize.CONCURRENT_HASHMAP +
711         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
712         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
713     long negateBlockSize = (long)(totalOverhead/numEntries);
714     negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
715     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*0.99f));
716   }
717 
718   private long calculateBlockSizeDefault(long maxSize, int numBlocks) {
719     long roughBlockSize = maxSize / numBlocks;
720     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
721     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
722         ClassSize.CONCURRENT_HASHMAP +
723         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
724         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
725     long negateBlockSize = totalOverhead / numEntries;
726     negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
727     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*
728         LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
729   }
730 
731   private static class CachedItem implements Cacheable {
732     BlockCacheKey cacheKey;
733     int size;
734 
735     CachedItem(String blockName, int size) {
736       this.cacheKey = new BlockCacheKey(blockName, 0);
737       this.size = size;
738     }
739 
740     /** The size of this item reported to the block cache layer */
741     @Override
742     public long heapSize() {
743       return ClassSize.align(size);
744     }
745 
746     /** Size of the cache block holding this item. Used for verification. */
747     public long cacheBlockHeapSize() {
748       return LruCachedBlock.PER_BLOCK_OVERHEAD
749           + ClassSize.align(cacheKey.heapSize())
750           + ClassSize.align(size);
751     }
752 
753     @Override
754     public int getSerializedLength() {
755       return 0;
756     }
757 
758     @Override
759     public CacheableDeserializer<Cacheable> getDeserializer() {
760       return null;
761     }
762 
763     @Override
764     public void serialize(ByteBuffer destination) {
765     }
766     
767     @Override
768     public BlockType getBlockType() {
769       return BlockType.DATA;
770     }
771 
772   }
773 
774 }
775