Computer data storage system with migration plan generator

• US 6,381,619 B1
• Filed: 09/13/1999
• Issued: 04/30/2002
• Est. Priority Date: 09/13/1999
• Status: Expired due to Term

• Current Assignee: QNAP Systems Incorporated
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Golding, Richard Andrew, Narayanan, Dushyanth, Borowsky, Elizabeth Lynn
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): TRUONG, CAM Y T
• Application Number:
  US09/394,221
• Time in Patent Office: 960 Days
• Field of Search: 707/200-205, 707/10, 711/170, 711/173
• US Class Current: 711/170
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A data storage system is provided in which a migration plan generates migration plans for reaching a goal configuration from an initial configuration in a predetermined period of time. The migration plan initially makes terminal moves until no further terminal moves can be made. A shunt move is then made based on reducing the contention (the total size of the data stores that need to be moved onto a particular data stores device divided by the amount of excess capacity on the data storage device). The shunt is selected to lead to the lowest contention for the data storage system. Subsequently, the migration plan returns to making terminal moves to develop a migration plan. Further migration plans are provided.

Claims

1. A data storage system comprising:

a plurality of data storage devices;

a plurality of data stores, each of said plurality of data stores capable of binding to one of said plurality of data storage devices;

a control connected to said plurality of data storage devices for moving one of said plurality of data stores among said plurality of storage devices from an initial configuration to a goal configuration; and

a migration plan generator connected to said control and responsive to said initial configuration and said goal configuration to provide a migration plan to cause said control to move said one of said plurality of data stores from said initial configuration to said goal configuration, said migration plan generator includes;

a migration planner for providing a migration plan for moving said one of said plurality of data stores from a first of said plurality of data storage devices in said initial configuration to a second of said plurality of data storage devices to said goal configuration in a first terminal move and

said migration planner for providing said migration plan for moving said first of said plurality of said data stores from said first of said plurality of data storage devices to an intermediate data storage device in said plurality of data storage devices in a shunt move when no terminal moves are possible whereby said first of said plurality of data stores is moved to one of said plurality of data storage devices which is not part of the goal configuration before moving to said second of said plurality of data storage devices to said goal configuration.

2. The data storage system as claimed in claim 1 wherein:

said migration planner is capable of providing said migration plan in which said shunt move is a plan selected from a group consisting of Greedy, Cycle, Hillclimbing, Simulated Annealing, and a combination thereof.

3. The data storage system as claimed in claim 1 including:

a data storage network connected to said plurality of data storage devices; and

a plurality of hosts connected to said data storage network.

4. The data storage system as claimed in claim 1 wherein:

said migration planner capable of providing said migration plan for moving at least one of said plurality of data stores to and from said plurality of data storage devices is a plan selected from a group consisting of Simple, Greedy Simple, Greedy, Cycle, Hillclimbing, Simulated Annealing, Other, and a combination thereof.

17. The data storage system as claimed in claim 3 wherein:

said migration planner uses information to provide the migration plan selected from a group consisting of;

access patterns to said data storage devices changing;

service requirements of the access changing;

number of said data stores changing;

new data storage devices being added or subtracted; and

said data storage devices failing or approaching failure.

18. The data storage system as claimed in claim 3 wherein:

said migration planner uses information to provide the migration plan selected from a group consisting of;

capacity constraints of said intermediate data storage device; and

minimizing migration load on the data storage system.

5. A data storage system comprising:

a plurality of data storage devices having constraints;

a plurality of data stores having constraints, each of said plurality of data stores capable of binding to one of said plurality of data storage devices when the constraints of said plurality of data storage devices are met;

a control connected to said data storage devices for moving said plurality of data stores among said plurality of data storage devices from an initial configuration to a goal configuration while meeting the constraints of each of said plurality of data storage devices;

a migration plan generator connected to said control responsive to said initial configuration and said goal configuration to provide a heuristic migration plan to cause said control to move said plurality of data stores from said initial configuration data storage devices to said goal configuration data storage devices, said migration plan generator includes;

a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in terminal moves selected from a group consisting of Random Selection, Preset Ordering, a Function of each of said plurality of data stores, and a combination thereof until no terminal move can be made when a shunt move will be made which leads to the lowest contention for said plurality of data storage devices.

6. The data storage system as claimed in claim 5 wherein:

said migration planner capable of providing said migration plan for moving said plurality of data stores among said plurality of data storage devices in terminal moves until no terminal move can be made when a shunt move will be made that leads to the lowest contention for the sum of said plurality of data storage devices, and then said migration plan continues to make terminal moves.

7. The data storage system as claimed in claim 5 wherein:

said migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in terminal moves until no terminal move can be made when a shunt move is found by finding cycles with small stores Greedily and then shunting the largest data store in the cycle to any of said plurality of data storage devices for which the constraints can be met.

8. The data storage system as claimed in claim 5 wherein:

said migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in selected moves that minimize the global contention of the sum of said plurality of data storage devices.

9. The data storage system as claimed in claim 5 wherein:

said migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in selected moves based on Simulated Annealing using a contention metric as an energy function.

10. The data storage system as claimed in claim 5 wherein:

said migration plan generator includes a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in selected moves while switching from plans selected from a group consisting of Simple, Greedy Simple, Greedy, Cycle, Hillclimbing, Simulated Annealing, Other, and a Meta plan.

11. The data storage system as claimed in claim 5 including:

a data storage network connected to said plurality of data storage devices; and

a plurality of hosts connected to said data storage network.

12. The data storage system as claimed in claim 5 wherein:

said migration plan generator includes a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in moves which use the lowest energy plan where the sequence of said moves is proportional to the energy of said plan.

13. The data storage system as claimed in claim 5 wherein:

said migration plan generator includes a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in moves which use genetic programming on a population of said plans from a group consisting of Greedy, Cycle, Hillclimbing, and Simulated Annealing plans to determine the migration plan.

14. The data storage system as claimed in claim 5 wherein:

said migration plan generator includes a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in moves which use a graph-theoretical heuristic to determine the moves.

15. The data storage system as claimed in claim 5 wherein:

said migration plan generator includes a migration planner capable of providing a migration plan for moving said plurality of data stores among said plurality of data storage devices in moves which will be designated as a “

fail”

when a migration plan is not generated within a predetermined period of time.

16. The data storage system as claimed in claim 5 wherein:

said plurality of data storage devices have constraints selected from a group consisting of capacity, bandwidth, movement rate, and a combination thereof; and

said plurality of data stores has capacity constraints.

19. The data storage system as claimed in claim 5 wherein:

said migration planner uses information to provide the migration plan selected from a group consisting of;

access patterns to said data storage devices changing;

service requirements of the access changing;

number of said data stores changing;

new data storage devices being added or subtracted; and

said data storage devices failing or approaching failure.

20. The data storage system as claimed in claim 5 wherein:

said migration planner uses information to provide the migration plan selected from a group consisting of;

capacity constraints of said intermediate data storage device; and

minimizing migration load on the data storage system.

21. A data storage system comprising:

first, second, and third data storage devices;

a data store for binding to the first, second, and third data storage devices;

a control connected to said first, second, and third data storage devices for moving the data store among said storage devices from an initial configuration to a goal configuration; and

a migration plan generator connected to said control and responsive to said initial configuration and said goal configuration to provide a migration plan to cause said control to move said data store from said initial configuration to said goal configuration, said migration plan generator including;

a migration planner for providing a migration plan for moving said data store from said first data storage device in said initial configuration to said third data storage device to said goal configuration in a first terminal move and

a migration planner for providing a migration plan for moving said data store from said first data storage device in said initial configuration to said second data storage in a shunt move when the first terminal move is not possible before moving said data store to said third data storage device to said goal configuration in a second terminal move.

22. A data storage system comprising:

first, second, and third data storage devices having predetermined constraints;

a data store for binding to the first, second, and third data storage devices when the predetermined constraints are met;

a control connected to said first, second, and third data storage devices for moving the data store among said storage devices from an initial configuration to a goal configuration; and

a migration plan generator connected to said control and responsive to said initial configuration and said goal configuration to provide a heuristic migration plan to cause said control to move said data store from said initial configuration to said goal configuration, said migration plan generator including;

a migration planner for providing a migration plan for moving said data store from said first data storage device in said initial configuration to said third data storage device to said goal configuration in a first terminal move in an order based on an order selected from a group consisting of Random Selection, Preset Ordering, a Function of each of said plurality of data stores and

a migration planner for providing a migration plan for moving said data store from said first data storage device in said initial configuration to said second data storage in a shunt move which leads to the lowest contention for said plurality of data storage devices when the first terminal move is not possible before moving said data store to said third data storage device to said goal configuration in a second terminal move.