System and method for load balancing in database queries

• US 20050021511A1
• Filed: 07/22/2004
• Published: 01/27/2005
• Est. Priority Date: 07/24/2003
• Status: Abandoned Application

• Current Assignee: KCI Licensing Incorporated (3M Company), Etagon Israel Limited
• Original Assignee: Etagon Israel Limited
• Inventors: Zarom, Rony
• Application Number:
  US10/895,952
• Publication Number:
  US 20050021511A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A system and method in which query load balancing process is performed in a cluster of middle-tier computing elements according to the load on at least one, but more preferably a plurality, of the computing elements of the group, this by passing pointers to queries between machines with information or processes pertinent to the query. Optionally the balancing may be carried out in two stages. The first stage performed rapidly, preferably implemented as a hardware device such as a switch for example in which a plurality of queries is distributed to a plurality of computing elements according to at least one descriptor attached to each query or a simple algorithm is used. The second stage preferably performed as above by at least one computing element of the group, but may optionally be performed by a plurality of such elements. Alternatively, the second stage may be performed by a separate computer.

Claims

1. A method for distributing at least one query to a plurality of computing elements, the query featuring at least one descriptor, the method comprising:

analyzing the at least one descriptor of the query; and

sending the query to a computing element according to the at least one descriptor.

2. The method of claim 1, wherein analyzing the at least one descriptor further comprises:

providing a plurality of rules; and

comparing the at least one descriptor to said plurality of rules.

3. The method of claim 2, wherein said plurality of rules is provided to a manager, and said manager receives the query and compares the at least one descriptor to said plurality of rules.

4. The method of claim 3, wherein said manager distributes the query to said computing element according to analysis of the at least one descriptor.

5. The method of claim 4, wherein said manager is at least one of the plurality of computing elements.

6. The method of claim 5, wherein said manager is a plurality of computing elements.

7. The method of claim 6, wherein preference is given to retaining the query at a computing element initially receiving the query as manager.

8. The method of claim 6, further comprising:

detecting that a number of queries at a computing element is below a predetermined level;

identifying a computing element having a highest number of queries; and

redistributing at least one query from said computing element having said highest number of queries to said computing element having said number of queries below said predetermined level.

9. The method of claim 1, comprising:

initially distributing the queries according to a first rapid algorithm, wherein said initial distribution is performed before said analyzing.

10. A system for distributing a load, comprising:

(a) a plurality of computing elements for receiving at least a portion of the load;

(b) an initial distribution element for performing an initial distribution of said at least a portion of the load, wherein said initial distribution element comprises a dedicated hardware device; and

(c) a manager for managing a redistribution of at least a part of said at least a portion of the load from at least one of said plurality of computing elements to at least another of said plurality of said computing elements.

11. The system of claim 10, wherein said dedicated hardware device is selected from the group consisting of a switch and a router.

12. The system of claim 10, wherein said manager is one of said plurality of computing elements.

13. The system of claim 10, wherein said manager is any of said plurality of computing elements, such that a plurality of said computing elements manage said redistribution sequentially.

14. The system of claim 10, wherein said initial distribution element is a hardware device, such that an assignment of said at least a portion of the load for said initial distribution is performed by hardware.

15. The system of claim 14, wherein said manager is a separate computing element.

16. The system of claim 10, further comprising a database, wherein the load features a plurality of queries for the database, and said initial distribution element initially distributes said plurality of queries to said computing elements and said manager redistributes queries between said computing elements.

17. The system of claim 16, wherein said manager directly removes at least one query from a computing element having a highest load and redistributes said at least one query to a second computing element.

18. The system of claim 17, wherein said second computing element sends a request to said manager before said manager directly removes said at least one query.

19. The system of claim 18, wherein said second computing element sends said request when a number of queries at said second computing element falls below a minimum number.

20. The system of claim 10, wherein said redistribution of at least a part of said at least a portion of the load is performed by analyzing said queries in the load according to at least one descriptor and performing said redistribution according to said analysis.

21. The system of claim 14, wherein each computing element operates a manager.

22. The system of claim 21, wherein each manager operates independently.

23. The system of claim 21, wherein each manager features a virtual query queue for containing a list of available queries.

24. A system for distributing a load, the load comprising a plurality of queries, each query featuring at least one descriptor, the system comprising:

(a) an initial distribution element for performing an initial distribution of said at least a portion of the load; and

(b) a plurality of computing elements for receiving at least a portion of the load, wherein each computing element comprises a manager, said manager functioning in at least one computing element for managing a redistribution of at least a part of said at least a portion of the load from at least one of said plurality of computing elements to at least another of said plurality of said computing elements, wherein said redistribution is performed by analyzing each query according to the at least one descriptor and performing said redistribution according to said analysis.

25. The system of claim 24, further comprising a virtual query queue at each of said managers, said virtual query queue containing a list of available queries.