Dynamic parity distribution technique

• US 7,328,305 B2
• Filed: 11/03/2003
• Issued: 02/05/2008
• Est. Priority Date: 11/03/2003
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): Kim; Matthew
• Assistant Examiner(s): PATEL, HETUL B
• Application Number:
  US10/700,227
• Publication Number:
  US 20050097270A1
• Time in Patent Office: 1,555 Days
• Field of Search: 711/113, 711/114, 714/5, 714/6, 714/701, 714/770, 714/800
• US Class Current: 711/114
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

A dynamic parity distribution system and technique distributes parity across disks of an array. The dynamic parity distribution system includes a storage operating system that integrates a file system with a RAID system. In response to a request to store (write) data on the array, the file system determines which disks contain free blocks in a next allocated stripe of the array. There may be multiple blocks within the stripe that do not contain file system data (i.e., unallocated data blocks) and that could potentially store parity. One or more of those unallocated data blocks can be assigned to store parity, arbitrarily. According to the dynamic parity distribution technique, the file system determines which blocks hold parity each time there is a write request to the stripe. The technique alternately allows the RAID system to assign a block to contain parity when each stripe is written.

Claims

1. A system adapted to distribute redundant information across disks of an array, the system comprising:

a storage operating system configured to invoke storage operations executed by a storage system, the storage operating system further configured to manage storage of information, including the redundant information and data, on blocks of the disks in response to disk access operations, the storage operating system including a storage module adapted to compute the redundant information in response to a layout of the data in stripes across the disks, the storage operating system maintaining at least one unallocated block per stripe for use by the storage module to store the computed redundant information, wherein the at least one unallocated block used to store the redundant information is located in any disk and wherein the location of the at least one unallocated block used to store the redundant information is dynamically allocated in a non-fixed pattern by the storage module before each write request is completed for each stripe.

2. The system of claim 1 wherein the storage module is a disk array controller configured to compute the redundant information and reconstruct blocks lost due to failure of one or more of the disks.

3. The system of claim 1 wherein the storage module is a RAID system configured to compute the redundant information and reconstruct blocks lost due to failure of one or more of the disks.

4. The system of claim 3 wherein the storage operating system is further configured to implement a high-level module that maintains information about locations of the data on the disks.

5. The system of claim 4 wherein the high-level module is a file system or database adapted to control layout of the data on the disks.

6. The system of claim 5 wherein the storage operating system integrates the file system or database with the RAID system.

7. The system of claim 6 wherein the file system or database is configured to determine block locations of the data on the disks and the RAID system is configured to determine the block locations of the redundant information on the disks.

8. The system of claim 6 wherein the file system or database is configured to determine block locations of the data and the redundant information on the disks.

9. The system of claim 8 wherein the file system or database renders balancing decisions to determine the block locations of the data and the redundant information on the disks.

10. The system of claim 9 wherein the balancing decisions comprises one of different sizes of disks, different speeds of disks, and whether a disk is more heavily utilized than other disks.

11. The system of claim 8 further comprising block allocation map structures used by the file system to determine the block locations of the data and the redundant information on the disks.

12. The system of claim 11 wherein the redundant information is parity.

13. The system of claim 1 wherein the storage module selects the at least one unallocated block to store the redundant information and wherein the storage module computes the redundant information using a redundant storage algorithm.

14. The system of claim 13 wherein the selection of the at least one unallocated block to store redundant information is independent of the redundant storage algorithm.

15. The system of claim 14 wherein the redundant storage algorithm is an asymmetric algorithm.

16. The system of claim 14 wherein the redundant storage algorithm is a symmetric algorithm.

17. The system of claim 16 wherein the redundant information is parity.

18. The system of claim 13 wherein the at least one unallocated block used to store the redundant information comprises two or more unallocated blocks used to store the redundant information.

19. The system of claim 18 wherein the selection of the unallocated blocks to store redundant information is independent of the redundant storage algorithm used to compute the redundant information.

20. The system of claim 19 wherein the redundant storage algorithm depends on positions of the blocks in the array.

21. The system of claim 20 wherein the redundant storage algorithm is a symmetric and wherein the redundant information is parity.

22. The system of claim 20 wherein the redundant storage algorithm is an asymmetric algorithm and wherein the redundant information is parity.

23. The system of claim 1, wherein the non-fixed pattern is created by the redundant information being stored in any block remaining after the data is allocated to blocks of the stripe.

24. A method for distributing redundant information across disks of an array, comprising:

dividing each disk into blocks, the blocks being organized into stripes such that each stripe contains one block from each disk;

selecting one or more blocks in a stripe layout of the stripe not used to contain data to contain the redundant information, wherein the selected one or more blocks used to contain the redundant information are located in any disk and wherein the location of the selected one or more blocks used to contain the redundant information is dynamically allocated in a non-fixed pattern before each write request for each stripe is completed;

computing the redundant information based on contents of all other blocks in the stripe layout, regardless of whether the blocks contain data; and

writing the data in one or more allocated blocks and the redundant information in the one or more selected blocks of the stripe that is written across the disks of the array.

25. The method of claim 24 further comprising the step of determining which block in a stripe contains redundant information each time there is a write request to the stripe.

26. The method of claim 25 further comprising the step of assigning a block to contain redundant information when each stripe is written.

27. The method of claim 26 wherein the step of determining is performed by a high-level module of a storage system and wherein the steps of computing and assigning are performed by a storage module of the storage system.

28. The method of claim 27 further comprising:

maintaining, by the high-level module, at least one unallocated block per stripe for use by the storage module; and

providing an indication from the high-level module to the storage module of the unallocated block to contain parity.

29. The method of claim 28 further comprising the step of reconstructing, using the storage module, a block that is lost due to failure of a disk.

30. The method of claim 27 wherein the high-level module is a file system and wherein the storage module is one of an array controller and a RAID system.

31. The method of claim 30 wherein the step of computing comprises computing the redundant information in response to the stripe layout of the data in stripes across the disks.

32. The method of claim 31 wherein the step of computing further comprises computing the redundant information using algebraic and algorithmic calculations in response to the placement of the data on the array.

33. Apparatus for distributing redundant information across disks of an array, the apparatus comprising:

means for dividing each disk into stripes, with each stripe containing one block from each disk;

means for selecting one or more blocks in a stripe layout of the stripe not used to contain data to contain redundant information, wherein the selected one or more blocks used to contain the redundant information are located in any disk and wherein the location of the selected one or more blocks used to contain the redundant information is dynamically allocated in a non-fixed pattern before each write request for each stripe is completed;

means for computing the redundant information based on contents of all other blocks in the stripe layout, regardless of whether the blocks contain data; and

means for writing the data in one or more allocated blocks and the redundant information in the one or more selected blocks of the stripe that is written across the disks of the array.

34. The apparatus of claim 33 further comprising means for determining which block or blocks in a stripe holds redundant information each time there is a write operation to the stripe.

35. A computer readable medium containing executable program instructions for distributing parity across disks of an array, the executable instructions comprising one or more program instructions for:

dividing each disk into stripes, with each stripe containing one block from each disk;

selecting one or more blocks in a stripe layout of the stripe not used to contain data to contain parity, wherein the selected one or more blocks used to contain the parity are located in any disk and wherein the location of the selected one or more block used to contain the parity is dynamically allocated in a non-fixed pattern before each write request for each stripe is completed;

computing the parity based on contents of all other blocks in the stripe, regardless of whether the blocks contain data; and

writing the data in one or more allocated blocks and the redundant information in the one or more selected blocks of the stripe that is written across the disks of the array.

36. A method for distributing redundant information across disks of an away with a plurality of blocks on each disk, comprising:

determining which blocks are unallocated in a stripe across the disks;

reserving unallocated blocks for storing the redundant information in one or more reserved unallocated blocks;

arranging data in the stripe for the data to be stored in one or more allocated blocks across the disks of the array;

assigning the redundant information in a non-fixed pattern to the one or more reserved unallocated blocks; and

writing the data in the allocated blocks and the redundant information in the one or more reserved unallocated blocks as the stripe across the disks of the array.

37. The method of claim 36, further comprising:

storing parity information as the redundant information in the one or more reserved unallocated blocks.

38. The method of claim 36, further comprising:

adding a disk to the array;

storing a second stripe across the array by determining one or more unallocated blocks across the array including the added disk, and writing the data to allocated blocks and the redundant information to the one or more unallocated blocks of the second stripe.

39. An apparatus for distributing redundant information across disks of an array with a plurality of blocks on each disk, comprising:

means for determining which blocks are unallocated in a stripe across the disks;

means for reserving unallocated blocks for storing the redundant information in one or more reserved unallocated blocks;

means for arranging data in the stripe for the data to be stored in one or more allocated blocks across the disks of the array;

means for assigning the redundant information in a non-fixed pattern to the one or more reserved unallocated block; and

means for writing the data in the allocated blocks and the redundant information in the one or more reserved unallocated blocks as the stripe across the disks of the array.

40. The apparatus of claim 39, further comprising:

means for storing parity information as the redundant information in the one or more reserved unallocated blocks.

41. The apparatus of claim 39, further comprising:

means for adding a disk to the array;

means for storing a second stripe across the array by determining one or more unallocated blocks across the array including the added disk, and writing the data to allocated blocks and the redundant information to the one or more unallocated blocks of the second stripe.

42. A system for distributing redundant information across disks of an array with a plurality of blocks on each disk, comprising:

a storage operating system configured to invoke storage operations executed by a storage system, the storage operating system further configured (i) to determine which blocks are unallocated in a stripe across the disks, (ii) to reserve unallocated blocks for storing the redundant information in one or more reserved unallocated blocks, (iii) to arrange data in the stripe for the data to be stored in one or more allocated blocks across the disks of the array, (iv) to assign the redundant information in a non-fixed pattern to the one or more reserved unallocated block, and (iv) to write the data in the allocated blocks and the redundant information in the one or more reserved unallocated blocks as the stripe across the disks of the array.

43. The system of claim 42, wherein the redundant information is parity information.

44. A computer readable medium containing executable program instructions for distributing parity across disks of an array, the executable instructions comprising one or more program instructions for:

determining which blocks are unallocated in a stripe across the disks, where each disk has a plurality of blocks;

reserving unallocated blocks for storing the redundant information in one or more reserved unallocated blocks;

arranging data in the stripe for the data to be stored in one or more allocated blocks across the disks of the array; and

assigning the redundant information in a non-fixed pattern to the one or more reserved unallocated block; and

writing the data in the allocated blocks and the redundant information in the one or more reserved unallocated blocks as the stripe across the disks of the array.

45. A method for distributing redundant information across disks of an array with a plurality of blocks on each disk, comprising:

allocating data to blocks in a stripe layout, where the stripe layout represents a stripe across the disks of the array;

reserving unallocated blocks for storing the redundant information in one or more reserved unallocated blocks;

assigning the redundant information to the one or more reserved unallocated blocks in a non-fixed pattern; and

writing the data in the allocated blocks and the redundant information in the one or more reserved unallocated blocks as the stripe across the disks of the array.

46. The method of claim 45, further comprising:

storing parity information as the redundant information in the one or more reserved unallocated blocks.

47. The method of claim 45, further comprising:

adding a disk to the array;

storing a second stripe across the array by determining one or more unallocated blocks across the array including the added disk, and writing the data to allocated blocks and the redundant information to the one or more unallocated blocks of the second stripe.

48. The method of claim 45, further comprising:

computing the redundant information based on contents of other blocks in the stripe layout, regardless of whether the blocks contain data or are empty.

49. The method of claim 48, wherein the step of computing uses a symmetric algorithm and wherein the redundant information is parity.

50. The method of claim 48, wherein the step of computing uses an asymmetric algorithm and wherein the redundant information is parity.

51. The method of claim 45, wherein the non-fixed pattern is created by the redundant information being stored in any block remaining after the data is allocated to blocks of the stripe.