Dynamic data recovery

• US 6,871,295 B2
• Filed: 01/29/2002
• Issued: 03/22/2005
• Est. Priority Date: 01/29/2001
• Status: Expired due to Term

• Current Assignee: Braodband Storage LLC, Overland Storage Incorporated (Silicon Valley Technology Partners LLC)
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Schweitzer, James R., Bolstad, Gregory D., Staub, John R., Randall, Jay G., Ulrich, Thomas R., Priester, George W.
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): Matthew, Aaron D
• Application Number:
  US10/060,686
• Publication Number:
  US 20020166079A1
• Time in Patent Office: 1,148 Days
• Field of Search: 714/5, 714/6, 714/7, 714/8, 714/800, 711/114
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A system and method for dynamic data recovery is described. The system and method for dynamic data recovery operates on a computer storage system that includes a plurality of disk drives for storing parity groups. Each parity group includes storage blocks. Each of the storage blocks is stored on a separate disk drive such that no two storage blocks from a given parity set reside on the same disk drive. The computer storage system further includes a recovery module to dynamically recover data that is lost when at least a portion of one disk drive in the plurality of disk drives becomes unavailable. The recovery module is configured to produce a reconstructed block by using information in the remaining storage blocks of a parity set that corresponds to an unavailable storage block. The recovery module is further configured to split the parity group corresponding to an unavailable storage block into two parity groups if the parity group corresponding to the unavailable storage block spanned all of the drives in the plurality of disk drives.

Claims

1. A computer storage system, comprising:

a plurality of disk drives for storing parity groups, each parity group comprising storage blocks, said storage blocks comprising one or more data blocks and a parity block associated with said one or more data blocks, each of said storage blocks stored on a separate disk drive such that no two storage blocks from a given parity group reside on the same disk drive; and

a recovery module to dynamically recover data lost when at least a portion of one disk drive in said plurality of disk drives becomes unavailable, said recovery module configured to produce a reconstructed block by using information in the remaining storage blocks of a parity group corresponding to an unavailable storage block, said recovery module further configured to split said parity group corresponding to an unavailable storage block into two parity groups if said parity group corresponding to said unavailable storage block spanned all of the drives in said plurality of disk drives.

2. The computer storage system of claim 1, wherein a size of a first parity group is larger than a size of a second parity group.

3. The computer storage system of claim 1, further comprising metadata to specify which disk drive in said plurality of disk drives contains a desired storage block.

4. The computer storage system of claim 1, further comprising metadata that specifies at least one Gnid-string.

5. The computer storage system of claim 4, wherein a one-to-one correspondence exists between said at least one Gnid-string and a directory of said file system.

6. The computer storage system of claim 4, wherein said Gnid-string comprises a collection of gnids.

7. The computer storage system of claim 6, wherein each of said gnids comprises information for locating a specified gnode.

8. The computer storage system of claim 7, wherein said information for locating a specified gnode comprises a pointer to said specified gnode.

9. The computer storage system of claim 7, wherein said specified gnode comprises file attributes for a file corresponding to said gnode.

10. The computer storage system of claim 9, wherein said file attributes include at least one of a file id, a file access time, a file creation time, and a file modification time.

11. The computer storage system of claim 7, wherein said specified gnode comprises information for locating a first gee of a plurality of gees corresponding to said gnode.

12. The computer storage system of claim 11, wherein said plurality of gees comprises gnode gees and data gees.

13. The computer storage system of claim 12, wherein each of said gnode gees comprises information to specify an extent.

14. The computer storage system of claim 12, wherein each of said data gees comprises information to specify a first logical disk block and information to specify which of said disk drives contains said first logical block.

15. The computer storage system of claim 12, wherein said plurality of gees further comprises parity gees.

16. The computer storage system of claim 15, wherein each of said parity gees comprises information regarding location of parity data for one or more preceding data gees in said plurality of gees.

17. The computer storage system of claim 11, wherein a parity group comprises a first set of one or more data gees and an associated parity gee.

18. The computer storage system of claim 17, wherein each data gee identifies a block of data and said parity gee identifies a parity block.

19. The computer storage system of claim 1, wherein said disk drives are provided to a Fibre channel network.

20. The computer storage system of claim 1, wherein a file is comprised of one or more of said parity groups.

21. The computer storage system of claim 1, further comprising metadata to specify a selected logical disk block and to specify which of said disks that contains said selected logical block.

22. The computer storage system of claim 1, wherein a size of a first parity group is larger than a size of a second parity group of the same file.

23. The computer storage system of claim 1, further comprising a redistribution module that combines a first parity group having m data blocks and one parity block and a second parity group having n data blocks and one parity block to produce a combined parity group having m+n data blocks and one parity block, where m+n is at most one less than the number of said disk drives.

24. The computer storage system of claim 23, wherein said redistribution module run in a background process during file system operations.

25. The computer storage system of claim 1, further comprising an allocation module to split a first parity group having k data blocks and one parity block into a second parity group having m data blocks and one parity block and a third parity group having n data blocks and one parity block, where k≧

m+n.

26. The computer storage system of claim 25, wherein said allocation module runs in a background process during file system operations.

27. The computer storage system of claim 25, wherein said first parity group is an unused parity group.

28. A method for storing data in a computer network, comprising:

determining a size of a parity group in response to a write request, said size describing a number of data blocks in said parity group;

arranging at least a portion of data from said write request according to said data blocks;

computing a parity block for said parity group;

storing each of said data blocks on a separate disk drive such that no two data blocks from said parity group reside on the same disk drive;

storing said parity block on a separate disk drive that does not contain any of said data blocks;

reconstructing lost data by using information in the remaining storage blocks of a parity group corresponding to an unavailable storage block to produce a reconstructed parity group;

splitting said reconstructed parity group corresponding to an unavailable storage block into two parity groups if said reconstructed parity group is too large to be stored on said plurality of disk drives.

29. The method of claim 28, further comprising storing metadata to describe a disk and logical block location of each of said data blocks and said parity block.

30. The method of claim 28, further comprising redistributing parity groups by combining a first parity group having a first size and a second parity group having a second size to produce a combined parity group having a third size, wherein said third size specifies a number of blocks that is, at most, one less than the number of disk drives available to store data from said parity group.

31. The method of claim 28, further comprises splitting a first unused parity group into a second unused parity group and a third unused parity group.

32. The method of claim 28, further comprising allocating space for a new parity group from a pool of available parity groups.

33. The method of claim 32, further comprising generating parity groups for said pool of available parity groups from unused disk space.

34. The method of claim 32, further comprising generating a plurality of differently-sized parity groups for said pool of available parity groups from unused disk space.

35. The method of claim 34, further comprising splitting a parity group in said pool of parity groups to produce two smaller parity groups in said pool of available parity groups.

36. The method of claim 34, further comprising combining one or more parity groups in said pool of parity groups to produce a combined parity group in said pool of available parity groups, said combined group larger than said one or more parity groups.

37. The method of claim 28, further comprising:

storing said reconstructed parity group on two or more of said plurality of disk drives.

38. The method of claim 37, wherein said storing occurs during normal file system operations.