SGDP: A Stream-Graph Neural Network Based Data Prefetcher
Data prefetching is important for storage system optimization and access
performance improvement. Traditional prefetchers work well for mining access
patterns of sequential logical block address (LBA) but cannot handle complex
non-sequential patterns that commonly exist in real-world applications. The
state-of-the-art (SOTA) learning-based prefetchers cover more LBA accesses.
However, they do not adequately consider the spatial interdependencies between
LBA deltas, which leads to limited performance and robustness. This paper
proposes a novel Stream-Graph neural network-based Data Prefetcher (SGDP).
Specifically, SGDP models LBA delta streams using a weighted directed graph
structure to represent interactive relations among LBA deltas and further
extracts hybrid features by graph neural networks for data prefetching. We
conduct extensive experiments on eight real-world datasets. Empirical results
verify that SGDP outperforms the SOTA methods in terms of the hit ratio by
6.21%, the effective prefetching ratio by 7.00%, and speeds up inference time
by 3.13X on average. Besides, we generalize SGDP to different variants by
different stream constructions, further expanding its application scenarios and
demonstrating its robustness. SGDP offers a novel data prefetching solution and
has been verified in commercial hybrid storage systems in the experimental
phase. Our codes and appendix are available at
https://github.com/yyysjz1997/SGDP/.
Yiyuan Yang, Rongshang Li, Qiquan Shi, Xijun Li, Gang Hu, Xing Li, Mingxuan Yuan
# SGDP: A Stream-Graph Neural Network Based Data Prefetcher

###### Abstract

Data prefetching is important for storage system optimization and access performance improvement. Traditional prefetchers work well for mining access patterns of sequential logical block address (LBA) but cannot handle complex non-sequential patterns that commonly exist in real-world applications. The state-of-the-art (SOTA) learning-based prefetchers cover more LBA accesses. However, they do not adequately consider the spatial interdependencies between LBA deltas, which leads to limited performance and robustness. This paper proposes a novel Stream-Graph neural network-based Data Prefetcher (SGDP). Specifically, SGDP models LBA delta streams using a weighted directed graph structure to represent interactive relations among LBA deltas and further extracts hybrid features by graph neural networks for data prefetching. We conduct extensive experiments on eight real-world datasets. Empirical results verify that SGDP outperforms the SOTA methods in terms of the hit ratio by 6.21%, the effective prefetching ratio by 7.00%, and speeds up inference time by 3.13\(\times\) on average. Besides, we generalize SGDP to different variants by different stream constructions, further expanding its application scenarios and demonstrating its robustness. SGDP offers a novel data prefetching solution and has been verified in commercial hybrid storage systems in the experimental phase. Our codes and appendix are available at [https://github.com/yyysjz12997/SGDP/](https://github.com/yyysjz12997/SGDP/).

 data prefetching, graph neural networks, logical block address, data mining

## I Introduction

In the big data era, the demand for high-performance storage systems is increasing rapidly. The Input/Output (I/O) speed gap between different storage devices in a hybrid storage system might cause high access latency [16]. To fill this gap, the cache is designed to temporarily keep data that are likely to be accessed in the future. The performance of cache, commonly represented by **hit ratio**, has a direct impact on the performance of the whole storage system.

To improve the hit ratio, data prefetching is introduced as an essential technique in the cache. Prefetchers reduce access latency by fetching data from their original storage in slower memory to cache before they are needed [54]. Common block-level cache prefetchers take in logical block address (LBA) access sequences as input (i.e., some integer numbers). Prefetchers predict the LBA of the block that might be accessed in a short time and decide whether to pre-load it or not. There are two major challenges in the design of effective prefetchers. First, the LBA access sequences in real-world applications have complex patterns due to concurrent and random accesses from different users or applications, which are common in modern large-scale storage systems [22, 51]. Second, effective prefetchers need to be accurate. Inaccurate prefetchers waste both I/O bandwidth and cache space [19]. Therefore, designing effective prefetchers is vital for storage systems.

Traditional prefetchers prefetch the data by matching LBA access sequences to specific predefined rules. However, they can hardly adapt to complex real-world scenarios as their predefined rules are limited to specific simple patterns such as sequential reading [18]. To learn complex patterns, several learning-based methods [1, 3, 4, 7] are applied. Recently, long short-term memory (LSTM) based methods like DeepPrefetcher [20] and Delta-LSTM [5] have shown promising results. They model the **LBA delta** (i.e., the difference between successive access requests), which covers more LBA accesses. However, due to concurrent accesses, the chronological order of LBA deltas within a short time period is likely to be disrupted. DeepPrefetcher and Delta-LSTM disregard the internal temporal correlation and result in limited performance.

Graph structures can effectively use nodes and edges to represent LBA (delta) and access sequence, and can mine intrinsic access patterns beyond chronological order in hybrid storage systems like relational databases. Therefore, to improve the performance of prefetching especially in applications with complex patterns, this work models the relations among LBA deltas using graph neural network, and proposes
a novel method called Stream-Graph Neural Network-Based Data Prefetcher (**SGDP**), as shown in **Figure**1. Specifically, we encode LBA deltas and split them into shorter streams. Then we build weighted directed graphs based on LBA delta streams and extract relations of sequential connection and temporal accesses of LBA deltas from each stream, which are represented as sequential connect matrices and full-connect matrices, respectively. By fusing those two matrices, we get hybrid matrices that contain the relations of LBA deltas. Finally, the hybrid matrix, along with embedding LBA deltas of each stream is fed into a gated graph neural network to learn access patterns for prefetching. Extensive experiments on eight real-world datasets show that SGDP outperforms the SOTA prefetchers in terms of performance and efficiency.

The contributions of this work are summarized as follows:

1. SGDP can accurately learn complex access patterns by capturing the relations of LBA deltas in each stream. The relations are represented by sequential connect matrices and full-connect matrices using graph structures.

2. To the best of our knowledge, SGDP is the first work that utilizes the stream-graph structure of the LBA delta in the data prefetching problem. Using gated graph neural networks and attention mechanisms, we extract and aggregate sequential and global information for better prefetching.

3. As a novel solution in the hybrid storage system, SGDP can be generalized to multiple variants by different stream construction methods, which further enhances its robustness and expands its application to various real-world scenarios.

4. SGDP outperforms SOTA prefetchers by 6.21% on hit ratio, 7.00% on effective prefetching ratio, and speeds up inference time by 3.13\(\times\) on average. It has been verified in commercial hybrid storage systems in the experimental phase and will be deployed in the future product series.

## II Related Work

**Traditional Data Prefetcher** The most commonly used prefetcher is the Stride prefetcher [27] which uses a reference prediction table to store the last few accessed LBAs and the stride to obtain the required LBA. Although it can capture a constant stride in sequential access patterns, it can hardly detect variable strides in irregular access patterns. Temporal prefetchers learn irregular access patterns by memorizing pairs of correlated LBAs [34, 39, 8, 40]. However, due to inconsistent correlation address pairs, these traditional methods cannot achieve good performance in practice.

**Learning-based Data Prefetcher** Prefetching needs to be accurate, as a small error in the numerical value of a prefetched LBA leads to useless prefetch and a waste of cache space and I/O bandwidth. Even though prefetching can be treated as a prediction problem, regression-based time-series prediction models like ARIMA are not widely considered by researchers. Classification-based methods seem more favoured because they can cover more LBA accesses, but not practical as it is hard to cover all LBAs. For example, in Microsoft Research Cambridge traces [2], the top-1000 most frequently occurring **LBAs** cover only 2.8% of all the LBA accesses, whereas the top-1000 most frequently occurring **LBA deltas** cover 91.7% of all LBA accesses [5]. To learn more complex access patterns, many deep learning approaches are proposed and consider the LBA delta as input directly [19]. Deep-Prefetcher [20] transforms the LBA sequence into LBA deltas, then employs the word2vec model and LSTM architecture to capture the hidden feature in the input sequence. However, it is inefficient on large-scale trace datasets. Delta-LSTM is

Fig. 1: The workflow of the SGDP framework. In Step 1, we compress the search space and reduce the learning complexity. In Step 2, we compute the hybrid connection matrix \(\mathbf{M}_{h}\) with sequential and global information and embed the LBA delta stream into a matrix \(\mathbf{S}_{\Delta}\). In Step 3, using gated graph neural networks to update the latent node vectors. Each stream is represented as the combination of the local preference \(\mathbf{v}_{l}\) and global interaction \(\mathbf{v}_{g}\) by an attention network. In Step 4, we predict the candidate with the highest score and decode it to get the next accessed LBA for prefetching. This framework corresponds to the four steps of **Algorithm 1**.
proposed [5] and addresses the large and sparse LBA space by co-learning top-\(K\) LBA delta and I/O size features. Within top-\(K\) (e.g., \(K=1000\)) classes, the searching space is restricted, which alleviates the class explosion problem. However, both of them do not consider the relations of LBA deltas to capture the more complex patterns (e.g., the continuous LBA accesses across many pages), which results in limited performance.

**Prefetching with Graph-based Structure** Complex patterns in LBA access streams can be constructed by graphs [43, 53]. Nexus uses metadata relationship graphs to assist prefetching decision-making [56]. Ainsworth et al. design a prefetcher for breadth-first searches on graphs [55]. These methods transform a sequence of observed LBAs into a directed graph, in which a node is utilized to represent a block access event to model block access patterns. However, LBA accesses are quite sparse, which results in large graphs in these LBA sequence-based methods and makes these prefetchers quite ineffective in practice.

## III Preliminaries

Consider an LBA access sequence with length \(n\):

\[\langle lba_{i}\rangle_{i=1}^{n}=\langle lba_{1},lba_{2},\ldots,lba_{n}\rangle, \tag{1}\]

in which \(lba_{i}\in N\) represents the address number of the \(i\)-th accessed blocks. The data prefetching problem can be regarded as given \(\langle lba_{i}\rangle_{i=1}^{n}\), predict \(lba_{n+1}\). Following the previous learning-based prefetchers, we compute LBA deltas (\(ld\)):

\[ld_{i}=lba_{i+1}-lba_{i}, \tag{2}\]

\[\langle ld_{i}\rangle_{i=1}^{n-1}=\langle ld_{1},ld_{2},\ldots,ld_{n-1}\rangle. \tag{3}\]

In order to get the prediction of the next LBA, \(\widehat{lba}_{n+1}\), we predict the delta \(\widehat{ld}_{n}\). Note that the variables with the \(\widehat{\ }\) symbol denotes the predicted values. In short, the data prefetching problem is formulated as follows:

\[\widehat{lba}_{n+1}=lba_{n}+\widehat{ld}_{n}. \tag{4}\]

To restrict the model size, the number of classes of LBA deltas that needs to be predicted is capped to a fixed number of \(K+1\). Here \(K\) is acquired by top-\(K\) most frequently occurring LBA delta in \(\langle ld_{i}\rangle_{i=1}^{l-1}\), and the extra class is for the other infrequent LBA deltas. The prefetcher treats this extra class as no-prefetch because infrequent LBA delta is hard to predict. We redefine these \(K+1\) classes as \(LD=\{ld_{c_{0}},ld_{c_{1}},\ldots,ld_{c_{K+1}}\}\), \(ld_{c_{0}}\) representing the no-prefetch class and \(\{ld_{c_{1}},\ldots,ld_{c_{K+1}}\}\) representing the top-\(K\) ones. The model predicts the \(ld_{c_{i}}\) of the next LBA delta, and prefetches it when the predicted class is in the top-\(K\) and does not prefetch if the class is \(ld_{c_{0}}\). Using the LBA delta and Top-\(K\) mechanism can effectively reduce the sparse problem and the search space of the model.

## IV Methodology

### _LBA Delta Streams_

It would yield expensive costs if building the directed graph of the LBA delta sequence generated by the whole LBA sequence (length \(\geq 1\times 10^{7}\)). To alleviate this problem, we use the concept of data access **stream**. We split the whole LBA delta sequence into shorter streams which represent the temporal access patterns. Specifically, we consider LBA accesses with close access times to be in the same stream. Whenever the time interval between two LBA accesses is longer than a preset time limit \(T\) (e.g. \(T=\) 0.1ms), the LBA sequence will be split to generate a new stream. We then split the LBA delta sequence correspondingly and use a sliding window inside each stream to generate equal-length LBA delta streams. A split LBA delta stream \(\mathbf{s}_{\Delta}\) can be represented by a vector \(\mathbf{s}_{\Delta}=[ld_{s,1},ld_{s,2},...,ld_{s,n}]\) in the chronological order, where \(ld_{s,i}\) denotes the \(i\)-th LBA delta in the stream \(\mathbf{s}_{\Delta}\). The LBA delta stream is not only suitable for building directed graphs but also implies the temporal locality of LBA accesses.

### _LBA Delta Based Graph Structure_

As discussed in **Section** II, LBA-based graph structure is ineffective for data prefetching in practice. To solve this problem, we propose a high-order graph based on the LBA delta. Here we present a toy example in **Figure** 2 to show that LBA deltas can also be represented by a directed graph. Consider three users sending concurrent sequential read requests. The concurrent requests are combined into one LBA sequence before being sent to the storage system. Following the LBA delta computation progress in **Section** IV-A, we can simplify the original LBA sequence that has 12 different LBAs and represent it with an LBA delta sequence with only 5 different nodes. We can build a directed graph based on the LBA delta sequence by using LBA deltas as a node and linking all the LBA deltas with their successor.

In contrast to previous works on extracting useful features from access patterns between nearby accessed LBAs only, we observed if an LBA request sequence is divided into several

Fig. 2: Example of LBA delta and graph.
streams, different streams are possible to be accessed by a similar pattern. Non-sequential features can be extracted from the observed access patterns by monitoring the change (or difference) between successive LBA requests. This is achieved by learning the hybrid connection matrix (which contains adjacent and interactive relations) along with the embedded LBA deltas. Also, the number of the graph nodes is constant, that is \(K+1\).

### _Weighted Directed Stream-based Graph_

Without loss of generality, each LBA delta stream \(\mathbf{s}_{\Delta}\) can be modeled as a directed graph \(\mathcal{G}_{\mathbf{s}_{\Delta}}=(\mathcal{V}_{\mathbf{s}_{\Delta}},\mathcal{ E}_{\mathbf{s}_{\Delta}})\). Each node in the directed graph \(\mathcal{G}_{\mathbf{s}_{\Delta}}\) expresses one of the classes of LBA deltas \(ld_{s,a}\in LD\). We build the graph with two kinds of edges, as shown in **Figure**3. The first one \((ld_{s,a},ld_{s,a+1})\in\mathcal{E}_{\mathbf{s}_{\Delta}}\) represents the order in an LBA delta stream \(\mathbf{s}_{\Delta}\) by linking \(ld_{s,a}\) to its successor \(ld_{s,a+1}\). The second one \((ld_{s,a},ld_{s,b})\in\mathcal{E}_{\mathbf{s}_{\Delta}}\) is built by fundy connecting all nodes in the stream to capture the global information of each LBA delta stream. We denote the set of sequential edges as \(\mathcal{E}_{\mathbf{s}_{\Delta}}^{S}\) and full-connected edges as \(\mathcal{E}_{\mathbf{s}_{\Delta}}^{F}\). We compute the adjacency matrices \(\mathbf{M}_{S}\) and \(\mathbf{M}_{F}\) of \(\mathcal{E}_{\mathbf{s}_{\Delta}}^{S}\) and \(\mathcal{E}_{\mathbf{s}_{\Delta}}^{F}\) separately. As every LBA delta node might appear more than once in a stream, we normalize the weights on each edge in \(\mathcal{E}_{\mathbf{s}_{\Delta}}\). The weight of an edge is set to be its occurrence counts divided by the out-degree of its start node. The higher the weight, the stronger the correlation between the corresponding two nodes. The incoming parts of \(\mathbf{M}_{S}\) and \(\mathbf{M}_{F}\) are computed as Eq. (5) and (6),

\[\mathbf{M}_{S}^{in}=\sum_{i=1}^{K+1}\frac{\mathbf{1}((ld_{s,a},ld_{s,a+1}) \mathcal{E}_{\mathbf{s}_{\Delta}}^{S})}{\mathbf{1}((ld_{s,i},ld_{s,a+1}) \mathcal{E}_{\mathbf{s}_{\Delta}}^{S})},\ (a\leq n-1), \tag{5}\]

\[\mathbf{M}_{F}^{in}=\sum_{i=1}^{K+1}\frac{\mathbf{1}((ld_{s,a},ld_{s,b}) \mathcal{E}_{\mathbf{s}_{\Delta}}^{F})}{\mathbf{1}((ld_{s,i},ld_{s,b}) \mathcal{E}_{\mathbf{s}_{\Delta}}^{F})\times|b-a|},\ (a,b\leq n), \tag{6}\]

where \(\mathbf{1}(\cdot)\) is indicator function and the outgoing parts \(\mathbf{M}_{F}^{out}\) and \(\mathbf{M}_{F}^{out}\) is computed in the same manner. Then, we expand \(\mathbf{M}_{S}\) and \(\mathbf{M}_{F}\) to the same dimension, \(\mathbf{M}_{S},\mathbf{M}_{F}\in\mathbb{R}^{(K+1)\times 2*(K+1)}\). To facilitate the fuse of information in \(\mathbf{M}_{S}\) and \(\mathbf{M}_{F}\), we conduct a weighted sum of them named as hybrid connection matrix \(\mathbf{M}_{h}\).

Then, the preprocessed LBA delta stream is embedded with the hybrid connection matrix \(\mathbf{M}_{h}\) and fed into a graph neural network. Specifically, we obtain each node vector \(\overrightarrow{ld}_{s,i}\in\mathbb{R}^{d}\) that indicates the \(d\)-dimensional latent vector of the original \(ld_{s,i}\in LD\). Each LBA delta stream \(\mathbf{s}_{\Delta}\) can be presented as an embedding matrix \(\mathbf{S}_{\Delta}\) by DeepWalk [58] where each node vector \(\overrightarrow{ld}_{s,i}\in\mathbb{R}^{d}\) denotes a \(d\)-dimensional real-valued latent vector. Note that SGDP can support LBA streams of various lengths and various graph model constructing strategies.

### _Latent Node Vectors Updating_

We apply the vanilla graph neural network (GNN) proposed by [49] and gated-recurrent-units-based GNN (gated GNN) [50] to obtain latent features of nodes. Specifically, for each LBA delta stream vector \(\mathbf{S}_{\Delta}=[\overrightarrow{ld}_{1}^{t-1},\overrightarrow{ld}_{2}^ {t-1},...,\overrightarrow{ld}_{n}^{t-1}]\) in the graph \(\mathcal{G}_{\mathbf{s}_{\Delta}}\), the update functions can be formalized as,

\[\mathbf{a}^{t}=\mathbf{A}_{\mathbf{M}_{h}}^{t-1}(\mathbf{S}_{\Delta}{\mathbf{ W_{a}}}^{t}+{\mathbf{b_{a}}}^{t}), \tag{7}\]

\[\mathbf{z}^{t}=\sigma({\mathbf{W_{z}}}^{t}\mathbf{a}^{t}+{\mathbf{U_{z}}}^{t }\overrightarrow{ld}_{n}^{t-1}), \tag{8}\]

\[\mathbf{r}^{t}=\sigma({\mathbf{W_{r}}}^{t}\mathbf{a}^{t}+{\mathbf{U_{r}}}^{t }\overrightarrow{ld}_{n}^{t-1}), \tag{9}\]

\[\tilde{\mathbf{h}}^{t}=tanh({\mathbf{W_{h}}}^{t}\mathbf{a}^{t}+{\mathbf{U_{h}}} ^{t}(\mathbf{r}^{t}\odot\overrightarrow{ld}_{n}^{t-1}), \tag{10}\]

\[\mathbf{h}^{t}=(1-\mathbf{z}^{t})\odot\overrightarrow{ld}_{n}^{t-1}+\mathbf{z} ^{t}\odot\tilde{\mathbf{h}}^{t}, \tag{11}\]

where \(\mathbf{A}_{\mathbf{M}_{h}}^{t-1}\in\mathbb{R}^{1\times 2n}\) is two rows of blocks (outgoing and incoming) in \(\mathbf{M}_{h}\) corresponding to node \(ld_{n}^{t-1}\). \(\mathbf{a}^{t}\) extracts the contextual features of neighborhoods for node \(ld_{n}^{t-1}\) with weight matrix \({\mathbf{W_{a}}}^{t}\in\mathbb{R}^{d\times 2d}\) and bias vector \({\mathbf{b_{a}}}^{t}\in\mathbb{R}^{2d}\). Then, we take \(\mathbf{a}^{t}\) and previous LBA delta vector \(\overrightarrow{lb}_{n}^{t-1}\) as input and feed them into the gated GNN. The updated functions are shown in Eq. (8)\(\sim\)(11). \(\mathbf{z}^{t}\) and \(\mathbf{r}^{t}\) are the updates and the reset gate, and control which features to be reserved or discarded. \(\sigma(\cdot)\) represents the logistic sigmoid function and \(\odot\) denotes the element-wise multiplication operator. \({\mathbf{W_{z}}}^{t}\), \({\mathbf{W_{r}}}^{t}\), \({\mathbf{W_{h}}}^{t}\) and \({\mathbf{U_{z}}}^{t}\), \({\mathbf{U_{r}}}^{t}\), \({\mathbf{U_{h}}}^{t}\) are the weight matrices to be learned. The final state \(\mathbf{h}^{t}\) is the latent node vector, which is the sum of the candidate states and the previous hidden states. Note that the model will update all nodes until they converge.

### _Generating Stream Hybrid Embedding Vector_

The next accessed LBA is strongly correlated with the previous ones, and that relationship is inversely proportional to the interval between the two LBAs. Therefore, we apply a hybrid embedding vector to extract features, i.e., local embedding and global embedding. Firstly, the local embedding vector named \(\mathbf{v}_{l}^{t}\) is defined as the last accessed LBA delta \(\overrightarrow{ld}_{n}^{t-1}\),

\[\mathbf{v}_{l}^{t}=\overrightarrow{ld}_{n}^{t-1}. \tag{12}\]

Fig. 3: Example of two kinds of graphs.
The global embedding vector \(\mathbf{v}_{g}^{t}\) aggregates all node vectors in the LBA delta stream \(\mathbf{S}_{\Delta}\). Specially, we use the soft-attention approach to more effectively represent the different levels of priority, as Eq. (13) and (14) show,

\[\alpha_{i}^{t}=\mathbf{q}^{t}{}^{\top}\sigma(\mathbf{W_{1}}{}^{t}\widehat{ld}_{ n}^{t-1}+\mathbf{W_{2}}{}^{t}\widehat{ld}_{i}^{t-1}+\mathbf{b}_{g}^{t}), \tag{13}\]

\[\mathbf{v}_{g}^{t}=\sum_{i=1}^{n}\alpha_{i}^{t}\overline{\widehat{ld}_{i}^{t-1}}, \tag{14}\]

where \(\mathbf{W_{1}}{}^{t},\mathbf{W_{2}}{}^{t}\in\mathbb{R}^{d\times d}\) and \(\mathbf{q}^{t}\in\mathbb{R}^{d}\) are weight matrices, and \(\mathbf{b}_{g}^{t}\in\mathbb{R}^{d}\) is bias vector.

Finally, the hybrid embedding vector \(\mathbf{v}_{h}^{t}\) combines the local embedding vector \(\mathbf{v}_{l}^{t}\) and the global embedding vector \(\mathbf{v}_{g}^{t}\) linearly, as the Eq. (15) shows,

\[\mathbf{v}_{h}^{t}=\mathbf{W}_{\mathbf{f}}{}^{t}[\mathbf{v}_{l}^{t};\mathbf{v }_{g}^{t}]+\mathbf{b_{h}}{}^{t}, \tag{15}\]

where \(\mathbf{W_{f}}{}^{t}\in\mathbb{R}^{d\times 2d}\) is weight matrix and \(\mathbf{b_{h}}{}^{t}\in\mathbb{R}^{d}\) is bias vector. The final hybrid embedding vector \(\mathbf{v}_{h}^{t}\) of the LBA delta stream \(\mathbf{S}_{\Delta}\) is in the \(d\) dimensions.

### _Forecasting and Prefetching_

After extracting the hybrid embedding vector \(\mathbf{v}_{h}^{t}\), we predict the score of each LBA delta candidate \(\widehat{\mathbf{z}}_{i}^{t}\) in stream \(\mathbf{s}_{\Delta}\) by multiplying \(\mathbf{v}_{h}^{t}\) and \(\widehat{ld}_{i}^{t-1}\) as

\[\widehat{\mathbf{z}}_{i}^{t}=\mathbf{v}_{h}^{t}{}^{\top}\widehat{ld}_{i}^{t-1}. \tag{16}\]

We take the candidate with the highest score as the predicted LBA delta. Besides, in order to train with labels, we need to compute the probability of each node \(\widehat{\mathbf{y}}^{t}\in\mathbb{R}^{K+1}\) in the next step using the softmax function, which is

\[\widehat{\mathbf{y}}^{t}=\mathit{Softmax}(\widehat{\mathbf{z}}^{t}). \tag{17}\]

The loss function is the cross-entropy of prediction \(\widehat{\mathbf{y}}^{t}\) and ground truth \(\mathbf{y}^{t}\) with regularization, as shown in Eq. (18).

\[\mathcal{L}(\widehat{\mathbf{y}}^{t})=-\sum_{i=1}^{m}[\mathbf{y}_{i}^{t}log( \widehat{\mathbf{y}}_{i}^{t})+(1-\mathbf{y}_{i}^{t})log(1-\widehat{\mathbf{y }}_{i}^{t})]+\lambda\|\theta\|_{2}^{2}, \tag{18}\]

where \(\lambda\) is \(l2\)-norm penalty factor, \(\theta\) is weight vectors.

Finally, we decode the index of \(\max\widehat{\mathbf{z}}_{i}^{t}\) to \(\widehat{ld}_{s,n+1}\), predict the next accessed LBA by Eq. (4), and prefetch the corresponding block from storage into the cache. Overall, we summarize the proposed SGDP framework in **Algorithm 1**.

## V Experimental Settings

### _Datasets_

We use representative eight datasets in production servers from different applications, including six datasets from an open-source benchmark **MSRC** and two datasets from a real enterprise storage system **HW**:

**MSRC**\({}^{*}\) (Microsoft Research Cambridge) [2]: It collects a 1-week LBA sequence of live enterprise servers at Microsoft. We use its five datasets from different application scenes named {**hm_1, mds_0, proj_0, prxy_0, src1_2**}.

**Input:** An LBA sequence \(\langle lba_{i}\rangle_{i=1}^{l}=\langle lba_{1},lba_{2},\ldots,lba_{l}\rangle\), the top number of most frequent LBA delta \(K\), dimension of embedding vector of each LBA delta stream \(d\), cache size \(N\), maximum iteration \(Q\), stop criteria \(tol\).

```
1:Step 1: LBA stream preprocessing
2:Compute delta of each adjacent LBA pair in \(\langle lba_{i}\rangle_{i=1}^{l}\) and get LBA delta \(\langle ld_{i}\rangle_{i=1}^{l-1}=\langle ld_{1},ld_{2},\ldots,ld_{n-1}\rangle\).
3:Encode \(ld\)s in all LBA streams by \(top(K)\) to \(LD\).
4:Generate LBA delta stream \(\mathbf{s}_{\Delta}\) by time limit and slide window.
5:Step 2: Embed LBA delta stream to a graph
6:Compute \(\mathbf{M}_{S}\) by Eq. (5) and \(\mathbf{M}_{F}\) by Eq. (6).
7:Expand \(\mathbf{M}_{S}\) and \(\mathbf{M}_{F}\) and conduct weighted sum to get \(\mathbf{M}_{h}\).
8:Conduct embedding of each \(\mathbf{s}_{\Delta}\in\mathbb{R}^{n}\) into \(\mathbf{S}_{\Delta}\in\mathbb{R}^{d\times n}\).
9:Step 3: Update hybrid embedding vector and training
10:Initialize the parameters in the gated GNN model.
11:for\(q=1,...,Q\)do
12:Compute the Eq.(7) \(\sim\) Eq.(18) to fit each stream with the input \(\mathbf{M}_{h}\) and \(\mathbf{S}_{\Delta}\).
13:Update the weight matrices list {\(\mathbf{W_{z}}\), \(\mathbf{W_{r}}\), \(\mathbf{W_{h}}\), \(\mathbf{U_{z}}\), \(\mathbf{U_{r}}\), \(\mathbf{U_{h}}\), \(\mathbf{W_{1}}\), \(\mathbf{W_{2}}\), \(\mathbf{W_{f}}\)} and vectors list {\(\mathbf{b_{g}}\), \(\mathbf{b_{h}}\)} by Adam with ground truth \(\mathbf{y}\).
14:Convergence checking: if \(\mathcal{L}(\widehat{\mathbf{y}})<tol\), break; otherwise, continue.
15:endfor
16:Step 4: Conduct forecasting and data prefetching
17:Conduct Eq.(16) and get \(\max\widehat{\mathbf{z}}\) with the updated model.
18:Decode it to \(\widehat{ld}_{n}\) and conduct Eq.(4) to get \(\widehat{lba}_{n+1}\).
19:Read the corresponding block and prefetch it into the cache or conduct no prefetching.
20:\(\widehat{lba}_{n+1}\), blocks \(\in\mathbb{R}^{N}\) in cache.
```

**Algorithm 1** The Workflow of **SGDP** Framework

**HW**: It consists of three datasets collected from a real-world commercial hybrid storage system, which describes storage traffic characteristics on enterprise virtual desktop infrastructure and production servers. It intercepts the stream from an intra-enterprise storage system under different application scenarios and reads the storage system record logs directly. We named these three datasets as {**hw_1, hw_2, hw_3**}.

**Table I provides the detail of the eight datasets from two data sources. Memory means the total amount of storage space that has been accessed in the trace. Sequential shows the percentage of sequential accesses in the trace.**

### _Compared Methods_

We compare SGDP with the following methods from three categories: traditional prefetchers, regression-based prefetchers, and learning-based prefetchers.

**No_pre** means without any prefetching facilities and is used as a baseline to show the gain by other schemes.
**Naive Prefetcher** treats the LBA stream as a whole sequence, i.e., \(\widehat{ld}_{n}=ld_{n-1}\), and directly uses Eq. (4) to predict LBA.

**Stride Prefetcher**[6] simultaneously records 128 LBA access streams, and each of them tracks the last 3 LBA accesses. Each access is mapped to a stream based on hashing the most significant LBA. If the difference between the 3 LBA accesses matches, it will detect a stride and conduct a prediction.

**ARIMA**[9] treats the problem as a time-series prediction problem and applies the ARIMA model built from \(t-\delta\) to \(t\) to forecast the next LBA.

**Informer\({}^{\dagger}\)**[11] is the SOTA for time-series forecasting. Same as ARIMA, it takes the previous LBA delta sequence as input and predicts the following LBA.

**DeepPrefetcher**[20] captures the LBA delta patterns by employing the word2vec model and LSTM architecture for prefetching.

**Delta-LSTM\({}^{\ddagger}\)**[5] is another learning-based prefetcher, which uses an LSTM-based model to predict the LBA delta for prefetching.

Besides, we set the sequences of LBA delta as the input for a fair comparison. There is a class explosion problem in DeepPrefetcher, which makes it unrealistic to train. To solve the problem, we restrict the top-\(K\) class with \(K=10000\). This \(K=10000\) value is to balance the efficiency and accuracy based on our preliminary study. For Delta-LSTM and SGDP, we set top-\(1000\) frequently occurring LBA deltas as input.

### _Evaluation Criteria_

**HR@N** (Hit Ratio) is the number of cache hits divided by the total number of memory requests over a given time interval. It is an important storage indicator given a fixed cache size \(N\). That is,

\[\mathrm{HR}=\frac{\mathrm{Cache\ Hits}}{\mathrm{Cache\ Hits}+\mathrm{Cache\ Misses}}\times 100\%. \tag{19}\]

**EPR@N** (Effective Prefetching Ratio) is the ratio of the number of correctly prefetched data to all executed prefetches given a fixed cache size \(N\), which is strongly related to the prefetcher's efficiency. That is,

\[\mathrm{EPR}=\frac{\mathrm{Correct\ Prefetchings}}{\mathrm{All\ Prefetchings}} \times 100\%. \tag{20}\]

Note that HR and EPR describe the prefetching results more precisely and feasible refer to Accuracy and Recall in DeepPrefetcher [20] and Delta-LSTM [5], respectively. We use HR and EPR in our work because they describe the prefetching results more precisely. Besides, there is a trade-off between HR and EPR in the subsection VI-B1 and some results are shown in **Figure**4.

Besides, we feed the next step predicted LBA into the cache simulator based on the Least Recently Used (LRU) strategy for prefetching. LRU is a classical cache elimination algorithm. It selects the most recently unused LBA to retire.

### _Implementation Details_

We implemented SGDP for offline training and online testing by PyTorch [57]. All experiments are trained and tested on a computing server equipped with an Intel Xeon Platinum 8180M CPU@2.50GHz and an NVIDIA Tesla V100 GPU.

For a more fair and effective comparison, we normalize all LBA in increments of 8KB blocks and according to the I/O size of the 8KB block alignment and increment operations. We apply the 10-fold cross-validation method for training and testing, the same as SOTA methods. As for neural networks, all parameters are initialized with a Gaussian distribution with a means of 0 and a standard deviation of 0.1 with the latent vectors \(d\) equaling 200 for all 8 datasets. Moreover, we set the initial learning rate to 1.5\(\times 10^{-3}\) with decay by 95% after every 3 epochs, the batch size to 128 with 10 epochs, and the \(\mathit{l}\mathit{\varnothing}\)-norm penalty factor to 10\({}^{-5}\). Adam optimizer [12] with default parameter is applied for optimization. We set the stream split time interval \(T\) as 0.1ms for HW and 0.01ms for MSRC, and set the top number of most frequent LBA delta \(K\) as 1000 for SGDP. Note that since the preprocessed LBA stream is shorter, the training epoch can be smaller to prevent over-fitting, which is also useful to shorten the training time.

## VI Experimental Results

### _Results of Single-Step Prefetching_

We analyze the results of data prefetching conducted by SGDP and the compared methods on different datasets in the case of single-step Prefetching, as reported in **Table** II. The detailed analysis is presented in the following.

**ARIMA and Informer** Time-series forecasting models (ARIMA and Informer) perform the worst, excepting the case of hw_2 trace where ARIMA achieves around 80% HR as this dataset has a very high degree of sequential access (95.1%). ARIMA and Informer take LBA delta inputs as scalar variables and can produce a correct prediction if the input sequences are steady. As there are frequent large fluctuations in complex non-sequential access patterns, ARIMA and Informer prompt incorrect LBA access. The worst results shown in almost all cases confirm our claims that regression-based approaches are not feasible for accurate and complex data prefetching.

**Naive and Stride Prefetcher** Traditional prefetchers (Naive and Stride) have relatively stable performances in sequential access. However, for the random accesses, those traditional prefetchers encounter a big gap compared to SGDP. Moreover,
Stride always achieves higher EPR while lower HR as it is more laziness and only prefetches when detecting an inside-page stride. As a result, it prefetches less and has higher accuracy for sequential access. In other words, although Stride has a high EPR, it prefetches less and gets quite low HR, which makes it impractical. Overall, the robustness performance of the Naive and Stride Prefetcher is poor, especially for completely random access.

**Delta-LSTM, DeepPrefetcher and SGDP** Learning-based prefetchers (Delta-LSTM, DeepPrefetcher and SGDP) cover all highest HR and almost the highest EPR. SGDP has higher HR than DeepPrefetcher/Delta-LSTM in 19/24 out of all 24 cases, and 24/19 about EPR. Specifically, Delta-LSTM and DeepPrefetcher share a similar structure and show a similar effect. DeepPrefetcher has a larger LBA delta candidates pool which leads to more prefetching and lowers accuracy, reflected in lower average EPR (71.6% compared to 80.3%). On the contrary, Delta-LSTM prefetches more accurately but with fewer blocks, which leads to lower HR (70.8% compared to 73.5%). To be fair, as SGDP takes the top-1000 LBA delta as input (same as Delta-LSTM), the comparison to Delta-LSTM can prove that SGDP has better feature extraction ability.

### _Ablation study and SGDP Variants by Stream Construction_

#### Iv-B1 Retaining top-\(K\) delta value (Sgdp\({}_{l}\))

SGDP considers the top-1000 most frequently occurring LBA delta in the whole search space. Considering more LBA delta values further increases the model coverage, but also increases the search space and degrades the accuracy of the model. So to explore it quantitatively and prove the HR-EPR trade-off, we apply the top-10000 LBA delta for model building and name it SGDP\({}_{large}\), or SGDP\({}_{l}\) for brevity.

The experiment of SGDP\({}_{l}\) confirms the trade-off of HR-EPR. As Table II shows, SGDP\({}_{l}\) achieves 1.5% slightly higher than SGDP in terms of HR while showing a large gap with 9.6% loss than SGDP in terms of EPR. Compared to DeepPrefetcher, which also uses top-10000 LBA delta as input, SGDP\({}_{l}\) maintains higher HR in 23 cases and higher EPR in 20 cases. Notice that for dataset hm_1, SGDP\({}_{l}\) gets a low EPR@1000 (24.4%). The reason is that with an extremely high HR@1000 (99.4%, almost all hit), SGDP\({}_{l}\) prefetches extra useless blocks without harm to HR, leading to an obvious decline of EPR.

To further verify the effectiveness of SGDP and the HR-EPR trade-off, we conduct extra tests on dataset prxy_0 by testing Delta-LSTM, DeepPrefetcher, SGDP and SGDP\({}_{l}\) on 20 different cache sizes ({5, 10, 20, \(\cdots\),90 and 100, 200, \(\cdots\), 900, 1000}). As shown in **Figure**4, the top-10000 methods
(SGDP\({}_{l}\) and DeepPrefetcher) show higher HR but lower EPR than their top-1000 counterparts (SGDP and Delta-LSTM). The two pairs of top-\(K\) comparisons confirm that SGDPs achieve better performance consistently than other methods.

#### Vi-B2 Stream partition with page (Sgdp\({}_{p}\))

Considering the spatially localized relevance of LBA access patterns, we divide the entire search space by 64MB size page, record the LBA access streams on each page simultaneously, and perform parallel prediction in each page stream for prefetching the next block inside the page stream. We call it SGDP\({}_{p}\). SGDP\({}_{p}\) models LBA deltas, as 64MB page contains 8192 unique blocks, the total LBA delta candidate class of SGDP\({}_{p}\) is 16383 (\(\pm 8191\)) instead of top-\(K\) classes.

SGDP\({}_{p}\) keeps the best HR results on half of all cases. Its average HR is slightly lower than SGDP and SGDP\({}_{l}\), but still higher than other methods. HR of SGDP\({}_{p}\) on hw\({}_{3}\) encounters a severe drop. The reason is that hw\({}_{3}\) is the shortest and has the second-largest storage capacity, which means the LBAs are much more sparse. SGDP\({}_{p}\) needs at least an LBA stream with length 2 to generate an LBA delta stream. But as hw\({}_{3}\) cross over \(1.4\times 10^{4}\) pages, the average length of inside-page-stream is 12.4, which means SGDP could not perform prefetching on 1/12 of data points. Nevertheless, SGDP\({}_{p}\) obtains the highest HR (79.9%) on all datasets except hw\({}_{3}\) on average. Therefore, it could be concluded that SGDP\({}_{p}\) performs well in real-world scenarios with sufficient data.

### _Multi-step Prefetching_

We further evaluate the performance of SGDP methods in multi-step prefetching based on rolling prediction. We feed the prediction of LBA back to the aforementioned learning-based prefetchers and get the rolling prediction for the next LBAs. The experiments are performed on cache size 100 with a rolling step from 2 to 10. The average results of HR@100 and EPR@100 are reported in **Table** III. Overall, SGDP\({}_{l}\) has the best HR@100 on all steps on average, and SGDP achieves the best EPR@100. SGDP\({}_{p}\) shows worse results than SGDP and SGDP\({}_{l}\). SGDP\({}_{p}\) gets the highest HR@100 (from 79.6% to 83.8%) on average in all steps on all the datasets except hw\({}_{3}\) as it is too sparse. The second best method is SGDP\({}_{l}\), of which HR@100s range from 78.9% to 83.0%. These results demonstrate that SGDP methods are able to keep their superiority and robustness in multi-step prefetching.

### _Offline Training and Online Testing Efficiency_

The offline training time in dataset hw\({}_{l}\) for SGDPs is 0.37 hours, and the training time for other learning-based methods is about 1.1 hours. The GPU utilization is 24%, the parameter number is 192,500, and the flop number is 48,570,779. For the online inference test, the GPU utilization is 10%, the model size is 1.47 MB, and the flop number is 1,884,055. Furthermore, to verify the practicality of SGDP compared to the other methods, we collect statistics of inference time as shown in **Table** VI. SGDPs process 469 to 670 LBA deltas per second, while Delta-LSTM and DeepPrefetcher can only process 91.2 and 197.7 on average. SGDP\({}_{l}\) speeds up inference time up to 3.13\(\times\) than DeepPrefetcher. Overall, SGDPs show much higher efficiency and practicality for real deployment applications.

## VII Conclusions

To improve the performance of the data prefetcher in practice, this paper proposed SGDP, a novel stream-graph-based data prefetcher. SGDP takes each LBA delta stream as a weighted directed graph fusing both sequential and global features. By gated GNN and attention mechanism, SGDP extracts and aggregates the sequential and global information for better data prefetching. The experiment results from eight different real-world datasets demonstrate that SGDP outperforms SOTA methods and high speeds up inference time. The generalized SGDP variants can further adapt to extensive application scenarios. This novel data prefetcher has been verified in commercial hybrid storage systems in the experimental phase and will be deployed in the future product series.
