Nick Dimiduk

n10k.com: blog et al.

BlockCache 101

Edit: The sequel post, BlockCache Showdown is now available!

HBase is a distributed database built around the core concepts of an ordered write log and a log-structured merge tree. As with any database, optimized I/O is a critical concern to HBase. When possible, the priority is to not perform any I/O at all. This means that memory utilization and caching structures are of utmost importance. To this end, HBase maintains two cache structures: the “memory store” and the “block cache”. Memory store, implemented as the MemStore, accumulates data edits as they’re received, buffering them in memory 1. The block cache, an implementation of the BlockCache interface, keeps data blocks resident in memory after they’re read.

The MemStore is important for accessing recent edits. Without the MemStore, accessing that data as it was written into the write log would require reading and deserializing entries back out of that file, at least a O(n) operation. Instead, MemStore maintains a skiplist structure, which enjoys a O(log n) access cost and requires no disk I/O. The MemStore contains just a tiny piece of the data stored in HBase, however.

Servicing reads from the BlockCache is the primary mechanism through which HBase is able to serve random reads with millisecond latency. When a data block is read from HDFS, it is cached in the BlockCache. Subsequent reads of neighboring data – data from the same block – do not suffer the I/O penalty of again retrieving that data from disk 2. It is the BlockCache that will be the remaining focus of this post.

Blocks to cache

Before understanding the BlockCache, it helps to understand what exactly an HBase “block” is. In the HBase context, a block is a single unit of I/O. When writing data out to an HFile, the block is the smallest unit of data written. Likewise, a single block is the smallest amount of data HBase can read back out of an HFile. Be careful not to confuse an HBase block with an HDFS block, or with the blocks of the underlying file system – these are all different 3.

HBase blocks come in 4 varieties: DATA, META, INDEX, and BLOOM.

DATA blocks store user data. When the BLOCKSIZE is specified for a column family, it is a hint for this kind of block. Mind you, it’s only a hint. While flushing the MemStore, HBase will do its best to honor this guideline. After each Cell is written, the writer checks if the amount written is >= the target BLOCKSIZE. If so, it’ll close the current block and start the next one 4.

INDEX and BLOOM blocks serve the same goal; both are used to speed up the read path. INDEX blocks provide an index over the Cells contained in the DATA blocks. BLOOM blocks contain a bloom filter over the same data. The index allows the reader to quickly know where a Cell should be stored. The filter tells the reader when a Cell is definitely absent from the data.

Finally, META blocks store information about the HFile itself and other sundry information – metadata, as you might expect. A more comprehensive overview of the HFile formats and the roles of various block types is provided in Apache HBase I/O - HFile.

HBase BlockCache and its implementations

There is a single BlockCache instance in a region server, which means all data from all regions hosted by that server share the same cache pool 5. The BlockCache is instantiated at region server startup and is retained for the entire lifetime of the process. Traditionally, HBase provided only a single BlockCache implementation: the LruBlockCache. The 0.92 release introduced the first alternative in HBASE-4027: the SlabCache. HBase 0.96 introduced another option via HBASE-7404, called the BucketCache.

The key difference between the tried-and-true LruBlockCache and these alternatives is the way they manage memory. Specifically, LruBlockCache is a data structure that resides entirely on the JVM heap, while the other two are able to take advantage of memory from outside of the JVM heap. This is an important distinction because JVM heap memory is managed by the JVM Garbage Collector, while the others are not. In the cases of SlabCache and BucketCache, the idea is to reduce the GC pressure experienced by the region server process by reducing the number of objects retained on the heap.

LruBlockCache

This is the default implementation. Data blocks are cached in JVM heap using this implementation. It is subdivided into three areas: single-access, multi-access, and in-memory. The areas are sized at 25%, 50%, 25% of the total BlockCache size, respectively 6. A block initially read from HDFS is populated in the single-access area. Consecutive accesses promote that block into the multi-access area. The in-memory area is reserved for blocks loaded from column families flagged as IN_MEMORY. Regardless of area, old blocks are evicted to make room for new blocks using a Least-Recently-Used algorithm, hence the “Lru” in “LruBlockCache”.

SlabCache

This implementation allocates areas of memory outside of the JVM heap using DirectByteBuffers. These areas provide the body of this BlockCache. The precise area in which a particular block will be placed is based on the size of the block. By default, two areas are allocated, consuming 80% and 20% of the total configured off-heap cache size, respectively. The former is used to cache blocks that are approximately the target block size 7. The latter holds blocks that are approximately 2x the target block size. A block is placed into the smallest area where it can fit. If the cache encounters a block larger than can fit in either area, that block will not be cached. Like LruBlockCache, block eviction is managed using an LRU algorithm.

BucketCache

This implementation can be configured to operate in one of three different modes: heap, offheap, and file. Regardless of operating mode, the BucketCache manages areas of memory called “buckets” for holding cached blocks. Each bucket is created with a target block size. The heap implementation creates those buckets on the JVM heap; offheap implementation uses DirectByteByffers to manage buckets outside of the JVM heap; file mode expects a path to a file on the filesystem wherein the buckets are created. file mode is intended for use with a low-latency backing store – an in-memory filesystem, or perhaps a file sitting on SSD storage 8. Regardless of mode, BucketCache creates 14 buckets of different sizes. It uses frequency of block access to inform utilization, just like LruBlockCache, and has the same single-access, multi-access, and in-memory breakdown of 25%, 50%, 25%. Also like the default cache, block eviction is managed using an LRU algorithm.

Multi-Level Caching

Both the SlabCache and BucketCache are designed to be used as part of a multi-level caching strategy. Thus, some portion of the total BlockCache size is allotted to an LruBlockCache instance. This instance acts as the first level cache, “L1,” while the other cache instance is treated as the second level cache, “L2.” However, the interaction between LruBlockCache and SlabCache is different from how the LruBlockCache and the BucketCache interact.

The SlabCache strategy, called DoubleBlockCache, is to always cache blocks in both the L1 and L2 caches. The two cache levels operate independently: both are checked when retrieving a block and each evicts blocks without regard for the other. The BucketCache strategy, called CombinedBlockCache, uses the L1 cache exclusively for Bloom and Index blocks. Data blocks are sent directly to the L2 cache. In the event of L1 block eviction, rather than being discarded entirely, that block is demoted to the L2 cache.

Which to choose?

There are two reasons to consider enabling one of the alternative BlockCache implementations. The first is simply the amount of RAM you can dedicate to the region server. Community wisdom recognizes the upper limit of the JVM heap, as far as the region server is concerned, to be somewhere between 14GB and 31GB 9. The precise limit usually depends on a combination of hardware profile, cluster configuration, the shape of data tables, and application access patterns. You’ll know you’ve entered the danger zone when GC pauses and RegionTooBusyExceptions start flooding your logs.

The other time to consider an alternative cache is when response latency really matters. Keeping the heap down around 8-12GB allows the CMS collector to run very smoothly 10, which has measurable impact on the 99th percentile of response times. Given this restriction, the only choices are to explore an alternative garbage collector or take one of these off-heap implementations for a spin.

This second option is exactly what I’ve done. In my next post, I’ll share some unscientific-but-informative experiment results where I compare the response times for different BlockCache implementations.

As always, stay tuned and keep on with the HBase!


1: The MemStore accumulates data edits as they’re received, buffering them in memory. This serves two purposes: it increases the total amount of data written to disk in a single operation, and it retains those recent changes in memory for subsequent access in the form of low-latency reads. The former is important as it keeps HBase write chunks roughly in sync with HDFS block sizes, aligning HBase access patterns with underlying HDFS storage. The latter is self-explanatory, facilitating read requests to recently written data. It’s worth pointing out that this structure is not involved in data durability. Edits are also written to the ordered write log, the HLog, which involves an HDFS append operation at a configurable interval, usually immediate.

2: Re-reading data from the local file system is the best-case scenario. HDFS is a distributed file system, after all, so the worst case requires reading that block over the network. HBase does its best to maintain data locality. These two articles provide an in-depth look at what data locality means for HBase and how its managed.

3: File system, HDFS, and HBase blocks are all different but related. The modern I/O subsystem is many layers of abstraction on top of abstraction. Core to that abstraction is the concept of a single unit of data, referred to as a “block”. Hence, all three of these storage layers define their own block, each of their own size. In general, a larger block size means increased sequential access throughput. A smaller block size facilitates faster random access.

4: Placing the BLOCKSIZE check after data is written has two ramifications. A single Cell is the smallest unit of data written to a DATA block. It also means a Cell cannot span multiple blocks.

5: This is different from the MemStore, for which there is a separate instance for every region hosted by the region server.

6: Until very recently, these memory partitions were statically defined; there was no way to override the 25/50/25 split. A given segment, the multi-access area for instance, could grow larger than it’s 50% allotment as long as the other areas were under-utilized. Increased utilization in the other areas will evict entries from the multi-access area until the 25/50/25 balance is attained. The operator could not change these default sizes. HBASE-10263, shipping in HBase 0.98.0, introduces configuration parameters for these sizes. The flexible behavior is retained.

7: The “approximately” business is to allow some wiggle room in block sizes. HBase block size is a rough target or hint, not a strictly enforced constraint. The exact size of any particular data block will depend on the target block size and the size of the Cell values contained therein. The block size hint is specified as the default block size of 64kb.

8: Using the BucketCache in file mode with a persistent backing store has another benefit: persistence. On startup, it will look for existing data in the cache and verify its validity.

9: As I understand it, there’s two components advising the upper bound on this range. First is a limit on JVM object addressability. The JVM is able to reference an object on the heap with a 32-bit relative address instead of the full 64-bit native address. This optimization is only possible if the total heap size is less than 32GB. See Compressed Oops for more details. The second is the ability of the garbage collector to keep up with the amount of object churn in the system. From what I can tell, the three sources of object churn are MemStore, BlockCache, and network operations. The first is mitigated by the MemSlab feature, enabled by default. The second is influenced by the size of your dataset vs. the size of the cache. The third cannot be helped so long as HBase makes use of a network stack that relies on data copy.

10: Just like with 8, this is assuming “modern hardware”. The interactions here are quite complex and well beyond the scope of a single blog post.

« HBase via Hive, Part 2 BlockCache Showdown »

About the Author

Nick found Hadoop and HBase in 2008 when his nightly ETL jobs started taking 20+ hours to complete. Since then, he has applied these tools to projects over social media, social gaming, click-stream analysis, climatology, and geographic data. Nick also helped establish Seattleā€™s Scalability Meetup and tried his hand at entrepreneurship. He is an HBase committer and coauthored HBase in Action, the unofficial user's guide for HBase. His passion is scalable, online access to scientific data.

Comments