Methods for avoiding over-commitment of virtual capacity in a redundant hierarchic data storage system

• US 5,651,133 A
• Filed: 02/01/1995
• Issued: 07/22/1997
• Est. Priority Date: 02/01/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Diamond, Bryan M., Burkes, Theresa A., Nelson, Marvin D.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): SAUNDERS, KEITH
• Application Number:
  US08/382,350
• Time in Patent Office: 902 Days
• Field of Search: 395/441, 395/182.04, 395/182.05, 395/416, 395/417, 371/10.1, 371/10.2
• 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 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies

Abstract

A hierarchic disk array data storage system has a disk array with multiple storage disks and a disk array controller which coordinates data transfer to and from the disks. The storage disks define a physical storage space. A RAID management system maps a RAID-level virtual storage space onto the physical storage space. The RAID-level virtual storage space presents the physical storage space as multiple RAID areas. The RAID areas include mirror RAID areas which contain mirror allocation blocks to store data according to mirror redundancy and parity RAID areas which contain parity allocation blocks to store data according to parity redundancy. The RAID management system dynamically migrates data between the mirror and parity RAID areas in a manner which optimizes performance and data reliability. As new storage requests are made, the RAID management system evaluates the existing storage conditions and computes a total virtual capacity that is available to the user given a disk array configuration. A total virtual capacity can be calculated without including the capacity of any given storage disk in the disk array data storage system. The total virtual capacity calculation is used to support hot spare space reservation, disk removal, rebuild of a failed disk, and to prevent over-commitment of storage to user data.

Claims

1. A method for avoiding over-commitment of virtual storage space in a hierarchic data storage system;

the data storage system comprising a disk array of multiple storage disks of selected capacities that define a physical storage space of a total physical capacity, the physical storage space being mapped into a RAID-level virtual storage space which presents the physical storage space as multiple RAID areas, the RAID areas including mirror RAID areas which store data according to mirror redundancy and parity RAID areas which store data according to parity redundancy, the RAID-level virtual storage space being mapped into an application-level storage space;

the method comprising the following steps;

mapping the RAID-level virtual storage space into an application-level storage space;

providing for a minimum percentage of user data to be kept in the mirror RAID areas;

providing for a remaining percentage of user data to be kept in parity RAID areas; and

computing a total virtual capacity of the application-level virtual storage space that can be committed to a user based upon the provision for the minimum percentage of user data to be kept in mirror RAID areas and the remaining percentage of user data to be kept in parity RAID areas.

2. A method according to claim 1 further comprising the following additional steps:

providing a hot spare option where a quantity of the RAID-level virtual storage space is reserved for disk sparing space;

detecting whether the user has activated the hot spare option; and

in the event the hot spare option is activated, computing the total virtual capacity of the application-level virtual storage space without including a capacity of a largest size storage disk.

3. A method according to claim 1 further comprising the following additional steps:

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user; and

computing an uncommitted capacity that has not been committed for use by the user by subtracting the committed capacity from the result of the total virtual capacity computation.

4. A method according to claim 1 further comprising the following additional steps:

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user;

in the event that a storage disk fails, the computing step comprises computing the total virtual capacity without including a capacity of a failed storage disk; and

determining whether there is sufficient capacity to permit rebuild of the failed storage disk by evaluating whether the total virtual capacity computed without including the capacity of the failed storage disk is greater than or equal to the committed capacity.

5. A method according to claim 1 further comprising the following additional steps:

providing a hot spare option where a quantity of the RAID-level virtual storage space is reserved for disk sparing space;

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user;

in the event that a user requests to activate a hot spare option, the computing step comprises computing the total virtual capacity without including a capacity of a failed storage disk; and

approving the request to activate the hot spare option if the total virtual capacity computed without including the capacity of the failed storage disk is greater than or equal to the committed capacity.

6. A method according to claim 1 further comprising the following additional steps:

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user;

receiving a request from the user to add a new quantity of application-level virtual storage space;

evaluating whether the new quantity of application-level virtual storage space can be committed to the user based upon the result of the total virtual capacity computation, the committed capacity, and the requested new quantity of application-level virtual storage space; and

approving commitment of the requested new quantity of application-level virtual storage space to the user if the requested new quantity is less than a difference between the total virtual capacity and the committed capacity.

7. A method according to claim 1 further comprising the following additional steps:

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user; and

evaluating whether the storage capacity of one storage disk can be lost without compromising the committed capacity to the user, the evaluation being based upon the result of the total virtual capacity computation, the committed capacity, and the capacity of the one storage disk.

8. A method according to claim 1 further comprising the following additional steps:

setting a desired threshold ratio of unused application-level virtual storage space to the result of the total virtual capacity computation;

determining an actual ratio of an actual amount of unused application-level virtual storage space to the result of the total virtual capacity computation; and

informing the user that capacity of the application-level virtual storage space is depleted if the actual ratio exceeds the threshold ratio.

9. A method according to claim 1 further comprising the following additional steps:

reserving a selected quantity of RAID-level virtual storage space; and

migrating data between the mirror and parity RAID areas using the reserved virtual storage space.

21. A computer-readable medium having computer-executable instructions for performing the steps in the method recited in claim 1.

10. A method for avoiding over-commitment of virtual storage space in a hierarchic data storage system;

the data storage system comprising a disk array of N storage disks of selected capacities that define a physical storage space of a total physical capacity;

the method comprising the following steps;

(a) mapping the physical storage space into a RAID-level virtual storage space which presents the physical storage space as multiple RAID areas, individual RAID areas extending across multiple storage disks, the RAID areas including a number of mirror RAID areas (MR) which store data according to mirror redundancy and a number of parity RAID areas (PR) which store data according to parity redundancy, the mirror RAID areas consuming a quantity of RAID-level virtual storage space (MVT) equal to 1/2MR*N, the parity RAID areas consuming a quantity of RAID-level virtual storage space (PVT) equal to PR(N-1);

(b) providing for a minimum percentage of user data to be kept in the mirror RAID areas (MR);

(c) defining one or more sets of RAID-level virtual storage space, individual sets comprising a group of RAID areas which extend across the same number of storage disks;

(d) assuming that the mirror RAID areas (MR) reside in one or more sets that contain the group of RAID areas with a highest number of storage disks;

(e) assuming that the parity RAID areas (PR) reside in the remaining RAID-level virtual storage space;

(f) locating the set which contains both the mirror RAID areas and the parity RAID areas;

(g) computing a capacity of the RAID-level virtual storage space of the set located in step (f) as a function of both MVT and PVT;

(h) computing a capacity of the RAID-level virtual storage space of any set other than the set located in step (f) as a function of one of MVT or PVT; and

(i) summing the capacities of the RAID-level virtual storage spaces for each set computed in steps (g) and (h) to yield a total virtual capacity.

11. A method according to claim 10 further comprising the following additional steps:

providing a hot spare option where a quantity of the RAID-level virtual storage space is reserved for disk sparing space;

detecting whether the user has activated the hot spare option; and

in the event the hot spare option is activated, computing the total virtual capacity of the application-level virtual storage space without including a capacity of a largest size storage disk.

12. A method according to claim 10 further comprising the following additional steps:

mapping the RAID-level virtual storage space into an application-level virtual storage space;

providing a committed capacity of the application-level virtual storage space that has been committed for use by the user; and

computing an uncommitted capacity that has not been committed for use by the user by subtracting the committed capacity from the result of the total virtual capacity computation.

13. A method according to claim 10 further comprising the following additional steps:

reserving a selected quantity of RAID-level virtual storage space; and

migrating data between the mirror and parity RAID areas using the reserved virtual storage space.

22. A computer-readable medium having computer-executable instructions for performing the steps in the method recited in claim 10.

14. A method for operating a hierarchic data storage system;

the data storage system comprising a disk array of multiple storage disks of selected capacities that define a physical storage space of a total physical capacity;

the method comprising the following steps;

(a) mapping the physical storage space into a RAID-level virtual storage space which presents the physical storage space as multiple RAID areas, the RAID areas including mirror RAID areas which contain mirror allocation blocks to store data according to mirror redundancy and parity RAID areas which contain parity allocation blocks to store data according to parity redundancy, individual RAID areas extending across multiple storage disks and being associated with a region from individual storage disks, the RAID-level virtual storage space also having unused allocation blocks;

(b) providing reserved storage space in a non-contiguous manner throughout the RAID-level virtual storage space;

(c) receiving a request to allocate a new allocation block as one of a mirror allocation block or a parity allocation block;

(d) examining individual RAID areas to identify any unused allocation blocks;

(e) counting a number of unused allocation blocks; and

(f) allowing the request to allocate a new allocation block if the number of unused allocation blocks is greater than or equal to the reserved storage space.

15. A method according to claim 14 wherein the allocation blocks having a size such that multiple allocation blocks can correlate to one region of the physical storage space and the step (c) of receiving a request comprises receiving a request to convert an undesignated RAID area to a new mirror RAID area of a selected size;

the method further comprising the following additional steps;

(g) deriving a maximum allowable size of a mirror RAID area as a function of the number of unused allocation blocks, the reserved storage space, and a number of allocation blocks per region; and

(h) allowing the request to convert the undesignated RAID area to a new mirror RAID area if its selected size is less than or equal to the maximum allowable size.

23. A computer-readable medium having computer-executable instructions for performing the steps in the method recited in claim 14.

16. A hierarchic data storage system comprising:

a disk array having a number of storage disks that define a physical storage space;

a disk array controller coupled to the disk array for coordinating data transfer to and from the disks;

a RAID management system operatively coupled to the disk array controller for mapping a RAID-level virtual storage space onto the physical storage space of the storage disks;

the RAID-level virtual storage space presenting the physical storage space as multiple RAID areas, individual RAID areas extending across multiple storage disks, the RAID areas including mirror RAID areas which store data according to mirror redundancy and parity RAID areas which store data according to parity redundancy;

the RAID management system providing for a minimum percentage of user data to be kept in the mirror RAID areas and for a remaining percentage of user data to be kept in parity RAID areas;

the RAID management system mapping the RAID-level virtual storage space into an application-level storage space presented to a user; and

the RAID management system computing a total virtual capacity of the application-level virtual storage space that can be committed to a user based upon the provision for the minimum percentage of user data to be kept in the mirror RAID areas and for the remaining percentage of user data to be kept in the parity RAID areas.

17. A hierarchic data storage system according to claim 16 wherein:

the RAID management system defines one or more sets of RAID-level virtual storage space, individual sets comprising a group of RAID areas which extend across the same number of storage disks;

the RAID management system assumes that the mirror RAID areas reside in one or more sets that contain the group of RAID areas with a highest number of storage disks and that the parity RAID areas reside in the remaining RAID-level virtual storage space, where one common set contains both mirror and parity RAID areas; and

the RAID management system computes the total virtual capacity TVC according to the following relationship;

##EQU4## where MR represents the number of mirror RAID areas, PR represents the number of parity RAID areas, NG represents a number of storage disks within the common set, NS represents a number of storage disks within a set other than the common set, the subscript "inside" designates that the mirror and parity RAID areas are located within the common set, and the subscript "outside" designates that the mirror and parity RAID areas are located in sets other than the common set.

18. A hierarchic data storage system according to claim 16 wherein:

the RAID management system defines one or more sets of RAID-level virtual storage space, individual sets comprising a group of RAID areas which extend across the same number of storage disks;

the RAID management system assumes that the mirror RAID areas reside in one or more sets i that contain the group of RAID areas with a highest number of storage disks and that the parity RAID areas reside in the remaining RAID-level virtual storage space, where one common set G contains both mirror and parity RAID areas; and

the RAID management system locates the common set G which is the smallest G that satisfies the following relationship;

##EQU5## where "VirCapacMirSet" represents the virtual capacity of the mirror RAID areas in set i, "VirCapacParSet" represents the virtual capacity of the parity RAID areas in set i, K represents a total number of sets, and C represents the minimum percentage of mirror RAID areas.

19. A hierarchic data storage system according to claim 16 wherein:

the RAID management system sets aside a quantity of the RAID-level virtual storage space for disk sparing space when a hot spare option is enabled; and

if the hot spare option is enabled, the RAID management system computes a total virtual capacity of the application-level virtual storage space that can be committed to a user without including a capacity of a largest size storage disk in the disk array.

20. A hierarchic data storage system according to claim 16 wherein the RAID management system computes the total virtual capacity without including a capacity of at least one of the storage disks in the physical storage space.