Method for virtual to physical mapping in a mapped compressed virtual storage subsystem

• US 5,778,411 A
• Filed: 09/18/1997
• Issued: 07/07/1998
• Est. Priority Date: 05/16/1995
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: Symbion Incorporated (Broadcom, Inc.)
• Inventors: Humlicek, Donald R., DeMoss, Robert A.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US08/933,327
• Time in Patent Office: 292 Days
• Field of Search: 711/4, 711/112, 711/203, 395/888
• US Class Current: 711/4
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11B 20/1252 for discontinuous data, e.g. digital information signals, computer programme data

Abstract

A method and corresponding controller apparatus for creating, updating and maintaining mapping information in a virtual mass storage subsystem. A request to manipulate a virtual block or cluster identifies a particular virtual block number. The virtual block number is mapped to a first physical block number by a direct calculation. A header data structure contained in the first physical block contains mapping information to locate other physical blocks associated with the virtual cluster. In addition to the header data structure, the first physical block contains a portion of the stored data for the corresponding virtual cluster. Additional physical blocks which stored the data of the virtual cluster are located from the mapping information in the header of the first physical block. The methods of the present invention provide improved performance and reduced buffer memory requirements in the virtual mass storage controller circuits of the subsystem as compared to prior approaches.

Claims

1. In a virtual mass storage subsystem having a plurality of physical storage blocks, a method for storing virtual clusters received from a host computer system in said physical storage blocks of said mass storage subsystem, said method comprising the steps of:

(a) mapping a virtual cluster number associated with a received virtual cluster to a first physical storage block number corresponding to a first physical storage block of a plurality of physical storage blocks corresponding to a physical cluster, wherein said mapping consists essentially of an arithmetic calculation devoid of memory table lookup functions;

(b) compressing said virtual cluster to generate a compressed physical cluster,

(c) identifying available physical storage blocks of said plurality of physical storage blocks in said physical cluster;

(d) storing a portion of said compressed physical cluster in said available physical storage blocks of said physical cluster wherein said available physical storage blocks includes said first physical storage block;

(e) determining whether a remaining portion of said compressed physical cluster can not be stored in said available physical storage blocks; and

(f) storing said remaining portion in additional physical storage blocks of another physical cluster.

2. The method of claim 1 wherein the step of identifying comprises the steps of:

reading said first physical storage block of said physical cluster to retrieve a header data structure therein; and

inspecting said header data structure to identify said available physical storage blocks in said physical cluster.

3. The method of claim 2, further comprising the step of:

updating said header data structure to reflect non-availability of said available physical storage blocks in said physical cluster in response to the step of storing said portion of said compressed physical cluster in said available physical storage blocks.

4. The method of claim 1 further comprising the step of:

providing a free block data structure in a memory associated with said mass storage subsystem, said free block data structure indicating an available status corresponding to each physical storage block in said mass storage subsystem.

5. The method of claim 4 wherein said free block data structure comprises an array of bits, wherein each bit corresponds to one of said physical storage blocks, and wherein one value of each bit indicates that the corresponding physical storage block is available and the other value of said each bit indicates that the corresponding physical storage block is unavailable.

6. The method of claim 4 further comprising the steps of:

(i) locating physical storage blocks which have a corresponding available status indication in said free block data structure; and

(ii) marking the available physical storage blocks located by operation of step (i) as unavailable in said free block data structure.

7. The method of claim 6 wherein said physical storage blocks are organized into a plurality of physical clusters, each of said physical clusters containing a predetermined number of said physical storage blocks, and wherein step (i) further comprises the steps of:

(i.1) locating physical storage blocks in the physical cluster which also contains said first physical storage block which have a corresponding available status indication in said free block data structure;

(i.2) determining that an insufficient number of physical storage blocks were located by operation of step (i.1) to permit storage of a header data structure and said virtual cluster; and

(i.3) locating, responsive to a determination that insufficient storage blocks were located by operation of step (i.2), additional physical storage blocks in physical clusters which do not contain said first physical storage block and which have a corresponding available status indication in said free block data structure.

8. The method of claim 7 further comprising the step of:

providing an overflow data structure in a memory associated with said mass storage subsystem, said overflow data structure indicating an overflow status corresponding to each physical cluster in said mass storage subsystem.

9. The method of claim 8 wherein said free block data structure comprises an array of bits, wherein each bit corresponds to one of said physical clusters, and wherein one value of each bit indicates that the corresponding physical cluster has an overflow status and the other value of said each bit indicates that the corresponding physical cluster does not have an overflow status.

10. The method of claim 8 further comprising the steps of:

setting, responsive to a determination that insufficient storage blocks were located by operation of step (i.2), the overflow status in said overflow data structure corresponding to the physical cluster which contains said first physical block; and

setting, responsive to locating additional physical storage blocks in physical clusters in step (i.3), the overflow status in said overflow data structure corresponding to each of said additional physical clusters located by operation of step (i.3).

11. In a virtual mass storage subsystem having a plurality of physical storage blocks, a method for retrieving virtual clusters previously stored in the physical storage blocks of said mass storage subsystem, said method comprising the steps of:

(a) receiving a request from a host computer system to retrieve a virtual cluster identified by a virtual cluster number;

(b) mapping said virtual cluster number to a first physical storage block number corresponding to a first physical storage block at which said virtual cluster was previously stored, wherein said mapping consists essentially of an arithmetic calculation to the exclusion of memory table lookup functions;

(c) reading the physical cluster containing said first physical storage block to retrieve a header data structure contained in said first physical storage block and having information regarding all physical storage blocks corresponding to said virtual cluster in said physical cluster;

(d) determining whether additional physical storage blocks need be read to retrieve the virtual cluster requested by said host computer system;

(e) skipping to step (h) responsive to a determination by step (d) that no additional physical storage blocks need be read;

f) determining, from said header data structure, additional physical storage block numbers corresponding to additional physical storage blocks used to store said virtual cluster and said header data structure;

(g) reading said additional physical storage blocks used to store said virtual cluster;

(h) decompressing compressed data contained in the read physical storage blocks to regenerate said virtual cluster; and

(i) returning said virtual cluster to said host computer system.

12. The method of claim 11 wherein said physical storage blocks are organized into a plurality of physical clusters, each of said physical clusters containing a predetermined number of said physical storage blocks,

wherein step (c) further includes a step of reading all physical storage blocks contained in the physical cluster which contains said first physical storage blocks, and

wherein step (g) further includes a step of reading all said additional physical storage blocks not contained in said physical cluster which contains said first physical storage block.

13. The method of claim 12 further comprising the step of:

providing an overflow data structure in a memory associated with said mass storage subsystem, said overflow data structure indicating an overflow status corresponding to each physical cluster in said mass storage subsystem.

14. The method of claim 13 wherein said overflow data structure comprises an array of bits, wherein each bit corresponds to one of said physical clusters, and wherein one value of each bit indicates that the corresponding physical cluster has an overflow status and the other value of said each bit indicates that the corresponding physical cluster does not have an overflow status.

15. The method of claim 13 wherein step (d) further comprises the steps of:

(d.1) determining that no additional physical storage blocks need be read responsive to a determination that the physical cluster containing said first physical storage block does not have an overflow status; and

(d.2) determining that additional physical storage blocks need be read responsive to a determination that the physical cluster containing said first physical storage block has an overflow status.

16. A compressed virtual storage subsystem for storage of a virtual cluster in said compressed virtual storage subsystem, said subsystem comprising:

at least one storage device containing a plurality of physical storage clusters, each of said plurality of physical storage clusters including a plurality of physical storage blocks;

a storage controller coupled to said at least one storage device and coupled to a host system for processing an 1/O write request received from said host system wherein said storage controller includes;

means for compressing data of said virtual cluster to generate a compressed cluster;

means for determining a required number of physical storage blocks to store said compressed cluster in said storage medium;

mapping means for calculating a physical cluster number from a virtual cluster number associated with said virtual cluster;

means for identifying available physical storage blocks in said desired physical storage cluster from information in a header portion of a first physical storage block of said physical storage cluster; and

means for storing said compressed cluster in the identified available physical storage blocks of said desired physical storage cluster.

17. The subsystem of claim 16 further comprising:

a memory having stored therein a free block data structure, said free block data structure including a stored indicator corresponding to an available status for each physical storage block in said mass storage subsystem.

18. The system of claim 16 further comprising:

a memory having stored therein an overflow data structure, said overflow data structure having an overflow status indicator corresponding to each physical cluster in said mass storage subsystem.

19. A compressed virtual storage subsystem for retrieval of a virtual cluster previously stored in said compressed virtual storage subsystem, said subsystem comprising:

at least one storage device containing a plurality of physical storage clusters, each of said plurality of physical storage clusters including a plurality of physical storage blocks;

a storage controller coupled to said at least one storage device and coupled to a host system for processing an I/O write request received from said host system wherein said storage controller includes;

mapping means for calculating a physical cluster number from a virtual cluster number associated with said virtual cluster;

means for identifying physical storage blocks in said desired physical storage cluster containing portions of said virtual cluster from information in a header portion of a first physical storage block of said physical storage cluster;

means for retrieving compressed data from the identified physical storage blocks of said desired physical storage cluster; and

means for decompressing the compressed data.

20. The subsystem of claim 19 further comprising:

a memory having stored therein a free block data structure, said free block data structure including a stored indicator corresponding to an available status for each physical storage block in said mass storage subsystem.

21. The system of claim 19 further comprising:

a memory having stored therein an overflow data structure, said overflow data structure having an overflow status indicator corresponding to each physical cluster in said mass storage subsystem.

22. In a compressed virtual storage subsystem having a storage medium consisting of a plurality of physical storage clusters each having a plurality of physical storage blocks, a method for storing a virtual cluster provided by an attached host system comprising the steps of:

compressing data of said virtual cluster to generate a compressed cluster;

determining a required number of physical storage blocks to store said compressed cluster in said storage medium;

mapping a virtual cluster number associated with said virtual cluster into a physical cluster number associated with a desired physical storage cluster wherein the mapping step consists essentially of arithmetic calculations devoid of memory lookup functions;

identifying available physical storage blocks in said desired physical storage cluster; and

storing said compressed cluster in the identified available physical storage blocks of said desired physical storage cluster.

23. The method of claim 22 further comprising the steps of:

determining that the identified available physical storage blocks are insufficient to store the entirety of said compressed cluster leaving a remaining portion of said compressed cluster;

identifying additional available physical storage blocks in another physical storage cluster; and

storing said remaining portion of said compressed cluster in said additional available physical storage blocks.

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

providing an overflow table structure having an entry for each of said plurality of physical storage clusters wherein said entry includes indicia that a corresponding physical storage cluster contains overflow blocks associated with a different physical storage cluster; and

marking an entry corresponding to said another physical storage cluster in said overflow table structure to indicate that said another physical storage cluster contains overflow blocks associated with said desired physical storage cluster.

25. The method of claim 24 wherein the step of identifying available physical storage blocks in said desired physical storage cluster includes the steps of:

determining whether the entry corresponding to said desired physical storage cluster in said overflow table structure indicates that said desired physical storage cluster contains overflow blocks associated with a different physical storage cluster;

determining whether said I/O request is for storage of an entire virtual cluster;

determining that all of said plurality of physical storage blocks of said desired physical storage cluster are available in response to the determination that said entry corresponding to said desired physical storage cluster in said overflow table structure indicates that said desired physical storage cluster contains no overflow blocks and the determination that said I/O request is for storage of an entire virtual cluster.

26. In a compressed virtual storage subsystem having a storage medium consisting of a plurality of physical storage clusters each having a plurality of physical storage blocks, a method for retrieving a compressed virtual cluster provided by an attached host system comprising the steps of:

mapping a virtual cluster number associated with said compressed virtual cluster into a physical cluster number associated with a desired physical storage cluster wherein the mapping step consists essentially of arithmetic calculations devoid of memory lookup functions;

reading said physical storage cluster wherein said physical storage cluster includes a header data structure in a first physical storage block of the plurality of physical storage blocks of said physical storage cluster and wherein;

determining from said header data structure which of said plurality of physical storage blocks correspond to said compressed virtual storage;

decompressing said virtual cluster from data stored in said plurality of physical blocks corresponding to said compressed virtual cluster; and

returning the decompressed virtual cluster to said host system.

27. The method of claim 26 further comprising the steps of:

determining whether additional physical storage blocks of another physical storage cluster correspond to said compressed virtual cluster,

wherein the step of decompressing further comprises the step of decompressing data stored in said additional physical storage blocks corresponding to said compressed virtual cluster.

28. The method of claim 27 further comprising the steps of:

inspecting an overflow table structure having an entry for each of said plurality of physical storage clusters to determine whether said physical storage cluster is associated with overflow blocks corresponding to another physical cluster, wherein each said entry includes indicia that a corresponding physical storage cluster contains overflow blocks associated with a different physical storage cluster; and

reading said overflow blocks associated with said physical storage cluster.