Semi-dynamic load balancer for periodically reassigning new transactions of a transaction type from an overload processor to an under-utilized processor based on the predicted load thereof

• US 5,283,897 A
• Filed: 04/30/1990
• Issued: 02/01/1994
• Est. Priority Date: 04/30/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, George W., Georgiadis, Leonidas, Nikolaou, Christos N.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US07/516,642
• Time in Patent Office: 1,373 Days
• Field of Search: 395/800, 395/650, 395/50, 395/51, 395/54
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A semi-dynamic load balancer for a transaction processing system reallocates transaction types among computers in the system as a group rather than as individual transactions. Statistical data is accumulated in an affinity matrix which records the number of times a transaction type i was blocked by transaction type j was holding a lock on a data item that transaction type i wanted to access. When an overloaded computer is detected, transaction types are reallocated on the computers of the system according to a transaction type routing table which is updated based on data from the affinity matrix.

Claims

1. A semi-dynamic load balancer for a transaction-type computer system having multiple processors and a shared database, said load balancer reassigning transaction types to respective ones of said multiple processors to balance respective loads of said multiple processors;

the load balancer comprising;

routing means connected to said multiple processors for assigning new transactions of a same type to a processor of said multiple processors according to a routing table;

monitoring means connected to said multiple processors for periodically determining whether a load imbalance has occurred among said processors, said monitoring means including threshold means for determining whether a processor utilization of one of said multiple processors exceeds a predetermined threshold; and

reallocation means connected to and responsive to said monitoring means and including lock contention means for determining a predicted load to a candidate processor of said multiple processors for a possible reassignment of said new transactions of said same type of said one of said multiple processors having a processor utilization exceeding said predetermined threshold;

said reallocation means updating said routing table to thereby automatically reassign said new transactions of said same type to said candidate processor of said multiple processors.

2. A semi-dynamic load balancer for a multi-computer, shared database transaction processing system, said load balancer reassigning transactions to balance loads of respective ones of said computers, the load balancer comprising:

routing means connected to said processing means for assigning new transactions of a same type to a common computer in accordance with a transaction type routing table;

statistical means connected to said processing system for creating and maintaining an affinity matrix that records the number of times a transaction type i was blocked by transaction type j because said transaction type j was holding a lock on a data item in said shared database that said transaction type i wanted to access;

monitoring means connected to said processing system for periodically checking for an over loaded computer in said system; and

reallocation means, connected to and responsive to said monitoring means, using said affinity matrix for predicting an expected change in a contention related loading factor for each said computer for various possible reassignments of transaction types, said reallocation means making one or more changes in said transaction type routing table based on said predicted expected change in said contention related loading factor for each said computer for the various possible reassignments of transaction types, said routing means thereafter automatically reassigning new transaction types from an over loaded computer to an under utilized computer in accordance with said routing table.

3. The semi-dynamic load balancer for a multi-computer transaction processing system as recited in claim 2 wherein one of the computers in said multi-computer system is designated as a front end computer and others of said multi-computer system are designated as back end computers, said routing means being installed on said front end computer and said monitoring means being installed on each of said back end computers, said system further including communication link means interconnecting said back end computers to said front end computers and said monitoring means periodically transmitting data to said front end computer, said statistical means being installed on said front end computer and generating said affinity matrix from said data transmitted by said back end computers.

4. A transaction processing system comprising:

a plurality of computers sharing a common database, said plurality of computers being interconnected via communication links, one of said computers being a front end computer and others of said computers being back end computers;

routing means at said front end computer for assigning new transactions of a same type to one of said back end computers in accordance with a transaction type routing table;

means at each of said back end computers for periodically accumulating statistical data on the respective back end computer'"'"'s work load and transmitting the statistical data to said front end computer;

load balancing means at said front end computer for periodically analyzing said statistical data from said back end computers;

wherein said load balancing means including statistical means for creating and maintaining an affinity matrix that records the number of times a transaction type i was blocked by transaction type j because said transaction type j was holding a lock on a data item in said shared common database that said transaction type i wanted to access, said load balancing means using said affinity matrix for predicting an expected change in a contention related loading factor for each said back end computer for various possible reassignments of transaction types and making one or more changes in said transaction type routing table based on said predicted expected change in said contention related loading factor for each said back end computer for the various possible reassignments of transaction types;

said routing means thereby automatically reassigning transaction types from an over loaded back end computer to an under utilized back end computer in accordance with said transaction type routing table as updated.

5. In a transaction processing system of the type having a plurality of computers sharing a common database, said plurality of computers being interconnected via communication links, each of said computers processing one or more transaction types, at least one of said computers being a front end computer and others of said computers being back end computers, a load balancing system for said back end computers comprising:

routing means at said front end computer for assigning new transactions of a same type to one computer of said back end computers in accordance with a transaction type routing table;

monitoring means at each of said back end computers for accumulating statistical data on the back end computer'"'"'s work load and periodically transmitting said statistical data to said front end computer;

load balancing means at said front end computer for periodically analyzing said statistical data and identifying ones of said back end computers having a processor utilization exceeding a predetermined threshold, said load balancing means selecting one of said back end computers with a greatest utilization exceeding said threshold and selecting a transaction type as a candidate transaction type for reallocating to another one of said back end computers;

said front end computer including calculating means for calculating an increase in loading to those back end computers having a processor utilization not exceeding said threshold due to reallocation of said candidate transaction type and then determining those of said back end computers for which the increase in loading plus current processor utilization do not exceed said threshold, said computers being candidate computers for reallocation of said candidate transaction type;

said load balancing means selecting one of said candidate computers for which the calculated increase in loading is a minimum and reassigning said candidate transaction type to the selected candidate computer by updating said transaction type routing table.

6. The load balancing system as recited in claim 5 wherein said load balancing means includes statistical means for creating and maintaining an affinity matrix that records the number of times a transaction type i was blocked by transaction type j because said transaction type j was holding a lock on a data item in said shared common database that said transaction type i wanted to access, said load balancing means using said affinity matrix for predicting an expected change in a contention related loading factor for each said back end computer for various possible reassignments of transaction types and making one or more changes in said transaction type routing table based on said predicted expected change in said contention related loading factor for each said back end computer for the various possible reassignments of transaction types.

7. The load balancing system as recited in claim 5 wherein if there is not single transaction type which can be reallocated to achieve processor utilization below said threshold, said balancing means selecting more than one transaction type as a candidate transaction type for reallocation to another back end computer and said calculating means calculating an increase in loading to those back end computers having a processor utilization not exceeding said threshold due to reallocation of said candidate transaction type comprising more than one transaction type.