Methods and system for reserving storage space for data migration in a redundant hierarchic data storage system by dynamically computing maximum storage space for mirror redundancy

• US 5,659,704 A
• Filed: 12/02/1994
• Issued: 08/19/1997
• Est. Priority Date: 12/02/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Burkes, Theresa A., Nelson, Marvin D., Diamond, Bryan M.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): SAUNDERS, KEITH
• Application Number:
  US08/348,391
• Time in Patent Office: 991 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 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies

Abstract

A hierarchic disk array data storage system has multiple storage disks that define a physical storage space and a RAID management system that maps the physical storage space into two virtual storage spaces. The RAID-level virtual storage space presents the physical storage space as mirror and parity RAID areas where the mirror RAID areas contain mirror allocation blocks to store data according to RAID Level 1 and the parity RAID areas contain parity allocation blocks to store data according to RAID Level 5. The application-level virtual storage space presents the physical storage space as multiple virtual blocks. The RAID management system migrates data between the mirror and parity RAID areas to optimize performance and reliability. To ensure that sufficient space is retained for this migration, the RAID management system limits the number of virtual blocks that are allocated in the mirror RAID areas. The maximum number of virtual blocks in mirror RAID areas is dynamically computed based upon a function of the physical capacity of the storage disks, the number of storage disks, and the allocated capacity at the time of each storage request from the user.

Claims

1. A method for reserving space in a hierarchic data storage system;

the data storage system comprising a disk array with a number of storage disks that define a physical storage space of a physical capacity, the physical storage space being mapped into a RAID-level virtual storage space having mirror and parity RAID areas, the RAID-level virtual storage space being mapped into an application-level virtual storage space having multiple virtual blocks which are associated with the mirror and parity RAID areas;

the method comprising the following steps;

(a) allocating virtual blocks in the application-level virtual storage space in mirror RAID areas for storing data according to mirror redundancy;

(b) storing data in the virtual blocks;

(c) determining an allocated capacity representing a total number of virtual blocks that are presently being used to store data; and

(d) dynamically computing a maximum allowable number of virtual blocks in mirror RAID areas as a function of the physical capacity, the allocated capacity, and the number of storage disks in the disk array in response to changes in the allocated capacity.

2. A method according to claim 1 further comprising the additional step of restricting allocation of more virtual blocks in mirror RAID areas than the computed maximum allowable number of virtual blocks in mirror RAID areas to thereby ensure space reservation for data migration between parity and mirror RAID areas.

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

allocating the virtual blocks in the application-level virtual storage space in parity RAID areas for storing data according to parity redundancy; and

migrating virtual blocks between mirror and parity storage using reserved space ensured by restricting allocation of virtual blocks in mirror RAID areas.

4. A method according to claim 1 further comprising the additional step of initially reserving an amount of physical storage space equivalent to at least one mirror RAID area.

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

in the event that the number of virtual blocks in mirror RAID areas is less than the maximum allowable number, storing data only in the virtual blocks in mirror RAID areas; and

in the event that the number of virtual blocks in mirror RAID areas exceeds the maximum allowable number,

allocating the virtual blocks in the application-level virtual storage space in parity RAID areas for storing data according to parity redundancy; and

storing data in virtual blocks in both the mirror and parity RAID areas.

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

allocating the virtual blocks in the application-level virtual storage space in parity RAID areas for storing data according to parity redundancy;

storing data in virtual blocks in both the mirror and parity RAID areas; and

as more data is stored in the disk array such that the allocated capacity approaches the physical capacity, migrating virtual blocks from mirror RAID areas to parity RAID areas to produce a decreasing proportion of data stored in mirror RAID areas to data stored in parity RAID areas.

7. A method according to claim 6 further comprising the additional step of maintaining a minimum number of virtual blocks in mirror RAID areas.

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

comparing the allocated capacity to the physical capacity; and

computing the maximum allowable number in step (d) only in the event that the allocated capacity is greater than or equal to one-half of the physical capacity.

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

10. A method for reserving space in a hierarchic data storage system;

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

the method comprising the following steps;

(a) providing a physical capacity of the physical storage space in the disk array;

(b) mapping the physical storage space into a RAID-level virtual storage space having multiple mirror and parity RAID areas;

(c) mapping the RAID-level virtual storage space into an application-level virtual storage space having multiple virtual blocks;

(d) allocating the virtual blocks in the application-level virtual storage space in mirror RAID areas for storing data according to mirror redundancy;

(e) storing data in the virtual blocks;

(f) determining an allocated capacity representing a total number of virtual blocks that are presently being used to store data;

(g) comparing the allocated capacity to the physical capacity; and

(h) if the allocated capacity is greater than or equal to one-half of the physical capacity, conducting the following steps;

(1) dynamically computing a maximum allowable number of virtual blocks in mirror RAID areas as a function of the physical capacity and the allocated capacity in response to changes in the allocated capacity;

(2) restricting allocation of more virtual blocks in mirror RAID areas than the computed maximum allowable number of virtual blocks in mirror RAID areas;

(3) allocating the virtual blocks in the application-level virtual storage space in parity RAID areas for storing data according to parity redundancy; and

(4) storing data in virtual blocks in both the mirror and parity RAID areas.

11. A method according to claim 10 wherein the mapping steps (b) and (c) yield RAID-level and application-level virtual storage spaces that have respective capacities which are less than the capacity of the physical storage space to logically reserve an amount of space that is not committed for use by a user.

12. A method according to claim 10 further comprising the additional step of maintaining a minimum number of virtual blocks in mirror RAID areas.

13. A method according to claim 10, wherein as more data is stored in the disk array such that the allocated capacity approaches the physical capacity, migrating virtual blocks from mirror RAID areas to parity RAID areas to produce a decreasing proportion of data stored in mirror RAID areas to data stored in parity RAID areas.

14. 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 into the physical storage space of the storage disks;

the RAID-level virtual storage space having multiple mirror and parity RAID areas;

the RAID management system allocating virtual blocks in mirror RAID areas for storing data according to mirror redundancy and virtual blocks in parity RAID areas for storing data according to parity redundancy, the RAID management system maintaining a count of the virtual blocks; and

the RAID management system being configured to dynamically compute a maximum allowable number of virtual blocks in the mirror RAID areas as a function of the physical capacity, the allocated capacity based on the count of virtual blocks, and the number of storage disks in response to changes in the allocated capacity.

15. A hierarchic data storage system comprising:

a homogenous disk array having a number of equal sized 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 into the physical storage space of the storage disks;

the RAID-level virtual storage space having multiple mirror and parity RAID areas;

the RAID management system allocating virtual blocks in mirror RAID areas for storing data according to mirror redundancy and virtual blocks in parity RAID areas for storing data according to parity redundancy, the RAID management system maintaining a count of the virtual blocks; and

the RAID management system being configured to dynamically compute a maximum allowable number of virtual blocks in the mirror RAID areas according to the following equation;

##EQU3## where "n" equals the number of storage disks in the disk array, "AllCap" represents the allocated capacity based on the count of the virtual blocks, and "PhyCap" represents the physical capacity of the disk array.

16. A hierarchic data storage system comprising:

a heterogeneous disk array having a number of various sized 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 into the physical storage space of the storage disks;

the RAID-level virtual storage space having multiple mirror and parity RAID areas;

the RAID management system allocating virtual blocks in mirror RAID areas for storing data according to mirror redundancy and virtual blocks in parity RAID areas for storing data according to parity redundancy, the RAID management system maintaining a count of the virtual blocks; and

the RAID management system being configured to dynamically compute a maximum allowable number of virtual blocks in the mirror RAID areas according to the following equation;

##EQU4## where "n" equals the number of storage disks in the disk array, "AllCap" represents the allocated capacity based on the count of the virtual blocks, "PhyCap" represents the physical capacity of the disk array, and "i" is the number of homogenous disk array representations that can be created from the heterogeneous disk array.

17. A method for reserving space in a hierarchic data storage system;

the data storage system comprising a homogeneous disk array with a number of equal sized storage disks that define a physical storage space of a physical capacity, the physical storage space being mapped into a RAID-level virtual storage space having mirror and parity RAID areas, the RAID-level virtual storage space being mapped into an application-level virtual storage space having multiple virtual blocks which are associated with the mirror and parity RAID areas;

the method comprising the following steps;

allocating virtual blocks in the application-level virtual storage space in mirror RAID areas for storing data according to mirror redundancy;

storing data in the virtual blocks;

determining an allocated capacity representing a total number of virtual blocks that are presently being used to store data; and

computing a maximum allowable number of virtual blocks in the mirror RAID areas according to the following equation;

##EQU5## where "n" equals the number of storage disks in the disk array, "AllCap" represents the allocated capacity based on the count of the virtual blocks, and "PhyCap" represents the physical capacity of the disk array.

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

19. A method for reserving space in a hierarchic data storage system;

the data storage system comprising a heterogeneous disk array with a number of various sized storage disks that define a physical storage space of a physical capacity, the physical storage space being mapped into a RAID-level virtual storage space having mirror and parity RAID areas, the RAID-level virtual storage space being mapped into an application-level virtual storage space having multiple virtual blocks which are associated with the mirror and parity RAID areas;

the method comprising the following steps;

allocating virtual blocks in the application-level virtual storage space in mirror RAID areas for storing data according to mirror redundancy;

storing data in the virtual blocks;

determining an allocated capacity representing a total number of virtual blocks that are presently being used to store data; and

computing a maximum allowable number of virtual blocks in the mirror RAID areas according to the following equation;

##EQU6## where "n" equals the number of storage disks in the disk array, "AllCap" represents the allocated capacity, "PhyCap" represents the physical capacity of the disk array, and "i" is the number of homogenous disk array representations that can be created from the heterogeneous disk array.

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