Modern Cache Management Designs for Web Applications

Written by K Jagadeesh, Pruthvisampath, Kirti Agarwal

Hyperbolic Cache: Flexible Caching for Web Applications, Aaron Blankstein, Siddhartha Sen, and Michael J. Freedman, USENIX ATC’17.

Memshare: a Dynamic Multi-tenant Key-value Cache, Asaf Cidon, Daniel Rushton, Stephen M. Rumble, Ryan Stutsman, USENIX ATC’17.

The CacheLib Caching Engine: Design and Experiences at Scale, Benjamin Berg, Daniel S. Berger, Sara McAllister and Isaac Grosof, Sathya Gunasekar, Jimmy Lu, Michael Uhlar, and Jim Carrig, Nathan Beckmann, Mor Harchol-Balter, and Gregory R. Ganger, USENIX OSDI’20

Modern Web Applications

Modern web applications are ubiquitous, important and diverse and they rely aggressively on caching for reducing latency and load balancing at the backend. But the requirements of each application is different. Significant performance gains can be achieved with application specific tailored strategies rather than using the existing ones which are fundamentally limited due their reliance on data structures to maintain ordering of cached objects.

What are the issues in traditional caching strategies ?

Algorithms like LRU, recency-based, use last access time for ordering which is difficult to customize in terms of cost as they use total misses as the cost. They perform very well generally but on stable, memoryless distributions are outperformed by frequency strategies. Algorithms like LFU, frequency-based, is easier to modify but non-local changes to priorities are expensive for data structure re-orderings. They punish new items as it has lower priorities since it has been accessed fewer times than the older items but may have high requests in future. Also, old items survive even after dropping importance even though they maybe of no use in future.

Let’s discuss the three different solutions that the papers mentioned above have demonstrated with regards to different application types.

Hyperbolic Caching

A new caching algorithm has been designed, which incorporates random sampling with lazy evaluation of cache item priority, called Hyperbolic caching.

It incorporates the time an item spends in the cache due to which data structures cannot be used for ordering since the order changes continuously. Hyperbolic caching can be customized by customizing the priority function by addition of extensions, for e.g. cost of items, item expiration time and windowing.

Hyperbolic caching with customizations has been found to reduce the miss rates by 10–20% and increase end-to-end throughput by 5–10%. It focuses on how important an object is, and not data structures. The priority function is defined as follows:

Customizing Hyperbolic Caching

Cost- Aware Caching: Different items may incur different penalty cost when a miss occurs. This can be due to their CPU or database load on misses, different item sizes or different origins. In real world applications, two of them benefit from cost awareness: first is the set of applications using Memcashier which uses cost(i) = 1/s(i) where s(i) is the object size. The second application is Viral Search(Microsoft internal website), which displays viral stories from twitter.

Priority Function for Cost-aware Hyperbolic caching

Cost Classes: Costs of items can be related to each other. Hence instead of measuring individual item costs, group of items can be associated with cost and performed can be measured for each class. Two main advantages of using cost classes are: change to a class’s cost is immediately applied to both new and already in cache items and updating whole class is very easy.

Priority Function for Cost-class Hyperbolic caching

Expiration-aware caching: An expiration time can be specified for cache items which will prevent staleness by telling how long the item is valid. In case of eviction of similar popular items, it is less costly to evict item which expiring soon than the one which is expiring later. The priority function can be modified as below where α is a parameter controlling how quickly to degrade the value of future requests.

Priority Function for Expiration-aware Hyperbolic caching

Performance

Performance of caching is determined by the workload and the caching algorithm, which is the eviction strategy used when cache is full. The services, such as Memcached, Redis, Guava, Varnish, use inflexible caching algorithms like LRU which is limited since it relies on data structures for ordering cached items and their priorities are only changed when they are accessed.

Miss Rate performance compared to LRU

Dynamic Multi-Tenant Key-Value Caching Mechanism

DRAM key-value caching mechanism is an integral part of web application infrastructure. In-memory cache managers are employed on the backend to utilize pool of cache clusters and reduce the latency introduced by multiple reads on hard disks. It does this by caching the frequently used data objects in DRAM memory (which is 100 times faster than magnetic hard disk) and providing it to the application without making repeated seek calls to the hard disk. Since, the original data is bound to change sometimes, the cache manager caches the data objects for few minutes or until the original data gets changed. Memcached, Redis are a few examples of cache memory managers which manages the memory themselves and provides cache as a service to the applications.

[embed]

Sometimes the hit rate of the cache management can become a bottleneck to the application performance. Let’s say we have an in-memory cache manager which achieves 98.2% hit rate. With an average cache latency of 100 µs and an access time of 100 ms for MySQL server, if we were able to increase the hit rate by 1%, it would improve the application performance 1.5 times and reduce the latency by 36%.

Speedup of mechanism 2 compared to mechanism 1

The standard way to implement a caching strategy for various applications is to split the cache memory into many partitions and allocate each partition to one application. Let’s say there are 4 applications A, B, C and D and we have a cache memory of 2GB. The cache management server will split the 2GB memory into 4 segments and allocate 500MB to each application. We call this fixed partitioning strategy where part of the memory is reserved for one application and cannot be shared by other applications. One major drawback of this approach is it will be very inefficient for bursty applications where one application might need more than the allocated cache portion and other application is simply not utilizing most of the allocated space.

Here, we discuss about the cache management strategy employed in Memcached, a cache management application and talk about its limitations and finally discuss about a new approach called MemShare which efficiently manages cache memory for multiple applications using dynamic pooling allocation strategy instead of fixed partitioning.

There are two policies to allocate cache memory to applications one is fixed partition policy where each application is allocated a cache memory segment and is not shared by any other application, the other way is pooling policy in which the entire cache memory is shared among all the applications. In fixed partition policy, cache memory will be under-utilized when there is huge difference between the number of hard-disk seeks among applications. In pooled policy, when an item comes from one application, it might evict an existing item of another application thus resulting in unfair treatment toward different applications.

MemShare combines the best of partition policy and pooled policy to create a new hybrid policy to share the cache memory among different application. It splits the cache memory into two partitions namely reserved partition and pooled partition. The reserved partition is again split into different chunks and allocated to each application thus guaranteeing minimum memory for each application. And the pooled memory portion will be shared among all the applications. The goal is to allocate the pooled memory to application which needs it most and reduce the cache miss rate. MemShare also employs a policy where it can claim the reserved portion of an application if that application is not utilizing it.

MemShare usage of Cache Memory

Cache management servers such as Memcached employs slab-based allocation to manage the cache memory among its tenant applications. In slab based allocation, the memory is treated as a series of 1 MB slabs and each slab is split into fixed size chunks according to its size class. The class units are of the form 64x2^i such as 64, 128, 256 and so on up to 1 MB. This is to avoid internal fragmentation introduced if we allocate entire 1MB for small data objects such as 100Bytes. So, a data object is cached in smallest possible slab class which can contain it. For example, a data object of 110 Bytes is cached in 128 Byte slab class chunks. LRU queues are maintained for each slab class and used for eviction policy.

Now imagine a scenario where 100MB cache is partitioned for two applications where each application is allocated 50MB. In a shared cache policy, if we want to cache 4KB data object of application 2 in application 1 portion, we need to evict an entire 1MB of application because LRU queues are maintained for entire slab. The main caveat here is the to-be-evited 1MB slab can contain data objects which are hot i.e., currently in use by application 1. This problem can even occur during eviction in the same application. That is why slab allocation strategy is not efficient for shared cache management, so MemShare uses a log-based approach to efficiently manage pooling cache portion which is shared by multiple applications.

Eviction of App 1 slab by App 2 data object

Memshare: hybrid approach for cache management

MemShare has two core components namely Arbiter and Cleaner. Arbiter determines how much memory should be assigned to each application (targetMem) and Cleaner prioritizes which memory segment should be cleaned from the applications which are using too much cache memory. Instead of slab-based allocation, MemShare uses a log-based allocation strategy to manage both reserved and sharable portion of cache memory.

MemShare views the entire cache memory as a sequence of 1MB blocks. In log-based memory management, data objects are inserted as they come. It maintains a head pointer to the empty offset of the active 1MB block. If the newly arrived data object cannot be fit into the current block, the head shifts to the next block and caches the data objects from there. This helps in simpler implementation of data structures which stores application wise cached key-value data objects. During this, the data objects to cache can come from different application, so the log is intermixed with data objects of different applications. Arbiter maintains a hash table per application to map data object key to cached data object memory region.

Log based allocation strategy

During eviction, the Cleaner chooses randomly selected n consecutive 1MB blocks and outputs at least (n-1) blocks thus effectively freeing at least one block. The Cleaner is usually put to work when the number of free segments fall below 1% of total cache memory segments. In the image below, the cleaner has picked up 4 blocks and empties one data block. Some of the data objects in 4 blocks are copied to 3 data blocks. The data objects to copy and the data objects to discard are determined by eviction policy. This is usually calculated by rank of a data object and memory need of an application. We can use LRU, LFU or any other policy to determine the rank of the data objects of an application.

Cleaner relocating data objects and freeing data segments

The arbiter determines the memory needed by an application based on the need of the application. It calculates need of an application as follows.

Where actualMem is the actual number of bytes currently storing items belonging to the application, and targetMem is the number of bytes that the application is supposed to be allocated. In the case of partitioned resource allocation targetMem is constant. The arbiter ranks applications by their need for memory; the cleaner prefers to clean from segments that contain more data from applications that have the lowest need.

But, how to determine targetMem of an application? To determine the targetMem Arbiter maintains a shadow queue for each application. Once data objects of an application are evicted from cache, their keys are stored in shadow queue. For example, imagine an application has 10,000 items stored in the cache, and it has a shadow queue that stores the keys of 1,000 more items. If a request misses the cache and hits in the application’s shadow queue, it means that if the application had been allocated space for another 1,000 items, the request would have been a hit. So, shadow queue hit rate gives a total approximation of the targetMem of an application.

Each application is initially given a portion of pooled memory. For each cache request that is a miss, the application’s shadow queue is checked. If the key is present in the shadow queue, that application is assigned a credit representing the right to use a small portion of pooled memory. The Cleaner uses targetMem to choose which applications to evict items from.

In a nutshell, MemShare allocates memory according to need of an application and makes efficient utilization of cache memory. It employs efficient log based cache memory allocation compared to slab based allocation. It is implemented as a wrapper around MemCached library and implements its own allocation strategy, Arbiter and Cleaner modules.

CacheLib

Web services rely on caching at nearly every layer of the system architecture. Large web service providers like facebook, amazon, reddit etc consist of a number of subsystems. Caching is often used in these subsystems to improve performance and efficiency. However these individual caches are maintained independently by a separate team and are highly specific to the domains they are implemented in. Traditionally it was believed that implementing the caching systems this way, that is, maintaining them independently for different use cases is ideal as different cache implementations are specialized for different use cases and require different features. But, these caches share common challenges which are being addressed independently. By solving these common challenges independently , teams repeated each other’s efforts and produced redundant code. So to handle this, CacheLib has been proposed. It has already been employed at Facebook.

CacheLib is a general purpose caching engine which combines these different features and functionalities required by different cache systems implemented in different use cases into a single C++ library.

So while developing a cache system for a use case, the development team can take the required features and functionalities from various features, functionalities that CacheLib provides.

Different types of cache systems and their use cases

Let us first understand various use cases of a cache system in a web application like facebook. Some of cache systems that are used in by facebook for different use cases are mentioned below:

1. Hierarchical and geo-distributed caches : Used in facebook’s Content Distribution Network (CDN).
2. Application look-aside caches.: Used in web applications to cache database queries, user data, usage statistics etc.
3. In-process caches : A special type of cache used for applications that cannot tolerate RPC overhead of a remote cache.
4. Storage-backend cache : Used in storage servers.

Apart from these there are many other caches systems for other use cases too. CacheLib handles these diverse use cases by providing a library of components that makes it easy to rapidly build performant caches.

Despite the diversity in use cases, cache systems share some features and functionalities in common like :

1. Massive Working Sets : A working set describes the set of objects in a workload which are popular enough to benefit from caching.
2. Size variability : Object size variability is one challenge that is common across different use cases.
3. Bursty Traffic : Facebooks’s traffic is highly bursty and all the cache systems in different use cases face this challenge which can be solved centrally and efficiently.
4. Resource Management : All cache systems use hardware resources like DRAM and flash memory which are to be managed. A common deployment scenario includes caches as well as application processes, and the kernel, all of which consume DRAM. In such a scenario the DRAM memory must be managed between the caches and application process dynamically so that efficient utilization of resources is achieved.
5. Computationally Costly Query for Empty Results : There are certain queries which are complex while executing but at the end output empty results. These occur often in database systems. Such queries are typically computationally costly for the backend database. Failure to cache empty results would thus lower the cache hit ratio significantly. This is handled in CacheLib using the idea called negative caching.
6. Support for Data Structures : Caches should support structured data by providing support for different data structures. This is particularly important for in-process caches that directly interact with application data structures.
7. Frequent Restarts : Caches often restart frequently to incorporate code fixes and updates. These are common in production caches. Most caching systems are transient and lose data once the system restarts. In such scenarios, warming up the cache takes a long time (hours or even days) for the cache hit ratios to stabilize.

Above mentioned are some challenges that caching systems for different use cases share in common. Although not all caching systems exhibit all the above mentioned challenges, each use case exhibits multiple challenges from mentioned above. So its efficient to come up with a general approach in solving these problems (CacheLib).

Let us see some features of CacheLib library to handle above mentioned challenges.

1. Thread-safe cache primitives: CacheLib provides a thread-safe API for reads, writes, and deletes to support consistency during concurrent calls to CacheLib API.
2. Hybrid Caching : CacheLib uses hybrid caches composed of both DRAM and flash caches in order to handle large working sets and still achieve decent cache hit rates.
3. Low resource overheads : This feature is helpful in case of inprocess caches where cache and application processes share DRAM resources. Low overheads enable cache to support working sets containing a large number of small objects.
4. Structured items : CacheLib provides support for data structures like arrays and hashmaps which will make it easier while caching structured data.
5. Dynamic Resource monitoring, allocation, and OOM protection : In scenarios where caches share memory with processes, CacheLib monitors and dynamically allocates the memory for caching so that there won’t be any crashes due to temporary spikes in memory usage.
6. Warm restarts : In environments where updates and code fixes are common and involve frequent cache restarts, CacheLib provides warm updates that retain cache state so as to overcome the need to warm up caches every time they are restarted.

Cache API Design : The CacheLib API is designed to be simple enough to allow application programmers to quickly build in-process caches, incorporating the required features for the particular use case out of a number of features and functionalities that CacheLib provides.

The API centers around the concept of an Item, an abstraction of a cached object. The access to an item is controlled by ItemHandle. ItemHandles enable referencing of items. Whenever an item is constructed or destroyed the reference counter corresponding to that Item is incremented or decremented. An Item cannot be evicted unless its reference count is 0. Some functions to manage cache objects are :

1. allocate : To insert a new object into the cache, allocate may first evict another Item according to some eviction policy and then memory is allocated to the new item. The new Items only become visible after an insertOrReplace operation completes on a corresponding ItemHandle.
2. remove : The remove call is used to delete an item from the cache.
3. find : The find call is used to find an item (identified by a key) in the cache.
4. To update an Item, one would allocate a new ItemHandle for the key they wish to update, perform the update using getMemory, and then make the update visible by calling insertOrReplace with the new ItemHandle.

CacheLib’s Caching Implementation

Architectural Overview of CacheLib : CacheLib consists of a DRAM cache and a flash cache. The flash memory is further composed of Large Object Cache (LOC) for Items above or equal to 2KB in size and Small Object Cache (SOC) for Items below 2KB in size .

• When an allocate request comes for an item, memory is allocated on DRAM evicting another item if necessary. The evicted item is sent to flash memory or is discarded.
• When a find request comes, first the DRAM is checked and then the flash cache is checked.
• If the item is found in DRAM the ItemHandle corresponding to that item is returned.
• If the item is found in flash cache, the item is first fetched into cache and the ItemHandle is returned
• If the item is not found in both DRAM and flash caches, an empty ItemHandler is returned denoting a cache miss.

Different cache systems are managed independently by different teams but they share some common challenges. The above approach comes up with a generalized CacheLib library to handle these common challenges. It is to be noted that such generalized approach may result in loss of certain domain specific optimizations for the cache systems, but it could reduce development overhead and increase synergistic efficiency between systems.

Conclusion

Caching is very important in web applications to achieve fast response times. In today’s world, web applications are very important to people hence it’s speed is essentially important.

We discussed three papers incorporating three cache management designs namely Hyperbolic Cache, MemShare and CacheLib.

Hyperbolic Cache focuses on prioritizing items, improves caching performance on web-like workloads and allows for a multitude of easily constructed variants.

MemShare, a dynamic cache management approach implements multi-tenant key-value cache that optimizes share for highest hit rate, provides minimal guarantees and uses novel log-structured design which uses cleaner as enforcer.

Cachelib, a widely used general-purpose caching engine that extracts common caching functionality, aggregates optimizations, reduces the cost of caching and is widely used at Facebook.

These are a few modern approaches we discussed, there are plenty more out there!