Stripe-schedule Aware Repair in Erasure-coded Clusters with Heterogeneous Star Networks

In practice, storage nodes typically have different network bandwidths for real storage cluster, and existing studies rarely consider heterogeneous bandwidth networks. This is for a few reasons. (i) Due to new node additions or regular upgrades of system components, the storage nodes in the same cluster have different computing and network capabilities, making nodes have different speeds for data access [5, 9, 40]; (ii) for the sake of avoiding the failure of an entire cluster, storage vendors (e.g., Amazon EC2 [1] and Google [11]) often adopt geo-distributed clusters that span multiple geographic regions to organize storage nodes, which makes the difference in link bandwidths even more significant [16, 36]; and (iii) meanwhile, although the bandwidth within a cluster is sufficient and stable, each node usually has multiple tasks running simultaneously in a hot storage system. The computing and network resources are often shared by diverse applications, limiting the available bandwidth (the remaining node bandwidth for the new task), even if the link bandwidth is the same [33, 34]. We analyze three common hot storage workloads (SWIM, TPC-DS, and TPC-H) in Reference [34] and show the node’s available bandwidths by boxplots. In Figure 1, we find that the medians of the available bandwidth of SWIM and TPC-H are lower than 8 MB/s, and 50% of the available bandwidths of SWIM range from 0.42 to 30.09 MB/s. In addition, half of the available bandwidths of TPC-DS and TPC-H have a wide range from 0.02 to 81.16 MB/s. Due to the uniform distribution of blocks [32, 33] and the use of parallel technology [19, 36], the slowest node will become the performance bottleneck and prolong the whole recovery time.

Many data centers use classic erasure coding for high data reliability and storage efficiency. Among many erasure codes, Reed–Solomon (RS) codes [25] are the most popular. RS code encodes k original fixed-size blocks (called data blocks) into m redundant blocks (called parity blocks). For simplicity, we denote the RS code configured by the parameters k and m as RS(\(k,m\)). A collection of \(k+m\) blocks is called a stripe, in which the \(k+m\) blocks are distributed across \(k+m\) storage nodes. Figure 2 illustrates an erasure-coded cluster in star topology networks. It shows three stripes of 12 blocks encoded by RS(2, 2), in which the blocks with the same color belong to the same stripe. Since erasure codes are based on linear coding, the block size is unchanged after the encoding and repairing. We mainly focus on single-block failures for each stripe, because it is the dominating (\(\gt\)98%) case in practice [13]. As shown in Figure 2, to repair the lost block, the center server will read k blocks (called helper) into the memory in parallel (step 1), calculate a repaired block (step 2), and send the repaired block to the node (step 3). When the entire node fails, it repairs multiple stripes contained in failed node and selects a new node that serves as the backup node without running any tasks (called hot-standby node) to replace the failed node [27]. The read time will dominate the recovery time, since the hot-standby node has sufficient network resources to receive the repaired blocks. Thus, this article focuses on reducing the read time (step 1).

We have provided an overview of the problems in Section 1, and the following discussions provide more detailed explanations.

We first notice that the helper blocks selected for per-stripe directly determine the recovery time. For example, in Figure 3, suppose a cluster of five nodes encoded by RS(2, 2), in which three stripes have lost blocks. Time Cost represents the time of reading one block from the node. To repair the lost block, \(k=2\) helper blocks (the dashed box in Figure 3) are selected from each stripe. Figure 3 shows two multi-stripe recovery solutions, where the first solution needs 10 s (the slowest \(N_{3}\)) to accomplish the recovery, while the latter needs only 6 s (the slowest \(N_{4}\)). This example indicates that a reasonable selection of the recovery solution can reduce the overall recovery time, determined by the node with the maximum read time. However, solving the multi-stripe failures recovery problem is non-trivial.

If we consider \(s \gt 1\) stripes, where each stripe has a maximum of \(C(k+m-1, k)\) possible solutions, then the total number of possible multi-stripe solutions will increase to \(C(k+m-1, k)^{s}\). The enumeration approach can involve a significantly large number of trials. EG [41] enumerates the feasible recovery solutions for each stripe and greedily replaces the old solution with another once introducing less read time. Since the greedy algorithm easily falls into the local-optimal, the recovery performance is deficient. SA [10] uses a simulated annealing algorithm to accept the worse solution to overcome the local optimal. However, it has a slow convergence speed and may be stuck in roundabout search regions caused by probabilistic tolerance. How to quickly find an efficient multi-stripe recovery solution will be critical.

In addition to adjusting the recovery solution, the memory overhead during recovery must also be considered. Since the server reads data in parallel, different bandwidths cause the time when blocks in each node are read into memory to be inconsistent. When k helper blocks within the stripe are read into memory, the server can aggregate them into an aggregated block and send it to the new node. It makes the first-arriving block reside in memory until all k blocks arrive, which leads to memory usage. We argue that memory usage is limited, because the server has many tasks competing for limited memory resources. When the available memory space is insufficient, it will likely hinder the recovery.

Figure 4 shows a cluster deployed with RS(2, 2) and the triple-stripe recovery solution. For convenience, we only show helper blocks with dashed boxes. Assume that the size of each block is M, and the reading, calculating, and sending processes are parallel. As shown in Figure 4(a), if the server reads the helper blocks in each node sequentially (e.g., the reading order of \(N_{1}\) is \(\lbrace b_{3}\) \(b_{5} \rbrace\)), then the maximum memory overhead appears in the 4th second. Currently, it occupies a total of 5M in memory. Since \(b_{3}\) (first-arriving block) cannot be aggregated with \(b_{4}\) until the 8th second, \(b_{3}\) resides in memory for a long time. As shown in Figure 4(b), if we change the reading order in \(N_{1}\) and \(N_{3}\) (e.g., the reading order of \(N_{1}\) is \(\lbrace b_{5}\) \(b_{3} \rbrace\)), then the maximum memory overhead is only 3M. Therefore, how to schedule the reading order of the block for each node to reduce the maximum memory overhead is also very important for further speeding up the recovery.

Based on the above problems, we first establish an optimization model for the multi-stripe recovery problem.

Consider an erasure-coded cluster that deploys an RS(k, m) over n nodes denoted by \(\lbrace\)\(N_{1}\), \(N_{2}\), ..., \(N_{n}\)\(\rbrace\). The cluster contains \(s \ge 1\) stripes with lost block, and each stripe \(S_{i}\) (\(1 \le i \le s\)) spans different \(k+m\) nodes. We use \(b_{i,j}\) to indicate that a block of stripe \(S_{i}\) is located in node \(N_{j}\), and let \(solu_{i}\) be the recovery solution of stripe \(S_{i}\). \(TimeCost_{i}\) represents the time of reading one block from node \(N_{i}\), which is obtained by dividing the block size M by the link bandwidth of \(N_{i}\). \(R(N_{i})\) represents the read time of node \(N_{i}\), which is the number of helpers in \(N_{i}\) multiplied by \(TimeCost_{i}\). According to the principle of parallel technology, the maximum read time \(\alpha\) is determined by the slowest node. Thus, the maximum read time \(\alpha\) required to read all blocks of s stripes is as follows:

As described in Section 2.1, the maximum memory overhead \(\beta\) during recovery also affects the performance. Therefore, we can formulate the following optimization problem:

Our optimization goal is to reduce the maximum read time and maximum memory overhead.

As referred in Section 3.1, sequentially and simultaneously reading all the needed helpers into memory will take up more space. To this end, we designed the Algorithm 2 to reduce memory overhead.

Algorithm Details: Let \(w[i]\) denote the read weight of the solution \(solu_{i}\), and \(Rorder_j\) denote the reading order for node \(N_{j}\). We set \(w[i]=0\) and initialize \(Rorder_{j}\) as the initial reading order for node \(N_{j}\) (lines 1–4). The logical order of the helper blocks in each node determines the initial reading order. For example, in Figure 7, the initial reading order of \(N_{1}\) is \(Rorder_{1} = \lbrace b_{2,1}~b_{3,1} \rbrace\). Then, for each solution \(solu_{i}\), we get the maximum time cost mTimeCost of the node where the block in \(solu_{i}\) is located and scan each helper block \(b_{i,j}\) in \(solu_{i}\) to compute the read weight. The read weight of solution \(solu_{i}\) is calculated as \(w[i] = \sum (mTimeCost-TimeCost_{j})^2\) (lines 5–8). The weight reflects the dispersion degree of the read rate of each block in the same stripe. The lower the weight, the more consistent the arrival time of each block, and vice versa. Each block in \(solu_{i}\) is given a weight \(w[i]\). Finally, we reorder the helper blocks in Rorder (lines 9 and 10). The lower the block weight in the same node, the higher the read priority. The weight of block \(b_{i,j}\) equals the weight of solution \(solu_{i}\).

An Example: For the convenience of description, we use the example in Figure 3 (Section 3.1: problem2) to describe Algorithm 2. Figure 7 shows the optimization process of reading order, and we only show the helper block. Algorithm 2 first constructs the initial reading order for Rorder that reads each block sequentially (step ①). Then, it calculates the weight for each stripe (step ②). Finally, we reorder the helper blocks in Rorder (step ③). For example, the weight of \(solu_{3}\) is less than that of \(solu_{2}~(w[3]\lt w[2])\), \(b_{3,1}\) should be read before \(b_{2,1}\) in node \(N_{1}\). For \(N_{3}\), the analysis is the same as above.

Discussion: We further analyze the helper’s status in the center server’s memory and find that there are still blocks that arrived first, remaining in memory and occupying memory space. For example, block \(b_{1,2}\) in Figure 7 is read into memory after the 1st second and encoded together with \(b_{1,2}\) in the 8th second. The time cost of \(N_{2}\) is 1, we can allow \(b_{1,2}\) to read into memory at the 7th second, which can further reduce memory overhead from 3M to 2M. To achieve the above optimization, we first predict the time each block is aggregated and encoded in memory. Assuming blocks \(b_{i,j}\) are encoded and merged at time point t, it can be read from node \(N_{j}\) at time point \(t-TimeCost_{j}\), effectively avoiding some blocks from staying in memory for a long time.

Time Complexity: The complexity of Algorithm 2 is \(O(s + n + s \cdot k + n) \approx O(s \cdot k + n)\).

In modern clusters, each node stores a tremendous number of blocks, which belong to different stripes [36]. Therefore, when a full node fails, it triggers a tremendous number of stripes to repair simultaneously. Repairing these stripes simultaneously is usually not preferable, as it easily blows up the network and memory to the center server. In addition, the dynamic and ever-changing application workloads in nodes may change the heterogeneity of network bandwidths, and we need to quickly generate the efficient recovery solution and complete the recovery process before bandwidths change. The current efficient recovery solution may not be effective after a while under rapidly changing network environments in the dynamic storage cluster. Therefore, SARepair batches process a tremendous number of stripes and selectively arranges appropriate stripes from all pending failed stripes to perform recovery based on the current bandwidth environment.

Algorithm Details: Let \(\mathbb {S}\) denote all failed stripes, and b be the number of repaired stripes in a batch. Algorithm 3 selectively selects b stripes to be repaired from \(\mathbb {S}\) and adjusts them to minimize the current read time for each batch. It first randomly selects b stripes \(BS = \lbrace S_{1}, \ldots , S_{b} \rbrace\) from \(\mathbb {S}\) and excludes them from \(\mathbb {S}\) (lines 2 and 3). Algorithm 3 next replaces the current stripes to be repaired in BS over a configurable number of iterations (denoted by l) to minimize the read time for the current batch (lines 4–15). For each iteration, Algorithm 3 first obtains the repair solution Solu via calling Algorithm 1 (Section 4.1) for the current BS. It then selects a stripe to be repaired in \(\mathbb {S}\) to replace a stripe in BS. To quickly find the two stripes, we define the priority of being selected \(Ps_{i}\) and replaced \(Pr_{i}\) for each stripe \(S_{i}\). Specifically, after obtaining Solu in line 5, we can determine the read time for each node. The priority of being selected \(Ps_{i}\) of \(S_{i}\) in \(\mathbb {S}\) is computed by the sum of k minimum read times in the nodes where the remaining \(k+m-1\) blocks of \(S_{i}\) are located. For example, in Figure 8(a), the \(k=2\) nodes with the least read time among the remaining \(k+m-1=3\) blocks of \(S_{4}\) are \(N_{2}\) and \(N_{3}\) (or \(N_{2}\) and \(N_{5}\)), and hence the \(Ps_{4} = 3+4=7\). The priority of being replaced \(Pr_{i}\) of \(S_{i}\) in BS is computed by the sum of read times in the nodes where the k helper blocks of \(S_{i}\) are located. In Figure 8(a), the nodes where the helper blocks for \(S_{3}\) are located are \(N_{4}\) and \(N_{5}\), and hence the \(Pr_{3} = 8+4=12\). After computing the priorities in lines 6 and 7, Algorithm 3 finds \(S_{x}\) in \(\mathbb {S}\) that has the lowest priority of being selected and \(S_{y}\) in BS that has the highest priority of being replaced (line 8). It then tries all valid solutions \(solu_{x}\) of \(S_{x}\) to replace the current solution \(solu_{y}\) of \(S_{y}\) in Solu and generates the new batch solution nSolu (lines 9 and 10). If the new solution nSolu has a lower read time than Solu, then Algorithm 3 substitutes Solu with nSolu, updates \(\mathbb {S}\) and BS, and jumps to the for-loop in line 4 to start the next iteration (line 11–15). After l iterations, it finally obtains Rorder via calling Algorithm 2 (Section 4.2) for Solu and performs the repairs for the current batch BS (line 16-17).

Extensions to LRC Code: Besides RS code, we argue that SARepair can also be extended to another representative erasure code called LRC code [15], which has been used in Microsoft Azure Storage Systems. An LRC(k, l, g) divides k blocks into l groups, each group encode one local parity block by \(k/l\) blocks, and the g global parity blocks are generated by k blocks like RS code. For global parity failure, we can repair it by carefully selecting the remaining \(k+g-1\) blocks like the RS code. However, when repairing the data or local parity block in each group, we cannot reduce the recovery time via selecting helper blocks, because each group only tolerates single-failure and needs all the remaining \(k/l\) blocks to repair. Therefore, we can re-organize the recovery of multiple data or local parity block via Algorithm 3, such that the resulting recovery time is reduced.

An Example: Figure 8 shows an example of Algorithm 3 for RS(2, 2) and batch size \(b = 3\). In Figure 8(a), the initial BS is \(\lbrace S_{1}, S_{2}, S_{3} \rbrace\), and the maximum read time is 8s after calling Algorithm 1. It computes the priorities, finds \(S_{3}\) in BS that has the highest priority of being replaced (e.g., \(Pr_{3} = 12\)) and \(S_{4}\) in \(\mathbb {S}\) that has the lowest priority of being selected (e.g., \(Ps_{4} = 4\)). Therefore, Algorithm 3 selects \(S_{4}\) to replace \(S_{3}\) and generates a new recovery solution, such that the maximum read time is 6s (Figure 8(b)). The stripe \(S_{3}\) to be repaired will be reorganized in \(\mathbb {S}\) and repaired in the next rounds.

Time Complexity: We finally analyze the time complexity of Algorithm 3 needs \(\lceil \frac{s}{b} \rceil\) rounds to repair s stripes. For each iteration, it calls Algorithm 1 (\(O(b + o \cdot e \cdot n \cdot b)\)) to obtain Solu for b stripes, takes at most \(O(s)\) time to compute priorities and find two stripes, and takes \(O(C(k+m-1, k))\) times to find a new solution. Finally, Algorithm 3 calls Algorithm 2 (\(O(b+n)\)) to obtain Rorder for each batch. The overall time complexity of Algorithm 3 is \(O(\lceil \frac{s}{b} \rceil \cdot [l \cdot (O(Alg. 1) + s + C(k+m-1, k)) + O(Alg. 2) ]) = O(\lceil \frac{s}{b} \rceil \cdot [l \cdot ((b + o \cdot e \cdot n \cdot b) + s + \frac{(k+m-1)!}{k!m!}) + (b \cdot k + n)])\). Note that Algorithms 1 and 2 process b stripes per batch. In real situations, \(s \gt \frac{(k+m-1)!}{k!m!}\), \(b \cdot k\), n, and b. Therefore, the time complexity of SARepair is approximately equal to \(O(\frac{s \cdot l \cdot (o \cdot e \cdot n \cdot b + s)}{b}) = O(s \cdot l \cdot o \cdot e \cdot n + \frac{s^{2} \cdot l}{b})\), and the time complexity of each batch is \(O(l \cdot (o \cdot e \cdot n \cdot b + s))\).

We implement a simulator for SARepair in Python with about 2,300 SLoC. We deploy the simulator on a server. By default, we randomly distribute the blocks of \(s=1,000\) stripes with the lost block across \(n=12\) nodes and use RS(6, 3) (used in QFS [24] and HDFS [12]), unless mentioned otherwise. We set block size as 4 MB, which is a moderate size for real erasure-coded clusters [26]. The simulator does not implement data transmission and coding operations, which are left to be done in Section 5.2. We measure the running time of algorithms and obtain the total recovery time of all failed stripes. All results are averaged over five runs, and the time is measured in seconds.

Experiment 1 (Efficiency of SARepair): Compared with the enumeration method, we first evaluate the efficiency of SARepair. We select RS(6, 3) and vary the number of stripes from 4 to 8. The results are shown in Table 2.

Regarding recovery time, SARepair obtains the optimal recovery solution with the same minimum read time compared to enumeration in \(s = 4, 6\). When \(s = 8\), the recovery time of the optimal recovery solution is less than that of SARepair by at most 4.5% only. About running time, we also observe that the running time of SARepair is negligible, which is less than 0.1 s. On the contrary, the running time of enumeration exponentially enlarges when the number of stripes increases.

Experiment 2 (Impact of parameter \(\boldsymbol {e}\)): We next evaluate SARepair with different parameter e from 1 to 5. We vary different erasure codes (RS(2, 2), RS(4, 2) (Typical RAID-6 [35] setup), and RS(6, 3) (used in QFS and HDFS), different number of nodes (from 9 to 15), and different number of stripes (from 500 to 1,500) for testing and further analyze the total time. Due to the large values of the experimental results, some values are not shown in Figure 9(b) and (c).

In Figure 9(a), when e is small (<3), the running time of SARepair does not change much with e. When e>3, the running time of SARepair increases exponentially. We observed that the running times of different erasure codes are very similar, because the time complexity of Algorithm 1 is independent of the encoding parameters (k and m). The overall recovery time of SARepair decreases with e. When e goes from 1 to 2, the recovery time drops the most. When \(e=1\), SARepair is similar to a greedy algorithm. When \(e \gt 1\), SARepair tolerates worse solutions to jump out of the local-optimal.

In Figure 9(b), the more nodes there are, the longer the running time and the shorter the recovery time. The main reason is that SARepair generates the recovery solution by constructing an \(s \cdot n\) metadata matrix, and the larger the n is, the more traversal times it takes. Each node will store and transmit fewer blocks of failed stripes when the cluster has more nodes. The recovery time of SARepair decreases dramatically with e when \(1 \lt e \lt 3\), while that decreases linearly when \(e \gt 3\).

In Figure 9(c), when e is greater than 3, the running times significantly increase for \(s = 1,000\) and \(s = 1,500\). Moreover, the increase in e does not significantly reduce the recovery time when handling the small-scale stripes. The reason is that the fewer the number of stripes, the smaller the optimization space for SARepair, which also explains why the corresponding runtime for \(s=500\) is significantly smaller than \(s=1,000\) and \(s=1,500\).

In Figure 9(d), we use the default configurations, measure the total time (running time + recovery time), and provide a breakdown of the total time in terms of the running time and the recovery time. We find that the total time decreases first and then increases sharply with e, and the turning point of the total time is \(e=3\). In addition, although the recovery time dominates the total time, the ratio of running time increases with e. For example, the ratio of running time is 45% when \(e=5\). Therefore, a large value e can reduce recovery time at the cost of running time, and vice versa.

Our experiment shows a fundamental tradeoff between recovery efficiency and performance, where parameter e plays a key factor. Therefore, we set \(e=3\) in the experiments to quickly and effectively generate the recovery solution. We suggest that the system designers can reasonably select variable parameters e based on the current system configuration and data status. We can deploy the SARepair with a smaller e in the online or hot storage system and require the failed blocks to be repaired quickly. We can also deploy the SARepair with a larger e in the offline or cold storage system, the center server can spend more time calculating recovery solutions with shorter recovery times, and reduces the occupation of overall cluster resources during the repair process.

Experiment 3 (Impact of batch size \(\boldsymbol {b}\)): The impact under different batch sizes from 50 to 1,000 is further evaluated. We choose the factor of total stripes (e.g., \(s=1,000\)) as the batch size, including b = 50, 100, 200, 250, 500, and 1,000. Note that when b is 1000 (equal to \(s=1,000\)), it is equivalent to repairing all failed stripes concurrently. We again use the default parameters and vary different coding parameters for testing.

As shown in Figure 10(a), the running time of SARepair gradually decreases from 50 to 250 while increasing from 250 to 1000. The difference in runtime under different encoding parameters is not significant. The reason behind this is that the overall time complexity of SARepair is \(O(s \cdot l \cdot o \cdot e \cdot n + \frac{s^{2} \cdot l}{b})\) (see Section 4.3), which is mainly dominated by other parameters (\(s, l, o, e, n, b\)). To further analyze the reasons for the trend of curve changes, we measure the optimization round o for each batch under different batch sizes b and show the results in Figure 10(b). We observe that o increases slowly with b when \(b=50\) to \(b=250\), while the optimization round o increases dramatically with the batch sizes b when \(b=500\) and \(b=1,000\). We indicate that when b is small, the value of o is small, and the determinant of the running time is \(\frac{s^{2} \cdot l}{b}\) (the downward trend of \(\frac{s^{2} \cdot l}{b}\) is greater than the upward trend of \(s \cdot l \cdot o \cdot e \cdot n\)), so the running time decreases; when b is large, the value of o is large, and the determinant of running time is \(s \cdot l \cdot o \cdot e \cdot n\) (the decreasing trend of \(\frac{s^{2} \cdot l}{b}\) is smaller than the increasing trend of \(s \cdot l \cdot o \cdot e \cdot n\)), so the running time increases.

As shown in Figure 10(c), increasing batch size within a specific range can reduce the recovery time. For example, from 50 to 250, the reduction ratio of recovery time is 18.67%, 27.01%, and 27.78% for RS(2, 2), RS(4, 2), and RS(6, 3). We also find that when b is greater than 250, a larger batch size will add the recovery time. Batch processing can effectively balance the transmission load among nodes for each batch, thereby further reducing recovery time. To investigate and elucidate this phenomenon, we calculate the standard deviation of the transmission time among nodes for each batch to measure the load balancing among them. The lower this metric is, the more balanced the load is. Figure 10(d) shows the experimental results, and we found that the standard deviation also shows a trend of first decreasing and then increasing. When b is 50, the standard deviation is highest, and when b is 250, the standard deviation is lowest. The smaller the value of b, the more batches there are, which is more likely to cause an imbalance between nodes for each batch, thus increasing the total recovery time; The larger the value of b, the smaller the optimization space available for stripe replacement within each batch, which may also cause uneven load within the batch and increase recovery time.

Therefore, system designers can measure the optimization round and standard deviation for different batch sizes based on parameter configuration to find turning points and determine the optimal batch size.

Experiment 4 (Impact of coding parameters): We measure the running and recovery time for different coding parameters. We consider three representative configurations for each RS(k, m): RS(2, 2), RS(4, 2) (Typical RAID-6 [35] setup), and RS(6, 3) (used in QFS and HDFS). We make three key observations from the results in Figure 11.

First, as shown in Figure 11(a), SARepair significantly reduces the running time of solution generation. For example, the reduction reaches up to 81.71% and 94.83% compared to EG and SA for parameters (6, 3). This is because SARepair uses the metadata of blocks to generate a recovery solution, which significantly narrows down the solution space to make it practically tractable. Second, as shown in Figure 11(b), SARepair has the lowest recovery time among the three techniques. SARepair reduces the recovery time by 21.74–39.39% and 10.21–18.70% on average compared to EG and SA, respectively. The rationale is that SARepair tolerates the worse solutions and uses a rollback mechanism to reduce recovery time. Finally, the running and recovery time of all three techniques increase when handling larger parameters.

Experiment 5 (Impact of different erasure codes): We finally evaluate SARepair for the non-RS code cluster and validate the efficiency of SARepair using LRC code [15]. For LRC(\(k, l, g\)), we select LRC(4, 2, 2) and LRC(6, 2, 2) in this evaluation, which is also used in previous studies [36, 37]. When the data block or local parity block fails, we repair it within each group, and the helper block is fixed. When the global parity block fails, we repair it by selecting k blocks.

We find that SARepair maintains the effectiveness of reducing running and recovery time for different erasure codes. It reduces 28.33–93.65% running time and 8.45–24.26% recovery time when compared to the EG and SA in Figure 12. Although LRC code needs all remaining blocks to repair the data block or local parity block, SARepair can reduce the recovery time by carefully arranging appropriate stripes to perform repairs for each repair batch. Therefore, SARepair can adapt to different erasure codes and improve the recovery of the LRC code.

We further implement SARepair by extending our simulator (Section 5.1) in C++ with about 2,400 SLoC. We deploy the SARepair on Amazon EC2 [1] with 13 instances of type t4g.xlarge within a data center in the Hong Kong region. Each instance is equipped with 4vCPUs and 16 GB RAM and runs Ubuntu 16.04 LTS. The network bandwidth across nodes is around 5 Gb/s (measured by iperf [20]). Among the 13 instances, one instance acts as the center server, and the remaining 12 instances are organized to act as storage nodes. We use the Linux command tc [21] to limit the link bandwidth for each link, and the bandwidth values are based on three common hot storage workloads in Reference [34]. We also implement RS codes based on Jerasure 1.2 [7] and use TCP sockets to realize network transmission. We adopt RS(6, 3) (used in QFS [24] and HDFS [12]) and set the block size as 4 MB by default. The average recovery throughput (the amount of repaired data per unit time) and memory overhead of each recovery batch are measured, and the average results over five runs.

Experiment 6 (Ratios of running and recovery time): Figure 13 shows the ratio of time taken by solution generation and data recovery.

We first observe that when the coding parameters increase, the ratio of running time in EG increases, and the running time ratio in SARepair decreases. The rationale is that each optimization of EG requires traversing \(s \cdot C(k+m-1, k)\) solutions, and the time complexity of SARepair is independent of the coding parameters. Although SA can reduce the recovery time by tolerating the worse solution, it needs more time to generate the recovery time. The running time of SA accounts for an average of 39.34% of the total time, which implies that reducing the running time is also crucial.

Experiment 7 (Impact of block size): To investigate how the block size affects the benefit of SARepair, we compare SARepair with EG and SA in terms of recovery throughput under different block sizes. By default, we fix the number of stripes to 200 and use RS(6, 3). Figure 14 shows the recovery throughput for the block sizes from 1 to 16 MB.

We find that the recovery throughput gradually increases along with the block size with all techniques. This is because the larger the block size, the greater the ratio of transmission time in the entire recovery. Therefore, it is crucial to generate effective recovery solutions to reduce transmission time. The larger the block size, the more significant the performance improvement of SARepair in heterogeneous network environments. For example, compared to EG, SARepair improves the performance by 59.97% when the block size is 1 MB and 81.52% when the block size is 16 MB. Experiment 8 (Impact of the number of nodes): We study the impact of the different number of nodes from 10 to 14. Figure 15 shows the experimental results. In terms of recovery throughput, it increases with the number of nodes. This is because the number of nodes increases, resulting in a more scattered distribution of blocks, and the number of blocks obtained from each node decreases. Overall, SARepair improves 37.50–62.07% and 14.04–42.83% of the recovery throughput compared to EG and SA, respectively. Therefore, the increase of nodes will not affect SARepair.

Experiment 9 (Impact of changing bandwidth): In practical erasure-coded clusters, the network bandwidths of storage nodes are changing, and the bandwidth values may not be obtained accurately. Therefore, it is necessary to ensure that the efficient recovery solution we find under inaccurate bandwidths is still efficient under the actual bandwidths. To simulate the changing network environments, we define the bandwidth change ratio (BCR) as

In the experiment, we set five different BCR ranges, including [1.0,1.0] (the bandwidth is accurately measured), [0.9,1.1], [0.8,1.2], [0.7,1.3], and [0.6,1.4] to evaluate SARepair. When the center server obtains the current accurate bandwidths, we multiply the current bandwidth value by a random value in the BCR range to limite the bandwidth of each node. We use different coding parameters in Figure 16.

Obviously, the changing network environment with the larger BCR range will incur more influence on the effectiveness of the recovery solution of SARepair. We observe that the changing bandwidth environments only impair the recovery throughput by at most 10.8%. The results prove that SARepair can adapt to the changing bandwidth under the dynamic hot storage clusters. Experiment 10 (Breakdown analysis of SARepair): In Section 4, we design three algorithms to improve the recovery performance. To analyze the effect of different designed algorithms on performance, we evaluate them individually. Specifically, the three algorithms of SARepair can be abbreviated as follows: (i) RRT: only use the Algorithm 1 to reduce the recovery time, sequentially read the helper block for each node, and randomly select stripes for each batch; (ii) RMO: use SA to generate the recovery solution and adopt the Algorithm 2 to reduce the memory overhead; and (iii) BAT: use SA to generate the recovery solution and adopt the Algorithm 3 to selectively arrange appropriate stripes for each batch. Therefore, SARepair is the synthesis of RRT+RMO+BAT. In addition, we set the maximum memory usage of the center server to 1GB. When the available memory is insufficient, the center server will delay the recovery of some stripes to release the memory. We again use the default settings, and Figure 17 shows the results.

We observe that RRT has the highest recovery throughput in all three designed algorithms, and optimizing the recovery solution is more effective than reducing memory overhead and arranging appropriate stripes. Compared with SA, RRT can promote the recovery performance by 25.91%, while RMO is only 8.02% and BAT is only 17.09%. Moreover, SARepair has the highest recovery throughput and improves the recovery performance by 33.61%. Therefore, the results also prove that the three designed algorithms of SARepair are complementary mutually and do not compromise the effectiveness of each other.

Experiment 11 (Recovery in rack clusters): We further conduct experiment on Amazon EC2 in real rack clusters. As shown in Table 1 in Section 4.1.2, we create a set of instances in Asia Pacific five regions, every three instances reside in the same rack. The network bandwidth between each instance is also shown in Table 1. We adopt RS(4, 2) and RS(6, 3), and randomly distribute blocks to five regions while maintaining rack-level fault tolerance. Figure 18 shows that SARepair reduces the recovery time by 39.62% and 25.14% on average compared to EG and SA, respectively. Therefore, SARepair can still maintain its performance gain in rack clusters.

Experiment 12 (Analysis of memory consumption): We finally evaluate the maximum memory overhead with the different coding parameters and the number of stripes. Figure 19 shows a series of experimental results.

As shown in Figure 19(a), the maximum memory usage of all techniques significantly increases with the coding parameters. This is because the center server needs to read more helper blocks to repair a failed block when handling larger coding parameters. Compared to without using Algorithm 2, the three techniques using Algorithm 2 significantly reduce the maximum memory overhead. For example, Algorithm 2 reduces the maximum memory overhead by 24.09–62.45% on EG, 21.42–39.73% on SA, and 19.39–54.78% on SARepair. As shown in Figure 19(b), consistent with the previous analysis, the optimization of Algorithm 2 can significantly reduce the memory overhead during recovery, which is significant for reducing the server’s workload. Moreover, the maximum memory overhead of SARepair is less than 1GB, which is acceptable for general servers.