Data storage subsystem including a storage disk array employing dynamic data striping

• US 6,745,284 B1
• Filed: 10/02/2000
• Issued: 06/01/2004
• Est. Priority Date: 10/02/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lee, Whay S., Rettberg, Randall D.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Li, Zhuo H.
• Application Number:
  US09/678,466
• Time in Patent Office: 1,338 Days
• Field of Search: 711/114, 711/113, 711/165, 711/170, 711/4, 711/207, 711/208, 711/202, 711/220, 711/112, 711/111, 711/161, 711/162, 711/205, 711/206, 714/6
• 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 2211/1026 Different size groups, i.e. non uniform size of groups in RAID systems with parity
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A data storage subsystem including a storage disk array employing dynamic data striping. A data storage subsystem includes a plurality of storage devices configured in an array and a storage controller coupled to the storage devices. The storage controller is configured to store a first stripe of data as a plurality of data stripe units across the plurality of storage devices. The plurality of data stripe units includes a plurality of data blocks and a parity block which is calculated for the plurality of data blocks. The storage controller is further configured to store a second stripe of data as a plurality of data stripe units across the storage devices. The second plurality of data stripe units includes another plurality of data blocks, which is different in number than the first plurality of data blocks, and a second parity block calculated for the second plurality of data blocks. Furthermore, the second plurality of data blocks may be a modified subset of the first plurality of data blocks. The storage controller is also configured to store the second plurality of data blocks and the second parity block to new locations.

Claims

1. A data storage subsystem, comprising:

a plurality of storage devices configured in an array; and

a storage controller coupled to said plurality of storage devices, wherein said storage controller is configured to store a first stripe of data as a first plurality of data stripe units across ones of said plurality of storage devices;

wherein said first plurality of data stripe units includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks;

wherein, in response to a data modification operation, said storage controller is configured to receive a write transaction modifying a second stripe of data, and to store only said second stripe of data as a second plurality of data stripe units to new locations across said ones of said plurality of storage devices,

wherein said second plurality of data stripe units includes a second plurality of data blocks, which is a subset of said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

2. The data storage subsystem as recited in claim 1, wherein said storage controller is further configured to compute said second parity block for said second plurality of data blocks, which is a modified subset of said first plurality of data blocks, and to store said second plurality of data blocks and said second parity block to a plurality of new locations.

3. The data storage subsystem as recited in claim 2, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said storage controller is further configured to select which ones of said plurality of new locations is closest in proximity to said disk head unit.

4. The data storage subsystem as recited in claim 1, wherein said storage controller is further configured to maintain a free segment bitmap comprising:

a listing of segments located on each one of said plurality of storage devices;

an indication of whether each of said segments contains active data, or no data; and

a current disk head position pointer configured to indicate the current position of a disk head unit on each one of said plurality of storage devices.

5. The data storage subsystem as recited in claim 4, wherein said storage controller is further configured to calculate a disk head offset value for each one of said plurality of storage devices, wherein said disk head offset value represents a positive or negative offset from a theoretical position indicated by said current disk head position pointer in said free segment bitmap.

6. The data storage subsystem as recited in claim 4, wherein said storage controller is further configured to maintain a block remapping table which maps a logical address for a data block to a first physical segment on one of said plurality of storage devices.

7. The data storage subsystem as recited in claim 6, wherein said block remapping table further maps said first physical segment in a first parity group to a second physical segment which belongs to said first parity group and is stored on another one of said plurality of storage devices.

8. The data storage subsystem as recited in claim 7, wherein said storage controller is further configured to remap a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups; and

storing each one of said plurality of new parity groups and said new parity blocks.

9. The data storage subsystem as recited in claim 8, wherein said storage controller is further configured to maintain a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.

10. A method for storing data in a data storage subsystem including a plurality of storage devices configured in an array and a storage controller coupled to said plurality of storage devices, said method comprising:

storing a first tripe of data as a first plurality of data stripe units across ones of a plurality of storage devices,

wherein said first plurality of data stripe units includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks; and

in response to a data modification operation, receiving a write transaction modifying a second stripe of data, and storing only said second stripe of data as a second plurality of data stripe units to new locations across said ones of said plurality of storage devices;

wherein said second plurality of data stripe units includes a second plurality of data blocks, which is a subset of said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

11. The method as recited in claim 10, wherein said method further comprises computing said second parity block for said second plurality of data blocks, which is a modified subset of said first plurality of data blocks, and to store said second plurality of data blocks and said second parity block to a plurality of new locations.

12. The method as recited in claim 11, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said method further comprises selecting which ones of said plurality of new locations is closest in proximity to said disk head unit.

13. The method as recited in claim 12, wherein said method further comprises maintaining a free segment bitmap comprising:

a listing of segments located on each one of said plurality of storage devices;

an indication of whether each of said segments contains active data, or no data; and

a current disk head position pointer configured to indicate the current position of said disk head unit on each one of said plurality of storage devices.

14. The method as recited in claim 13, wherein said method further comprises calculating a disk head offset value for each one of said plurality of storage devices, wherein said disk head offset value represents a positive or negative offset from a theoretical position indicated by said current disk head position pointer in said free segment bitmap.

15. The method as recited in claim 14, wherein said method further comprises maintaining a block remapping table which maps a logical address of a data block to a first physical segment on one of said plurality of storage devices.

16. The method as recited in claim 14, wherein said method further comprises said block remapping table further mapping said first physical segment in a first parity group to a second physical segment which belongs to said first parity group and is stored on another one of said plurality of storage devices.

17. The method as recited in claim 14, wherein said method further comprises remapping a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups;

storing each one of said plurality of new parity groups and said new parity blocks.

18. The method as recited in claim 14, wherein said method further comprises maintaining a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.

19. A computer system, comprising:

a processor,

a bus bridge unit coupled to said processor,

a memory coupled to said bus bridge unit; and

a data storage subsystem coupled to said bus bridge unit, the data storage subsystem including;

a plurality of storage devices configured in an array; and

a storage controller coupled to said plurality of storage devices, wherein said storage controller is configured to store a first strip of data as a first plurality of data stripe units across ones of said plurality of storage devices;

wherein said first plurality of data stripe unites includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks;

wherein, in response to a data modification operation, said storage controller is configured to receive a write transaction modifying a second stripe of data and to store only said second stripe of data as a second plurality of data stripe units to new locations across said ones of said plurality of storage devices; and

wherein said second plurality of data stripe units includes a second plurality of data blocks, which is a subset of said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

20. The computer system as recited in claim 19, wherein said storage controller is further configured to compute said second parity block for said second plurality of data blocks, which is a modified subset of said first plurality of data blocks, and to store said second plurality of data blocks and said second parity block to a plurality of new locations.

21. The computer system as recited in claim 20, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said storage controller is further configured to select which ones of said plurality of new locations is closest in proximity to said disk head unit.

22. The computer system as recited in claim 19, wherein said storage controller is further configured to maintain a free segment bitmap comprising:

a listing of segments located on each one of said plurality of storage devices;

an indication of whether each of said segments contains active data, or no data; and

a current disk head position pointer configured to indicate the current position of a disk head unit on each one of said plurality of storage devices.

23. The computer system as recited in claim 22, wherein said storage controller is further configured to calculate a disk head offset value for each one of said plurality of storage devices, wherein said disk head offset value represents a positive or negative offset from a theoretical position indicated by said current disk head position pointer in said free segment bitmap.

24. The computer system as recited in claim 22, wherein said storage controller is further configured to maintain a block remapping table which maps a logical address of a data block to a first physical segment on one of said plurality of storage devices.

25. The computer system as recited in claim 24, wherein said block remapping table further maps said first physical segment in a first parity group to a second physical segment which belongs to said first parity group and is stored on another one of said plurality of storage devices.

26. The computer system as recited in claim 25, wherein said storage controller is further configured to remap a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups;

storing each one of said plurality of new parity groups and said new parity blocks.

27. The computer system as recited in claim 26, wherein said storage controller is further configured to maintain a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.

28. A data storage subsystem comprising:

a plurality of storage devices configured in an array; and

a storage controller coupled to said plurality of storage devices, wherein said storage controller is configured to store a first stripe of data as a first plurality of data stripe units across ones of said plurality of storage devices;

wherein said first plurality of data stripe units includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks;

wherein said storage controller is configured to receive a write transaction modifying a subset of said first plurality of data blocks;

wherein said storage controller is configured to calculate a new parity block for said subset of said first plurality of data blocks;

wherein said storage controller is configured to only store said subset of said first plurality of data blocks modified by the write transaction and said new parity block as a new parity group to new locations across ones of said plurality of storage devices.

29. The data storage subsystem as recited in claim 28, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said storage controller is further configured to select ones of a plurality of new locations closest in proximity to said disk head unit.

30. The data storage subsystem as recited in claim 28, wherein said storage controller is further configured to store a second stripe of data as a second plurality of data stripe units across said ones of said plurality of storage devices, wherein said second plurality of data stripe units includes a second plurality of data blocks, which is different in number than said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

31. The data storage subsystem as recited in claim 28, wherein said storage controller is further configured to remap a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups;

and

storing each one of said plurality of new parity groups and said new parity blocks to new locations across ones of said plurality of storage devices.

32. The data storage subsystem as recited in claim 31, wherein said storage controller is further configured to maintain a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.

33. A method for storing data in a data storage subsystem including a plurality of storage devices configured in an array and a storage controller coupled to said plurality of storage devices, said method comprising:

storing a first stripe of data as a first plurality of data stripe units across ones of a plurality of storage devices;

wherein said first plurality of data stripe units includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks;

receiving a write transaction modifying a subset of said first plurality of data blocks;

calculating a new parity block for said subset of said first plurality of data blocks; and

storing only said subset of said first plurality of data blocks modified by the write transaction and said new parity block as a new parity group to new locations across ones of said plurality of storage devices.

34. The method as recited in claim 33, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said method further comprises selecting which ones of said plurality of new locations is closest in proximity to said disk head unit.

35. The method as recited in claim 34, wherein said method further comprises storing a second stripe of data as a second plurality of data stripe units across said ones of said plurality of storage devices, wherein said second plurality of data stripe units includes a second plurality of data blocks, which is different in number than said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

36. The method as recited in claim 35, wherein said method further comprises remapping a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups; and

storing each one of said plurality of new parity groups and said new parity blocks to new locations across ones of said plurality of storage devices.

37. The method as recited in claim 35, wherein said method further comprises maintaining a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.

38. A computer system comprising:

a processor;

a bus bridge unit coupled to said processor;

a memory coupled to said bus bridge unit; and

a data storage subsystem coupled to said bus bridge unit, the data storage subsystem including;

a plurality of storage devices configured in an array; and

a storage controller coupled to said plurality of storage devices, wherein said storage controller is configured to store a first stripe of data as a first plurality of data stripe units across ones of said plurality of storage devices,

wherein said first plurality of data stripe units includes a first plurality of data blocks and a first parity block which is calculated for said first plurality of data blocks; and

wherein said storage controller is configured to receive a write transaction modifying a subset of said first plurality of data blocks;

wherein said storage controller is configured to calculate a new parity block for said subset of said first plurality of data blocks;

wherein said storage controller is configured to only store said subset of said first plurality of data blocks modified by the write transaction and said new parity block as a new parity group to new locations across ones of said plurality of storage devices.

39. The computer system as recited in claim 38, wherein each one of said plurality of storage devices includes a disk head unit configured for reading and writing data, and wherein said storage controller is further configured to select ones of a plurality of new locations closest in proximity to said disk head unit.

40. The computer system as recited in claim 39, wherein said storage controller is further configured to store a second stripe of data as a second plurality of data stripe units across said ones of said plurality of storage devices, wherein said second plurality of data stripe units includes a second plurality of data blocks, which is different in number than said first plurality of data blocks, and a second parity block which is calculated for said second plurality of data blocks.

41. The computer system as recited in claim 40, wherein said storage controller is further configured to remap a plurality of parity groups by:

collecting a plurality of existing parity groups each one of which comprises a non-default number of data blocks stored across said storage devices;

forming a plurality of new parity groups from said plurality of existing parity groups, wherein each one of said plurality of new parity groups comprises a default number of data blocks;

calculating a plurality of new parity blocks for each one of said new parity groups; and

storing each one of said plurality of new parity groups and said new parity blocks to new locations across ones of said plurality of storage devices.

42. The computer system as recited in claim 41, wherein said storage controller is further configured to maintain a plurality of versions of said plurality of existing parity groups which existed prior to a modification of ones of said data blocks in said plurality of existing parity groups.