Method and apparatus for recovering errors in a storage system

• US 8,775,870 B2
• Filed: 12/22/2011
• Issued: 07/08/2014
• Est. Priority Date: 12/22/2010
• Status: Active Grant

• Current Assignee: KT Corporation
• Original Assignee: KT Corporation
• Inventors: Park, Chang-Sik, Kim, Mi-Jeom, Kim, Hyo-Min, Lee, Eo-Hyung, Hwang, Jin-Kyung
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): KUDIRKA, JOSEPH R
• Application Number:
  US13/334,710
• Publication Number:
  US 20120166870A1
• Time in Patent Office: 929 Days
• Field of Search: 714/6.1, 714/6.24, 714/6.3, 714/13, 714/15, 714/21, 714/52, 714/54, 714/800, 714/803, 714/805, 714/799, 714/819, 707/690, 707/691, 707697-699
• US Class Current: 714/15
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/186 Passive fault masking when reading multiple copies of the same data

Abstract

Apparatus and method for recovering errors from erroneous files in a storage system. In order to recover the errors from the erroneous files, each of at least three erroneous files stored in the storage system may be divided in half to form three sets of divided files. Three corresponding, portions from each of the three sets of divided files may be compared. A determination may be made as to whether at least two portions among the three corresponding portions are substantially identical. Based on the determination, substantially identical portions are determined to be non-erroneous portions. Then, a non-matched portion that is not substantially identical to the two substantially identical portions may be replaced with one of the non-erroneous portions.

Claims

1. A method for recovering errors from erroneous files in a storage system, the method comprising:

dividing each of at least three erroneous files stored in the storage system in half to form three sets of divided files;

comparing three corresponding portions from each of the three sets of divided files;

determining whether at least two portions among the three corresponding portions are identical, wherein identical portions are determined to be non-erroneous portions; and

replacing a non-matched portion that is not identical to the two identical portions with one of the non-erroneous portions,

wherein the method further comprises;

(a) dividing each of the three corresponding portions in half when the at least two portions are not determined to be identical;

(b) comparing three corresponding sub-portions with each other;

(c) determining whether at least two sub-portions among the three corresponding sub-portions are identical, wherein identical sub-portions are determined to be non-erroneous sub-portions; and

(d) replacing a non-matched sub-portion that is not identical to the two identical sub-portions with one of the non-erroneous sub-portions.

2. The method of claim 1, wherein the at least three erroneous files comprise at least one of an original file and its replicas.

3. The method of claim 1, wherein the comparing the three corresponding portions comprises computing parities of each of the three corresponding portions.

4. The method of claim 1, after the replacing the non-matched portion with the non-erroneous portion, the method further comprising:

combining respective divided portions from each of the at least three erroneous files to form recovered files;

comparing parities of the recovered files with a master parity stored in the storage system; and

determining an error recovery to be successful when at least one parity among the parities of the recovered files is identical to the master parity.

5. The method of claim 1, after the replacing the non-matched portion with the non-erroneous portion, the method further comprising:

combining respective divided portions from each of the at least three erroneous files to form recovered files;

comparing parities of the recovered files with each other; and

determining an error recovery to be successful when at least two parities among the parities of the recovered files are identical.

6. The method of claim 1, wherein prior to the dividing each of the at least three erroneous files, the method further comprises:

comparing parities of corresponding files including an original file and its replicas with a master parity stored in the storage system; and

determining all of the corresponding files to be erroneous when no parities of the corresponding files are identical to the master parity.

7. The method of claim 1, wherein prior to the dividing each of the at least three erroneous files, the method further comprises:

comparing parities of corresponding files including an original file and its replicas with each other; and

determining all of the corresponding files to be erroneous when no parities of the corresponding files are identical to each other.

8. The method of claim 1, wherein after the determining whether the at least two sub-portions are identical, the method further comprising:

repeating steps (a), (b), and (c) until a size of a divided sub-portion becomes 1 bit, when the at least two sub-portions are not determined to be identical.

9. A method for recovering errors from erroneous files in a storage system, the method comprising:

comparing corresponding portions from each of the erroneous files;

determining whether at least two corresponding portions among the corresponding portions are identical, wherein identical portions are determined to be non-erroneous portions;

replacing a non-matched portion that is not identical to the two identical portions with one of the non-erroneous portions

repeatedly dividing each of the corresponding portions into sub-portions until at least two corresponding sub-portions are identical.

10. The method of claim 9, wherein the repeatedly dividing each of the corresponding portions into the sub-portions comprises repeatedly dividing each of the corresponding portions into the sub-portions until a size of a non-matched sub-portion becomes 1 bit.

11. The method of claim 10, wherein the repeatedly dividing each of the corresponding portions into the sub-portions comprises dividing each of the corresponding portions in half.

12. The method of claim 9, wherein the comparing the corresponding portions from each of the erroneous files comprises comparing at least three corresponding portions divided from each of the erroneous files.

13. The method of claim 9, wherein the comparing the corresponding portions comprises computing parities of the corresponding portions to verify data consistency among the corresponding portions.

14. An apparatus for recovering errors from erroneous files stored in a storage system, the system comprising:

a comparison unit configured to compare corresponding portions from each of the erroneous files;

a determination unit configured to determine whether at least two corresponding portions among the corresponding portions are identical, wherein identical portions are determined to be non-erroneous portions;

an error recovery unit configured to replace a non-matched portion that is not identical to the two identical portions with one of the non-erroneous portions to recover errors in the non-matched portion; and

a division unit configured to divide each of the corresponding portions into sub-portions and to repeatedly divide each of the corresponding portions in half until at least two corresponding sub-portions are identical.

15. The apparatus of claim 14, wherein the erroneous files comprise at least one of an original file and its replicas.

16. The apparatus of claim 14, wherein the comparison unit is further configured to compute parities of the corresponding portions to verify data consistency among the corresponding portions.

17. The apparatus of claim 14, wherein the division unit is further configured to repeatedly divide each of the corresponding portions in half until a size of a divided sub-portion becomes 1 bit, when the at least two corresponding sub-portions are not identical.