001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.io.hfile;
019
020import static org.apache.hadoop.hbase.io.ByteBuffAllocator.HEAP;
021import static org.junit.Assert.assertEquals;
022import static org.junit.Assert.assertNotNull;
023import static org.junit.Assert.assertNull;
024import static org.junit.Assert.assertTrue;
025
026import java.nio.ByteBuffer;
027import java.util.Random;
028import java.util.concurrent.ExecutorService;
029import java.util.concurrent.Executors;
030import java.util.concurrent.ThreadLocalRandom;
031import java.util.concurrent.TimeUnit;
032import java.util.concurrent.atomic.AtomicBoolean;
033import java.util.concurrent.atomic.AtomicInteger;
034import org.apache.hadoop.conf.Configuration;
035import org.apache.hadoop.hbase.HBaseClassTestRule;
036import org.apache.hadoop.hbase.HBaseConfiguration;
037import org.apache.hadoop.hbase.HConstants;
038import org.apache.hadoop.hbase.Waiter;
039import org.apache.hadoop.hbase.Waiter.ExplainingPredicate;
040import org.apache.hadoop.hbase.io.HeapSize;
041import org.apache.hadoop.hbase.io.hfile.LruBlockCache.EvictionThread;
042import org.apache.hadoop.hbase.nio.ByteBuff;
043import org.apache.hadoop.hbase.testclassification.IOTests;
044import org.apache.hadoop.hbase.testclassification.SmallTests;
045import org.apache.hadoop.hbase.util.ClassSize;
046import org.junit.Assert;
047import org.junit.ClassRule;
048import org.junit.Test;
049import org.junit.experimental.categories.Category;
050import org.slf4j.Logger;
051import org.slf4j.LoggerFactory;
052
053/**
054 * Tests the concurrent LruBlockCache.
055 * <p>
056 * Tests will ensure it grows and shrinks in size properly, evictions run when they're supposed to
057 * and do what they should, and that cached blocks are accessible when expected to be.
058 */
059@Category({ IOTests.class, SmallTests.class })
060public class TestLruBlockCache {
061
062  @ClassRule
063  public static final HBaseClassTestRule CLASS_RULE =
064    HBaseClassTestRule.forClass(TestLruBlockCache.class);
065
066  private static final Logger LOG = LoggerFactory.getLogger(TestLruBlockCache.class);
067
068  private static final Configuration CONF = HBaseConfiguration.create();
069
070  @Test
071  public void testCacheEvictionThreadSafe() throws Exception {
072    long maxSize = 100000;
073    int numBlocks = 9;
074    int testRuns = 10;
075    final long blockSize = calculateBlockSizeDefault(maxSize, numBlocks);
076    assertTrue("calculateBlockSize appears broken.", blockSize * numBlocks <= maxSize);
077
078    final LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
079    EvictionThread evictionThread = cache.getEvictionThread();
080    assertTrue(evictionThread != null);
081    Waiter.waitFor(CONF, 10000, 100, () -> evictionThread.isEnteringRun());
082    final String hfileName = "hfile";
083    int threads = 10;
084    final int blocksPerThread = 5 * numBlocks;
085    for (int run = 0; run != testRuns; ++run) {
086      final AtomicInteger blockCount = new AtomicInteger(0);
087      ExecutorService service = Executors.newFixedThreadPool(threads);
088      for (int i = 0; i != threads; ++i) {
089        service.execute(new Runnable() {
090          @Override
091          public void run() {
092            for (int blockIndex = 0; blockIndex < blocksPerThread
093              || (!cache.isEvictionInProgress()); ++blockIndex) {
094              CachedItem block =
095                new CachedItem(hfileName, (int) blockSize, blockCount.getAndIncrement());
096              boolean inMemory = Math.random() > 0.5;
097              cache.cacheBlock(block.cacheKey, block, inMemory);
098            }
099            cache.evictBlocksByHfileName(hfileName);
100          }
101        });
102      }
103      service.shutdown();
104      // The test may fail here if the evict thread frees the blocks too fast
105      service.awaitTermination(10, TimeUnit.MINUTES);
106      Waiter.waitFor(CONF, 10000, 100, new ExplainingPredicate<Exception>() {
107        @Override
108        public boolean evaluate() throws Exception {
109          return cache.getBlockCount() == 0;
110        }
111
112        @Override
113        public String explainFailure() throws Exception {
114          return "Cache block count failed to return to 0";
115        }
116      });
117      assertEquals(0, cache.getBlockCount());
118      assertEquals(cache.getOverhead(), cache.getCurrentSize());
119    }
120  }
121
122  @Test
123  public void testBackgroundEvictionThread() throws Exception {
124    long maxSize = 100000;
125    int numBlocks = 9;
126    long blockSize = calculateBlockSizeDefault(maxSize, numBlocks);
127    assertTrue("calculateBlockSize appears broken.", blockSize * numBlocks <= maxSize);
128
129    LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
130    EvictionThread evictionThread = cache.getEvictionThread();
131    assertTrue(evictionThread != null);
132
133    CachedItem[] blocks = generateFixedBlocks(numBlocks + 1, blockSize, "block");
134
135    // Make sure eviction thread has entered run method
136    Waiter.waitFor(CONF, 10000, 10, () -> evictionThread.isEnteringRun());
137
138    // Add all the blocks
139    for (CachedItem block : blocks) {
140      cache.cacheBlock(block.cacheKey, block);
141    }
142
143    // wait until at least one eviction has run
144    Waiter.waitFor(CONF, 30000, 200, new ExplainingPredicate<Exception>() {
145
146      @Override
147      public boolean evaluate() throws Exception {
148        return cache.getStats().getEvictionCount() > 0;
149      }
150
151      @Override
152      public String explainFailure() throws Exception {
153        return "Eviction never happened.";
154      }
155    });
156
157    // let cache stabilize
158    // On some systems, the cache will run multiple evictions before it attains
159    // steady-state. For instance, after populating the cache with 10 blocks,
160    // the first eviction evicts a single block and then a second eviction
161    // evicts another. I think this is due to the delta between minSize and
162    // acceptableSize, combined with variance between object overhead on
163    // different environments.
164    int n = 0;
165    for (long prevCnt = 0 /* < number of blocks added */, curCnt = cache.getBlockCount(); prevCnt
166        != curCnt; prevCnt = curCnt, curCnt = cache.getBlockCount()) {
167      Thread.sleep(200);
168      assertTrue("Cache never stabilized.", n++ < 100);
169    }
170
171    long evictionCount = cache.getStats().getEvictionCount();
172    assertTrue(evictionCount >= 1);
173    LOG.info("Background Evictions run: {}", evictionCount);
174  }
175
176  @Test
177  public void testCacheSimple() throws Exception {
178    long maxSize = 1000000;
179    long blockSize = calculateBlockSizeDefault(maxSize, 101);
180
181    LruBlockCache cache = new LruBlockCache(maxSize, blockSize);
182
183    CachedItem[] blocks = generateRandomBlocks(100, blockSize);
184
185    long expectedCacheSize = cache.heapSize();
186
187    // Confirm empty
188    for (CachedItem block : blocks) {
189      assertTrue(cache.getBlock(block.cacheKey, true, false, true) == null);
190    }
191
192    // Add blocks
193    for (CachedItem block : blocks) {
194      cache.cacheBlock(block.cacheKey, block);
195      expectedCacheSize += block.cacheBlockHeapSize();
196    }
197
198    // Verify correctly calculated cache heap size
199    assertEquals(expectedCacheSize, cache.heapSize());
200
201    // Check if all blocks are properly cached and retrieved
202    for (CachedItem block : blocks) {
203      HeapSize buf = cache.getBlock(block.cacheKey, true, false, true);
204      assertTrue(buf != null);
205      assertEquals(buf.heapSize(), block.heapSize());
206    }
207
208    // Re-add same blocks and ensure nothing has changed
209    long expectedBlockCount = cache.getBlockCount();
210    for (CachedItem block : blocks) {
211      cache.cacheBlock(block.cacheKey, block);
212    }
213    assertEquals("Cache should ignore cache requests for blocks already in cache",
214      expectedBlockCount, cache.getBlockCount());
215
216    // Verify correctly calculated cache heap size
217    assertEquals(expectedCacheSize, cache.heapSize());
218
219    // Check if all blocks are properly cached and retrieved
220    for (CachedItem block : blocks) {
221      HeapSize buf = cache.getBlock(block.cacheKey, true, false, true);
222      assertTrue(buf != null);
223      assertEquals(buf.heapSize(), block.heapSize());
224    }
225
226    // Expect no evictions
227    assertEquals(0, cache.getStats().getEvictionCount());
228    Thread t = new LruBlockCache.StatisticsThread(cache);
229    t.start();
230    t.join();
231  }
232
233  @Test
234  public void testCacheEvictionSimple() throws Exception {
235    long maxSize = 100000;
236    long blockSize = calculateBlockSizeDefault(maxSize, 10);
237
238    LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false);
239
240    CachedItem[] blocks = generateFixedBlocks(10, blockSize, "block");
241
242    long expectedCacheSize = cache.heapSize();
243
244    // Add all the blocks
245    for (CachedItem block : blocks) {
246      cache.cacheBlock(block.cacheKey, block);
247      expectedCacheSize += block.cacheBlockHeapSize();
248    }
249
250    // A single eviction run should have occurred
251    assertEquals(1, cache.getStats().getEvictionCount());
252
253    // Our expected size overruns acceptable limit
254    assertTrue(expectedCacheSize > (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
255
256    // But the cache did not grow beyond max
257    assertTrue(cache.heapSize() < maxSize);
258
259    // And is still below the acceptable limit
260    assertTrue(cache.heapSize() < (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
261
262    // All blocks except block 0 should be in the cache
263    assertTrue(cache.getBlock(blocks[0].cacheKey, true, false, true) == null);
264    for (int i = 1; i < blocks.length; i++) {
265      assertEquals(cache.getBlock(blocks[i].cacheKey, true, false, true), blocks[i]);
266    }
267  }
268
269  @Test
270  public void testCacheEvictionTwoPriorities() throws Exception {
271    long maxSize = 100000;
272    long blockSize = calculateBlockSizeDefault(maxSize, 10);
273
274    LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false);
275
276    CachedItem[] singleBlocks = generateFixedBlocks(5, 10000, "single");
277    CachedItem[] multiBlocks = generateFixedBlocks(5, 10000, "multi");
278
279    long expectedCacheSize = cache.heapSize();
280
281    // Add and get the multi blocks
282    for (CachedItem block : multiBlocks) {
283      cache.cacheBlock(block.cacheKey, block);
284      expectedCacheSize += block.cacheBlockHeapSize();
285      assertEquals(cache.getBlock(block.cacheKey, true, false, true), block);
286    }
287
288    // Add the single blocks (no get)
289    for (CachedItem block : singleBlocks) {
290      cache.cacheBlock(block.cacheKey, block);
291      expectedCacheSize += block.heapSize();
292    }
293
294    // A single eviction run should have occurred
295    assertEquals(1, cache.getStats().getEvictionCount());
296
297    // We expect two entries evicted
298    assertEquals(2, cache.getStats().getEvictedCount());
299
300    // Our expected size overruns acceptable limit
301    assertTrue(expectedCacheSize > (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
302
303    // But the cache did not grow beyond max
304    assertTrue(cache.heapSize() <= maxSize);
305
306    // And is now below the acceptable limit
307    assertTrue(cache.heapSize() <= (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
308
309    // We expect fairness across the two priorities.
310    // This test makes multi go barely over its limit, in-memory
311    // empty, and the rest in single. Two single evictions and
312    // one multi eviction expected.
313    assertTrue(cache.getBlock(singleBlocks[0].cacheKey, true, false, true) == null);
314    assertTrue(cache.getBlock(multiBlocks[0].cacheKey, true, false, true) == null);
315
316    // And all others to be cached
317    for (int i = 1; i < 4; i++) {
318      assertEquals(cache.getBlock(singleBlocks[i].cacheKey, true, false, true), singleBlocks[i]);
319      assertEquals(cache.getBlock(multiBlocks[i].cacheKey, true, false, true), multiBlocks[i]);
320    }
321  }
322
323  @Test
324  public void testCacheEvictionThreePriorities() throws Exception {
325    long maxSize = 100000;
326    long blockSize = calculateBlockSize(maxSize, 10);
327
328    LruBlockCache cache =
329      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
330        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min
331        0.99f, // acceptable
332        0.33f, // single
333        0.33f, // multi
334        0.34f, // memory
335        1.2f, // limit
336        false, 16 * 1024 * 1024);
337
338    CachedItem[] singleBlocks = generateFixedBlocks(5, blockSize, "single");
339    CachedItem[] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
340    CachedItem[] memoryBlocks = generateFixedBlocks(5, blockSize, "memory");
341
342    long expectedCacheSize = cache.heapSize();
343
344    // Add 3 blocks from each priority
345    for (int i = 0; i < 3; i++) {
346
347      // Just add single blocks
348      cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
349      expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
350
351      // Add and get multi blocks
352      cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
353      expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
354      cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
355
356      // Add memory blocks as such
357      cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true);
358      expectedCacheSize += memoryBlocks[i].cacheBlockHeapSize();
359
360    }
361
362    // Do not expect any evictions yet
363    assertEquals(0, cache.getStats().getEvictionCount());
364
365    // Verify cache size
366    assertEquals(expectedCacheSize, cache.heapSize());
367
368    // Insert a single block, oldest single should be evicted
369    cache.cacheBlock(singleBlocks[3].cacheKey, singleBlocks[3]);
370
371    // Single eviction, one thing evicted
372    assertEquals(1, cache.getStats().getEvictionCount());
373    assertEquals(1, cache.getStats().getEvictedCount());
374
375    // Verify oldest single block is the one evicted
376    assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
377
378    // Change the oldest remaining single block to a multi
379    cache.getBlock(singleBlocks[1].cacheKey, true, false, true);
380
381    // Insert another single block
382    cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
383
384    // Two evictions, two evicted.
385    assertEquals(2, cache.getStats().getEvictionCount());
386    assertEquals(2, cache.getStats().getEvictedCount());
387
388    // Oldest multi block should be evicted now
389    assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
390
391    // Insert another memory block
392    cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true);
393
394    // Three evictions, three evicted.
395    assertEquals(3, cache.getStats().getEvictionCount());
396    assertEquals(3, cache.getStats().getEvictedCount());
397
398    // Oldest memory block should be evicted now
399    assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
400
401    // Add a block that is twice as big (should force two evictions)
402    CachedItem[] bigBlocks = generateFixedBlocks(3, blockSize * 3, "big");
403    cache.cacheBlock(bigBlocks[0].cacheKey, bigBlocks[0]);
404
405    // Four evictions, six evicted (inserted block 3X size, expect +3 evicted)
406    assertEquals(4, cache.getStats().getEvictionCount());
407    assertEquals(6, cache.getStats().getEvictedCount());
408
409    // Expect three remaining singles to be evicted
410    assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
411    assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
412    assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
413
414    // Make the big block a multi block
415    cache.getBlock(bigBlocks[0].cacheKey, true, false, true);
416
417    // Cache another single big block
418    cache.cacheBlock(bigBlocks[1].cacheKey, bigBlocks[1]);
419
420    // Five evictions, nine evicted (3 new)
421    assertEquals(5, cache.getStats().getEvictionCount());
422    assertEquals(9, cache.getStats().getEvictedCount());
423
424    // Expect three remaining multis to be evicted
425    assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
426    assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
427    assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
428
429    // Cache a big memory block
430    cache.cacheBlock(bigBlocks[2].cacheKey, bigBlocks[2], true);
431
432    // Six evictions, twelve evicted (3 new)
433    assertEquals(6, cache.getStats().getEvictionCount());
434    assertEquals(12, cache.getStats().getEvictedCount());
435
436    // Expect three remaining in-memory to be evicted
437    assertEquals(null, cache.getBlock(memoryBlocks[1].cacheKey, true, false, true));
438    assertEquals(null, cache.getBlock(memoryBlocks[2].cacheKey, true, false, true));
439    assertEquals(null, cache.getBlock(memoryBlocks[3].cacheKey, true, false, true));
440  }
441
442  @Test
443  public void testCacheEvictionInMemoryForceMode() throws Exception {
444    long maxSize = 100000;
445    long blockSize = calculateBlockSize(maxSize, 10);
446
447    LruBlockCache cache =
448      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
449        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min
450        0.99f, // acceptable
451        0.2f, // single
452        0.3f, // multi
453        0.5f, // memory
454        1.2f, // limit
455        true, 16 * 1024 * 1024);
456
457    CachedItem[] singleBlocks = generateFixedBlocks(10, blockSize, "single");
458    CachedItem[] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
459    CachedItem[] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
460
461    long expectedCacheSize = cache.heapSize();
462
463    // 0. Add 5 single blocks and 4 multi blocks to make cache full, si:mu:me = 5:4:0
464    for (int i = 0; i < 4; i++) {
465      // Just add single blocks
466      cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
467      expectedCacheSize += singleBlocks[i].cacheBlockHeapSize();
468      // Add and get multi blocks
469      cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
470      expectedCacheSize += multiBlocks[i].cacheBlockHeapSize();
471      cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
472    }
473    // 5th single block
474    cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]);
475    expectedCacheSize += singleBlocks[4].cacheBlockHeapSize();
476    // Do not expect any evictions yet
477    assertEquals(0, cache.getStats().getEvictionCount());
478    // Verify cache size
479    assertEquals(expectedCacheSize, cache.heapSize());
480
481    // 1. Insert a memory block, oldest single should be evicted, si:mu:me = 4:4:1
482    cache.cacheBlock(memoryBlocks[0].cacheKey, memoryBlocks[0], true);
483    // Single eviction, one block evicted
484    assertEquals(1, cache.getStats().getEvictionCount());
485    assertEquals(1, cache.getStats().getEvictedCount());
486    // Verify oldest single block (index = 0) is the one evicted
487    assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
488
489    // 2. Insert another memory block, another single evicted, si:mu:me = 3:4:2
490    cache.cacheBlock(memoryBlocks[1].cacheKey, memoryBlocks[1], true);
491    // Two evictions, two evicted.
492    assertEquals(2, cache.getStats().getEvictionCount());
493    assertEquals(2, cache.getStats().getEvictedCount());
494    // Current oldest single block (index = 1) should be evicted now
495    assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
496
497    // 3. Insert 4 memory blocks, 2 single and 2 multi evicted, si:mu:me = 1:2:6
498    cache.cacheBlock(memoryBlocks[2].cacheKey, memoryBlocks[2], true);
499    cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true);
500    cache.cacheBlock(memoryBlocks[4].cacheKey, memoryBlocks[4], true);
501    cache.cacheBlock(memoryBlocks[5].cacheKey, memoryBlocks[5], true);
502    // Three evictions, three evicted.
503    assertEquals(6, cache.getStats().getEvictionCount());
504    assertEquals(6, cache.getStats().getEvictedCount());
505    // two oldest single blocks and two oldest multi blocks evicted
506    assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true));
507    assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true));
508    assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
509    assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
510
511    // 4. Insert 3 memory blocks, the remaining 1 single and 2 multi evicted
512    // si:mu:me = 0:0:9
513    cache.cacheBlock(memoryBlocks[6].cacheKey, memoryBlocks[6], true);
514    cache.cacheBlock(memoryBlocks[7].cacheKey, memoryBlocks[7], true);
515    cache.cacheBlock(memoryBlocks[8].cacheKey, memoryBlocks[8], true);
516    // Three evictions, three evicted.
517    assertEquals(9, cache.getStats().getEvictionCount());
518    assertEquals(9, cache.getStats().getEvictedCount());
519    // one oldest single block and two oldest multi blocks evicted
520    assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true));
521    assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true));
522    assertEquals(null, cache.getBlock(multiBlocks[3].cacheKey, true, false, true));
523
524    // 5. Insert one memory block, the oldest memory evicted
525    // si:mu:me = 0:0:9
526    cache.cacheBlock(memoryBlocks[9].cacheKey, memoryBlocks[9], true);
527    // one eviction, one evicted.
528    assertEquals(10, cache.getStats().getEvictionCount());
529    assertEquals(10, cache.getStats().getEvictedCount());
530    // oldest memory block evicted
531    assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true));
532
533    // 6. Insert one new single block, itself evicted immediately since
534    // all blocks in cache are memory-type which have higher priority
535    // si:mu:me = 0:0:9 (no change)
536    cache.cacheBlock(singleBlocks[9].cacheKey, singleBlocks[9]);
537    // one eviction, one evicted.
538    assertEquals(11, cache.getStats().getEvictionCount());
539    assertEquals(11, cache.getStats().getEvictedCount());
540    // the single block just cached now evicted (can't evict memory)
541    assertEquals(null, cache.getBlock(singleBlocks[9].cacheKey, true, false, true));
542  }
543
544  // test scan resistance
545  @Test
546  public void testScanResistance() throws Exception {
547
548    long maxSize = 100000;
549    long blockSize = calculateBlockSize(maxSize, 10);
550
551    LruBlockCache cache =
552      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
553        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min
554        0.99f, // acceptable
555        0.33f, // single
556        0.33f, // multi
557        0.34f, // memory
558        1.2f, // limit
559        false, 16 * 1024 * 1024);
560
561    CachedItem[] singleBlocks = generateFixedBlocks(20, blockSize, "single");
562    CachedItem[] multiBlocks = generateFixedBlocks(5, blockSize, "multi");
563
564    // Add 5 multi blocks
565    for (CachedItem block : multiBlocks) {
566      cache.cacheBlock(block.cacheKey, block);
567      cache.getBlock(block.cacheKey, true, false, true);
568    }
569
570    // Add 5 single blocks
571    for (int i = 0; i < 5; i++) {
572      cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
573    }
574
575    // An eviction ran
576    assertEquals(1, cache.getStats().getEvictionCount());
577
578    // To drop down to 2/3 capacity, we'll need to evict 4 blocks
579    assertEquals(4, cache.getStats().getEvictedCount());
580
581    // Should have been taken off equally from single and multi
582    assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true));
583    assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true));
584    assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true));
585    assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true));
586
587    // Let's keep "scanning" by adding single blocks. From here on we only
588    // expect evictions from the single bucket.
589
590    // Every time we reach 10 total blocks (every 4 inserts) we get 4 single
591    // blocks evicted. Inserting 13 blocks should yield 3 more evictions and
592    // 12 more evicted.
593
594    for (int i = 5; i < 18; i++) {
595      cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
596    }
597
598    // 4 total evictions, 16 total evicted
599    assertEquals(4, cache.getStats().getEvictionCount());
600    assertEquals(16, cache.getStats().getEvictedCount());
601
602    // Should now have 7 total blocks
603    assertEquals(7, cache.getBlockCount());
604
605  }
606
607  @Test
608  public void testMaxBlockSize() throws Exception {
609    long maxSize = 100000;
610    long blockSize = calculateBlockSize(maxSize, 10);
611
612    LruBlockCache cache =
613      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
614        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min
615        0.99f, // acceptable
616        0.33f, // single
617        0.33f, // multi
618        0.34f, // memory
619        1.2f, // limit
620        false, 1024);
621    CachedItem[] tooLong = generateFixedBlocks(10, 1024 + 5, "long");
622    CachedItem[] small = generateFixedBlocks(15, 600, "small");
623
624    for (CachedItem i : tooLong) {
625      cache.cacheBlock(i.cacheKey, i);
626    }
627    for (CachedItem i : small) {
628      cache.cacheBlock(i.cacheKey, i);
629    }
630    assertEquals(15, cache.getBlockCount());
631    for (CachedItem i : small) {
632      assertNotNull(cache.getBlock(i.cacheKey, true, false, false));
633    }
634    for (CachedItem i : tooLong) {
635      assertNull(cache.getBlock(i.cacheKey, true, false, false));
636    }
637
638    assertEquals(10, cache.getStats().getFailedInserts());
639  }
640
641  // test setMaxSize
642  @Test
643  public void testResizeBlockCache() throws Exception {
644    long maxSize = 300000;
645    long blockSize = calculateBlockSize(maxSize, 31);
646
647    LruBlockCache cache =
648      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
649        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min
650        0.99f, // acceptable
651        0.33f, // single
652        0.33f, // multi
653        0.34f, // memory
654        1.2f, // limit
655        false, 16 * 1024 * 1024);
656
657    CachedItem[] singleBlocks = generateFixedBlocks(10, blockSize, "single");
658    CachedItem[] multiBlocks = generateFixedBlocks(10, blockSize, "multi");
659    CachedItem[] memoryBlocks = generateFixedBlocks(10, blockSize, "memory");
660
661    // Add all blocks from all priorities
662    for (int i = 0; i < 10; i++) {
663      // Just add single blocks
664      cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]);
665
666      // Add and get multi blocks
667      cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]);
668      cache.getBlock(multiBlocks[i].cacheKey, true, false, true);
669
670      // Add memory blocks as such
671      cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true);
672    }
673
674    // Do not expect any evictions yet
675    assertEquals(0, cache.getStats().getEvictionCount());
676
677    // Resize to half capacity plus an extra block (otherwise we evict an extra)
678    cache.setMaxSize((long) (maxSize * 0.5f));
679
680    // Should have run a single eviction
681    assertEquals(1, cache.getStats().getEvictionCount());
682
683    // And we expect 1/2 of the blocks to be evicted
684    assertEquals(15, cache.getStats().getEvictedCount());
685
686    // And the oldest 5 blocks from each category should be gone
687    for (int i = 0; i < 5; i++) {
688      assertEquals(null, cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
689      assertEquals(null, cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
690      assertEquals(null, cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
691    }
692
693    // And the newest 5 blocks should still be accessible
694    for (int i = 5; i < 10; i++) {
695      assertEquals(singleBlocks[i], cache.getBlock(singleBlocks[i].cacheKey, true, false, true));
696      assertEquals(multiBlocks[i], cache.getBlock(multiBlocks[i].cacheKey, true, false, true));
697      assertEquals(memoryBlocks[i], cache.getBlock(memoryBlocks[i].cacheKey, true, false, true));
698    }
699  }
700
701  // test metricsPastNPeriods
702  @Test
703  public void testPastNPeriodsMetrics() throws Exception {
704    double delta = 0.01;
705
706    // 3 total periods
707    CacheStats stats = new CacheStats("test", 3);
708
709    // No accesses, should be 0
710    stats.rollMetricsPeriod();
711    assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
712    assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
713
714    // period 1, 1 hit caching, 1 hit non-caching, 2 miss non-caching
715    // should be (2/4)=0.5 and (1/1)=1
716    stats.hit(false, true, BlockType.DATA);
717    stats.hit(true, true, BlockType.DATA);
718    stats.miss(false, false, BlockType.DATA);
719    stats.miss(false, false, BlockType.DATA);
720    stats.rollMetricsPeriod();
721    assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
722    assertEquals(1.0, stats.getHitCachingRatioPastNPeriods(), delta);
723
724    // period 2, 1 miss caching, 3 miss non-caching
725    // should be (2/8)=0.25 and (1/2)=0.5
726    stats.miss(true, false, BlockType.DATA);
727    stats.miss(false, false, BlockType.DATA);
728    stats.miss(false, false, BlockType.DATA);
729    stats.miss(false, false, BlockType.DATA);
730    stats.rollMetricsPeriod();
731    assertEquals(0.25, stats.getHitRatioPastNPeriods(), delta);
732    assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
733
734    // period 3, 2 hits of each type
735    // should be (6/12)=0.5 and (3/4)=0.75
736    stats.hit(false, true, BlockType.DATA);
737    stats.hit(true, true, BlockType.DATA);
738    stats.hit(false, true, BlockType.DATA);
739    stats.hit(true, true, BlockType.DATA);
740    stats.rollMetricsPeriod();
741    assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
742    assertEquals(0.75, stats.getHitCachingRatioPastNPeriods(), delta);
743
744    // period 4, evict period 1, two caching misses
745    // should be (4/10)=0.4 and (2/5)=0.4
746    stats.miss(true, false, BlockType.DATA);
747    stats.miss(true, false, BlockType.DATA);
748    stats.rollMetricsPeriod();
749    assertEquals(0.4, stats.getHitRatioPastNPeriods(), delta);
750    assertEquals(0.4, stats.getHitCachingRatioPastNPeriods(), delta);
751
752    // period 5, evict period 2, 2 caching misses, 2 non-caching hit
753    // should be (6/10)=0.6 and (2/6)=1/3
754    stats.miss(true, false, BlockType.DATA);
755    stats.miss(true, false, BlockType.DATA);
756    stats.hit(false, true, BlockType.DATA);
757    stats.hit(false, true, BlockType.DATA);
758    stats.rollMetricsPeriod();
759    assertEquals(0.6, stats.getHitRatioPastNPeriods(), delta);
760    assertEquals((double) 1 / 3, stats.getHitCachingRatioPastNPeriods(), delta);
761
762    // period 6, evict period 3
763    // should be (2/6)=1/3 and (0/4)=0
764    stats.rollMetricsPeriod();
765    assertEquals((double) 1 / 3, stats.getHitRatioPastNPeriods(), delta);
766    assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
767
768    // period 7, evict period 4
769    // should be (2/4)=0.5 and (0/2)=0
770    stats.rollMetricsPeriod();
771    assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
772    assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
773
774    // period 8, evict period 5
775    // should be 0 and 0
776    stats.rollMetricsPeriod();
777    assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta);
778    assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta);
779
780    // period 9, one of each
781    // should be (2/4)=0.5 and (1/2)=0.5
782    stats.miss(true, false, BlockType.DATA);
783    stats.miss(false, false, BlockType.DATA);
784    stats.hit(true, true, BlockType.DATA);
785    stats.hit(false, true, BlockType.DATA);
786    stats.rollMetricsPeriod();
787    assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta);
788    assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta);
789  }
790
791  @Test
792  public void testCacheBlockNextBlockMetadataMissing() {
793    long maxSize = 100000;
794    long blockSize = calculateBlockSize(maxSize, 10);
795    int size = 100;
796    int length = HConstants.HFILEBLOCK_HEADER_SIZE + size;
797    byte[] byteArr = new byte[length];
798    ByteBuffer buf = ByteBuffer.wrap(byteArr, 0, size);
799    HFileContext meta = new HFileContextBuilder().build();
800    HFileBlock blockWithNextBlockMetadata = new HFileBlock(BlockType.DATA, size, size, -1,
801      ByteBuff.wrap(buf), HFileBlock.FILL_HEADER, -1, 52, -1, meta, HEAP);
802    HFileBlock blockWithoutNextBlockMetadata = new HFileBlock(BlockType.DATA, size, size, -1,
803      ByteBuff.wrap(buf), HFileBlock.FILL_HEADER, -1, -1, -1, meta, HEAP);
804
805    LruBlockCache cache =
806      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
807        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min
808        0.99f, // acceptable
809        0.33f, // single
810        0.33f, // multi
811        0.34f, // memory
812        1.2f, // limit
813        false, 1024);
814
815    BlockCacheKey key = new BlockCacheKey("key1", 0);
816    ByteBuffer actualBuffer = ByteBuffer.allocate(length);
817    ByteBuffer block1Buffer = ByteBuffer.allocate(length);
818    ByteBuffer block2Buffer = ByteBuffer.allocate(length);
819    blockWithNextBlockMetadata.serialize(block1Buffer, true);
820    blockWithoutNextBlockMetadata.serialize(block2Buffer, true);
821
822    // Add blockWithNextBlockMetadata, expect blockWithNextBlockMetadata back.
823    CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithNextBlockMetadata, actualBuffer,
824      block1Buffer);
825
826    // Add blockWithoutNextBlockMetada, expect blockWithNextBlockMetadata back.
827    CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithoutNextBlockMetadata, actualBuffer,
828      block1Buffer);
829
830    // Clear and add blockWithoutNextBlockMetadata
831    cache.clearCache();
832    assertNull(cache.getBlock(key, false, false, false));
833    CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithoutNextBlockMetadata, actualBuffer,
834      block2Buffer);
835
836    // Add blockWithNextBlockMetadata, expect blockWithNextBlockMetadata to replace.
837    CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithNextBlockMetadata, actualBuffer,
838      block1Buffer);
839  }
840
841  private CachedItem[] generateFixedBlocks(int numBlocks, int size, String pfx) {
842    CachedItem[] blocks = new CachedItem[numBlocks];
843    for (int i = 0; i < numBlocks; i++) {
844      blocks[i] = new CachedItem(pfx + i, size);
845    }
846    return blocks;
847  }
848
849  private CachedItem[] generateFixedBlocks(int numBlocks, long size, String pfx) {
850    return generateFixedBlocks(numBlocks, (int) size, pfx);
851  }
852
853  private CachedItem[] generateRandomBlocks(int numBlocks, long maxSize) {
854    CachedItem[] blocks = new CachedItem[numBlocks];
855    Random rand = ThreadLocalRandom.current();
856    for (int i = 0; i < numBlocks; i++) {
857      blocks[i] = new CachedItem("block" + i, rand.nextInt((int) maxSize) + 1);
858    }
859    return blocks;
860  }
861
862  private long calculateBlockSize(long maxSize, int numBlocks) {
863    long roughBlockSize = maxSize / numBlocks;
864    int numEntries = (int) Math.ceil((1.2) * maxSize / roughBlockSize);
865    long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD + ClassSize.CONCURRENT_HASHMAP
866      + (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY)
867      + (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
868    long negateBlockSize = (long) (totalOverhead / numEntries);
869    negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
870    return ClassSize.align((long) Math.floor((roughBlockSize - negateBlockSize) * 0.99f));
871  }
872
873  private long calculateBlockSizeDefault(long maxSize, int numBlocks) {
874    long roughBlockSize = maxSize / numBlocks;
875    int numEntries = (int) Math.ceil((1.2) * maxSize / roughBlockSize);
876    long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD + ClassSize.CONCURRENT_HASHMAP
877      + (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY)
878      + (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
879    long negateBlockSize = totalOverhead / numEntries;
880    negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD;
881    return ClassSize.align((long) Math
882      .floor((roughBlockSize - negateBlockSize) * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR));
883  }
884
885  private static class CachedItem implements Cacheable {
886    BlockCacheKey cacheKey;
887    int size;
888
889    CachedItem(String blockName, int size, int offset) {
890      this.cacheKey = new BlockCacheKey(blockName, offset);
891      this.size = size;
892    }
893
894    CachedItem(String blockName, int size) {
895      this.cacheKey = new BlockCacheKey(blockName, 0);
896      this.size = size;
897    }
898
899    /** The size of this item reported to the block cache layer */
900    @Override
901    public long heapSize() {
902      return ClassSize.align(size);
903    }
904
905    /** Size of the cache block holding this item. Used for verification. */
906    public long cacheBlockHeapSize() {
907      return LruCachedBlock.PER_BLOCK_OVERHEAD + ClassSize.align(cacheKey.heapSize())
908        + ClassSize.align(size);
909    }
910
911    @Override
912    public int getSerializedLength() {
913      return 0;
914    }
915
916    @Override
917    public CacheableDeserializer<Cacheable> getDeserializer() {
918      return null;
919    }
920
921    @Override
922    public void serialize(ByteBuffer destination, boolean includeNextBlockMetadata) {
923    }
924
925    @Override
926    public BlockType getBlockType() {
927      return BlockType.DATA;
928    }
929  }
930
931  static void testMultiThreadGetAndEvictBlockInternal(BlockCache cache) throws Exception {
932    int size = 100;
933    int length = HConstants.HFILEBLOCK_HEADER_SIZE + size;
934    byte[] byteArr = new byte[length];
935    HFileContext meta = new HFileContextBuilder().build();
936    BlockCacheKey key = new BlockCacheKey("key1", 0);
937    HFileBlock blk = new HFileBlock(BlockType.DATA, size, size, -1,
938      ByteBuff.wrap(ByteBuffer.wrap(byteArr, 0, size)), HFileBlock.FILL_HEADER, -1, 52, -1, meta,
939      HEAP);
940    AtomicBoolean err1 = new AtomicBoolean(false);
941    Thread t1 = new Thread(() -> {
942      for (int i = 0; i < 10000 && !err1.get(); i++) {
943        try {
944          cache.getBlock(key, false, false, true);
945        } catch (Exception e) {
946          err1.set(true);
947          LOG.info("Cache block or get block failure: ", e);
948        }
949      }
950    });
951
952    AtomicBoolean err2 = new AtomicBoolean(false);
953    Thread t2 = new Thread(() -> {
954      for (int i = 0; i < 10000 && !err2.get(); i++) {
955        try {
956          cache.evictBlock(key);
957        } catch (Exception e) {
958          err2.set(true);
959          LOG.info("Evict block failure: ", e);
960        }
961      }
962    });
963
964    AtomicBoolean err3 = new AtomicBoolean(false);
965    Thread t3 = new Thread(() -> {
966      for (int i = 0; i < 10000 && !err3.get(); i++) {
967        try {
968          cache.cacheBlock(key, blk);
969        } catch (Exception e) {
970          err3.set(true);
971          LOG.info("Cache block failure: ", e);
972        }
973      }
974    });
975    t1.start();
976    t2.start();
977    t3.start();
978    t1.join();
979    t2.join();
980    t3.join();
981    Assert.assertFalse(err1.get());
982    Assert.assertFalse(err2.get());
983    Assert.assertFalse(err3.get());
984  }
985
986  @Test
987  public void testMultiThreadGetAndEvictBlock() throws Exception {
988    long maxSize = 100000;
989    long blockSize = calculateBlockSize(maxSize, 10);
990    LruBlockCache cache =
991      new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize),
992        LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min
993        0.99f, // acceptable
994        0.33f, // single
995        0.33f, // multi
996        0.34f, // memory
997        1.2f, // limit
998        false, 1024);
999    testMultiThreadGetAndEvictBlockInternal(cache);
1000  }
1001}