Managing data migration

• US 20060129771A1
• Filed: 12/14/2004
• Published: 06/15/2006
• Est. Priority Date: 12/14/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Verma, Akshat, Dasgupta, Koustuv, Jain, Rohit, Sharma, Upendra
• Application Number:
  US11/011,861
• Publication Number:
  US 20060129771A1
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for performing a data migration task on an on-line data storage system comprises computing a migration utility, which is a function of the expected time taken to complete the data migration task and generating migration requests for performing the data migration task, where the data migration task is divided into sub-tasks and a migration request is generated for each sub-task. Next determining a migration deadline for performing the data migration; assigning reward values to customer storage requests; assigning reward values to the migration requests. Then scheduling the migration requests and the customer storage requests to maximize total rewards earned and executing the schedule in order to perform the data migration task

Claims

1. A method of managing a data migration task for an data storage system, wherein the method comprises:

generating a schedule comprising data migration requests for performing sub-tasks of the data migration task and customer (input/output) I/O storage requests for performing customer storage operations, wherein the schedule is generated with reference to migration utility requirements and client performance requirements; and

executing the schedule of requests in order to perform the data migration task.

2. The method of claim 1, wherein the schedule is generated such that the rate of data migration is adapted in response to received customer I/O storage requests and the data migration requests, thereby achieving a balance between the migration and customer I/O storage requests.

3. The method of claim 1, wherein the schedule is generated such that the rate of data migration is adapted in response to received customer I/O storage requests and the data migration requests, thereby achieving the migration utility requirements while maximizing rewards earned by the data storage system.

4. The method of claim 3, further comprising:

assigning reward values to individual customer storage requests; and

assigning reward values to individual migration requests, which constitute the data migration task; and

comparing the rewards of the data migration requests with customer storage requests in order to maximize said rewards.

5. The method of claim 1, wherein the schedule is generated such that the rate of data migration is adapted in response to received customer I/O storage requests and the data migration requests, thereby achieving the migration utility requirements while maximizing customer storage performance.

6. A method of performing a data migration task on an on-line data storage system, wherein the method comprises:

computing a-migration utility which is a function of the time taken to complete the data migration task;

generating migration requests for performing the data migration task, wherein the data migration task is divided into sub-tasks and a migration request is generated for each sub-task;

determining a migration deadline for performing the data migration;

assigning reward values to received customer storage requests, which reward values are representative of revenue generated by performing the customer storage requests;

assigning reward values to the migration requests, which reward values are representative of revenue generated by performing the data migration task and are based on a reward distribution of expected customer storage requests, available storage capacity, number of remaining migration requests, and the migration utility;

scheduling the migration requests and the customer storage requests in such a manner to maximize total rewards earned; and

executing the schedule of requests in order to perform the data migration task.

7. The method of claim 6, wherein the data migration task is stipulated to be completed within a deadline and the determining step sets the migration deadline to the stipulated deadline.

8. The method of claim 7, wherein the migration utility function is a step function of the form:

$U_m<br><br>\left(t\right)=\{\begin{array}{cc}U& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\le <br><br>T_{\max }\\ 0& \mathrm{otherwise}\end{array}$

where U is the rewards earned by meeting the deadline T_max.

9. The method of claim 6, wherein there is no stipulated deadline for completion of the data migration task and the determining step determines the migration deadline as an optimal target deadline that maximizes the total rewards expected to be earned.

10. The method of claim 9, wherein the migration utility function is non-increasing with increase in delay.

11. The method of claim 10, wherein the optimal target deadline T_opt is computed in accordance with:

$\frac{B_m}{T_{\mathrm{opt}}}=C_m$ ${<br><br>\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>U_m<br><br>\left(t\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>T}<br><br>}_{T_{\mathrm{opt}}}=R_m-R_l,$

where R_l denotes a long term average reward of customer storage requests that have reward less than R_m, where R_m denotes a potential reward to be assigned to a migration request, B_m is a bandwidth required for the data migration task to meet a deadline, C_m average bandwidth required for the data migration task to meet the deadline, U_m(t) is a migration utility function.

12. The method of claim 8, wherein the step of assigning rewards to migration requests is performed in accordance with:

$R_m<br><br>\left(t\right)=\{\begin{array}{cc}<br><br>0& <br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{U}{N_m^t}<<br><br>R_m\\ <br><br>R_m& <br><br>\mathrm{otherwise}\end{array},$

where R_m(t) is the reward assigned to a migration request at time t, N_m^t is a number of migration requests remaining at time t, R_m is a potential reward given by

$\mathrm{\lambda <br><br>}<br><br>{\int <br><br>}_{R_m}^{\mathrm{\infty <br><br>}}<br><br>c_r<br><br>p_r\le <br><br>C-C_m$

where c_r is an expected capacity used by customer storage requests with reward r, λ

is an expected number of customer storage requests present at any given time, p_r is a probability that a customer storage request has reward r, C is total available storage capacity of the data storage system, and C_m denotes average bandwidth required for the data migration task to meet the migration deadline.

13. The method of claim 6, wherein the deadline for migration is completed within a predefined deadline and the determining step sets the migration deadline to the predefined deadline.

14. The method of claim 13, wherein the step of assigning rewards to migration requests is performed in accordance with:

$R_m<br><br>\left(t\right)=\frac{U}{N_m^t}$

where R_m(t) is a reward assigned to a migration request at time t, N_m^t is a number of migration requests remaining at time t, R_m is a potential reward given by

$\mathrm{\lambda <br><br>}<br><br>{\int <br><br>}_{R_m}^{\mathrm{\infty <br><br>}}<br><br>c_r<br><br>p_r\le <br><br>C-C_m$

where c_r is an expected capacity used by customer storage requests with reward r, λ

is an expected number of customer storage requests present at any given time, p_r is a probability that a customer storage request has reward r, C is total available storage capacity of the data storage system, C_m denotes average bandwidth required for the data migration task to meet the migration deadline, and U is the reward earned by meeting the deadline.

15. The method of claim 6, wherein the reward distribution of expected customer storage requests is based on long term averages of the customer storage requests.

16. The method of claim 15, wherein the method further comprises:

adapting the assigned migration rewards with a confidence factor to correct any errors in prediction of the long term averages.

17. The method of claim 6, wherein the method further comprises:

recomputing the migration deadline and migration rewards after a chosen interval of time.

18. The method of claim 6, wherein the scheduling step further comprises:

admitting those migration requests for scheduling that have reward per unit capacity greater than the customer storage request currently under consideration for scheduling.

19. A method as claimed in claim 6, wherein the method utilizes both long term and short term forecasts of the expected customer storage requests to schedule the migration requests so as to ensure that said migration deadline is met and that the migration is adjusted to cope with bursts in traffic of customer storage requests.

20. A data storage system adapted for managing a data migration task, wherein the system comprises:

means for generating a schedule comprising data migration requests for performing sub-tasks of the data migration task and customer (input/output) I/O storage requests for performing customer storage operations, wherein the schedule is generated with reference to migration utility requirements and client performance requirements; and

means for executing the schedule of requests in order to perform the data migration task.

21. An on-line data storage system for performing customer storage operations and adapted for performing a data migration task, wherein the system comprises:

means for computing a migration utility which is a function of the time taken to complete the data migration task;

means for generating migration requests for performing the data migration task, wherein the data migration task is divided into sub-tasks and a migration request is generated for each sub-task;

means for determining a migration deadline for performing the data migration;

means for assigning reward values to received customer storage requests;

which reward values are representative of revenue generated by performing the customer storage requests;

means for assigning reward values to the migration requests, which reward values are representative of revenue generated by performing the data migration task and are based on a reward distribution of expected customer storage requests, available storage capacity, number of remaining migration requests, and the migration utility;

means for scheduling the migration requests and the customer storage requests in such a manner to maximize total rewards earned; and

means for executing the schedule of requests in order to perform the data migration task.

22. A computer program product for managing a data migration task for an data storage system, the computer program product comprising computer software recorded on a computer-readable medium for performing a method comprising:

generating a schedule comprising data migration requests for performing sub-tasks of the data migration task and customer (input/output) I/O storage requests for performing customer storage operations, wherein the schedule is generated with reference to migration utility requirements and client performance requirements.

23. A computer program product for performing a data migration task on an online data storage system, the computer program product comprising computer software recorded on a computer-readable medium for performing a method comprising:

computing a migration utility which is a function of the time taken to complete the data migration task;

generating migration requests for performing the data migration task, wherein the data migration task is divided into sub-tasks and a migration request is generated for each sub-task;

determining a migration deadline for performing the data migration;

assigning reward values to received customer storage requests;

which reward values are representative of revenue generated by performing the customer storage requests

assigning reward values to the migration requests, which reward values are representative of revenue generated by performing the data migration task and are based on a reward distribution of expected customer storage requests, available storage capacity, number of remaining migration requests, and the migration utility; and

scheduling the migration requests and the customer storage requests in such a manner to maximize total rewards earned.