Proactively prefetching data items instead of passively caching them has been utilized in practice to accelerate data access, e.g, for content data networks [1,2]. This strategy becomes even more appealing given that the advances in learning techniques provide effective tools to predict various data request patterns [3,4,5,6]. For certain applications, the prediction can be reasonably accurate [7,8]. To design an optimal strategy that combines prefetching and caching demands careful investigation. Proactively prefetching data brings the data into the cache before the actual requests occur. Passively caching data, on the other hand, only fetches the missed data from the backend storage after the requests arrive.
There is a trade-off between prefetching and caching. Due to competing the limited cache space, loading a prefetched data item into the cache typically has to trigger cache evictions, which may potentially introduce more cache misses for future requests. Although great efforts have been put to approximate the short-term and long-term data statistics to prefetch the most popular data [9,10,11,12,13,14], a fundamental question remains to be answered: even with a perfect knowledge of future requests, how to optimally prefetch data items beforehand instead of caching them upon requests?
Knowing the entire request sequence defines an offline algorithm, which nevertheless can help an online deployment. Using predictions has successfully made optimal offline policies practical in real applications [4,5,6]. Theoretically, the optimal offline policy provides an effective performance bound for online cases [15]. It can also be used to guide the online design. For example, by leveraging machine learning, an optimal offline policy can be used to train an online decision model using history information [16].
Previous studies on optimal offline prefetching and caching policies mainly focus on file systems [17,18,19,20,21,22], where prefetching and caching are not clearly distinguished. However, in many other important scenarios, e.g., for CDNs, prefetching and caching have significant differences. First, prefetching and caching can design separate cache update rules. For prefetching, the prefetched data remain in the cache until the future requests arrive. For caching, when a miss occurs, the requested data item is directly fetched from the backend, but whether to put it into the cache or not is up to the cache policy [15]. Second, prefetching incurs lower costs than caching. If fetching a missed data item is scheduled after the arrival of a request, it must be performed urgently to satisfy delay requirements. Prefetching, on the other hand, is performed beforehand and is not time-sensitive. It can be performed at a lower rate and avoid congestions, which allows more flexibility for scheduling. For example, data can be prefetched at off-peak times to reduce costs [23,24]. Third, prefetching can achieve a lower service delay by loading the data into the cache in advance. Therefore, the existing analysis on prefetching and caching for file systems does not directly apply in the above-mentioned scenarios.
To address this issue, we propose a cost-based service model to jointly optimize prefetching and caching, by assuming that prefetching incurs a lower cost than caching, due to less I/O consumption, more flexibility in scheduling and lower service delays. If the requested data is not cached, it can be served by fetching the data from the backend data storage after the request arrives, by paying a fetching cost. And the fetched data can be either loaded into the cache, or discarded to save space. Based on the predictions, we can prefetch the data items before they are requested. The prefetched data items need to remain in the cache until the requests arrive. Otherwise, they should not be prefetched at the first place, assuming that we know the future requests. With the goal to minimize the accumulated cost, we decide whether to cache a missed data item when a request occurs or prefetch it before the request arrives. We propose flowbased algorithms to find the optimal offline policy, as well as a lightweight "look-ahead" approximation policy that only knows the request information in the near future. These new designs not only reveal the fundamental trade-off between prefetching and caching, but also provide useful insights to improve real applications.
Our contributions are summarized as follows.
• We propose a cost-based caching model where different costs will be incurred depending on whether a missed data item is prefetched or fetched. With the objective to understand the fundamental trade-off between prefetching and caching, we investigate the optimal offline policy that minimizes the accumulated cost (see Section 2).
• We reformulate the optimal prefetching and caching problem as a min-cost flow problem. For a given request sequence of length N, the optimal policy can be obtained by flow-based algorithms in O(N 3/2 ) expected time (see Section 4).
• We analytically characterize the optimal policy by providing sufficient conditions under which prefetching the missed data is the optimal choice (see Section 5). Moreover, we prove that consistently prefetching is not always optimal, with a competitive ratio as high as 2, depending on the future requests and the prefetching cost (see Section 6).
• We propose a lightweight "look-ahead" approximation policy based on the insights revealed by the characteristics of the optimal policy. The approximation policy can be executed in real time and processes the entire trace in O(N) expected time. Performance guarantees are provided by deriving the competitive ratio (see Section 6).
• We conduct extensive experiments using real CDN traces and synthetic data requests that are generated from both heavy and light-tailed popularity distributions. The approximation policy always achieves near-optimal average performance (see Section 8).
Related Works: Caching algorithms have been extensively studied. It is known that Belady's algorithm [25] is an optimal offline eviction policy that minimizes the number of misses, assuming that the data items have identical sizes.
Specifically, it evicts the data item that is requested farthest in the future. When the data sizes are not identical, Belady's algorithm is no longer optimal, and finding the optimal offline policy is NP-hard. A few approximation policies have been proposed with different complexities and performance bounds [26,27,28,20]. One recent work [15] provides an asymptotically optimal solution and practical approximation algorithms with tight performance bounds for real traces. It leverages a flow-based representation, and shows that the optimal offline caching policy can be obtained by solving a min-cost flow problem. These offline policies have successfully guided the design of online algorithms [16].
Prefetching strategies, together with caching algorithms, have been widely explored in real applications, including processor architectures [29,30], file systems [31,32] and networks [33,34,35,24,36]. The offline optimal strategies have been studied for disk systems with an objective to minimize the stall time [17,18,19,20,21,22]. It is shown in [37] that the optimal offline solution can be found in polynomial time for single-disk systems. This problem is reformulated as a min-cost multi-commodity flow problem in [21]. For disk systems, the existing work does not distinguish the costs caused by caching and prefetching, which makes proactive prefetching almost always a better choice than passive caching. In this paper, we consider the scenarios where prefetching and caching can have different costs. Interestingly, we show that consistently prefetching is not always optimal. The new insights can be used to further improve the design of prefetching and caching mechanisms.
Consider a set of data items D = {d i : 1 ≤ i ≤ M} of unit sizes, and a sequence of data requests that arrive at the time points {τ n , 1 ≤ n ≤ N}. Let R n (R n ∈ D) denote the data item that is requested at time τ n and {R n } N n=1 denote the entire request sequence. We assume that {R n } N n=1 is known. If the requested data item is already in the cache, then the request can be served without paying a cost. However, if it is not cached, we have two options to serve the corresponding data request at different costs. The first option is to fetch the data from the backend after the request arrives, paying a fetching cost 1. We can decide whether to load the fetched item into the cache or not. The second option is to prefetch the data item before it is requested, paying a prefetching cost c, 0 ≤ c ≤ 1. Note that the prefetched data item has to be loaded into the cache. If the cache space is full, other items must be evicted before storing a new one. For ease of analysis, we first assume a best-case scenario where the prefetched data item is loaded into the cache right before it is requested. In Section 7, we will show that this assumption could be waived to some extent.
We observe that the optimal offline policy shall satisfy the following two properties. Property 1 (Interval caching decisions): As illustrated in [15], the optimal offline policy will not evict a cached data item d i between two requests for d i . Consider an example where d i is initially cached and requested at τ 1 and τ 5 . It is suboptimal to evict d i at some time (e.g., τ 3 ) between τ 1 and τ 5 , because storing d i in (τ 1 , τ 3 ] does not serve any requests and is a waste of caching resource. A wiser decision will be evicting d i right after serving R 1 or caching it at least until R 5 arrives. Therefore, we focus on caching policies that only evict a cached data item immediately after serving a request for it. Property 2 (Fetching without caching): When the optimal policy fetches a missed request, it must not load the fetched data into the cache and trigger evictions, because otherwise prefetching will be a better option. Therefore, it is sufficient to consider the policies such that data items will only be loaded into the cache by prefetching.
In the rest of the paper, we restrict the design space by only considering the policies that satisfy these two properties, and call them feasible policies. An optimal offline policy is guaranteed to exist in this design space.
Let l n = max {i < n : R i = R n }, which indicates that τ l n is the most recent time when R n is requested. If R n is the first request for that item, then set l n = 0. Formally, we define three decision variables for each request R n , 1 ≤ n ≤ N:
x n 1(Store R n in the cache during (τ l n , τ n ]),
where 1(E) is an indicator function that takes value 1 if the event E occurs, and 0 otherwise. The optimal offline policy for a cache of size b is the solution of the following optimization problem.
x n + f n + p n ≥ 1 for ∀n
x n , f n , p n ∈ {0, 1} for ∀n (4)
If x n = 0, i.e., R n is not stored in cache at τ n , then a cost f n + cp n will be induced depending on whether R n is fetched or prefetched as shown in the objective function (1). The cache capacity constraint is described by (2). If R n is prefetched (i.e., p n = 1), then the cache should have an available space to accommodate the prefetched data at τ n . Furthermore, Constraints (3) and (4) guarantee that the request R n must be either directly served from the cache or prefetched/fetched from the backend data storage.
Solving the optimal solution is equivalent to answering the following two questions: Q1: If a request is not cached, should we prefetch it beforehand or fetch it upon the request? Q2: If a data item is prefetched and the cache is full, which item should be evicted?
We will analytically answer these two questions in Section 5. And here are the short answers: A1: Prefetching the requested data is a better choice, if
• there exist requests for popular items in the near future, and the popular items are not cached currently, or
• the prefetching cost is sufficiently low.
The farthest-in-future data item should be evicted, if we choose to prefetch an item and the cache is full.
In this Section, we will introduce a motivating example to show that 1) prefetching is not always beneficial; 2) the optimal policy is non-trivial and depends on the prefetching cost. We always fetch the missed data after the request arrives, and make caching decisions based on Belady's algorithm which is optimal for caching without prefetching [38]. For this specific example, Belady's algorithm will never update the cache content. As shown in Figure 2, a total cost 3 will be incurred for the given sequence. Strategy 3 (Combination of fetching and prefetching): As shown in Figure 3, the first request is not stored in the cache and the requested data d 3 is fetched. Then, R 4 , R 5 , R 7 are prefetched with d 1 , d 4 , d 5 being evicted, respectively. A total cost 3c + 1 is incurred by this strategy. We have the following two observations from this motivating example. Observation 1: Prefetching is not always beneficial. If c > 3/5, Strategy 1 (always prefetching) will even incur a larger accumulated cost than Strategy 2 (always fetching). If the prefetching cost c is considerably small, then prefetching the data item before the request will be a better choice than fetching it upon the request. Observation 2: The optimal policy is non-trivial and highly depends on the prefetching costs. Actually, all the three strategies described above are optimal policies for the given trace and some specific c values. Specifically, Strategies 1, 2, 3 are optimal for c ∈ (0, 1/2], (2/3, 1], (1/2, 2/3], respectively.
Therefore, the optimal prefetching and caching decision depends on the joint effect of future requests and the prefetching cost c. Even for the same given trace, a fixed policy cannot work uniformly well for different c values. When the trace is long, the design space can be considerably large, since the possible combinations of fetching and prefetching will increase exponentially. How to efficiently find the optimal policy is a challenging task.
Instead of directly exploring the optimization problem (1), we leverage the underlying structure of prefetching and caching, and reformulate it as a min-cost flow problem which aims to send a certain amount of flow through a flow network at a smallest cost. We will show that the optimal prefetching and caching policy can be constructed from the min-cost flow.
In this paper, we use the flow notations that are shown in Figure 4. A flow network is represented by a directed graph where each edge is associated with a parameter tuple (capacity, cost). The total amount of flow going through an edge must not exceed its capacity. And a cost per unit flow will be charged for the flow going through the edge.
The node i is associated with a number β i representing its surplus/demand. If β i > 0, then the node is a source node. If β i < 0, then the node is a sink node. We will not label β i in the graph if it is zero.
In [15], the min-cost flow representation is used to solve optimal offline caching without prefetching, where each request is represented by a node. By constructing a proper flow network, the optimal offline caching can be constructed from the min-cost flow solution. However, the flow network constructed in [15] does not support prefetching operations, and therefore cannot be applied to our settings. To this end, we propose a more general min-cost flow representation, which supports both proactive prefetching and passive caching. In Section 4.1, we will show how to construct a flow network for a given sequence of requests. Then, we will prove that the optimal prefetching and caching policy can be obtained by finding the min-cost flow in Section 4.2.
Trace:
For a given sequence of requests, a corresponding flow network can be constructed, where each request is represented by four or five nodes and the nodes are connected by five types of edges including caching edges, fetching edges, prefetching edges, eviction edges and auxiliary edges. Detailed construction steps are presented as follows. The result of each step is illustrated in Figure 6 for the request sequence shown in Table 1 and a cache of size 2.
Step 1 (Generate nodes): For each request in the trace, if it is the first time to request the data, then generate five nodes where three of them are placed in the first row and two in the second, as shown in Figure 5. To facilitate the description of the following steps, we denote these nodes by n 0 , n 1 , n 2 , n 3 and n 4 . If the request is not the first request for the data, then we will only generate n 1 , n 2 , n 3 and n 4 nodes for that request. Moreover, for each data item, let the n 0 node of its first request be the source node, and the n 2 node of its last request be the sink node. These nodes are added for the example trace in Figure 6a. Step 2 (Add caching edges): As shown in Figure 6a. link the nodes in the second row by edges with capacity = b, cost = 0, where b is the cache size. These edges are named caching edges. A flow going through these edges represents that the corresponding request is stored in the cache.
Step 3 (Add prefetching edges): For each request, add an edge that is directed from the n 2 node of the last request for the same data and to the n 3 node of the request. If the request is the first request for that data, then add an edge directed from its source node n 0 to the n 3 node. The capacity of the edge is 1 and the cost is c. The flow going through these edges means that the corresponding requested data is prefetched. We add these prefetching edges in Figure 6b.
Step 4 (Add eviction edges): For each request, add an edge directed from its n 4 node to its n 1 node with capacity = 1 and cost = 0, as shown in Figure 6c. The flow going through these edges indicates that the corresponding requested data is evicted.
Step 5 (Add fetching edges): For each request, if it is not the last request for that data item, add an edge directed from the n 2 node of the request and to the n 1 node of the next request for the same data item, as shown in Figure 6d. Moreover, if it is the first request for the corresponding data item, add an edge directed from its n 0 to its n 1 node. The parameter tuple (capacity, cost) for these edges is set to be (1, 1). The flow going through these edges indicates that the corresponding request is a miss and the requested data is fetched.
Step 6 (Add auxiliary edges): For each request, add an auxiliary edge directed from its n 1 node to the n 2 node, as shown in Figure 6e. The parameter tuple (capacity, cost) is set to be (1, 0). The capacity of the auxiliary edge guarantees that the amount of flow going through the prefetching and the fetching edges must not exceed 1. The function of these auxiliary edges is to ensure that an integer flow routing solution can correspond to a feasible prefetching and caching policy (see Section 4.2).
According to the proposed six steps, a flow network can be constructed for a given data trace. See Figure 6e for the flow network constructed for the example trace in Table 1. In Section 4.2, we will demonstrate how the constructed flow network can be leveraged to solve the caching problem.
In this section, we will leverage the constructed flow network to find the optimal offline prefetching and caching policy. Specifically, we will show that there is an one-to-one correspondence between feasible prefetching and caching policies and integer flow routing solutions in the flow network.
Theorem 1. For a given data trace, a feasible prefetching and caching policy corresponds to an integer flow routing solution in the constructed flow network, and vice versa. An optimal prefetching and caching policy corresponds to an integer min-cost flow, and vice versa. The proof of Theorem 1 is straightforward. For a feasible prefetching and caching policy, we can construct an integer flow routing solution in the constructed flow network where the amount of flow going through each edge is an integer. Specifically, any cache operation (i.e., fetching, prefetching or eviction) corresponds to an edge (i.e., fetching, prefetching or eviction edge) in the flow network. Based on how the request is served, we can route the flow through the corresponding edges. Similarly, given an integer flow routing solution, a corresponding feasible prefetching and caching policy can be constructed from it.
Furthermore, the cost achieved by a prefetching and caching policy is the same as the cost of its corresponding flow routing solution. Therefore, the optimal prefetching and caching policy can be obtained by finding the integer min-cost flow solution.
Theorem 1 shows that an optimal prefetching and caching policy can be obtained by finding an integer min-cost flow. Formally, we define the flow-based optimal offline policy as follows. Flow-based optimal offline policy (π OPT ): Given a sequence of data requests, solve the integer min-cost flow for the flow network constructed according to the steps introduced in Section 4.1. Then prefetch, fetch or evict the data item if the min-cost flow is routed through the corresponding prefetching, fetching or eviction edges, respectively.
Note that the integer min-cost flow always exists, since the capacities, surpluses and demands are all integers in the flow network [39]. Moreover, the integer min-cost flow can be efficiently solved, if the prefetching cost c is assumed to be a rational number. Given a trace with N requests, there are at most 5N nodes and 6N -1 edges in the corresponding flow network. For rational prefetching costs, the problem is solvable in O(N 3/2 ) expected time [40,41,42].
Although the proposed flow-based policy π OPT is offline optimal, the problem is not satisfactorily solved for the following reasons:
• The flow-based algorithm cannot reveal the underlying insights of the optimal decision. It does not provide analytical answers to the two questions proposed in Section 2, i.e., whether to prefetch or fetch the missed data, and which data item to evict.
• The flow-based algorithm requires the knowledge about all future requests to find the optimal policy. Moreover, the policy cannot be executed in real time, since the optimal decision for a request is unavailable unless the process for the entire data trace is completed. In real practice, the request sequence could be too long to make this method practical [15].
These unanswered questions motivate us to
• analytically characterize the properties of the optimal policy and explicitly answer the questions proposed in Section 2 (see Section 5);
• design a lightweight approximation policy that requires only near-future information, can be executed in real time and achieves near-optimal performance (see Section 6).
In this section, we will analyze the characteristics of the optimal policy and explicitly answer the two questions proposed in Section 2. Notably, the questions will be addressed in reverse order. We will first show that evicting the farthest-in-future item is optimal when prefetching. Then, we will provide sufficient conditions under which prefetching is a better choice than fetching.
The farthest-in-future item is defined as the data item that is stored in the cache and will be reused after the other cached items. It is known that evicting the farthest-in-future item minimizes the number of misses for caching without prefetching [38]. In this section, we will generalize this result and show that evicting the farthest-in-future item is the optimal choice to minimize the accumulated costs for caching with prefetching. We start by proving the following lemma.
Lemma 1. Assume that a policy π n evicts the farthest-in-future items for the first n prefetching operations. Then, there exists a policy π n+1 that evicts the farthest-in-future items for the first n + 1 prefetching operations and does not incur a larger cost than π n .
Proof. Assume that τ m 1 is the first time when π n prefetches a request (i.e., R m 1 ) but does not evict the farthest-in-future item. Let d i be the item that is evicted by π n when prefetching R m 1 . We will construct a policy π n+1 that prefetches R m 1 and evicts the farthest-in-future item without incurring a larger cost than π n . The idea is to let π n+1 eventually have the same cache content as π n at some time point without introducing additional costs before that.
Assume that the next request for the farthest-in-future item arrives at τ m 2 , m 2 > m 1 . We may interchangeably use R m 2 to denote the farthest-in-future item and the request for it. Next, we will prove the lemma by considering two possible cases. Case 1: Consider the case where R m 2 is evicted by π n before τ m 2 . For each request, let π n+1 make the same prefetching/fetching decision as π n if the data is not cached by π n+1 , and evict the same data as π n if the data is stored in the cache. Then, there will be at most one item that is cached by π n+1 but not cached by π n . When π n evicts R m 2 , which is not cached by π n+1 according to the described update rule, let π n+1 evict the only item that is not cached by π n . Then the two policies lead to the same cache content, and no additional cost is introduced by π n+1 . Case 2: Consider the case where π n does not evict R m 2 before τ m 2 . Similar to Case 1, let π n+1 always make the same decisions as π n when possible. There is only one item that is cached by π n+1 but not cached by π n before τ m 2 . Then, at τ m 2 , let π n+1 prefetch R m 2 and evict the item that is not cached by π n . So far, the two policies will have the same cache content. Next, we will show that this prefetching operation by π n+1 will not result in a larger accumulated cost. Since R m 2 is the farthest-in-future item at τ m 1 , there must exist a request for d i between R m 1 and R m 2 . Note that d i should be prefetched or fetched by π n , but can be directly served by π n+1 from the cache. This prefetching/fetching operation by π n compensates for the prefetching operation performed by π n+1 at τ m 2 . Therefore, π n+1 will not incur a larger cost than π n .
Next, we will prove the optimal eviction mechanism by leveraging Lemma 1.
Theorem 2. There exists an optimal policy that evicts the farthest-in-future item for all prefetching operations.
Proof. Let π * be an optimal prefetching and caching policy. Assume that π * evicts the farthest-in-future items for the first n prefetch operations. Applying Lemma 1, we can construct a new policy which evicts the farthest-in-future items for the first n + 1 prefetching operations without increasing the accumulated cost. Using an induction argument, we can conclude that there must exists an optimal policy that evicts the farthest-in-future item for all prefetching operations.
Theorem 2 shows that evicting the farthest-in-future item is optimal when a data item is prefetched and the cache is full, which provides an explicit answer to the question Q2 proposed in Section 2. In the rest of the paper, we always follow the farthest-in-future eviction principle unless other specific mechanisms are stated.
In this section, we will analytically answer the question: whether we should prefetch or fetch an item if it is not stored in cache, assuming that the cache content is updated according to the farthest-in-future principle. In particular, we will provide sufficient conditions, under which prefetching is the optimal choice.
Let S n denote the set of cached data items before serving R n . If R n S n , then R n should be prefetched or fetched. Without loss of generality, assume that the cache is initially full and let S 1 denote the initial cache content. It suffices to analyze whether R 1 should be prefetched or fetched given that R 1 S 1 . Define
R σ is the farthest-in-future item, and τ σ is the first time when R σ is requested after τ 1 . Define ω = min{n > 1 : R n ∈ S 1 and R n is not requested in (τ n , τ σ )}.
Note that R σ is always the farthest-in-future item in the time interval [τ 1 , τ ω ], if no prefetching operation is performed.
We start by proving the following lemma.
Lemma 2. Assume c < 1. For any optimal policy π * , if π * decides to fetch R 1 , then it must also fetch all requests R n ,
Proof. Suppose for the sake of contradiction that there exists an optimal policy π * which fetches R 1 and prefetches R n , 1 ≤ n ≤ ω. Assume without loss of generality that R n is the first prefetched item after R 1 . Therefore, we have S 1 = S i for all 1 ≤ i ≤ n. Moreover, the farthest-in-future eviction principle yields S n+1 = S n ∪ {R n }\{R σ }. To introduce a contradiction, we will design a new policy π • which achieves the same cache state S n+1 as π * , but incurs a lower cost.
For the same request sequence and initial cache state S 1 , let π • prefetches R 1 and evicts R σ at τ 1 . For the requests arrive in the interval (τ 1 , τ n ), let π • make the same caching decision as π * . We have S n = S 1 ∪ {R 1 }\{R σ }, since there is no prefetching operations by π • in (τ 1 , τ n ). Then, let π • prefetch R n and evict R 1 . Consequently, it achieves the same cache state S n+1 as π * . Notably, the caching decisions of π * and π • in [τ 1 , τ n ] are all identical, except that π * fetches R 1 but π • prefetches R 1 . As a result, the cost of π • is lower than the cost of π * since c < 1, which contradicts to our assumption that π * is the optimal policy. Therefore, we prove the lemma.
Leveraging the property of the optimal policy illustrated in Lemma 2, we will show that prefetching before the request is the optimal choice under some insightful conditions. Theorem 3. Assume that the upcoming request R 1 is not stored in the cache. Prefetching R 1 is the optimal choice, if any of the following two conditions is satisfied:
• C1: There is a request R n , 1 ≤ n ≤ ω, such that R n S 1 and R n is requested at least twice in the time interval
[τ 1 , τ σ ];
• C2: The prefetching cost c satisfies c ≤ L/(L + 1), where L = ω n=1 1(R n S 1 ) is the number of requests that arrive in the time interval [τ 1 , τ ω ] but do not belong to S 1 .
Proof. Assuming that the upcoming request R 1 is a miss, we will prove that under any of the proposed conditions, prefetching R 1 is the optimal choice to minimize the accumulated cost.
First, we will show that under Condition C1, prefetching R 1 is a better choice than fetching. Assume that R 1 is requested at least twice in the time interval [τ 1 , τ ω ]. Suppose for the sake of contradiction that the optimal policy π * fetches R 1 . Next, we will construct a new policy π • that prefetches R 1 and incurs a lower accumulated cost than π * .
Consider the case where π * evicts R σ when prefetching some missed request R k for 1 < k < σ. Then let π • prefetches R 1 and evict R σ , and then prefetch R k and evict R 1 . Furthermore, let π • perform the same operation as π * for other requests. Then, π • will reduce the cost of π * by 1c.
Then, consider the case where π * keeps R σ in the cache until τ σ . Let R n 1 = R 1 for some n 1 ∈ (1, σ). If R 1 is fetched by π * , then let π • prefetches R 1 and evict R σ , and then prefetch R s igma and evict R 1 . For other requests, let π • perform the same operation as π * . Note that R n 1 will be a hit for π • , and therefore, π • reduces the accumulated cost of π * by 2 -2c. Instead, if R n 1 is prefetched by π * and meanwhile some cached data d i is evicted, then the next request for d i must arrive after τ σ due to the farthest-in-future eviction principle. Let π • prefetches R 1 and evict R σ , and then prefetch R σ and evict d i . For other requests, let π • make the same decisions as π * . Then, π • reduces the cost of π * by 1c. Therefore, we prove that prefetching is the optimal choice if R 1 is requested twice before τ σ .
Using a similar argument, we can prove that if there is a request R n , 1 < n < ω, such that Condition C1 holds, then prefetching R n is the optimal choice. Moreover, since n < ω, we can conclude that prefetching R 1 is also the optimal by applying Lemma 2.
Next, we will show that if Condition C2 holds, then prefetching R 1 is optimal. Let R n i , 1
denote the L requests that are not in the set S 1 . Suppose for the sake of contradiction that the optimal policy π * fetches R 1 . Then, Lemma 2 indicates that π * must also fetch all the L missed data items before τ ω . Let π • prefetch R 1 and evict R σ , prefetch R n i+1 and evict R n i for 1 ≤ i ≤ L -1, and then prefetch R σ and evict R n L . For these requests, π • pays a total cost (L + 1)c and π * pay a total cost L. For other requests, let π • make the same decisions as π * . Since c ≤ L/(L + 1), π • induces a lower cost than π * . Therefore, we prove that prefetching R 1 is the optimal choice if Condition C2 holds.
Theorem 3 provides sufficient conditions under which prefetching is the optimal choice. And these conditions reveal the following useful insights that can be leveraged to guide practical designs:
• Prefetching the upcoming request is optimal, if there exist popular items that will be requested in the near future and are not stored in the cache currently. Note that the upcoming request may not necessarily be popular. The reason is that the popular data will be prefetched and trigger evictions. Thus, evicting these items earlier can be even more beneficial, because more prefetching opportunities (e.g., prefetching the upcoming request) will be provided. This insight is characterized by Condition C1.
• Prefetching is optimal if the prefetching cost c is sufficiently low. This insight is straightforward. Condition C2 characterizes the critical value of c to make prefetching a better choice than fetching. Note that, since 1/2 ≤ L/(L + 1) for L ≥ 1, prefetching is always optimal for any data traces if c ≤ 1/2.
Note that the proposed conditions only depend on the current cache content S 1 and the request information between R 1 and R σ . No information after τ σ or before τ 1 is required. In Section 6, we will leverage this nice property to propose an approximation policy that only requires near-future information. However, if neither C1 nor C2 is satisfied, the optimal decision will depend on the future requests after R σ .
In this section, we propose an approximation policy using near-future information, and show that it is close to optimal by deriving the competitive ratio.
Based on the analytical results obtained in Section 5, we propose an approximation policy as follows. Approximation Policy (π A ): Prefetch the missed request and evict the farthest-in-future item, if c ≤ √ 2/2, or any of the conditions C1 and C2 introduced in Theorem 3 is satisfied. Otherwise, fetch the missed item but do not store it into the cache.
Applying Theorem 3, we know that, for c
, π A prefetches a data item only when prefetching is the optimal choice. The threshold √ 2/2 is chosen to achieve a better competitive ratio, as shown in Section 6.2. Notably, the proposed approximation policy makes caching and prefetching decisions merely based on the request information before τ σ . If the data requests are generated independently from a popularity distribution (e.g., Zipf's distribution as observed in real practice [43]), then τ σ is independent of the trace length N. Although τ σ can depend on the cache size b, considering the fact that the trace length is typically far larger than the cache size in real practice, N is the dominant term in the time complexity and the impact of b is negligible. Therefore, π A has an expected time complexity O(1) to make decisions for a single request and O(N) to process the entire trace. In Section 8, we verify through simulations that the required information for π A to make decisions for a single request does not scale with the trace length. In summary, unlike the flow-based algorithm that need all future requests to make optimal decisions, π A is lightweight and practical since
• it only exploits near-future information to make decisions;
• it does not have to process the entire trace to find the optimal decision for a single request and can be executed in real time.
In this section, we will show that the proposed approximation policy achieves near-optimal performance by characterizing its competitive ratio.
We introduce two additional policies (i.e., always prefetching policy and always fetching policy) as benchmarks. Always Prefetching Policy (π P ): Always prefetch the missed item. If the cache is full, evict the farthest-in-future item. Always Fetching Policy (π F ): Always fetch the missed item. If the next request for the fetched item arrives before the farthest-in-future item, then evict the farthest-in-future item and store the fetched one in cache. Otherwise, do not load the fetched item into the cache.
π P and π F represent two extreme policies that always prefetch or fetch the missed data. To emphasize different consequences of fetching and prefetching, we eliminate the impact of eviction by applying the optimal eviction to both π F and π P . Notably, π F is also known as the Belady's algorithm [38,44], which is the optimal caching policy when prefetching is disabled and data sizes are all identical. We will use π F and π P as benchmarks to show that a wise combination of prefetching and fetching (e.g., policy π A ) can yield better performance. Specifically, we will prove that π A always achieves the smallest competitive ratio among the three policies.
Let cost(π, {R n } N n=1 ) denote the accumulated cost achieved by a policy π for a given trace {R n } N n=1 . The competitive ratio for a given prefetching policy π is defined as
, where π * represents the optimal policy. The competitive ratio evaluates the worst-case performance of a policy. From the definition, we have r π ≥ 1 for any policy π. Let r A , r P , r F denote the competitive ratio of the proposed approximation policy, always prefetching policy and always fetching policy. Theorem 4. Given the prefetching cost c, the competitive ratios of π F , π P and π A can be computed as r F = 1/c for c ∈ (0, 1],
In addition, for c ∈ (
where b is the cache size.
Proof. For compactness, we omit the term {R n } N n=1 in the cost expression cost(π, {R n } N n=1 ). The competitive ratio results for π F , π P and π A are proven as follows.
Competitive ratio for π F : For the π F policy, we will first show that its competitive ratio is upper bounded by 1/c. Consider a new setting where fetching cost is the same as the prefetching cost c, 0 ≤ c ≤ 1. Let π • and cost • denote the optimal policy and the minimum cost under the new setting. Then, for any request sequence, we have cost • ≤ cost(π * ). Note that there is no additional benefits to prefetch in the new scenario. Therefore, there must exist a π • that always makes the same decision as π F for the same request sequence. As a result, we have, for any request sequence
Next, we will show that for any > 0, π F can achieve a competitive ratio larger than 1/c -. For a given cache size b, assume without loss of generality that the set of items {d i : 1 ≤ i ≤ b} is initially stored in the cache. Consider the request sequence
and achieves a cost k. In contrast, if we choose to prefetch every missed item and evict the farthest-in-future item, a cost (k + 1)c will be introduced. Thus, we have
.
By choosing the k ≥ 1/( c), a lower bound 1/ccan be achieved for ∀ > 0. Combining the upper and lower bounds, we prove the tight competitive ratio for π F .
Competitive ratio for π P : For c ∈ [0, 1/2], we will show that π P is the optimal policy. Assume that R 1 is a miss. A cost 1 will be induced if R 1 is fetched. However, the request can be served at a lower cost 2c, if we choose to prefetch R 1 and evict some cached data saying d i , and then after serving R 1 , prefetch d i back to the cache and evict R 1 . Therefore, when c ∈ [0, 1/2], the optimal policy always choose to prefetch the miss requests. Moreover, according to Theorem 2, we can conclude that π P is the optimal policy for c ∈ [0, 1/2]. For c ∈ (1/2, 1], we will first show that r P is upper bounded by 2c. We know that π P is the optimal policy for c = 1/2. For a given request sequence, let cost • denote the cost achieved by π P with c = 1/2. Then, we have, for the same request sequence and c > 1/2 cost • ≤ cost(π * ) ≤ cost(π P ), and therefore
Next, we will show that there exists a request sequence such that a competitive ratio 2c is achieved, if M ≥ b + 2, where M is the total number of data items and b is the cache size. Assume without loss of generality that d i , 1 ≤ i ≤ b, are initially stored in the cache. Consider a periodic request sequence that repeats the request pattern
. π P will induce a cost 4c in each period. And the optimal policy is always fetching the missed data, which induces a cost 2 in each period. Therefore, a competitive ratio 2c is achieved and we can conclude that r P = 2c. Competitive ratio for π A : For c ≤ √ 2/2, π A always makes the same decision as π P , and therefore, achieve the same competitive ratio. We have
For √ 2/2 < c ≤ 1, we will first show that r A is upper bounded by 1/c. According to Theorem 3, we know that if π A decides to prefetch the missed item, then prefetching must be the optimal choice. Therefore, π A only yields worse performance than π * , if π A decides to fetch the missed item while π * decides to prefetch.
We will introduce a new policy π • to bound the competitive ratio. Given a request sequence, let π • make the same decision as π A if the decision is optimal. However, when the decision of π A is not optimal (i.e., when π A decides to fetch, while π * decides to prefetch), let π • prefetch the missed data without evicting any cached items. Then, after serving the request, let π • evict the prefetched data. Note that π • breaks the cache capacity constraint and is not a feasible solution. We will use π • to provide a lower bound for the cost achieved by the optimal policy π * . Specifically, for a given request sequence, let cost • denote the cost induced by π • . We will show cost • ≤ cost(π * ) for any given request sequence.
Assume without loss of generality that R 1 is a miss and π A decides to fetch R 1 , while the optimal choice is to prefetch. According to Theorem 2, the optimal policy π * will evict the farthest-in-future item R σ and serve R 1 at a cost c. In contrast, the policy π • will keep R σ in cache and serve R 0 at the same cost c. Since π A chooses to fetch R 1 , according to Condition C1, the next request for R 1 must arrive after the farthest-in-future item R σ . Based on the farthest-in-future principle, the cache content of π • is more beneficial than that of π * . Therefore, we have cost • ≤ cost(π * ). In addition, since π A and π • always have the same cache content before serving each request, we have cost(π A )/cost(π • ) ≤ 1/c, which yields
for any request sequence. Next, we will show the lower bound for r A when √ 2/2 < c ≤ 1. Assume without loss of generality that {d i , 1 ≤ i ≤ b} are stored in the cache initially. The lower bound can be achieved by a periodic trace that repeats the request pattern {d b+1 , d 1 , d 2 , • • • , d b }. π A will always choose to fetch the missed item. And the cache content under π A is also updated periodically with period b(b + 1). For the first b(b + 1) requests, the approximation policy achieves a total cost b, and the optimal policy is to always prefetch the missed item which yields a cost (b + 1)c. Therefore, we have
In Theorem 4, we provide upper and lower bounds for the competitive ratio achieved by π A , as well as the exact competitive ratios for π F and π P . Moreover, the upper and lower bounds for r A are asymptotically tight as the cache size goes to infinity. We plot r F , r P and the upper bound of r A in Figure 7. It is easy to conclude from Theorem 4 and observe in Figure 7 that
for ∀c ∈ [0, 1]. The proposed approximation policy always achieves the smallest competitive ratio which is at most √ 2 ≈ 1.414. Therefore, π A is near optimal in terms of the worst-case performance. Furthermore, in Section 8, we will verify that π A also achieves near-optimal average performance for both synthetic and real data traces.
Note that applying π P for c ≤ √ 2/2 and π F for c > √ 2/2 can achieve the same competitive ratio as π A . However, experiments in Section 8 show that simply switching π F and π P at the threshold c = √ 2/2 will incur considerably larger average costs than the proposed approximation policy π A .
In this section, we discuss the possibility of waiving the perfect prefetching time assumption, and the generalization of the proposed min-cost flow representation to support heterogeneous prefetching and fetching costs and variable data sizes.
In our previous model, a perfect prefetching time is assumed to simplify the analysis. Specifically, we assume that the prefetched data item is loaded into the cache right before it is requested. In this section, we will argue that all the previous results will still hold, even when the prefetched data is loaded some time ahead of the request.
Recall that R 1 is the upcoming request and R σ is the farthest-in-future item. Let {R -n } n≥1 be the sequence of historical requests as shown in Figure 8. Define
R -θ is the most recent request that is identical to R σ . Assume that the policy decides to prefetch R 1 . We claim that, it is equivalent to load R 1 into the cache at any time point in the interval (τ -θ , τ 1 ), as long as the farthest-in-future eviction policy is adopted. According to the definition of θ, the farthest-in-future item is not requested in the time interval (τ -θ , τ 1 ). Consequently, evicting R σ (i.e., R -θ ) and loading R 1 at any time between τ -θ and τ 1 does not impact the cost or the future decisions. In contrast, if R 1 is prefetched and loaded into the cache before τ -θ with R σ evicted, then R -θ will be a miss and can incur additional costs.
Since the pre-mentioned policies (including π OPT , π A and π P ) all adopt the farthest-in-future eviction, the main results of this paper still hold, if the prefetched data is loaded into the cache in the time interval (τ -θ , τ 1 ). Specifically,
• The proposed policies (including π OPT , π A and π P ) still work. In particular, π OPT , π A and π P will first make the decision of whether a data item should be prefetched or not. Then, we can find the τ -θ for each prefetched item and schedule the prefetching time accordingly.
• The π OPT is still optimal, and the competitive ratio analysis for π A , π P and π F still hold, since the optimal decision and the incurred cost will not be impacted if the prefetched data is loaded between τ -θ and τ 1 .
The value of θ indicates the flexibility of choosing the prefetching time. When the requests are independently generated from a popularity distribution, θ is a random variable that depends on the cache size and is independent of the trace length and the prefetching cost. In Section 8, we will show that θ could be considerably large through simulations.
In the previous setting, we assume that the prefetching/fetching costs are identical for every requests. However, in real practice, the cost to fetch a data item can depend on the traffic load and be time-varying. Similarly, the prefetching costs may also take different values to support more flexible model settings. Our flow-based method can be easily generalized to heterogeneous prefetching and fetching costs by setting the costs for prefetching and fetching edges in the flow network as the corresponding values. The cycle-canceling algorithm can still find the optimal solution as long as the costs are rational numbers.
For real CDN traces, data sizes can take disparate values ranging from a few bytes to gigabytes [45,46]. The constructed flow network can be modified to accommodate variable data sizes. Specifically, for data item, we can set its surplus/demand and the capacities of prefetching, fetching, eviction and auxiliary edges as the data size. However, we may not be able to find the optimal policy via the min-cost flow, since it is possible that the min-cost flow prefetches/fetches a fraction of the data item, which is not feasible for a caching policy. Instead, by leverage the min-cost flow, we can construct the upper and lower bounds for the performance of the optimal offline policy.
The cost achieved by the min-cost flow is a lower bound for the cost achieved by the optimal policy, since fractional solutions are allowed for the min-cost problem. Additionally, we can construct a feasible caching policy from the mincost flow by rounding up the fractional solution. Specifically, if a fraction of some request goes through the fetching edge in the flow network, then we will fetch the whole item. Otherwise, we will perform the same operation as the min-cost flow. The rounded solution is a feasible prefetching and caching policy and therefore provides an upper bound for the performance of the optimal policy. Notably, if the lower and upper bounds coincide, the rounded solution becomes optimal. It is shown in [15] that for caching without prefetching, the bounds are asymptotically tight under mild assumptions. Whether similar asymptotic results hold for prefetching deserves future investigations.
In this section, we evaluate the average performance for various policies of interest using both synthetic and real data traces. Specifically, in Experiment 1, we evaluate the policies for data requests generated from light-tailed and heavy-tailed popularity distributions. Real CDN traces are used for evaluation in Experiment 2. Moreover, in Experiment 3, we illustrate the amount of future information that is required by the approximation policy.
In addition to the pre-mentioned policies (π OPT , π A , π P and π F ), we also simulate the optimal static policy (denoted by π S ). The optimal static policy stores the most popular data in the cache, and will neither update the cache content nor prefetch future requests. When the requests are generated independently from a popularity distribution, the optimal static policy can provide a lower bound for the costs incurred by a bunch of statistic-based policies (e.g., LRU, LFU) that only exploit data statistics and are unaware of the exact request sequence. In the following experiments, the cache is initially empty and the data items are prefetched, fetched or evicted based on specific policies.
Experiment 1. In this experiment, we compare the average performance of the proposed policies under both light-tailed and heavy-tailed data popularity distributions. In particular, we consider three popularity distributions with different tails. The first one is a light-tailed exponential distribution with P
, where c 1 = 1/ 10 6 i=1 exp(-0.3i) ≈ 0.3499 is a normalization factor. The second popularity distribution is a heavy-tailed Weibull distribution with P[R n = d i ] = c 2 • exp(-i 0.6 ), 1 ≤ n ≤ 10 5 , 1 ≤ i ≤ 10 6 , where c 2 ≈ 0.8671. The third one is a heavy-tailed Zipf's distribution with P[R n = d i ] = c 3 /i 2 , 1 ≤ n ≤ 10 5 , 1 ≤ i ≤ 10 6 , c 3 ≈ 0.6079. For each popularity distribution, we generate a sequence of 10 5 requests independently and test the proposed policies for a cache of size 20. The average cost incurred by a request is plotted in Figure 9.
It can be observed from Figure 9a that the flow-based optimal offline policy π OPT always incurs the smallest cost, and the proposed approximation policy π A achieves near-optimal performance. The always-prefetching policy π P 0.5 0.6 0.7 0.8 0.9 achieves the optimal performance when c = 0.5. For c > 0.5, π P always incurs larger costs than π OPT . Note that when c is close to 1, always prefetching can incur as high costs as the static optimal policy π S , which loses the advantage of the sample path. Moreover, the always-fetching policy π F (a.k.a. the Belady's algorithm [38]) only achieves the optimal performance when the prefetching cost is 1. Although π F and π A have almost the same competitive ratios for c ∈ [ √ 2/2, 1], π A achieves significantly better average performance when c < 1. Therefore, simply switching π F and π P at the threshold √ 2/2 (≈ 0.71) can incur much larger average costs than π A and π OPT . The same trend can be observed for heavy-tailed Weibull distributions in Figure 9b. However, the performance difference between π A and π P are not as large as those for exponential distributions. Moreover, when the distribution tail is even heavier (e.g., for Zipf's popularities), both π A and π P achieve almost optimal performance as shown in Figure 9c. An intuitive explanation is that when the popularity is heavy-tailed, the requests will be less concentrated. As a result, it is more likely to have an unpopular data item stored in the cache, which provides a harmless eviction opportunity for prefetching. In such scenarios, prefetching is almost always the optimal choice, and therefore, π A , π P and π OPT could achieve similar performance. Experiment 2. In this experiment, we test the proposed policies using a real CDN data trace 1 . The trace contains a million requests for 449380 distinct data items where the data sizes are set to be 1. In Figure 10, we plot the empirical data popularities which can be approximated by a Zipf's distribution with P[R n = d i ] = 0.0313/i 0.88 , 1 ≤ i ≤ 449380, 1 ≤ n ≤ 10 6 . We simulate the proposed policies for a cache of size 20000 using the request sequence in the CDN trace. The average costs are plotted in Figure 11. It can be observed that π A and π P achieve almost the same performance as π OPT , which coincides with the observation in Experiment 1 for Zipf's popularities. Experiment 3. In this experiment, we will verify that the approximation policy π A only requires near-future information to make decisions for a single request. Let T denote the number of future requests required for making decision for a request. We will evaluate the statistics of T under different trace lengths, prefetching costs and cache sizes. Generate data requests from the Zipf's popularity distribution considered in Experiment 1. Note that we omit the experiments for exponential and Weibull distributions since the obtained results and the revealed insights are similar. First, set c = 0.85, b = 50. We collect the statistics of T for multiple traces with different lengths. The results are presented as box plots in Figure 12a, where the central red bar and the green "+" sign represent the median and the mean, respectively. The top and bottom edges of the box indicate the 75 th and 25 th percentiles. The whiskers extend to the extreme values within 1.5 × IQR (interquartile range) [47]. All these statistics of T do not scale with the trace length N, which verifies the analysis in Section 6. Furthermore, we investigate how the cache size and the prefetching cost can impact T . Set N = 5 × 10 5 . For a fixed b = 50, we collect the statistics of T under different prefetching costs. The results are plotted in Figure 12b. For a fixed c = 0.85 and repeat the experiments for different cache sizes, and present the results in Figure 12c. As we expect, the required information will increase with the prefetching cost, since Condition C2 of π A becomes stricter for a larger c. Moreover, T can scale considerably with the cache size, because τ σ and τ ω will take larger values, and the miss ratio will decrease. Consequently, more future observations are required to check whether Conditions C1 and C2 hold. For a typical scenario where the policy is applied for a fixed cache size and processes requests that keep arriving, the future information required by π A will not scale up.
Experiment 4. It is shown in Section 7 that the main results of this paper will still hold as long as the prefetched data is loaded into the cache in the time interval (τ -θ , τ 1 ) for R 1 . And the value of θ could represent the flexibility of choosing the prefetching time. In this experiment, we show that θ could be considerably large by evaluating its statistics for the Zipf's popularity distribution defined in Experiment 1. Specifically, we first set c = 0.85 and b = 50, and conduct simulations for different trace lengths. Then, we repeat the experiment for N = 5 × 10 5 , b = 50 and different prefetching costs. Next, we conduct simulations for N = 5 × 10 5 , c = 0.85 and different cache sizes. The results are shown as the box plots in Figure 13, where the symbols represent the same statistics as those in Experiment 3. It can be observed from Figure 13a and 13b that θ will not be impacted by the trace length or the prefetching cost. The mean of θ is round 250, which is considerably large. Moreover, as shown in Figure 13c, θ will increase with the cache size. For b = 250, the mean of θ could be as large as 5907, which brings even more flexibility to choose the prefetching time. The intuition is that, for large cache sizes, the farthest-in-future item will be less popular. And therefore, the most recent time when the farthest-in-future item was requested (i.e., τ -θ ) is far in the past.
To characterize the fundamental trade-off between prefetching and caching, we developed a cost-based service model and investigated the optimal offline policy, assuming that the entire request sequence is known. We casted it as a min-cost flow problem, and found the optimal policy for a data trace of length N via flow-based algorithms in O(N 3/2 ) expected time. To apply this offline algorithm without the precise knowledge on future requests, we utilized the characteristics of the optimal solution and derived non-trivial conditions for an optimal prefetching and eviction policy. Based on these insights, we proposed a lightweight approximation policy using the predicted requests in the near future. The approximation policy can be applied in real time and process the entire trace in O(N) expected time, with a competitive ratio √ 2 ≈ 1.4. Extensive experiments verified that it achieves near-optimal average performance for both light and heavy-tailed popularity distributions.
The trace is originally used for evaluation and labeled as "cdn1" in[15]. We use the first one million requests in the trace.