kuniga.me > NP-Incompleteness > CacheLib

CacheLib

28 Aug 2026

CacheLib is an open-source C++ library from Meta for constructing in-process caches. At a high level, we can think of it as a hash table in memory with the option to spill to flash storage.

In this post we’ll study this library, mainly the in-memory portion based on the paper The CacheLib Caching Engine: Design and Experiences at Scale [1] and the code.

Motivation

The paper [1] states the problem CacheLib aims to solve: different systems reinvent the wheel when writing an in-process cache system. The argument for that is different systems require specialized cache solutions, so they can’t use off the shelf solutions.

CacheLib challenges that assumption by providing a flexible cache library that supports a multitude of production use cases including CDN, distributed application cache (e.g. memcached), general in-process cache, etc.

It also provides efficient multi-thread support and a secondary layer of flash storage.

Example

I always understand things better via examples, so let’s start with one, even though some parts need explaining later. The plan is to write a simple key to the cache, then query for that key and then another key that is not in there.

The API can feel a bit un-ergonomic because it’s meant to support multiple use cases, but we can define helpers that make it look more like a hash-table. First inserting an element:

bool put(
  Cache& cache,
  PoolId pid,
  const std::string& key,
  const std::string& value) {

  auto handle = cache.allocate(pid, key, value.size());
  if (!handle) {
    return false; // pool is full and nothing was evictable
  }
  std::memcpy(handle->getMemory(), value.data(), value.size());
  cache.insertOrReplace(handle);
  return true;
}

The API requires a pool, which we’ll cover later. When calling .allocate() it gets an ItemHandle if the library was able to find available memory. Then we copy the data from the value to the handle’s memory and finally signal to the handle to perform the write.

A natural question to ask is why the API is split into 3 pieces. I haven’t found an explicit motivation, but a legit one is that by giving you the memory buffer, you can construct the object directly there instead of copying. In our case we did end up copying anyway, but there might be cases where we don’t have to.

The get() is simpler:

std::optional<std::string> get(Cache& cache, const std::string& key) {
  auto handle = cache.find(key);
  if (!handle) {
    return std::nullopt;
  }
  auto *payload = reinterpret_cast<const char*>(handle->getMemory());
  return std::string(payload, handle->getSize());
}

The only observation is that we store raw bytes in the cache so we need to cast them back to the expected type. Here’s an example on how to write and read back from it:

#include <cachelib/allocator/CacheAllocator.h>

using Cache = facebook::cachelib::LruAllocator;
using facebook::cachelib::PoolId;

Cache::Config config;

config.setCacheName("example")
  .setCacheSize(256 * 1024 * 1024) // 256 MB of DRAM
  .validate();

Cache cache(config);

const auto pid =
  cache.addPool("default", cache.getCacheMemoryStats().ramCacheSize);

put(cache, pid, "hello", "world");

// retrieval
std::cout << get(cache, "my_key").value_or("<miss>") << "\n";
std::cout << get(cache, "other_key").value_or("<miss>") << "\n";

The size we set to setCacheSize() is a hard ceiling on how much the pools can consume. The pools themselves have a size, which in this case is the same as the cache size since we only have a single pool.

It’s worth mentioning that the size passed to the Cache::Config is the “physical” amount of memory we allow it to use, including for overhead such as metadata. The size we provide to the pool is the “logical” amount, how much it can use to store actual data.

To make the point clearer, we can’t do:

cache.addPool("default", 256 * 1024 * 1024);

We have to use cache.getCacheMemoryStats().ramCacheSize which is the effective amount of space available for use.

Concepts

Now that we have some idea on how to use CacheLib, let’s cover the major components and connect it to the example we saw.

Slab

The unit of memory used by CacheLib is called a slab, a chunk of contiguous 4MB memory. The slabs are 4MB-aligned too, meaning their starting address is divisible by 4MB. This allows us to optimize the logic to determine the slab address from a chunk address as we’ll see later (see Chunk).

Each slab carries 3 pieces of metadata: pool id (see Pool), class id (see Allocation Classes) and the chunk size (see Chunk).

Multiple items can be stored in a slab, but if its size is greater than 4MB, then an item is stored across multiple slabs connected as a linked list.

Slab Allocator

The slabs are stored in a contiguous array, which is initialized when creating the cache (based on setCacheSize()). The library uses mmap to get a contiguous virtual address space, but the mapping to physical space is done lazily by the OS.

This array is byte-aligned to 4MB meaning the address of each slab is divisible by 4MB or $2^{22}$. The maximum number of slabs the allocator supports is $2^{32} - 1$.

This array is owned by the slab allocator and it also maintains a list of free slabs.

Chunk

A chunk is a subdivision of a slab. We can think of each slab having an array of chunks of a fixed size, called allocation class and stored as the slab’s metadata.

Each chunk stores exactly one item. This means we need to have slabs with lots of different sizes to avoid internal fragmentation. Because if an item has size 75B and the smallest chunk size is 1K, all the remaining space is wasted. The minimum chunk size is 64B ($2^6$), so each slab can hold at most 65,536 ($2^{16}$) chunks.

In some situations we need to determine the slab address the chunk lives in with only the chunk address. Since we know slabs always have 4MB, first we can determine the slab index via:

// index of the slab in the slab array
idx  = (p - slabMemoryStart_) >> 22;
// address of the slab
slab = slabMemoryStart_ + (idx << 22);

But since we know it’s aligned at 4MB, we can simply zero the least significant 22 bits of the chunk address:

slab = p & ~((1 << 22) - 1);

Item

An item (CacheItem) is a class containing the key and value of the stored entry. It also stores metadata such as TTL. There’s a 1:1 mapping between a chunk and an item, so conceptually we can treat them as the same thing, as we’ll do throughout the post.

A chunk is a blob of memory, whereas the item is the data that lives in that location. A chunk has fixed size whereas the item size depends on what it’s storing. The chunk is not deleted when an item is evicted.

An item also represents a node in two linked lists, which we’ll call the index-linked-list and the eviction-linked-list. We’ll discuss them in Index and Eviction-Order, respectively. So while chunks have a fixed “physical” order inside a slab, the items have different logical orders for indexing and eviction purposes.

Allocation Classes

We can think of an allocation class as an object that manages all slabs with chunks of a given size. This is the ultimate object that determines which address to return back to the allocate() API.

It contains a few sets of information: a list of “active” slabs, a list of “free” slabs (empty slabs that it can use) and the current slab. All these are pointers to the global slab array. It also stores a stack of pointers to chunks that have been freed (freedAllocations).

An active slab never goes back to be a free slab. So as the program runs, and assuming the cache is fully utilized, we’ll get to an equilibrium state where there are no free slabs and each class is “right sized”. If item distribution changes though, there’s a background process to rebalance things (see Rebalancing).

Pool

A pool (class MemoryPool) is a collection of allocation classes. We can think of pools as strict partitions of the cache memory, because it has a specified size that is honored by the system. This is not true for allocation classes within a pool. As we’ll see in Rebalancing, the rebalancer can move slabs between allocation classes within a pool.

Pools are stored as an array by the pool manager (class MemoryPoolManager) and the pool id is just an index on that array. You can use multiple pools if you want the cache to be shared by different use cases with different quotas. At most 64 pools can be used, but in most cases a single pool is often enough.

The addPool() method hints at the responsibilities of the pool:

PoolId addPool(
    folly::StringPiece name,
    size_t size,
    const std::set<uint32_t>& allocSizes,
    const MMConfig& config = {},
    std::shared_ptr<RebalanceStrategy> rebalanceStrategy = nullptr,
    ...,
);

The allocSizes determines the allocation classes available to this pool, that is, the chunk sizes it supports. Note that it takes a set because it doesn’t make sense to have 2 classes with the same size. The MMConfig config is for the eviction policy (see Eviction-Order Container) and the others are related to rebalancing (see Rebalancing).

Index

The index is a hash table which conceptually maps a key to the chunk holding the value. The implementation is a fixed size array of 32-bit integers. The array size represents the number of buckets and it’s fixed throughout the cache lifetime. So when we insert a key into this array we hash the key to an integer, and take the modulo with the bucket count to find the index.

The 32-bit integer is used to store the location of a chunk. The 16 least significant bits identify the index of the slab in the global slab array while the 16 most significant bits identify the index of the chunk within that slab. With this addressing only $2^{16}$ or 65,536 slabs can be addressed, but we mentioned there can be up to $2^{32} - 1$ (see Slab). In this case a different address mechanism is used but we’ll not discuss it here.

To insert an entry in the index, the key is hashed and a bucket id is computed, and then the corresponding entry on the array points to the chunk address. If there was already a chunk at that bucket, the new chunk’s “next” pointer will now point to that previous chunk. In other words, on collisions we insert at the head of the linked list, like in a typical hash table.

Eviction-Order Container

Conceptually an eviction-order container is a doubly linked list containing the elements of a given pool-allocation class pair. Each such container implements different eviction policies, but let’s assume it’s LRU (least recently used) for simplicity.

At any given time, the order in this list represents the eviction order, such that the last element on the list will be evicted first when needed. So assuming LRU, whenever an item is inserted in the cache, it’s inserted at the head. The container has a pointer to both the head and tail of the list.

The problem with eviction policies is that we often need to update the order when we read from the cache. Suppose we read a given chunk belonging to a linked list. We need to move it to the head of the list. This can be done in $O(1)$ because we get access to the chunk via the index and the “prev” and “next” pointers are part of the chunk. So we just do some pointer stitching to move it to the head.

Data Flows

Let’s now cover a few data flows, the main one being insertion and see how the components fit together.

Insertion

When we call cache.allocate(pid, key, size) like in the example, it will internally ask the pool corresponding to pid for a chunk of at least size amount of memory. The pool will look at the different size classes it has and will ask the one with the smallest size that is greater or equal to size.

Within the class, the request for a new chunk is: if freedAllocations is not empty it returns the top of the stack. Otherwise, it gets a new chunk on the current slab. If the current slab is full, it chooses a free slab and makes it current. If no free slabs remain, the pool will try to give it more slabs.

The pool has its own set of free slabs. If it has it available, it gives it to the allocation class. If not and it’s within its budget, it requests to the slab allocator which has a global set of free slabs.

If no such slab can be found, then the cache might try to evict items from the allocation class. In Eviction-Order Container we mentioned how chunks are kept in “eviction order” so it will give that chunk to the requester. It’s not always possible to evict a chunk so it may still fail to return one.

It will not insert the item in the chunk until insertOrReplace() is called, so it will not update the index-linked-list nor the eviction-linked-list until this method is called. This means this item is not “visible” to other threads until then, but its chunk is reserved.

Existing Key. One interesting difference in behavior from a hash table is that allocate() does not check if the key already exists in the cache. It first acquires a chunk and then when calling insertOrReplace() the old item is removed.

Eviction

Let’s focus on a flow mentioned during insertion: eviction. As we’ve seen the most common way to evict an item is when we run out of available space. Before we return it to the requester, we need to remove the chunk from the eviction order container’s doubly linked list and from the linked list on the allocator class.

An entry can be explicitly removed via remove() or via insertOrReplace(): recall that it allocates a new chunk and then removes the old one, it doesn’t update the chunk in-place. In these cases, the chunk is also added to the freedAllocations of its allocation class. It might need to update the index too (if this was the first chunk on the list).

There’s also a background thread, the reaper, which runs every 5 seconds by default. It traverses the array of slabs and within each slab the array of chunks. Within each chunk it will check the item’s TTL and if it’s expired it gets evicted.

Lookup

A lookup for a key consists of hashing the key, finding the right entry in the index and then traversing the corresponding linked list formed by the items, until we find the one matching the key. A handle is then returned to that item from which we can read the data.

As we discussed in Eviction-Order Container, the item might need to be moved depending on the eviction policy. For policies such as LRU it can be done in $O(1)$.

Rebalancing

Rebalancing is done by a background thread that runs every second. For each pool, it transfers slabs from the most empty class to the most full one.

If the source class has slabs in its free slabs list, the move is straightforward. If any of the active slabs is actually empty, it’s chosen. If it has some items in it, they’re std::moved to a different slab (defragmented) and this slab is chosen.

Concurrency

In describing the data flows above we glossed over the intricacies of concurrency. CacheLib is designed to support multiple threads at a time so some designs that may seem arbitrarily complex might make sense in light of thread safety.

Index and Eviction-Container Locks

The first layer of lock is on the index table. In theory we could have one lock per row, but if we use a mutex, it’s 4 bytes per row, which would double the memory size of the index table. On the other hand, if we locked the entire table with a single lock we’d run into massive contention. A middle ground is for a lock to be responsible for a subset of rows. There’s contention only for rows on the same set, but we use fewer locks.

During a lookup, it acquires a read lock on the index to find the right chunk to retrieve. Note that this conceptually gives a read lock to the index-linked-list associated with that bucket. Implementation wise, the “next” pointer for the index-linked-list can only be used after acquiring the appropriate lock.

To “move” the item within an eviction-order container, a write lock is acquired, which analogously gives write access to the eviction-linked-list, and that is implemented by requiring a lock to read/write the “prev” / “next” pointer for that list.

For the put() it needs to acquire a write lock on the index in addition to write locks on the eviction-order container. There are several other locks involved, especially when a new slab is needed, but the linked list ones are the more interesting.

Item

The ItemHandle returned by cache.allocate() has a reference count. If the reference count is non-zero, then the cache won’t evict the corresponding item.

Recall from Data Flows > Insertion that when we do cache.allocate(pid, key, size) we don’t update the linked lists, so effectively the ItemHandle is not visible to other threads. So doing

std::memcpy(handle->getMemory(), value.data(), value.size());

in put() is thread safe. Note that it’s possible multiple threads call put() on the same key, and the last one to call insertOrReplace(), which is thread safe, will win.

Flash

All we’ve discussed so far is about the structure in memory. CacheLib has a second layer of caching backed by Flash. We won’t cover too many details in this post though.

When an eviction happens in memory, there’s an option to save the data in flash. There are some tricks described in [1] to avoid writing to flash excessively due to limited write lifetime.

Once the entry is written to flash it’s also written to an in-memory per-bucket Bloom filter. During lookup, when the in-memory lookups fail, it will check if the entry is on the bloom filter.

If yes, there’s a chance it exists in flash, so it tries to read the entry from flash. If a match is found, the entry that was in flash is moved to memory again.

Conclusion

I’m having a lot of fun studying these data structures such as CacheLib and F14Map. They have lots of interesting tricks to make it efficient and perform well under concurrent use. I especially liked the fact that an item is a node in multiple linked lists.

These complex data structures also make me think of the joke that tech interviews ask interviewees how to reverse a linked list but that no one uses that in their job. To be fair this is pretty rare or unheard of for many programmers but I found the deeper one goes on the stack the more likely they’ll need Computer Science knowledge.

I was surprised that the paper focuses so much on unification and use cases instead of the technical details (the exception seems to be about writing to flash). Maybe because these are standard tricks in cache implementation, but they felt all novel to me.

References

• [1] The CacheLib Caching Engine: Design and Experiences at Scale
• [2] Github: CacheLib

Related Posts

There are a lot of similarities in how systems memory allocators manage memory. One of them is hierarchy: we see them in arenas in Jemalloc and pools in Velox: Memory, the latter having an entire tree of hierarchy. Velox also has disk spill capabilities, much like CacheLib can “spill” to flash.

At a very high level, an in-process cache is a hash table, but it has substantial differences from a general purpose hash map such as Folly F14 Map. It typically has a fixed size and it evicts entries automatically, which leads to very different design decisions.

Memory allocators also have to worry about fragmentation, which can lead to inefficient use of space. This is also a concern of the Buddy Memory Allocation.

In terms of similar use cases, the CPU also has a cache, as we’ve studied in CPU Cache. We also discussed CDNs before in Content Delivery Network.

Finally, speaking of nodes that belong to multiple linked lists, we talked about Dancing Links in The Algorithm X and the Dancing Links which is a way to represent sparse matrices.

Source code | RSS feed | Tags: c++ data structures