Automated optimal workload balancing during failover in share-nothing database systems

• US 8,326,990 B1
• Filed: 07/15/2005
• Issued: 12/04/2012
• Est. Priority Date: 07/15/2005
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Li, Qiang, Hu, Ron-Chung, Hsiung, HanCheng
• Primary Examiner(s): Bates, Kevin
• Assistant Examiner(s): Ma, Wing
• Application Number:
  US11/182,907
• Time in Patent Office: 2,699 Days
• Field of Search: 709/226, 709215-216, 714/714, 714/715
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Procedures and systems may be used for assigning data partitions to data-processing host computers, for example, to initially assign data partitions at the outset of a large data-processing job or during failover measures taken in response to a failed host in a share-nothing database management system (SN-DBMS). In one implementation, a method of managing exclusive access to a data partition within a database system assesses a first host and a second host that have exclusive access to a first and second data partition, respectively, within a database system. The method assigns exclusive access of the data partition to one of the first and second hosts based on factors that may include the processing powers of first and second the hosts, and on processing requirements (such as data quantity and data criticalness) for data on the first and second data partitions.

Claims

1. A method comprising:

calculating a first device assessment for a first computing device, wherein

the first device assessment is based at least in part on a first plurality of data portion assessments, and

each data portion assessment in the first plurality of data portion assessments comprises a weighted data quantity based at least in part on a product of;

a quantity of data stored in a respective data portion accessible by the first computing device, and

a weighting factor based at least in part on a type of data stored in the respective data portion accessible by the first computing device;

calculating a second device assessment for a second computing device, wherein

the second computing device is distinct from the first computing device,

the second device assessment comprises a weighted data quantity based at least in part on a second plurality of data portion assessments, and

each data portion assessment in the second plurality of data portion assessments is based at least in part on a product of;

a quantity of data stored in a respective data portion accessible by the second computing device, and

a weighting factor based at least in part on a type of data stored in the respective data portion accessible by the second computing device;

calculating a first task assessment for a first collection of data portions, wherein

the first task assessment is based at least in part on a third plurality of data portion assessments, and

each data portion assessment in the third plurality of data portion assessments is based at least in part on

a quantity of data stored in a respective data portion among the first collection of data portions, and

a weighting factor based at least in part on a type of data stored in the respective data portion among the first collection of data portions;

calculating a second task assessment for a second collection of data portions, wherein

the second collection of data portions is distinct from the first collection of data portions,

the second task assessment is based at least in part on a fourth plurality of data portion assessments, and

each data portion assessment in the fourth plurality of data portion assessments is based at least in part on

a quantity of data stored in a respective data portion among the second collection of data portions, and

a weighting factor based at least in part on a type of data stored in the respective data portion among the second collection of data portions;

selecting a target task, wherein the selecting the target task comprises comparing, using a processor, the first task assessment to the second task assessment;

selecting a target device, wherein the selecting the target device comprises comparing the first device assessment to the second device assessment; and

assigning the target task to be performed by the target device.

2. The method of claim 1, wherein the second computing device is a standby host.

3. The method of claim 1, wherein

the second computing device has exclusive access to a second data partition;

the first device assessment depends on a first processing power of the first computing device; and

the second device assessment depends on a second processing power of the second computing device.

4. The method of claim 3, wherein the first and second device assessments are normalized work loads (NWLs), the first and second processing powers are processing resource (PR) metrics, and the first and second task assessments are partition-weighted data quantities (PWDQ).

5. The method of claim 3, wherein the first processing power of the first computing device is indicative of a relative time for the first computing device to complete a standardized task.

6. The method of claim 1, wherein the calculating the first device assessment, the comparing the first device assessment to the second device assessment, and the assigning are performed in response to a failure of a third computing device to which the first collection of data portions was previously assigned.

7. The method of claim 1, wherein the first collection of data portions is a first unassigned data partition selected from a plurality of unassigned data partitions, and wherein the first unassigned data partition has a highest processing requirement among the plurality of unassigned data partitions.

8. The method of claim 7, further comprising, after the assigning:

repeating the calculating the first device assessment, the comparing the first device assessment to the second device assessment, and the assigning for a second unassigned data partition selected from among the remaining unassigned data partitions, wherein the second unassigned data partition has a highest processing requirement among the remaining unassigned data partitions.

9. The method of claim 1, wherein the first device assessment is a measure of an expected time to complete processing of pre-existing tasks on the first computing device.

10. The method of claim 1, wherein:

the second computing device is a standby host; and

the first device assessment is a measure of an expected time to complete processing of pre-existing tasks on the first computing device.

11. The method of claim 1, wherein:

the weighting factor based at least in part on the type of data stored in the respective data portion accessible by the first computing device is based at least in part on a type of access to be made to the respective data portion accessible by the first computing device; and

the type of access is based on a type of the respective data portion accessible by the first computing device.

12. The method of claim 1, wherein:

the weighting factor based at least in part on the type of data stored in the respective data portion accessible by the first computing device is based at least in part on a frequency of access to be made to the respective data portion accessible by the first computing device; and

the frequency of access is based on a type of the respective data portion accessible by the first computing device.

13. A method comprising:

calculating a first value and a second value, wherein

a first host has exclusive access to a first data partition,

a second host has exclusive access to a second data partition,

the first value is a first normalized work load (NWL),

the first value is based at least in part on

a first processing resource (PR) metric of the first host, and

a first partition-weighted data quantity (PWDQ) for a first quantity of data on the first data partition, wherein the first PWDQ depends at least in part on a product of;

a size of the first quantity of data, and

a weighting factor based at least in part on an access characteristic of the first quantity of data, and

the second value is a second NWL,

the second value is based at least in part on

a second PR metric of the second host, and

a second PWDQ for a second quantity of data on the second data partition, and

the first and second NWLs are calculated according to the following formulas;

$\mathrm{NWL}<br><br>\left(k\right)=\frac{\underset{j}{\sum <br><br>}<br><br>\mathrm{PWDQ}<br><br>\left(j\right)}{\mathrm{PR}<br><br>\left(k\right)},$
PWDQ(j)=Σ

_iWDQ(i,j); and

WDQ(i,j)=W(i,j)×

DQ(i,j), wherein

k is an index for the first and second hosts,

j is an index for data partitions assigned to a host,

i is an index for categories of information on a partition,

NWL(k) represents the NWL of a kth host,

PWDQ(j) represents a PWDQ for a jth partition of data,

PR(k) represents the PR of the kth host,

WDQ(i, j) represents a weighted data quantity of an ith category of information on a jth partition of data,

W(i, j) represents a weighting factor of an ith category of information on a jth partition of data, and

DQ(i, j) represents a quantity of data in an ith category of information on a jth partition of data;

comparing the first and second values, wherein the comparing is performed by a processor; and

assigning, in response to the comparing, exclusive access of a third data partition to one of the first and second hosts.

14. A system comprising:

a data server coupled to a first host and to a second host and comprising

a first data partition assigned to the first host,

a second data partition assigned to the second host,

a third data partition, and

a fourth data partition;

a selection module coupled to the data server and configured to select the third data partition or the fourth data partition,

a processor coupled to the data server and configured to assign exclusive access of the selected data partition to one of the first and second hosts based at least in part on

a first processing power of the first host,

a second processing power of the second host,

a first processing requirement for a first quantity of data on the first data partition, wherein the first processing requirement depends at least in part on a product of;

a size of the first quantity of data, and

a weighting factor based at least in part on an access characteristic that depends on a type of data of the first quantity of data;

a second processing requirement for a second quantity of data on the second data partition, wherein the second processing requirement depends at least in part on a product of;

a size of the second quantity of data, and

a weighting factor based at least in part on an access characteristic that depends on a type of data of the second quantity of data;

wherein the selection module is configured to select the third data partition or the fourth data partition based at least in part on

a third processing requirement for a third quantity of data on the third data partition, wherein the third processing requirement depends at least in part on a product of;

a size of the third quantity of data, and

a weighting factor based at least in part on an access characteristic that depends on a type of data of the third quantity of data, and

a fourth processing requirement for a fourth quantity of data on the fourth data partition, wherein the fourth processing requirement depends at least in part on a product of;

a size of the fourth quantity of data, and

a weighting factor based at least in part on an access characteristic that depends on a type of data of the fourth quantity of data.

15. The system of claim 14, wherein the first processing requirement is based at least in part on weighted data quantities WDQ determined according to the following equation:

WDQ(i)=W(i)×

DQ(i), wherein

i is an index for categories of information on the first data partition,

W(i) represents a weighting factor of an ith category of information on the first data partition,

W(i) is based at least in part on an access characteristic of the ith category of information on the first data partition, and

DQ(i) represents a quantity of data in an ith category of information on the first data partition.

16. The system of claim 14, further comprising:

a third host coupled to the data server, wherein

the processor is further configured to assign the exclusive access based at least in part on a failure of the third means for data processing.