System And Method For Flexible Physical-Logical Mapping Raid Arrays

• US 20080120462A1
• Filed: 09/22/2005
• Published: 05/22/2008
• Est. Priority Date: 09/22/2005
• Status: Active Grant

• Current Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Original Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Inventors: Nehse, Paul
• Granted Patent: US 7,694,072 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system, method and computer program for allocating physical memory from a group of N memory devices to logical volumes. A group of N memory devices are partitioned into a plurality of bands, each of the group of N memory devices sharing a portion of each of the plurality of bands. A cluster map for each of the plurality of bands is generated. The cluster maps indicate the physical address for each of a plurality of clusters. Each of the plurality of clusters are distributed equally over two or more of the N memory devices to ensure a specified level of redundancy for each of the plurality of bands. Each of the N memory devices share an approximately equal number of clusters. Available bands are determined and are allocated to a logical volume.

Claims

1. A method of allocating physical memory from a group of N memory devices to logical volumes, the method comprising:

partitioning the group of N memory devices into a plurality of bands, each of the group of N memory devices sharing a portion of each of the plurality of bands;

generating a cluster map for each of the plurality of bands, each cluster map indicating the physical address for each of a plurality of clusters, each of the plurality of clusters equally distributed over two or more of the N memory devices to ensure a specified level of redundancy for each of the plurality of bands, each of the N memory devices sharing an approximately equal number of clusters;

determining if a band is available; and

allocating an available band to a logical volume.

2. The method of claim 1, wherein the boundaries between adjacent bands of the plurality of bands are determined such that each band is compatible with multiple levels of redundancy.

3. The method of claim 2, wherein the partitioning step further comprises generating a redundancy group map for each of multiple levels of redundancy, each redundancy group map indicating the location of redundancy groups on the N memory devices, wherein band boundaries between adjacent bands of the plurality of bands are determined at shared boundaries of the redundancy group maps.

4. The method of claim 3, wherein a redundancy group map for a RAID 0 system is determined by:

setting a RAID 0 redundancy number equal to the highest integer power of two divisible into N;

calculating a number of RAID 0 redundancy groups needed in a RAID 0 architecture for the group of N memory devices, the number of RAID 0 redundancy groups being equal to one if N is equal to the RAID 0 redundancy number, and the number of RAID 0 redundancy groups being equal to N if N is not equal to the RAID 0 redundancy number; and

generating a RAID 0 redundancy group map, wherein each RAID 0 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 0 redundancy number, each of the N memory devices hosting an equal number of RAID 0 redundancy groups.

5. The method of claim 4, wherein the step of generating a cluster map further comprises mapping each RAID 0 redundancy group to a cluster.

6. The method of claim 3, wherein a redundancy group map for a RAID 5 system is determined by:

setting a RAID 5 redundancy number equal to the highest integer power of two plus one divisible into N;

calculating a number of RAID 5 redundancy groups needed in a RAID 5 architecture for the group of N memory devices, the number of RAID 5 redundancy groups being equal to one if N is equal to the RAID 5 redundancy number, and the number of RAID 5 redundancy groups being equal to N if N is not equal to the RAID 5 redundancy number; and

generating a RAID 5 redundancy group map, wherein each RAID 5 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 5 redundancy number, each of the N memory devices hosting an equal number of RAID 5 redundancy groups.

7. The method of claim 6, wherein the step of generating a cluster map further comprises mapping each RAID 5 redundancy group to a cluster.

8. The method of claim 1, wherein each of the N memory devices in the group of N memory devices belong to a same storage class.

9. A computer program for allocating physical memory from a group of N memory devices to logical volumes, the program configured to:

partition the group of N memory devices into a plurality of bands, each of the group of N memory devices sharing a portion of each of the plurality of bands;

generate a cluster map for each of the plurality of bands, each cluster map indicating the physical address for each of a plurality of clusters, each of the plurality of clusters equally distributed over two or more of the N memory devices to ensure a specified level of redundancy for each of the plurality of bands, each of the N memory devices sharing an approximately equal number of clusters;

determine if a band is available; and

allocate an available band to a logical volume.

10. The program of claim 9, wherein the boundaries between adjacent bands of the plurality of bands are determined such that each band is compatible with multiple levels of redundancy.

11. The program of claim 10, wherein the partitioning step further comprises generating a redundancy group map for each of multiple levels of redundancy, each redundancy group map indicating the location of redundancy groups on the N memory devices, wherein band boundaries between adjacent bands of the plurality of bands are determined at shared boundaries of the redundancy group maps.

12. The program of claim 11, wherein a redundancy group map for a RAID 0 system is determined by

setting a RAID 0 redundancy number equal to the highest integer power of two divisible into N;

calculating a number of RAID 0 redundancy groups needed in a RAID 0 architecture for the group of N memory devices, the number of RAID 0 redundancy groups being equal to one if N is equal to the RAID 0 redundancy number, and the number of RAID 0 redundancy groups being equal to N if N is not equal to the RAID 0 redundancy number; and

generating a RAID 0 redundancy group map, wherein each RAID 0 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 0 redundancy number, each of the N memory devices hosting an equal number of RAID 0 redundancy groups.

13. The program of claim 12, wherein the step of generating a cluster map further comprises mapping each RAID 0 redundancy group to a cluster.

14. The program of claim 11, wherein a redundancy group map for a RAID 5 system is determined by:

setting a RAID 5 redundancy number equal to the highest integer power of two plus one divisible into N;

calculating a number of RAID 5 redundancy groups needed in a RAID 5 architecture for the group of N memory devices, the number of RAID 5 redundancy groups being equal to one if N is equal to the RAID 5 redundancy number, and the number of RAID 5 redundancy groups being equal to N if N is not equal to the RAID 5 redundancy number; and

generating a RAID 5 redundancy group map, wherein each RAID 5 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 5 redundancy number, each of the N memory devices hosting an equal number of RAID 5 redundancy groups.

15. The program of claim 14, wherein the step of generating a cluster map further comprises mapping each RAID 5 redundancy group to a cluster.

16. The program of claim 9, wherein the program is further configured to allow a user to classify all N memory devices in the group of N memory devices as a same storage class.

17. The program of claim 9, wherein the program is further configured to generate an error condition if no available bands are found.

18. A system for allocating physical memory to logical volumes, comprising:

a group of N memory devices, partitioned into a plurality of bands, each of the group of N memory devices sharing a portion of each of the plurality of bands;

a cluster map for each of the plurality of bands, each cluster map indicating the physical address for each of a plurality of clusters, each of the plurality of clusters equally distributed over two or more of the N memory devices to ensure a specified level of redundancy for each of the plurality of bands, each of the N memory devices sharing an approximately equal number of clusters;

an array controller configured to determine if a band from the plurality of bands is available and to allocate an available band to a logical volume.

19. The system of claim 18, wherein the boundaries between adjacent bands of the plurality of bands are arranged such that each band is compatible with multiple levels of redundancy.

20. The system of claim 19, further comprising a redundancy group map for each of multiple levels of redundancy, each redundancy group map indicating the location of redundancy groups on the N memory devices, wherein band boundaries between adjacent bands of the plurality of bands are located at shared boundaries of the redundancy group maps.

21. The system of claim 20, wherein a redundancy group map for a RAID 0 system comprises:

a RAID 0 redundancy number equal to the highest integer power of two divisible into N;

a number of RAID 0 redundancy groups, the number of RAID 0 redundancy groups being equal to one if N is equal to the RAID 0 redundancy number, and the number of RAID 0 redundancy groups being equal to N if N is not equal to the RAID 0 redundancy number; and

a RAID 0 redundancy group distribution, wherein each RAID 0 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 0 redundancy number, each of the N memory devices hosting an equal number of RAID 0 redundancy groups.

22. The system of claim 21, wherein each RAID 0 redundancy group is mapped to a cluster.

23. The program of claim 20, wherein a redundancy group map for a RAID 5 system comprises:

a RAID 5 redundancy number equal to the highest integer power of two plus one divisible into N;

a number of RAID 5 redundancy groups, the number of RAID 5 redundancy groups being equal to one if N is equal to the RAID 5 redundancy number, and the number of RAID 5 redundancy groups being equal to N if N is not equal to the RAID 5 redundancy number; and

a RAID 5 redundancy group distribution, wherein each RAID 5 redundancy group is distributed among a plurality of the N memory devices equal to the RAID 5 redundancy number, each of the N memory devices hosting an equal number of RAID 5 redundancy groups.

24. The system of claim 23, wherein each RAID 5 redundancy group is mapped to a cluster.

25. The system of claim 18, wherein all N memory devices in the group of N memory devices are classified as a same storage class.