HBase BlockCache：LRU Cache

BlockCache 的内存使用：灵活的二级缓存（L1+L2）架构

HBase 提供了两种主要的 BlockCache 实现：

在现代 HBase 版本（2.0+）中，当启用 BucketCache 时，通常会采用一种名为 CombinedBlockCache 的组合模式：

• 堆内 LruBlockCache (L1 Cache): 作为一级缓存，更多是为了缓存元数据块（META blocks），如 HFile 的索引块（INDEX blocks）和布隆过滤器块（BLOOM blocks）。这些块通常较小且访问频繁，放在堆内可以获得极低的访问延迟。
• 堆外 BucketCache (L2 Cache): 作为二级缓存，专门缓存数据块（DATA blocks）。数据块通常很大，构成了缓存的主体。将它们放在堆外可以缓存巨大的数据量（几十上百GB）而完全不增加 JVM 的 GC 压力，从而避免了因缓存过大导致的长时间 GC 停顿。

从文档片段中也能印证这一点：

src/main/asciidoc/_chapters/architecture.adoc:973-998 

…when BucketCache is enabled, all DATA blocks are kept in the BucketCache tier and meta blocks — INDEX and BLOOM blocks — are on-heap in the LruBlockCache.

为什么HBase 没有使用哈希双链表实现LRU

LruBlockCache 没有使用 常见的“哈希表 + 双向链表”来实现 LRU。这背后其实是 HBase 针对其特定场景做出的性能权衡和设计选择。

简单来说，原因主要有以下几点：

复杂的分区和优先级策略

从 evict() 方法的实现中我们可以看到，HBase 的 LruBlockCache 并不是一个单一的 LRU 队列。它将缓存的 Block 分为三个不同的优先级桶（Bucket）：

• bucketSingle: 存放只被访问过一次的 Block。
• bucketMulti: 存放被多次访问的 Block。
• bucketMemory: 存放需要常驻内存的 Block（例如元数据、索引等高优先级数据）。

// … existing code …
// Instantiate priority buckets
BlockBucket bucketSingle = new BlockBucket("single", bytesToFree, blockSize, singleSize());
BlockBucket bucketMulti = new BlockBucket("multi", bytesToFree, blockSize, multiSize());
BlockBucket bucketMemory = new BlockBucket("memory", bytesToFree, blockSize, memorySize());

// Scan entire map putting into appropriate buckets
for (LruCachedBlock cachedBlock : map.values()) {
switch (cachedBlock.getPriority()) {
case SINGLE: {
bucketSingle.add(cachedBlock);
break;
}
case MULTI: {
bucketMulti.add(cachedBlock);
break;
}
case MEMORY: {
bucketMemory.add(cachedBlock);
break;
}
}
}
// … existing code …

驱逐数据时，它的逻辑也比简单的“淘汰最久未使用的”复杂得多。它会根据每个桶的配置大小（singleFactor, multiFactor, memoryFactor）和当前实际大小计算出“溢出”量，然后按比例从不同的桶中淘汰数据。

如果使用双向链表，就需要维护三个独立的链表，并且在 Block 的优先级发生变化时（例如，一个 SINGLE 访问的 Block 被再次访问，需要升级到 MULTI），需要在不同链表之间移动节点，这会增加并发控制的复杂性。

优化并发读写，简化锁竞争

HBase 是一个高并发的分布式数据库，它的 BlockCache 会被大量的读写线程同时访问。设计上必须优先保证 getBlock()（读缓存）和 cacheBlock()（写缓存）的性能。

• 读操作 (getBlock)：在 LruBlockCache 中，一次缓存命中（hit）的操作非常快。它通过 ConcurrentHashMap.computeIfPresent 来实现，这在很大程度上是无锁的。命中后，仅仅是调用 cb.access() 更新一下访问时间和计数器，这个操作也是轻量级的，不涉及复杂的数据结构修改（如链表指针的移动）。

• 写操作 (cacheBlock)：主要是向 ConcurrentHashMap 中 put 一个元素。

如果使用传统的哈希双向链表，每次访问（getBlock）都需要移动节点到链表头部，这个操作需要对链表进行写操作，必须加锁来保证线程安全，这在高并发场景下会成为严重的性能瓶颈。

LruBlockCache 的设计做了一个非常明确的取舍：将复杂性和性能开销从高频的读操作转移到了相对低频的驱逐操作上。

evict() 方法在执行时会获取一个全局的 evictionLock，此时整个驱逐过程是串行执行的。通过遍历 map 的所有 values() 来实时构建各个驱逐桶和优先级队列，虽然这个操作是 O(N) 的，但它避免了在每次读缓存时都进行加锁的链表操作。对于一个设计良好、命中率高的缓存来说，这种“读快，驱逐慢”的设计是完全值得的。

总结

LruBlockCache 不使用哈希双向链表，是因为：

这种设计是典型的在特定业务场景下对通用数据结构进行权衡和优化的范例。

为什么Caffeine 使用哈希和双链表 实现多队列

Caffeine  通过多个队列和复杂的算法（W-TinyLFU）在维持 O(1) 复杂度的同时，实现了比传统 LRU 更高的命中率。

那么，为什么 HBase 的 LruBlockCache 没有采用类似 Caffeine 的“多队列（双向链表）”设计，而是选择了“驱逐时遍历建堆”这种看起来更“笨重”的方式呢？

Caffeine 通过多指针构建了一个图，重复利用了节点

这主要是由历史原因、设计演进和特定场景下的性能权衡共同决定的。

LruBlockCache 是 HBase 中一个相当“元老”级别的组件。在它被设计和实现的年代（远早于 Caffeine 的出现），面临的主要痛点是如何在高并发下减少锁竞争。

• 传统“哈希+双向链表”的问题：正如我们讨论的，每次 get 操作都需要移动链表节点，这意味着高频的读操作需要加锁，这在 HBase 的高并发场景下是不可接受的。
• HBase 的选择：LruBlockCache 的设计者做出了一个非常务实的权衡——牺牲低频的驱逐操作的性能，来换取高频的读操作的极致性能。读操作几乎无锁，而驱逐操作则通过一个全局锁 evictionLock 来保证线程安全，虽然驱逐时 O(N) 的遍历开销很大，但只要驱逐不是一个持续发生的操作，这个开销就可以被接受。

Caffeine 的复杂性 vs. LruBlockCache 的专用性

Caffeine 是一个通用的、顶级的本地缓存库，它的 W-TinyLFU 算法非常复杂，需要精确地管理多个队列、频率草图（Frequency Sketch）等，以达到近似最优的缓存效果。

而 LruBlockCache 的目标则更专一：为 HFile 的 Block 服务。它的三级优先级设计（SINGLE, MULTI, MEMORY）是为 HBase 的特定工作负载量身定做的：

• SINGLE：抵御扫描（Scan）操作对缓存的污染。一次扫描会读入大量数据块，但这些块很可能之后不再被访问，将它们放在最低优先级可以被快速淘汰。
• MULTI：保护被多次访问的热点数据。
• MEMORY：保护元数据等常驻内存的重要数据。

这种简单的三级分类虽然不如 Caffeine 精细，但对于 HBase 的场景来说，足够有效且实现简单、逻辑清晰、易于调试。

HBase 已经拥抱了 Caffeine

HBase 后来引入了基于 Caffeine 的缓存实现！

为了提供更优的缓存性能，HBase 社区开发了 TinyLfuBlockCache。这个类其实就是对 Caffeine Cache 的一个封装和适配，使其能够无缝地在 HBase 中使用。

可以在 HBase 的配置中，通过 hfile.block.cache.policy 来选择使用哪种缓存策略。

hbase-default.xml

<property>
<name>hfile.block.cache.policy</name>
<value>LRU</value> <!– 默认是 LruBlockCache –>
<!– 你可以将其修改为 TinyLFU 来启用基于 Caffeine 的缓存 –>
<!– <value>TinyLFU</value> –>
</property>

之所以不直接用 TinyLfuBlockCache (Caffeine) 替换掉 LruBlockCache，而是作为一种可选项，主要有以下考虑：

• 稳定性与兼容性：LruBlockCache 经过了十多年的大规模生产环境验证，其稳定性和行为是众所周知的。直接替换核心组件风险很高。
• 提供选择：让用户可以根据自己的业务负载和对性能的要求来选择最合适的缓存策略。对于某些特定场景，简单的 LRU 可能已经足够，甚至行为更可预测。

总结

可以这样理解：

• LruBlockCache 是 HBase 的 “经典款” 。它采用了一种务实的设计，通过牺牲驱逐性能来保证高并发读的性能，并且其简单的三级优先级策略对于 HFile Block 缓存这个特定场景是长期有效的。
• Caffeine (TinyLfuBlockCache) 是 HBase 引入的 “性能款” 。它利用了现代缓存研究的最新成果，提供了更高的缓存命中率和整体性能，是追求极致性能用户的首选。

所以，HBase 并非没有看到更优的方案，而是通过“插件化”的方式，在保证系统稳定性的前提下，优雅地集成了更现代、更高效的设计。

LruCachedBlock 

LruCachedBlock 是 Apache HBase 中 LRU (Least Recently Used, 最近最少使用) 缓存策略的核心实现之一。它代表了 LruBlockCache 中的一个缓存条目。我们可以从它的定义、成员变量、构造函数和关键方法等方面来深入理解其设计和作用。

@InterfaceAudience.Private
public class LruCachedBlock implements HeapSize, Comparable<LruCachedBlock> {
//…
}

• @InterfaceAudience.Private: 这个注解表明该类是 HBase 内部使用的私有 API，不建议外部应用直接依赖它，因为它的接口可能会在不同版本间发生变化。
• implements HeapSize: 这个接口意味着 LruCachedBlock 的实例能够报告它在 JVM 堆内存中所占用的空间大小。这对于缓存系统来说至关重要，因为缓存需要精确地知道每个缓存项占用的内存，从而控制总内存使用量，并在达到上限时触发淘汰机制。

  // … existing code …
  public interface HeapSize {
  /**
  * Return the approximate 'exclusive deep size' of implementing object. Includes count of payload
  * and hosting object sizings.
  */
  long heapSize();
  }

• implements Comparable<LruCachedBlock>: 这个接口表明 LruCachedBlock 的实例之间可以进行比较。这是实现 LRU 淘汰策略的基础。通过比较，可以确定哪些块是“最久未被使用”的，从而在缓存满时优先淘汰它们。

核心成员变量

LruCachedBlock 封装了作为一个缓存条目所需的所有信息。

// … existing code …
public final static long PER_BLOCK_OVERHEAD =
ClassSize.align(ClassSize.OBJECT + (3 * ClassSize.REFERENCE) + (3 * Bytes.SIZEOF_LONG)
+ ClassSize.STRING + ClassSize.BYTE_BUFFER);

private final BlockCacheKey cacheKey;
private final Cacheable buf;
private volatile long accessTime;
private long size;
private BlockPriority priority;
/**
* Time this block was cached. Presumes we are created just before we are added to the cache.
*/
private final long cachedTime = System.nanoTime();
// … existing code …

• PER_BLOCK_OVERHEAD: 这是一个静态常量，用于估算一个 LruCachedBlock 对象自身的固定开销。它通过 ClassSize 工具类计算得出，包括了对象头、3个引用（cacheKey, buf, priority）、3个long类型（accessTime, size, cachedTime）以及其他一些基础对象的开销。这个值在计算总的 heapSize 时会用到，以确保内存统计的准确性。
• cacheKey (BlockCacheKey): 缓存块的唯一标识。通常由 HFile 的文件名和块在文件中的偏移量（offset）组成。缓存系统通过这个 key 来查找、存储和删除块。
• buf (Cacheable): 实际缓存的数据。Cacheable 是一个接口，通常的实现是 HFileBlock，它封装了从 HFile 中读取的字节数据。
• accessTime (volatile long): 块的最后访问时间。这里的“时间”实际上是一个单调递增的序列号（由 LruBlockCache 中的一个 AtomicLong 计数器生成）。每次块被访问时，这个值都会被更新。volatile 关键字确保了多线程之间的可见性，因为缓存的读写是高并发的。这个字段是 compareTo 方法的核心，直接决定了淘汰顺序。
• size (long): 该缓存块的总堆内存占用，在构造函数中计算得出。它等于 cacheKey 的大小 + buf 的大小 + PER_BLOCK_OVERHEAD。
• priority (BlockPriority): 块的优先级。HBase 的 LRU 缓存实现了一种带优先级的淘汰策略，分为三级：
  • SINGLE: 单次访问。新缓存进来的块默认为这个优先级。
  • MULTI: 多次访问。当一个 SINGLE 优先级的块被再次访问时，它的优先级会提升为 MULTI。这给了被访问过的块“第二次机会”，避免了“缓存污染”（即大量只被访问一次的块将热点块挤出缓存）。
  • MEMORY: 内存中。通常用于元数据块（如索引块）或者明确指定需要驻留内存的块。这类块有最高的优先级，最不容易被淘汰。
• cachedTime (final long): 块被缓存时的时间戳（使用 System.nanoTime()）。这个值是不可变的，主要用于缓存统计，例如计算块在被淘汰前的存活时间。

构造函数

// … existing code …
public LruCachedBlock(BlockCacheKey cacheKey, Cacheable buf, long accessTime) {
this(cacheKey, buf, accessTime, false);
}

public LruCachedBlock(BlockCacheKey cacheKey, Cacheable buf, long accessTime, boolean inMemory) {
this.cacheKey = cacheKey;
this.buf = buf;
this.accessTime = accessTime;
// We approximate the size of this class by the size of its name string
// plus the size of its byte buffer plus the overhead associated with all
// the base classes. We also include the base class
// sizes in the PER_BLOCK_OVERHEAD variable rather than align()ing them with
// their buffer lengths. This variable is used elsewhere in unit tests.
this.size =
ClassSize.align(cacheKey.heapSize()) + ClassSize.align(buf.heapSize()) + PER_BLOCK_OVERHEAD;
if (inMemory) {
this.priority = BlockPriority.MEMORY;
} else {
this.priority = BlockPriority.SINGLE;
}
}
// … existing code …

构造函数完成了所有字段的初始化。

关键方法

这些方法定义了 LruCachedBlock 的行为，是 LRU 缓存逻辑能够正确运行的保证。

• access(long accessTime): 当缓存块被命中时调用。

  // … existing code …
  public void access(long accessTime) {
  this.accessTime = accessTime;
  if (this.priority == BlockPriority.SINGLE) {
  this.priority = BlockPriority.MULTI;
  }
  }
  // … existing code …

  它会更新 accessTime 为最新的访问序列号，并检查当前优先级。如果优先级是 SINGLE，就将其提升为 MULTI。这个机制是 LRU 缓存的重要优化。

• heapSize(): 实现了 HeapSize 接口。

  // … existing code …
  @Override
  public long heapSize() {
  return size;
  }
  // … existing code …

  直接返回在构造函数中计算好的 size 字段。

• compareTo(LruCachedBlock that): 实现了 Comparable 接口，定义了排序规则。

  // … existing code …
  @Override
  public int compareTo(LruCachedBlock that) {
  // Newer accessed blocks sort before older ones.
  if (this.accessTime == that.accessTime) return 0;
  return this.accessTime < that.accessTime ? 1 : -1;
  }
  // … existing code …

  这里的比较逻辑非常关键：

  • 它完全基于 accessTime。
  • 如果 this.accessTime 小于 that.accessTime，意味着 this 块比 that 块更“老”（更早被访问），方法返回 1。
  • 在标准的排序算法中（如 PriorityQueue），这会导致 accessTime 较小的（老的）元素排在后面，而 accessTime 较大的（新的）元素排在前面。
  • 因此，当需要淘汰时，从排序集合的“末尾”取出的就是最近最少使用的块。

• equals(Object obj) 和 hashCode():

  // … existing code …
  @Override
  public int hashCode() {
  return (int) (accessTime ^ (accessTime >>> 32));
  }

  @Override
  public boolean equals(Object obj) {
  if (this == obj) {
  return true;
  }
  if (obj == null || getClass() != obj.getClass()) {
  return false;
  }
  LruCachedBlock other = (LruCachedBlock) obj;
  return compareTo(other) == 0;
  }
  // … existing code …

  这两个方法的实现都只依赖于 accessTime。这意味着，如果两个 LruCachedBlock 实例的 accessTime 相同，它们就被认为是 equals 的。这在通常的业务对象中比较少见（通常会基于ID或内容），但在这里是特意为之，因为在某些用于排序的数据结构（如 MinMaxPriorityQueue）中，元素的相等性判断和排序逻辑需要保持一致。

总结

LruCachedBlock 是一个精心设计的类，它不仅仅是一个数据持有者，更是 LruBlockCache 能够实现高效、带优先级的 LRU 淘汰策略的核心组件。它通过：

通过将这些逻辑内聚在 LruCachedBlock 内部，使得上层的 LruBlockCache 和 LruAdaptiveBlockCache 的实现可以更加清晰，专注于缓存的宏观管理和并发控制，而将单个缓存条目的状态和行为交由 LruCachedBlock 自己管理。

LruBlockCache

LruBlockCache 是 Apache HBase 中默认的、基于堆内内存的 Block Cache（块缓存）实现。它是一个至关重要的组件，直接影响 HBase 的读取性能。它的核心目标是将在 HDFS 中读取过的热点数据块（HFile Block）缓存在 RegionServer 的 JVM 堆内存中，从而避免下一次读取相同数据时昂贵的磁盘 I/O 操作。

@InterfaceAudience.Private
public class LruBlockCache implements FirstLevelBlockCache {
//…
}

• implements FirstLevelBlockCache: 这个接口定义了其作为“一级缓存”（L1 Cache）的角色。在 HBase 的缓存体系中，可以存在多级缓存。LruBlockCache 通常作为 L1 缓存，可以直接与性能更高的 L2 缓存（如基于堆外内存的 BucketCache）协同工作。
  • FirstLevelBlockCache 接口继承了 ResizableBlockCache 和 HeapSize，意味着 LruBlockCache 的大小是可调整的，并且能够报告自身占用的堆内存大小。
  • 它还定义了 setVictimCache(BlockCache victimCache) 方法。当一个块因为空间不足而从 L1 缓存中被“淘汰”（evict）时，它可以被传递给这个 "victim cache"（通常是 L2 缓存），从而实现分层缓存。

LruBlockCache 的设计精髓在于它并非一个简单的 LRU 缓存，而是融合了并发控制、优先级和精细化内存管理的复杂系统。

并发性 (Concurrency)

缓存系统必须支持高并发的读写。LruBlockCache 使用 java.util.concurrent.ConcurrentHashMap 作为其底层存储结构。

// … existing code …
/**
* Defined the cache map as {@link ConcurrentHashMap} here, because in
* {@link LruBlockCache#getBlock}, we need to guarantee the atomicity of map#k (key, func).
* Besides, the func method must execute exactly once only when the key is present and under the
* lock context, otherwise the reference count will be messed up. Notice that the
* {@link java.util.concurrent.ConcurrentSkipListMap} can not guarantee that. Some code using
* #computeIfPresent also expects the supplier to be executed only once. ConcurrentHashMap can
* guarantee that. Other types may not.
*/
private transient final ConcurrentHashMap<BlockCacheKey, LruCachedBlock> map;
// … existing code …

选择 ConcurrentHashMap 的关键在于其 computeIfPresent 等原子操作方法，这能保证在“获取并更新”一个缓存块（例如更新其访问时间）这个复合操作的原子性，避免了在高并发场景下使用显式锁带来的性能开销和复杂性。

带有优先级的 LRU 淘汰策略

纯粹的 LRU 算法在某些场景下表现不佳，例如，一次大的扫描操作（Scan）可能会读入大量低价值、只访问一次的数据块，从而将真正需要频繁访问的热点数据块“冲刷”出缓存。为了解决这个问题，LruBlockCache 引入了三级优先级：

这三个优先级各自被分配了一定比例的缓存空间（由配置参数 singleFactor, multiFactor, memoryFactor 决定），淘汰算法会根据每个优先级分区的使用情况来公平地进行淘汰。

异步淘汰机制 (Eviction)

为了保证 cacheBlock 和 getBlock 方法的低延迟，淘汰操作在一个独立的后台线程 (EvictionThread) 中执行。

• 触发时机: 当缓存的当前大小 size 超过了 maxSize * acceptableFactor（默认 0.99）时，会触发淘汰。
• 淘汰目标: 淘汰线程会持续工作，直到缓存大小降低到 maxSize * minFactor（默认 0.95）以下。
• 硬限制: 还有一个 hardCapacityLimitFactor（默认 1.2），当缓存大小超过 maxSize * acceptableFactor * hardCapacityLimitFactor 时，新的缓存请求会被直接拒绝，防止缓存无限膨胀。

关键成员变量

LruBlockCache 内部有大量的成员变量来维护其状态和配置。

// … existing code …
/** Cache access count (sequential ID) */
private final AtomicLong count;

/** hard capacity limit */
private float hardCapacityLimitFactor;

/** Cache statistics */
private final CacheStats stats;

/** Maximum allowable size of cache (block put if size > max, evict) */
private long maxSize;

// … existing code …
/** Acceptable size of cache (no evictions if size < acceptable) */
private float acceptableFactor;

/** Minimum threshold of cache (when evicting, evict until size < min) */
private float minFactor;

/** Single access bucket size */
private float singleFactor;

/** Multiple access bucket size */
private float multiFactor;

/** In-memory bucket size */
private float memoryFactor;

// … existing code …
/**
* Where to send victims (blocks evicted/missing from the cache). This is used only when we use an
* external cache as L2. Note: See org.apache.hadoop.hbase.io.hfile.MemcachedBlockCache
*/
private transient BlockCache victimHandler = null;
// … existing code …

• map: 核心存储。
• size, elements, dataBlockSize, indexBlockSize 等: 使用 AtomicLong 和 LongAdder 来高效、线程安全地记录缓存的各种统计指标。
• count: 一个原子递增的计数器，用于为每个 LruCachedBlock 生成唯一的 accessTime。
• maxSize, acceptableFactor, minFactor, singleFactor 等: 控制缓存行为和淘汰策略的各种配置因子。
• evictionInProgress: 一个 volatile 标志，用于表示淘汰是否正在进行。
• evictionLock: 一个 ReentrantLock，确保同一时间只有一个淘汰任务在执行。
• victimHandler: 指向 L2 缓存的引用。

cacheBlock(…) – 缓存块

这是向缓存中添加新块的入口。

// … existing code …
@Override
public void cacheBlock(BlockCacheKey cacheKey, Cacheable buf, boolean inMemory) {
if (buf.heapSize() > maxBlockSize) {
// … existing code …
return;
}

LruCachedBlock cb = map.get(cacheKey);
if (cb != null && !BlockCacheUtil.shouldReplaceExistingCacheBlock(this, cacheKey, buf)) {
return;
}
long currentSize = size.get();
long currentAcceptableSize = acceptableSize();
long hardLimitSize = (long) (hardCapacityLimitFactor * currentAcceptableSize);
if (currentSize >= hardLimitSize) {
stats.failInsert();
// … existing code …
if (!evictionInProgress) {
runEviction();
}
return;
}
// Ensure that the block is an heap one.
buf = asReferencedHeapBlock(buf);
cb = new LruCachedBlock(cacheKey, buf, count.incrementAndGet(), inMemory);
long newSize = updateSizeMetrics(cb, false);
map.put(cacheKey, cb);
// … existing code …
if (newSize > currentAcceptableSize && !evictionInProgress) {
runEviction();
}
}
// … existing code …

其执行流程如下：

getBlock(…) – 获取块

这是从缓存中读取块的入口。它利用了 map.computeIfPresent 来原子地完成“获取并更新”操作，保证了线程安全和高性能。如果命中，它会更新块的 accessTime 和优先级，这是 LRU 逻辑的核心。

evict() – 淘汰逻辑

evict() 方法是 LruBlockCache 中负责执行缓存淘汰的核心函数。它的主要目标是当缓存大小超过预设的阈值时，通过移除最近最少使用的块（LRU），将缓存大小降低到一个可接受的水平。这个过程是异步的，通常由一个专门的 EvictionThread 线程来调用，以避免阻塞正常的缓存读写操作。

我们来逐段分析它的实现：

// … existing code …
void evict() {

// Ensure only one eviction at a time
if (!evictionLock.tryLock()) {
return;
}

try {
evictionInProgress = true;
long currentSize = this.size.get();
long bytesToFree = currentSize – minSize();

if (LOG.isTraceEnabled()) {
// … existing code …
}

if (bytesToFree <= 0) {
return;
}

// Instantiate priority buckets
BlockBucket bucketSingle = new BlockBucket("single", bytesToFree, blockSize, singleSize());
BlockBucket bucketMulti = new BlockBucket("multi", bytesToFree, blockSize, multiSize());
BlockBucket bucketMemory = new BlockBucket("memory", bytesToFree, blockSize, memorySize());

// Scan entire map putting into appropriate buckets
for (LruCachedBlock cachedBlock : map.values()) {
switch (cachedBlock.getPriority()) {
case SINGLE: {
bucketSingle.add(cachedBlock);
break;
}
case MULTI: {
bucketMulti.add(cachedBlock);
break;
}
case MEMORY: {
bucketMemory.add(cachedBlock);
break;
}
}
}

long bytesFreed = 0;
if (forceInMemory || memoryFactor > 0.999f) {
// … (special eviction logic) …
} else {
PriorityQueue<BlockBucket> bucketQueue = new PriorityQueue<>(3);

bucketQueue.add(bucketSingle);
bucketQueue.add(bucketMulti);
bucketQueue.add(bucketMemory);

int remainingBuckets = bucketQueue.size();

BlockBucket bucket;
while ((bucket = bucketQueue.poll()) != null) {
long overflow = bucket.overflow();
if (overflow > 0) {
long bucketBytesToFree =
Math.min(overflow, (bytesToFree – bytesFreed) / remainingBuckets);
bytesFreed += bucket.free(bucketBytesToFree);
}
remainingBuckets–;
}
}
// … (logging) …
} finally {
stats.evict();
evictionInProgress = false;
evictionLock.unlock();
}
}
// … existing code …

加锁与状态设置

// Ensure only one eviction at a time
if (!evictionLock.tryLock()) {
return;
}

try {
evictionInProgress = true;
// …
} finally {
// …
evictionInProgress = false;
evictionLock.unlock();
}

• evictionLock.tryLock(): 这是整个淘汰过程的入口保护。evictionLock 是一个 ReentrantLock。使用 tryLock() 而不是 lock() 是一个非阻塞的尝试。如果锁已经被其他线程（或当前线程的另一次调用）持有，tryLock() 会立即返回 false，方法直接退出。这确保了在任何时刻，最多只有一个淘汰过程在执行，避免了并发淘汰带来的竞态条件和不必要的开销。
• evictionInProgress = true: 这是一个 volatile 标志位，用于向其他线程（如 cacheBlock 方法）表明淘汰正在进行中。这可以用来防止在淘汰期间发生某些操作，或者作为触发其他逻辑的信号。
• try…finally: 这是一个标准的、健壮的锁管理模式。无论淘汰过程是否成功或抛出异常，finally 块中的代码都会被执行，保证 evictionInProgress 标志被重置，并且锁一定会被释放，防止死锁。

计算需要释放的空间

long currentSize = this.size.get();
long bytesToFree = currentSize – minSize();

if (bytesToFree <= 0) {
return;
}

• currentSize 是缓存当前的总大小。
• minSize() 计算的是淘汰的目标大小，通常是 maxSize * minFactor (默认 0.95)。
• bytesToFree 就是需要从缓存中移除的块的总大小。如果这个值小于等于0，说明当前缓存大小已经在健康范围内，无需淘汰，方法直接返回。

分桶 (Bucketing)

这是实现带优先级淘汰策略的核心步骤。

注意这里的构造，最小最大堆的 容量 就是 bytesToFree，即要淘汰的数量，是一个top K用法。

// Instantiate priority buckets
BlockBucket bucketSingle = new BlockBucket("single", bytesToFree, blockSize, singleSize());
BlockBucket bucketMulti = new BlockBucket("multi", bytesToFree, blockSize, multiSize());
BlockBucket bucketMemory = new BlockBucket("memory", bytesToFree, blockSize, memorySize());

// Scan entire map putting into appropriate buckets
for (LruCachedBlock cachedBlock : map.values()) {
switch (cachedBlock.getPriority()) {
case SINGLE: {
bucketSingle.add(cachedBlock);
break;
}
// … other cases
}
}

• 创建 BlockBucket: 代码创建了三个 BlockBucket 实例，分别对应 SINGLE、MULTI 和 MEMORY 三种优先级。每个 BlockBucket 在初始化时被告知了它的目标大小（如 singleSize()）。
• 遍历和分类: 接着，代码会遍历整个 ConcurrentHashMap (map.values())。这是一个昂贵的操作，也是为什么淘汰需要异步执行的主要原因。对于每一个 LruCachedBlock，它会检查其优先级，并将其添加到相应的 BlockBucket 中。

BlockBucket.add(LruCachedBlock block)

// in class BlockBucket
public void add(LruCachedBlock block) {
totalSize += block.heapSize();
queue.add(block);
}

这个方法很简单，它累加桶的总大小，并将 LruCachedBlock 添加到内部的 LruCachedBlockQueue 中。LruCachedBlockQueue 内部是一个 MinMaxPriorityQueue，它会根据 LruCachedBlock 的 compareTo 方法（即比较 accessTime）来自动排序，确保访问时间最老和最新的块总是在队列的两端，可以被快速访问到。

执行淘汰算法

这里有两种主要的淘汰逻辑：

默认淘汰逻辑

PriorityQueue<BlockBucket> bucketQueue = new PriorityQueue<>(3);

bucketQueue.add(bucketSingle);
bucketQueue.add(bucketMulti);
bucketQueue.add(bucketMemory);

int remainingBuckets = bucketQueue.size();

BlockBucket bucket;
while ((bucket = bucketQueue.poll()) != null) {
long overflow = bucket.overflow();
if (overflow > 0) {
long bucketBytesToFree =
Math.min(overflow, (bytesToFree – bytesFreed) / remainingBuckets);
bytesFreed += bucket.free(bucketBytesToFree);
}
remainingBuckets–;
}

这是标准的、基于“溢出”的公平淘汰算法。

BlockBucket.free(long toFree)

// in class BlockBucket
public long free(long toFree) {
// … logging …
LruCachedBlock cb;
long freedBytes = 0;
while ((cb = queue.pollLast()) != null) {
freedBytes += evictBlock(cb, true);
if (freedBytes >= toFree) {
return freedBytes;
}
}
// … logging …
return freedBytes;
}

优先保护内存中（in-memory）数据块的特殊淘汰模式。

这个逻辑的触发条件是：

if (forceInMemory || memoryFactor > 0.999f)

• forceInMemory: 这是一个布尔类型的配置项，当它为 true 时，表示强制优先保留内存块。
• memoryFactor: 这是一个浮点数配置项，代表为内存块（in-memory blocks）分配的缓存空间比例。当这个值非常接近1时（> 0.999f），意味着几乎所有的缓存都应该用于内存块。

当满足以上任一条件时，就会进入这个特殊的淘汰逻辑，其核心思想是：尽可能地避免淘汰 "memory" 类型的缓存块，优先淘汰 "single-access" 和 "multi-access" 类型的缓存块。

这个逻辑内部分为两种情况：

evictBlock(LruCachedBlock block, boolean evictedByEvictionProcess)

// in class LruBlockCache
protected long evictBlock(LruCachedBlock block, boolean evictedByEvictionProcess) {
final MutableBoolean evicted = new MutableBoolean(false);
map.computeIfPresent(block.getCacheKey(), (k, v) -> {
if (evictedByEvictionProcess && victimHandler != null) {
victimHandler.cacheBlock(k, v.getBuffer());
}
v.getBuffer().release();
evicted.setTrue();
return null;
});
if (evicted.isFalse()) {
return 0;
}
// … update metrics …
return block.heapSize();
}

这是移除单个块的最终实现，非常关键：

最终清理

} finally {
stats.evict();
evictionInProgress = false;
evictionLock.unlock();
}

在 finally 块中：

• stats.evict(): 更新淘汰次数的统计。
• evictionInProgress = false: 重置状态标志。
• evictionLock.unlock(): 释放锁，允许下一次淘汰操作可以进行。

LruBlockCache.evict() 是一个设计精良、逻辑复杂的函数，它完美地体现了该缓存系统的核心思想：

整个流程从宏观的加锁、计算，到中观的分桶、排序，再到微观的原子移除和引用计数管理，层层递进，逻辑严谨，是理解 HBase 高性能缓存实现的关键。

LruBlockCache 中 block 的优先级

在 single（单次访问）、multi（多次访问）和 in-memory（内存中）之间转换的。

这个转换逻辑主要由 LruBlockCache 的设计决定，其目的是为了在缓存中更好地区分不同访问模式的数据，防止偶然的大量扫描（scan）操作污染整个缓存，从而提高缓存命中率。

当一个 block 首次被放入缓存时，它的初始优先级就被确定了。这主要发生在 cacheBlock 方法中。

// … existing code …
@Override
public void cacheBlock(BlockCacheKey cacheKey, Cacheable buf, boolean inMemory) {
if (buf.heapSize() > maxBlockSize) {
// … existing code …
return;
}

// … existing code …
// Ensure that the block is an heap one.
buf = asReferencedHeapBlock(buf);
cb = new LruCachedBlock(cacheKey, buf, count.incrementAndGet(), inMemory);
long newSize = updateSizeMetrics(cb, false);
map.put(cacheKey, cb);
// … existing code …
}
// … existing code …

从 cacheBlock 方法的签名和实现可以看出：

• in-memory 优先级: 如果 cacheBlock 被调用时，inMemory 参数为 true（这通常意味着该 block 所属的列族被配置为 inMemory=true），那么新创建的 LruCachedBlock 会被赋予 MEMORY 优先级。这类 block 会被优先保留在缓存中。
• single-access 优先级: 如果 inMemory 参数为 false，那么该 block 在首次被缓存时，会被赋予 SINGLE 优先级。

从 single 到 multi 的转换

当一个已经是 SINGLE 优先级的 block 被再次访问时，它的优先级会被提升为 MULTI。这个逻辑发生在 getBlock 方法中。

// … existing code …
@Override
public Cacheable getBlock(BlockCacheKey cacheKey, boolean caching, boolean repeat,
boolean updateCacheMetrics) {
// Note: 'map' must be a ConcurrentHashMap or the supplier may be invoked more than once.
LruCachedBlock cb = map.computeIfPresent(cacheKey, (key, val) -> {
// … existing code …
val.getBuffer().retain();
return val;
});
if (cb == null) {
// … existing code …
return null;
}
if (updateCacheMetrics) {
stats.hit(caching, cacheKey.isPrimary(), cacheKey.getBlockType());
}
cb.access(count.incrementAndGet());
return cb.getBuffer();
}
// … existing code …

当 getBlock 方法成功在缓存中找到一个 block（即缓存命中）时，会调用 cb.access(…) 方法。这个 access 方法（在 LruCachedBlock 内部实现，其行为在 LruBlockCache 的类注释中有详细描述）会检查当前 block 的优先级：

• 如果当前优先级是 SINGLE，它会将其提升为 MULTI。
• 如果当前优先级已经是 MULTI 或 MEMORY，则保持不变。

/**
* Block has been accessed.
* @param accessTime Last access; this is actually a incremented sequence number rather than an
* actual time.
*/
public void access(long accessTime) {
this.accessTime = accessTime;
if (this.priority == BlockPriority.SINGLE) {
this.priority = BlockPriority.MULTI;
}
}

block 的优先级转换路径是单向的：

一旦一个 block 的优先级变为 MULTI 或 MEMORY，它就不会再降级。这种机制确保了频繁访问的“热”数据和配置为常驻内存的数据能够有更高的概率保留在缓存中，而只被访问一次的“冷”数据（如全表扫描产生的数据）则更容易被淘汰。

总结

LruBlockCache 是一个高度优化的、生产级的缓存实现。它通过以下设计实现了高性能和高效率：

• 并发数据结构: 使用 ConcurrentHashMap 避免了显式锁，提供了高并发访问能力。
• 异步淘汰: 将耗时的淘汰操作放在后台线程，保证了前台读写请求的低延迟。
• 优先级分区: 通过 SINGLE, MULTI, MEMORY 三个优先级，有效抵抗了扫描操作对缓存的污染，提高了热点数据的命中率。
• 精细化内存管理: 通过 HeapSize 接口和详细的统计，精确控制 JVM 堆内存的使用。
• 可扩展性: 通过 FirstLevelBlockCache 和 victimHandler 机制，可以方便地与 L2 缓存（如 BucketCache）组合，构建更强大的分层缓存系统。

理解 LruBlockCache 的工作原理对于 HBase 的性能调优和问题诊断至关重要。

LruCachedBlockQueue 

LruCachedBlockQueue 是 HBase 中 LruBlockCache 淘汰机制的一个关键辅助类。它并不是一个通用的队列，而是为一个非常特定的场景设计的：在内存大小受限的情况下，维护一组“最优”的元素。在 LruBlockCache 的上下文中，这个“最优”指的是 访问时间最新（accessTime 最大） 的 LruCachedBlock 集合。

下面我们从它的设计目标、核心数据结构、构造函数和关键方法等方面来深入剖析。

@InterfaceAudience.Private
public class LruCachedBlockQueue implements HeapSize {
//…
}

• implements HeapSize: 这个接口表明 LruCachedBlockQueue 实例可以报告其内部所有元素占用的总堆内存大小。这对于上层调用者（BlockBucket）统计内存使用非常重要。

它的核心设计目标在类的注释中有清晰的描述：

A memory-bound queue that will grow until an element brings total size >= maxSize. From then on, only entries that are sorted larger than the smallest current entry will be inserted/replaced.

翻译过来就是：一个受内存限制的队列。它会一直增长，直到内部所有元素的总大小（heapSize）超过了设定的 maxSize。从那一刻起，只有当一个新元素的排序（compareTo 的结果）比队列中当前最小的元素还要大时，才会被考虑加入队列（并可能替换掉最小的元素）。

这个类的作用是在 LruBlockCache 的 evict() 过程中，为每个优先级（SINGLE, MULTI, MEMORY）的 BlockBucket 临时存放该优先级的全部 LruCachedBlock，并能快速地从中找到并移除最近最少使用（accessTime 最小）的块。

核心成员变量

// … existing code …
private MinMaxPriorityQueue<LruCachedBlock> queue;

private long heapSize;
private long maxSize;
// … existing code …

• queue (MinMaxPriorityQueue<LruCachedBlock>): 这是实现 LruCachedBlockQueue 功能的核心数据结构。MinMaxPriorityQueue 是 Google Guava 库提供的一种特殊的优先队列。与标准的 PriorityQueue（只能高效访问最小元素）不同，MinMaxPriorityQueue 可以在 O(1) 时间内访问到最小和最大的元素，并在 O(log n) 时间内移除它们。
  • 在这个场景下，LruCachedBlock 的 compareTo 方法定义了 accessTime 越大（越新）的块排序越靠前（被认为是“更大”的元素）。
  • 因此，queue.peek() 或 queue.poll() 会返回**accessTime 最小**的块（最近最少使用的）。
  • queue.peekLast() 或 queue.pollLast() 会返回**accessTime 最大**的块（最近刚使用的）。
• heapSize (long): 记录当前队列中所有 LruCachedBlock 的 heapSize() 之和。
• maxSize (long): 队列的目标内存大小上限。这个值在构造时传入，通常是 LruBlockCache.evict() 方法中计算出的 bytesToFree。

构造函数

// … existing code …
public LruCachedBlockQueue(long maxSize, long blockSize) {
Preconditions.checkArgument(blockSize > 0, "negative blockSize %s", blockSize);
Preconditions.checkArgument(maxSize > 0, "negative maxSize %s", maxSize);
int initialSize = (int) (maxSize / blockSize);
if (initialSize == 0) {
initialSize++;
}
queue = MinMaxPriorityQueue.expectedSize(initialSize).create();
heapSize = 0;
this.maxSize = maxSize;
}
// … existing code …

构造函数主要做初始化工作：

add(LruCachedBlock cb)

这是这个类中最核心、逻辑最复杂的方法。它定义了元素如何被添加到这个受限队列中。

// … existing code …
public void add(LruCachedBlock cb) {
if (heapSize < maxSize) {
queue.add(cb);
heapSize += cb.heapSize();
} else {
LruCachedBlock head = queue.peek();
if (cb.compareTo(head) > 0) {
heapSize += cb.heapSize();
heapSize -= head.heapSize();
if (heapSize > maxSize) {
queue.poll();
} else {
heapSize += head.heapSize();
}
queue.add(cb);
}
}
}
// … existing code …

该方法分为两种情况：

注意: add 方法的逻辑在 LruBlockCache 的 evict 场景下是正确的，因为 evict 只是用这个队列来维护top K 待淘汰元素，之后会通过 pollLast 来主动移除元素。

这是在构建淘汰候选池，如果池子满了，每当遇到一个新块，就和池里最年轻的那个候选者（head）比较。如果新块比它还老，就说明新块更应该被淘汰，于是用新块换掉那个最年轻的候选者。这个“换掉”的操作，就是通过 poll() 移除 head，再 add(cb) 实现的。

poll() 和 pollLast()

// … existing code …
/** Returns The next element in this queue, or {@code null} if the queue is empty. */
public LruCachedBlock poll() {
return queue.poll();
}

/** Returns The last element in this queue, or {@code null} if the queue is empty. */
public LruCachedBlock pollLast() {
return queue.pollLast();
}
// … existing code …

• poll(): 移除并返回队列中最小的元素（accessTime 最老的块）。
• pollLast(): 移除并返回队列中最大的元素（accessTime 最新的块）。在 LruBlockCache.BlockBucket.free() 方法中，正是通过不断调用 pollLast() 来获取并淘汰最近最少使用的块。这里有一个重要的细节：LruCachedBlock 的 compareTo 返回 1 表示 this 比 that 老，所以排序后，accessTime 小的（老的）被认为是“大”元素，accessTime 大的（新的）被认为是“小”元素。因此，poll() 会移除最新的块，而 pollLast() 会移除最老的块。这与 MinMaxPriorityQueue 的通用语义有些反直觉，但完全取决于 LruCachedBlock 的 compareTo 实现。

让我们再次确认 LruCachedBlock.compareTo 的实现：

public int compareTo(LruCachedBlock that) {
if (this.accessTime == that.accessTime) return 0;
return this.accessTime < that.accessTime ? 1 : -1;
}

this.accessTime < that.accessTime (this更老) -> 返回 1。在 PriorityQueue 中，返回值大于0意味着 this 的优先级更低，会排在后面。所以 poll() 会取出 accessTime 最大的（最新的），pollLast() 会取出 accessTime 最小的（最老的）。BlockBucket.free() 中调用 queue.pollLast() 是正确的，它确实在淘汰最老的块。

总结

LruCachedBlockQueue 是一个高度特化的数据结构，它巧妙地利用了 Guava 的 MinMaxPriorityQueue 来满足 LruBlockCache 淘汰算法的需求。

• 核心作用: 在淘汰过程中，为每个优先级桶临时存储所有的块，并提供高效地访问和移除“最近最少使用”块的能力。
• 关键数据结构: MinMaxPriorityQueue 提供了 O(log n) 时间复杂度的 pollLast() 操作，这对于从大量块中找出最老的块进行淘汰至关重要。
• 内存感知: 通过实现 HeapSize 并维护 heapSize 字段，它使其内部状态对上层调用者透明。
• 特化的 add 逻辑: add 方法的行为是为“保留最优元素”这个特定目标设计的，而不是一个通用的队列添加操作。

总而言之，LruCachedBlockQueue 是 LruBlockCache 实现其高效、带优先级的淘汰策略的一个不可或缺的底层组件。