Method and system for managing storage systems containing multiple data storage devices

• US 6,880,102 B1
• Filed: 05/29/2002
• Issued: 04/12/2005
• Est. Priority Date: 10/23/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Bridge, William
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US10/158,757
• Time in Patent Office: 1,049 Days
• Field of Search: 714/6, 714/5, 714/7, 714/42, 714/54, 714/710, 714/718, 711/113, 711/114, 711/165, 711/166
• 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/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover

Abstract

An approach for efficiently managing logical volumes of data includes subdividing logical volumes of data into relatively small pieces that are spread over several physical disks. When a determination is made that a particular disk drive is to store more than one piece of a volume, a plurality of pieces of the volume are selected to be stored on the particular disk drive based at least in part on how far apart the pieces are within an address space of the volume. In response to an addition of one or more new drives to a system that contains a plurality of disk drives, at least a piece of each of the plurality of volumes may be moved from a drive of the plurality of disk drives to at least one of the one or more new drives.

Claims

1. A method of distributing a volume across a plurality of disk drives, the method comprising the steps of:

determining that a particular disk drive of said plurality of disk drives is to store more than one piece of said volume; and

selecting a plurality of pieces of said volume to store on said particular disk drive based at least in part on how far apart said pieces are within an address space of said volume.

2. The method of claim 1 wherein the step of selecting includes selecting to store, on said particular disk drive, pieces that are farther apart within the address space of said volume over pieces that are closer together within the address space of said volume.

3. A method of managing data, the method comprising the steps of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives;

maintaining, for each volume of said plurality of logical volumes, a list of entries;

wherein each entry in the list of entries corresponds to a logical volume piece and identifies a disk drive piece that stores the corresponding logical volume piece;

maintaining a logical volume directory that includes the list of entries for each logical volume of said plurality of logical volumes; and

using the list of entries for a particular logical volume to translate logical volume I/O requests into physical disk drive I/O requests.

4. The method of claim 3 wherein the step of maintaining a list of entries includes maintaining an ordered list of entries, wherein the list of entries is ordered based on logical volume addresses associated with the entries in the list of entries.

5. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about the size of each logical volume.

6. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about a striping factor of each logical volume.

7. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about a stripe unit of each logical volume.

8. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about allocation of each logical volume.

9. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about a disk group of each logical volume.

10. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about an extent size of each logical volume.

11. The method of claim 3, further comprising the step of maintaining, within said logical volume directory, information about a redundancy algorithm of each logical volume.

12. The method of claim 3 wherein:

the plurality of logical volumes includes a first logical volume;

the method includes the steps of

maintaining a directory entry for the first logical volume;

storing one or more extent pointers for the first logical volume in the directory entry for the first logical volume.

13. The method of claim 12 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point directly to data extents of the first logical volume.

14. The method of claim 12 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point indirectly to data extents of the first logical volume.

15. The method of claim 14 wherein the step of storing one or more extent pointers that point indirectly to data extents of the first logical volume includes storing one or more extent pointers that point to pointer extents.

16. The method of claim 15 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extend that resides in a second disk group;

wherein the first disk group is different than said second disk group.

17. The method of claim 15 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

18. A method of managing data, the method comprising the steps of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives, wherein the plurality of logical volumes includes a first logical volume;

maintaining a logical volume directory that includes a directory entry for each volume of said plurality of logical volumes;

storing, in the directory entry for the first logical volume, one or more extent pointers for locating data extents that belong to the first logical volume.

19. The method of claim 18 wherein the step of storing one or more extent pointers includes the step of:

determining whether the first logical volume exceeds a size threshold; and

if the first logical volume exceeds a size threshold, then storing one or more extent pointers that point indirectly, through one or more pointer extents, to data extents for said first logical volume; and

if the first logical volume does not exceed said size threshold, then storing one or more extent pointers that point directly to data extents for said first logical volume.

20. The method of claim 18 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point to pointer extents.

21. The method of claim 20 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extent that resides in a second disk group;

wherein the first disk group is different than said second disk group.

22. The method of claim 21 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

23. The method of claim 18 wherein the step of maintaining a logical volume directory includes storing, at a first position in the logical volume directory, a particular directory entry that corresponds to a logical volume for storing said logical volume directory.

24. The method of claim 18 further comprising the steps of:

establishing a set of said plurality of disk drives as a root disk group; and

recording in a header of every disk drive in the root disk group an address associated with a first data extent of a logical volume for storing the logical volume directory.

25. The method of claim 18 further comprising the step of:

on each disk drive of said plurality of disk drives, maintaining an allocation table that has an entry for each allocation unit of the disk drive; and

wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating that the allocation unit is part of said particular logical volume.

26. The method of claim 25 wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating a specific data extent, of said particular logical volume, to which said allocation unit belongs.

27. The method of claim 25 further comprising the step of using information from the allocation table of a disk drive to rebuild lost pointer extents that held extent pointers to one or more allocation units on the disk drive.

28. The method of claim 25 further comprising the step of using information from pointer extents that hold extent pointers to one or more allocation units on a disk drive to restore an allocation table of the disk drive.

29. The method of claim 25 further comprising the step of deleting a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be deleted;

after writing the active change directory entry, updating allocation tables of disk drives that contain pieces of said particular logical volume, and updating the logical volume directory entry for the particular logical volume; and

after updating the allocation tables and the logical volume directory entry, marking the active change directory entry as complete.

30. The method of claim 25 further comprising the step of creating a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be created;

after writing the active change directory entry, updating allocation tables of disk drives that are to contain pieces of said particular logical volume, and creating a logical volume directory entry for the particular logical volume; and

after updating the allocation tables and creating the logical volume directory entry, marking the active change directory entry as complete.

31. The method of claim 18 wherein the step of storing one or more extent pointers includes the step of:

storing one or more extent pointers that point directly to data extents for said first logical volume; and

in response to a change that increases the size of the first logical volume, performing the steps of

allocating one or more pointer extents; and

storing in the directory entry one or more extent pointers that point indirectly, through said one or more pointer extents, to data extents for said first logical volume.

32. A computer-readable medium carrying instructions for distributing a volume across a plurality of disk drives, the computer-readable medium comprising instructions for performing the steps of:

determining that a particular disk drive of said plurality of disk drives is to store more than one piece of said volume; and

selecting a plurality of pieces of said volume to store on said particular disk drive based at least in part on how far apart said pieces are within an address space of said volume.

33. The computer-readable medium of claim 32 wherein the step of selecting includes selecting to store, on said particular disk drive, pieces that are farther apart within the address space of said volume over pieces that are closer together within the address space of said volume.

34. A computer-readable medium carrying instructions for managing data, the computer-readable medium comprising instructions for performing the steps of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives;

maintaining, for each volume of said plurality of logical volumes, a list of entries;

wherein each entry in the list of entries corresponds to a logical volume piece and identifies a disk drive piece that stores the corresponding logical volume piece;

maintaining a logical volume directory that includes the list of entries for each logical volume of said plurality of logical volumes; and

using the list of entries for a particular logical volume to translate logical volume I/O requests into physical disk drive I/O requests.

35. The computer-readable medium of claim 34 wherein the step of maintaining a list of entries includes maintaining an ordered list of entries, wherein the list of entries is ordered based on logical volume addresses associated with the entries in the list of entries.

36. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about the size of each logical volume.

37. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about a striping factor of each logical volume.

38. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about a stripe unit of each logical volume.

39. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about allocation of each logical volume.

40. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about a disk group of each logical volume.

41. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about an extent size of each logical volume.

42. The computer-readable medium of claim 34, further comprising instructions for performing the step of maintaining, within said logical volume directory, information about a redundancy algorithm of each logical volume.

43. The computer-readable medium of claim 34 wherein:

the plurality of logical volumes includes a first logical volume;

the computer-readable medium includes instructions for performing the steps of

maintaining a directory entry for the first logical volume;

storing one or more extent pointers for the first logical volume in the directory entry for the first logical volume.

44. The computer-readable medium of claim 43 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point directly to data extents of the first logical volume.

45. The computer-readable medium of claim 43 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point indirectly to data extents of the first logical volume.

46. The computer-readable medium of claim 45 wherein the step of storing one or more extent pointers that point indirectly to data extents of the first logical volume includes storing one or more extent pointers that point to pointer extents.

47. The computer-readable medium of claim 46 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extend that resides in a second disk group;

wherein the first disk group is different than said second disk group.

48. The computer-readable medium of claim 46 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

49. A computer-readable medium carrying instructions for managing data, the computer-readable medium comprising instructions for performing the steps of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives, wherein the plurality of logical volumes includes a first logical volume;

maintaining a logical volume directory that includes a directory entry for each volume of said plurality of logical volumes;

storing, in the directory entry for the first logical volume, one or more extent pointers for locating data extents that belong to the first logical volume.

50. The computer-readable medium of claim 49 wherein the step of storing one or more extent pointers includes the step of:

determining whether the first logical volume exceeds a size threshold; and

if the first logical volume exceeds a size threshold, then storing one or more extent pointers that point indirectly, through one or more pointer extents, to data extents for said first logical volume; and

if the first logical volume does not exceed said size threshold, then storing one or more extent pointers that point directly to data extents for said first logical volume.

51. The computer-readable medium of claim 49 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point to pointer extents.

52. The computer-readable medium of claim 51 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extent that resides in a second disk group;

wherein the first disk group is different than said second disk group.

53. The computer-readable medium of claim 52 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

54. The computer-readable medium of claim 49 wherein the step of maintaining a logical volume directory includes storing, at a first position in the logical volume directory, a particular directory entry that corresponds to a logical volume for storing said logical volume directory.

55. The computer-readable medium of claim 49 further comprising instructions for performing the steps of:

establishing a set of said plurality of disk drives as a root disk group; and

recording in a header of every disk drive in the root disk group an address associated with a first data extent of a logical volume for storing the logical volume directory.

56. The computer-readable medium of claim 49 further comprising instructions for performing the step of:

on each disk drive of said plurality of disk drives, maintaining an allocation table that has an entry for each allocation unit of the disk drive; and

wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating that the allocation unit is part of said particular logical volume.

57. The computer-readable medium of claim 56 wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating a specific data extent, of said particular logical volume, to which said allocation unit belongs.

58. The computer-readable medium of claim 56 further comprising instructions for performing the step of using information from the allocation table of a disk drive to rebuild lost pointer extents that held extent pointers to one or more allocation units on the disk drive.

59. The computer-readable medium of claim 56 further comprising instructions for performing the step of using information from pointer extents that hold extent pointers to one or more allocation units on a disk drive to restore an allocation table of the disk drive.

60. The computer-readable medium of claim 56 further comprising instructions for performing the step of deleting a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be deleted;

after writing the active change directory entry, updating allocation tables of disk drives that contain pieces of said particular logical volume, and updating the logical volume directory entry for the particular logical volume; and

after updating the allocation tables and the logical volume directory entry, marking the active change directory entry as complete.

61. The computer-readable medium of claim 56 further comprising instructions for performing the step of creating a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be created;

after writing the active change directory entry, updating allocation tables of disk drives that are to contain pieces of said particular logical volume, and creating a logical volume directory entry for the particular logical volume; and

after updating the allocation tables and creating the logical volume directory entry, marking the active change directory entry as complete.

62. The computer-readable medium of claim 49 wherein the step of storing one or more extent pointers includes the step of:

storing one or more extent pointers that point directly to data extents for said first logical volume; and

in response to a change that increases the size of the first logical volume, performing the steps of

allocating one or more pointer extents; and

storing in the directory entry one or more extent pointers that point indirectly, through said one or more pointer extents, to data extents for said first logical volume.

63. An apparatus for distributing a volume across a plurality of disk drives, the apparatus comprising a memory storing instructions which, when executed by one or more processors, causes the performance of:

determining that a particular disk drive of said plurality of disk drives is to store more than one piece of said volume; and

selecting a plurality of pieces of said volume to store on said particular disk drive based at least in part on how far apart said pieces are within an address space of said volume.

64. The apparatus of claim 63 wherein the step of selecting includes selecting to store, on said particular disk drive, pieces that are farther apart within the address space of said volume over pieces that are closer together within the address space of said volume.

65. An apparatus for managing data, the apparatus comprising a memory storing instructions which, when executed by one or more processors, causes the performance of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives;

maintaining, for each volume of said plurality of logical volumes, a list of entries;

wherein each entry in the list of entries corresponds to a logical volume piece and identifies a disk drive piece that stores the corresponding logical volume piece;

maintaining a logical volume directory that includes the list of entries for each logical volume of said plurality of logical volumes; and

using the list of entries for a particular logical volume to translate logical volume I/O requests into physical disk drive I/O requests.

66. The apparatus of claim 65 wherein the step of maintaining a list of entries includes maintaining an ordered list of entries, wherein the list of entries is ordered based on logical volume addresses associated with the entries in the list of entries.

67. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about the size of each logical volume.

68. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about a striping factor of each logical volume.

69. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about a stripe unit of each logical volume.

70. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about allocation of each logical volume.

71. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about a disk group of each logical volume.

72. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about an extent size of each logical volume.

73. The apparatus of claim 65, wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of maintaining, within said logical volume directory, information about a redundancy algorithm of each logical volume.

74. The apparatus of claim 65 wherein:

the plurality of logical volumes includes a first logical volume;

The apparatus includes instructions for performing the steps of

maintaining a directory entry for the first logical volume;

storing one or more extent pointers for the first logical volume in the directory entry for the first logical volume.

75. The apparatus of claim 74 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point directly to data extents of the first logical volume.

76. The apparatus of claim 74 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point indirectly to data extents of the first logical volume.

77. The apparatus of claim 76 wherein the step of storing one or more extent pointers that point indirectly to data extents of the first logical volume includes storing one or more extent pointers that point to pointer extents.

78. The apparatus of claim 77 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extend that resides in a second disk group;

wherein the first disk group is different than said second disk group.

79. The apparatus of claim 77 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

80. An apparatus for managing data, the apparatus comprising a memory storing instructions which, when executed by one or more processors, causes the performance of:

storing the data within a plurality of logical volumes spread across a plurality of disk drives, wherein the plurality of logical volumes includes a first logical volume;

maintaining a logical volume directory that includes a directory entry for each volume of said plurality of logical volumes;

storing, in the directory entry for the first logical volume, one or more extent pointers for locating data extents that belong to the first logical volume.

81. The apparatus of claim 80 wherein the step of storing one or more extent pointers includes the step of:

determining whether the first logical volume exceeds a size threshold; and

if the first logical volume exceeds a size threshold, then storing one or more extent pointers that point indirectly, through one or more pointer extents, to data extents for said first logical volume; and

if the first logical volume does not exceed said size threshold, then storing one or more extent pointers that point directly to data extents for said first logical volume.

82. The apparatus of claim 80 wherein the step of storing one or more extent pointers includes storing one or more extent pointers that point to pointer extents.

83. The apparatus of claim 82 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that resides on a disk in a first disk group; and

storing in the pointer extent a second extent pointer that points to a data extent that resides in a second disk group;

wherein the first disk group is different than said second disk group.

84. The apparatus of claim 83 wherein the step of storing one or more extent pointers that point to pointer extents includes:

storing a first extent pointer that points to a pointer extent that has a first size; and

storing in the pointer extent a second extent pointer that points to a data extend that has a second size;

wherein the first size is different than said second size.

85. The apparatus of claim 80 wherein the step of maintaining a logical volume directory includes storing, at a first position in the logical volume directory, a particular directory entry that corresponds to a logical volume for storing said logical volume directory.

86. The apparatus of claim 80 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of:

establishing a set of said plurality of disk drives as a root disk group; and

recording in a header of every disk drive in the root disk group an address associated with a first data extent of a logical volume for storing the logical volume directory.

87. The apparatus of claim 80 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of:

on each disk drive of said plurality of disk drives, maintaining an allocation table that has an entry for each allocation unit of the disk drive; and

wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating that the allocation unit is part of said particular logical volume.

88. The apparatus of claim 87 wherein the entry associated with an allocation unit that is part of a particular logical volume includes data indicating a specific data extent, of said particular logical volume, to which said allocation unit belongs.

89. The apparatus of claim 81 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of using information from the allocation table of a disk drive to rebuild lost pointer extents that held extent pointers to one or more allocation units on the disk drive.

90. The apparatus of claim 87 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of using information from pointer extents that hold extent pointers to one or more allocation units on a disk drive to restore an allocation table of the disk drive.

91. The apparatus of claim 87 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of deleting a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be deleted;

after writing the active change directory entry, updating allocation tables of disk drives that contain pieces of said particular logical volume, and updating the logical volume directory entry for the particular logical volume; and

after updating the allocation tables and the logical volume directory entry, marking the active change directory entry as complete.

92. The apparatus of claim 87 wherein the memory further comprises one or more additional instructions which, when executed by the one or more processors, cause the performance of creating a particular logical volume by performing the steps of:

writing an active change directory entry indicating that the particular logical volume is to be created;

after writing the active change directory entry, updating allocation tables of disk drives that are to contain pieces of said particular logical volume, and creating a logical volume directory entry for the particular logical volume; and

after updating the allocation tables and creating the logical volume directory entry, marking the active change directory entry as complete.

93. The apparatus of claim 80 wherein the step of storing one or more extent pointers includes the step of:

storing one or more extent pointers that point directly to data extents for said first logical volume; and

in response to a change that increases the size of the first logical volume, performing the steps of

allocating one or more pointer extents; and

storing in the directory entry one or more extent pointers that point indirectly, through said one or more pointer extents, to data extents for said first logical volume.