2.1

Erasure code

Erasure code has lower storage overhead than replication, which are widely used in cloud systems^1-3, there is various kind of erasure codes, RS code⁴ is a traditional code and widely deployed in the storage system, it is because it can tolerate any m blocks are lost, m is the number of parity blocks of a stripe there. After the Google disclosed Google File System⁵, which used triple replication with the diffusion of commodity disks. Since the data generated by multiple services started to grow explosively, the erasure code’s space efficiency was revalued again.

2.2

Failure recovery

In recent years, recovery overhead is important, it has been regarded as a serious problem in storage, especially in large storage systems^{6, 7}. Many methods aim at failure recovery in Erasure code, including local parity techniques to decrease the recovery overhead. WEAVER Codes⁸ suggested a generic method that contains almost all of the possible placements. Followed by Azure’s Local Reconstruction Codes⁶ and Facebook Xorbas⁷, Microsoft Pyramid Codes⁹ studies the durability of local parities.

2.3

Greedy algorithm

The greedy algorithm is widely studied and applied in different fields because of its simple design, easy implementation, and low complexity compared with other methods. Reference¹⁰ uses powerful sampling methods to apply greedy algorithms to the MapReduce paradigm, including maximum cover and submodular maximization subject to p-system constraint problems. Based on the greedy strategy, Reference¹¹ proposed a new method to obtain good space to solve a parameter family partial differential equation. Reference¹² proposed an improved the greedy algorithm, Carousel Greedy, aiming at the defects of the greedy algorithm, and applied it to a variety of combinational optimization problems.

3.1

Problem definition

Here we define the problem to be solved in the form of mathematical symbols. The node-set in the system is N = {N₁, N₂, …, N_n}, the corresponding bandwidth of each node is , where is measured in the size of one data block. We define the set of tasks awaiting recovery as R = {R₁, R₂, …, R_l], l represents the number of tasks, corresponding to the task R_i, the optional node-set to participate in the recovery of the task is , , where p represents the number of nodes and is the same for all tasks, the actual number of nodes required by the task is defined as q(q < p). Then the problem is defined as, on the premise that the bandwidth used for each node N_i(N_i ∈ N) does not exceed , t(t ≤ l) tasks are selected from the set R, and each task selects a fixed number of nodes from the optional set S_i. And our goal is to maximize t, that is, to process as many recovery tasks as possible with limited bandwidth.

3.2

Gre-N

Gre-N method considering the characteristics of the node bandwidth imbalance, priority is assigned to nodes with high bandwidth, we first sort the nodes by bandwidth from high to low, and first assign tasks to the nodes with high bandwidth. For each node, if there are enough tasks involving the node, select the same number of tasks as the node bandwidth; otherwise, select all tasks until there are no qualified tasks to end the allocation process.

As shown in Figure 1, circles represent the nodes used to perform tasks, and they are arranged in descending order of bandwidth. Squares represent tasks, and the gray grid on the right of each square represents the list of nodes needed to perform the task. Gre-N’s policy is to assign tasks to nodes in descending order of bandwidth. As shown in Figure 1, since the nodes involved in task 0 and task 3 have the highest bandwidth, they are preferentially processed, so task 1 and task 4 are subsequently processed.

Figure 1.

The strategy of Gre-N.

3.3

Gre-T

Compared with the random allocation method, Gre-N method takes into account the problem of bandwidth imbalance. However, since the bandwidth of the top nodes is always inevitably occupied, it is difficult to consider the subsequent better schemes and tasks. Therefore, we propose a better strategy based on the greedy algorithm: Gre-T. Gre-T contains three technical points, which we will introduce separately.

3.3.1

Tasks Sorting.

In the process of selecting tasks to be processed, how to select task combinations is very important. Choosing the right task combination may improve the bandwidth utilization of nodes, so we take this into account in Gre-T. Gre-T computes a bandwidth score for each task R_i as the sum of the initial bandwidth of the nodes involved in the task. The calculation formula is as follows:

where S_i represents the node-set that the processing task R_i needs to participate in, w represents the number of elements in the corresponding node-set, all elements in S_i belong to the set N, represents the initial bandwidth of node h_j.

Then, the tasks are sorted in ascending order according to the score, and the next tasks are selected in this order. This is similar to Gre-N’s Greedy strategy, in which the tasks are preferentially allocated to nodes with high bandwidth for processing. However, Gre-T adopts a more flexible policy to balance the bandwidth utilization of each node, rather than exhausting the bandwidth of a node.

3.3.2

Assign Tasks Based on Bandwidth Utilization.

We calculate the used bandwidth of all nodes in the system in real-time, and then divide the used bandwidth by the initial bandwidth to get the bandwidth utilization of the current node. For each selected task R_i, we first select p nodes corresponding to the task according to S_i, and then select q (q<p) nodes with the lowest bandwidth utilization as the final nodes to participate in the task, after the current task is complete, the bandwidth utilization of the q nodes is updated in real-time. As shown in Figure 2, we first calculate the score of tasks according to equation (1), and then sort the tasks in order of high score to a low score, and process the tasks in this order. As shown in Figure 2, for task 0, among the four nodes (N-1, N-2, N-3, N-4) that can participate in the task, the two nodes (N-1, N-2) with low bandwidth utilization are selected to participate in the task. At the end of task 0, we update the bandwidth utilization of N-1 and N-2, and then repeat the above operations for task 1 and task 2. We avoid using a greedy strategy based on the remaining available bandwidth (RAGS) to select nodes. This is because the task sequencing method in Section 3.3.1 is based on the initial bandwidth of the corresponding node, we take the initial bandwidth order to represent the bandwidth order at any time. If RAGS is used, the ranking of the available bandwidth of the node will change greatly after completing part of the task, at this moment need the corresponding adjustment in order to adapt to the current bandwidth scheduling state, because there are a large number of the task, sort of delay cost is very big, the Gre-T according to the node is assigned to a task can guarantee the bandwidth of the node order bandwidth utilization is always consistent with the initial basic bandwidth order. In this way, task reordering is not required.

Figure 2.

The strategy of Gre-T.

3.3.3

Low Bandwidth Node Compensation Policy.

Since tasks are sorted according to the sum of initial bandwidth of nodes involved in tasks, nodes with low initial bandwidth will not be frequently used in the whole process. The Gre-T method uses low bandwidth node compensation policy (LBC) to alleviate the problem of the greedy policy over selecting nodes with high initial bandwidth. In Gre-T, we define a constant f. When the node number is smaller than f, it is a low-bandwidth node; when the node number is larger than f, it is a high-bandwidth node. As shown in Figure 3, we use an on/off logic valve to control whether to trigger the LBC, specifically: LBC is disabled by default. When the bandwidth usage of high-bandwidth nodes is low, LBC is disabled. In this case, the task selection sequence is front to back. When the bandwidth usage of high-bandwidth nodes is too high, LBC is triggered to select tasks from the end of the task sequence. The default LBC trigger conditions are as follows:

Figure 3.

Description of the conversion graph under bandwidth utilization control.

where D_i represents the node, and N is the set of nodes arranged in descending order of bandwidth, represents the remaining bandwidth of node D_i, represents the used bandwidth of node D_i, n represents the total number of nodes. In the beginning, obviously C is greater than 0, LBC is not triggered, and LBC is triggered when c is less than or equal to 0. This indicates that LBC is triggered when the sum of the bandwidth used by all high-bandwidth nodes is greater than or equal to the sum of the unused bandwidth of all low-bandwidth nodes.

4.1

Test method

We use C++ language to simulate the implementation of our proposed two methods, Gre-N and Gre-T, in a Linux environment. We simulate 1000 nodes in the implementation and use a random function to randomly generate bandwidth for these 1000 nodes. During the experiment, our erasure code strip was composed of nine data blocks and three check blocks. Therefore, for each recovery task, we randomly selected 11 different nodes as the optional node-set, and compared our proposed method with the existing original method to test the effect of our proposed method.

The LBC policy is used when the valve is open and suspended when the valve is closed.

4.2

Results

First, for a total of one million tasks, we tested the total bandwidth utilization of the original versus Gre-N and Gre-T. The duration of executing a recovery task reflects the advantages and disadvantages of a recovery policy. If the total number of recovery tasks is constant, the higher the bandwidth usage, the faster the task execution speed and the shorter the task execution time, indicating that the better the recovery policy is. According to Figure 4, when the total number of tasks is 1 million, the total bandwidth utilization of the original method is 74%, Gre-N is 89%, which is 20.2% higher than that of the original method, Gre-T is 96%, which is 29.7% higher. When the total number of tasks is 3 million, the bandwidth utilization of the original method is 77%, 87% for Gre-N, and 94% for Gre-T, Gre-N improves by 13.0% and Gre-T by 22.1% compared with the original method, which proves that our method is effective under the different total number of tasks.

Figure 4.

Performance of the three approaches in the case of tasks of 1 million and 3 million.

We did a further experiment with a total of one million tasks to compare Gre-N and Gre-T. After multiple rounds of task selection, all tasks are executed, and the bandwidth utilization after each round is calculated, as shown in Figure 5. As can be seen from the figure, Gre-T has higher bandwidth utilization than Gre-N in most of the iterations, and Gre-T needs fewer rounds of iteration (about 2200) to complete all tasks than Gren (about 2500).

Figure 5.

The bandwidth utilization ratio curve of Gre-N and Gre-T.