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.bucket;
019
020import static org.apache.hadoop.hbase.io.hfile.BlockCacheFactory.BLOCKCACHE_STATS_PERIODS;
021import static org.apache.hadoop.hbase.io.hfile.BlockCacheFactory.BLOCKCACHE_STATS_PERIOD_MINUTES_KEY;
022import static org.apache.hadoop.hbase.io.hfile.BlockCacheFactory.DEFAULT_BLOCKCACHE_STATS_PERIODS;
023import static org.apache.hadoop.hbase.io.hfile.BlockCacheFactory.DEFAULT_BLOCKCACHE_STATS_PERIOD_MINUTES;
024import static org.apache.hadoop.hbase.io.hfile.CacheConfig.BUCKETCACHE_PERSIST_INTERVAL_KEY;
025
026import java.io.File;
027import java.io.FileInputStream;
028import java.io.FileOutputStream;
029import java.io.IOException;
030import java.nio.ByteBuffer;
031import java.util.ArrayList;
032import java.util.Arrays;
033import java.util.Collections;
034import java.util.Comparator;
035import java.util.HashSet;
036import java.util.Iterator;
037import java.util.List;
038import java.util.Map;
039import java.util.NavigableSet;
040import java.util.Optional;
041import java.util.PriorityQueue;
042import java.util.Set;
043import java.util.concurrent.ArrayBlockingQueue;
044import java.util.concurrent.BlockingQueue;
045import java.util.concurrent.ConcurrentHashMap;
046import java.util.concurrent.ConcurrentMap;
047import java.util.concurrent.ConcurrentSkipListSet;
048import java.util.concurrent.Executors;
049import java.util.concurrent.ScheduledExecutorService;
050import java.util.concurrent.TimeUnit;
051import java.util.concurrent.atomic.AtomicBoolean;
052import java.util.concurrent.atomic.AtomicLong;
053import java.util.concurrent.atomic.LongAdder;
054import java.util.concurrent.locks.Lock;
055import java.util.concurrent.locks.ReentrantLock;
056import java.util.concurrent.locks.ReentrantReadWriteLock;
057import java.util.function.Consumer;
058import java.util.function.Function;
059import org.apache.commons.io.IOUtils;
060import org.apache.hadoop.conf.Configuration;
061import org.apache.hadoop.fs.Path;
062import org.apache.hadoop.hbase.HBaseConfiguration;
063import org.apache.hadoop.hbase.HBaseIOException;
064import org.apache.hadoop.hbase.TableName;
065import org.apache.hadoop.hbase.client.Admin;
066import org.apache.hadoop.hbase.io.ByteBuffAllocator;
067import org.apache.hadoop.hbase.io.ByteBuffAllocator.Recycler;
068import org.apache.hadoop.hbase.io.HeapSize;
069import org.apache.hadoop.hbase.io.hfile.BlockCache;
070import org.apache.hadoop.hbase.io.hfile.BlockCacheKey;
071import org.apache.hadoop.hbase.io.hfile.BlockCacheUtil;
072import org.apache.hadoop.hbase.io.hfile.BlockPriority;
073import org.apache.hadoop.hbase.io.hfile.BlockType;
074import org.apache.hadoop.hbase.io.hfile.CacheConfig;
075import org.apache.hadoop.hbase.io.hfile.CacheStats;
076import org.apache.hadoop.hbase.io.hfile.Cacheable;
077import org.apache.hadoop.hbase.io.hfile.CachedBlock;
078import org.apache.hadoop.hbase.io.hfile.CombinedBlockCache;
079import org.apache.hadoop.hbase.io.hfile.HFileBlock;
080import org.apache.hadoop.hbase.io.hfile.HFileContext;
081import org.apache.hadoop.hbase.io.hfile.HFileInfo;
082import org.apache.hadoop.hbase.nio.ByteBuff;
083import org.apache.hadoop.hbase.nio.RefCnt;
084import org.apache.hadoop.hbase.protobuf.ProtobufMagic;
085import org.apache.hadoop.hbase.regionserver.DataTieringManager;
086import org.apache.hadoop.hbase.regionserver.HRegion;
087import org.apache.hadoop.hbase.regionserver.StoreFileInfo;
088import org.apache.hadoop.hbase.util.Bytes;
089import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
090import org.apache.hadoop.hbase.util.IdReadWriteLock;
091import org.apache.hadoop.hbase.util.IdReadWriteLockPoolJanitor;
092import org.apache.hadoop.hbase.util.IdReadWriteLockStrongRef;
093import org.apache.hadoop.hbase.util.IdReadWriteLockWithObjectPool;
094import org.apache.hadoop.hbase.util.IdReadWriteLockWithObjectPool.ReferenceType;
095import org.apache.hadoop.hbase.util.Pair;
096import org.apache.hadoop.hbase.util.Threads;
097import org.apache.hadoop.util.StringUtils;
098import org.apache.yetus.audience.InterfaceAudience;
099import org.slf4j.Logger;
100import org.slf4j.LoggerFactory;
101
102import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
103import org.apache.hbase.thirdparty.com.google.common.util.concurrent.ThreadFactoryBuilder;
104
105import org.apache.hadoop.hbase.shaded.protobuf.generated.BucketCacheProtos;
106
107/**
108 * BucketCache uses {@link BucketAllocator} to allocate/free blocks, and uses BucketCache#ramCache
109 * and BucketCache#backingMap in order to determine if a given element is in the cache. The bucket
110 * cache can use off-heap memory {@link ByteBufferIOEngine} or mmap
111 * {@link ExclusiveMemoryMmapIOEngine} or pmem {@link SharedMemoryMmapIOEngine} or local files
112 * {@link FileIOEngine} to store/read the block data.
113 * <p>
114 * Eviction is via a similar algorithm as used in
115 * {@link org.apache.hadoop.hbase.io.hfile.LruBlockCache}
116 * <p>
117 * BucketCache can be used as mainly a block cache (see
118 * {@link org.apache.hadoop.hbase.io.hfile.CombinedBlockCache}), combined with a BlockCache to
119 * decrease CMS GC and heap fragmentation.
120 * <p>
121 * It also can be used as a secondary cache (e.g. using a file on ssd/fusionio to store blocks) to
122 * enlarge cache space via a victim cache.
123 */
124@InterfaceAudience.Private
125public class BucketCache implements BlockCache, HeapSize {
126  private static final Logger LOG = LoggerFactory.getLogger(BucketCache.class);
127
128  /** Priority buckets config */
129  static final String SINGLE_FACTOR_CONFIG_NAME = "hbase.bucketcache.single.factor";
130  static final String MULTI_FACTOR_CONFIG_NAME = "hbase.bucketcache.multi.factor";
131  static final String MEMORY_FACTOR_CONFIG_NAME = "hbase.bucketcache.memory.factor";
132  static final String EXTRA_FREE_FACTOR_CONFIG_NAME = "hbase.bucketcache.extrafreefactor";
133  static final String ACCEPT_FACTOR_CONFIG_NAME = "hbase.bucketcache.acceptfactor";
134  static final String MIN_FACTOR_CONFIG_NAME = "hbase.bucketcache.minfactor";
135  static final String BACKING_MAP_PERSISTENCE_CHUNK_SIZE =
136    "hbase.bucketcache.persistence.chunksize";
137
138  /** Use strong reference for offsetLock or not */
139  private static final String STRONG_REF_KEY = "hbase.bucketcache.offsetlock.usestrongref";
140  private static final boolean STRONG_REF_DEFAULT = false;
141
142  /**
143   * Frequency in seconds to clean up the underlying IdReadWriteLock ObjectPool (default: 10s)
144   */
145  static final String LOCK_JANITOR_PERIOD_SECONDS_CONFIG_NAME =
146    "hbase.bucketcache.lock.janitor.period.seconds";
147  private static final int DEFAULT_LOCK_JANITOR_PERIOD_SECONDS = 10;
148
149  /** The cache age of blocks to check if the related file is present on any online regions. */
150  static final String BLOCK_ORPHAN_GRACE_PERIOD =
151    "hbase.bucketcache.block.orphan.evictgraceperiod.seconds";
152
153  static final long BLOCK_ORPHAN_GRACE_PERIOD_DEFAULT = 24 * 60 * 60 * 1000L;
154
155  /** Priority buckets */
156  static final float DEFAULT_SINGLE_FACTOR = 0.25f;
157  static final float DEFAULT_MULTI_FACTOR = 0.50f;
158  static final float DEFAULT_MEMORY_FACTOR = 0.25f;
159  static final float DEFAULT_MIN_FACTOR = 0.85f;
160
161  static final float DEFAULT_EXTRA_FREE_FACTOR = 0.10f;
162  static final float DEFAULT_ACCEPT_FACTOR = 0.95f;
163
164  // Number of blocks to clear for each of the bucket size that is full
165  static final int DEFAULT_FREE_ENTIRE_BLOCK_FACTOR = 2;
166
167  /** Statistics thread */
168  private static final int statThreadPeriod = 5 * 60;
169
170  final static int DEFAULT_WRITER_THREADS = 3;
171  final static int DEFAULT_WRITER_QUEUE_ITEMS = 64;
172
173  final static long DEFAULT_BACKING_MAP_PERSISTENCE_CHUNK_SIZE = 10000;
174
175  // Store/read block data
176  transient final IOEngine ioEngine;
177
178  // Store the block in this map before writing it to cache
179  transient final RAMCache ramCache;
180
181  // In this map, store the block's meta data like offset, length
182  transient Map<BlockCacheKey, BucketEntry> backingMap;
183
184  private AtomicBoolean backingMapValidated = new AtomicBoolean(false);
185
186  /**
187   * Map of hFile -> Region -> File size. This map is used to track all files completed prefetch,
188   * together with the region those belong to and the total cached size for the
189   * region.TestBlockEvictionOnRegionMovement
190   */
191  transient final Map<String, Pair<String, Long>> fullyCachedFiles = new ConcurrentHashMap<>();
192  /**
193   * Map of region -> total size of the region prefetched on this region server. This is the total
194   * size of hFiles for this region prefetched on this region server
195   */
196  final Map<String, Long> regionCachedSize = new ConcurrentHashMap<>();
197
198  private transient BucketCachePersister cachePersister;
199
200  /**
201   * Enum to represent the state of cache
202   */
203  protected enum CacheState {
204    // Initializing: State when the cache is being initialised from persistence.
205    INITIALIZING,
206    // Enabled: State when cache is initialised and is ready.
207    ENABLED,
208    // Disabled: State when the cache is disabled.
209    DISABLED
210  }
211
212  /**
213   * Flag if the cache is enabled or not... We shut it off if there are IO errors for some time, so
214   * that Bucket IO exceptions/errors don't bring down the HBase server.
215   */
216  private volatile CacheState cacheState;
217
218  /** The single cleanup thread shared by disable and explicit shutdown calls. */
219  private volatile Thread cacheCleanupThread;
220
221  /** The thread restoring the persistent cache index during initialization. */
222  private volatile Thread persistenceRetrieverThread;
223
224  /**
225   * A list of writer queues. We have a queue per {@link WriterThread} we have running. In other
226   * words, the work adding blocks to the BucketCache is divided up amongst the running
227   * WriterThreads. Its done by taking hash of the cache key modulo queue count. WriterThread when
228   * it runs takes whatever has been recently added and 'drains' the entries to the BucketCache. It
229   * then updates the ramCache and backingMap accordingly.
230   */
231  transient final ArrayList<BlockingQueue<RAMQueueEntry>> writerQueues = new ArrayList<>();
232  transient final WriterThread[] writerThreads;
233
234  /** Volatile boolean to track if free space is in process or not */
235  private volatile boolean freeInProgress = false;
236  private transient final Lock freeSpaceLock = new ReentrantLock();
237
238  private final LongAdder realCacheSize = new LongAdder();
239  private final LongAdder heapSize = new LongAdder();
240  /** Current number of cached elements */
241  private final LongAdder blockNumber = new LongAdder();
242
243  /** Cache access count (sequential ID) */
244  private final AtomicLong accessCount = new AtomicLong();
245
246  private final BucketCacheStats cacheStats;
247  private final String persistencePath;
248  static AtomicBoolean isCacheInconsistent = new AtomicBoolean(false);
249  private final long cacheCapacity;
250  /** Approximate block size */
251  private final long blockSize;
252
253  /** Duration of IO errors tolerated before we disable cache, 1 min as default */
254  private final int ioErrorsTolerationDuration;
255  // 1 min
256  public static final int DEFAULT_ERROR_TOLERATION_DURATION = 60 * 1000;
257
258  // Start time of first IO error when reading or writing IO Engine, it will be
259  // reset after a successful read/write.
260  private volatile long ioErrorStartTime = -1;
261
262  private transient Configuration conf;
263
264  /**
265   * A ReentrantReadWriteLock to lock on a particular block identified by offset. The purpose of
266   * this is to avoid freeing the block which is being read.
267   * <p>
268   */
269  transient final IdReadWriteLock<Long> offsetLock;
270
271  transient NavigableSet<BlockCacheKey> blocksByHFile = new ConcurrentSkipListSet<>(
272    Comparator.comparing(BlockCacheKey::getHfileName).thenComparingLong(BlockCacheKey::getOffset));
273
274  /** Statistics thread schedule pool (for heavy debugging, could remove) */
275  private transient final ScheduledExecutorService scheduleThreadPool =
276    Executors.newScheduledThreadPool(1,
277      new ThreadFactoryBuilder().setNameFormat("BucketCacheStatsExecutor").setDaemon(true).build());
278
279  /** Janitor thread schedule pool (critical cleanup, don't remove) */
280  private transient final ScheduledExecutorService janitorThreadPool =
281    Executors.newScheduledThreadPool(1,
282      new ThreadFactoryBuilder().setNameFormat("BucketCacheRWLockJanitor").setDaemon(true).build());
283
284  // Allocate or free space for the block
285  private transient BucketAllocator bucketAllocator;
286
287  /** Acceptable size of cache (no evictions if size < acceptable) */
288  private float acceptableFactor;
289
290  /** Minimum threshold of cache (when evicting, evict until size < min) */
291  private float minFactor;
292
293  /**
294   * Free this floating point factor of extra blocks when evicting. For example free the number of
295   * blocks requested * (1 + extraFreeFactor)
296   */
297  private float extraFreeFactor;
298
299  /** Single access bucket size */
300  private float singleFactor;
301
302  /** Multiple access bucket size */
303  private float multiFactor;
304
305  /** In-memory bucket size */
306  private float memoryFactor;
307
308  /** Lock janitor period in seconds */
309  private final int lockJanitorPeriod;
310
311  private volatile long bucketcachePersistInterval;
312
313  private static final String FILE_VERIFY_ALGORITHM =
314    "hbase.bucketcache.persistent.file.integrity.check.algorithm";
315  private static final String DEFAULT_FILE_VERIFY_ALGORITHM = "MD5";
316
317  static final String QUEUE_ADDITION_WAIT_TIME = "hbase.bucketcache.queue.addition.waittime";
318  private static final long DEFAULT_QUEUE_ADDITION_WAIT_TIME = 0;
319  private long queueAdditionWaitTime;
320  /**
321   * Use {@link java.security.MessageDigest} class's encryption algorithms to check persistent file
322   * integrity, default algorithm is MD5
323   */
324  private String algorithm;
325
326  private long persistenceChunkSize;
327
328  /* Tracing failed Bucket Cache allocations. */
329  private long allocFailLogPrevTs; // time of previous log event for allocation failure.
330  private static final int ALLOCATION_FAIL_LOG_TIME_PERIOD = 60000; // Default 1 minute.
331
332  private transient Map<String, HRegion> onlineRegions;
333
334  private long orphanBlockGracePeriod = 0;
335
336  public BucketCache(String ioEngineName, long capacity, int blockSize, int[] bucketSizes,
337    int writerThreadNum, int writerQLen, String persistencePath) throws IOException {
338    this(ioEngineName, capacity, blockSize, bucketSizes, writerThreadNum, writerQLen,
339      persistencePath, DEFAULT_ERROR_TOLERATION_DURATION, HBaseConfiguration.create());
340  }
341
342  public BucketCache(String ioEngineName, long capacity, int blockSize, int[] bucketSizes,
343    int writerThreadNum, int writerQLen, String persistencePath, int ioErrorsTolerationDuration,
344    Configuration conf) throws IOException {
345    this(ioEngineName, capacity, blockSize, bucketSizes, writerThreadNum, writerQLen,
346      persistencePath, ioErrorsTolerationDuration, conf, null);
347  }
348
349  public BucketCache(String ioEngineName, long capacity, int blockSize, int[] bucketSizes,
350    int writerThreadNum, int writerQLen, String persistencePath, int ioErrorsTolerationDuration,
351    Configuration conf, Map<String, HRegion> onlineRegions) throws IOException {
352    Preconditions.checkArgument(blockSize > 0,
353      "BucketCache capacity is set to " + blockSize + ", can not be less than 0");
354
355    // Initialize the lock pool
356    boolean useStrongRef = conf.getBoolean(STRONG_REF_KEY, STRONG_REF_DEFAULT);
357    this.lockJanitorPeriod =
358      conf.getInt(LOCK_JANITOR_PERIOD_SECONDS_CONFIG_NAME, DEFAULT_LOCK_JANITOR_PERIOD_SECONDS);
359    if (useStrongRef) {
360      this.offsetLock = new IdReadWriteLockStrongRef<>();
361    } else {
362      // Optimization (low-latency): move the lock pool cleanup off the read-path
363      this.offsetLock = new IdReadWriteLockWithObjectPool<>(ReferenceType.SOFT, false);
364    }
365
366    this.conf = conf;
367    this.algorithm = conf.get(FILE_VERIFY_ALGORITHM, DEFAULT_FILE_VERIFY_ALGORITHM);
368    this.ioEngine = getIOEngineFromName(ioEngineName, capacity, persistencePath);
369    this.writerThreads = new WriterThread[writerThreadNum];
370    this.onlineRegions = onlineRegions;
371    this.orphanBlockGracePeriod =
372      conf.getLong(BLOCK_ORPHAN_GRACE_PERIOD, BLOCK_ORPHAN_GRACE_PERIOD_DEFAULT);
373    long blockNumCapacity = capacity / blockSize;
374    if (blockNumCapacity >= Integer.MAX_VALUE) {
375      // Enough for about 32TB of cache!
376      throw new IllegalArgumentException("Cache capacity is too large, only support 32TB now");
377    }
378
379    // these sets the dynamic configs
380    this.onConfigurationChange(conf);
381    this.cacheStats =
382      new BucketCacheStats(conf.getInt(BLOCKCACHE_STATS_PERIODS, DEFAULT_BLOCKCACHE_STATS_PERIODS),
383        conf.getInt(BLOCKCACHE_STATS_PERIOD_MINUTES_KEY, DEFAULT_BLOCKCACHE_STATS_PERIOD_MINUTES));
384
385    LOG.info("Instantiating BucketCache with acceptableFactor: " + acceptableFactor
386      + ", minFactor: " + minFactor + ", extraFreeFactor: " + extraFreeFactor + ", singleFactor: "
387      + singleFactor + ", multiFactor: " + multiFactor + ", memoryFactor: " + memoryFactor
388      + ", useStrongRef: " + useStrongRef + ", lockJanitorPeriod: " + lockJanitorPeriod);
389
390    this.cacheCapacity = capacity;
391    this.persistencePath = persistencePath;
392    this.blockSize = blockSize;
393    this.ioErrorsTolerationDuration = ioErrorsTolerationDuration;
394    this.cacheState = CacheState.INITIALIZING;
395
396    this.allocFailLogPrevTs = 0;
397
398    for (int i = 0; i < writerThreads.length; ++i) {
399      writerQueues.add(new ArrayBlockingQueue<>(writerQLen));
400    }
401
402    assert writerQueues.size() == writerThreads.length;
403    this.ramCache = new RAMCache();
404
405    this.backingMap = new ConcurrentHashMap<>((int) blockNumCapacity);
406    instantiateWriterThreads();
407
408    if (isCachePersistent()) {
409      if (ioEngine instanceof FileIOEngine) {
410        startBucketCachePersisterThread();
411      }
412      startPersistenceRetriever(bucketSizes, capacity);
413    } else {
414      bucketAllocator = new BucketAllocator(capacity, bucketSizes);
415      this.cacheState = CacheState.ENABLED;
416      startWriterThreads();
417    }
418
419    // Run the statistics thread periodically to print the cache statistics log
420    // TODO: Add means of turning this off. Bit obnoxious running thread just to make a log
421    // every five minutes.
422    this.scheduleThreadPool.scheduleAtFixedRate(new StatisticsThread(this), statThreadPeriod,
423      statThreadPeriod, TimeUnit.SECONDS);
424
425    // Schedule the lock pool janitor (if using Soft Refs)
426    if (!useStrongRef) {
427      this.janitorThreadPool.scheduleAtFixedRate(
428        new IdReadWriteLockPoolJanitor("BucketCache",
429          (IdReadWriteLockWithObjectPool<Long>) offsetLock),
430        lockJanitorPeriod, lockJanitorPeriod, TimeUnit.SECONDS);
431    }
432
433    LOG.info("Started bucket cache; ioengine=" + ioEngineName + ", capacity="
434      + StringUtils.byteDesc(capacity) + ", blockSize=" + StringUtils.byteDesc(blockSize)
435      + ", writerThreadNum=" + writerThreadNum + ", writerQLen=" + writerQLen + ", persistencePath="
436      + persistencePath + ", bucketAllocator=" + BucketAllocator.class.getName());
437  }
438
439  private void startPersistenceRetriever(int[] bucketSizes, long capacity) {
440    Runnable persistentCacheRetriever = () -> {
441      try {
442        retrieveFromFile(bucketSizes);
443        LOG.info("Persistent bucket cache recovery from {} is complete.", persistencePath);
444      } catch (Throwable ex) {
445        LOG.warn("Can't restore from file[{}]. The bucket cache will be reset and rebuilt."
446          + " Exception seen: ", persistencePath, ex);
447        backingMap.clear();
448        fullyCachedFiles.clear();
449        backingMapValidated.set(true);
450        regionCachedSize.clear();
451        try {
452          bucketAllocator = new BucketAllocator(capacity, bucketSizes);
453        } catch (BucketAllocatorException allocatorException) {
454          LOG.error("Exception during Bucket Allocation", allocatorException);
455        }
456      } finally {
457        synchronized (BucketCache.this) {
458          if (cacheState == CacheState.INITIALIZING) {
459            cacheState = CacheState.ENABLED;
460            startWriterThreads();
461          }
462        }
463      }
464    };
465    persistenceRetrieverThread = new Thread(persistentCacheRetriever,
466      "BucketCachePersistenceRetriever-" + System.identityHashCode(this));
467    persistenceRetrieverThread.start();
468  }
469
470  private void sanityCheckConfigs() {
471    Preconditions.checkArgument(acceptableFactor <= 1 && acceptableFactor >= 0,
472      ACCEPT_FACTOR_CONFIG_NAME + " must be between 0.0 and 1.0");
473    Preconditions.checkArgument(minFactor <= 1 && minFactor >= 0,
474      MIN_FACTOR_CONFIG_NAME + " must be between 0.0 and 1.0");
475    Preconditions.checkArgument(minFactor <= acceptableFactor,
476      MIN_FACTOR_CONFIG_NAME + " must be <= " + ACCEPT_FACTOR_CONFIG_NAME);
477    Preconditions.checkArgument(extraFreeFactor >= 0,
478      EXTRA_FREE_FACTOR_CONFIG_NAME + " must be greater than 0.0");
479    Preconditions.checkArgument(singleFactor <= 1 && singleFactor >= 0,
480      SINGLE_FACTOR_CONFIG_NAME + " must be between 0.0 and 1.0");
481    Preconditions.checkArgument(multiFactor <= 1 && multiFactor >= 0,
482      MULTI_FACTOR_CONFIG_NAME + " must be between 0.0 and 1.0");
483    Preconditions.checkArgument(memoryFactor <= 1 && memoryFactor >= 0,
484      MEMORY_FACTOR_CONFIG_NAME + " must be between 0.0 and 1.0");
485    Preconditions.checkArgument((singleFactor + multiFactor + memoryFactor) == 1,
486      SINGLE_FACTOR_CONFIG_NAME + ", " + MULTI_FACTOR_CONFIG_NAME + ", and "
487        + MEMORY_FACTOR_CONFIG_NAME + " segments must add up to 1.0");
488    Preconditions.checkArgument(lockJanitorPeriod > 0,
489      LOCK_JANITOR_PERIOD_SECONDS_CONFIG_NAME + " must be greater than 0");
490    if (this.persistenceChunkSize <= 0) {
491      persistenceChunkSize = DEFAULT_BACKING_MAP_PERSISTENCE_CHUNK_SIZE;
492    }
493  }
494
495  /**
496   * Called by the constructor to instantiate the writer threads.
497   */
498  private void instantiateWriterThreads() {
499    final String threadName = Thread.currentThread().getName();
500    for (int i = 0; i < this.writerThreads.length; ++i) {
501      this.writerThreads[i] = new WriterThread(this.writerQueues.get(i));
502      this.writerThreads[i].setName(threadName + "-BucketCacheWriter-" + i);
503      this.writerThreads[i].setDaemon(true);
504    }
505  }
506
507  /**
508   * Called by the constructor to start the writer threads. Used by tests that need to override
509   * starting the threads.
510   */
511  protected void startWriterThreads() {
512    for (WriterThread thread : writerThreads) {
513      thread.start();
514    }
515  }
516
517  void startBucketCachePersisterThread() {
518    LOG.info("Starting BucketCachePersisterThread");
519    cachePersister = new BucketCachePersister(this);
520    cachePersister.setDaemon(true);
521    cachePersister.start();
522  }
523
524  @Override
525  public boolean isCacheEnabled() {
526    return this.cacheState == CacheState.ENABLED;
527  }
528
529  @Override
530  public long getMaxSize() {
531    return this.cacheCapacity;
532  }
533
534  public String getIoEngine() {
535    return ioEngine.toString();
536  }
537
538  /**
539   * Get the IOEngine from the IO engine name
540   * @return the IOEngine
541   */
542  private IOEngine getIOEngineFromName(String ioEngineName, long capacity, String persistencePath)
543    throws IOException {
544    if (ioEngineName.startsWith("file:") || ioEngineName.startsWith("files:")) {
545      // In order to make the usage simple, we only need the prefix 'files:' in
546      // document whether one or multiple file(s), but also support 'file:' for
547      // the compatibility
548      String[] filePaths =
549        ioEngineName.substring(ioEngineName.indexOf(":") + 1).split(FileIOEngine.FILE_DELIMITER);
550      return new FileIOEngine(capacity, persistencePath != null, filePaths);
551    } else if (ioEngineName.startsWith("offheap")) {
552      return new ByteBufferIOEngine(capacity);
553    } else if (ioEngineName.startsWith("mmap:")) {
554      return new ExclusiveMemoryMmapIOEngine(ioEngineName.substring(5), capacity);
555    } else if (ioEngineName.startsWith("pmem:")) {
556      // This mode of bucket cache creates an IOEngine over a file on the persistent memory
557      // device. Since the persistent memory device has its own address space the contents
558      // mapped to this address space does not get swapped out like in the case of mmapping
559      // on to DRAM. Hence the cells created out of the hfile blocks in the pmem bucket cache
560      // can be directly referred to without having to copy them onheap. Once the RPC is done,
561      // the blocks can be returned back as in case of ByteBufferIOEngine.
562      return new SharedMemoryMmapIOEngine(ioEngineName.substring(5), capacity);
563    } else {
564      throw new IllegalArgumentException(
565        "Don't understand io engine name for cache- prefix with file:, files:, mmap: or offheap");
566    }
567  }
568
569  public boolean isCachePersistenceEnabled() {
570    return persistencePath != null;
571  }
572
573  /**
574   * Cache the block with the specified name and buffer.
575   * @param cacheKey block's cache key
576   * @param buf      block buffer
577   */
578  @Override
579  public void cacheBlock(BlockCacheKey cacheKey, Cacheable buf) {
580    cacheBlock(cacheKey, buf, false);
581  }
582
583  /**
584   * Cache the block with the specified name and buffer.
585   * @param cacheKey   block's cache key
586   * @param cachedItem block buffer
587   * @param inMemory   if block is in-memory
588   */
589  @Override
590  public void cacheBlock(BlockCacheKey cacheKey, Cacheable cachedItem, boolean inMemory) {
591    cacheBlockWithWait(cacheKey, cachedItem, inMemory, false);
592  }
593
594  /**
595   * Cache the block with the specified name and buffer.
596   * @param cacheKey   block's cache key
597   * @param cachedItem block buffer
598   * @param inMemory   if block is in-memory
599   */
600  @Override
601  public void cacheBlock(BlockCacheKey cacheKey, Cacheable cachedItem, boolean inMemory,
602    boolean waitWhenCache) {
603    cacheBlockWithWait(cacheKey, cachedItem, inMemory, waitWhenCache && queueAdditionWaitTime > 0);
604  }
605
606  /**
607   * Cache the block to ramCache
608   * @param cacheKey   block's cache key
609   * @param cachedItem block buffer
610   * @param inMemory   if block is in-memory
611   * @param wait       if true, blocking wait when queue is full
612   */
613  public void cacheBlockWithWait(BlockCacheKey cacheKey, Cacheable cachedItem, boolean inMemory,
614    boolean wait) {
615    if (isCacheEnabled()) {
616      if (backingMap.containsKey(cacheKey) || ramCache.containsKey(cacheKey)) {
617        if (shouldReplaceExistingCacheBlock(cacheKey, cachedItem)) {
618          BucketEntry bucketEntry = backingMap.get(cacheKey);
619          if (bucketEntry != null && bucketEntry.isRpcRef()) {
620            // avoid replace when there are RPC refs for the bucket entry in bucket cache
621            return;
622          }
623          cacheBlockWithWaitInternal(cacheKey, cachedItem, inMemory, wait);
624        }
625      } else {
626        cacheBlockWithWaitInternal(cacheKey, cachedItem, inMemory, wait);
627      }
628    }
629  }
630
631  protected boolean shouldReplaceExistingCacheBlock(BlockCacheKey cacheKey, Cacheable newBlock) {
632    return BlockCacheUtil.shouldReplaceExistingCacheBlock(this, cacheKey, newBlock);
633  }
634
635  protected void cacheBlockWithWaitInternal(BlockCacheKey cacheKey, Cacheable cachedItem,
636    boolean inMemory, boolean wait) {
637    if (!isCacheEnabled()) {
638      return;
639    }
640    if (cacheKey.getBlockType() == null && cachedItem.getBlockType() != null) {
641      cacheKey.setBlockType(cachedItem.getBlockType());
642    }
643    LOG.debug("Caching key={}, item={}, key heap size={}", cacheKey, cachedItem,
644      cacheKey.heapSize());
645    // Stuff the entry into the RAM cache so it can get drained to the persistent store
646    RAMQueueEntry re = new RAMQueueEntry(cacheKey, cachedItem, accessCount.incrementAndGet(),
647      inMemory, isCachePersistent() && ioEngine instanceof FileIOEngine, wait);
648    /**
649     * Don't use ramCache.put(cacheKey, re) here. because there may be a existing entry with same
650     * key in ramCache, the heap size of bucket cache need to update if replacing entry from
651     * ramCache. But WriterThread will also remove entry from ramCache and update heap size, if
652     * using ramCache.put(), It's possible that the removed entry in WriterThread is not the correct
653     * one, then the heap size will mess up (HBASE-20789)
654     */
655    if (ramCache.putIfAbsent(cacheKey, re) != null) {
656      return;
657    }
658    int queueNum = (cacheKey.hashCode() & 0x7FFFFFFF) % writerQueues.size();
659    BlockingQueue<RAMQueueEntry> bq = writerQueues.get(queueNum);
660    boolean successfulAddition = false;
661    if (wait) {
662      try {
663        successfulAddition = bq.offer(re, queueAdditionWaitTime, TimeUnit.MILLISECONDS);
664      } catch (InterruptedException e) {
665        LOG.error("Thread interrupted: ", e);
666        Thread.currentThread().interrupt();
667      }
668    } else {
669      successfulAddition = bq.offer(re);
670    }
671    if (!successfulAddition) {
672      LOG.debug("Failed to insert block {} into the cache writers queue", cacheKey);
673      ramCache.remove(cacheKey);
674      cacheStats.failInsert();
675    } else {
676      this.blockNumber.increment();
677      this.heapSize.add(cachedItem.heapSize());
678    }
679  }
680
681  /**
682   * If the passed cache key relates to a reference (&lt;hfile&gt;.&lt;parentEncRegion&gt;), this
683   * method looks for the block from the referred file, in the cache. If present in the cache, the
684   * block for the referred file is returned, otherwise, this method returns null. It will also
685   * return null if the passed cache key doesn't relate to a reference.
686   * @param key the BlockCacheKey instance to look for in the cache.
687   * @return the cached block from the referred file, null if there's no such block in the cache or
688   *         the passed key doesn't relate to a reference.
689   */
690  public BucketEntry getBlockForReference(BlockCacheKey key) {
691    BlockCacheKey referredKey = getBlockKeyForReference(key);
692    BucketEntry foundEntry = referredKey != null ? backingMap.get(referredKey) : null;
693    if (referredKey != null) {
694      LOG.debug("Got a link/ref: {}. Related cacheKey: {}. Found entry: {}", key.getHfileName(),
695        referredKey, foundEntry);
696    }
697    return foundEntry;
698  }
699
700  private BlockCacheKey getBlockKeyForReference(BlockCacheKey key) {
701    if (!StoreFileInfo.isReference(key.getHfileName())) {
702      return null;
703    }
704    String referredFileName =
705      StoreFileInfo.getReferredToRegionAndFile(key.getHfileName()).getSecond();
706    return referredFileName != null ? new BlockCacheKey(referredFileName, key.getOffset()) : null;
707  }
708
709  /**
710   * Get the buffer of the block with the specified key.
711   * @param key                block's cache key
712   * @param caching            true if the caller caches blocks on cache misses
713   * @param repeat             Whether this is a repeat lookup for the same block
714   * @param updateCacheMetrics Whether we should update cache metrics or not
715   * @return buffer of specified cache key, or null if not in cache
716   */
717  @Override
718  public Cacheable getBlock(BlockCacheKey key, boolean caching, boolean repeat,
719    boolean updateCacheMetrics) {
720    if (!isCacheEnabled()) {
721      cacheStats.miss(caching, key.isPrimary(), key.getBlockType());
722      return null;
723    }
724    RAMQueueEntry re = ramCache.get(key);
725    if (re != null) {
726      if (updateCacheMetrics) {
727        cacheStats.hit(caching, key.isPrimary(), key.getBlockType());
728      }
729      re.access(accessCount.incrementAndGet());
730      return re.getData();
731    }
732    BlockCacheKey backingMapLookupKey = key;
733    BucketEntry bucketEntry = backingMap.get(backingMapLookupKey);
734    LOG.debug("bucket entry for key {}: {}", key,
735      bucketEntry == null ? null : bucketEntry.offset());
736    if (bucketEntry == null) {
737      backingMapLookupKey = getBlockKeyForReference(key);
738      if (backingMapLookupKey != null) {
739        bucketEntry = backingMap.get(backingMapLookupKey);
740        LOG.debug("Got a link/ref: {}. Related cacheKey: {}. Found entry: {}", key.getHfileName(),
741          backingMapLookupKey, bucketEntry);
742      }
743    }
744    if (bucketEntry != null) {
745      long start = System.nanoTime();
746      ReentrantReadWriteLock lock = offsetLock.getLock(bucketEntry.offset());
747      boolean inconsistentEntry = false;
748      try {
749        lock.readLock().lock();
750        // We can not read here even if backingMap does contain the given key because its offset
751        // maybe changed. If we lock BlockCacheKey instead of offset, then we can only check
752        // existence here.
753        if (bucketEntry.equals(backingMap.get(backingMapLookupKey))) {
754          // Read the block from IOEngine based on the bucketEntry's offset and length, NOTICE: the
755          // block will use the refCnt of bucketEntry, which means if two HFileBlock mapping to
756          // the same BucketEntry, then all of the three will share the same refCnt.
757          Cacheable cachedBlock = ioEngine.read(bucketEntry);
758          if (ioEngine.usesSharedMemory()) {
759            // If IOEngine use shared memory, cachedBlock and BucketEntry will share the
760            // same RefCnt, do retain here, in order to count the number of RPC references
761            cachedBlock.retain();
762          }
763          // Update the cache statistics.
764          if (updateCacheMetrics) {
765            cacheStats.hit(caching, key.isPrimary(), key.getBlockType());
766            cacheStats.ioHit(System.nanoTime() - start);
767          }
768          bucketEntry.access(accessCount.incrementAndGet());
769          if (this.ioErrorStartTime > 0) {
770            ioErrorStartTime = -1;
771          }
772          return cachedBlock;
773        }
774      } catch (HBaseIOException hioex) {
775        // FileIOEngine throws this when its cached time differs from the persisted index. A plain
776        // IOException still follows the configured tolerance policy below.
777        inconsistentEntry = true;
778        LOG.debug("Failed to fetch block for cache key: {}.", key, hioex);
779      } catch (IOException ioex) {
780        LOG.error("Failed reading block " + key + " from bucket cache", ioex);
781        checkIOErrorIsTolerated();
782      } finally {
783        lock.readLock().unlock();
784      }
785      if (inconsistentEntry) {
786        evictInconsistentEntry(backingMapLookupKey, bucketEntry);
787      }
788    }
789    if (!repeat && updateCacheMetrics) {
790      cacheStats.miss(caching, key.isPrimary(), key.getBlockType());
791    }
792    return null;
793  }
794
795  private void evictInconsistentEntry(BlockCacheKey lookupKey, BucketEntry bucketEntry) {
796    BlockCacheKey storedKey = blocksByHFile.ceiling(lookupKey);
797    if (storedKey == null || !storedKey.equals(lookupKey)) {
798      return;
799    }
800    bucketEntry.withWriteLock(offsetLock, () -> {
801      if (backingMap.remove(storedKey, bucketEntry)) {
802        blockEvicted(storedKey, bucketEntry, true, false);
803      }
804      return null;
805    });
806  }
807
808  /**
809   * This method is invoked after the bucketEntry is removed from {@link BucketCache#backingMap}
810   */
811  void blockEvicted(BlockCacheKey cacheKey, BucketEntry bucketEntry, boolean decrementBlockNumber,
812    boolean evictedByEvictionProcess) {
813    bucketEntry.markAsEvicted();
814    blocksByHFile.remove(cacheKey);
815    // putIntoBackingMap accounts every entry added to the backingMap, regardless of the IOEngine,
816    // so every entry removed from it must be decremented as well.
817    updateRegionCachedSize(cacheKey, (bucketEntry.getLength() * -1));
818    if (decrementBlockNumber) {
819      this.blockNumber.decrement();
820      if (ioEngine.isPersistent()) {
821        fullyCachedFiles.remove(cacheKey.getHfileName());
822      }
823    }
824    if (evictedByEvictionProcess) {
825      cacheStats.evicted(bucketEntry.getCachedTime(), cacheKey.isPrimary());
826    }
827    if (ioEngine.isPersistent()) {
828      setCacheInconsistent(true);
829    }
830  }
831
832  public void fileCacheCompleted(Path filePath, long size) {
833    Pair<String, Long> pair = new Pair<>();
834    // sets the region name
835    String regionName = filePath.getParent().getParent().getName();
836    pair.setFirst(regionName);
837    pair.setSecond(size);
838    fullyCachedFiles.put(filePath.getName(), pair);
839  }
840
841  private void updateRegionCachedSize(BlockCacheKey key, long cachedSize) {
842    if (key.getRegionName() != null) {
843      if (key.isArchived()) {
844        LOG.trace("Skipping region cached size update for archived file:{} from region: {}",
845          key.getHfileName(), key.getRegionName());
846      } else {
847        String regionName = key.getRegionName();
848        regionCachedSize.merge(regionName, cachedSize,
849          (previousSize, newBlockSize) -> previousSize + newBlockSize);
850        // If all the blocks for a region are evicted from the cache,
851        // remove the entry for that region from regionCachedSize map.
852        if (regionCachedSize.getOrDefault(regionName, 0L) <= 0) {
853          regionCachedSize.remove(regionName);
854        }
855      }
856    }
857  }
858
859  /**
860   * Free the {{@link BucketEntry} actually,which could only be invoked when the
861   * {@link BucketEntry#refCnt} becoming 0.
862   */
863  void freeBucketEntry(BucketEntry bucketEntry) {
864    bucketAllocator.freeBlock(bucketEntry.offset(), bucketEntry.getLength());
865    realCacheSize.add(-1 * bucketEntry.getLength());
866  }
867
868  /**
869   * Try to evict the block from {@link BlockCache} by force. We'll call this in few cases:<br>
870   * 1. Close an HFile, and clear all cached blocks. <br>
871   * 2. Call {@link Admin#clearBlockCache(TableName)} to clear all blocks for a given table.<br>
872   * <p>
873   * Firstly, we'll try to remove the block from RAMCache,and then try to evict from backingMap.
874   * Here we evict the block from backingMap immediately, but only free the reference from bucket
875   * cache by calling {@link BucketEntry#markedAsEvicted}. If there're still some RPC referring this
876   * block, block can only be de-allocated when all of them release the block.
877   * <p>
878   * NOTICE: we need to grab the write offset lock firstly before releasing the reference from
879   * bucket cache. if we don't, we may read an {@link BucketEntry} with refCnt = 0 when
880   * {@link BucketCache#getBlock(BlockCacheKey, boolean, boolean, boolean)}, it's a memory leak.
881   * @param cacheKey Block to evict
882   * @return true to indicate whether we've evicted successfully or not.
883   */
884  @Override
885  public boolean evictBlock(BlockCacheKey cacheKey) {
886    return doEvictBlock(cacheKey, null, false);
887  }
888
889  /**
890   * Evict the {@link BlockCacheKey} and {@link BucketEntry} from {@link BucketCache#backingMap} and
891   * {@link BucketCache#ramCache}. <br/>
892   * NOTE:When Evict from {@link BucketCache#backingMap},only the matched {@link BlockCacheKey} and
893   * {@link BucketEntry} could be removed.
894   * @param cacheKey    {@link BlockCacheKey} to evict.
895   * @param bucketEntry {@link BucketEntry} matched {@link BlockCacheKey} to evict.
896   * @return true to indicate whether we've evicted successfully or not.
897   */
898  private boolean doEvictBlock(BlockCacheKey cacheKey, BucketEntry bucketEntry,
899    boolean evictedByEvictionProcess) {
900    if (!isCacheEnabled()) {
901      return false;
902    }
903    boolean existedInRamCache = removeFromRamCache(cacheKey);
904    if (bucketEntry == null) {
905      bucketEntry = backingMap.get(cacheKey);
906    }
907    final BucketEntry bucketEntryToUse = bucketEntry;
908
909    if (bucketEntryToUse == null) {
910      if (existedInRamCache && evictedByEvictionProcess) {
911        cacheStats.evicted(0, cacheKey.isPrimary());
912      }
913      return existedInRamCache;
914    } else {
915      return bucketEntryToUse.withWriteLock(offsetLock, () -> {
916        if (backingMap.remove(cacheKey, bucketEntryToUse)) {
917          LOG.debug("removed key {} from back map with offset lock {} in the evict process",
918            cacheKey, bucketEntryToUse.offset());
919          blockEvicted(cacheKey, bucketEntryToUse, !existedInRamCache, evictedByEvictionProcess);
920          return true;
921        }
922        return false;
923      });
924    }
925  }
926
927  /**
928   * <pre>
929   * Create the {@link Recycler} for {@link BucketEntry#refCnt},which would be used as
930   * {@link RefCnt#recycler} of {@link HFileBlock#buf} returned from {@link BucketCache#getBlock}.
931   * NOTE: for {@link BucketCache#getBlock},the {@link RefCnt#recycler} of {@link HFileBlock#buf}
932   * from {@link BucketCache#backingMap} and {@link BucketCache#ramCache} are different:
933   * 1.For {@link RefCnt#recycler} of {@link HFileBlock#buf} from {@link BucketCache#backingMap},
934   *   it is the return value of current {@link BucketCache#createRecycler} method.
935   *
936   * 2.For {@link RefCnt#recycler} of {@link HFileBlock#buf} from {@link BucketCache#ramCache},
937   *   it is {@link ByteBuffAllocator#putbackBuffer}.
938   * </pre>
939   */
940  public Recycler createRecycler(final BucketEntry bucketEntry) {
941    return () -> {
942      freeBucketEntry(bucketEntry);
943      return;
944    };
945  }
946
947  /**
948   * NOTE: This method is only for test.
949   */
950  public boolean evictBlockIfNoRpcReferenced(BlockCacheKey blockCacheKey) {
951    BucketEntry bucketEntry = backingMap.get(blockCacheKey);
952    if (bucketEntry == null) {
953      return false;
954    }
955    return evictBucketEntryIfNoRpcReferenced(blockCacheKey, bucketEntry);
956  }
957
958  /**
959   * Evict {@link BlockCacheKey} and its corresponding {@link BucketEntry} only if
960   * {@link BucketEntry#isRpcRef} is false. <br/>
961   * NOTE:When evict from {@link BucketCache#backingMap},only the matched {@link BlockCacheKey} and
962   * {@link BucketEntry} could be removed.
963   * @param blockCacheKey {@link BlockCacheKey} to evict.
964   * @param bucketEntry   {@link BucketEntry} matched {@link BlockCacheKey} to evict.
965   * @return true to indicate whether we've evicted successfully or not.
966   */
967  boolean evictBucketEntryIfNoRpcReferenced(BlockCacheKey blockCacheKey, BucketEntry bucketEntry) {
968    if (!bucketEntry.isRpcRef()) {
969      return doEvictBlock(blockCacheKey, bucketEntry, true);
970    }
971    return false;
972  }
973
974  /**
975   * Since HBASE-29249, the following properties governin freeSpace behaviour and block priorities
976   * were made dynamically configurable: - hbase.bucketcache.acceptfactor -
977   * hbase.bucketcache.minfactor - hbase.bucketcache.extrafreefactor -
978   * hbase.bucketcache.single.factor - hbase.bucketcache.multi.factor -
979   * hbase.bucketcache.multi.factor - hbase.bucketcache.memory.factor The
980   * hbase.bucketcache.queue.addition.waittime property allows for introducing a delay in the
981   * publishing of blocks for the cache writer threads during prefetch reads only (client reads
982   * wouldn't get delayed). It has also been made dynamic configurable since HBASE-29249. The
983   * hbase.bucketcache.persist.intervalinmillis property determines the frequency for saving the
984   * persistent cache, and it has also been made dynamically configurable since HBASE-29249. The new
985   * interval applies to subsequent sleeps without interrupting a sleep already in progress. The
986   * hbase.bucketcache.persistence.chunksize property determines the size of the persistent file
987   * splits (due to the limitation of maximum allowed protobuff size), and it has also been made
988   * dynamically configurable since HBASE-29249.
989   * @param config the new configuration to be updated.
990   */
991  @Override
992  public void onConfigurationChange(Configuration config) {
993    this.acceptableFactor = conf.getFloat(ACCEPT_FACTOR_CONFIG_NAME, DEFAULT_ACCEPT_FACTOR);
994    this.minFactor = conf.getFloat(MIN_FACTOR_CONFIG_NAME, DEFAULT_MIN_FACTOR);
995    this.extraFreeFactor = conf.getFloat(EXTRA_FREE_FACTOR_CONFIG_NAME, DEFAULT_EXTRA_FREE_FACTOR);
996    this.singleFactor = conf.getFloat(SINGLE_FACTOR_CONFIG_NAME, DEFAULT_SINGLE_FACTOR);
997    this.multiFactor = conf.getFloat(MULTI_FACTOR_CONFIG_NAME, DEFAULT_MULTI_FACTOR);
998    this.memoryFactor = conf.getFloat(MEMORY_FACTOR_CONFIG_NAME, DEFAULT_MEMORY_FACTOR);
999    this.queueAdditionWaitTime =
1000      conf.getLong(QUEUE_ADDITION_WAIT_TIME, DEFAULT_QUEUE_ADDITION_WAIT_TIME);
1001    this.bucketcachePersistInterval = conf.getLong(BUCKETCACHE_PERSIST_INTERVAL_KEY, 1000);
1002    this.persistenceChunkSize =
1003      conf.getLong(BACKING_MAP_PERSISTENCE_CHUNK_SIZE, DEFAULT_BACKING_MAP_PERSISTENCE_CHUNK_SIZE);
1004    sanityCheckConfigs();
1005  }
1006
1007  protected boolean removeFromRamCache(BlockCacheKey cacheKey) {
1008    return ramCache.remove(cacheKey, re -> {
1009      if (re != null) {
1010        this.blockNumber.decrement();
1011        this.heapSize.add(-1 * re.getData().heapSize());
1012      }
1013    });
1014  }
1015
1016  public boolean isCacheInconsistent() {
1017    return isCacheInconsistent.get();
1018  }
1019
1020  public void setCacheInconsistent(boolean setCacheInconsistent) {
1021    isCacheInconsistent.set(setCacheInconsistent);
1022  }
1023
1024  protected void setCacheState(CacheState state) {
1025    cacheState = state;
1026  }
1027
1028  /*
1029   * Statistics thread. Periodically output cache statistics to the log.
1030   */
1031  private static class StatisticsThread extends Thread {
1032    private final BucketCache bucketCache;
1033
1034    public StatisticsThread(BucketCache bucketCache) {
1035      super("BucketCacheStatsThread");
1036      setDaemon(true);
1037      this.bucketCache = bucketCache;
1038    }
1039
1040    @Override
1041    public void run() {
1042      bucketCache.logStats();
1043    }
1044  }
1045
1046  public void logStats() {
1047    if (!isCacheInitialized("BucketCache::logStats")) {
1048      return;
1049    }
1050
1051    long totalSize = bucketAllocator.getTotalSize();
1052    long usedSize = bucketAllocator.getUsedSize();
1053    long freeSize = totalSize - usedSize;
1054    long cacheSize = getRealCacheSize();
1055    LOG.info("failedBlockAdditions=" + cacheStats.getFailedInserts() + ", " + "totalSize="
1056      + StringUtils.byteDesc(totalSize) + ", " + "freeSize=" + StringUtils.byteDesc(freeSize) + ", "
1057      + "usedSize=" + StringUtils.byteDesc(usedSize) + ", " + "cacheSize="
1058      + StringUtils.byteDesc(cacheSize) + ", " + "accesses=" + cacheStats.getRequestCount() + ", "
1059      + "hits=" + cacheStats.getHitCount() + ", " + "IOhitsPerSecond="
1060      + cacheStats.getIOHitsPerSecond() + ", " + "IOTimePerHit="
1061      + String.format("%.2f", cacheStats.getIOTimePerHit()) + ", " + "hitRatio="
1062      + (cacheStats.getHitCount() == 0
1063        ? "0,"
1064        : (StringUtils.formatPercent(cacheStats.getHitRatio(), 2) + ", "))
1065      + "cachingAccesses=" + cacheStats.getRequestCachingCount() + ", " + "cachingHits="
1066      + cacheStats.getHitCachingCount() + ", " + "cachingHitsRatio="
1067      + (cacheStats.getHitCachingCount() == 0
1068        ? "0,"
1069        : (StringUtils.formatPercent(cacheStats.getHitCachingRatio(), 2) + ", "))
1070      + "evictions=" + cacheStats.getEvictionCount() + ", " + "evicted="
1071      + cacheStats.getEvictedCount() + ", " + "evictedPerRun=" + cacheStats.evictedPerEviction()
1072      + ", " + "allocationFailCount=" + cacheStats.getAllocationFailCount() + ", blocksCount="
1073      + backingMap.size());
1074    cacheStats.reset();
1075
1076    bucketAllocator.logDebugStatistics();
1077  }
1078
1079  public long getRealCacheSize() {
1080    return this.realCacheSize.sum();
1081  }
1082
1083  public long acceptableSize() {
1084    if (!isCacheInitialized("BucketCache::acceptableSize")) {
1085      return 0;
1086    }
1087    return (long) Math.floor(bucketAllocator.getTotalSize() * acceptableFactor);
1088  }
1089
1090  long getPartitionSize(float partitionFactor) {
1091    if (!isCacheInitialized("BucketCache::getPartitionSize")) {
1092      return 0;
1093    }
1094
1095    return (long) Math.floor(bucketAllocator.getTotalSize() * partitionFactor * minFactor);
1096  }
1097
1098  /**
1099   * Return the count of bucketSizeinfos still need free space
1100   */
1101  private int bucketSizesAboveThresholdCount(float minFactor) {
1102    if (!isCacheInitialized("BucketCache::bucketSizesAboveThresholdCount")) {
1103      return 0;
1104    }
1105
1106    BucketAllocator.IndexStatistics[] stats = bucketAllocator.getIndexStatistics();
1107    int fullCount = 0;
1108    for (int i = 0; i < stats.length; i++) {
1109      long freeGoal = (long) Math.floor(stats[i].totalCount() * (1 - minFactor));
1110      freeGoal = Math.max(freeGoal, 1);
1111      if (stats[i].freeCount() < freeGoal) {
1112        fullCount++;
1113      }
1114    }
1115    return fullCount;
1116  }
1117
1118  /**
1119   * This method will find the buckets that are minimally occupied and are not reference counted and
1120   * will free them completely without any constraint on the access times of the elements, and as a
1121   * process will completely free at most the number of buckets passed, sometimes it might not due
1122   * to changing refCounts
1123   * @param completelyFreeBucketsNeeded number of buckets to free
1124   **/
1125  private void freeEntireBuckets(int completelyFreeBucketsNeeded) {
1126    if (!isCacheInitialized("BucketCache::freeEntireBuckets")) {
1127      return;
1128    }
1129
1130    if (completelyFreeBucketsNeeded != 0) {
1131      // First we will build a set where the offsets are reference counted, usually
1132      // this set is small around O(Handler Count) unless something else is wrong
1133      Set<Integer> inUseBuckets = new HashSet<>();
1134      backingMap.forEach((k, be) -> {
1135        if (be.isRpcRef()) {
1136          inUseBuckets.add(bucketAllocator.getBucketIndex(be.offset()));
1137        }
1138      });
1139      Set<Integer> candidateBuckets =
1140        bucketAllocator.getLeastFilledBuckets(inUseBuckets, completelyFreeBucketsNeeded);
1141      for (Map.Entry<BlockCacheKey, BucketEntry> entry : backingMap.entrySet()) {
1142        if (candidateBuckets.contains(bucketAllocator.getBucketIndex(entry.getValue().offset()))) {
1143          evictBucketEntryIfNoRpcReferenced(entry.getKey(), entry.getValue());
1144        }
1145      }
1146    }
1147  }
1148
1149  private long calculateBytesToFree(StringBuilder msgBuffer) {
1150    long bytesToFreeWithoutExtra = 0;
1151    BucketAllocator.IndexStatistics[] stats = bucketAllocator.getIndexStatistics();
1152    long[] bytesToFreeForBucket = new long[stats.length];
1153    for (int i = 0; i < stats.length; i++) {
1154      bytesToFreeForBucket[i] = 0;
1155      long freeGoal = (long) Math.floor(stats[i].totalCount() * (1 - minFactor));
1156      freeGoal = Math.max(freeGoal, 1);
1157      if (stats[i].freeCount() < freeGoal) {
1158        bytesToFreeForBucket[i] = stats[i].itemSize() * (freeGoal - stats[i].freeCount());
1159        bytesToFreeWithoutExtra += bytesToFreeForBucket[i];
1160        if (msgBuffer != null) {
1161          msgBuffer.append("Free for bucketSize(" + stats[i].itemSize() + ")="
1162            + StringUtils.byteDesc(bytesToFreeForBucket[i]) + ", ");
1163        }
1164      }
1165    }
1166    if (msgBuffer != null) {
1167      msgBuffer.append("Free for total=" + StringUtils.byteDesc(bytesToFreeWithoutExtra) + ", ");
1168    }
1169    return bytesToFreeWithoutExtra;
1170  }
1171
1172  /**
1173   * Free the space if the used size reaches acceptableSize() or one size block couldn't be
1174   * allocated. When freeing the space, we use the LRU algorithm and ensure there must be some
1175   * blocks evicted
1176   * @param why Why we are being called
1177   */
1178  void freeSpace(final String why) {
1179    if (!isCacheInitialized("BucketCache::freeSpace")) {
1180      return;
1181    }
1182    // Ensure only one freeSpace progress at a time
1183    if (!freeSpaceLock.tryLock()) {
1184      return;
1185    }
1186    try {
1187      freeInProgress = true;
1188      StringBuilder msgBuffer = LOG.isDebugEnabled() ? new StringBuilder() : null;
1189      long bytesToFreeWithoutExtra = calculateBytesToFree(msgBuffer);
1190      if (bytesToFreeWithoutExtra <= 0) {
1191        return;
1192      }
1193      long currentSize = bucketAllocator.getUsedSize();
1194      long totalSize = bucketAllocator.getTotalSize();
1195      if (LOG.isDebugEnabled() && msgBuffer != null) {
1196        LOG.debug("Free started because \"" + why + "\"; " + msgBuffer + " of current used="
1197          + StringUtils.byteDesc(currentSize) + ", actual cacheSize="
1198          + StringUtils.byteDesc(realCacheSize.sum()) + ", total="
1199          + StringUtils.byteDesc(totalSize));
1200      }
1201      long bytesToFreeWithExtra =
1202        (long) Math.floor(bytesToFreeWithoutExtra * (1 + extraFreeFactor));
1203      // Instantiate priority buckets
1204      BucketEntryGroup bucketSingle =
1205        new BucketEntryGroup(bytesToFreeWithExtra, blockSize, getPartitionSize(singleFactor));
1206      BucketEntryGroup bucketMulti =
1207        new BucketEntryGroup(bytesToFreeWithExtra, blockSize, getPartitionSize(multiFactor));
1208      BucketEntryGroup bucketMemory =
1209        new BucketEntryGroup(bytesToFreeWithExtra, blockSize, getPartitionSize(memoryFactor));
1210
1211      Set<String> allValidFiles = null;
1212      // We need the region/stores/files tree, in order to figure out if a block is "orphan" or not.
1213      // See further comments below for more details.
1214      if (onlineRegions != null) {
1215        allValidFiles = BlockCacheUtil.listAllFilesNames(onlineRegions);
1216      }
1217      // the cached time is recored in nanos, so we need to convert the grace period accordingly
1218      long orphanGracePeriodNanos = orphanBlockGracePeriod * 1000000;
1219      long bytesFreed = 0;
1220      // Check the list of files to determine the cold files which can be readily evicted.
1221      Map<String, String> coldFiles = null;
1222
1223      DataTieringManager dataTieringManager = DataTieringManager.getInstance();
1224      if (dataTieringManager != null) {
1225        coldFiles = dataTieringManager.getColdFilesList();
1226      }
1227      // Scan entire map putting bucket entry into appropriate bucket entry
1228      // group
1229      for (Map.Entry<BlockCacheKey, BucketEntry> bucketEntryWithKey : backingMap.entrySet()) {
1230        BlockCacheKey key = bucketEntryWithKey.getKey();
1231        BucketEntry entry = bucketEntryWithKey.getValue();
1232        // Under certain conditions, blocks for regions not on the current region server might
1233        // be hanging on the cache. For example, when using the persistent cache feature, if the
1234        // RS crashes, then if not the same regions are assigned back once its online again, blocks
1235        // for the previous online regions would be recovered and stay in the cache. These would be
1236        // "orphan" blocks, as the files these blocks belong to are not in any of the online
1237        // regions.
1238        // "Orphan" blocks are a pure waste of cache space and should be evicted first during
1239        // the freespace run.
1240        // Compactions and Flushes may cache blocks before its files are completely written. In
1241        // these cases the file won't be found in any of the online regions stores, but the block
1242        // shouldn't be evicted. To avoid this, we defined this
1243        // hbase.bucketcache.block.orphan.evictgraceperiod property, to account for a grace
1244        // period (default 24 hours) where a block should be checked if it's an orphan block.
1245        if (
1246          allValidFiles != null
1247            && entry.getCachedTime() < (System.nanoTime() - orphanGracePeriodNanos)
1248        ) {
1249          if (!allValidFiles.contains(key.getHfileName())) {
1250            if (evictBucketEntryIfNoRpcReferenced(key, entry)) {
1251              // We calculate the freed bytes, but we don't stop if the goal was reached because
1252              // these are orphan blocks anyway, so let's leverage this run of freeSpace
1253              // to get rid of all orphans at once.
1254              bytesFreed += entry.getLength();
1255              continue;
1256            }
1257          }
1258        }
1259
1260        if (
1261          bytesFreed < bytesToFreeWithExtra && coldFiles != null
1262            && coldFiles.containsKey(bucketEntryWithKey.getKey().getHfileName())
1263        ) {
1264          int freedBlockSize = bucketEntryWithKey.getValue().getLength();
1265          if (evictBlockIfNoRpcReferenced(bucketEntryWithKey.getKey())) {
1266            bytesFreed += freedBlockSize;
1267          }
1268          continue;
1269        }
1270
1271        switch (entry.getPriority()) {
1272          case SINGLE: {
1273            bucketSingle.add(bucketEntryWithKey);
1274            break;
1275          }
1276          case MULTI: {
1277            bucketMulti.add(bucketEntryWithKey);
1278            break;
1279          }
1280          case MEMORY: {
1281            bucketMemory.add(bucketEntryWithKey);
1282            break;
1283          }
1284        }
1285      }
1286
1287      // Check if the cold file eviction is sufficient to create enough space.
1288      bytesToFreeWithExtra -= bytesFreed;
1289      if (bytesToFreeWithExtra <= 0) {
1290        LOG.debug("Bucket cache free space completed; freed space : {} bytes of cold data blocks.",
1291          StringUtils.byteDesc(bytesFreed));
1292        return;
1293      }
1294
1295      if (LOG.isDebugEnabled()) {
1296        LOG.debug(
1297          "Bucket cache free space completed; freed space : {} "
1298            + "bytes of cold data blocks. {} more bytes required to be freed.",
1299          StringUtils.byteDesc(bytesFreed), bytesToFreeWithExtra);
1300      }
1301
1302      PriorityQueue<BucketEntryGroup> bucketQueue =
1303        new PriorityQueue<>(3, Comparator.comparingLong(BucketEntryGroup::overflow));
1304
1305      bucketQueue.add(bucketSingle);
1306      bucketQueue.add(bucketMulti);
1307      bucketQueue.add(bucketMemory);
1308
1309      int remainingBuckets = bucketQueue.size();
1310      BucketEntryGroup bucketGroup;
1311      while ((bucketGroup = bucketQueue.poll()) != null) {
1312        long overflow = bucketGroup.overflow();
1313        if (overflow > 0) {
1314          long bucketBytesToFree =
1315            Math.min(overflow, (bytesToFreeWithoutExtra - bytesFreed) / remainingBuckets);
1316          bytesFreed += bucketGroup.free(bucketBytesToFree);
1317        }
1318        remainingBuckets--;
1319      }
1320
1321      // Check and free if there are buckets that still need freeing of space
1322      if (bucketSizesAboveThresholdCount(minFactor) > 0) {
1323        bucketQueue.clear();
1324        remainingBuckets = 3;
1325        bucketQueue.add(bucketSingle);
1326        bucketQueue.add(bucketMulti);
1327        bucketQueue.add(bucketMemory);
1328        while ((bucketGroup = bucketQueue.poll()) != null) {
1329          long bucketBytesToFree = (bytesToFreeWithExtra - bytesFreed) / remainingBuckets;
1330          bytesFreed += bucketGroup.free(bucketBytesToFree);
1331          remainingBuckets--;
1332        }
1333      }
1334      // Even after the above free we might still need freeing because of the
1335      // De-fragmentation of the buckets (also called Slab Calcification problem), i.e
1336      // there might be some buckets where the occupancy is very sparse and thus are not
1337      // yielding the free for the other bucket sizes, the fix for this to evict some
1338      // of the buckets, we do this by evicting the buckets that are least fulled
1339      freeEntireBuckets(DEFAULT_FREE_ENTIRE_BLOCK_FACTOR * bucketSizesAboveThresholdCount(1.0f));
1340
1341      if (LOG.isDebugEnabled()) {
1342        long single = bucketSingle.totalSize();
1343        long multi = bucketMulti.totalSize();
1344        long memory = bucketMemory.totalSize();
1345        if (LOG.isDebugEnabled()) {
1346          LOG.debug("Bucket cache free space completed; " + "freed="
1347            + StringUtils.byteDesc(bytesFreed) + ", " + "total=" + StringUtils.byteDesc(totalSize)
1348            + ", " + "single=" + StringUtils.byteDesc(single) + ", " + "multi="
1349            + StringUtils.byteDesc(multi) + ", " + "memory=" + StringUtils.byteDesc(memory));
1350        }
1351      }
1352    } catch (Throwable t) {
1353      LOG.warn("Failed freeing space", t);
1354    } finally {
1355      cacheStats.evict();
1356      freeInProgress = false;
1357      freeSpaceLock.unlock();
1358    }
1359  }
1360
1361  // This handles flushing the RAM cache to IOEngine.
1362  class WriterThread extends Thread {
1363    private final BlockingQueue<RAMQueueEntry> inputQueue;
1364    private volatile boolean writerEnabled = true;
1365    private final ByteBuffer metaBuff = ByteBuffer.allocate(HFileBlock.BLOCK_METADATA_SPACE);
1366
1367    WriterThread(BlockingQueue<RAMQueueEntry> queue) {
1368      super("BucketCacheWriterThread");
1369      this.inputQueue = queue;
1370    }
1371
1372    // Used for test
1373    void disableWriter() {
1374      this.writerEnabled = false;
1375    }
1376
1377    @Override
1378    public void run() {
1379      List<RAMQueueEntry> entries = new ArrayList<>();
1380      try {
1381        while (isCacheEnabled() && writerEnabled) {
1382          try {
1383            try {
1384              // Blocks
1385              entries = getRAMQueueEntries(inputQueue, entries);
1386            } catch (InterruptedException ie) {
1387              if (!isCacheEnabled() || !writerEnabled) {
1388                break;
1389              }
1390            }
1391            doDrain(entries, metaBuff);
1392          } catch (Exception ioe) {
1393            LOG.error("WriterThread encountered error", ioe);
1394          }
1395        }
1396      } catch (Throwable t) {
1397        LOG.warn("Failed doing drain", t);
1398      }
1399      LOG.info(this.getName() + " exiting, cacheEnabled=" + isCacheEnabled());
1400    }
1401  }
1402
1403  /**
1404   * Put the new bucket entry into backingMap. Notice that we are allowed to replace the existing
1405   * cache with a new block for the same cache key. there's a corner case: one thread cache a block
1406   * in ramCache, copy to io-engine and add a bucket entry to backingMap. Caching another new block
1407   * with the same cache key do the same thing for the same cache key, so if not evict the previous
1408   * bucket entry, then memory leak happen because the previous bucketEntry is gone but the
1409   * bucketAllocator do not free its memory.
1410   * @see BlockCacheUtil#shouldReplaceExistingCacheBlock(BlockCache blockCache,BlockCacheKey
1411   *      cacheKey, Cacheable newBlock)
1412   * @param key         Block cache key
1413   * @param bucketEntry Bucket entry to put into backingMap.
1414   */
1415  protected void putIntoBackingMap(BlockCacheKey key, BucketEntry bucketEntry) {
1416    BucketEntry previousEntry = backingMap.put(key, bucketEntry);
1417    updateRegionCachedSize(key, bucketEntry.getLength());
1418    if (previousEntry != null && previousEntry != bucketEntry) {
1419      previousEntry.withWriteLock(offsetLock, () -> {
1420        blockEvicted(key, previousEntry, false, false);
1421        return null;
1422      });
1423    }
1424    bucketEntry.withWriteLock(offsetLock, () -> {
1425      if (backingMap.get(key) == bucketEntry) {
1426        blocksByHFile.add(key);
1427      }
1428      return null;
1429    });
1430  }
1431
1432  /**
1433   * Prepare and return a warning message for Bucket Allocator Exception
1434   * @param fle The exception
1435   * @param re  The RAMQueueEntry for which the exception was thrown.
1436   * @return A warning message created from the input RAMQueueEntry object.
1437   */
1438  private static String getAllocationFailWarningMessage(final BucketAllocatorException fle,
1439    final RAMQueueEntry re) {
1440    final StringBuilder sb = new StringBuilder();
1441    sb.append("Most recent failed allocation after ");
1442    sb.append(ALLOCATION_FAIL_LOG_TIME_PERIOD);
1443    sb.append(" ms;");
1444    if (re != null) {
1445      if (re.getData() instanceof HFileBlock) {
1446        final HFileContext fileContext = ((HFileBlock) re.getData()).getHFileContext();
1447        final String columnFamily = Bytes.toString(fileContext.getColumnFamily());
1448        final String tableName = Bytes.toString(fileContext.getTableName());
1449        if (tableName != null) {
1450          sb.append(" Table: ");
1451          sb.append(tableName);
1452        }
1453        if (columnFamily != null) {
1454          sb.append(" CF: ");
1455          sb.append(columnFamily);
1456        }
1457        sb.append(" HFile: ");
1458        if (fileContext.getHFileName() != null) {
1459          sb.append(fileContext.getHFileName());
1460        } else {
1461          sb.append(re.getKey());
1462        }
1463      } else {
1464        sb.append(" HFile: ");
1465        sb.append(re.getKey());
1466      }
1467    }
1468    sb.append(" Message: ");
1469    sb.append(fle.getMessage());
1470    return sb.toString();
1471  }
1472
1473  /**
1474   * Flush the entries in ramCache to IOEngine and add bucket entry to backingMap. Process all that
1475   * are passed in even if failure being sure to remove from ramCache else we'll never undo the
1476   * references and we'll OOME.
1477   * @param entries Presumes list passed in here will be processed by this invocation only. No
1478   *                interference expected.
1479   */
1480  void doDrain(final List<RAMQueueEntry> entries, ByteBuffer metaBuff) throws InterruptedException {
1481    if (entries.isEmpty()) {
1482      return;
1483    }
1484    // This method is a little hard to follow. We run through the passed in entries and for each
1485    // successful add, we add a non-null BucketEntry to the below bucketEntries. Later we must
1486    // do cleanup making sure we've cleared ramCache of all entries regardless of whether we
1487    // successfully added the item to the bucketcache; if we don't do the cleanup, we'll OOME by
1488    // filling ramCache. We do the clean up by again running through the passed in entries
1489    // doing extra work when we find a non-null bucketEntries corresponding entry.
1490    final int size = entries.size();
1491    BucketEntry[] bucketEntries = new BucketEntry[size];
1492    // Index updated inside loop if success or if we can't succeed. We retry if cache is full
1493    // when we go to add an entry by going around the loop again without upping the index.
1494    int index = 0;
1495    while (isCacheEnabled() && index < size) {
1496      RAMQueueEntry re = null;
1497      try {
1498        re = entries.get(index);
1499        if (re == null) {
1500          LOG.warn("Couldn't get entry or changed on us; who else is messing with it?");
1501          index++;
1502          continue;
1503        }
1504        // Reset the position for reuse.
1505        // It should be guaranteed that the data in the metaBuff has been transferred to the
1506        // ioEngine safely. Otherwise, this reuse is problematic. Fortunately, the data is already
1507        // transferred with our current IOEngines. Should take care, when we have new kinds of
1508        // IOEngine in the future.
1509        metaBuff.clear();
1510        BucketEntry bucketEntry = re.writeToCache(ioEngine, bucketAllocator, realCacheSize,
1511          this::createRecycler, metaBuff, acceptableSize());
1512        // Successfully added. Up index and add bucketEntry. Clear io exceptions.
1513        bucketEntries[index] = bucketEntry;
1514        if (ioErrorStartTime > 0) {
1515          ioErrorStartTime = -1;
1516        }
1517        index++;
1518      } catch (BucketAllocatorException fle) {
1519        long currTs = EnvironmentEdgeManager.currentTime();
1520        cacheStats.allocationFailed(); // Record the warning.
1521        if (
1522          allocFailLogPrevTs == 0 || (currTs - allocFailLogPrevTs) > ALLOCATION_FAIL_LOG_TIME_PERIOD
1523        ) {
1524          LOG.warn(getAllocationFailWarningMessage(fle, re));
1525          allocFailLogPrevTs = currTs;
1526        }
1527        // Presume can't add. Too big? Move index on. Entry will be cleared from ramCache below.
1528        bucketEntries[index] = null;
1529        index++;
1530      } catch (CacheFullException cfe) {
1531        // Cache full when we tried to add. Try freeing space and then retrying (don't up index)
1532        if (!freeInProgress && !re.isPrefetch()) {
1533          freeSpace("Full!");
1534        } else if (re.isPrefetch()) {
1535          bucketEntries[index] = null;
1536          index++;
1537        } else {
1538          Thread.sleep(50);
1539        }
1540      } catch (IOException ioex) {
1541        // Hopefully transient. Retry. checkIOErrorIsTolerated disables cache if problem.
1542        LOG.error("Failed writing to bucket cache", ioex);
1543        checkIOErrorIsTolerated();
1544      }
1545    }
1546
1547    // Make sure data pages are written on media before we update maps.
1548    try {
1549      ioEngine.sync();
1550    } catch (IOException ioex) {
1551      LOG.error("Failed syncing IO engine", ioex);
1552      checkIOErrorIsTolerated();
1553      // Since we failed sync, free the blocks in bucket allocator
1554      for (int i = 0; i < entries.size(); ++i) {
1555        BucketEntry bucketEntry = bucketEntries[i];
1556        if (bucketEntry != null) {
1557          bucketAllocator.freeBlock(bucketEntry.offset(), bucketEntry.getLength());
1558          bucketEntries[i] = null;
1559        }
1560      }
1561    }
1562
1563    // Now add to backingMap if successfully added to bucket cache. Remove from ramCache if
1564    // success or error.
1565    for (int i = 0; i < size; ++i) {
1566      BlockCacheKey key = entries.get(i).getKey();
1567      // Only add if non-null entry.
1568      if (bucketEntries[i] != null) {
1569        putIntoBackingMap(key, bucketEntries[i]);
1570        if (ioEngine.isPersistent()) {
1571          setCacheInconsistent(true);
1572        }
1573      }
1574      // Always remove from ramCache even if we failed adding it to the block cache above.
1575      boolean existed = ramCache.remove(key, re -> {
1576        if (re != null) {
1577          heapSize.add(-1 * re.getData().heapSize());
1578        }
1579      });
1580      if (!existed && bucketEntries[i] != null) {
1581        // Block should have already been evicted. Remove it and free space.
1582        final BucketEntry bucketEntry = bucketEntries[i];
1583        bucketEntry.withWriteLock(offsetLock, () -> {
1584          if (backingMap.remove(key, bucketEntry)) {
1585            blockEvicted(key, bucketEntry, false, false);
1586          }
1587          return null;
1588        });
1589      }
1590      long used = bucketAllocator.getUsedSize();
1591      if (!entries.get(i).isPrefetch() && used > acceptableSize()) {
1592        LOG.debug("Calling freeSpace for block: {}", entries.get(i).getKey());
1593        freeSpace("Used=" + used + " > acceptable=" + acceptableSize());
1594      }
1595    }
1596
1597  }
1598
1599  /**
1600   * Blocks until elements available in {@code q} then tries to grab as many as possible before
1601   * returning.
1602   * @param receptacle Where to stash the elements taken from queue. We clear before we use it just
1603   *                   in case.
1604   * @param q          The queue to take from.
1605   * @return {@code receptacle} laden with elements taken from the queue or empty if none found.
1606   */
1607  static List<RAMQueueEntry> getRAMQueueEntries(BlockingQueue<RAMQueueEntry> q,
1608    List<RAMQueueEntry> receptacle) throws InterruptedException {
1609    // Clear sets all entries to null and sets size to 0. We retain allocations. Presume it
1610    // ok even if list grew to accommodate thousands.
1611    receptacle.clear();
1612    receptacle.add(q.take());
1613    q.drainTo(receptacle);
1614    return receptacle;
1615  }
1616
1617  /**
1618   * @see #retrieveFromFile(int[])
1619   */
1620  @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "OBL_UNSATISFIED_OBLIGATION",
1621      justification = "false positive, try-with-resources ensures close is called.")
1622  void persistToFile() throws IOException {
1623    persistToFile(entry -> {
1624    });
1625  }
1626
1627  private void persistToFile(Consumer<Map.Entry<BlockCacheKey, BucketEntry>> entryCopiedAction)
1628    throws IOException {
1629    LOG.debug("Thread {} started persisting bucket cache to file",
1630      Thread.currentThread().getName());
1631    if (!isCachePersistent()) {
1632      throw new IOException("Attempt to persist non-persistent cache mappings!");
1633    }
1634    File tempPersistencePath = new File(persistencePath + EnvironmentEdgeManager.currentTime());
1635    try (FileOutputStream fos = new FileOutputStream(tempPersistencePath, false)) {
1636      LOG.debug("Persist in new chunked persistence format.");
1637
1638      persistChunkedBackingMap(fos, entryCopiedAction);
1639
1640      LOG.debug(
1641        "PersistToFile: after persisting backing map size: {}, fullycachedFiles size: {},"
1642          + " file name: {}",
1643        backingMap.size(), fullyCachedFiles.size(), tempPersistencePath.getName());
1644    } catch (IOException e) {
1645      LOG.error("Failed to persist bucket cache to file", e);
1646      throw e;
1647    } catch (Throwable e) {
1648      LOG.error("Failed during persist bucket cache to file: ", e);
1649      throw e;
1650    }
1651    LOG.debug("Thread {} finished persisting bucket cache to file, renaming",
1652      Thread.currentThread().getName());
1653    if (!tempPersistencePath.renameTo(new File(persistencePath))) {
1654      LOG.warn("Failed to commit cache persistent file. We might lose cached blocks if "
1655        + "RS crashes/restarts before we successfully checkpoint again.");
1656    }
1657  }
1658
1659  public boolean isCachePersistent() {
1660    return ioEngine.isPersistent() && persistencePath != null;
1661  }
1662
1663  @Override
1664  public Optional<Map<String, Long>> getRegionCachedInfo() {
1665    return Optional.of(Collections.unmodifiableMap(regionCachedSize));
1666  }
1667
1668  /**
1669   * @see #persistToFile()
1670   */
1671  private void retrieveFromFile(int[] bucketSizes) throws IOException {
1672    LOG.info("Started retrieving bucket cache from file");
1673    File persistenceFile = new File(persistencePath);
1674    if (!persistenceFile.exists()) {
1675      LOG.warn("Persistence file missing! "
1676        + "It's ok if it's first run after enabling persistent cache.");
1677      bucketAllocator = new BucketAllocator(cacheCapacity, bucketSizes, backingMap, realCacheSize);
1678      blockNumber.add(backingMap.size());
1679      backingMapValidated.set(true);
1680      return;
1681    }
1682    assert !isCacheEnabled();
1683
1684    try (FileInputStream in = new FileInputStream(persistenceFile)) {
1685      int pblen = ProtobufMagic.lengthOfPBMagic();
1686      byte[] pbuf = new byte[pblen];
1687      IOUtils.readFully(in, pbuf, 0, pblen);
1688
1689      if (ProtobufMagic.isPBMagicPrefix(pbuf)) {
1690        LOG.info("Reading old format of persistence.");
1691        // The old non-chunked version of backing map persistence.
1692        BucketCacheProtos.BucketCacheEntry cacheEntry =
1693          BucketCacheProtos.BucketCacheEntry.parseDelimitedFrom(in);
1694        if (cacheEntry == null) {
1695          throw new IOException(
1696            "Failed to parse cache entry from persistence file: " + persistencePath);
1697        }
1698        parsePB(cacheEntry);
1699      } else if (Arrays.equals(pbuf, BucketProtoUtils.PB_MAGIC_V2)) {
1700        // The new persistence format of chunked persistence.
1701        LOG.info("Reading new chunked format of persistence.");
1702        retrieveChunkedBackingMap(in);
1703      } else {
1704        // In 3.0 we have enough flexibility to dump the old cache data.
1705        // TODO: In 2.x line, this might need to be filled in to support reading the old format
1706        throw new IOException(
1707          "Persistence file does not start with protobuf magic number. " + persistencePath);
1708      }
1709      bucketAllocator = new BucketAllocator(cacheCapacity, bucketSizes, backingMap, realCacheSize);
1710      blockNumber.add(backingMap.size());
1711      LOG.info("Bucket cache retrieved from file successfully with size: {}", backingMap.size());
1712    }
1713  }
1714
1715  private void updateRegionSizeMapWhileRetrievingFromFile() {
1716    // Update the regionCachedSize with the region size while restarting the region server
1717    if (LOG.isDebugEnabled()) {
1718      LOG.debug("Updating region size map after retrieving cached file list");
1719      dumpPrefetchList();
1720    }
1721    regionCachedSize.clear();
1722    backingMap.forEach((k, v) -> updateRegionCachedSize(k, v.getLength()));
1723  }
1724
1725  private void dumpPrefetchList() {
1726    for (Map.Entry<String, Pair<String, Long>> outerEntry : fullyCachedFiles.entrySet()) {
1727      LOG.debug("Cached File Entry:<{},<{},{}>>", outerEntry.getKey(),
1728        outerEntry.getValue().getFirst(), outerEntry.getValue().getSecond());
1729    }
1730  }
1731
1732  private void verifyCapacityAndClasses(long capacitySize, String ioclass, String mapclass)
1733    throws IOException {
1734    if (capacitySize != cacheCapacity) {
1735      throw new IOException("Mismatched cache capacity:" + StringUtils.byteDesc(capacitySize)
1736        + ", expected: " + StringUtils.byteDesc(cacheCapacity));
1737    }
1738    if (!ioEngine.getClass().getName().equals(ioclass)) {
1739      throw new IOException("Class name for IO engine mismatch: " + ioclass + ", expected:"
1740        + ioEngine.getClass().getName());
1741    }
1742    if (!backingMap.getClass().getName().equals(mapclass)) {
1743      throw new IOException("Class name for cache map mismatch: " + mapclass + ", expected:"
1744        + backingMap.getClass().getName());
1745    }
1746  }
1747
1748  private void verifyFileIntegrity(BucketCacheProtos.BucketCacheEntry proto) {
1749    try {
1750      if (proto.hasChecksum()) {
1751        ((PersistentIOEngine) ioEngine).verifyFileIntegrity(proto.getChecksum().toByteArray(),
1752          algorithm);
1753      }
1754      backingMapValidated.set(true);
1755    } catch (IOException e) {
1756      LOG.warn("Checksum for cache file failed. "
1757        + "We need to validate each cache key in the backing map. "
1758        + "This may take some time, so we'll do it in a background thread,");
1759
1760      Runnable cacheValidator = () -> {
1761        while (bucketAllocator == null) {
1762          try {
1763            Thread.sleep(50);
1764          } catch (InterruptedException ex) {
1765            throw new RuntimeException(ex);
1766          }
1767        }
1768        long startTime = EnvironmentEdgeManager.currentTime();
1769        int totalKeysOriginally = backingMap.size();
1770        for (Map.Entry<BlockCacheKey, BucketEntry> keyEntry : backingMap.entrySet()) {
1771          try {
1772            ((FileIOEngine) ioEngine).checkCacheTime(keyEntry.getValue());
1773          } catch (IOException e1) {
1774            LOG.debug("Check for key {} failed. Evicting.", keyEntry.getKey());
1775            evictBlock(keyEntry.getKey());
1776            fullyCachedFiles.remove(keyEntry.getKey().getHfileName());
1777          }
1778        }
1779        backingMapValidated.set(true);
1780        LOG.info("Finished validating {} keys in the backing map. Recovered: {}. This took {}ms.",
1781          totalKeysOriginally, backingMap.size(),
1782          (EnvironmentEdgeManager.currentTime() - startTime));
1783      };
1784      Thread t = new Thread(cacheValidator);
1785      t.setDaemon(true);
1786      t.start();
1787    }
1788  }
1789
1790  private void updateCacheIndex(BucketCacheProtos.BackingMap chunk,
1791    java.util.Map<java.lang.Integer, java.lang.String> deserializer) throws IOException {
1792    Pair<ConcurrentHashMap<BlockCacheKey, BucketEntry>, NavigableSet<BlockCacheKey>> pair2 =
1793      BucketProtoUtils.fromPB(deserializer, chunk, this::createRecycler);
1794    pair2.getFirst().forEach((k, v) -> {
1795      backingMap.put(k, v);
1796      updateRegionCachedSize(k, v.getLength());
1797    });
1798    blocksByHFile.addAll(pair2.getSecond());
1799  }
1800
1801  private void parsePB(BucketCacheProtos.BucketCacheEntry proto) throws IOException {
1802    Pair<ConcurrentHashMap<BlockCacheKey, BucketEntry>, NavigableSet<BlockCacheKey>> pair =
1803      BucketProtoUtils.fromPB(proto.getDeserializersMap(), proto.getBackingMap(),
1804        this::createRecycler);
1805    backingMap = pair.getFirst();
1806    blocksByHFile = pair.getSecond();
1807    fullyCachedFiles.clear();
1808    fullyCachedFiles.putAll(BucketProtoUtils.fromPB(proto.getCachedFilesMap()));
1809
1810    LOG.info("After retrieval Backing map size: {}, fullyCachedFiles size: {}", backingMap.size(),
1811      fullyCachedFiles.size());
1812
1813    verifyFileIntegrity(proto);
1814    updateRegionSizeMapWhileRetrievingFromFile();
1815    verifyCapacityAndClasses(proto.getCacheCapacity(), proto.getIoClass(), proto.getMapClass());
1816  }
1817
1818  private void persistChunkedBackingMap(FileOutputStream fos,
1819    Consumer<Map.Entry<BlockCacheKey, BucketEntry>> entryCopiedAction) throws IOException {
1820    LOG.debug(
1821      "persistToFile: before persisting backing map size: {}, "
1822        + "fullycachedFiles size: {}, chunkSize: {}",
1823      backingMap.size(), fullyCachedFiles.size(), persistenceChunkSize);
1824
1825    BucketProtoUtils.serializeAsPB(this, fos, persistenceChunkSize, entryCopiedAction);
1826
1827    LOG.debug(
1828      "persistToFile: after persisting backing map size: {}, " + "fullycachedFiles size: {}",
1829      backingMap.size(), fullyCachedFiles.size());
1830  }
1831
1832  private void retrieveChunkedBackingMap(FileInputStream in) throws IOException {
1833    // Read the first chunk that has all the details.
1834    BucketCacheProtos.BucketCacheEntry cacheEntry =
1835      BucketCacheProtos.BucketCacheEntry.parseDelimitedFrom(in);
1836
1837    // HBASE-29857: Handle case where persistence file is empty.
1838    // parseDelimitedFrom() returns null when there's no data to read.
1839    // Note: Corrupted files would throw InvalidProtocolBufferException (subclass of IOException).
1840    if (cacheEntry == null) {
1841      throw new IOException("Failed to read cache entry from persistence file (file is empty)");
1842    }
1843
1844    fullyCachedFiles.clear();
1845    fullyCachedFiles.putAll(BucketProtoUtils.fromPB(cacheEntry.getCachedFilesMap()));
1846
1847    backingMap.clear();
1848    blocksByHFile.clear();
1849    regionCachedSize.clear();
1850
1851    // Read the backing map entries in batches.
1852    int numChunks = 0;
1853    while (in.available() > 0) {
1854      updateCacheIndex(BucketCacheProtos.BackingMap.parseDelimitedFrom(in),
1855        cacheEntry.getDeserializersMap());
1856      numChunks++;
1857    }
1858
1859    LOG.info("Retrieved {} of chunks with blockCount = {}.", numChunks, backingMap.size());
1860    verifyFileIntegrity(cacheEntry);
1861    verifyCapacityAndClasses(cacheEntry.getCacheCapacity(), cacheEntry.getIoClass(),
1862      cacheEntry.getMapClass());
1863  }
1864
1865  /**
1866   * Check whether we tolerate IO error this time. If the duration of IOEngine throwing errors
1867   * exceeds ioErrorsDurationTimeTolerated, we will disable the cache
1868   */
1869  private void checkIOErrorIsTolerated() {
1870    long now = EnvironmentEdgeManager.currentTime();
1871    // Do a single read to a local variable to avoid timing issue - HBASE-24454
1872    long ioErrorStartTimeTmp = this.ioErrorStartTime;
1873    if (ioErrorStartTimeTmp > 0) {
1874      if (isCacheEnabled() && (now - ioErrorStartTimeTmp) > this.ioErrorsTolerationDuration) {
1875        LOG.error("IO errors duration time has exceeded " + ioErrorsTolerationDuration
1876          + "ms, disabling cache, please check your IOEngine");
1877        disableCache();
1878      }
1879    } else {
1880      this.ioErrorStartTime = now;
1881    }
1882  }
1883
1884  /**
1885   * Used to shut down the cache -or- turn it off in the case of something broken.
1886   * @return whether explicit shutdown should wait for cleanup
1887   */
1888  private synchronized boolean disableCache() {
1889    if (cacheState == CacheState.DISABLED) {
1890      return false;
1891    }
1892    boolean waitForCleanup = cacheState == CacheState.ENABLED && isCachePersistent();
1893    LOG.info("Disabling cache");
1894    cacheState = CacheState.DISABLED;
1895    this.scheduleThreadPool.shutdown();
1896    this.janitorThreadPool.shutdown();
1897    for (WriterThread writerThread : writerThreads) {
1898      writerThread.interrupt();
1899    }
1900    // Closing the IO engine helps unblock an in-flight writer before the cleanup thread joins it.
1901    // FileIOEngine can reopen a channel, so cleanup closes the engine again after writers stop.
1902    ioEngine.shutdown();
1903    if (cacheStats.getMetricsRollerScheduler() != null) {
1904      cacheStats.getMetricsRollerScheduler().shutdownNow();
1905    }
1906    cacheCleanupThread = Threads.setDaemonThreadRunning(new Thread(this::cleanupCache),
1907      "BucketCacheCleanup-" + System.identityHashCode(this), Threads.LOGGING_EXCEPTION_HANDLER);
1908    return waitForCleanup;
1909  }
1910
1911  private void cleanupCache() {
1912    try {
1913      Threads.shutdown(persistenceRetrieverThread);
1914      for (WriterThread writerThread : writerThreads) {
1915        Threads.shutdown(writerThread);
1916      }
1917      for (BlockingQueue<RAMQueueEntry> writerQueue : writerQueues) {
1918        writerQueue.clear();
1919      }
1920      ramCache.clear();
1921      if (cachePersister != null) {
1922        LOG.info("Shutting down cache persister thread.");
1923        cachePersister.shutdown();
1924        Threads.shutdown(cachePersister);
1925      }
1926      if (isCachePersistent()) {
1927        try {
1928          // The serializer already visits every entry. Release owner references in the same pass.
1929          persistToFile(this::cleanupBackingMapEntry);
1930        } catch (IOException ex) {
1931          LOG.error("Unable to persist data on exit: " + ex.toString(), ex);
1932        }
1933      }
1934    } finally {
1935      try {
1936        cleanupCacheIndex();
1937      } finally {
1938        ioEngine.shutdown();
1939      }
1940    }
1941  }
1942
1943  private void cleanupCacheIndex() {
1944    // A successful persistent cleanup emptied the map during serialization. Avoid creating a
1945    // second iterator over a large ConcurrentHashMap in that case.
1946    if (!backingMap.isEmpty()) {
1947      for (Map.Entry<BlockCacheKey, BucketEntry> entry : backingMap.entrySet()) {
1948        cleanupBackingMapEntry(entry);
1949      }
1950    }
1951    blocksByHFile.clear();
1952    fullyCachedFiles.clear();
1953    regionCachedSize.clear();
1954  }
1955
1956  private void cleanupBackingMapEntry(Map.Entry<BlockCacheKey, BucketEntry> entry) {
1957    BlockCacheKey cacheKey = entry.getKey();
1958    BucketEntry bucketEntry = entry.getValue();
1959    bucketEntry.withWriteLock(offsetLock, () -> {
1960      if (backingMap.remove(cacheKey, bucketEntry)) {
1961        bucketEntry.markAsEvicted();
1962      }
1963      return null;
1964    });
1965  }
1966
1967  private void waitForCacheCleanup() throws InterruptedException {
1968    Thread cleanupThread = cacheCleanupThread;
1969    if (cleanupThread == null || cleanupThread == Thread.currentThread()) {
1970      return;
1971    }
1972    cleanupThread.join();
1973  }
1974
1975  @Override
1976  public void shutdown() {
1977    if (disableCache()) {
1978      try {
1979        waitForCacheCleanup();
1980      } catch (InterruptedException e) {
1981        Thread.currentThread().interrupt();
1982        LOG.warn("Interrupted while waiting for bucket cache cleanup", e);
1983      }
1984    }
1985    LOG.info("Shutdown bucket cache: IO persistent=" + ioEngine.isPersistent() + "; path to write="
1986      + persistencePath);
1987  }
1988
1989  /**
1990   * Needed mostly for UTs that might run in the same VM and create different BucketCache instances
1991   * on different UT methods.
1992   */
1993  @Override
1994  protected void finalize() {
1995    if (cachePersister != null && !cachePersister.isInterrupted()) {
1996      cachePersister.interrupt();
1997    }
1998  }
1999
2000  @Override
2001  public CacheStats getStats() {
2002    return cacheStats;
2003  }
2004
2005  public BucketAllocator getAllocator() {
2006    return this.bucketAllocator;
2007  }
2008
2009  @Override
2010  public long heapSize() {
2011    return this.heapSize.sum();
2012  }
2013
2014  @Override
2015  public long size() {
2016    return this.realCacheSize.sum();
2017  }
2018
2019  @Override
2020  public long getCurrentDataSize() {
2021    return size();
2022  }
2023
2024  @Override
2025  public long getFreeSize() {
2026    if (!isCacheInitialized("BucketCache:getFreeSize")) {
2027      return 0;
2028    }
2029    return this.bucketAllocator.getFreeSize();
2030  }
2031
2032  @Override
2033  public long getBlockCount() {
2034    return this.blockNumber.sum();
2035  }
2036
2037  @Override
2038  public long getDataBlockCount() {
2039    return getBlockCount();
2040  }
2041
2042  @Override
2043  public long getCurrentSize() {
2044    if (!isCacheInitialized("BucketCache::getCurrentSize")) {
2045      return 0;
2046    }
2047    return this.bucketAllocator.getUsedSize();
2048  }
2049
2050  protected String getAlgorithm() {
2051    return algorithm;
2052  }
2053
2054  /**
2055   * Evicts all blocks for a specific HFile.
2056   * <p>
2057   * This is used for evict-on-close to remove all blocks of a specific HFile.
2058   * @return the number of blocks evicted
2059   */
2060  @Override
2061  public int evictBlocksByHfileName(String hfileName) {
2062    return evictBlocksRangeByHfileName(hfileName, 0, Long.MAX_VALUE);
2063  }
2064
2065  @Override
2066  public int evictBlocksRangeByHfileName(String hfileName, long initOffset, long endOffset) {
2067    Set<BlockCacheKey> keySet = getAllCacheKeysForFile(hfileName, initOffset, endOffset);
2068    // We need to make sure whether we are evicting all blocks for this given file. In case of
2069    // split references, we might be evicting just half of the blocks
2070    LOG.debug("found {} blocks for file {}, starting offset: {}, end offset: {}", keySet.size(),
2071      hfileName, initOffset, endOffset);
2072    return evictBlockSet(keySet);
2073  }
2074
2075  private int evictBlockSet(Set<BlockCacheKey> keySet) {
2076    int numEvicted = 0;
2077    for (BlockCacheKey key : keySet) {
2078      if (evictBlock(key)) {
2079        ++numEvicted;
2080      }
2081    }
2082    return numEvicted;
2083  }
2084
2085  private Set<BlockCacheKey> getAllCacheKeysForFile(String hfileName, long init, long end) {
2086    Set<BlockCacheKey> cacheKeys = new HashSet<>();
2087    // At this moment, Some Bucket Entries may be in the WriterThread queue, and not yet put into
2088    // the backingMap. So, when executing this method, we should check both the RAMCache and
2089    // backingMap to ensure all CacheKeys are obtained.
2090    // For more details, please refer to HBASE-29862.
2091    Set<BlockCacheKey> ramCacheKeySet = ramCache.getRamBlockCacheKeysForHFile(hfileName);
2092    for (BlockCacheKey key : ramCacheKeySet) {
2093      if (key.getOffset() >= init && key.getOffset() <= end) {
2094        cacheKeys.add(key);
2095      }
2096    }
2097
2098    // These keys are just for comparison and are short lived, so we need only file name and offset
2099    cacheKeys.addAll(blocksByHFile.subSet(new BlockCacheKey(hfileName, init), true,
2100      new BlockCacheKey(hfileName, end), true));
2101    return cacheKeys;
2102  }
2103
2104  /**
2105   * Used to group bucket entries into priority buckets. There will be a BucketEntryGroup for each
2106   * priority (single, multi, memory). Once bucketed, the eviction algorithm takes the appropriate
2107   * number of elements out of each according to configuration parameters and their relative sizes.
2108   */
2109  private class BucketEntryGroup {
2110
2111    private CachedEntryQueue queue;
2112    private long totalSize = 0;
2113    private long bucketSize;
2114
2115    public BucketEntryGroup(long bytesToFree, long blockSize, long bucketSize) {
2116      this.bucketSize = bucketSize;
2117      queue = new CachedEntryQueue(bytesToFree, blockSize);
2118      totalSize = 0;
2119    }
2120
2121    public void add(Map.Entry<BlockCacheKey, BucketEntry> block) {
2122      totalSize += block.getValue().getLength();
2123      queue.add(block);
2124    }
2125
2126    public long free(long toFree) {
2127      Map.Entry<BlockCacheKey, BucketEntry> entry;
2128      long freedBytes = 0;
2129      // TODO avoid a cycling siutation. We find no block which is not in use and so no way to free
2130      // What to do then? Caching attempt fail? Need some changes in cacheBlock API?
2131      while ((entry = queue.pollLast()) != null) {
2132        BlockCacheKey blockCacheKey = entry.getKey();
2133        BucketEntry be = entry.getValue();
2134        if (evictBucketEntryIfNoRpcReferenced(blockCacheKey, be)) {
2135          freedBytes += be.getLength();
2136        }
2137        if (freedBytes >= toFree) {
2138          return freedBytes;
2139        }
2140      }
2141      return freedBytes;
2142    }
2143
2144    public long overflow() {
2145      return totalSize - bucketSize;
2146    }
2147
2148    public long totalSize() {
2149      return totalSize;
2150    }
2151  }
2152
2153  /**
2154   * Block Entry stored in the memory with key,data and so on
2155   */
2156  static class RAMQueueEntry {
2157    private final BlockCacheKey key;
2158    private final Cacheable data;
2159    private long accessCounter;
2160    private boolean inMemory;
2161    private boolean isCachePersistent;
2162
2163    private boolean isPrefetch;
2164
2165    RAMQueueEntry(BlockCacheKey bck, Cacheable data, long accessCounter, boolean inMemory,
2166      boolean isCachePersistent, boolean isPrefetch) {
2167      this.key = bck;
2168      this.data = data;
2169      this.accessCounter = accessCounter;
2170      this.inMemory = inMemory;
2171      this.isCachePersistent = isCachePersistent;
2172      this.isPrefetch = isPrefetch;
2173    }
2174
2175    public Cacheable getData() {
2176      return data;
2177    }
2178
2179    public BlockCacheKey getKey() {
2180      return key;
2181    }
2182
2183    public boolean isPrefetch() {
2184      return isPrefetch;
2185    }
2186
2187    public void access(long accessCounter) {
2188      this.accessCounter = accessCounter;
2189    }
2190
2191    private ByteBuffAllocator getByteBuffAllocator() {
2192      if (data instanceof HFileBlock) {
2193        return ((HFileBlock) data).getByteBuffAllocator();
2194      }
2195      return ByteBuffAllocator.HEAP;
2196    }
2197
2198    public BucketEntry writeToCache(final IOEngine ioEngine, final BucketAllocator alloc,
2199      final LongAdder realCacheSize, Function<BucketEntry, Recycler> createRecycler,
2200      ByteBuffer metaBuff, final Long acceptableSize) throws IOException {
2201      int len = data.getSerializedLength();
2202      // This cacheable thing can't be serialized
2203      if (len == 0) {
2204        return null;
2205      }
2206      if (isCachePersistent && data instanceof HFileBlock) {
2207        len += Long.BYTES; // we need to record the cache time for consistency check in case of
2208                           // recovery
2209      }
2210      long offset = alloc.allocateBlock(len);
2211      // In the case of prefetch, we want to avoid freeSpace runs when the cache is full.
2212      // this makes the cache allocation more predictable, and is particularly important
2213      // when persistent cache is enabled, as it won't trigger evictions of the recovered blocks,
2214      // which are likely the most accessed and relevant blocks in the cache.
2215      if (isPrefetch() && alloc.getUsedSize() > acceptableSize) {
2216        alloc.freeBlock(offset, len);
2217        return null;
2218      }
2219      boolean succ = false;
2220      BucketEntry bucketEntry = null;
2221      try {
2222        int diskSizeWithHeader = (data instanceof HFileBlock)
2223          ? ((HFileBlock) data).getOnDiskSizeWithHeader()
2224          : data.getSerializedLength();
2225        bucketEntry = new BucketEntry(offset, len, diskSizeWithHeader, accessCounter, inMemory,
2226          createRecycler, getByteBuffAllocator());
2227        bucketEntry.setDeserializerReference(data.getDeserializer());
2228        if (data instanceof HFileBlock) {
2229          // If an instance of HFileBlock, save on some allocations.
2230          HFileBlock block = (HFileBlock) data;
2231          ByteBuff sliceBuf = block.getBufferReadOnly();
2232          block.getMetaData(metaBuff);
2233          // adds the cache time prior to the block and metadata part
2234          if (isCachePersistent) {
2235            ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
2236            buffer.putLong(bucketEntry.getCachedTime());
2237            buffer.rewind();
2238            ioEngine.write(buffer, offset);
2239            ioEngine.write(sliceBuf, (offset + Long.BYTES));
2240          } else {
2241            ioEngine.write(sliceBuf, offset);
2242          }
2243          ioEngine.write(metaBuff, offset + len - metaBuff.limit());
2244        } else {
2245          // Only used for testing.
2246          ByteBuffer bb = ByteBuffer.allocate(len);
2247          data.serialize(bb, true);
2248          ioEngine.write(bb, offset);
2249        }
2250        succ = true;
2251      } finally {
2252        if (!succ) {
2253          alloc.freeBlock(offset, len);
2254        }
2255      }
2256      realCacheSize.add(len);
2257      return bucketEntry;
2258    }
2259  }
2260
2261  /**
2262   * Only used in test
2263   */
2264  void stopWriterThreads() throws InterruptedException {
2265    for (WriterThread writerThread : writerThreads) {
2266      writerThread.disableWriter();
2267      writerThread.interrupt();
2268      writerThread.join();
2269    }
2270  }
2271
2272  @Override
2273  public Iterator<CachedBlock> iterator() {
2274    // Don't bother with ramcache since stuff is in here only a little while.
2275    final Iterator<Map.Entry<BlockCacheKey, BucketEntry>> i = this.backingMap.entrySet().iterator();
2276    return new Iterator<CachedBlock>() {
2277      private final long now = System.nanoTime();
2278
2279      @Override
2280      public boolean hasNext() {
2281        return i.hasNext();
2282      }
2283
2284      @Override
2285      public CachedBlock next() {
2286        final Map.Entry<BlockCacheKey, BucketEntry> e = i.next();
2287        return new CachedBlock() {
2288          @Override
2289          public String toString() {
2290            return BlockCacheUtil.toString(this, now);
2291          }
2292
2293          @Override
2294          public BlockPriority getBlockPriority() {
2295            return e.getValue().getPriority();
2296          }
2297
2298          @Override
2299          public BlockType getBlockType() {
2300            // Not held by BucketEntry. Could add it if wanted on BucketEntry creation.
2301            return null;
2302          }
2303
2304          @Override
2305          public long getOffset() {
2306            return e.getKey().getOffset();
2307          }
2308
2309          @Override
2310          public long getSize() {
2311            return e.getValue().getLength();
2312          }
2313
2314          @Override
2315          public long getCachedTime() {
2316            return e.getValue().getCachedTime();
2317          }
2318
2319          @Override
2320          public String getFilename() {
2321            return e.getKey().getHfileName();
2322          }
2323
2324          @Override
2325          public int compareTo(CachedBlock other) {
2326            int diff = this.getFilename().compareTo(other.getFilename());
2327            if (diff != 0) return diff;
2328
2329            diff = Long.compare(this.getOffset(), other.getOffset());
2330            if (diff != 0) return diff;
2331            if (other.getCachedTime() < 0 || this.getCachedTime() < 0) {
2332              throw new IllegalStateException(
2333                "" + this.getCachedTime() + ", " + other.getCachedTime());
2334            }
2335            return Long.compare(other.getCachedTime(), this.getCachedTime());
2336          }
2337
2338          @Override
2339          public int hashCode() {
2340            return e.getKey().hashCode();
2341          }
2342
2343          @Override
2344          public boolean equals(Object obj) {
2345            if (obj instanceof CachedBlock) {
2346              CachedBlock cb = (CachedBlock) obj;
2347              return compareTo(cb) == 0;
2348            } else {
2349              return false;
2350            }
2351          }
2352        };
2353      }
2354
2355      @Override
2356      public void remove() {
2357        throw new UnsupportedOperationException();
2358      }
2359    };
2360  }
2361
2362  @Override
2363  public BlockCache[] getBlockCaches() {
2364    return null;
2365  }
2366
2367  public int getRpcRefCount(BlockCacheKey cacheKey) {
2368    BucketEntry bucketEntry = backingMap.get(cacheKey);
2369    if (bucketEntry != null) {
2370      return bucketEntry.refCnt() - (bucketEntry.markedAsEvicted.get() ? 0 : 1);
2371    }
2372    return 0;
2373  }
2374
2375  float getAcceptableFactor() {
2376    return acceptableFactor;
2377  }
2378
2379  float getMinFactor() {
2380    return minFactor;
2381  }
2382
2383  float getExtraFreeFactor() {
2384    return extraFreeFactor;
2385  }
2386
2387  float getSingleFactor() {
2388    return singleFactor;
2389  }
2390
2391  float getMultiFactor() {
2392    return multiFactor;
2393  }
2394
2395  float getMemoryFactor() {
2396    return memoryFactor;
2397  }
2398
2399  long getQueueAdditionWaitTime() {
2400    return queueAdditionWaitTime;
2401  }
2402
2403  long getPersistenceChunkSize() {
2404    return persistenceChunkSize;
2405  }
2406
2407  long getBucketcachePersistInterval() {
2408    return bucketcachePersistInterval;
2409  }
2410
2411  public String getPersistencePath() {
2412    return persistencePath;
2413  }
2414
2415  /**
2416   * Wrapped the delegate ConcurrentMap with maintaining its block's reference count.
2417   */
2418  static class RAMCache {
2419    /**
2420     * Defined the map as {@link ConcurrentHashMap} explicitly here, because in
2421     * {@link RAMCache#get(BlockCacheKey)} and
2422     * {@link RAMCache#putIfAbsent(BlockCacheKey, BucketCache.RAMQueueEntry)} , we need to guarantee
2423     * the atomicity of map#computeIfPresent(key, func) and map#putIfAbsent(key, func). Besides, the
2424     * func method can execute exactly once only when the key is present(or absent) and under the
2425     * lock context. Otherwise, the reference count of block will be messed up. Notice that the
2426     * {@link java.util.concurrent.ConcurrentSkipListMap} can not guarantee that.
2427     */
2428    final ConcurrentHashMap<BlockCacheKey, RAMQueueEntry> delegate = new ConcurrentHashMap<>();
2429
2430    public boolean containsKey(BlockCacheKey key) {
2431      return delegate.containsKey(key);
2432    }
2433
2434    public RAMQueueEntry get(BlockCacheKey key) {
2435      return delegate.computeIfPresent(key, (k, re) -> {
2436        // It'll be referenced by RPC, so retain atomically here. if the get and retain is not
2437        // atomic, another thread may remove and release the block, when retaining in this thread we
2438        // may retain a block with refCnt=0 which is disallowed. (see HBASE-22422)
2439        re.getData().retain();
2440        return re;
2441      });
2442    }
2443
2444    /**
2445     * Return the previous associated value, or null if absent. It has the same meaning as
2446     * {@link ConcurrentMap#putIfAbsent(Object, Object)}
2447     */
2448    public RAMQueueEntry putIfAbsent(BlockCacheKey key, RAMQueueEntry entry) {
2449      AtomicBoolean absent = new AtomicBoolean(false);
2450      RAMQueueEntry re = delegate.computeIfAbsent(key, k -> {
2451        // The RAMCache reference to this entry, so reference count should be increment.
2452        entry.getData().retain();
2453        absent.set(true);
2454        return entry;
2455      });
2456      return absent.get() ? null : re;
2457    }
2458
2459    public boolean remove(BlockCacheKey key) {
2460      return remove(key, re -> {
2461      });
2462    }
2463
2464    /**
2465     * Defined an {@link Consumer} here, because once the removed entry release its reference count,
2466     * then it's ByteBuffers may be recycled and accessing it outside this method will be thrown an
2467     * exception. the consumer will access entry to remove before release its reference count.
2468     * Notice, don't change its reference count in the {@link Consumer}
2469     */
2470    public boolean remove(BlockCacheKey key, Consumer<RAMQueueEntry> action) {
2471      RAMQueueEntry previous = delegate.remove(key);
2472      action.accept(previous);
2473      if (previous != null) {
2474        previous.getData().release();
2475      }
2476      return previous != null;
2477    }
2478
2479    public boolean isEmpty() {
2480      return delegate.isEmpty();
2481    }
2482
2483    public void clear() {
2484      Iterator<Map.Entry<BlockCacheKey, RAMQueueEntry>> it = delegate.entrySet().iterator();
2485      while (it.hasNext()) {
2486        RAMQueueEntry re = it.next().getValue();
2487        it.remove();
2488        re.getData().release();
2489      }
2490    }
2491
2492    public boolean hasBlocksForFile(String fileName) {
2493      return delegate.keySet().stream().filter(key -> key.getHfileName().equals(fileName))
2494        .findFirst().isPresent();
2495    }
2496
2497    public Set<BlockCacheKey> getRamBlockCacheKeysForHFile(String fileName) {
2498      Set<BlockCacheKey> ramCacheKeySet = new HashSet<>();
2499      for (BlockCacheKey blockCacheKey : delegate.keySet()) {
2500        if (blockCacheKey.getHfileName().equals(fileName)) {
2501          ramCacheKeySet.add(blockCacheKey);
2502        }
2503      }
2504      return ramCacheKeySet;
2505    }
2506  }
2507
2508  public Map<BlockCacheKey, BucketEntry> getBackingMap() {
2509    return backingMap;
2510  }
2511
2512  public AtomicBoolean getBackingMapValidated() {
2513    return backingMapValidated;
2514  }
2515
2516  @Override
2517  public Optional<Map<String, Pair<String, Long>>> getFullyCachedFiles() {
2518    return Optional.of(fullyCachedFiles);
2519  }
2520
2521  public static Optional<BucketCache> getBucketCacheFromCacheConfig(CacheConfig cacheConf) {
2522    if (cacheConf.getBlockCache().isPresent()) {
2523      BlockCache bc = cacheConf.getBlockCache().get();
2524      if (bc instanceof CombinedBlockCache) {
2525        BlockCache l2 = ((CombinedBlockCache) bc).getSecondLevelCache();
2526        if (l2 instanceof BucketCache) {
2527          return Optional.of((BucketCache) l2);
2528        }
2529      } else if (bc instanceof BucketCache) {
2530        return Optional.of((BucketCache) bc);
2531      }
2532    }
2533    return Optional.empty();
2534  }
2535
2536  private int countBlocksForFile(Path fileName, List<ReentrantReadWriteLock> locks) {
2537    LOG.debug("iterating over {} entries in the backing map", backingMap.size());
2538    Set<BlockCacheKey> result = getAllCacheKeysForFile(fileName.getName(), 0, Long.MAX_VALUE);
2539    if (result.isEmpty() && StoreFileInfo.isReference(fileName)) {
2540      result = getAllCacheKeysForFile(
2541        StoreFileInfo.getReferredToRegionAndFile(fileName.getName()).getSecond(), 0,
2542        Long.MAX_VALUE);
2543    }
2544    int count = 0;
2545    for (BlockCacheKey entry : result) {
2546      LOG.debug("found block for file {} in the backing map. Acquiring read lock for offset {}",
2547        fileName.getName(), entry.getOffset());
2548      ReentrantReadWriteLock lock = offsetLock.getLock(entry.getOffset());
2549      lock.readLock().lock();
2550      locks.add(lock);
2551      if (backingMap.containsKey(entry) && entry.getBlockType().isData()) {
2552        count++;
2553      }
2554    }
2555    return count;
2556  }
2557
2558  private void releaseAllLocks(List<ReentrantReadWriteLock> locks) {
2559    for (ReentrantReadWriteLock lock : locks) {
2560      lock.readLock().unlock();
2561    }
2562  }
2563
2564  @Override
2565  public void notifyFileCachingCompleted(Path fileName, int totalBlockCount, int dataBlockCount,
2566    long size) {
2567    // block eviction may be happening in the background as prefetch runs,
2568    // so we need to count all blocks for this file in the backing map under
2569    // a read lock for the block offset
2570    final List<ReentrantReadWriteLock> locks = new ArrayList<>();
2571    LOG.debug("Notifying caching completed for file {}, with total blocks {}, and data blocks {}",
2572      fileName, totalBlockCount, dataBlockCount);
2573    try {
2574      boolean lastTry = false;
2575      for (;;) {
2576        int count = countBlocksForFile(fileName, locks);
2577        // BucketCache would only have data blocks
2578        if (dataBlockCount == count) {
2579          LOG.debug("File {} has now been fully cached.", fileName);
2580          fileCacheCompleted(fileName, size);
2581          break;
2582        }
2583        if (lastTry) {
2584          LOG.info(
2585            "The total block count was {}. We found only {} data blocks cached from "
2586              + "a total of {} data blocks for file {}, "
2587              + "but no blocks pending caching. Maybe cache is full or evictions "
2588              + "happened concurrently to cache prefetch.",
2589            totalBlockCount, count, dataBlockCount, fileName);
2590          break;
2591        }
2592        if (ramCache.hasBlocksForFile(fileName.getName())) {
2593          releaseAllLocks(locks);
2594          locks.clear();
2595          LOG.debug("There are still blocks pending caching for file {}. Will sleep 100ms "
2596            + "and try the verification again.", fileName);
2597          Thread.sleep(100);
2598        } else {
2599          // there are no pending blocks, so count for the last time, if we still can not get enough
2600          // data blocks, quit
2601          LOG.debug("There are no blocks pending cache for file {}. Will try the verification "
2602            + "for the last time.");
2603          lastTry = true;
2604        }
2605      }
2606    } catch (InterruptedException e) {
2607      throw new RuntimeException(e);
2608    } finally {
2609      releaseAllLocks(locks);
2610    }
2611  }
2612
2613  @Override
2614  public Optional<Boolean> blockFitsIntoTheCache(HFileBlock block) {
2615    if (!isCacheInitialized("blockFitsIntoTheCache")) {
2616      return Optional.of(false);
2617    }
2618
2619    long currentUsed = bucketAllocator.getUsedSize();
2620    boolean result = (currentUsed + block.getOnDiskSizeWithHeader()) < acceptableSize();
2621    return Optional.of(result);
2622  }
2623
2624  @Override
2625  public Optional<Boolean> shouldCacheFile(HFileInfo hFileInfo, Configuration conf) {
2626    String fileName = hFileInfo.getHFileContext().getHFileName();
2627    DataTieringManager dataTieringManager = DataTieringManager.getInstance();
2628    if (dataTieringManager != null && !dataTieringManager.isHotData(hFileInfo, conf)) {
2629      LOG.debug("Custom tiering is enabled for file: '{}' and it is not hot data", fileName);
2630      // If custom tiering has been just enabled for a file that was cached, we now need
2631      // to evict it.
2632      Set<BlockCacheKey> keySet =
2633        getAllCacheKeysForFile(hFileInfo.getHFileContext().getHFileName(), 0, Long.MAX_VALUE);
2634      int evictedBlocks = evictBlockSet(keySet);
2635      if (evictedBlocks > 0) {
2636        LOG.debug(
2637          "Evicted {} blocks for file {} as it is now considered cold by DataTieringManager",
2638          evictedBlocks, fileName);
2639      }
2640      return Optional.of(false);
2641    }
2642    // if we don't have the file in fullyCachedFiles, we should cache it
2643    return Optional.of(!fullyCachedFiles.containsKey(fileName));
2644  }
2645
2646  @Override
2647  public Optional<Boolean> shouldCacheBlock(BlockCacheKey key, long maxTimestamp,
2648    Configuration conf) {
2649    DataTieringManager dataTieringManager = DataTieringManager.getInstance();
2650    if (dataTieringManager != null && !dataTieringManager.isHotData(maxTimestamp, conf)) {
2651      LOG.debug("Data tiering is enabled for file: '{}' and it is not hot data",
2652        key.getHfileName());
2653      return Optional.of(false);
2654    }
2655    return Optional.of(true);
2656  }
2657
2658  @Override
2659  public Optional<Boolean> isAlreadyCached(BlockCacheKey key) {
2660    boolean foundKey = backingMap.containsKey(key);
2661    // if there's no entry for the key itself, we need to check if this key is for a reference,
2662    // and if so, look for a block from the referenced file using this getBlockForReference method.
2663    return Optional.of(foundKey ? true : getBlockForReference(key) != null);
2664  }
2665
2666  @Override
2667  public Optional<Integer> getBlockSize(BlockCacheKey key) {
2668    BucketEntry entry = backingMap.get(key);
2669    if (entry == null) {
2670      // the key might be for a reference tha we had found the block from the referenced file in
2671      // the cache when we first tried to cache it.
2672      entry = getBlockForReference(key);
2673      return entry == null ? Optional.empty() : Optional.of(entry.getOnDiskSizeWithHeader());
2674    } else {
2675      return Optional.of(entry.getOnDiskSizeWithHeader());
2676    }
2677
2678  }
2679
2680  boolean isCacheInitialized(String api) {
2681    if (cacheState == CacheState.INITIALIZING) {
2682      LOG.warn("Bucket initialisation pending at {}", api);
2683      return false;
2684    }
2685    return true;
2686  }
2687
2688  @Override
2689  public boolean waitForCacheInitialization(long timeout) {
2690    while (cacheState == CacheState.INITIALIZING) {
2691      if (timeout <= 0) {
2692        break;
2693      }
2694      try {
2695        Thread.sleep(100);
2696      } catch (InterruptedException e) {
2697        LOG.warn("Interrupted while waiting for cache initialization", e);
2698        Thread.currentThread().interrupt();
2699        break;
2700      }
2701      timeout -= 100;
2702    }
2703    return isCacheEnabled();
2704  }
2705}