Can Increasing the Hit Ratio Hurt Cache Throughput?
Ziyue Qiu Juncheng Yang Mor Harchol-Balter



































Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers.  Almost all these prior papers evaluate the caching algorithm based on its hit ratio, namely the fraction of requests that are found in the cache, as opposed to disk.  The “hit ratio” is viewed as a proxy for traditional performance metrics like system throughput or response time.  Intuitively it makes sense that higher hit ratio should lead to higher throughput (and lower response time), since more requests are found in the cache (low access time) as opposed to the disk (high access time).  

This paper challenges this intuition. We show that increasing the hit ratio can actually hurt the throughput (and response time) for many caching algorithms.  Our investigation follows a three-pronged approach involving (i) queueing modeling and analysis, (ii) implementation and measurement, and (iii) simulation to validate the accuracy of the queueing model. We also show that the phenomenon of throughput decreasing at higher hit ratios is likely to be more pronounced in future systems, where the trend is towards faster disks and higher numbers of cores per CPU.  






















Can Increasing the Hit Ratio Hurt Cache Throughput?
    Ting Yu
    April 29, 2024
===================================================







§ INTRODUCTION




Software caches are widely deployed in today's infrastructure.   Examples range from simple and small page caches in laptops and mobile phones to large multi-layer distributed and heterogeneous key-value caches and object caches in the data centers, e.g., Meta Cachelib <cit.>, Google CliqueMap <cit.>, and include many types of caches in between <cit.>. 

The purpose of the cache is to allow fast data access.
This paper focuses on DRAM-based software caches.

Typically, cached items can be accessed anywhere from 100 to 10,000 times faster than those on disk <cit.>. 
The principle of caching is very simple: Store items that are likely to be accessed soon in the cache.  Store everything else on disk.


The goal of utilizing a cache is to 

improve throughput, the average number of requests served per second (RPS). This is particularly important in data processing applications where the goal is to process as many data requests as possible per unit time. 
Examples include the caches used in big-data systems such as Hadoop and HDFS <cit.>, deep learning systems such as Pytorch <cit.> and Alluxio <cit.>, and databases such as RocksDB <cit.>.



 §.§ Cache eviction algorithms


All caches have a common component: the cache eviction algorithm. The eviction algorithm decides which item to evict when the cache is full. 
The most common cache eviction algorithm is Least-Recently-Used (LRU) <cit.>, which evicts the least recently accessed item in the cache.
Because of its popularity, this paper will focus on LRU cache eviction.
LRU is widely used because data access patterns often show locality where recently used data have a higher chance to get reused <cit.>. 
Another common algorithm is First-In-First-Out (FIFO), which evicts the least recently inserted item, i.e., the oldest item. 
Besides LRU and FIFO, many advanced eviction algorithms have been designed <cit.>. 




 §.§ The quest for higher hit ratio
  


While the overall performance goal of a cache is to improve the request throughput and reduce the mean latency for requests, researchers have resorted to using the cache hit ratio as a proxy for measuring performance <cit.>.

The hit ratio is defined as the fraction of requests that are found in the cache.  



Maximizing the hit ratio makes intuitive sense for improving system performance since we want to maximize the fraction of accesses that can be completed quickly from the cache and minimize the fraction of accesses that need to go to the slow disk.

But what if this intuition is wrong?  What if increasing the hit ratio actually hurts performance?

This is the question investigated in this paper. The cache eviction algorithms we evaluate are summarized in Table <ref>.  


































 §.§ A three-pronged approach to determining if higher hit ratio helps


We take a three-pronged approach to determine if a higher hit ratio, in fact, improves throughput.




  §.§.§ A. Queueing model for upper bounding throughput


While many papers have analyzed caching policies in the past, all of these works have focused on analyzing the hit ratio, see for example  <cit.>.
The question of how the hit ratio affects throughput has been overlooked.  Perhaps this is because it seems so obvious that increasing the hit ratio can only help. 

Instead we develop a queueing model of our DRAM-based software cache for a range of popular eviction policies, based on measurements from our implementation. We then use queueing theory to derive an upper bound on the throughput of this queueing model. An example of such an upper bound for the case of LRU is given in Figure <ref> via the red solid line. While the analysis provides only an upper bound on throughput, it clearly shows that throughput first increases with hit ratio, then levels off, and then decreases.



  §.§.§ B. Simulation of the queueing model


Because exact analysis of the queueing model is not possible,
we next simulate the queueing model to obtain its exact throughput. For LRU, the result is shown in Figure <ref> via the blue dotted line.



  §.§.§ C. Implementation of the caching system




Finally we implement our caching system with a range of eviction algorithms. Our implementation is a prototype of Meta's HHVM Cache <cit.>. The Meta HHVM Cache is similar to many other in-memory caches, e.g.,  CacheLib <cit.>, Memcached <cit.>, Intel OCF <cit.>, BCache <cit.>, and RocksDB LRU Cache <cit.>.

Additionally, to gain insights into evolving trends, our implementation includes a feature to emulate varying disk speeds and Multi-Programming Limits. This functionality is crucial for understanding how the hit ratio will affect throughput in future caching systems.   

For LRU, the result of our implementation is shown via the green dashed line in Figure <ref>.
Importantly, the simulation result is within 5% of the implementation result.
This tells us the performance predicted by our queueing model provides a very good estimate of system performance.  











 §.§ Contributions


The contributions of this paper are summarized below:


  * This paper shows that increasing cache hit ratio can hurt throughput for many LRU-based cache eviction algorithms. We show this via a three-pronged approach, involving queueing theory, simulation, and implementation. This counterintuitive result will be explained in Section <ref> after we discuss the relevant queueing model.

  * We develop queueing models that allow us to understand the effect of the cache hit ratio on system throughput. This is done for six different caching policies.
The modeling is non-trivial and, to the best of our knowledge, such models do not exist in prior work. 


  * While our queueing analysis only provides upper bounds, the analysis clearly indicates that throughput initially rises with hit ratio and then drops with hit ratio.


  * We also implement many caching policies, including LRU, FIFO, Probabilistic LRU, and CLOCK. We validate the correctness of our queueing models, by simulating the queueing models and showing that the simulation results match the implementation results within 5% for all caching policies studied.

  * We evaluate the effect of changing disk latency as we move from older disk speeds (500 μ s) to current disk speeds (100 μ s) to future disk speeds (5 μ s).   An example of the effect of the disk speed trend is given in Figure <ref>, for the case of Segmented LRU (SLRU).  As we move to future disk speeds (move from left to right in the figure), the point at which throughput starts to deteriorate moves earlier and earlier.  

  * We also evaluate the effect of another trend, increasing the number of CPU cores, which allows more requests to be served concurrently – the Multi-Programming Level (MPL) increases. The effect of increasing the MPL is shown in Figure <ref> when looking from top (MPL = 72) to bottom (MPL = 144). The point at which throughput starts to deteriorate moves earlier for higher MPL.
















§ SCOPE OF THE PAPER


Our paper is limited to DRAM-based software caches. 



 §.§ DRAM-based software caches versus other caches



In a DRAM-based software cache, DRAM is used to cache the accessed data. This is in contrast to SSD-based software caches where the data are cached in an SSD. In an SSD-based cache, the cache access is 100 times slower and far less concurrent than in the DRAM system. Consequently, results are very different from DRAM-based software caches. We will explain this in more detail in Section <ref>.

Hardware caches are also outside the scope of this paper.
While software caches are characterized by a global linked list that orders the cache items, hardware caches are typically set-associative caches (e.g., RRIP-based eviction algorithms <cit.>). This means that the eviction algorithm is limited to evicting data in the same “set.” There is no concept of a global linked list and hence no software operations.

Network-connected caches are also outside the scope of this paper. Here the bottleneck is the time needed to move the data, rather than the time to manage software operations.  




 §.§ Hardware trends


The performance of DRAM-based software caches is highly dependent on the cores on which the software runs and the backend disks.  Over the years, the number of cores increases dramatically while the speed and concurrency of backend disks have improved. 


Before 2000, CPUs had only one core <cit.>, but a modern CPU has 32-192 cores <cit.>. The increase in CPU cores enables better performance, allowing more concurrent requests; however, it also presents challenges because the cores need to coordinate with each other. 

Meanwhile, the backend disk latency stagnated around 2-10 ms until the wide adoption of SSDs as the backend device. Today's SSDs exhibit a wide range of latency characteristics. High-end SSDs have latencies around 5 μ s <cit.>; low-end SSDs show latencies of a few hundred μ s <cit.>, and most commercial SSDs have latency in between <cit.>. 

In addition to the reduced latency, SSDs today support massive concurrency <cit.>. This means that requests at the disk can all be served in parallel without queueing.  
































§ A THREE-PRONGED APPROACH TO LRU



Because LRU is the most common caching policy, we focus on carefully understanding its performance. The purpose of this section is to explain why increasing the hit ratio can actually lead to decreased throughput for DRAM-based software caches. Our takeaways are summarized in Section <ref>.



 §.§ A closed-loop queueing model of LRU



As with many caching systems evaluations and benchmarks, e.g., Cachelib <cit.>, YCSB benchmark <cit.>, S3-FIFO <cit.>, and FrozenHot <cit.>, our system is best modeled by a   closed-loop queueing model,
where new requests are triggered by the completion of previous requests.  There is a fixed Multi-Programming Limit (MPL), N, denoting the number of requests that can be in the system at a time (this is dictated by the number of cores – in our case 72). 



  §.§.§ Modeling concurrency in a closed-loop model


Each request is handled by a single core. The total number of requests in the system is thus limited by the total number of cores. Throughout, we assume that there is one CPU with 72 cores (this will match our experimental setup), and thus we can process 72 requests concurrently.

We thus model our caching system via a closed-loop queueing model, where a new request is allowed to enter only when some other request completes. The multi-programming limit (MPL) for the system is N = 72. See <cit.> for background on modeling closed-loop queueing models.



  §.§.§ Modeling disk access and cache access



Our disk has enough concurrency that it can be accessed simultaneously by all 72 requests. Thus, in queueing speak, we can model the disk as a think station (infinite number of simultaneous service stations) with mean think time Z_disk= 100 μ s. 
Likewise, the cache lookup can also be executed concurrently. Thus, the cache lookup can also be modeled as a “think” station but with a much faster mean think time of Z_cache = 0.51 μ s. Note that a think station is different from a queue station in that there is no queueing at a think station – every request is served immediately and concurrently.



  §.§.§ Modeling software global list operations


In an LRU cache, all cached items are stored in a single global linked list, 
where the least-recently-used item is the “tail” item and is the one to evict, while the most-recently-used item is at the “head” of the list. 
A request for some item d first goes to the cache to look for d. Either the request finds d in the cache (called a “hit”), or it does not (a “miss”). The probability of a hit is denoted by p_hit and the probability of a miss is p_miss, where p_hit + p_miss = 1.

If the request is a hit, then two things need to happen:


  * The item d must be delinked from its position in the global linked list. This is the delink operation. The delink time is denoted by the service time random variable S_delink. 

  * The item d needs to be attached to the head of the global linked list. This is called the cache head update. The head update time is denoted by the random variable S_head. 


Note that the actual “reading time” (the time to read a 4KB block)  is not included in our model.  The reason is that this is very small compared with cache lookup, is handled concurrently,  and is the same across all algorithms.


If the request is a miss, then three things need to happen:


  * The item d needs to be found on disk. 

  * The least-recently-used item (the one at the tail of the global list) needs to be removed. We call this the cache tail update and denote it by the random variable S_tail. 

  * Item d needs to be attached to the head of the global linked list. This is the cache head update mentioned earlier, denoted by random variable S_head.


We can thus model the LRU Caching system via the queueing model shown in Figure <ref>. 



Understanding how to properly model S_head, S_tail, and S_delink is important and non-trivial and will come up again when discussing different eviction policies. We will explain these here. 
We start with S_head, which denotes the time needed for a head update on the global linked list. This has two components. The first component is obvious: just the update to the global list. The second component is less obvious: communicating this update to all the other requests in the queue. Specifically, the core performing the head update needs to communicate with all the other cores in the head update queue to alert them that this head update is happening. Obviously, if there are many requests in the head update queue, then this communication will take longer.

In summary, S_head consists of a constant head update time and a communication time dependent on queue length.
When the head update is the bottleneck operation, our measurements show that these two components add up to S_head = 0.59 μ s. When the head update is not the bottleneck operation, the queue length at the head update queue drops, thus S_head decreases. However, as we'll see in the analysis of LRU (Section <ref>), in the case where an operation is not a bottleneck, its service time does not impact overall throughput much. Specifically, any value in 0 < S_head < 0.59 μ s will produce the same throughput if a head update is not the bottleneck operation.  We find that S_head follows approximately a Bounded Pareto distribution (with α = 0.45) ranging from 0.1 μ s to 1.2 μ s. However, as we'll see in Section <ref>, the throughput analysis of the queueing model is only influenced by the mean, S_head. Similarly, when the delink queue is the bottleneck, S_delink = 0.7 μ s. When the delink queue is not the bottleneck, its value has little impact on analysis.

Importantly, when we look at other eviction algorithms, the number for S_head can change because the queue length at the head update queue will change.



To measure S_head, we create a setting where the head update is the bottleneck operation. This means that the head update queue will be flooded.  Consequently the service time, S_head, is simply the inter-departure time from this flooded queue (namely the time between consecutive departures from the queue), which is easy to measure.  Likewise, it is easy to measure S_delink, because that device can also be made into the bottleneck (by setting p_hit appropriately).  

The case of S_tail is slightly different because the tail update is never the bottleneck operation. This makes it difficult to precisely measure S_tail because we can't keep the tail update server fully utilized as we were able to do for the other servers. Fortunately, again, as shown in Section <ref>, the precise value will not matter.  





Before ending the section, we note that there is an alternative implementation possible for LRU, used in systems such as Varnish <cit.> and Alluxio <cit.>, that combines the delink, tail update, and head update operations into a single queue. 

However, we chose to use a three-queue implementation because it allows higher concurrency and higher throughput. The three-queue implementation is 33% faster than the single-queue implementation for high hit ratios at N = MPL=72.  


















 §.§ Analysis of LRU queueing model



The goal of this section is to determine analytically how the system throughput is affected by hit ratio, p_hit. We first illustrate our analysis assuming that mean disk latency is Z_disk = 100 μ s and then explain how the result generalizes to other disk latencies. Our analysis of closed systems is based on <cit.>) and produces an upper bound on throughput for the queueing network in Figure <ref>.

The first step is to determine the mean think time of the system, Z, where Z is the mean time spent on accesses that can be executed concurrently by all cores.  This includes cache lookup and disk access:

    Z    =    Z_cache + p_miss·Z_disk
        =     0.51 + p_miss· 100 = 100.51 - 100 p_hit


For each queue, we now compute the device demand, which is the expected service demand on the corresponding server, per request into the system.  The device demands are:
  
    D_delink    =     p_hit· 0.7 
    
    D_tail    <     (1 - p_hit)  · 0.59 
    
    D_head    =     0.59





The total demand, D, is the sum of the device demands: 

    D     =      D_delink + D_tail + D_head

Because 0 < D_tail < 0.59, we have upper and lower bounds on D as follows:

    0.7 p_hit + 0.59 <     D     < 0.7 p_hit + 0.59 (1 - p_hit) + 0.59 
    
    0.7 p_hit + 0.59 <     D     < 0.11 p_hit + 1.18


The next step is to determine the bottleneck device, which is the device with the highest demand.  We can see that the bottleneck device is the delink device if p_hit is sufficiently high, specifically p_hit > 0.84.  Otherwise, the bottleneck device is the head update device.   We write this as:  
  
    D_max = max(0.59, 0.7 p_hit) = {[         0.59 p_hit < 0.84;    0.7 p_hit p_hit > 0.84 ].

  
We use X to denote system throughput.  From <cit.>, we know that  X is upper-bounded by two terms, as follows:    

    X ≤min( N/D + Z ,  1/D_max).

Substituting in the expressions for Z, and D_max that we have already derived, as well as the lower bound on D and the fact that N=MPL = 72, we have that, for the case of Z_disk= 100 μ s:



    X_≤min( 72/101.1 - 99.3 p_hit ,  1/max(0.59, 0.7p_hit))





Equation (<ref>) represents an upper bound on throughput, shown in red in Figure <ref>(b). This turns out to be a very good bound on the measured throughput from our implementation. 
When p_hit < 0.59, the first term in (<ref>) is the relevant bound (minimum term).   When 0.59 < p_hit < 0.84, the second term in (<ref>) is the relevant bound, where the max term in the denominator is 0.59.  When p_hit > 0.84, the second term in (<ref>) is again the relevant bound, but the max term in the denominator is 0.7p_hit. 

Recall that 0 < S_tail < 0.59.  In the above analysis, we assumed that S_tail = 0 because we wanted an upper bound on X.  If instead, we had used any value of S_tail in the range between 0 and 0.59, the impact on our result for X would be very small (< 0.5%).  The reason is that changing S_tail would only change D, not D_max. Hence only the first term in (<ref>) would change, and we only care about this first term when p_hit is low, specifically p_hit < 0.59.   Within this first term, D + Z would change from 101.1  - 99.3 p_hit to 101.69  - 99.89 p_hit. 


The above analysis assumed that Z_disk= 100 μ s.  If we redo the analysis for the case where Z_disk = 5 μ s, the throughput is (<ref>), as shown in red in Figure <ref>(c).


    X_≤min( 72/6.1  - 4.3 p_hit ,  1/max(0.59, 0.7p_hit))


If we repeat the analysis for the case where Z_disk = 500 μ s, we get (<ref>) shown in 
red in Figure <ref>(a).



    X_≤min( 72/501.1  - 499.3 p_hit ,  1/max(0.59, 0.7p_hit))









  §.§.§ Discussion of the analytic results



We've seen that increasing the hit ratio leads to lower throughput when the hit ratio is high.  We have shown via a queueing analysis why this happens. From a more intuitive perspective, when the hit ratio is high, we see that the delink operation becomes the bottleneck. Hence almost all requests are queued behind the delink server in Figure <ref>.  Thus,  while it seems that we are saving time by not going to disk, we instead are wasting time by having to queue up at the delink device.  Thus requests can actually take longer. This longer response time translates to a drop in throughput.

In all the curves of Figure <ref>, we find that there is some point,  p^*_hit, after which increasing the hit ratio only hurts.  This point p^*_hit decreases as the mean disk latency decreases.  
When the mean disk latency is really low(Figure <ref>(c)), increasing the hit ratio never helps! Thus our message about not blindly increasing the hit ratio will become more and more valid as we move to faster disks.

Throughout, we have looked at throughput, but we could instead have looked at mean response time, namely the time from when a request is submitted until it completes.  Given that we have a closed-loop setting, mean response time and throughput are inversely related (see <cit.>). Hence mean response time increases for higher hit ratios.     



  §.§.§ How the analysis changes for SSD caches


In an SSD cache, the queueing network looks similar to Figure <ref>, but cache lookup and disk access can no longer be modeled as think stations. Because the SSD hardware has much lower concurrency than DRAM, cache lookup is better modeled via a queue of waiting requests. Likewise, the backend disk should be modeled as a queue due to its low concurrency. The device demands on the cache lookup and the disk access are now much higher than that of delink, tail update, and head update. Hence throughput is dominated by the disk access time. Thus  increasing the hit ratio never hurts throughput.



 §.§ Simulation evaluation



Recall that our queueing analysis from Section <ref> only provides upper bounds on throughput.
To get the exact throughput of the queueing network, we turn to simulation.


We use an event-driven simulation.  We model the service time for each operation as exponentially distributed with the appropriate mean (where the mean comes from the implementation measurements).   While we chose the service time distribution arbitrarily, we note that we tried other distributions and found that the results were insensitive to the particular service time distribution used.  This is consistent with the findings in <cit.> for closed-loop models.   


The results of our simulation are shown in Figure <ref> via dotted blue lines. We also show 95% confidence intervals but they are typically too small to be visible. As expected, the results of simulation lie below the red theory lines, which represent the theoretical upper bound.






 §.§ Implementation Setup and Results



In both the analysis (Section <ref>) and the simulation (Section <ref>), we were evaluating the queueing network in Figure <ref>. We now study LRU via our implementation that is independent of any queueing network. 

Our implementation is a prototype based on Meta's HHVM Cache.  Figure <ref> shows the results of our LRU implementation via green dashed lines  with 95% confidence intervals.



  §.§.§ Implementation and experimental setup


Our experiments use dual-socket servers with Intel Xeon Platinum 8360Y 36-core processors (Ubuntu 20) at 2.4GHz, running on CloudLab platform <cit.>. To avoid Non-Uniform Memory Access (NUMA) impacts, our evaluations only use a single socket with hyperthreading enabled. To provide consistent results, we disable turbo-boosting and fix the per-core frequency at 3.1 GHz.

Our Intel Xeon Platinum CPU allows for 72 cores to run concurrently.  This limits the number of requests that can be in the system at once to 72. Each request accesses a 4KB block of data,  the common size in database block caches. 
We emulate three different disk speeds:
500 μ s, 100 μ s, and 5 μ s.  

In our experiments, we consider p_hit in the range of [0.4, 1], with a step size of 0.05 in most cases, but a step size of 0.02 for higher p_hit values. 
Each experiment is run 20 times, and we determine 95% confidence intervals in each case.



  §.§.§ Workload creation

For request generation, we employ 72 client threads, where each thread is assigned to a single CPU core. We use a synthetic popularity distribution following the Zipfian parameter θ = 0.99, representative of cache accesses from e-Commerce websites <cit.> and social networks <cit.>. Recognizing that our goal is to assess the impact of hit ratio on throughput, and that the popularity distribution only affects the hit ratio, we determine that it is sufficient to test with this well-established Zipfian distribution without the need for a broader range of models or real-world access traces. Throughput measurements are conducted after some warmup period, when the cache is full.



  §.§.§ Results of implementation

Our implementation results and simulation results are always within 5%. 



 §.§ Takeaways



We started the section by presenting a queueing model of our LRU caching system (Section <ref>). We were able to derive an upper bound on throughput in our model as a function of the hit ratio (Section <ref>). Our analysis elucidated that when the hit ratio gets high, the delink operation becomes the bottleneck in the queueing network, resulting in longer delays and lower throughout. We next simulated the queueing network (Section <ref>), which allowed us to determine the exact throughput as a function of hit ratio. Finally, in Section <ref>, we implemented our LRU caching system and showed that the results are always within 5% of the simulation.

There are two takeaways. First, because the implementation matches the simulation, we conclude that our queueing model is an excellent representation of the real system, at least with respect to understanding system throughput as a function of hit ratio. Second, we see that a very simple queueing analysis enables us to easily predict the point at which increasing the hit ratio starts to hurt the throughput. This foreshadows a theme of this paper – queueing analysis alone suffices to predict the behavior of throughput as a function of hit ratio for many eviction policies.












§ EVALUATION OF OTHER POLICIES



In this section, we will apply our three-pronged approach to the remaining algorithms in Table <ref>. Our goal is to determine how the throughput is affected by the hit ratio, p_hit. 



 §.§ FIFO





In the FIFO policy we  store all cached objects into a single global linked list. 
The list maintains the same ordering the entire time, with new items being added to the list head and the oldest item dropping off the tail.  

If a request for item d is a cache hit, nothing happens to the global linked list.  
When the request is a miss, the list must be updated.   Specifically: 


  * The item, d, needs to be read from disk.  

  * The oldest item needs to be removed from the global list, requiring a cache tail update. 

  * Item d needs to be attached to the head of the list, requiring a cache head update.  




We can thus model the FIFO caching system via the closed-loop queueing model in Figure <ref>.  
It may seem strange that  S_head is higher in the FIFO system (Figure <ref>) than in the LRU system (Figure <ref>). To understand why this happens, recall from Section <ref> that there are two components to S_head: (i) a constant time needed for a head update to the global linked list, and (ii) a communication time proportional to the queue length at the head update queue.  Now, in LRU there are 72 jobs in the system, split among three queues, but in FIFO, the 72 jobs are split among only two queues.  Consequently the expected queue length of each of FIFO's two queues is larger than each of LRU's three queues. This in turn means that component (ii) is higher under FIFO, explaining why S_head is larger under FIFO.
  




  §.§.§ Analysis of the queueing network model
  

We now follow the same approach that we used for LRU to analyze our closed queueing network.  

Again the mean think time of the system is: 

    Z    =    Z_cache + p_miss·Z_disk  =  100.51 - 100 p_hit


For each queue, we now compute the device demand: 
  
    D_tail    <     (1 - p_hit)  · 0.73  
    D_head  =  (1 - p_hit) · 0.73




The total demand, D, is the sum of the device demands: 
    D  =   D_tail + D_head





Because 0 < D_tail < (1 - p_hit)  · 0.73, we have upper and lower bounds on D as follows:



    (1 - p_hit) · 0.73 <     D     < (1 - p_hit) · 0.73 + (1 - p_hit) · 0.73 
    
    0.73 - 0.73 p_hit <     D     < 1.46 - 1.46 p_hit


The bottleneck device is always the head update, so:
  
    D_max = 0.73 - 0.73p_hit.

  
   Given all the above terms, where Z_disk= 100 μ s, from <cit.> our upper bound on throughput X is:

    X_≤min( 72/101.24  - 100.73 p_hit ,  1/0.73 - 0.73p_hit)





Equation (<ref>) represents an upper bound on throughput, shown in red Figure <ref>(b).  
Recall that 0 < S_tail < 0.73.  In the above analysis, we assumed that S_tail = 0 because we wanted an upper bound on X.  If instead, we had used any value of S_tail in the range between 0 and 0.73, X would only change by <0.5%.  

What's interesting about (<ref>) is that for both terms in the bound of X, increasing p_hit increases the throughput.   This contrasts with the expressions of throughput for LRU, where increasing p_hit decreased the second term in the bound of X.

The above analysis assumed that Z_disk= 100 μ s.  We can likewise redo the analysis for the case where Z_disk = 5 μ s, obtaining:  




    X_≤min( 72/6.24  - 5.73 p_hit ,  1/0.73 - 0.73 p_hit)



Likewise, when Z_disk = 500 μ s, we obtain:


    X_≤min( 72/501.24  - 500.73 p_hit ,  1/0.73 - 0.73 p_hit)


The upper bounds in (<ref>), (<ref>), and (<ref>) are shown via the red solid lines in Figure <ref>.




  §.§.§ Results of the three-pronged approach


Our analysis for FIFO shows that increasing the hit ratio always leads to higher throughput, regardless of the mean disk latency.  The queueing theory shows this mathematically.  More intuitively, the bottleneck device (the head update) is now in the miss path, not in the hit path. Therefore, increasing the hit ratio does not result in increased demand on the bottleneck device, and hence does not lead to deleterious effects on throughput.  

Our simulation of the queueing network follows the same process as Section <ref>, and our implementation follows the process of Section <ref>. Results of simulation are shown in blue dotted lines and results of implementation are shown via green dashed lines in Figure <ref>. These agree within 5%.



 §.§ Probabilistic LRU





Under Probabilistic LRU there is an additional parameter q that controls how close the algorithm is to LRU (lower q) versus FIFO (higher q).   
As always, there is a global linked list; however, now the ordering of items in the linked list is a mixture of FIFO and LRU.

If a request for item d is a hit, then, with probability q nothing happens to the global linked list (as in FIFO).
However, with probability 1-q, we follow LRU, where: 


  * The item d needs to be unlinked from its position in the global linked list (a delink operation). 

  * The item d needs to be attached to the head of the global linked list (a head update operation). 

If the request is a miss, then three things need to happen:


  * The item d needs to be read from disk.   

  * The item at the tail of the global linked list needs to be removed (a tail update operation).

  * Item d needs to be attached to the head of the global linked list (a head update operation).


The service times for the usual operations turn out to be slightly affected by the value of q.  This is because q affects the queue lengths, hence affecting the communication overhead as explained in Sections <ref>.
The queueing network for Probabilistic LRU is shown in the case of q = 0.5 (Figure <ref>(a)) and q = 1 - 1/72 (Figure <ref>(b)).   We chose these values because it turns out that q has to be extremely high, ≥ 1 - 1/N, to show FIFO-like behavior.  For all other values of q, our analysis (and implementation), shows LRU-like behavior.  This is an interesting finding in its own right.







  §.§.§ Analysis of the queueing network model
  

Analysis is deferred to the supplemental document.







  §.§.§ Results of the three-pronged approach


Figures <ref> and <ref> show the results of analysis (red solid lines), simulation (blue dotted lines) and implementation (green dashed lines). Again simulation and implementatin agree within 5% and the analytic upper bound provides an excellent indication of the trends.

The behavior of Probabilistic LRU is highly dependent on the q parameter.  When q is not very high, we see that the throughput starts decreasing beyond hit ratio p^*_hit.  The queueing theory shows this fact mathematically.  More intuitively, given that q is not high, many requests need to go through the delink queue, which becomes the bottleneck, resulting in higher queueing times, and reduced throughput.



By contrast, when  q is very high, we basically skip the delink operation.  Hence our network behaves very similarly to FIFO.  Now the bottleneck device is on the miss path, and hence is not affected by increasing the hit ratio.




 §.§ CLOCK


The CLOCK cache eviction policy operates a global linked list, ordered like FIFO, however every object that is accessed gets a “second chance" to live before eviction.   As in FIFO, each object d is appended to the head of the linked list and moves down towards the tail of the list as new objects are appended to the head. Each object is given a special bit set to 0.  If object d gets to the tail of the list, and its bit is still 0, then it is removed from the tail.  However, if d is accessed before it gets to the tail, then d's bit is set to 1.  Note that d's position in the list does not change. When d gets to the tail of the list, because its bit is 1, it is skipped over for eviction, provided that there are other candidates with a 0 bit. The CLOCK queueing network is shown in Figure <ref>.













  §.§.§ Analysis of the queueing network model
  

Analysis is deferred to the supplemental document.



  §.§.§ Results of the three-pronged approach

Figure <ref> shows the result of the theory, simulation, and implementation of CLOCK. 
We see


that increasing the hit ratio, p_hit, 
always leads to higher throughput, regardless of the mean disk latency.  The queueing theory shows this fact mathematically.  Intuitively, the bottleneck device (the tail update) is in the miss path, not in the hit path. Therefore, increasing the hit ratio this does not result in increased demand on the bottleneck device, and hence does not impinge on throughput.  



 §.§ Segmented LRU


The Segmented LRU (SLRU) policy is one of the more advanced policies that researchers and practitioners use.  
The high-level idea in SLRU is that the global linked list of all objects in the cache is divided into two lists: the Probationary list ( denoted B for bottom) and the Protected list (T for top).




Objects initially enter the B list.
If an object is never accessed after being put on the B list, it will eventually leave the cache. 
However, if an object on the B List is accessed, 
then the object will be delinked from the B list and moved onto 

the T list.  The T list is an LRU list in the sense that it is sorted from most recently accessed to least recently accessed.   When an object on the T list is accessed, the object moves to the head of the T list.  When an object leaves the T list, it is moved back to the B list and the process repeats.  



The queueing network for SLRU is shown in Figure <ref>.  
When an object d is first accessed, we do a cache lookup.  There are now three cases of what might happen.  If d is currently in the T list (which runs LRU), then d needs to be delinked from its current location and moved to the head of the B list (thus we have a delinkT operation followed a headT update).
If d is currently in the B list, then d is delinked from the B list and moved to the head of the T list.  When this happens, we need to remove the object that is at the tail of the T list.  That object is moved to the head of the B list.  
Finally, if d is not in the cache (a “miss"), then we need to find d in the disk.  After finding d, we put it on the head of the B list and remove the object at the tail of the B list.  

To do a queueing analysis of the network in Figure <ref>, we need two more things:
First, we need the service times of potential bottleneck operations. These are the same as the numbers in the LRU network.  Second, and more challenging, we need to understand the fraction of time that an object is found on the T list as opposed to the B list.  This is obviously a function of p_hit.  We used our simulation to estimate this function. The details are in the supplementary document.

































































  §.§.§ Results of analysis and simulation


Figure <ref> (see the front of the paper) shows the results of analysis (red solid lines) and simulation (blue dotted lines) for Segmented LRU. We have not implemented SLRU.

Like LRU, SLRU also experiences reduced throughput with high hit ratios.

The queueing theory shows this mathematically.  More intuitively, the bottleneck here is often the delinkT operation.

Therefore, increasing hit ratio makes more requests queue behind the delinkT server which is already bottlenecked, hence lowering the throughput.
Note that this same behavior would happen if the DelinkB operation were the bottleneck.  Thus using a more complex policy, like SLRU, which has more queues, does not alleviate the problem of having a bottleneck on the hit path.

In all the curves of Figure <ref>, we find that there is some point,  p^*_hit, after which increasing the hit ratio only hurts.  
This point p*_hit decreases as the mean disk latency decreases.  




 §.§ S3-FIFO


The S3-FIFO policy is a new algorithm that claims to have state-of-the-art hit ratio. We have not implemented this policy, but will study it via analysis and simulation.  S3-FIFO divides the global list of all elements in the cache into two global FIFO-ordered lists.  The first global list is called the Small List, because it has a fixed short length, while the second global list is called the Main List.  Typically, the Small List contains 10% of the items while the Main List contains the rest (we used these numbers in our model).  The S3-FIFO algorithm is very similar to CLOCK in that only a miss causes work to be done, while a hit only involves setting a bit.

There is also a Ghost element which determines whether the requested item should be stored in the Small list or the Main list.  The 
Ghost's decision is generally based on whether the object was accessed within the last x misses of the cache, where x is the number of items in the Main List.  Ghost lookup is similar in speed to a cache lookup, so Z_ghost = 0.51 μ s.

As in CLOCK, every object in the cache has a special bit.
When the object first enters the cache, the object is assigned a bit of 0.  If the object is accessed while it is in the cache, then its bit is changed from 0 to 1.  

When an object d is requested, if d is in the cache (regardless of which list), we get d and set d's bit to 1 (if it's not already 1), completing the request.  
If, on the other hand, d is not in the cache (a “miss"), then we need to get d from disk.  We now use the Ghost to figure out in which list to store d.  If d was “missed recently" (meaning it was missed sometime within the last x misses of the cache), then we store d in the Main List, M.  Otherwise, we store d in the Small List, S.  Since both lists are FIFO lists, it is advantageous to d to be stored in M (which is a lot longer).  Either way, we still need a Head Update (to append d) and also a Tail Update (to remove the object at the tail of the list), thus keeping both lists at their original size.  



Before the object at the tail of the S list is thrown out, it has the opportunity to move to the M list.  This happens if and only if its bit is 1.  Otherwise it is removed from the cache.
Objects in the M list never move to the S list.  

To do a queueing analysis of the network in Figure <ref>, we need three more things:
First, we need to know the service times for all  potential bottleneck operations.  These are the same as the numbers in the CLOCK network.   Second, and more challenging, we need to understand the fraction of requests that the Ghost sends to the M list (denoted p_ghost) as opposed to the S list. 
Third, we need to know the fraction of items, p_M, at the tail of the S list that have a 1 bit associated with them as opposed to a 0 bit.  
We used our simulation to estimate both p_ghost and p_M as functions of p_hit. Our results are expressible in terms of the χ^2 function. See the supplementary document for details.
























    

























  §.§.§ Results of analysis and simulation

Figure <ref> shows the results of analysis (red solid lines) and simulation (blue dotted lines) for S3-FIFO.
We see that increasing the hit ratio, p_hit, always leads to higher throughput, regardless of the mean disk latency, Z_disk.   Intuitively, this holds because 
the bottleneck device (no matter whether it is the headS update or tailM update) is in the miss  path, not in the hit path. Therefore, increasing the hit ratio does not result in increased demand on the bottleneck device, and hence does not hurt throughput.  









































































































































§ DISCUSSION
















 §.§ A classification of eviction algorithms


Throughout our model analysis, simulation, and implementation study, we find that common eviction algorithms can be classified into two categories: LRU-like algorithms and FIFO-like algorithms. The throughput of LRU-like algorithms (LRU, Probabilistic LRU with lower q, and SLRU) typically drops when the hit ratio becomes high.  By contrast, the throughput of FIFO-like algorithms (FIFO, Probabilistic LRU with very high q, CLOCK, and S3-FIFO) always increases with the hit ratio. 



While we have only studied six eviction algorithms, we can conjecture the behavior of other algorithms based on what we've learned. In Table <ref>, we have classified recent caching algorithms into LRU-like versus FIFO-like.
The LRU-like algorithms all have the common feature that they perform a delink operation upon a cache hit.  This delink operation becomes the bottleneck, meaning that increasing the hit ratio will increase the queueing time at the delink queue, which will lead to lower throughput.  


















The FIFO-like algorithms  have the common feature that they do not update the global data structure upon cache hits.  Consequently, increasing the hit ratio will not increase the queue length at the bottleneck device, and therefore will not lead to lower throughput.  
These FIFO-like algorithms can be further divided into two types. Algorithms in the first type use FIFO as the basic building block, e.g., CLOCK variants <cit.>, S3-FIFO <cit.>, QDLP <cit.>, and SIEVE <cit.>. 
The second type of FIFO-like algorithms does not have a global data structure, but rather uses random sampling to choose eviction candidates. Examples include LHD <cit.>, LRB <cit.>, and Hyperbolic <cit.>. 
Because these algorithms do not maintain a global data structure, they are never bottlenecked by cache hits, so throughput always increases with hit ratio.   



 §.§ Trends for future caching systems


There are two trends in computing and storage hardware.
First, newer CPUs have more and more cores, increasing their concurrency.

At the same time, disks are getting faster, with 
high-end disks having single-digit microseconds of latency. 
Figure <ref> shows the effects of these two trends.
We see that the hit ratio threshold p^*_hit (the hit ratio point where throughput starts dropping) will shift to smaller values in the future.  




 §.§ Implication of future trends


As we move to a higher number of cores per CPU and lower disk times, it is evident the LRU-like caching algorithms will start to experience more problems.  Given that LRU is the predominant caching algorithm used today, we need to figure out how we can adapt LRU-like algorithms so that their throughput doesn't deteriorate with increasing hit ratio.  

The easiest mitigation is to reduce the number of delink operations. This can be achieved by performing the delink operation probabilistically (probabilistic LRU).

As we have shown in Section <ref>, when q is very high, probabilistic LRU behaves like FIFO, where increasing the hit ratio only helps. 


Another solution is to simply reduce the hit ratio when it 
exceeds p^*_hit by reducing the cache size. This helps with both throughput and cost because the cache is expensive. 

Another approach is to send some of the requests to the disk directly without touching the cache. This solution has been proposed recently <cit.>.
In such a system, a request is either sent to the cache or to the disk, depending on the load of the cache. 
 










































§ PRIOR WORK



DRAM-based caches are increasingly deployed in today's system stack and have been the topic of many research papers <cit.>.




As mentioned in Section <ref>, most of the above works use the hit ratio as a proxy for system performance.  The others that do look at throughput only consider throughput or latency under a single thread (i.e., MPL=1), e.g., DistCache <cit.>, p-redis <cit.>, LRB <cit.>, GL-Cache <cit.>. By contrast, our paper models modern systems with MPL = 72 concurrent threads. Moreover, none of these works uses queueing-theoretic modeling to understand performance.

There are two papers that deserve a bit more attention because, like our paper, both are aimed at increasing throughput and both assume a high number of threads.  In the first paper, FrozenHot <cit.>, the authors fix the hit ratio at 99% and do not study throughput as a function of changing hit ratio.  
The second paper, NHC <cit.>, is quite different from ours because it uses a single-queue implementation of a cache (rather than a 3-queue implementation).  Consequently, there is no separate path for cache hits versus misses.
Finally, neither paper has any analytic modeling component.













Non-DRAM-based caches are outside this paper's scope.  



































§ CONCLUSION




The goal of this paper is to understand the effect of the cache hit ratio on the request throughput of DRAM-based software caching systems.  Such caching systems manage the cached items through a global linked list, where the particular eviction policy dictates the organization of this list.  Our investigation uses a three-pronged approach. First we create a queueing model of the particular eviction policy, which we evaluate analytically to obtain an upper bound on the throughput as a function of the hit ratio. We next use simulation to exactly evaluate the queueing network. Finally we use implementation to study the eviction policy outside of a queueing network.

For all policies studied, our simulation and implementation agree within 5%, indicating that our queueing network models are quite accurate. Another takeaway is that our analysis, while only providing an upper bound, is an excellent indicator of the point at which throughput stops increasing with hit ratio. The message is that for the evaluation of future eviction policies, it suffices to use analytic upper bounds to understand whether increasing hit ratio is a good idea.



While it intuitively makes sense that higher hit ratio should lead to higher throughput, we find that this is not always true.  In fact, we find that for a broad class of LRU-like algorithms (including LRU, most settings of Probabilistic LRU, and Segmented LRU), when the hit ratio gets high, the throughput actually decreases.  By contrast, the throughput of FIFO-like algorithms (including FIFO, extreme settings of Probabilistic LRU, CLOCK, S3-FIFO) always increases with the hit ratio. 

Our queueing analysis clearly shows why throughput drops with higher hit ratio for LRU-like algorithms.  In a nutshell, LRU-like algorithms have a common feature: a cache hit requires updating the global linked list. Our analysis shows that this update operation becomes the system bottleneck, meaning that many requests queue up there.  As a consequence, increasing the hit ratio increases the queueing time at this bottleneck, which reduces system throughput.   
Based on this intuition, we conjecture that many algorithms that we have not yet studied (ARC, LIRS, LFU, CACHEUS, LeCAR) should also exhibit this perverse behavior.  
By contrast, the FIFO-like algorithms all have the common feature that they do not update the global linked list upon cache hits, so increasing the hit ratio 

does not diminish throughput.  

We also study two major trends in computing and storage: newer CPUs have an increasing number of cores, while disk latencies are steadily decreasing.  We show that both these two trends imply that LRU-like algorithms will only behave worse in the future; i.e., throughput will start to decrease at lower and lower values of the hit ratio.

Funding: This work was supported by NSF-IIS-2322973 and NSF-CMMI-1938909.













plain





