1   /**
2    * Copyright 2009 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.io.hfile;
21  
22  import java.nio.ByteBuffer;
23  import java.util.Random;
24  
25  import org.apache.hadoop.hbase.io.HeapSize;
26  import org.apache.hadoop.hbase.util.ClassSize;
27  
28  import junit.framework.TestCase;
29  
30  /**
31   * Tests the concurrent LruBlockCache.<p>
32   *
33   * Tests will ensure it grows and shrinks in size properly,
34   * evictions run when they're supposed to and do what they should,
35   * and that cached blocks are accessible when expected to be.
36   */
37  public class TestLruBlockCache extends TestCase {
38  
39    public void testBackgroundEvictionThread() throws Exception {
40  
41      long maxSize = 100000;
42      long blockSize = calculateBlockSizeDefault(maxSize, 9); // room for 9, will evict
43  
44      LruBlockCache cache = new LruBlockCache(maxSize,blockSize);
45  
46      Block [] blocks = generateFixedBlocks(10, blockSize, "block");
47  
48      // Add all the blocks
49      for(Block block : blocks) {
50        cache.cacheBlock(block.blockName, block.buf);
51      }
52  
53      // Let the eviction run
54      int n = 0;
55      while(cache.getEvictionCount() == 0) {
56        System.out.println("sleep");
57        Thread.sleep(1000);
58        assertTrue(n++ < 2);
59      }
60      System.out.println("Background Evictions run: " + cache.getEvictionCount());
61  
62      // A single eviction run should have occurred
63      assertEquals(cache.getEvictionCount(), 1);
64    }
65  
66    public void testCacheSimple() throws Exception {
67  
68      long maxSize = 1000000;
69      long blockSize = calculateBlockSizeDefault(maxSize, 101);
70  
71      LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
72  
73      Block [] blocks = generateRandomBlocks(100, blockSize);
74  
75      long expectedCacheSize = cache.heapSize();
76  
77      // Confirm empty
78      for(Block block : blocks) {
79        assertTrue(cache.getBlock(block.blockName, true) == null);
80      }
81  
82      // Add blocks
83      for(Block block : blocks) {
84        cache.cacheBlock(block.blockName, block.buf);
85        expectedCacheSize += block.heapSize();
86      }
87  
88      // Verify correctly calculated cache heap size
89      assertEquals(expectedCacheSize, cache.heapSize());
90  
91      // Check if all blocks are properly cached and retrieved
92      for(Block block : blocks) {
93        ByteBuffer buf = cache.getBlock(block.blockName, true);
94        assertTrue(buf != null);
95        assertEquals(buf.capacity(), block.buf.capacity());
96      }
97  
98      // Re-add same blocks and ensure nothing has changed
99      for(Block block : blocks) {
100       try {
101         cache.cacheBlock(block.blockName, block.buf);
102         assertTrue("Cache should not allow re-caching a block", false);
103       } catch(RuntimeException re) {
104         // expected
105       }
106     }
107 
108     // Verify correctly calculated cache heap size
109     assertEquals(expectedCacheSize, cache.heapSize());
110 
111     // Check if all blocks are properly cached and retrieved
112     for(Block block : blocks) {
113       ByteBuffer buf = cache.getBlock(block.blockName, true);
114       assertTrue(buf != null);
115       assertEquals(buf.capacity(), block.buf.capacity());
116     }
117 
118     // Expect no evictions
119     assertEquals(0, cache.getEvictionCount());
120     Thread t = new LruBlockCache.StatisticsThread(cache);
121     t.start();
122     t.join();
123   }
124 
125   public void testCacheEvictionSimple() throws Exception {
126 
127     long maxSize = 100000;
128     long blockSize = calculateBlockSizeDefault(maxSize, 10);
129 
130     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
131 
132     Block [] blocks = generateFixedBlocks(10, blockSize, "block");
133 
134     long expectedCacheSize = cache.heapSize();
135 
136     // Add all the blocks
137     for(Block block : blocks) {
138       cache.cacheBlock(block.blockName, block.buf);
139       expectedCacheSize += block.heapSize();
140     }
141 
142     // A single eviction run should have occurred
143     assertEquals(1, cache.getEvictionCount());
144 
145     // Our expected size overruns acceptable limit
146     assertTrue(expectedCacheSize >
147       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
148 
149     // But the cache did not grow beyond max
150     assertTrue(cache.heapSize() < maxSize);
151 
152     // And is still below the acceptable limit
153     assertTrue(cache.heapSize() <
154         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
155 
156     // All blocks except block 0 and 1 should be in the cache
157     assertTrue(cache.getBlock(blocks[0].blockName, true) == null);
158     assertTrue(cache.getBlock(blocks[1].blockName, true) == null);
159     for(int i=2;i<blocks.length;i++) {
160       assertEquals(cache.getBlock(blocks[i].blockName, true),
161           blocks[i].buf);
162     }
163   }
164 
165   public void testCacheEvictionTwoPriorities() throws Exception {
166 
167     long maxSize = 100000;
168     long blockSize = calculateBlockSizeDefault(maxSize, 10);
169 
170     LruBlockCache cache = new LruBlockCache(maxSize,blockSize,false);
171 
172     Block [] singleBlocks = generateFixedBlocks(5, 10000, "single");
173     Block [] multiBlocks = generateFixedBlocks(5, 10000, "multi");
174 
175     long expectedCacheSize = cache.heapSize();
176 
177     // Add and get the multi blocks
178     for(Block block : multiBlocks) {
179       cache.cacheBlock(block.blockName, block.buf);
180       expectedCacheSize += block.heapSize();
181       assertEquals(cache.getBlock(block.blockName, true), block.buf);
182     }
183 
184     // Add the single blocks (no get)
185     for(Block block : singleBlocks) {
186       cache.cacheBlock(block.blockName, block.buf);
187       expectedCacheSize += block.heapSize();
188     }
189 
190     // A single eviction run should have occurred
191     assertEquals(cache.getEvictionCount(), 1);
192 
193     // We expect two entries evicted
194     assertEquals(cache.getEvictedCount(), 2);
195 
196     // Our expected size overruns acceptable limit
197     assertTrue(expectedCacheSize >
198       (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
199 
200     // But the cache did not grow beyond max
201     assertTrue(cache.heapSize() <= maxSize);
202 
203     // And is now below the acceptable limit
204     assertTrue(cache.heapSize() <=
205         (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
206 
207     // We expect fairness across the two priorities.
208     // This test makes multi go barely over its limit, in-memory
209     // empty, and the rest in single.  Two single evictions and
210     // one multi eviction expected.
211     assertTrue(cache.getBlock(singleBlocks[0].blockName, true) == null);
212     assertTrue(cache.getBlock(multiBlocks[0].blockName, true) == null);
213 
214     // And all others to be cached
215     for(int i=1;i<4;i++) {
216       assertEquals(cache.getBlock(singleBlocks[i].blockName, true),
217           singleBlocks[i].buf);
218       assertEquals(cache.getBlock(multiBlocks[i].blockName, true),
219           multiBlocks[i].buf);
220     }
221   }
222 
223   public void testCacheEvictionThreePriorities() throws Exception {
224 
225     long maxSize = 100000;
226     long blockSize = calculateBlockSize(maxSize, 10);
227 
228     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
229         (int)Math.ceil(1.2*maxSize/blockSize),
230         LruBlockCache.DEFAULT_LOAD_FACTOR,
231         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
232         0.98f, // min
233         0.99f, // acceptable
234         0.33f, // single
235         0.33f, // multi
236         0.34f);// memory
237 
238 
239     Block [] singleBlocks = generateFixedBlocks(5, blockSize, "single");
240     Block [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
241     Block [] memoryBlocks = generateFixedBlocks(5, blockSize, "memory");
242 
243     long expectedCacheSize = cache.heapSize();
244 
245     // Add 3 blocks from each priority
246     for(int i=0;i<3;i++) {
247 
248       // Just add single blocks
249       cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
250       expectedCacheSize += singleBlocks[i].heapSize();
251 
252       // Add and get multi blocks
253       cache.cacheBlock(multiBlocks[i].blockName, multiBlocks[i].buf);
254       expectedCacheSize += multiBlocks[i].heapSize();
255       cache.getBlock(multiBlocks[i].blockName, true);
256 
257       // Add memory blocks as such
258       cache.cacheBlock(memoryBlocks[i].blockName, memoryBlocks[i].buf, true);
259       expectedCacheSize += memoryBlocks[i].heapSize();
260 
261     }
262 
263     // Do not expect any evictions yet
264     assertEquals(0, cache.getEvictionCount());
265 
266     // Verify cache size
267     assertEquals(expectedCacheSize, cache.heapSize());
268 
269     // Insert a single block, oldest single should be evicted
270     cache.cacheBlock(singleBlocks[3].blockName, singleBlocks[3].buf);
271 
272     // Single eviction, one thing evicted
273     assertEquals(1, cache.getEvictionCount());
274     assertEquals(1, cache.getEvictedCount());
275 
276     // Verify oldest single block is the one evicted
277     assertEquals(null, cache.getBlock(singleBlocks[0].blockName, true));
278 
279     // Change the oldest remaining single block to a multi
280     cache.getBlock(singleBlocks[1].blockName, true);
281 
282     // Insert another single block
283     cache.cacheBlock(singleBlocks[4].blockName, singleBlocks[4].buf);
284 
285     // Two evictions, two evicted.
286     assertEquals(2, cache.getEvictionCount());
287     assertEquals(2, cache.getEvictedCount());
288 
289     // Oldest multi block should be evicted now
290     assertEquals(null, cache.getBlock(multiBlocks[0].blockName, true));
291 
292     // Insert another memory block
293     cache.cacheBlock(memoryBlocks[3].blockName, memoryBlocks[3].buf, true);
294 
295     // Three evictions, three evicted.
296     assertEquals(3, cache.getEvictionCount());
297     assertEquals(3, cache.getEvictedCount());
298 
299     // Oldest memory block should be evicted now
300     assertEquals(null, cache.getBlock(memoryBlocks[0].blockName, true));
301 
302     // Add a block that is twice as big (should force two evictions)
303     Block [] bigBlocks = generateFixedBlocks(3, blockSize*3, "big");
304     cache.cacheBlock(bigBlocks[0].blockName, bigBlocks[0].buf);
305 
306     // Four evictions, six evicted (inserted block 3X size, expect +3 evicted)
307     assertEquals(4, cache.getEvictionCount());
308     assertEquals(6, cache.getEvictedCount());
309 
310     // Expect three remaining singles to be evicted
311     assertEquals(null, cache.getBlock(singleBlocks[2].blockName, true));
312     assertEquals(null, cache.getBlock(singleBlocks[3].blockName, true));
313     assertEquals(null, cache.getBlock(singleBlocks[4].blockName, true));
314 
315     // Make the big block a multi block
316     cache.getBlock(bigBlocks[0].blockName, true);
317 
318     // Cache another single big block
319     cache.cacheBlock(bigBlocks[1].blockName, bigBlocks[1].buf);
320 
321     // Five evictions, nine evicted (3 new)
322     assertEquals(5, cache.getEvictionCount());
323     assertEquals(9, cache.getEvictedCount());
324 
325     // Expect three remaining multis to be evicted
326     assertEquals(null, cache.getBlock(singleBlocks[1].blockName, true));
327     assertEquals(null, cache.getBlock(multiBlocks[1].blockName, true));
328     assertEquals(null, cache.getBlock(multiBlocks[2].blockName, true));
329 
330     // Cache a big memory block
331     cache.cacheBlock(bigBlocks[2].blockName, bigBlocks[2].buf, true);
332 
333     // Six evictions, twelve evicted (3 new)
334     assertEquals(6, cache.getEvictionCount());
335     assertEquals(12, cache.getEvictedCount());
336 
337     // Expect three remaining in-memory to be evicted
338     assertEquals(null, cache.getBlock(memoryBlocks[1].blockName, true));
339     assertEquals(null, cache.getBlock(memoryBlocks[2].blockName, true));
340     assertEquals(null, cache.getBlock(memoryBlocks[3].blockName, true));
341 
342 
343   }
344 
345   // test scan resistance
346   public void testScanResistance() throws Exception {
347 
348     long maxSize = 100000;
349     long blockSize = calculateBlockSize(maxSize, 10);
350 
351     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
352         (int)Math.ceil(1.2*maxSize/blockSize),
353         LruBlockCache.DEFAULT_LOAD_FACTOR,
354         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
355         0.66f, // min
356         0.99f, // acceptable
357         0.33f, // single
358         0.33f, // multi
359         0.34f);// memory
360 
361     Block [] singleBlocks = generateFixedBlocks(20, blockSize, "single");
362     Block [] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
363 
364     // Add 5 multi blocks
365     for(Block block : multiBlocks) {
366       cache.cacheBlock(block.blockName, block.buf);
367       cache.getBlock(block.blockName, true);
368     }
369 
370     // Add 5 single blocks
371     for(int i=0;i<5;i++) {
372       cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
373     }
374 
375     // An eviction ran
376     assertEquals(1, cache.getEvictionCount());
377 
378     // To drop down to 2/3 capacity, we'll need to evict 4 blocks
379     assertEquals(4, cache.getEvictedCount());
380 
381     // Should have been taken off equally from single and multi
382     assertEquals(null, cache.getBlock(singleBlocks[0].blockName, true));
383     assertEquals(null, cache.getBlock(singleBlocks[1].blockName, true));
384     assertEquals(null, cache.getBlock(multiBlocks[0].blockName, true));
385     assertEquals(null, cache.getBlock(multiBlocks[1].blockName, true));
386 
387     // Let's keep "scanning" by adding single blocks.  From here on we only
388     // expect evictions from the single bucket.
389 
390     // Every time we reach 10 total blocks (every 4 inserts) we get 4 single
391     // blocks evicted.  Inserting 13 blocks should yield 3 more evictions and
392     // 12 more evicted.
393 
394     for(int i=5;i<18;i++) {
395       cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
396     }
397 
398     // 4 total evictions, 16 total evicted
399     assertEquals(4, cache.getEvictionCount());
400     assertEquals(16, cache.getEvictedCount());
401 
402     // Should now have 7 total blocks
403     assertEquals(7, cache.size());
404 
405   }
406 
407   // test setMaxSize
408   public void testResizeBlockCache() throws Exception {
409 
410     long maxSize = 300000;
411     long blockSize = calculateBlockSize(maxSize, 31);
412 
413     LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false,
414         (int)Math.ceil(1.2*maxSize/blockSize),
415         LruBlockCache.DEFAULT_LOAD_FACTOR,
416         LruBlockCache.DEFAULT_CONCURRENCY_LEVEL,
417         0.98f, // min
418         0.99f, // acceptable
419         0.33f, // single
420         0.33f, // multi
421         0.34f);// memory
422 
423     Block [] singleBlocks = generateFixedBlocks(10, blockSize, "single");
424     Block [] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
425     Block [] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
426 
427     // Add all blocks from all priorities
428     for(int i=0;i<10;i++) {
429 
430       // Just add single blocks
431       cache.cacheBlock(singleBlocks[i].blockName, singleBlocks[i].buf);
432 
433       // Add and get multi blocks
434       cache.cacheBlock(multiBlocks[i].blockName, multiBlocks[i].buf);
435       cache.getBlock(multiBlocks[i].blockName, true);
436 
437       // Add memory blocks as such
438       cache.cacheBlock(memoryBlocks[i].blockName, memoryBlocks[i].buf, true);
439     }
440 
441     // Do not expect any evictions yet
442     assertEquals(0, cache.getEvictionCount());
443 
444     // Resize to half capacity plus an extra block (otherwise we evict an extra)
445     cache.setMaxSize((long)(maxSize * 0.5f));
446 
447     // Should have run a single eviction
448     assertEquals(1, cache.getEvictionCount());
449 
450     // And we expect 1/2 of the blocks to be evicted
451     assertEquals(15, cache.getEvictedCount());
452 
453     // And the oldest 5 blocks from each category should be gone
454     for(int i=0;i<5;i++) {
455       assertEquals(null, cache.getBlock(singleBlocks[i].blockName, true));
456       assertEquals(null, cache.getBlock(multiBlocks[i].blockName, true));
457       assertEquals(null, cache.getBlock(memoryBlocks[i].blockName, true));
458     }
459 
460     // And the newest 5 blocks should still be accessible
461     for(int i=5;i<10;i++) {
462       assertEquals(singleBlocks[i].buf, cache.getBlock(singleBlocks[i].blockName, true));
463       assertEquals(multiBlocks[i].buf, cache.getBlock(multiBlocks[i].blockName, true));
464       assertEquals(memoryBlocks[i].buf, cache.getBlock(memoryBlocks[i].blockName, true));
465     }
466   }
467 
468   private Block [] generateFixedBlocks(int numBlocks, int size, String pfx) {
469     Block [] blocks = new Block[numBlocks];
470     for(int i=0;i<numBlocks;i++) {
471       blocks[i] = new Block(pfx + i, size);
472     }
473     return blocks;
474   }
475 
476   private Block [] generateFixedBlocks(int numBlocks, long size, String pfx) {
477     return generateFixedBlocks(numBlocks, (int)size, pfx);
478   }
479 
480   private Block [] generateRandomBlocks(int numBlocks, long maxSize) {
481     Block [] blocks = new Block[numBlocks];
482     Random r = new Random();
483     for(int i=0;i<numBlocks;i++) {
484       blocks[i] = new Block("block" + i, r.nextInt((int)maxSize)+1);
485     }
486     return blocks;
487   }
488 
489   private long calculateBlockSize(long maxSize, int numBlocks) {
490     long roughBlockSize = maxSize / numBlocks;
491     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
492     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
493         ClassSize.CONCURRENT_HASHMAP +
494         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
495         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
496     long negateBlockSize = (long)(totalOverhead/numEntries);
497     negateBlockSize += CachedBlock.PER_BLOCK_OVERHEAD;
498     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*0.99f));
499   }
500 
501   private long calculateBlockSizeDefault(long maxSize, int numBlocks) {
502     long roughBlockSize = maxSize / numBlocks;
503     int numEntries = (int)Math.ceil((1.2)*maxSize/roughBlockSize);
504     long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD +
505         ClassSize.CONCURRENT_HASHMAP +
506         (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
507         (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
508     long negateBlockSize = totalOverhead / numEntries;
509     negateBlockSize += CachedBlock.PER_BLOCK_OVERHEAD;
510     return ClassSize.align((long)Math.floor((roughBlockSize - negateBlockSize)*
511         LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
512   }
513 
514   private static class Block implements HeapSize {
515     String blockName;
516     ByteBuffer buf;
517 
518     Block(String blockName, int size) {
519       this.blockName = blockName;
520       this.buf = ByteBuffer.allocate(size);
521     }
522 
523     public long heapSize() {
524       return CachedBlock.PER_BLOCK_OVERHEAD +
525       ClassSize.align(blockName.length()) +
526       ClassSize.align(buf.capacity());
527     }
528   }
529 }