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