View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.io.hfile;
20  
21  import java.lang.ref.WeakReference;
22  import java.nio.ByteBuffer;
23  import java.util.EnumMap;
24  import java.util.Iterator;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.PriorityQueue;
28  import java.util.SortedSet;
29  import java.util.TreeSet;
30  import java.util.concurrent.ConcurrentHashMap;
31  import java.util.concurrent.Executors;
32  import java.util.concurrent.ScheduledExecutorService;
33  import java.util.concurrent.TimeUnit;
34  import java.util.concurrent.atomic.AtomicLong;
35  import java.util.concurrent.locks.ReentrantLock;
36  
37  import com.google.common.base.Objects;
38  import org.apache.commons.logging.Log;
39  import org.apache.commons.logging.LogFactory;
40  import org.apache.hadoop.hbase.classification.InterfaceAudience;
41  import org.apache.hadoop.conf.Configuration;
42  import org.apache.hadoop.hbase.HColumnDescriptor;
43  import org.apache.hadoop.hbase.io.HeapSize;
44  import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding;
45  import org.apache.hadoop.hbase.io.hfile.bucket.BucketCache;
46  import org.apache.hadoop.hbase.util.Bytes;
47  import org.apache.hadoop.hbase.util.ClassSize;
48  import org.apache.hadoop.hbase.util.HasThread;
49  import org.apache.hadoop.util.StringUtils;
50  import org.codehaus.jackson.annotate.JsonIgnoreProperties;
51  
52  import com.google.common.annotations.VisibleForTesting;
53  import com.google.common.util.concurrent.ThreadFactoryBuilder;
54  
55  /**
56   * A block cache implementation that is memory-aware using {@link HeapSize},
57   * memory-bound using an LRU eviction algorithm, and concurrent: backed by a
58   * {@link ConcurrentHashMap} and with a non-blocking eviction thread giving
59   * constant-time {@link #cacheBlock} and {@link #getBlock} operations.<p>
60   *
61   * Contains three levels of block priority to allow for
62   * scan-resistance and in-memory families {@link HColumnDescriptor#setInMemory(boolean)} (An
63   * in-memory column family is a column family that should be served from memory if possible):
64   * single-access, multiple-accesses, and in-memory priority.
65   * A block is added with an in-memory priority flag if
66   * {@link HColumnDescriptor#isInMemory()}, otherwise a block becomes a single access
67   * priority the first time it is read into this block cache.  If a block is accessed again while
68   * in cache, it is marked as a multiple access priority block.  This delineation of blocks is used
69   * to prevent scans from thrashing the cache adding a least-frequently-used
70   * element to the eviction algorithm.<p>
71   *
72   * Each priority is given its own chunk of the total cache to ensure
73   * fairness during eviction.  Each priority will retain close to its maximum
74   * size, however, if any priority is not using its entire chunk the others
75   * are able to grow beyond their chunk size.<p>
76   *
77   * Instantiated at a minimum with the total size and average block size.
78   * All sizes are in bytes.  The block size is not especially important as this
79   * cache is fully dynamic in its sizing of blocks.  It is only used for
80   * pre-allocating data structures and in initial heap estimation of the map.<p>
81   *
82   * The detailed constructor defines the sizes for the three priorities (they
83   * should total to the <code>maximum size</code> defined).  It also sets the levels that
84   * trigger and control the eviction thread.<p>
85   *
86   * The <code>acceptable size</code> is the cache size level which triggers the eviction
87   * process to start.  It evicts enough blocks to get the size below the
88   * minimum size specified.<p>
89   *
90   * Eviction happens in a separate thread and involves a single full-scan
91   * of the map.  It determines how many bytes must be freed to reach the minimum
92   * size, and then while scanning determines the fewest least-recently-used
93   * blocks necessary from each of the three priorities (would be 3 times bytes
94   * to free).  It then uses the priority chunk sizes to evict fairly according
95   * to the relative sizes and usage.
96   */
97  @InterfaceAudience.Private
98  @JsonIgnoreProperties({"encodingCountsForTest"})
99  public class LruBlockCache implements ResizableBlockCache, HeapSize {
100 
101   static final Log LOG = LogFactory.getLog(LruBlockCache.class);
102 
103   /**
104    * Percentage of total size that eviction will evict until; e.g. if set to .8, then we will keep
105    * evicting during an eviction run till the cache size is down to 80% of the total.
106    */
107   static final String LRU_MIN_FACTOR_CONFIG_NAME = "hbase.lru.blockcache.min.factor";
108 
109   /**
110    * Acceptable size of cache (no evictions if size < acceptable)
111    */
112   static final String LRU_ACCEPTABLE_FACTOR_CONFIG_NAME = "hbase.lru.blockcache.acceptable.factor";
113 
114   static final String LRU_SINGLE_PERCENTAGE_CONFIG_NAME = "hbase.lru.blockcache.single.percentage";
115   static final String LRU_MULTI_PERCENTAGE_CONFIG_NAME = "hbase.lru.blockcache.multi.percentage";
116   static final String LRU_MEMORY_PERCENTAGE_CONFIG_NAME = "hbase.lru.blockcache.memory.percentage";
117 
118   /**
119    * Configuration key to force data-block always (except in-memory are too much)
120    * cached in memory for in-memory hfile, unlike inMemory, which is a column-family
121    * configuration, inMemoryForceMode is a cluster-wide configuration
122    */
123   static final String LRU_IN_MEMORY_FORCE_MODE_CONFIG_NAME = "hbase.lru.rs.inmemoryforcemode";
124 
125   /** Default Configuration Parameters*/
126 
127   /** Backing Concurrent Map Configuration */
128   static final float DEFAULT_LOAD_FACTOR = 0.75f;
129   static final int DEFAULT_CONCURRENCY_LEVEL = 16;
130 
131   /** Eviction thresholds */
132   static final float DEFAULT_MIN_FACTOR = 0.95f;
133   static final float DEFAULT_ACCEPTABLE_FACTOR = 0.99f;
134 
135   /** Priority buckets */
136   static final float DEFAULT_SINGLE_FACTOR = 0.25f;
137   static final float DEFAULT_MULTI_FACTOR = 0.50f;
138   static final float DEFAULT_MEMORY_FACTOR = 0.25f;
139 
140   static final boolean DEFAULT_IN_MEMORY_FORCE_MODE = false;
141 
142   /** Statistics thread */
143   static final int statThreadPeriod = 60 * 5;
144 
145   /** Concurrent map (the cache) */
146   private final Map<BlockCacheKey,LruCachedBlock> map;
147 
148   /** Eviction lock (locked when eviction in process) */
149   private final ReentrantLock evictionLock = new ReentrantLock(true);
150 
151   /** Volatile boolean to track if we are in an eviction process or not */
152   private volatile boolean evictionInProgress = false;
153 
154   /** Eviction thread */
155   private final EvictionThread evictionThread;
156 
157   /** Statistics thread schedule pool (for heavy debugging, could remove) */
158   private final ScheduledExecutorService scheduleThreadPool = Executors.newScheduledThreadPool(1,
159     new ThreadFactoryBuilder().setNameFormat("LruBlockCacheStatsExecutor").setDaemon(true).build());
160 
161   /** Current size of cache */
162   private final AtomicLong size;
163 
164   /** Current number of cached elements */
165   private final AtomicLong elements;
166 
167   /** Cache access count (sequential ID) */
168   private final AtomicLong count;
169 
170   /** Cache statistics */
171   private final CacheStats stats;
172 
173   /** Maximum allowable size of cache (block put if size > max, evict) */
174   private long maxSize;
175 
176   /** Approximate block size */
177   private long blockSize;
178 
179   /** Acceptable size of cache (no evictions if size < acceptable) */
180   private float acceptableFactor;
181 
182   /** Minimum threshold of cache (when evicting, evict until size < min) */
183   private float minFactor;
184 
185   /** Single access bucket size */
186   private float singleFactor;
187 
188   /** Multiple access bucket size */
189   private float multiFactor;
190 
191   /** In-memory bucket size */
192   private float memoryFactor;
193 
194   /** Overhead of the structure itself */
195   private long overhead;
196 
197   /** Whether in-memory hfile's data block has higher priority when evicting */
198   private boolean forceInMemory;
199 
200   /** Where to send victims (blocks evicted/missing from the cache) */
201   // TODO: Fix it so this is not explicit reference to a particular BlockCache implementation.
202   private BucketCache victimHandler = null;
203 
204   /**
205    * Default constructor.  Specify maximum size and expected average block
206    * size (approximation is fine).
207    *
208    * <p>All other factors will be calculated based on defaults specified in
209    * this class.
210    * @param maxSize maximum size of cache, in bytes
211    * @param blockSize approximate size of each block, in bytes
212    */
213   public LruBlockCache(long maxSize, long blockSize) {
214     this(maxSize, blockSize, true);
215   }
216 
217   /**
218    * Constructor used for testing.  Allows disabling of the eviction thread.
219    */
220   public LruBlockCache(long maxSize, long blockSize, boolean evictionThread) {
221     this(maxSize, blockSize, evictionThread,
222         (int)Math.ceil(1.2*maxSize/blockSize),
223         DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL,
224         DEFAULT_MIN_FACTOR, DEFAULT_ACCEPTABLE_FACTOR,
225         DEFAULT_SINGLE_FACTOR,
226         DEFAULT_MULTI_FACTOR,
227         DEFAULT_MEMORY_FACTOR,
228         false
229         );
230   }
231 
232   public LruBlockCache(long maxSize, long blockSize, boolean evictionThread, Configuration conf) {
233     this(maxSize, blockSize, evictionThread,
234         (int)Math.ceil(1.2*maxSize/blockSize),
235         DEFAULT_LOAD_FACTOR,
236         DEFAULT_CONCURRENCY_LEVEL,
237         conf.getFloat(LRU_MIN_FACTOR_CONFIG_NAME, DEFAULT_MIN_FACTOR),
238         conf.getFloat(LRU_ACCEPTABLE_FACTOR_CONFIG_NAME, DEFAULT_ACCEPTABLE_FACTOR),
239         conf.getFloat(LRU_SINGLE_PERCENTAGE_CONFIG_NAME, DEFAULT_SINGLE_FACTOR),
240         conf.getFloat(LRU_MULTI_PERCENTAGE_CONFIG_NAME, DEFAULT_MULTI_FACTOR),
241         conf.getFloat(LRU_MEMORY_PERCENTAGE_CONFIG_NAME, DEFAULT_MEMORY_FACTOR),
242         conf.getBoolean(LRU_IN_MEMORY_FORCE_MODE_CONFIG_NAME, DEFAULT_IN_MEMORY_FORCE_MODE)
243         );
244   }
245 
246   public LruBlockCache(long maxSize, long blockSize, Configuration conf) {
247     this(maxSize, blockSize, true, conf);
248   }
249 
250   /**
251    * Configurable constructor.  Use this constructor if not using defaults.
252    * @param maxSize maximum size of this cache, in bytes
253    * @param blockSize expected average size of blocks, in bytes
254    * @param evictionThread whether to run evictions in a bg thread or not
255    * @param mapInitialSize initial size of backing ConcurrentHashMap
256    * @param mapLoadFactor initial load factor of backing ConcurrentHashMap
257    * @param mapConcurrencyLevel initial concurrency factor for backing CHM
258    * @param minFactor percentage of total size that eviction will evict until
259    * @param acceptableFactor percentage of total size that triggers eviction
260    * @param singleFactor percentage of total size for single-access blocks
261    * @param multiFactor percentage of total size for multiple-access blocks
262    * @param memoryFactor percentage of total size for in-memory blocks
263    */
264   public LruBlockCache(long maxSize, long blockSize, boolean evictionThread,
265       int mapInitialSize, float mapLoadFactor, int mapConcurrencyLevel,
266       float minFactor, float acceptableFactor, float singleFactor,
267       float multiFactor, float memoryFactor, boolean forceInMemory) {
268     if(singleFactor + multiFactor + memoryFactor != 1 ||
269         singleFactor < 0 || multiFactor < 0 || memoryFactor < 0) {
270       throw new IllegalArgumentException("Single, multi, and memory factors " +
271           " should be non-negative and total 1.0");
272     }
273     if(minFactor >= acceptableFactor) {
274       throw new IllegalArgumentException("minFactor must be smaller than acceptableFactor");
275     }
276     if(minFactor >= 1.0f || acceptableFactor >= 1.0f) {
277       throw new IllegalArgumentException("all factors must be < 1");
278     }
279     this.maxSize = maxSize;
280     this.blockSize = blockSize;
281     this.forceInMemory = forceInMemory;
282     map = new ConcurrentHashMap<BlockCacheKey,LruCachedBlock>(mapInitialSize,
283         mapLoadFactor, mapConcurrencyLevel);
284     this.minFactor = minFactor;
285     this.acceptableFactor = acceptableFactor;
286     this.singleFactor = singleFactor;
287     this.multiFactor = multiFactor;
288     this.memoryFactor = memoryFactor;
289     this.stats = new CacheStats(this.getClass().getSimpleName());
290     this.count = new AtomicLong(0);
291     this.elements = new AtomicLong(0);
292     this.overhead = calculateOverhead(maxSize, blockSize, mapConcurrencyLevel);
293     this.size = new AtomicLong(this.overhead);
294     if(evictionThread) {
295       this.evictionThread = new EvictionThread(this);
296       this.evictionThread.start(); // FindBugs SC_START_IN_CTOR
297     } else {
298       this.evictionThread = null;
299     }
300     // TODO: Add means of turning this off.  Bit obnoxious running thread just to make a log
301     // every five minutes.
302     this.scheduleThreadPool.scheduleAtFixedRate(new StatisticsThread(this),
303         statThreadPeriod, statThreadPeriod, TimeUnit.SECONDS);
304   }
305 
306   @Override
307   public void setMaxSize(long maxSize) {
308     this.maxSize = maxSize;
309     if(this.size.get() > acceptableSize() && !evictionInProgress) {
310       runEviction();
311     }
312   }
313 
314   // BlockCache implementation
315 
316   /**
317    * Cache the block with the specified name and buffer.
318    * <p>
319    * It is assumed this will NOT be called on an already cached block. In rare cases (HBASE-8547)
320    * this can happen, for which we compare the buffer contents.
321    * @param cacheKey block's cache key
322    * @param buf block buffer
323    * @param inMemory if block is in-memory
324    * @param cacheDataInL1
325    */
326   @Override
327   public void cacheBlock(BlockCacheKey cacheKey, Cacheable buf, boolean inMemory,
328       final boolean cacheDataInL1) {
329     LruCachedBlock cb = map.get(cacheKey);
330     if (cb != null) {
331       // compare the contents, if they are not equal, we are in big trouble
332       if (compare(buf, cb.getBuffer()) != 0) {
333         throw new RuntimeException("Cached block contents differ, which should not have happened."
334           + "cacheKey:" + cacheKey);
335       }
336       String msg = "Cached an already cached block: " + cacheKey + " cb:" + cb.getCacheKey();
337       msg += ". This is harmless and can happen in rare cases (see HBASE-8547)";
338       LOG.warn(msg);
339       return;
340     }
341     cb = new LruCachedBlock(cacheKey, buf, count.incrementAndGet(), inMemory);
342     long newSize = updateSizeMetrics(cb, false);
343     map.put(cacheKey, cb);
344     long val = elements.incrementAndGet();
345     if (LOG.isTraceEnabled()) {
346       long size = map.size();
347       assertCounterSanity(size, val);
348     }
349     if (newSize > acceptableSize() && !evictionInProgress) {
350       runEviction();
351     }
352   }
353 
354   /**
355    * Sanity-checking for parity between actual block cache content and metrics.
356    * Intended only for use with TRACE level logging and -ea JVM.
357    */
358   private static void assertCounterSanity(long mapSize, long counterVal) {
359     if (counterVal < 0) {
360       LOG.trace("counterVal overflow. Assertions unreliable. counterVal=" + counterVal +
361         ", mapSize=" + mapSize);
362       return;
363     }
364     if (mapSize < Integer.MAX_VALUE) {
365       double pct_diff = Math.abs((((double) counterVal) / ((double) mapSize)) - 1.);
366       if (pct_diff > 0.05) {
367         LOG.trace("delta between reported and actual size > 5%. counterVal=" + counterVal +
368           ", mapSize=" + mapSize);
369       }
370     }
371   }
372 
373   private int compare(Cacheable left, Cacheable right) {
374     ByteBuffer l = ByteBuffer.allocate(left.getSerializedLength());
375     left.serialize(l);
376     ByteBuffer r = ByteBuffer.allocate(right.getSerializedLength());
377     right.serialize(r);
378     return Bytes.compareTo(l.array(), l.arrayOffset(), l.limit(),
379       r.array(), r.arrayOffset(), r.limit());
380   }
381 
382   /**
383    * Cache the block with the specified name and buffer.
384    * <p>
385    * @param cacheKey block's cache key
386    * @param buf block buffer
387    */
388   public void cacheBlock(BlockCacheKey cacheKey, Cacheable buf) {
389     cacheBlock(cacheKey, buf, false, false);
390   }
391 
392   /**
393    * Helper function that updates the local size counter and also updates any
394    * per-cf or per-blocktype metrics it can discern from given
395    * {@link LruCachedBlock}
396    *
397    * @param cb
398    * @param evict
399    */
400   protected long updateSizeMetrics(LruCachedBlock cb, boolean evict) {
401     long heapsize = cb.heapSize();
402     if (evict) {
403       heapsize *= -1;
404     }
405     return size.addAndGet(heapsize);
406   }
407 
408   /**
409    * Get the buffer of the block with the specified name.
410    * @param cacheKey block's cache key
411    * @param caching true if the caller caches blocks on cache misses
412    * @param repeat Whether this is a repeat lookup for the same block
413    *        (used to avoid double counting cache misses when doing double-check locking)
414    * @param updateCacheMetrics Whether to update cache metrics or not
415    * @return buffer of specified cache key, or null if not in cache
416    */
417   @Override
418   public Cacheable getBlock(BlockCacheKey cacheKey, boolean caching, boolean repeat,
419       boolean updateCacheMetrics) {
420     LruCachedBlock cb = map.get(cacheKey);
421     if (cb == null) {
422       if (!repeat && updateCacheMetrics) stats.miss(caching);
423       if (victimHandler != null) {
424         return victimHandler.getBlock(cacheKey, caching, repeat, updateCacheMetrics);
425       }
426       return null;
427     }
428     if (updateCacheMetrics) stats.hit(caching);
429     cb.access(count.incrementAndGet());
430     return cb.getBuffer();
431   }
432 
433   /**
434    * Whether the cache contains block with specified cacheKey
435    * @param cacheKey
436    * @return true if contains the block
437    */
438   public boolean containsBlock(BlockCacheKey cacheKey) {
439     return map.containsKey(cacheKey);
440   }
441 
442   @Override
443   public boolean evictBlock(BlockCacheKey cacheKey) {
444     LruCachedBlock cb = map.get(cacheKey);
445     if (cb == null) return false;
446     evictBlock(cb, false);
447     return true;
448   }
449 
450   /**
451    * Evicts all blocks for a specific HFile. This is an
452    * expensive operation implemented as a linear-time search through all blocks
453    * in the cache. Ideally this should be a search in a log-access-time map.
454    *
455    * <p>
456    * This is used for evict-on-close to remove all blocks of a specific HFile.
457    *
458    * @return the number of blocks evicted
459    */
460   @Override
461   public int evictBlocksByHfileName(String hfileName) {
462     int numEvicted = 0;
463     for (BlockCacheKey key : map.keySet()) {
464       if (key.getHfileName().equals(hfileName)) {
465         if (evictBlock(key))
466           ++numEvicted;
467       }
468     }
469     if (victimHandler != null) {
470       numEvicted += victimHandler.evictBlocksByHfileName(hfileName);
471     }
472     return numEvicted;
473   }
474 
475   /**
476    * Evict the block, and it will be cached by the victim handler if exists &&
477    * block may be read again later
478    * @param block
479    * @param evictedByEvictionProcess true if the given block is evicted by
480    *          EvictionThread
481    * @return the heap size of evicted block
482    */
483   protected long evictBlock(LruCachedBlock block, boolean evictedByEvictionProcess) {
484     map.remove(block.getCacheKey());
485     updateSizeMetrics(block, true);
486     long val = elements.decrementAndGet();
487     if (LOG.isTraceEnabled()) {
488       long size = map.size();
489       assertCounterSanity(size, val);
490     }
491     stats.evicted(block.getCachedTime());
492     if (evictedByEvictionProcess && victimHandler != null) {
493       boolean wait = getCurrentSize() < acceptableSize();
494       boolean inMemory = block.getPriority() == BlockPriority.MEMORY;
495       victimHandler.cacheBlockWithWait(block.getCacheKey(), block.getBuffer(),
496           inMemory, wait);
497     }
498     return block.heapSize();
499   }
500 
501   /**
502    * Multi-threaded call to run the eviction process.
503    */
504   private void runEviction() {
505     if(evictionThread == null) {
506       evict();
507     } else {
508       evictionThread.evict();
509     }
510   }
511 
512   /**
513    * Eviction method.
514    */
515   void evict() {
516 
517     // Ensure only one eviction at a time
518     if(!evictionLock.tryLock()) return;
519 
520     try {
521       evictionInProgress = true;
522       long currentSize = this.size.get();
523       long bytesToFree = currentSize - minSize();
524 
525       if (LOG.isTraceEnabled()) {
526         LOG.trace("Block cache LRU eviction started; Attempting to free " +
527           StringUtils.byteDesc(bytesToFree) + " of total=" +
528           StringUtils.byteDesc(currentSize));
529       }
530 
531       if(bytesToFree <= 0) return;
532 
533       // Instantiate priority buckets
534       BlockBucket bucketSingle = new BlockBucket("single", bytesToFree, blockSize,
535           singleSize());
536       BlockBucket bucketMulti = new BlockBucket("multi", bytesToFree, blockSize,
537           multiSize());
538       BlockBucket bucketMemory = new BlockBucket("memory", bytesToFree, blockSize,
539           memorySize());
540 
541       // Scan entire map putting into appropriate buckets
542       for(LruCachedBlock cachedBlock : map.values()) {
543         switch(cachedBlock.getPriority()) {
544           case SINGLE: {
545             bucketSingle.add(cachedBlock);
546             break;
547           }
548           case MULTI: {
549             bucketMulti.add(cachedBlock);
550             break;
551           }
552           case MEMORY: {
553             bucketMemory.add(cachedBlock);
554             break;
555           }
556         }
557       }
558 
559       long bytesFreed = 0;
560       if (forceInMemory || memoryFactor > 0.999f) {
561         long s = bucketSingle.totalSize();
562         long m = bucketMulti.totalSize();
563         if (bytesToFree > (s + m)) {
564           // this means we need to evict blocks in memory bucket to make room,
565           // so the single and multi buckets will be emptied
566           bytesFreed = bucketSingle.free(s);
567           bytesFreed += bucketMulti.free(m);
568           if (LOG.isTraceEnabled()) {
569             LOG.trace("freed " + StringUtils.byteDesc(bytesFreed) +
570               " from single and multi buckets");
571           }
572           bytesFreed += bucketMemory.free(bytesToFree - bytesFreed);
573           if (LOG.isTraceEnabled()) {
574             LOG.trace("freed " + StringUtils.byteDesc(bytesFreed) +
575               " total from all three buckets ");
576           }
577         } else {
578           // this means no need to evict block in memory bucket,
579           // and we try best to make the ratio between single-bucket and
580           // multi-bucket is 1:2
581           long bytesRemain = s + m - bytesToFree;
582           if (3 * s <= bytesRemain) {
583             // single-bucket is small enough that no eviction happens for it
584             // hence all eviction goes from multi-bucket
585             bytesFreed = bucketMulti.free(bytesToFree);
586           } else if (3 * m <= 2 * bytesRemain) {
587             // multi-bucket is small enough that no eviction happens for it
588             // hence all eviction goes from single-bucket
589             bytesFreed = bucketSingle.free(bytesToFree);
590           } else {
591             // both buckets need to evict some blocks
592             bytesFreed = bucketSingle.free(s - bytesRemain / 3);
593             if (bytesFreed < bytesToFree) {
594               bytesFreed += bucketMulti.free(bytesToFree - bytesFreed);
595             }
596           }
597         }
598       } else {
599         PriorityQueue<BlockBucket> bucketQueue =
600           new PriorityQueue<BlockBucket>(3);
601 
602         bucketQueue.add(bucketSingle);
603         bucketQueue.add(bucketMulti);
604         bucketQueue.add(bucketMemory);
605 
606         int remainingBuckets = 3;
607 
608         BlockBucket bucket;
609         while((bucket = bucketQueue.poll()) != null) {
610           long overflow = bucket.overflow();
611           if(overflow > 0) {
612             long bucketBytesToFree = Math.min(overflow,
613                 (bytesToFree - bytesFreed) / remainingBuckets);
614             bytesFreed += bucket.free(bucketBytesToFree);
615           }
616           remainingBuckets--;
617         }
618       }
619 
620       if (LOG.isTraceEnabled()) {
621         long single = bucketSingle.totalSize();
622         long multi = bucketMulti.totalSize();
623         long memory = bucketMemory.totalSize();
624         LOG.trace("Block cache LRU eviction completed; " +
625           "freed=" + StringUtils.byteDesc(bytesFreed) + ", " +
626           "total=" + StringUtils.byteDesc(this.size.get()) + ", " +
627           "single=" + StringUtils.byteDesc(single) + ", " +
628           "multi=" + StringUtils.byteDesc(multi) + ", " +
629           "memory=" + StringUtils.byteDesc(memory));
630       }
631     } finally {
632       stats.evict();
633       evictionInProgress = false;
634       evictionLock.unlock();
635     }
636   }
637 
638   @Override
639   public String toString() {
640     return Objects.toStringHelper(this)
641       .add("blockCount", getBlockCount())
642       .add("currentSize", getCurrentSize())
643       .add("freeSize", getFreeSize())
644       .add("maxSize", getMaxSize())
645       .add("heapSize", heapSize())
646       .add("minSize", minSize())
647       .add("minFactor", minFactor)
648       .add("multiSize", multiSize())
649       .add("multiFactor", multiFactor)
650       .add("singleSize", singleSize())
651       .add("singleFactor", singleFactor)
652       .toString();
653   }
654 
655   /**
656    * Used to group blocks into priority buckets.  There will be a BlockBucket
657    * for each priority (single, multi, memory).  Once bucketed, the eviction
658    * algorithm takes the appropriate number of elements out of each according
659    * to configuration parameters and their relatives sizes.
660    */
661   private class BlockBucket implements Comparable<BlockBucket> {
662 
663     private final String name;
664     private LruCachedBlockQueue queue;
665     private long totalSize = 0;
666     private long bucketSize;
667 
668     public BlockBucket(String name, long bytesToFree, long blockSize, long bucketSize) {
669       this.name = name;
670       this.bucketSize = bucketSize;
671       queue = new LruCachedBlockQueue(bytesToFree, blockSize);
672       totalSize = 0;
673     }
674 
675     public void add(LruCachedBlock block) {
676       totalSize += block.heapSize();
677       queue.add(block);
678     }
679 
680     public long free(long toFree) {
681       if (LOG.isTraceEnabled()) {
682         LOG.trace("freeing " + StringUtils.byteDesc(toFree) + " from " + this);
683       }
684       LruCachedBlock cb;
685       long freedBytes = 0;
686       while ((cb = queue.pollLast()) != null) {
687         freedBytes += evictBlock(cb, true);
688         if (freedBytes >= toFree) {
689           return freedBytes;
690         }
691       }
692       if (LOG.isTraceEnabled()) {
693         LOG.trace("freed " + StringUtils.byteDesc(freedBytes) + " from " + this);
694       }
695       return freedBytes;
696     }
697 
698     public long overflow() {
699       return totalSize - bucketSize;
700     }
701 
702     public long totalSize() {
703       return totalSize;
704     }
705 
706     public int compareTo(BlockBucket that) {
707       if(this.overflow() == that.overflow()) return 0;
708       return this.overflow() > that.overflow() ? 1 : -1;
709     }
710 
711     @Override
712     public boolean equals(Object that) {
713       if (that == null || !(that instanceof BlockBucket)){
714         return false;
715       }
716       return compareTo((BlockBucket)that) == 0;
717     }
718 
719     @Override
720     public int hashCode() {
721       return Objects.hashCode(name, bucketSize, queue, totalSize);
722     }
723 
724     @Override
725     public String toString() {
726       return Objects.toStringHelper(this)
727         .add("name", name)
728         .add("totalSize", StringUtils.byteDesc(totalSize))
729         .add("bucketSize", StringUtils.byteDesc(bucketSize))
730         .toString();
731     }
732   }
733 
734   /**
735    * Get the maximum size of this cache.
736    * @return max size in bytes
737    */
738   public long getMaxSize() {
739     return this.maxSize;
740   }
741 
742   @Override
743   public long getCurrentSize() {
744     return this.size.get();
745   }
746 
747   @Override
748   public long getFreeSize() {
749     return getMaxSize() - getCurrentSize();
750   }
751 
752   @Override
753   public long size() {
754     return getMaxSize();
755   }
756 
757   @Override
758   public long getBlockCount() {
759     return this.elements.get();
760   }
761 
762   EvictionThread getEvictionThread() {
763     return this.evictionThread;
764   }
765 
766   /*
767    * Eviction thread.  Sits in waiting state until an eviction is triggered
768    * when the cache size grows above the acceptable level.<p>
769    *
770    * Thread is triggered into action by {@link LruBlockCache#runEviction()}
771    */
772   static class EvictionThread extends HasThread {
773     private WeakReference<LruBlockCache> cache;
774     private volatile boolean go = true;
775     // flag set after enter the run method, used for test
776     private boolean enteringRun = false;
777 
778     public EvictionThread(LruBlockCache cache) {
779       super(Thread.currentThread().getName() + ".LruBlockCache.EvictionThread");
780       setDaemon(true);
781       this.cache = new WeakReference<LruBlockCache>(cache);
782     }
783 
784     @Override
785     public void run() {
786       enteringRun = true;
787       while (this.go) {
788         synchronized(this) {
789           try {
790             this.wait(1000 * 10/*Don't wait for ever*/);
791           } catch(InterruptedException e) {}
792         }
793         LruBlockCache cache = this.cache.get();
794         if (cache == null) break;
795         cache.evict();
796       }
797     }
798 
799     @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="NN_NAKED_NOTIFY",
800         justification="This is what we want")
801     public void evict() {
802       synchronized(this) {
803         this.notifyAll();
804       }
805     }
806 
807     synchronized void shutdown() {
808       this.go = false;
809       this.notifyAll();
810     }
811 
812     /**
813      * Used for the test.
814      */
815     boolean isEnteringRun() {
816       return this.enteringRun;
817     }
818   }
819 
820   /*
821    * Statistics thread.  Periodically prints the cache statistics to the log.
822    */
823   static class StatisticsThread extends Thread {
824     private final LruBlockCache lru;
825 
826     public StatisticsThread(LruBlockCache lru) {
827       super("LruBlockCacheStats");
828       setDaemon(true);
829       this.lru = lru;
830     }
831 
832     @Override
833     public void run() {
834       lru.logStats();
835     }
836   }
837 
838   public void logStats() {
839     // Log size
840     long totalSize = heapSize();
841     long freeSize = maxSize - totalSize;
842     LruBlockCache.LOG.info("totalSize=" + StringUtils.byteDesc(totalSize) + ", " +
843         "freeSize=" + StringUtils.byteDesc(freeSize) + ", " +
844         "max=" + StringUtils.byteDesc(this.maxSize) + ", " +
845         "blockCount=" + getBlockCount() + ", " +
846         "accesses=" + stats.getRequestCount() + ", " +
847         "hits=" + stats.getHitCount() + ", " +
848         "hitRatio=" + (stats.getHitCount() == 0 ?
849           "0" : (StringUtils.formatPercent(stats.getHitRatio(), 2)+ ", ")) + ", " +
850         "cachingAccesses=" + stats.getRequestCachingCount() + ", " +
851         "cachingHits=" + stats.getHitCachingCount() + ", " +
852         "cachingHitsRatio=" + (stats.getHitCachingCount() == 0 ?
853           "0,": (StringUtils.formatPercent(stats.getHitCachingRatio(), 2) + ", ")) +
854         "evictions=" + stats.getEvictionCount() + ", " +
855         "evicted=" + stats.getEvictedCount() + ", " +
856         "evictedPerRun=" + stats.evictedPerEviction());
857   }
858 
859   /**
860    * Get counter statistics for this cache.
861    *
862    * <p>Includes: total accesses, hits, misses, evicted blocks, and runs
863    * of the eviction processes.
864    */
865   public CacheStats getStats() {
866     return this.stats;
867   }
868 
869   public final static long CACHE_FIXED_OVERHEAD = ClassSize.align(
870       (3 * Bytes.SIZEOF_LONG) + (9 * ClassSize.REFERENCE) +
871       (5 * Bytes.SIZEOF_FLOAT) + Bytes.SIZEOF_BOOLEAN
872       + ClassSize.OBJECT);
873 
874   @Override
875   public long heapSize() {
876     return getCurrentSize();
877   }
878 
879   public static long calculateOverhead(long maxSize, long blockSize, int concurrency){
880     // FindBugs ICAST_INTEGER_MULTIPLY_CAST_TO_LONG
881     return CACHE_FIXED_OVERHEAD + ClassSize.CONCURRENT_HASHMAP +
882         ((long)Math.ceil(maxSize*1.2/blockSize)
883             * ClassSize.CONCURRENT_HASHMAP_ENTRY) +
884         ((long)concurrency * ClassSize.CONCURRENT_HASHMAP_SEGMENT);
885   }
886 
887   @Override
888   public Iterator<CachedBlock> iterator() {
889     final Iterator<LruCachedBlock> iterator = map.values().iterator();
890 
891     return new Iterator<CachedBlock>() {
892       private final long now = System.nanoTime();
893 
894       @Override
895       public boolean hasNext() {
896         return iterator.hasNext();
897       }
898 
899       @Override
900       public CachedBlock next() {
901         final LruCachedBlock b = iterator.next();
902         return new CachedBlock() {
903           @Override
904           public String toString() {
905             return BlockCacheUtil.toString(this, now);
906           }
907 
908           @Override
909           public BlockPriority getBlockPriority() {
910             return b.getPriority();
911           }
912 
913           @Override
914           public BlockType getBlockType() {
915             return b.getBuffer().getBlockType();
916           }
917 
918           @Override
919           public long getOffset() {
920             return b.getCacheKey().getOffset();
921           }
922 
923           @Override
924           public long getSize() {
925             return b.getBuffer().heapSize();
926           }
927 
928           @Override
929           public long getCachedTime() {
930             return b.getCachedTime();
931           }
932 
933           @Override
934           public String getFilename() {
935             return b.getCacheKey().getHfileName();
936           }
937 
938           @Override
939           public int compareTo(CachedBlock other) {
940             int diff = this.getFilename().compareTo(other.getFilename());
941             if (diff != 0) return diff;
942             diff = (int)(this.getOffset() - other.getOffset());
943             if (diff != 0) return diff;
944             if (other.getCachedTime() < 0 || this.getCachedTime() < 0) {
945               throw new IllegalStateException("" + this.getCachedTime() + ", " +
946                 other.getCachedTime());
947             }
948             return (int)(other.getCachedTime() - this.getCachedTime());
949           }
950 
951           @Override
952           public int hashCode() {
953             return b.hashCode();
954           }
955 
956           @Override
957           public boolean equals(Object obj) {
958             if (obj instanceof CachedBlock) {
959               CachedBlock cb = (CachedBlock)obj;
960               return compareTo(cb) == 0;
961             } else {
962               return false;
963             }
964           }
965         };
966       }
967 
968       @Override
969       public void remove() {
970         throw new UnsupportedOperationException();
971       }
972     };
973   }
974 
975   // Simple calculators of sizes given factors and maxSize
976 
977   long acceptableSize() {
978     return (long)Math.floor(this.maxSize * this.acceptableFactor);
979   }
980   private long minSize() {
981     return (long)Math.floor(this.maxSize * this.minFactor);
982   }
983   private long singleSize() {
984     return (long)Math.floor(this.maxSize * this.singleFactor * this.minFactor);
985   }
986   private long multiSize() {
987     return (long)Math.floor(this.maxSize * this.multiFactor * this.minFactor);
988   }
989   private long memorySize() {
990     return (long)Math.floor(this.maxSize * this.memoryFactor * this.minFactor);
991   }
992 
993   public void shutdown() {
994     if (victimHandler != null)
995       victimHandler.shutdown();
996     this.scheduleThreadPool.shutdown();
997     for (int i = 0; i < 10; i++) {
998       if (!this.scheduleThreadPool.isShutdown()) {
999         try {
1000           Thread.sleep(10);
1001         } catch (InterruptedException e) {
1002           LOG.warn("Interrupted while sleeping");
1003           Thread.currentThread().interrupt();
1004           break;
1005         }
1006       }
1007     }
1008 
1009     if (!this.scheduleThreadPool.isShutdown()) {
1010       List<Runnable> runnables = this.scheduleThreadPool.shutdownNow();
1011       LOG.debug("Still running " + runnables);
1012     }
1013     this.evictionThread.shutdown();
1014   }
1015 
1016   /** Clears the cache. Used in tests. */
1017   @VisibleForTesting
1018   public void clearCache() {
1019     this.map.clear();
1020     this.elements.set(0);
1021   }
1022 
1023   /**
1024    * Used in testing. May be very inefficient.
1025    * @return the set of cached file names
1026    */
1027   @VisibleForTesting
1028   SortedSet<String> getCachedFileNamesForTest() {
1029     SortedSet<String> fileNames = new TreeSet<String>();
1030     for (BlockCacheKey cacheKey : map.keySet()) {
1031       fileNames.add(cacheKey.getHfileName());
1032     }
1033     return fileNames;
1034   }
1035 
1036   @VisibleForTesting
1037   Map<BlockType, Integer> getBlockTypeCountsForTest() {
1038     Map<BlockType, Integer> counts =
1039         new EnumMap<BlockType, Integer>(BlockType.class);
1040     for (LruCachedBlock cb : map.values()) {
1041       BlockType blockType = ((Cacheable)cb.getBuffer()).getBlockType();
1042       Integer count = counts.get(blockType);
1043       counts.put(blockType, (count == null ? 0 : count) + 1);
1044     }
1045     return counts;
1046   }
1047 
1048   @VisibleForTesting
1049   public Map<DataBlockEncoding, Integer> getEncodingCountsForTest() {
1050     Map<DataBlockEncoding, Integer> counts =
1051         new EnumMap<DataBlockEncoding, Integer>(DataBlockEncoding.class);
1052     for (LruCachedBlock block : map.values()) {
1053       DataBlockEncoding encoding =
1054               ((HFileBlock) block.getBuffer()).getDataBlockEncoding();
1055       Integer count = counts.get(encoding);
1056       counts.put(encoding, (count == null ? 0 : count) + 1);
1057     }
1058     return counts;
1059   }
1060 
1061   public void setVictimCache(BucketCache handler) {
1062     assert victimHandler == null;
1063     victimHandler = handler;
1064   }
1065 
1066   @VisibleForTesting
1067   Map<BlockCacheKey, LruCachedBlock> getMapForTests() {
1068     return map;
1069   }
1070 
1071   BucketCache getVictimHandler() {
1072     return this.victimHandler;
1073   }
1074 
1075   @Override
1076   public BlockCache[] getBlockCaches() {
1077     return null;
1078   }
1079 }