## 3 The Design of the Cliff-Aware Cache Allocation Algorithm
### Cliff-Aware Cache Allocation Algorithm
Under each capacity constraint, we calculate the maximum (only use DRAM) and the minimum performances (only use SSD), and then we take 9 performance points at equal intervals between the max-min performance, for a total of 11 performance points. For each capacity and performance constraint, we calculate the results of the cliff removal and the cliff-aware algorithm. The algorithm parameters are shown in the Table 2. We use Equation (6) to calculate the cost difference between the two allocation results. \[diff=(cost_{aware}-cost_{remove})/cost_{remove}, \tag{6}\]

The result of proj_2 is shown in Figure 7 with the form of a heat map. The blue area indicates that the cliff-aware algorithm has achieved a lower cache cost; however, the red area manifests that the cliff removal algorithm has a cost advantage. From the distribution of the blue area, it is easily found that the dominant area of the cliff-aware algorithm is closely related to the position of the cliff. At the end area of the cliff (204,832), our algorithm has obtained a significant cost reduction, and then with performance requirements and the overall capacity increases, these kinds of advantages gradually decrease. In the area far away behind the cliff (321,845), there is a small blue area, because in the original MRC, there has a significant increase in the miss rate, which can be treated as an approximated performance area, so that the place for this part of the capacity in the high-speed cache can make a profit. \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline _cliff\_size\_threshold_ & 0.2 \\ _cliff\_hit\_rate\_threshold_ & 0.4 \\ _capacity\_proportion_ & 0.6 \\ _hit\_rate\_proportion_ & 0.4 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The algorithm parameters. Figure 7: The Allocation Results of proj_2. In addition, there are purple areas in the heat map, which indicates the cliff-aware algorithm is invalid. This is because the cliff removal can provide a higher cache hit rate under the same capacity. The max IOPS is calculated based on this hit rate, with all cache capacities as DRAM, so that even if our algorithm can obtain the same DRAM size but cannot realize the same hit rate, the performance requirements cannot be met. However, cliff-aware algorithms are not always effective. Figure 8 shows the allocation results of usr_1, whose performance area is <307,096, 373,856>. We observe that the cliff-aware distribution method does not reduce the cache cost in any capacity or performance constraints. The reason for this is that usr_1 has approximately vertical cache benefits at the initial area. Essentially, the cliff-aware algorithm is based on the phenomenon that the cliff performance area has a higher cache benefit than the MRC starting area, even if the cliff is removed sometimes, but if the revenue does not exist or is very small, the cliff-aware method cannot obtain a better result. ### Running on Real Devices

Figure 9 shows the cumulative latency probability curve of the two allocation methods. The green area represents the cliff-remove method, and the orange area represents the cliff-aware method. It is obvious that the cliff-aware method has a greater percentage of low-latency request finish times; the proportion of requests with a finish time of less than 130 us is increased by 33.3% (from 0.6 to 0.8). This is consistent with expectations that the cliff-aware method provides a better hit benefit with the same hit rate. ## 5 Conclusions

The cache performance cliff is a phenomenon that is closely related to application access patterns, which leads to a non-convex MRC, and it has been found that the optimal

Figure 8: The Allocation Results of usr_1. Figure 9: Probability Cumulative Curve of Request Latency (us). allocation under non-convex curves is an NP-complete problem. Existing studies use partition technology to eliminate it, but these techniques ignore the access hot spot contained in the cliff area.