| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.hadoop.hbase.io.hfile; |
| |
| import static org.apache.hadoop.hbase.io.ByteBuffAllocator.HEAP; |
| import static org.junit.Assert.assertEquals; |
| import static org.junit.Assert.assertNotNull; |
| import static org.junit.Assert.assertNull; |
| import static org.junit.Assert.assertTrue; |
| |
| import java.nio.ByteBuffer; |
| import java.util.Random; |
| import java.util.concurrent.ExecutorService; |
| import java.util.concurrent.Executors; |
| import java.util.concurrent.ThreadLocalRandom; |
| import java.util.concurrent.TimeUnit; |
| import java.util.concurrent.atomic.AtomicBoolean; |
| import java.util.concurrent.atomic.AtomicInteger; |
| import org.apache.hadoop.conf.Configuration; |
| import org.apache.hadoop.hbase.HBaseClassTestRule; |
| import org.apache.hadoop.hbase.HBaseConfiguration; |
| import org.apache.hadoop.hbase.HConstants; |
| import org.apache.hadoop.hbase.Waiter; |
| import org.apache.hadoop.hbase.Waiter.ExplainingPredicate; |
| import org.apache.hadoop.hbase.io.HeapSize; |
| import org.apache.hadoop.hbase.io.hfile.LruBlockCache.EvictionThread; |
| import org.apache.hadoop.hbase.nio.ByteBuff; |
| import org.apache.hadoop.hbase.testclassification.IOTests; |
| import org.apache.hadoop.hbase.testclassification.SmallTests; |
| import org.apache.hadoop.hbase.util.ClassSize; |
| import org.junit.Assert; |
| import org.junit.ClassRule; |
| import org.junit.Test; |
| import org.junit.experimental.categories.Category; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| /** |
| * Tests the concurrent LruBlockCache. |
| * <p> |
| * Tests will ensure it grows and shrinks in size properly, evictions run when they're supposed to |
| * and do what they should, and that cached blocks are accessible when expected to be. |
| */ |
| @Category({ IOTests.class, SmallTests.class }) |
| public class TestLruBlockCache { |
| |
| @ClassRule |
| public static final HBaseClassTestRule CLASS_RULE = |
| HBaseClassTestRule.forClass(TestLruBlockCache.class); |
| |
| private static final Logger LOG = LoggerFactory.getLogger(TestLruBlockCache.class); |
| |
| private static final Configuration CONF = HBaseConfiguration.create(); |
| |
| @Test |
| public void testCacheEvictionThreadSafe() throws Exception { |
| long maxSize = 100000; |
| int numBlocks = 9; |
| int testRuns = 10; |
| final long blockSize = calculateBlockSizeDefault(maxSize, numBlocks); |
| assertTrue("calculateBlockSize appears broken.", blockSize * numBlocks <= maxSize); |
| |
| final LruBlockCache cache = new LruBlockCache(maxSize, blockSize); |
| EvictionThread evictionThread = cache.getEvictionThread(); |
| assertTrue(evictionThread != null); |
| Waiter.waitFor(CONF, 10000, 100, () -> evictionThread.isEnteringRun()); |
| final String hfileName = "hfile"; |
| int threads = 10; |
| final int blocksPerThread = 5 * numBlocks; |
| for (int run = 0; run != testRuns; ++run) { |
| final AtomicInteger blockCount = new AtomicInteger(0); |
| ExecutorService service = Executors.newFixedThreadPool(threads); |
| for (int i = 0; i != threads; ++i) { |
| service.execute(new Runnable() { |
| @Override |
| public void run() { |
| for (int blockIndex = 0; blockIndex < blocksPerThread |
| || (!cache.isEvictionInProgress()); ++blockIndex) { |
| CachedItem block = |
| new CachedItem(hfileName, (int) blockSize, blockCount.getAndIncrement()); |
| boolean inMemory = Math.random() > 0.5; |
| cache.cacheBlock(block.cacheKey, block, inMemory); |
| } |
| cache.evictBlocksByHfileName(hfileName); |
| } |
| }); |
| } |
| service.shutdown(); |
| // The test may fail here if the evict thread frees the blocks too fast |
| service.awaitTermination(10, TimeUnit.MINUTES); |
| Waiter.waitFor(CONF, 10000, 100, new ExplainingPredicate<Exception>() { |
| @Override |
| public boolean evaluate() throws Exception { |
| return cache.getBlockCount() == 0; |
| } |
| |
| @Override |
| public String explainFailure() throws Exception { |
| return "Cache block count failed to return to 0"; |
| } |
| }); |
| assertEquals(0, cache.getBlockCount()); |
| assertEquals(cache.getOverhead(), cache.getCurrentSize()); |
| } |
| } |
| |
| @Test |
| public void testBackgroundEvictionThread() throws Exception { |
| long maxSize = 100000; |
| int numBlocks = 9; |
| long blockSize = calculateBlockSizeDefault(maxSize, numBlocks); |
| assertTrue("calculateBlockSize appears broken.", blockSize * numBlocks <= maxSize); |
| |
| LruBlockCache cache = new LruBlockCache(maxSize, blockSize); |
| EvictionThread evictionThread = cache.getEvictionThread(); |
| assertTrue(evictionThread != null); |
| |
| CachedItem[] blocks = generateFixedBlocks(numBlocks + 1, blockSize, "block"); |
| |
| // Make sure eviction thread has entered run method |
| Waiter.waitFor(CONF, 10000, 10, () -> evictionThread.isEnteringRun()); |
| |
| // Add all the blocks |
| for (CachedItem block : blocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| } |
| |
| // wait until at least one eviction has run |
| Waiter.waitFor(CONF, 30000, 200, new ExplainingPredicate<Exception>() { |
| |
| @Override |
| public boolean evaluate() throws Exception { |
| return cache.getStats().getEvictionCount() > 0; |
| } |
| |
| @Override |
| public String explainFailure() throws Exception { |
| return "Eviction never happened."; |
| } |
| }); |
| |
| // let cache stabilize |
| // On some systems, the cache will run multiple evictions before it attains |
| // steady-state. For instance, after populating the cache with 10 blocks, |
| // the first eviction evicts a single block and then a second eviction |
| // evicts another. I think this is due to the delta between minSize and |
| // acceptableSize, combined with variance between object overhead on |
| // different environments. |
| int n = 0; |
| for (long prevCnt = 0 /* < number of blocks added */, curCnt = cache.getBlockCount(); prevCnt |
| != curCnt; prevCnt = curCnt, curCnt = cache.getBlockCount()) { |
| Thread.sleep(200); |
| assertTrue("Cache never stabilized.", n++ < 100); |
| } |
| |
| long evictionCount = cache.getStats().getEvictionCount(); |
| assertTrue(evictionCount >= 1); |
| LOG.info("Background Evictions run: {}", evictionCount); |
| } |
| |
| @Test |
| public void testCacheSimple() throws Exception { |
| long maxSize = 1000000; |
| long blockSize = calculateBlockSizeDefault(maxSize, 101); |
| |
| LruBlockCache cache = new LruBlockCache(maxSize, blockSize); |
| |
| CachedItem[] blocks = generateRandomBlocks(100, blockSize); |
| |
| long expectedCacheSize = cache.heapSize(); |
| |
| // Confirm empty |
| for (CachedItem block : blocks) { |
| assertTrue(cache.getBlock(block.cacheKey, true, false, true) == null); |
| } |
| |
| // Add blocks |
| for (CachedItem block : blocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| expectedCacheSize += block.cacheBlockHeapSize(); |
| } |
| |
| // Verify correctly calculated cache heap size |
| assertEquals(expectedCacheSize, cache.heapSize()); |
| |
| // Check if all blocks are properly cached and retrieved |
| for (CachedItem block : blocks) { |
| HeapSize buf = cache.getBlock(block.cacheKey, true, false, true); |
| assertTrue(buf != null); |
| assertEquals(buf.heapSize(), block.heapSize()); |
| } |
| |
| // Re-add same blocks and ensure nothing has changed |
| long expectedBlockCount = cache.getBlockCount(); |
| for (CachedItem block : blocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| } |
| assertEquals("Cache should ignore cache requests for blocks already in cache", |
| expectedBlockCount, cache.getBlockCount()); |
| |
| // Verify correctly calculated cache heap size |
| assertEquals(expectedCacheSize, cache.heapSize()); |
| |
| // Check if all blocks are properly cached and retrieved |
| for (CachedItem block : blocks) { |
| HeapSize buf = cache.getBlock(block.cacheKey, true, false, true); |
| assertTrue(buf != null); |
| assertEquals(buf.heapSize(), block.heapSize()); |
| } |
| |
| // Expect no evictions |
| assertEquals(0, cache.getStats().getEvictionCount()); |
| Thread t = new LruBlockCache.StatisticsThread(cache); |
| t.start(); |
| t.join(); |
| } |
| |
| @Test |
| public void testCacheEvictionSimple() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSizeDefault(maxSize, 10); |
| |
| LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false); |
| |
| CachedItem[] blocks = generateFixedBlocks(10, blockSize, "block"); |
| |
| long expectedCacheSize = cache.heapSize(); |
| |
| // Add all the blocks |
| for (CachedItem block : blocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| expectedCacheSize += block.cacheBlockHeapSize(); |
| } |
| |
| // A single eviction run should have occurred |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| |
| // Our expected size overruns acceptable limit |
| assertTrue(expectedCacheSize > (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR)); |
| |
| // But the cache did not grow beyond max |
| assertTrue(cache.heapSize() < maxSize); |
| |
| // And is still below the acceptable limit |
| assertTrue(cache.heapSize() < (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR)); |
| |
| // All blocks except block 0 should be in the cache |
| assertTrue(cache.getBlock(blocks[0].cacheKey, true, false, true) == null); |
| for (int i = 1; i < blocks.length; i++) { |
| assertEquals(cache.getBlock(blocks[i].cacheKey, true, false, true), blocks[i]); |
| } |
| } |
| |
| @Test |
| public void testCacheEvictionTwoPriorities() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSizeDefault(maxSize, 10); |
| |
| LruBlockCache cache = new LruBlockCache(maxSize, blockSize, false); |
| |
| CachedItem[] singleBlocks = generateFixedBlocks(5, 10000, "single"); |
| CachedItem[] multiBlocks = generateFixedBlocks(5, 10000, "multi"); |
| |
| long expectedCacheSize = cache.heapSize(); |
| |
| // Add and get the multi blocks |
| for (CachedItem block : multiBlocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| expectedCacheSize += block.cacheBlockHeapSize(); |
| assertEquals(cache.getBlock(block.cacheKey, true, false, true), block); |
| } |
| |
| // Add the single blocks (no get) |
| for (CachedItem block : singleBlocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| expectedCacheSize += block.heapSize(); |
| } |
| |
| // A single eviction run should have occurred |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| |
| // We expect two entries evicted |
| assertEquals(2, cache.getStats().getEvictedCount()); |
| |
| // Our expected size overruns acceptable limit |
| assertTrue(expectedCacheSize > (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR)); |
| |
| // But the cache did not grow beyond max |
| assertTrue(cache.heapSize() <= maxSize); |
| |
| // And is now below the acceptable limit |
| assertTrue(cache.heapSize() <= (maxSize * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR)); |
| |
| // We expect fairness across the two priorities. |
| // This test makes multi go barely over its limit, in-memory |
| // empty, and the rest in single. Two single evictions and |
| // one multi eviction expected. |
| assertTrue(cache.getBlock(singleBlocks[0].cacheKey, true, false, true) == null); |
| assertTrue(cache.getBlock(multiBlocks[0].cacheKey, true, false, true) == null); |
| |
| // And all others to be cached |
| for (int i = 1; i < 4; i++) { |
| assertEquals(cache.getBlock(singleBlocks[i].cacheKey, true, false, true), singleBlocks[i]); |
| assertEquals(cache.getBlock(multiBlocks[i].cacheKey, true, false, true), multiBlocks[i]); |
| } |
| } |
| |
| @Test |
| public void testCacheEvictionThreePriorities() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 16 * 1024 * 1024); |
| |
| CachedItem[] singleBlocks = generateFixedBlocks(5, blockSize, "single"); |
| CachedItem[] multiBlocks = generateFixedBlocks(5, blockSize, "multi"); |
| CachedItem[] memoryBlocks = generateFixedBlocks(5, blockSize, "memory"); |
| |
| long expectedCacheSize = cache.heapSize(); |
| |
| // Add 3 blocks from each priority |
| for (int i = 0; i < 3; i++) { |
| |
| // Just add single blocks |
| cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]); |
| expectedCacheSize += singleBlocks[i].cacheBlockHeapSize(); |
| |
| // Add and get multi blocks |
| cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]); |
| expectedCacheSize += multiBlocks[i].cacheBlockHeapSize(); |
| cache.getBlock(multiBlocks[i].cacheKey, true, false, true); |
| |
| // Add memory blocks as such |
| cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true); |
| expectedCacheSize += memoryBlocks[i].cacheBlockHeapSize(); |
| |
| } |
| |
| // Do not expect any evictions yet |
| assertEquals(0, cache.getStats().getEvictionCount()); |
| |
| // Verify cache size |
| assertEquals(expectedCacheSize, cache.heapSize()); |
| |
| // Insert a single block, oldest single should be evicted |
| cache.cacheBlock(singleBlocks[3].cacheKey, singleBlocks[3]); |
| |
| // Single eviction, one thing evicted |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| assertEquals(1, cache.getStats().getEvictedCount()); |
| |
| // Verify oldest single block is the one evicted |
| assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true)); |
| |
| // Change the oldest remaining single block to a multi |
| cache.getBlock(singleBlocks[1].cacheKey, true, false, true); |
| |
| // Insert another single block |
| cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]); |
| |
| // Two evictions, two evicted. |
| assertEquals(2, cache.getStats().getEvictionCount()); |
| assertEquals(2, cache.getStats().getEvictedCount()); |
| |
| // Oldest multi block should be evicted now |
| assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true)); |
| |
| // Insert another memory block |
| cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true); |
| |
| // Three evictions, three evicted. |
| assertEquals(3, cache.getStats().getEvictionCount()); |
| assertEquals(3, cache.getStats().getEvictedCount()); |
| |
| // Oldest memory block should be evicted now |
| assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true)); |
| |
| // Add a block that is twice as big (should force two evictions) |
| CachedItem[] bigBlocks = generateFixedBlocks(3, blockSize * 3, "big"); |
| cache.cacheBlock(bigBlocks[0].cacheKey, bigBlocks[0]); |
| |
| // Four evictions, six evicted (inserted block 3X size, expect +3 evicted) |
| assertEquals(4, cache.getStats().getEvictionCount()); |
| assertEquals(6, cache.getStats().getEvictedCount()); |
| |
| // Expect three remaining singles to be evicted |
| assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true)); |
| |
| // Make the big block a multi block |
| cache.getBlock(bigBlocks[0].cacheKey, true, false, true); |
| |
| // Cache another single big block |
| cache.cacheBlock(bigBlocks[1].cacheKey, bigBlocks[1]); |
| |
| // Five evictions, nine evicted (3 new) |
| assertEquals(5, cache.getStats().getEvictionCount()); |
| assertEquals(9, cache.getStats().getEvictedCount()); |
| |
| // Expect three remaining multis to be evicted |
| assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true)); |
| |
| // Cache a big memory block |
| cache.cacheBlock(bigBlocks[2].cacheKey, bigBlocks[2], true); |
| |
| // Six evictions, twelve evicted (3 new) |
| assertEquals(6, cache.getStats().getEvictionCount()); |
| assertEquals(12, cache.getStats().getEvictedCount()); |
| |
| // Expect three remaining in-memory to be evicted |
| assertEquals(null, cache.getBlock(memoryBlocks[1].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(memoryBlocks[2].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(memoryBlocks[3].cacheKey, true, false, true)); |
| } |
| |
| @Test |
| public void testCacheEvictionInMemoryForceMode() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min |
| 0.99f, // acceptable |
| 0.2f, // single |
| 0.3f, // multi |
| 0.5f, // memory |
| 1.2f, // limit |
| true, 16 * 1024 * 1024); |
| |
| CachedItem[] singleBlocks = generateFixedBlocks(10, blockSize, "single"); |
| CachedItem[] multiBlocks = generateFixedBlocks(10, blockSize, "multi"); |
| CachedItem[] memoryBlocks = generateFixedBlocks(10, blockSize, "memory"); |
| |
| long expectedCacheSize = cache.heapSize(); |
| |
| // 0. Add 5 single blocks and 4 multi blocks to make cache full, si:mu:me = 5:4:0 |
| for (int i = 0; i < 4; i++) { |
| // Just add single blocks |
| cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]); |
| expectedCacheSize += singleBlocks[i].cacheBlockHeapSize(); |
| // Add and get multi blocks |
| cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]); |
| expectedCacheSize += multiBlocks[i].cacheBlockHeapSize(); |
| cache.getBlock(multiBlocks[i].cacheKey, true, false, true); |
| } |
| // 5th single block |
| cache.cacheBlock(singleBlocks[4].cacheKey, singleBlocks[4]); |
| expectedCacheSize += singleBlocks[4].cacheBlockHeapSize(); |
| // Do not expect any evictions yet |
| assertEquals(0, cache.getStats().getEvictionCount()); |
| // Verify cache size |
| assertEquals(expectedCacheSize, cache.heapSize()); |
| |
| // 1. Insert a memory block, oldest single should be evicted, si:mu:me = 4:4:1 |
| cache.cacheBlock(memoryBlocks[0].cacheKey, memoryBlocks[0], true); |
| // Single eviction, one block evicted |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| assertEquals(1, cache.getStats().getEvictedCount()); |
| // Verify oldest single block (index = 0) is the one evicted |
| assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true)); |
| |
| // 2. Insert another memory block, another single evicted, si:mu:me = 3:4:2 |
| cache.cacheBlock(memoryBlocks[1].cacheKey, memoryBlocks[1], true); |
| // Two evictions, two evicted. |
| assertEquals(2, cache.getStats().getEvictionCount()); |
| assertEquals(2, cache.getStats().getEvictedCount()); |
| // Current oldest single block (index = 1) should be evicted now |
| assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true)); |
| |
| // 3. Insert 4 memory blocks, 2 single and 2 multi evicted, si:mu:me = 1:2:6 |
| cache.cacheBlock(memoryBlocks[2].cacheKey, memoryBlocks[2], true); |
| cache.cacheBlock(memoryBlocks[3].cacheKey, memoryBlocks[3], true); |
| cache.cacheBlock(memoryBlocks[4].cacheKey, memoryBlocks[4], true); |
| cache.cacheBlock(memoryBlocks[5].cacheKey, memoryBlocks[5], true); |
| // Three evictions, three evicted. |
| assertEquals(6, cache.getStats().getEvictionCount()); |
| assertEquals(6, cache.getStats().getEvictedCount()); |
| // two oldest single blocks and two oldest multi blocks evicted |
| assertEquals(null, cache.getBlock(singleBlocks[2].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(singleBlocks[3].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true)); |
| |
| // 4. Insert 3 memory blocks, the remaining 1 single and 2 multi evicted |
| // si:mu:me = 0:0:9 |
| cache.cacheBlock(memoryBlocks[6].cacheKey, memoryBlocks[6], true); |
| cache.cacheBlock(memoryBlocks[7].cacheKey, memoryBlocks[7], true); |
| cache.cacheBlock(memoryBlocks[8].cacheKey, memoryBlocks[8], true); |
| // Three evictions, three evicted. |
| assertEquals(9, cache.getStats().getEvictionCount()); |
| assertEquals(9, cache.getStats().getEvictedCount()); |
| // one oldest single block and two oldest multi blocks evicted |
| assertEquals(null, cache.getBlock(singleBlocks[4].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[2].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[3].cacheKey, true, false, true)); |
| |
| // 5. Insert one memory block, the oldest memory evicted |
| // si:mu:me = 0:0:9 |
| cache.cacheBlock(memoryBlocks[9].cacheKey, memoryBlocks[9], true); |
| // one eviction, one evicted. |
| assertEquals(10, cache.getStats().getEvictionCount()); |
| assertEquals(10, cache.getStats().getEvictedCount()); |
| // oldest memory block evicted |
| assertEquals(null, cache.getBlock(memoryBlocks[0].cacheKey, true, false, true)); |
| |
| // 6. Insert one new single block, itself evicted immediately since |
| // all blocks in cache are memory-type which have higher priority |
| // si:mu:me = 0:0:9 (no change) |
| cache.cacheBlock(singleBlocks[9].cacheKey, singleBlocks[9]); |
| // one eviction, one evicted. |
| assertEquals(11, cache.getStats().getEvictionCount()); |
| assertEquals(11, cache.getStats().getEvictedCount()); |
| // the single block just cached now evicted (can't evict memory) |
| assertEquals(null, cache.getBlock(singleBlocks[9].cacheKey, true, false, true)); |
| } |
| |
| // test scan resistance |
| @Test |
| public void testScanResistance() throws Exception { |
| |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 16 * 1024 * 1024); |
| |
| CachedItem[] singleBlocks = generateFixedBlocks(20, blockSize, "single"); |
| CachedItem[] multiBlocks = generateFixedBlocks(5, blockSize, "multi"); |
| |
| // Add 5 multi blocks |
| for (CachedItem block : multiBlocks) { |
| cache.cacheBlock(block.cacheKey, block); |
| cache.getBlock(block.cacheKey, true, false, true); |
| } |
| |
| // Add 5 single blocks |
| for (int i = 0; i < 5; i++) { |
| cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]); |
| } |
| |
| // An eviction ran |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| |
| // To drop down to 2/3 capacity, we'll need to evict 4 blocks |
| assertEquals(4, cache.getStats().getEvictedCount()); |
| |
| // Should have been taken off equally from single and multi |
| assertEquals(null, cache.getBlock(singleBlocks[0].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(singleBlocks[1].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[0].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[1].cacheKey, true, false, true)); |
| |
| // Let's keep "scanning" by adding single blocks. From here on we only |
| // expect evictions from the single bucket. |
| |
| // Every time we reach 10 total blocks (every 4 inserts) we get 4 single |
| // blocks evicted. Inserting 13 blocks should yield 3 more evictions and |
| // 12 more evicted. |
| |
| for (int i = 5; i < 18; i++) { |
| cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]); |
| } |
| |
| // 4 total evictions, 16 total evicted |
| assertEquals(4, cache.getStats().getEvictionCount()); |
| assertEquals(16, cache.getStats().getEvictedCount()); |
| |
| // Should now have 7 total blocks |
| assertEquals(7, cache.getBlockCount()); |
| |
| } |
| |
| @Test |
| public void testMaxBlockSize() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 1024); |
| CachedItem[] tooLong = generateFixedBlocks(10, 1024 + 5, "long"); |
| CachedItem[] small = generateFixedBlocks(15, 600, "small"); |
| |
| for (CachedItem i : tooLong) { |
| cache.cacheBlock(i.cacheKey, i); |
| } |
| for (CachedItem i : small) { |
| cache.cacheBlock(i.cacheKey, i); |
| } |
| assertEquals(15, cache.getBlockCount()); |
| for (CachedItem i : small) { |
| assertNotNull(cache.getBlock(i.cacheKey, true, false, false)); |
| } |
| for (CachedItem i : tooLong) { |
| assertNull(cache.getBlock(i.cacheKey, true, false, false)); |
| } |
| |
| assertEquals(10, cache.getStats().getFailedInserts()); |
| } |
| |
| // test setMaxSize |
| @Test |
| public void testResizeBlockCache() throws Exception { |
| long maxSize = 300000; |
| long blockSize = calculateBlockSize(maxSize, 31); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.98f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 16 * 1024 * 1024); |
| |
| CachedItem[] singleBlocks = generateFixedBlocks(10, blockSize, "single"); |
| CachedItem[] multiBlocks = generateFixedBlocks(10, blockSize, "multi"); |
| CachedItem[] memoryBlocks = generateFixedBlocks(10, blockSize, "memory"); |
| |
| // Add all blocks from all priorities |
| for (int i = 0; i < 10; i++) { |
| // Just add single blocks |
| cache.cacheBlock(singleBlocks[i].cacheKey, singleBlocks[i]); |
| |
| // Add and get multi blocks |
| cache.cacheBlock(multiBlocks[i].cacheKey, multiBlocks[i]); |
| cache.getBlock(multiBlocks[i].cacheKey, true, false, true); |
| |
| // Add memory blocks as such |
| cache.cacheBlock(memoryBlocks[i].cacheKey, memoryBlocks[i], true); |
| } |
| |
| // Do not expect any evictions yet |
| assertEquals(0, cache.getStats().getEvictionCount()); |
| |
| // Resize to half capacity plus an extra block (otherwise we evict an extra) |
| cache.setMaxSize((long) (maxSize * 0.5f)); |
| |
| // Should have run a single eviction |
| assertEquals(1, cache.getStats().getEvictionCount()); |
| |
| // And we expect 1/2 of the blocks to be evicted |
| assertEquals(15, cache.getStats().getEvictedCount()); |
| |
| // And the oldest 5 blocks from each category should be gone |
| for (int i = 0; i < 5; i++) { |
| assertEquals(null, cache.getBlock(singleBlocks[i].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(multiBlocks[i].cacheKey, true, false, true)); |
| assertEquals(null, cache.getBlock(memoryBlocks[i].cacheKey, true, false, true)); |
| } |
| |
| // And the newest 5 blocks should still be accessible |
| for (int i = 5; i < 10; i++) { |
| assertEquals(singleBlocks[i], cache.getBlock(singleBlocks[i].cacheKey, true, false, true)); |
| assertEquals(multiBlocks[i], cache.getBlock(multiBlocks[i].cacheKey, true, false, true)); |
| assertEquals(memoryBlocks[i], cache.getBlock(memoryBlocks[i].cacheKey, true, false, true)); |
| } |
| } |
| |
| // test metricsPastNPeriods |
| @Test |
| public void testPastNPeriodsMetrics() throws Exception { |
| double delta = 0.01; |
| |
| // 3 total periods |
| CacheStats stats = new CacheStats("test", 3); |
| |
| // No accesses, should be 0 |
| stats.rollMetricsPeriod(); |
| assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 1, 1 hit caching, 1 hit non-caching, 2 miss non-caching |
| // should be (2/4)=0.5 and (1/1)=1 |
| stats.hit(false, true, BlockType.DATA); |
| stats.hit(true, true, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(1.0, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 2, 1 miss caching, 3 miss non-caching |
| // should be (2/8)=0.25 and (1/2)=0.5 |
| stats.miss(true, false, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.25, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 3, 2 hits of each type |
| // should be (6/12)=0.5 and (3/4)=0.75 |
| stats.hit(false, true, BlockType.DATA); |
| stats.hit(true, true, BlockType.DATA); |
| stats.hit(false, true, BlockType.DATA); |
| stats.hit(true, true, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.75, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 4, evict period 1, two caching misses |
| // should be (4/10)=0.4 and (2/5)=0.4 |
| stats.miss(true, false, BlockType.DATA); |
| stats.miss(true, false, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.4, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.4, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 5, evict period 2, 2 caching misses, 2 non-caching hit |
| // should be (6/10)=0.6 and (2/6)=1/3 |
| stats.miss(true, false, BlockType.DATA); |
| stats.miss(true, false, BlockType.DATA); |
| stats.hit(false, true, BlockType.DATA); |
| stats.hit(false, true, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.6, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals((double) 1 / 3, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 6, evict period 3 |
| // should be (2/6)=1/3 and (0/4)=0 |
| stats.rollMetricsPeriod(); |
| assertEquals((double) 1 / 3, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 7, evict period 4 |
| // should be (2/4)=0.5 and (0/2)=0 |
| stats.rollMetricsPeriod(); |
| assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 8, evict period 5 |
| // should be 0 and 0 |
| stats.rollMetricsPeriod(); |
| assertEquals(0.0, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.0, stats.getHitCachingRatioPastNPeriods(), delta); |
| |
| // period 9, one of each |
| // should be (2/4)=0.5 and (1/2)=0.5 |
| stats.miss(true, false, BlockType.DATA); |
| stats.miss(false, false, BlockType.DATA); |
| stats.hit(true, true, BlockType.DATA); |
| stats.hit(false, true, BlockType.DATA); |
| stats.rollMetricsPeriod(); |
| assertEquals(0.5, stats.getHitRatioPastNPeriods(), delta); |
| assertEquals(0.5, stats.getHitCachingRatioPastNPeriods(), delta); |
| } |
| |
| @Test |
| public void testCacheBlockNextBlockMetadataMissing() { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| int size = 100; |
| int length = HConstants.HFILEBLOCK_HEADER_SIZE + size; |
| byte[] byteArr = new byte[length]; |
| ByteBuffer buf = ByteBuffer.wrap(byteArr, 0, size); |
| HFileContext meta = new HFileContextBuilder().build(); |
| HFileBlock blockWithNextBlockMetadata = new HFileBlock(BlockType.DATA, size, size, -1, |
| ByteBuff.wrap(buf), HFileBlock.FILL_HEADER, -1, 52, -1, meta, HEAP); |
| HFileBlock blockWithoutNextBlockMetadata = new HFileBlock(BlockType.DATA, size, size, -1, |
| ByteBuff.wrap(buf), HFileBlock.FILL_HEADER, -1, -1, -1, meta, HEAP); |
| |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 1024); |
| |
| BlockCacheKey key = new BlockCacheKey("key1", 0); |
| ByteBuffer actualBuffer = ByteBuffer.allocate(length); |
| ByteBuffer block1Buffer = ByteBuffer.allocate(length); |
| ByteBuffer block2Buffer = ByteBuffer.allocate(length); |
| blockWithNextBlockMetadata.serialize(block1Buffer, true); |
| blockWithoutNextBlockMetadata.serialize(block2Buffer, true); |
| |
| // Add blockWithNextBlockMetadata, expect blockWithNextBlockMetadata back. |
| CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithNextBlockMetadata, actualBuffer, |
| block1Buffer); |
| |
| // Add blockWithoutNextBlockMetada, expect blockWithNextBlockMetadata back. |
| CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithoutNextBlockMetadata, actualBuffer, |
| block1Buffer); |
| |
| // Clear and add blockWithoutNextBlockMetadata |
| cache.clearCache(); |
| assertNull(cache.getBlock(key, false, false, false)); |
| CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithoutNextBlockMetadata, actualBuffer, |
| block2Buffer); |
| |
| // Add blockWithNextBlockMetadata, expect blockWithNextBlockMetadata to replace. |
| CacheTestUtils.getBlockAndAssertEquals(cache, key, blockWithNextBlockMetadata, actualBuffer, |
| block1Buffer); |
| } |
| |
| private CachedItem[] generateFixedBlocks(int numBlocks, int size, String pfx) { |
| CachedItem[] blocks = new CachedItem[numBlocks]; |
| for (int i = 0; i < numBlocks; i++) { |
| blocks[i] = new CachedItem(pfx + i, size); |
| } |
| return blocks; |
| } |
| |
| private CachedItem[] generateFixedBlocks(int numBlocks, long size, String pfx) { |
| return generateFixedBlocks(numBlocks, (int) size, pfx); |
| } |
| |
| private CachedItem[] generateRandomBlocks(int numBlocks, long maxSize) { |
| CachedItem[] blocks = new CachedItem[numBlocks]; |
| Random rand = ThreadLocalRandom.current(); |
| for (int i = 0; i < numBlocks; i++) { |
| blocks[i] = new CachedItem("block" + i, rand.nextInt((int) maxSize) + 1); |
| } |
| return blocks; |
| } |
| |
| private long calculateBlockSize(long maxSize, int numBlocks) { |
| long roughBlockSize = maxSize / numBlocks; |
| int numEntries = (int) Math.ceil((1.2) * maxSize / roughBlockSize); |
| long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD + ClassSize.CONCURRENT_HASHMAP |
| + (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) |
| + (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT); |
| long negateBlockSize = (long) (totalOverhead / numEntries); |
| negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD; |
| return ClassSize.align((long) Math.floor((roughBlockSize - negateBlockSize) * 0.99f)); |
| } |
| |
| private long calculateBlockSizeDefault(long maxSize, int numBlocks) { |
| long roughBlockSize = maxSize / numBlocks; |
| int numEntries = (int) Math.ceil((1.2) * maxSize / roughBlockSize); |
| long totalOverhead = LruBlockCache.CACHE_FIXED_OVERHEAD + ClassSize.CONCURRENT_HASHMAP |
| + (numEntries * ClassSize.CONCURRENT_HASHMAP_ENTRY) |
| + (LruBlockCache.DEFAULT_CONCURRENCY_LEVEL * ClassSize.CONCURRENT_HASHMAP_SEGMENT); |
| long negateBlockSize = totalOverhead / numEntries; |
| negateBlockSize += LruCachedBlock.PER_BLOCK_OVERHEAD; |
| return ClassSize.align((long) Math |
| .floor((roughBlockSize - negateBlockSize) * LruBlockCache.DEFAULT_ACCEPTABLE_FACTOR)); |
| } |
| |
| private static class CachedItem implements Cacheable { |
| BlockCacheKey cacheKey; |
| int size; |
| |
| CachedItem(String blockName, int size, int offset) { |
| this.cacheKey = new BlockCacheKey(blockName, offset); |
| this.size = size; |
| } |
| |
| CachedItem(String blockName, int size) { |
| this.cacheKey = new BlockCacheKey(blockName, 0); |
| this.size = size; |
| } |
| |
| /** The size of this item reported to the block cache layer */ |
| @Override |
| public long heapSize() { |
| return ClassSize.align(size); |
| } |
| |
| /** Size of the cache block holding this item. Used for verification. */ |
| public long cacheBlockHeapSize() { |
| return LruCachedBlock.PER_BLOCK_OVERHEAD + ClassSize.align(cacheKey.heapSize()) |
| + ClassSize.align(size); |
| } |
| |
| @Override |
| public int getSerializedLength() { |
| return 0; |
| } |
| |
| @Override |
| public CacheableDeserializer<Cacheable> getDeserializer() { |
| return null; |
| } |
| |
| @Override |
| public void serialize(ByteBuffer destination, boolean includeNextBlockMetadata) { |
| } |
| |
| @Override |
| public BlockType getBlockType() { |
| return BlockType.DATA; |
| } |
| } |
| |
| static void testMultiThreadGetAndEvictBlockInternal(BlockCache cache) throws Exception { |
| int size = 100; |
| int length = HConstants.HFILEBLOCK_HEADER_SIZE + size; |
| byte[] byteArr = new byte[length]; |
| HFileContext meta = new HFileContextBuilder().build(); |
| BlockCacheKey key = new BlockCacheKey("key1", 0); |
| HFileBlock blk = new HFileBlock(BlockType.DATA, size, size, -1, |
| ByteBuff.wrap(ByteBuffer.wrap(byteArr, 0, size)), HFileBlock.FILL_HEADER, -1, 52, -1, meta, |
| HEAP); |
| AtomicBoolean err1 = new AtomicBoolean(false); |
| Thread t1 = new Thread(() -> { |
| for (int i = 0; i < 10000 && !err1.get(); i++) { |
| try { |
| cache.getBlock(key, false, false, true); |
| } catch (Exception e) { |
| err1.set(true); |
| LOG.info("Cache block or get block failure: ", e); |
| } |
| } |
| }); |
| |
| AtomicBoolean err2 = new AtomicBoolean(false); |
| Thread t2 = new Thread(() -> { |
| for (int i = 0; i < 10000 && !err2.get(); i++) { |
| try { |
| cache.evictBlock(key); |
| } catch (Exception e) { |
| err2.set(true); |
| LOG.info("Evict block failure: ", e); |
| } |
| } |
| }); |
| |
| AtomicBoolean err3 = new AtomicBoolean(false); |
| Thread t3 = new Thread(() -> { |
| for (int i = 0; i < 10000 && !err3.get(); i++) { |
| try { |
| cache.cacheBlock(key, blk); |
| } catch (Exception e) { |
| err3.set(true); |
| LOG.info("Cache block failure: ", e); |
| } |
| } |
| }); |
| t1.start(); |
| t2.start(); |
| t3.start(); |
| t1.join(); |
| t2.join(); |
| t3.join(); |
| Assert.assertFalse(err1.get()); |
| Assert.assertFalse(err2.get()); |
| Assert.assertFalse(err3.get()); |
| } |
| |
| @Test |
| public void testMultiThreadGetAndEvictBlock() throws Exception { |
| long maxSize = 100000; |
| long blockSize = calculateBlockSize(maxSize, 10); |
| LruBlockCache cache = |
| new LruBlockCache(maxSize, blockSize, false, (int) Math.ceil(1.2 * maxSize / blockSize), |
| LruBlockCache.DEFAULT_LOAD_FACTOR, LruBlockCache.DEFAULT_CONCURRENCY_LEVEL, 0.66f, // min |
| 0.99f, // acceptable |
| 0.33f, // single |
| 0.33f, // multi |
| 0.34f, // memory |
| 1.2f, // limit |
| false, 1024); |
| testMultiThreadGetAndEvictBlockInternal(cache); |
| } |
| } |