Method, system, program, and data structures for mapping logical blocks to physical blocks

• US 6,839,827 B1
• Filed: 01/18/2000
• Issued: 01/04/2005
• Est. Priority Date: 01/18/2000
• Status: Expired due to Term

• Current Assignee: International Business Corporation (Kleangas Energy Technologies, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kalos, Matthew Joseph, Beardsley, Brent Cameron
• Primary Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/484,574
• Time in Patent Office: 1,813 Days
• Field of Search: 711/4, 711/114, 711/202, 711/203, 711/206, 711/173
• US Class Current: 711/206
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Disclosed is a method, system, program, and data structure for a storage controller to map logical blocks to physical storage blocks. The storage controller is in communication with at least one host system that views a logical storage space. The storage controller defines the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space. The storage controller further defines a physical storage space as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical blocks in the physical storage system. The storage controller associates each logical chunk in the sequence of logical chunks defining the logical storage space with one physical chunk in the physical storage system. Further, the contiguous logical chunks are capable of being associated with non-contiguous physical chunks.

Claims

1. A method for mapping logical blocks to physical storage blocks in a storage controller in communication with at least one host system that views a logical storage space, comprising:

defining, with the storage controller, the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

defining with the storage controller, a physical storage space as a sequence of physical chunks managed by the storage controller, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system;

associating, with the storage controller, each logical chunk in the sequence of logical chunks defining the logical storage space in the at least one host system with one physical chunk in the physical storage system, wherein continuous logical chunks are capable of being associated with non-contiguous physical chunks;

determining a number of logical chunks to add to the logical storage space to expand storage in the logical storage space;

determining one physical chunk not associated with a logical chunk in the physical storage space for each determined logical chunks to add; and

associating each determined physical chunk with each determined logical chunk to add to the logical storage space.

2. The method of claim 1, wherein the logical storage space comprises a logical volume and the physical storage space comprises multiple storage devices, wherein the physical chunks associated with at least two logical chunks in the logical volume are located in separate storage devices.

3. The method of claim 2, wherein each of the multiple storage devices comprises a RAID array and wherein at least two logical chunks in the logical volume are located in separate RAID arrays.

4. The method of claim 3, wherein the physical chunk size is a multiple of a stripe size.

5. The method of claim 4, wherein the physical chunk size is further selected such that a storage space in the RAID array is a multiple of the physical chunk size.

6. A method for mapping logical blocks to physical storage blocks in a storage controller in communication with at least one host system that views a logical storage space, comprising:

defining, with the storage controller, the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

defining, with the storage controller, a physical storage space as a sequence of physical chunks managed by the storage controller, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system; and

associating, with the storage controller, each logical chunk in the sequence of logical chunks defining the logical storage space in the at least one host system with one physical chunk in the physical storage system, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, wherein the logical chunk size is selected such that the logical storage space is a multiple of the logical chunk size.

7. The method of claim 6, wherein at least one host system does not include a logical volume manager for mapping logical blocks to physical storage space.

8. The method of claim 6, further comprising:

receiving a command to delete the logical storage space; and

removing, with the storage controller, the association of each logical chunk in the deleted logical storage space with each associated physical chunk, wherein each physical chunk for which the association is removed is available to be associated with another logical chunk.

9. A method for mapping logical blocks to physical storage blocks in a storage controller in communication with at least one host system that views a logical storage space, comprising:

defining, with the storage controller, the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

defining, with the storage controller, a physical storage space as a sequence of physical chunks managed by the storage controller, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system;

associating, with the storage controller, each logical chunk in the sequence of logical chunks defining the logical storage space in the at least one host system with one physical chunk in the physical storage system, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

receiving an input/output (I/O) request with respect to one logical block from one host system;

determining one logical chunk including the requested logical block;

determining the physical chunk associated with the determined logical chunk; and

determining the physical storage block within the physical chunk including data for the requested logical block.

10. The method of claim 9, wherein the logical block has a logical block address indicating a location of the logical block within a sequence of logical blocks, wherein the associated physical chunk begins at a beginning physical storage block, wherein determining the logical chunk including the requested logical block comprises determining a quotient of an operation dividing the logical block address by a number of logical block addresses per logical chunk, and wherein determining the physical storage block within the physical chunk comprises determining a physical storage block at an offset equal to a remainder of the operation from the beginning physical storage block.

11. A method for mapping logical blocks to physical storage blocks in a storage controller in communication with at least one host system that views a logical storage space, comprising:

defining, with the storage controller, the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

defining, with the storage controller, a physical storage space as a sequence of logical chunks managed by the storage controller, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system;

associating, with the storage controller, each logical chunk in the sequence of logical chunks defining the logical storage space in the at least one host system with one physical chunk in the physical storage system, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

generating a logical storage table including one entry for each logical chunk in the logical storage space, wherein each entry includes;

(i) a logical chunk number indicating a location of the logical chunk for the entry in a sequence of logical chunks defining the logical storage space;

(ii) a physical chunk number indicating a location of the physical chunk associated with the logical chunk for the entry in the physical storage space; and

generating a physical storage table including one entry for each physical chunk in the physical storage space, wherein each entry includes;

(i) a physical chunk number indicating a location of the physical chunk for the entry in a sequence of physical chunks defining the logical storage space;

(ii) a logical chunk number indicating a location of the logical chunk associated with the physical chunk for the entry in the logical storage space, wherein associating one physical chunk to one logical chunk comprises indicating in the physical chunk number in the entry for the associated logical chunk in the logical storage table the physical chunk number in the physical storage table of the associated physical chunk and indicating in the logical chunk number in the entry for the physical chunk in the physical storage table the logical chunk number in the logical storage table of the associated logical chunk.

12. The method of claim 11, wherein the physical storage system comprises multiple storage devices, wherein each entry in the logical storage table further includes a device number indicating the storage device including the associated physical chunk, wherein the associated physical chunk is located at a position corresponding to the physical number in the storage device.

13. The method of claim 12, wherein each storage device comprises a RAID array and wherein the device number indicates the RAID array including the associated physical chunk.

14. The method of claim 11, wherein the physical chunk size is selected such that the physical storage and logical storage tables will not exceed a predetermined size.

15. A storage controller system for mapping logical blocks defining a logical storage space to physical storage blocks in a physical storage system, wherein the storage controller is in communication with at least one host system that views a logical storage space, comprising:

means for defining the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

means for defining a physical storage space as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system;

means for associating each logical clunk in the sequence of logical chunks defining the logical storage space with one physical chunk in the physical storage system, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

means for determining a number of logical chunks to add to the logical storage space to expand storage in the logical storage space;

means for determining one physical chunk not associated with a logical chunk in the physical storage space for each detained logical chunks to add; and

means for associating each determined physical chunk with each determined logical chunk to add to the logical storage space.

16. The storage controller system of claim 15, wherein the logical storage space comprises a logical volume in a host system and the physical storage system comprises multiple storage devices, wherein the physical chunks associated with at least two logical chunks in the logical volume are located in separate storage devices.

17. The storage controller system of claim 16, wherein each of the multiple storage devices comprises a RAID array and wherein at least two logical chunks in the logical volume are located in separate RAID arrays.

18. The storage controller system of claim 17, wherein the physical chunk size is a multiple of a stripe size.

19. The storage controller system of claim 18, wherein the physical chunk size is further selected such that a storage space in the RAID array is an integer multiple of the physical chunk size.

20. A storage controller system for mapping logical blocks defining a logical storage space to physical storage blocks in a physical storage system, wherein the storage controller is in communication with at least one host system that views a logical storage space, comprising:

means for defining the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

means for defining a physical storage space as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the physical storage system;

means for associating each logical chunk in the sequence of logical chunks defining the logical storage space with one physical chunk in the physical storage system, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

means for receiving an input/output (I/O) request with respect to one logical block;

means for determining one logical chunk including the requested logical block;

means for determining the physical chunk associated with the determined logical chunk; and

means for determining the physical storage block within the physical chunk including data for the requested logical block.

21. The storage controller system of claim 20, wherein the logical storage space is implemented in a host system in communication with a storage controller that controls access to the physical storage system, wherein the storage controller includes the means for defining the logical and physical chunks and associating logical with physical chunks.

22. The storage controller system of claim 20, wherein the logical chunk size is selected such that the logical storage space is an integer multiple of the logical chunk size.

23. The storage controller system of claim 20 further comprising:

means for deleting the logical storage space; and

means for removing the association of each logical chunk in the deleted logical storage space with each associated physical chunk, wherein each physical chunk for which the association is removed is available to be associated with another logical chunk.

24. The system of claim 20, wherein the logical block has a logical block address indicating a location of the logical block within a sequence of logical blocks, wherein the associated physical chunk begins at a beginning physical storage block, wherein the means for determining the logical chunk including the requested logical block comprises determining a quotient of an operation dividing the logical block address by a number of logical block addresses per logical chunk, and wherein determining the physical storage block within the physical chunk comprises means for determining a physical storage block at an offset equal to a remainder of the operation from the beginning physical storage block.

25. An article of manufacture for mapping logical blocks to physical storage blocks, wherein at least one host system views a logical storage spaces the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a storage controller to perform;

defining the logical storage space as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical storage space;

defining a physical storage space as a sequence of physical chunks, wherein each logical chunk comprises a plurality of physical storage blocks in the physical storage system;

associating each logical chunk in the sequence of logical chunks defining the logical storage space with one physical chunk in the physical storage system wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

determining a number of logical chunks to add to the logical storage space to expand storage in the logical storage space;

determining one physical chunk not associated with a logical chunk in the physical storage space for each determined logical chunks to add; and

associating each determined physical chunk with each determined logical chunk to add to the logical storage space.

26. An article of manufacture for mapping logical blocks to physical storage blocks, wherein at least one host system views a logical volume, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a storage controller to perform;

defining the logical volume as a sequence of logical chunks wherein each logical chunk comprises a plurality of logical blocks in the logical volume,

defining multiple RAID arrays as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the RAID arrays;

associating each logical chunk in the sequence of logical chunks defining the logical volume with one physical chunk in the RAID arrays, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, and wherein at least two logical chunks in the logical volume are located in separate RAID arrays.

27. The article of manufacture of claim 26, wherein the physical chunk size is a multiple of a stripe size.

28. The article of manufacture of claim, 27, wherein the physical chunk size is further selected such that a storage space in the RAID array is a multiple of the physical chunk size.

29. An article of manufacture for mapping logical blocks to physical storage blocks, wherein at least one host system views a logical volume, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a storage controller to perform:

defining the logical volume as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical volume;

defining multiple RAID arrays as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the RAID arrays;

associating each logical chunk in the sequence of logical chunks defining the logical volume with one physical chunk in the RAID arrays, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, wherein the logical chunk size is selected such that the logical storage space is a multiple of the logical chunk size.

30. The article of manufacture of claim 29, wherein the logical storage space comprises a logical volume and the physical storage system comprises multiple storage devices, wherein the physical chunks associated with at least two logical chunks in the logical volume are located it separate storage devices.

31. The article of manufacture of claim 29, further causing the storage controller to perform:

deleting the logical storage space; and

removing the association of each logical chunk in the deleted logical storage space with each associated physical chunk, wherein each physical chunk for which the association is removed is available to be associated with another logical chunk.

32. An article of manufacture for mapping logical blocks to physical storage blocks, wherein at least one host system views a logical volume, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a storage controller to perform:

defining the logical volume as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical volume;

defining multiple RAID arrays as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the RAID arrays;

associating each logical chunk in the sequence of logical chunks defining the logical volume with one physical chunk in the RAID arrays, wherein contiguous logical chunk are capable of being associated with non-continuous physical chunks;

receiving an input/output (I/O) request with respect to one logical block;

determining one logical chunk including the requested logical block;

determining the physical chunk associated with the determined logical chunk; and

determining the physical storage block within the physical chunk including data for the requested logical block.

33. The article of manufacture of claim 32, wherein the logical block has a logical block address indicating a location of the logical block within a sequence of logical blocks, wherein the associated physical chunk begins at a beginning physical storage block, wherein determining the logical chunk including the requested logical block comprises determining a quotient of an operation dividing the logical block address by a number of logical block addresses per logical chunk, and wherein determining the physical storage block within the physical chunk comprises determining a physical storage block at an offset equal to a remainder of the operation from the beginning physical storage block.

34. An article of manufacture for mapping logical blocks to physical storage blocks, wherein at least one host system views a logical volume, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a storage controller to perform:

defining the logical volume as a sequence of logical chunks, wherein each logical chunk comprises a plurality of logical blocks in the logical volume;

defining multiple RAID arrays as a sequence of physical chunks, wherein each physical chunk comprises a plurality of physical storage blocks in the RAID arrays;

associating each logical chunk in the sequence of logical chunks defining the logical volume with one physical chunk in the RAID arrays, wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks;

generating a logical storage table including one entry for each logical chunk in the logical storage space, wherein each entry includes;

(i) a logical chunk number indicating a location of the logical chunk for the entry in a sequence of logical chunks defining the logical storage space;

(ii) a physical chunk number indicating a location of the physical chunk associated with the logical chunk for the entry in the physical storage space; and

generating a physical storage table including one entry for each physical chunk in the physical storage space, wherein each entry includes;

(i) a physical chunk number indicating a location of the physical chunk for the entry in a sequence of physical chunks defining the logical storage space;

(ii) a logical chunk number indicating a location of the logical chunk associated with the physical chunk for the entry in the logical storage space, wherein associating one physical chunk to one logical chunk comprises indicating in the physical chunk number in the entry for the associated logical chunk in the logical storage table the physical chunk number in the physical storage table of the associated physical chunk and indicating in the logical chunk number in the entry for the physical chunk in the physical storage table the logical chunk number in the logical storage table of the associated logical chunk.

35. The article of manufacture of claim 34, wherein the physical storage system comprises multiple storage devices, wherein each entry in the logical storage table further includes a device number indicating the storage device including the associated physical chunk, wherein the associated physical chunk is located at a position corresponding to the physical number in the storage device.

36. The article of manufacture of claim 35, wherein each storage device comprises a RAID array and wherein the device number indicates the RAID array including the associated physical chunk.

37. The article of manufacture of claim 34, wherein the physical chunk size is selected such that the physical storage and logical storage tables will not exceed a predetermined size.

38. A computer useable data transmission medium including data structures for use by a storage controller for mapping logical blocks to physical storage blocks, comprising:

information on a sequence of logical chunks, wherein each logical chunk defines a plurality of contiguous logical blocks in a logical storage space;

information on a sequence of physical chunks that define a plurality of contiguous physical storage blocks in a RAID array;

information on an association of logical chunks to physical chunks, wherein each logical chunk in the sequence of logical chunks defining the logical storage space is associated with one physical chunk in the RAID array, and wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, wherein at least two logical chunks in the logical volume are located in separate RAID arrays.

39. A computer useable data transmission medium including data structures for use by a storage controller for mapping logical blocks to physical storage blocks, comprising:

information on a sequence of logical chunks, wherein each logical chunk defines a plurality of contiguous logical blocks in a logical storage space;

information on a sequencing of physical chunks that define a plurality of contiguous physical storage blocks in a physical storage system;

information on an association of logical chunks to physical chunks, wherein each logical chunk in the sequence of logical chunks defining the logical storage space is associated with one physical chunk in the physical storage system, and wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, wherein the physical chunk size is a multiple of a stripe size.

40. The computer useable transmission medium of claim 39, wherein the physical chunk size is further selected such that a storage space in the RAID array is a multiple of the physical chunk size.

41. A computer useable data transmission medium including data structures for use by a storage controller for mapping logical blocks to physical storage blocks, comprising:

information on a sequence of logical chunks wherein each logical chunk defines a plurality of contiguous logical blocks in a logical storage space;

information on a sequence of physical chunks that define a plurality of contiguous physical storage blocks in a physical storage system;

information on an association of logical chunks to physical chunks, wherein each logical chunk in the sequence of logical chunks defining the logical storage space is associated with one physical chunk in the physical storage system, and wherein contiguous logical chunks are capable of being associated with non-contiguous physical chunks, wherein the logical chunk size is selected such that the logical storage space is a multiple of the logical chunk size.

42. The computer useable transmission medium of claim 41, wherein the physical storage system comprises multiple storage devices, wherein each entry in the logical storage table further includes a device number indicating the storage device including the associated physical chunk, wherein the associated physical chunk is located at a position corresponding to the physical number in the storage device.

43. The computer useable transmission medium of claim 42, wherein each storage device comprises a RAID array and wherein the device number indicates the RAID array including the associated physical chunk.