Method and apparatus for optimizing recovery of single-disk failure

• US 10,048,999 B2
• Filed: 12/28/2015
• Issued: 08/14/2018
• Est. Priority Date: 09/25/2015
• Status: Active Grant

• Current Assignee: Tsinghua University
• Original Assignee: Tsinghua University
• Inventors: Shu, Jiwu, Shen, Zhirong
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US14/980,571
• Publication Number:
  US 20170091018A1
• Time in Patent Office: 960 Days
• Field of Search: 714 612
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial

Abstract

The present invention discloses a method for optimizing recovery of a single-disk failure, including the following steps: obtaining, according to current load information, an amount of data expected to be read and an allowed number of iterations; obtaining a recovery optimization policy for failed data in each single stripe, and combining an initial recovery policy for multiple stripes; and further optimizing the initial recovery policy by using a greedy algorithm based on tabu search, subject to the amount of data expected to be read and the allowed number of iterations, to finally obtain an optimal recovery policy with a smallest quantity of seeks. The optimization method of the present invention reduces the amount of data to be read and the quantity of seek operations, and improves the efficiency of recovering a single-disk failure. The present invention further discloses an apparatus for optimizing recovery of a single-disk failure.

Claims

1. A method for optimizing recovery of a failure of a single-disk, comprising:

using a processor of a computer system to execute the following steps;

obtaining, according to current load information of an erasure-coded storage system comprising a first disk and a second disk, an amount of data expected to be read and an allowed number of iterations, wherein the first disk comprises a first portion and a second portion, and the second disk comprises a third portion and a fourth portion, the first portion and the third portion store failed data in a first stripe, and the second portion and the fourth portion store failed data in a second stripe;

obtaining a recovery optimization policy for the failed data in each single stripe of the first stripe and the second stripe, and combining the recovery optimization policy for the failed data in the each single stripe to obtain an initial recovery policy for the first stripe and the second stripe;

further optimizing the initial recovery policy by using a greedy algorithm based on tabu search, subject to the amount of data expected to be read and the allowed number of iterations, to obtain an optimal recovery policy with a smallest quantity of seeks, so that the failure of the single-disk is recovered according to the optimal recovery policy;

wherein the step of optimizing the initial recovery policy by using a greedy algorithm based on tabu search, subject to the amount of data expected to be read and the allowed number of iterations, to obtain an optimal recovery policy with a smallest quantity of seeks, further comprises;

initializing a tabu list to an empty set, wherein the tabu list stores a quantity of seeks needed by an optimal solution that is found during each iteration;

during each iteration, performing an input by using the optimal recovery solution in a last iteration as the initial recovery policy in the current iteration; and

after the allowed number of iterations, selecting a solution with the smallest quantity of seeks from the tabu list to serve as the optimal recovery policy; and

recovering the failure of the single-disk according to the optimal recovery policy,

wherein the optimal recovery policy is to read data from the each single stripe according to the amount of data expected to be read and a decoding rule of an erasure code to recover the failed data stored in the each single stripe, and

wherein to read the data from the each single stripe, the following steps further comprise rotating a magnetic head of the single-disk to a position where the data resides.

2. The method for optimizing recovery of a failure of a single-disk according to claim 1, wherein if the amount of data needed by the optimal recovery policy is smaller than the amount of data expected to be read, data padding is performed.

3. The method for optimizing recovery of a failure of a single-disk according to claim 1, wherein the quantity of seeks comprises the number of magnetic head rotations and preparations before the data is read, and the single stripe is a set of multiple data strips and corresponding parity strips generated by an erasure code.

4. A non-transitory computer readable medium having stored thereon executable instructions that when executed by one or more processors of a computer system, cause the computer system to

obtain, by an obtaining module, according to current load information of an erasure-coded storage system comprising a first disk and a second disk, an amount of data expected to be read and an allowed number of iterations, wherein the first disk comprises a first portion and a second portion, and the second disk comprises a third portion and a fourth portion, the first portion and the third portion store failed data in a first stripe, and the second portion and the fourth portion store failed data in a second stripe;

obtain, by a combining module, a recovery optimization policy for the failed data in each single stripe of the first stripe and the second stripe,

combine, by the obtaining module, the recovery optimization policy for the failed data in each single stripe to obtain an initial recovery policy for the first stripe and the second stripe; and

further optimzied, by an optimizing module, the initial recovery policy by using a greedy algorithm based on tabu search, subject to the amount of data expected to be read and the allowed number of iterations, to obtain an optimal recovery policy with a smallest quantity of seeks, so that the single-disk failure is recovered according to the optimal recovery policy;

wherein the optimizing module is further configured to;

initialize a tabu list to an empty set, wherein the tabu list stores a quantity of seeks needed by an optimal solution that is found during each iteration;

during each iteration, perform an input by using the optimal recovery solution in a last iteration as the initial recovery policy in the current iteration; and

after the allowed number of iterations, select a solution with the smallest quantity of seeks from the tabu list to serve as the optimal recovery policy; and

recovering the failure of the single-disk according to the optimal recovery policy,

wherein the optimal recovery policy is to read data from the each single stripe according to the amount of data expected to be read and a decoding rule of an erasure code to recover the failed data stored in the each single stripe, and

wherein to read the data from the each single stripe, the executable instructions further cause the computer system to rotate a magnetic head of the single-disk to a position where the data resides.

5. The non-transitory computer readable medium of claim 4, wherein the executable instructions cause-the computer system to further perform a data padding, by the optimizing module, if the amount of data needed by the optimal recovery policy is smaller than the amount of data expected to be read.

6. The non-transitory computer readable medium of claim 4, wherein the quantity of seeks comprises the number of magnetic head rotations and preparations before the data is read, and the each single stripe is a set of multiple data strips and corresponding parity strips generated by an erasure code.