Method and apparatus for expanding a virtual storage device

• US 8,656,131 B2
• Filed: 02/02/2009
• Issued: 02/18/2014
• Est. Priority Date: 10/31/2008
• Status: Active Grant

• Current Assignee: Dot Hill Systems Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Dot Hill Systems Corporation (Seagate Technology Holdings Plc)
• Inventors: Wicklund, Thomas George
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Eun, Stella
• Application Number:
  US12/363,870
• Publication Number:
  US 20100115210A1
• Time in Patent Office: 1,842 Days
• Field of Search: 711/170
• US Class Current: 711/170
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0632 by initialisation or re-initialisation of storage systems
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The present invention provides for the expansion of a virtual storage device. Expansion of the virtual storage device includes adding one or more additional storage device units to an existing virtual storage device. Blocks or strips included in an added storage device unit are assigned addresses, to allow the added storage capacity to be accessed immediately. In order to reestablish a pattern of data storage addresses from the original storage device units of the pre-expanded virtual storage device across all of the storage device units of the post-expanded virtual storage device, temporary storage is provided. In particular, as a strip of data is relocated to its proper post-expand location, the data occupying that location is placed in a temporary storage buffer. Data in the temporary storage buffer is then written to the proper post-expand location for that data, with displaced data being written to a second temporary storage buffer.

Claims

1. A method for expanding a virtual storage device, comprising:

expanding the virtual storage device that includes N storage device units by adding M storage device units, wherein each of the N storage device units and the M storage device units have B strips available for data storage, wherein each of the B strips in the N storage device units are assigned a logical address according to an initial mapping function, wherein data in the M storage device units is not required to be initialized, wherein data stored in the B strips in the N storage device units have an original physical location corresponding to the initial mapping function, and wherein each of the B strips in the initial mapping function are arranged in the same order as the B strips in the M storage device units;

assigning a logical address to each of the B strips in the M storage device units according to a new storage device mapping function, wherein the logical addresses assigned to the B strips in the M storage device units are sequentially concatenated to the highest logical address in the initial mapping function;

identifying by logical address in the initial mapping function each strip in each of the (N+M)×

B strips available for data storage;

assigning a new logical address to each of the B strips in the combined N+M storage device units according to a final mapping function;

assigning a first status value to each strip that has a location in the virtual storage device that does not conform to the final mapping function, wherein all strips except the first N strips of the initial mapping function and the last strip of the new storage device mapping function have the first status value;

assigning a second status value to each strip that has a location in the virtual storage device that conforms to the final mapping function, wherein the first N strips of the initial mapping function and the last strip of the new storage device mapping function have the second status value, wherein data in strips having the second status value are not copied elsewhere while expanding the virtual storage device, wherein strips having the second status value always maintain the second status value while expanding the virtual storage device;

after assigning first and second status values, selecting a first strip associated with the first status value, wherein the first strip associated with the first status value is the first strip in the new storage device mapping function;

identifying the logical address of the selected first strip, wherein the logical address of the selected first strip is the address of the first strip in the new storage device mapping function;

determining a destination location for the selected first strip, wherein the destination location for the selected first strip is determined by applying the logical address of the selected first strip to the final mapping function;

writing data in a second strip occupying the destination location for the selected first strip to a first temporary storage buffer, wherein the data in the second strip is associated with a second logical address, wherein the first temporary storage buffer is separate from the virtual storage device; and

writing data stored in the original location of the selected first strip to the destination location for the selected first strip, wherein the destination location for the selected first strip conforms to the final mapping function.

2. The method of claim 1, further comprising:

determining a destination location for the second strip, wherein the destination location for the second strip is determined by applying the second logical address to the final mapping function;

writing data stored in the original location of a third strip occupying the destination location for the second strip to a second temporary storage buffer, wherein the second temporary storage buffer is separate from the virtual storage device; and

writing the data from the second strip stored in the first temporary storage buffer to the destination location for the second strip, wherein the destination location for the second strip conforms to the final mapping function.

3. The method of claim 2, further comprising:

determining a destination location for the third strip, wherein the destination for the third strip is determined by applying the logical address of the third strip to the final mapping function;

writing data stored in an original location of a fourth strip occupying the destination location for the third strip to the first temporary storage buffer; and

writing the data from the third strip stored in the second temporary storage buffer to the destination location for the third strip, wherein the destination location for the third strip conforms to the final mapping function.

4. The method of claim 3, further comprising:

given data for a Kth strip stored in a first one of two temporary storage buffers, determining a destination location for the Kth strip, wherein the destination location for the Kth strip is determined by applying the logical address of the Kth strip to the final mapping function;

writing data stored in an original location of a K+Ith strip occupying the destination location for the Kth strip to a second one of two temporary storage buffers; and

writing the data from the Kth strip stored in the first one of two temporary storage buffers to the destination location for the Kth strip, wherein the destination location for the Kth strip conforms to the final mapping function.

5. The method of claim 2, further comprising:

after writing data from the first temporary storage buffer, determining a destination location for a strip stored the temporary storage buffer; and

in response to determining that the destination location for the strip stored in the second temporary storage buffer is occupied by a strip associated with the second value in a data moved array, scanning the data moved array to determine whether a Jth strip is associated with the first status value.

6. The method of claim 5, further comprising:

in response to determining that a Jth strip is associated with the first status value, selecting the Jth strip;

identifying the logical address for the selected Jth strip;

determining a destination location for the selected Jth strip, wherein the destination location is determined by applying the logical address for the selected Jth strip to the final mapping function;

writing data in a Kth strip occupying the destination location for the selected Jth strip to the first one of the first and second temporary storage buffers, wherein the data stored in the destination location for the selected Jth strip is associated with a Kth logical address; and

writing data stored in the original location of the Jth strip to the destination location for the selected Jth strip, wherein the destination location for the selected Jth strip conforms to the final mapping function.

7. The method of claim 1, further comprising:

reading or writing data from a host device by identifying a logical address associated with the data being read or written;

determining the status value associated with the identified logical address;

in response to determining that the first status value is associated with the identified logical address, reading or writing that data at the location determined by applying the initial mapping function if the identified logical address is within the first N×

B strips or the new storage device mapping function if the identified logical address is within the final M×

B strips; and

in response determining the second status value is associated with the identified logical address, reading or writing the data at the location determined by applying the identified logical address to the final mapping function.

8. The method of claim 1, further comprising:

creating a redundancy information coverage array, wherein the redundancy information coverage array includes;

an identification of each stripe in the virtual storage device; and

for each of the identified stripes, a first or second redundancy information value, wherein the first redundancy information value indicates that redundancy information for an associated stripe protects only those strips from the original N storage device units included in the associated stripe, and wherein the second redundancy information value indicates that redundancy information for an associated stripe protects all the strips of the N+M storage device units included in the associated stripe.

9. The method of claim 8, wherein the redundancy information coverage array is updated to protect all strips of the N+M storage device units whenever data is written to a strip contained on one of the M storage device units.

10. The method of claim 1, further comprising:

creating a data moved array; and

setting the status value associated with the first strip equal to the second status value.

11. A data storage system, comprising a plurality of storage device units comprising N original storage device units and M new storage device units;

a controller interconnected to the plurality of storage device units, including;

memory, including;

executable instructions for performing control and mapping functions;

a data moved array in which each available strip in a virtual storage device is identified, wherein the virtual storage device comprises the plurality of storage device units; and

a final mapping function for determining a location of a stripe of data in the virtual storage device, and

a redundancy information array in which each stripe in the data storage system is identified, and wherein for each stripe a redundancy information value is contained in the redundancy information coverage array indicating whether all of the strips associated this stripe are protected by redundancy information;

wherein for each of the identified strips a status value is contained in the data moved array indicating whether a location of each of the identified strips conforms to the final mapping function, wherein the status values initially indicate the first N strips and the last strip in the data moved array have a location that conforms to the final mapping function, wherein data in the M new storage device units is not required to be initialized.

12. The system of claim 11, further comprising:

an interface configured to interconnect the data storage system to a host device.

13. The system of claim 12, wherein each of the N and M storage device units includes B strips.

14. The system of claim 11, wherein the memory further includes:

a first temporary storage buffer; and

a second temporary storage buffer.

15. The system of claim 11, wherein the memory includes blocks located on a virtual storage device.

16. The system of claim 11, wherein the executable instructions for performing control and mapping functions include:

an initial mapping function for determining a location of a strip of data associated with a first status value in the data moved array on the N original storage device units included in the plurality of storage device units; and

a new storage device mapping function for determining a location of a strip of data associated with a first status value in the data moved array on the M new storage device units included in the plurality of storage device units, wherein the new storage device mapping function assigns logical addresses to the strips in the M storage device units, wherein the logical addresses assigned to the strips in the M storage device units are sequentially concatenated to a highest logical address in the initial mapping function, wherein each of the strips in the M storage device units are represented in the new storage device mapping function in the same order as in the M storage device units;

wherein the final mapping function determines the location of strips of data associated with a second status value in the data moved array on any of the N+M storage device units, wherein strips of data associated with the second status value have a different logical address in the final mapping function than at least one of the initial mapping function and the new storage device mapping function.

17. A method for restriping a virtual data storage device, comprising:

mapping N original storage device units according to an initial mapping function;

mapping M new storage device units according to a new disk mapping function, wherein the new disk mapping function maps the M new storage device units sequentially concatenated to the N original storage device units, wherein data in the M new storage device units is not required to be initialized, wherein each of the strips in the M new storage device units are represented in the new disk mapping function in the same order as in the M new storage device units;

associating a first status value or a second status value with each strip included in said N+M storage device units, wherein the first status value indicates that an associated strip needs to be relocated to conform to a final mapping function, wherein all strips except the first N strips of the initial mapping function and the last strip of the new storage device mapping function have the first status value;

wherein the second status value indicates that an associated strip does not need to be relocated to conform to the final mapping function, wherein the first N strips of the initial mapping function and the last strip of the new disk mapping function have the second status value, wherein data in strips having the second status value are not copied elsewhere while expanding the virtual storage device, wherein strips having the second status value always maintain the second status value while expanding the virtual storage device;

identifying a first strip associated with the first status value, wherein the first strip associated with the first status value is the first strip in the new disk mapping function;

identifying a second strip occupying a destination location of the first strip according to the final mapping function;

moving the second strip to a first temporary storage buffer, wherein the first temporary storage buffer is separate from the virtual storage device; and

moving the first strip to the destination location of the first strip.

18. The method of claim 17, further comprising:

associating the second status value with the first strip;

identifying a third strip occupying a destination location of the second strip according to the final mapping function;

moving the third strip to a second temporary storage buffer;

wherein the second temporary storage buffer is separate from the virtual storage device; and

moving the second strip from the first temporary storage buffer to the destination location of the second strip.