DATA STORAGE ARRAY SCALING METHOD AND SYSTEM WITH MINIMAL DATA MOVEMENT
A method for rearranging data blocks in a data storage system when adding new storage devices to create an expanded data storage system. A temporary configuration is selected for which the exchange of one or more data blocks between the temporary configuration and the source configuration produces the destination configuration before identifying and exchanging data blocks between the temporary configuration and the source configuration to produce the destination configuration. A single data element transfer chain embodiment provides superior performance in an embodiment that maintains (does not reduce) the source array data storage efficiency at the destination array after scaling. When adding a single new device to an existing array, the required data movement is minimized and does not exceed the capacity of the new device.
1 - 20 . (canceled)
21 . A method for rearranging data blocks in a data storage system including N coupled storage devices having a source data element configuration and a source data storage efficiency E S , when adding M coupled storage devices to create an expanded data storage system including (N+M) coupled storage devices having a destination data storage efficiency E D , wherein M and N are positive integers, the method comprising the unordered steps of:
selecting a destination data element configuration for the (N+M) coupled storage devices that provides the destination data storage efficiency E D , wherein the destination data storage efficiency E D does not exceed the source data storage efficiency E S ;
selecting a temporary data element configuration for the M coupled storage devices for which the exchange of one or more data blocks between the temporary data element configuration and the source data element configuration produces the destination data element configuration
identifying the data blocks that can be exchanged between the temporary data element configuration and the source data element configuration to produce the destination data element configuration as a chain of data blocks, said data block chain being created by executing for each integer value of i from 1 to N, performing:
if the ith data element of the source data element configuration is equal to the ith data element of the destination configuration, proceed to the next ith data element;
for each integer value of j from (N+1) to (N+M), performing:
if the jth data element of the destination data element configuration is not equal to the ith data element of the source data element configuration, proceed to the next jh data element;
setting the jth data element of the temporary data element configuration equal to the ith data element of the destination data element configuration;
identifying said jth data element in the source data and the jth data element in the temporary data element configuration as exchangeable;
for each integer value of k from (N+1) to (N+M), performing:
if the kth data element of the temporary data element configuration was set in a previous step, proceed to the next kh data element;
setting the kth data element of the temporary data element configuration equal to the kth data element of the destination data element configuration; and
exchanging the identified data blocks between the temporary data element configuration and the source data element configuration to produce the destination data element configuration, said exchange being performed by:
accessing the chain of data blocks between the temporary data element configuration and the source data element.
22 . A data storage system comprising:
N coupled storage devices including a source data element configuration and a source data storage efficiency E S where N is a positive integer; and
program means for rearranging data blocks when adding M coupled storage devices to create an expanded data storage system including (N+M) coupled storage devices having a destination data element configuration and a destination data storage efficiency E D , wherein M is a positive integer, including:
first program means for selecting a destination data element configuration for the (N+M) coupled storage devices that provides the destination data storage efficiency E D ,
second program means selecting a temporary data element configuration for the M coupled storage devices for which the exchange of one or more data blocks between the temporary data element configuration and the source data element configuration produces the destination data element configuration,
third program means for identifying the data blocks that can be exchanged between the temporary data element configuration and the source data element configuration to produce the destination data element configuration, and
fourth program means for exchanging the identified data blocks between the temporary data element configuration and the source data element configuration to produce the destination data element configuration having the destination data storage efficiency E D , wherein the destination data storage efficiency F0 does not exceed the source data storage efficiency E S ;
fifth program means for initiating operation of the data storage system under the control of a host system to store and retrieve data before completion of the data block rearrangement and identifying a single chained move of data blocks between the temporary data element configuration and the source data element configuration for producing the destination data element configuration having the destination data storage efficiency E D by repeating, for each integer value of i from 1 to M, the steps of:
if the ith data element of the source data element configuration is equal to the ith data element of the destination data element configuration, doing nothing; otherwise
for each integer value of j from (N+1) to (N+M), performing the steps of:
if the jth data element of the destination data element configuration is not equal to the ith data element of the source data element configuration, doing nothing; otherwise
setting the jth data element of the temporary data element configuration equal to the ith data element of the destination data element configuration;
sixth program means for performing the single chain of data block exchanges between the temporary data element configuration and the source data element configuration to produce the destination data element configuration having the destination data storage efficiency E D by repeating, for each integer value of k from (N+1) to (N+M), the steps of
if the kth data element of the temporary data element configuration was set in a previous step, doing nothing; otherwise
setting the kth data element of the temporary data element configuration equal to the kth data element of the destination data element configuration;
seventh program means for repeating, for each integer values of i from 1 to M, the steps of
if the ith data element of the source data element configuration is equal to the ith data element of the destination data element configuration, doing nothing; otherwise
for each integer value of j from (N+1) to (N+M), performing the steps of:
if the jth data element of the destination data element configuration is not equal to the ith data element of the source data element configuration, doing nothing; otherwise
identifying the ith data block of the source data element configuration for exchange with the jth data block of the temporary data element configuration.
23 . An article of manufacture for use in a data storage system including N coupled storage devices having a source data element configuration and a source data storage efficiency E S for rearranging data blocks when adding M coupled storage devices to create an expanded data storage system including (N+M) coupled storage devices having a destination data element configuration and as destination data storage efficiency E D , wherein M and N are positive integers, the article of manufacture comprising:
a computer readable storage medium;
a computer program code embodiment in the medium that causes the data storage system to select a destination data element configuration for the (N+M) coupled storage devices that provides the destination data storage efficiency E D ;
a computer program code embodiment in the medium that causes the data storage system to select a temporary data element configuration for the M coupled storage devices for which the exchange of one or more data blocks between the temporary data element configuration and the source data element configuration produces the destination data element configuration;
a computer program code embodiment in the medium that causes the data storage system to initiate operation under the control of a host system to store and retrieve data before completion of the data block exchanges and to identify a single chained move of data blocks between the temporary data element configuration and the source data element configuration for producing the destination data element configuration having the destination data storage efficiency E D ;
a computer program code embodiment in the medium that causes the data storage system to perform the single chain of data block exchanges between the temporary data element configuration and the source data element configuration to produce the destination data element configuration having the destination data storage efficiency E D ;
a computer program code embodiment in the medium that causes the data storage system to identify the data blocks that can be exchanged between the temporary data element configuration and the source data element configuration to produce the destination data element configuration; and
a computer program code embodiment in the medium that causes the data storage system to exchange the identified data blocks between the temporary data element configuration and the source data element configuration to produce the destination data element configuration having the destination data storage efficiency E D wherein the destination data storage efficiency E D does not exceed the source data storage efficiency E S .