Understanding Application-level Caching in Web Applications: a Comprehensive Introduction and Survey of State-of-the-art Approaches

The simplest programmatic approach for application-level caching consists of the use of abstract solutions such as design and implementation patterns. Recent work done by Mertz and Nunes (2016) provided practical guidance to developers as patterns and guidelines to be followed while designing, implementing and maintaining application-level caching, derived from a set of existing web applications that use application-level caching. Although simple, patterns are abstract solutions and require a significant amount of changes in the base code to be adopted, which may not provide an adequate degree of transparency and flexibility to developers (Pohl, 2005). To provide concrete support, libraries and frameworks have been developed, providing useful and ready-to-use cache-related features. Redis³³3https://redis.io/, Memcached, Spring Caching⁴⁴4https://docs.spring.io/spring/docs/current/spring-framework-reference/html/cache.html, EhCache and Caffeine⁵⁵5https://github.com/ben-manes/caffeine are popular examples of libraries and frameworks. For a deeper analysis of typical cache systems and libraries, as well as their main techniques regarding data management, we refer the reader to elsewhere (Zhang et al., 2015b).

Typically, concrete solutions provide an in-memory storage component along with methods that allow to put and get arbitrary content, identified by a key, i.e. a hash table. The key benefit of such implementations is that they are: (a) flexible, because different types of content can be stored, ranging from database query results to entirely generated web pages; (b) simple; and (c) scalable. Besides being storage units, these caching solutions also provide support to basic caching issues, such as memory allocation, eviction policies, and size limitations. Despite these advantages, adopting such solutions still require a programming effort to manage the cache and couples caching concerns to the base code, which adds complexity and reduces the possibility of reuse within it (Ports et al., 2010; Wang et al., 2014).

Distributed key-value stores (or caches) have become popular for supporting large-scale web applications because they can easily scale up—i.e. they can be distributed to multiple servers, which means it can linearly scale to handle greater transaction loads—and cache a significant portion of user requests, improving hit ratios and response time. Such distributed caches are an essential component in the infrastructure required by large enterprises such as Netflix⁶⁶6http://techblog.netflix.com/2016/03/caching-for-global-netflix.html, Facebook (Nishtala et al., 2013) and Twitter⁷⁷7https://github.com/twitter/twemproxy. Besides design, implementation and maintenance issues of application-level caching, there is research work that proposes and improves cache components in the context of distributed infrastructures (Zhu et al., 2012; Fan et al., 2013; Xu et al., 2014; Li et al., 2015). These approaches are not further discussed in this survey, given that our focus is on issues specific to application-level caching, and not broad caching issues, such as storage, concurrency management, and other topics of distributed systems. Such topics have been widely researched and addressed by other communities (Zhang et al., 2015a; Abdullahi et al., 2015).

Applications can also be developed with business logic at the client-side, typically with the support of JavaScript frameworks. Popular frameworks provide features to develop complex and sophisticated applications. However, caching configurations are usually specified by the content provider (web server that received the request) in the header of the response, and caching is automatically done by browsers, which are limited to caching cache entire web pages or request responses. To increase the flexibility regarding the customization of caching configurations at the client-side, Huang et al. (2010) proposed a caching framework in which developers can define the appropriate strategy among pre-defined possibilities. Similar to the caching provided by browsers, the proposed framework does not require developers to manage the cache content manually but allows customizations, such as setting cache granularity and eviction policies. Huang et al. (2010) also proposed an approach to adaptively deal with consistency management, which is better explored in Section 3.3.

Compositional approaches can partially relieve the developers’ burden by automating tasks through declarative or seamless approaches. The former is based on the provision of knowledge associated with the semantics of application code and data. In this case, annotations referred to as assertions or contracts, are used to describe application properties, which can be processed at runtime to execute specific tasks without coupling the caching logic with the application base code. Such annotations have become widely adopted in dynamic programming languages (Stulova et al., 2015). CacheGenie (Gupta et al., 2011) is a system that provides a higher level of abstraction for caching frequently observed query patterns in web applications. These abstractions take the form of declarative query objects and, once developers specify them, insertions, deletions, and invalidations are done automatically. CacheGenie is based on triggers inside the database to automatically invalidate the cache, or keep it synchronized with the data source, as expressed by the developer in the application code. Similarly, Ports et al. (2010) proposed TxCache which offers for developers a simple way to indicate database query functions as cacheable, and then TxCache automatically manages and caches those marked function results. CacheGenie and TxCache also provide automatic consistency management, which is better explored in Section 3.2.

Seamless solutions are those that are coupled to the application in a transparent way, being added to the application, for example, as a surrounding layer, similarly to, e.g., a database and web proxy, without the need for refactoring application code. Such solutions are especially useful in scenarios in which the application was not conceived to use caching since the beginning, and requests for performance and scalability improvements emerged after many releases. In this context, middleware-based approaches that integrate two or more layers of a web application have been proposed as easy-to-use and transparent solutions to deal with caching (Huang et al., 2010; Wang et al., 2014). Furthermore, aspect-oriented programming (AOP) (Kiczales et al., 1997) has been explored by increasing modularity with an improved separation of cross-cutting concerns. As caching is fundamentally a cross-cutting concern, Bouchenak et al. (2006) and Surapaneni et al. (2013) demonstrated the use of AOP to develop caching solutions. Such approaches come as an alternative to refactoring the application with the introduction of programmatic approaches. Although faster results may be obtained with transparent solutions, they can be hard to support and tune, because system administrators, or even developers, might need to be specially trained or experienced in particular caching solutions and scenarios to configure them properly.

A non-exhaustive survey on database and mid-tier transparent approaches are presented by Ravi et al. (2009), while Ali et al. (2011) surveyed some studies of proxy-level caching. We complement such surveys with seamless approaches that consider application-level specificities, which are better explored in Sections 3.2 and 3.3, given they also provide static or adaptive solutions to design and maintenance of application-level caching.

Although programmatic and compositional approaches focused solely on implementation issues can raise the level of abstraction and, consequently, reduce a significant amount of caching logic to be added to the base code, they still require design reasoning, such as deciding whether to cache content and ensuring consistency. Therefore, a more fine-grained solution would require reduced effort and input from developers, which are the focus of the approaches described next.

There are two main ways of helping developers select cacheable content: providing caching recommendations, or providing an automated admission by automatically identifying and caching content. Table 1 summarizes the caching approaches that deal with admission issues.

The first way of helping developers while admitting content in the cache is by recommending improvement opportunities. Approaches in this context are usually based on the analysis of application profiling information, which can capture application-specific details through monitoring its execution when facing different situations. Traditional profiling approaches typically record measurements of method calls. Usually, cost measurements are captured with calling context information, which conveys the hierarchy of active methods calls of a request.

Della Toffola et al. (2015) addressed this problem by identifying and suggesting method-caching opportunities. Their approach, called MemoizeIt, is based on comparing inputs and outputs of method calls and dynamically identifying redundant operations, according to specified thresholds. To prevent the expected overhead of the approach, which implies a comparison of all method invocations, MemoizeIt analyzes the collected executions level by level through iterations. First, it compares input and output objects without tracking dependencies, and then iteratively tracks deeper dependency levels of objects that remain under the specified thresholds. By doing this, MemoizeIt can explore the application traces faster to define a set of methods that would provide benefits if cached. Also by analyzing method calls in an application profile, the work of Maplesden et al. (2015) can identify the entry point to repeated patterns of method calls, which are called subsuming methods and are identified by analyzing the smallest parent distance among all the common parents of a method.

Xu (2012) focused on a common problem in object-oriented applications, in which an allocation site creates data structures with the same content repeatedly, but in different moments during an execution. He follows the same principle of helping developers with a report, which lists the top allocation sites that create such data structures. Then developers can manually inspect the code and implement the appropriate solution to improve performance. Cachetor, proposed by Nguyen and Xu (2013), addresses repeated computations by suggesting spots of invariant data values that could be cached for later use. They proposed a runtime profiling tool, which uses a combination of dynamic dependency and value profiling to identify and report operations that keep generating identical data values. However, Cachetor makes strong assumptions about the programming language, such as the presence of a specialized type system, which is not valid in dynamically-typed languages. Infante (2014) addressed this type system restriction by proposing a multi-stage profiling technique that uses dynamically collected data to reduce the profiling overhead.

Although these approaches can reduce complexity and time required by caching design, developers should still review the recommendations, decide whether to cache or not the suggested opportunities and integrate the appropriate caching logic into the application. Thus, a second way of helping developers while dealing with content admission is to automatically identify and cache the cacheable content, as opposed to just report potentially cacheable methods. Such approaches require not only ways to analyze the application behavior, but also mechanisms to manage cache and application at runtime.

Guo and Engler (2011) achieved this by implementing a customized Python interpreter, namely IncPy, which includes an approach to identify and cache repetitive creation or processing of data files stored on disk. Such disk accesses may lead to long-running method calls resulting in bottlenecks. Thus, at runtime, it monitors and analyzes disk operations based on heuristics regarding safeness and worthiness, which are used as reference to cache and evict content. Similarly, Scully and Chlipala (2017) proposed Sqlcache, which consists of a compiler optimization that is able to analyze the application code and generate the appropriate caching logic for database queries. However, Sqlcache is specifically proposed and implemented to web applications in the Ur/Web⁸⁸8http://www.impredicative.com/ur/ programming language.

EasyCache (Wang et al., 2014) combines properties of database caching with application-level specificities to provide a mid-tier mechanism, which caches database queries and translates it into application-level objects in a seamless way. Such approach is built on top of a popular application programming interface to access databases, and thus does not require any modification of the application code. As it is delivered as a caching layer over the integration between application and database, it is able to inspect all the text from database queries that comes from the application in order to automatically find cacheable queries and maintain consistency. However, in order to keep the approach feasible regarding memory and network bandwidth, complex queries (e.g. nested and statistics queries) are unsupported, as well as large objects. Moreover, because it is implemented at a lower level, as a Java Database Connectivity (JDBC) driver, the approach does not work with object-relational mapping frameworks (despite the authors argued that the integration is feasible), which are commonly used while implementing web applications.

Also based on JDBC, Bouchenak et al. (2006) used AOP to implement a middleware support for caching, named AutoWebCache. Such middleware is based on intercepting web application servlets as well as database queries through JDBC. AutoWebCache then automatically integrates front-end and back-end by analyzing the queries to identify cacheable web pages. Furthermore, such analysis gives the content dependencies, which are used to trigger cache invalidations to maintain consistency with the back-end database. Despite built to support only databases as source of information, this approach is generic enough to be implemented with other types of sources. Furthermore, AOP is used by Surapaneni et al. (2013), which described an approach to cache the results of join sub-queries, with the goal of caching partial query results, rather than whole queries. Such approach identifies cacheable sub-queries based on a cache factor, which takes into account monitored information such as frequency, cost of updates and an estimation of selectivity (calculated through histograms built from observed collections of data at runtime) of sub-queries.

We can classify static application-level caching consistency approaches as relying on two main techniques: expiration and invalidation. The former provides higher availability by allowing stale data to be returned from the cache. The latter ensures that no stale data is returned by identifying when the underlying data source is modified and evicting related cached items. For more detailed information regarding web caching consistency concepts, please refer to Appendix A. Table 2 summarizes the caching approaches that address these problems of dealing with consistency management.

Ports et al. (2010) introduced TxCache, which consists of a caching approach with transaction support for data-driven web applications. TxCache associates cached content with invalidation tags, which indicate content dependencies. Every query processed in the database server, if not read-only, is returned along with its invalidation tags, which indicates content that is affected by the write operation (e.g. insertions, updates and removals). Write operations trigger invalidation processes that take the invalidation tags and evict all the related content in the cache, based on the presence of such tags. By doing so, TxCache provides a validity interval for cached content, instead of defining an arbitrary expiration time. Unlike TxCache, CacheGenie (Gupta et al., 2011) keeps consistency by performing in-place updates rather than invalidating and recomputing data. CacheGenie is integrated with the object-relational mapping module provided by the web framework Django⁹⁹9https://www.djangoproject.com/ and takes as input caching configurations for each application object that is mapped to the database through a key-value structure. Such specification contains strategies, dependencies and other meta-data about caching and are used to automatically creating triggers within the database to evict and update cached data. Furthermore, CacheGenie also provides a weak consistency approach based on the definition of an expiration time, considering that many web applications do not require strong consistency approaches.

Instead of requiring developer inputs, Leszczyński and Stencel (2010) described an approach to cache data, which keeps it in a consistent state based on a dependency graph that provides a mapping between update statements in a relational database and cached content. When a database update is performed, the graph allows detection of cached content that must be invalidated to preserve the consistency of the cache and the data source. Also focused on keeping consistency by using the database as source of information, Wang et al. (2014) and Bouchenak et al. (2006) both propose solutions in the form of a middleware, which monitors database queries through JDBC and, based on the analysis of queries to track content dependencies, it triggers invalidations of all cached content that is related to a change, when a changing query is executed.

Although we in this survey do not explore approaches that focus on general caching issues such as concurrency, scheduling, and other distributed systems topics, there are infrastructure-related issues that developers usually need to configure or at least be aware of, when implementing application-level caching (Mertz and Nunes, 2016), being cache size one of them. Because caches are size-limited, two main decisions must be made: (i) the definition of the adequate cache size, and (ii) the choice of a replacement algorithm. Table 3 summarizes the caching approaches that address these problems of dealing with size limitation.

Regarding the first decision, Saemundsson et al. (2014) proposed an insight into how much memory is necessary to trade-off the desired performance. Their approach is based on an online profiler, called Mimir, which estimates how the popular least recently used (LRU) algorithm would perform with different ways of memory allocation, by continually exposing the hit ratio curve as a function of size cache. Thus, the approach allows what-if questions, providing dynamic estimations of the cost and performance regarding different cache sizes.

While cache size is a key to improve the cache efficiency, replacement algorithms are fundamental as well. Such algorithms are usually based on simple heuristics such as recency, frequency or even randomly. Popular and well-accepted examples of replacement algorithms are the already mentioned LRU and least frequently used (LFU). Even though replacement seems a solved problem (Podlipnig and Böszörmenyi, 2003), new proposals have been developed. Zaidenberg et al. (2015) presented a quantitative evaluation of alternative replacement strategies that consider both recency and frequency properties. They control data replacement through the management of different lists of cached items and levels of frequency and recency. The authors used LRU as a baseline and, according to benchmarks, the new proposals can increase the hit ratio. Despite this improvement, there are disadvantages, such as the sensibility to cache thrashing.

Recently, Li and Cox (2015) proposed GD-Wheel, a cost-aware replacement policy based on the greedy-dual size (GDS) algorithm. GD-Wheel brings the exact GDS in the context of application-level caches, given that GDS was initially proposed by Young (1994) for web proxy caches. In a nutshell, besides the benefits of LRU, GDS also takes into account the cost to retrieve a piece of content while selecting content to be evicted (Cao and Irani, 1997). Thus, GD-Wheel provides developers with a mechanism to include the cost information on each insertion or update in the cache. Such cost is taken into account in the replacement decisions. GDS works by maintaining a value of remaining priority $Rp$ for each cache entry. When inserting or reusing a piece of content $i$, $Rp(i)$ is defined as the cost of retrieving it $c(i)$. When an eviction is required, the piece of content with the lowest $Rp$ is evicted. After the eviction of $i$, all $Rp$ values of cached content are decreased by $Rp(i)$. By doing this, the algorithm integrates recency and cost to retrieve, because content with lower cost and not recently used has lower $Rp$ values, and consequently tends to be evicted faster.

A key limitation of the approaches presented in this section is that, due to the non-adaptive nature of these solutions, they do not automatically consider changes in application workload and access patterns, which can lead such approaches to a poor or sub-optimal performance before the revision of caching decisions. Furthermore, such approaches usually do not take application specificities into account and require human intervention for configuring, customizing and tuning the solution to the application requirements and needs.

Adaptive approaches address different caching issues and, for doing so, they analyze a particular property associated with caching. For example, if an approach focuses on consistency maintenance, it usually analyzes content changeability, because if the source of a cached content changes, it should be updated or removed from the cache. Based on this analysis, approaches adapt a particular task of cache management, e.g. definition of expiration time of cached item. This we refer to as adaptation target. Broadly, adaptive caching approaches aim at increasing the cache performance as a means of improving the application performance. Selected measurements are used to evaluate the cache performance, and are thus associated with the expected outcomes of a particular approach. We summarize the different adaptive caching approaches in Table 4, analyzing these discussed approach characteristics as well as give examples from literature.

Adaptation is usually driven by changes and behavior of the application environment and, therefore, monitoring this environment is needed. This is typically done by capturing the execution traces of an application or cache to be analyzed, and deciding which actions to take. Such traces allow retrieving input data for the analysis, which can be mainly of two types. The first is stateless data, which depend on the content that can be cached (e.g. the size of a query result, the frequency of a method call, and the recency of a requested content), and the second is stateful data, which are based on historical information. The most straightforward approach is to use historical access information regarding the observed web component, such as requested URLs or database queries (Baeza-Yates et al., 2007; Ma et al., 2014; Chen et al., 2016). Such monitored data can be easily obtained from web servers or database systems, which automatically store them in the form of weblogs. Moreover, the spatial locality can be used by analyzing the content context (Negrão et al., 2015). Although such contextual information can be useful, it requires a deeper analysis of the content being managed.

The analysis of monitored data requires the characterization of the execution of an application or cache. Such task can be done based on simple heuristics (Negrão et al., 2015), or by using sophisticated techniques, such as a mathematical model (Huang et al., 2010; Chen et al., 2016) and machine learning (Sajeev and Sebastian, 2010). Furthermore, static analysis of source code can also be useful (Chen et al., 2016). Such static analysis can reduce the complexity and processing required to achieve the caching decisions, i.e. reduce the learning phase. For example, while looking for cacheable opportunities, static analysis can provide a limited set of possibilities and places to look at, thus reducing the amount of data that should be analyzed, making the decision process faster and more efficient.

The decision can be implemented also with heuristics (Negrão et al., 2015), utility-functions (Baeza-Yates et al., 2007; Ma et al., 2014; Einziger and Friedman, 2014), or even taking into account the output of a classifier (Sajeev and Sebastian, 2010). Finally, the goals can be achieved by effectors connected directly with the cache (Ma et al., 2014; Einziger and Friedman, 2014), the application (Chen et al., 2016), or even with a middleware component.

The general activities presented and exemplified above (i.e. monitoring, analyzing, deciding and adapting) are seen in self-adaptive systems as a feedback loop mechanism. Based on such a loop, these systems are able to change their behavior in response to noted changes in their environment. A deeper discussion about autonomic computing and self-adaptive systems is given by Huebscher and McCann (2008) and Lalanda et al. (2013). In this survey, we capture characteristics of existing approaches matching the activities of a feedback loop to facilitate understanding and comparison of the approaches, even if an approach is not explicitly structured in this way. A feedback loop of an adaptive system can be described in terms of six key properties, as described below. These properties are used to compare and describe adaptive approaches in later sections.

Monitored data:

Monitored data are measurable input parameters from which the current state of the system can be characterized.

Analysis:

Based on the monitored data, an analysis process should be employed to characterize the state of the system. Such characterization can be based on a single monitored piece of information or a combination of a set of inputs, such as a utility function, or even a complex model built through machine learning approaches.

Behavior:

The behavior represents how the adaptive component acts over the managed resource or system. It can be reactive, i.e. responding to observed events after it occurs, or proactive, i.e. taking actions in advance before events have a chance to happen.

Operation:

The operation corresponds to when and how the adaptation process can analyze data and take actions. Online operation is the case when the adaptation process takes place while the application is executing, possibly impacting in its functioning. The adaptation process can be seen as part of the application. Offline operation, in contrast, is performed separately, based on the information collected from the application to a later analysis. Actions to be taken are performed when deemed adequate.

Decision:

Decisions are conclusions or resolutions achieved after the analysis. Such decisions involve reasoning about the current state of the system and defining necessary adaptations (if needed) to achieve the goals.

Goal:

Goals consist of one or more expected properties that should be achieved by the adaptations. They summarize the desired system performance or behavior regarding input parameters.

We now focus on approaches that can dynamically evaluate the cacheability status towards discovering cacheable data, i.e. whether a particular piece of content should be cached. As previously mentioned, admission approaches help developers while selecting caching opportunities. This task is particularly complex because selected opportunities must continuously be revised, due to the changing workload characteristics and access patterns, or even the application evolution. This shortcoming motivates the need for adaptive caching solutions, which can minimize the effort required from application developers to maintain caching solutions by automatically improving themselves regarding changes in the application context.

As shown in Figure 2, adaptive admission-focused approaches can be seen from two different perspectives, depending on the purpose of the adaptation: (a) dynamic selection of the best cacheable opportunities through the evaluation of cacheability properties, and (b) reactive filtering of content that was previously identified as cacheable but should not anymore, due to some particular reason. Table 5 summarizes the surveyed adaptive caching approaches that deal with admission issues.

The automatic identification of caching opportunities at the application level is addressed by CacheOptimizer (Chen et al., 2016), which monitors readable weblogs to create mappings between workload and database access. The analysis part consists of two processes: a static code analysis to identify possible caching configuration spots, and a characterization with colored Petri nets, which models the transition of states of an application based on weblogs from the web server. By doing so, it can reach a global optimal caching decision, instead of focusing on top cache accesses, using a greedy approach. Differently from other approaches, CacheOptimizer is not implemented as a new caching framework; instead, it is integrated with those existing, automating the caching configuration according to the results of its analysis. Although this approach addresses method caching opportunities, it focuses on database-centric web applications; thus, only database-related methods are cached. By focusing on general application methods as cacheable options, Mertz and Nunes (2017); Mertz (2017) proposed a seamless approach that automates the evaluation of cacheability properties and admits application methods at runtime based on the Cacheability Pattern (Mertz and Nunes, 2016). These approaches were evaluated considering single-shot scenarios, without having their adaptive behavior measured.

Reactive filtering approaches act at runtime by dynamically evaluating the cacheability of content that was previously identified as cacheable, according to the workload and access pattern, to avoid unworthy content taking place in the cache. By doing this, it can reduce the amount of cached data, freeing space in the cache, avoiding evictions and leading to higher hit ratios. Reactive filtering approaches are specifically useful when dealing with search engines, since not all search combinations will frequently be requested as shown by Baeza-Yates et al. (2007). They proposed an approach to filter infrequent searches, which would not improve application performance if cached. The proposed admission solution monitors query executions and caches such queries into a split cache scheme: controlled and uncontrolled. Both parts internally implement a regular LRU-based cache, but an admission policy is used to distinguish frequent queries, which are placed into the controlled space, from infrequent queries, which are placed into the uncontrolled space. The admission policy is implemented as a function that evaluates each processed search query taking into consideration the query metadata and past usage information. As result, the controlled cache is less pollution-prone, and frequent queries tend to remain cached for longer periods, improving hit ratios. Although infrequent queries are more rapidly evicted in the uncontrolled space, it is still an LRU-based cache and can provide good responses in cases of short-period bursts of infrequent queries.

Also focusing on reactively filtering content, Einziger and Friedman (2014) proposed TinyLFU. Despite such approach acts only when the cache is full, it admits new content in the cache only when such content is expected to provide more benefit than the content already in the cache. TinyLFU estimates the worthiness (i.e. contribution to the hit ratio) of the eviction candidate and compares it with the worthiness of the newly accessed content. To achieve such behavior, TinyLFU uses an approximate LFU structure, maintaining a frequency histogram for cached content, and then it is possible to trade-off the cost of eviction and the usefulness of the new content. A small variation of such approach is currently available to developers as a default replacement policy of the Caffeine caching framework, due to its high hit rate and low memory footprint.

Admission approaches can also be implemented by using sophisticated learning techniques. Sajeev and Sebastian (2010) proposed an admission technique using multinomial logistic regression (MLR) as a classifier. The model built with MLR assigns a worthiness class to the response of a processed request based on the application traffic and response content properties. Such model is trained with previously collected traces and sanitized logs for classifying the web cache’s content worthiness. Then, at runtime, when there is an incoming content, its worthiness class is computed and used in an admission control mechanism based on thresholds to decide whether the content should be cached or not.

Adaptation in consistency maintenance can be employed in both introduced consistency approaches, i.e. expiration-based and invalidation-based. However, differently from static approaches, existing adaptive work focuses only on the former, as can be seen in Figure 2. Consequently, all the approaches assume that stale data is allowed to be returned from the cache, that is, they are based on weak consistency. Table 6 summarizes the surveyed adaptive caching approaches that deal with consistency issues.

In such approaches, it is assumed that cached content is accessed irregularly, and then the definition of a fixed timeout is inadequate. If the cached content has a short expiration time, it tends to lower hit ratios in situations different from a short burst of requests. Otherwise, if it has a long expiration time, it can result in stale data being returned to users. Despite staleness is expected in weak consistency approaches, the level in which it affects the system execution should be taken into account by developers. Due to this, Huang et al. (2010) proposed a cache framework that provides transparency for developers by offering an adaptive expiration time—also called time-to-live (TTL)—definition. The proposed strategy is based on the rationale behind the popular simulated annealing algorithm, in which an expiration time function is approximated according to changes into how users access content. Also focused on TTL definition, Alici et al. (2012) proposed a query result caching for search engines, which considers query-specific TTL values, using a machine learning model to assign TTL values to queries. Their machine learning model exploits a query log and result-specific features to predict the best TTL values. The authors showed that this strategy outperforms the fixed TTL strategy, by means of an evaluation of some parameterized functions (average and incremental TTL).

Cache frameworks and libraries are usually based on a fixed memory size to allocate content. It can be done in terms of allowed number of entries or absolute size. As introduced, there are static approaches that help determine the appropriate cache size and deal with replacement issues that emerge due to a size-limited cache. There are also adaptive approaches that support them, presented and compared in Table 7.

Radhakrishnan (2004) addressed the trade-off between cache space allocation and performance improvement by dynamically changing the cache size according to the access patterns and workload. It uses a linear quadratic estimation (i.e. kalman filtering) algorithm that estimates properly cache size values based on runtime information (hit ratio and memory in use) collected over time and pre-defined thresholds. Given the cache size estimation, the approach is able to decide which action promotes more benefits: increasing or decreasing the cache size, or even keeping it as it is and replacing content.

Regarding replacement policies, popular algorithms such as LRU and LFU have the limitation of considering a single factor, possibly ignoring important properties that can influence the replacement efficiency. In realistic applications, access patterns significantly change over time, and simple replacement policies may not have enough information to properly deal with these situations. A common problem is cache pollution, in which the cache is loaded with unnecessary data, resulting in useful data being evicted. Such problem can be either cold (affecting LRU) or hot cache pollution (affecting LFU and size-based policies) (Ayani et al., 2003).

As shown in Figure 2, adaptive replacement approaches can be classified into three groups: (a) dynamic selection of algorithms, which focuses on exploring the advantages of each algorithm, (b) evolution of traditional replacement policies to achieve adaptation, including the modification of replacement approaches proposed originally for other caching levels (e.g. web proxy caching and database), and (c) the proposal of new and application-level specific approaches.

One of the first initiatives to adapt replacement policies is the Adaptive Replacement Cache (ARC) (Megiddo and Modha, 2003) approach, which combines the merits of different replacement policies, and dynamically balances between the recency and frequency components online. The policy keeps: (i) the cache space is partitioned according to defined constraints in order to hold content that was accessed recently and frequently (at least twice); and (ii) a recent eviction history of the partitions. It uses a learning rule to continually revise the adaptation parameter in response to the observed workload. A practical implementation done by the same authors (Megiddo and Modha, 2004) revealed a better hit ratio with ARC over LRU across a wide range of workloads while incurring practically the same low time cost as the LRU. Although it became popular and is currently implemented in frameworks available to developers, such as Caffeine, it is patented¹⁰¹⁰10https://www.google.com/patents/US20040098541 and requires a license agreement with IBM to be used. Furthermore, Raigoza and Sun (2014) proposed the Adaptive Replacement Cache-Temporal Data (ARC-TD), in which a buffer replacement policy is built upon the ARC policy. Both ARC and ARC-TD policies address the problem of caching priority by trading-off between frequently accessed and recently used content. However, the ARC-TD policy favors the cache retention of content in proportion to the average life span of the content in the buffer. Thus, a higher cache hit ratio can be achieved.

El Abdouni Khayari et al. (2011) presented a runtime closed-loop for self-reconfiguration of the Class-Based Least Recently Used (C-LRU) strategy. In C-LRU, the cache is divided into portions reserved for content of a specific size, and the content size distribution is described by a hyper-exponential distribution using the EM-algorithm. The approach is based on a continuous analysis of the cache trace (access logs), from which relevant data, such as the requested data sizes, the arriving times, hits and misses, are retrieved. Then, it computes the parameters for a hyper-exponential distribution function of the request content sizes, which are used to determine a new configuration for the C-LRU.

Recently, by using cost as an important feature to guide replacement decisions, Ghandeharizadeh et al. (2014) proposed the Cost Adaptive Multi-Queue Eviction Policy (CAMP), which is an adaptation of the GDS algorithm (Young, 1994) (as described in Section 3.2). CAMP manages multiple LRU queues based on the distribution of cost and size of cached content. Each queue is ordered according to the remaining priority of the items. When a replacement is required, CAMP finds the eviction candidate across all queues based on looking the remaining priority at the front of each queue, which conveys the item with the smallest priority. Such approach also has a variation in which FIFO queues are adopted (Ghandeharizadeh et al., 2015), because it demands fewer content moves.

As shown, most of the adaptive replacement approaches use temporal locality information to make replacement decisions. However, a recent work done by Negrão et al. (2015) proposed the consideration of spatial locality of cached content while finding an eviction candidate. Semantics-Aware Caching System (SACS) incorporates the assumption that content (in this case, web pages) that can be achieved from recently requested content tends to be requested shortly and, thus, should also be kept in the cache. Such assumption is captured by a distance metric, which is calculated as the minimum number of links that users are supposed to follow to navigate from one page to the other. Then, while selecting content to evict, SACS takes the most recently requested content (given a threshold) as pivots and calculates the distance of other cached content from pivots. Older cached content with higher distance values is removed until there is enough space to insert the new content. Thus, cached content that is spatially near to recently requested content is kept cached. In addition, when the same distance occurs in two or more entries, the frequency is used as the next criterion to make the decision.

Finally, focused on the client-side, Ali Ahmed and Shamsuddin (2011) proposed a neuro-fuzzy system, called Intelligent Client-side Web Caching Scheme (ICWCS), that estimates content that can be accessed in the future. This approach splits the cache space into short-term and long-term caches, in which the former is an LRU-based cache that receives content directly, and the latter receives content evicted from the short-term cache. When the long-term cache achieves its full capacity, a trained neuro-fuzzy system is employed to distinguish content in the long-term cache as cacheable or uncacheable. Then, content classified as uncacheable are evicted.