Source: http://www.google.com/patents/US8185909?ie=ISO-8859-1&dq=6,304,975
Timestamp: 2015-03-29 10:42:34
Document Index: 161337353

Matched Legal Cases: ['art 501', 'art 502', 'art 501', 'art 501', 'art 501', 'art 502', 'art 502', 'art 503']

Patent US8185909 - Predictive database resource utilization and load balancing using neural ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA preemptive neural network database load balancer configured to observe, learn and predict the resource utilization that given incoming tasks utilize. Allows for efficient execution and use of system resources. Preemptively assigns incoming tasks to particular servers based on predicted CPU, memory,...http://www.google.com/patents/US8185909?utm_source=gb-gplus-sharePatent US8185909 - Predictive database resource utilization and load balancing using neural network modelAdvanced Patent SearchPublication numberUS8185909 B2Publication typeGrantApplication numberUS 11/682,866Publication dateMay 22, 2012Filing dateMar 6, 2007Priority dateMar 6, 2007Also published asUS20080222646Publication number11682866, 682866, US 8185909 B2, US 8185909B2, US-B2-8185909, US8185909 B2, US8185909B2InventorsLev Sigal, Alexander GlaubermanOriginal AssigneeSap AgExport CitationBiBTeX, EndNote, RefManPatent Citations (15), Non-Patent Citations (1), Classifications (15), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetPredictive database resource utilization and load balancing using neural network model
US 8185909 B2Abstract
1. A computer program product comprising computer readable instruction code stored in a memory for execution by a computer, said computer readable instruction code configured to:
receive, at a neural network model of a database load balancer, a first incoming task name identifying a type of database task to be executed in a remote server cluster having a plurality of database servers;
receive, at the neural network model from a load balancer engine in the database load balancer, an actual resource utilization result associated with the first incoming task name when the database task identified by the first incoming task name is executed by one of the database servers in the remote server cluster;
train the neural network model based on the actual resource utilization result associated with the first incoming task name, wherein a first set of input parameters is associated with the first income task name;
provide, from the neural network model to the load balancer engine, a predicted resource utilization generated by the neural network model based on a second incoming task name, wherein said second incoming task name is associated with a second set of input parameters, and further wherein the neural network model generates the predicted resource utilization based on: (i) the second incoming task name, (ii) the second set of input parameters, and (iii) the number of records in the plurality of database servers in the remote server cluster; and
identify, by the load balancer engine, based on the predicted resource utilization, one or more of the plurality of database servers to execute the database task identified by the second incoming task name.
2. The computer program product of claim 1 wherein said second incoming task name is a write-based task and wherein said second incoming task is forwarded by the load balancer to a master server in the remote server cluster.
3. The computer program product of claim 1 wherein said second incoming task name is a read-based task and wherein said second incoming task name is forwarded by the load balancer engine to a slave server in the remote server cluster.
4. The computer program product of claim 1 wherein said second incoming task name is associated with one of: an import, syndication, mass delete, matching, recalculation of a calculated field, search on expression, search with operators, search on main table fields, search with qualifiers or search with taxonomy attributes.
5. The computer program product of claim 1 wherein said neural network model comprises a feed-forward back-propagation neural network.
6. The computer program product of claim 1 wherein said actual resource utilization result includes all of central processing unit (CPU), memory, disk and network utilization.
7. The computer program product of claim 1 wherein said actual resource utilization result includes at least one of central processing unit (CPU), memory, disk or network utilization as at least one of an average, a maximum, or a minimum that (i) is linear in time or (ii) that varies over time to allow for phase interleaving.
8. The computer program product of claim 1 wherein the predicted resource utilization is based at least in part on a number of images in a database coupled with said remote server cluster.
9. The computer program product of claim 1 wherein the predicted resource utilization is based at least in part on a number of PDF files in a database coupled with said remote server cluster.
10. The computer program product of claim 1 wherein the predicted resource utilization is based at least in part on a number of BLOBs in a database coupled with said remote server cluster.
11. The computer program product of claim 1 wherein the predicted resource utilization is based at least in part on a database version of a database coupled with said remote server cluster.
Load balancers are software or hardware components that are used to spread tasks between multiple computing resources. Load balancing is performed to obtain scalability, decrease latency, and maximize performance for example. Load balancers may be utilized with server farms or clusters. Many load balancers can operate when a given server fails or during periods of server maintenance for example. Providing access to the computing resources when a server is not accessible allows for increased availability, or �up time� of the computing resources. Many types of load balancing are currently used including round-robin, least connections, least response time, least bandwidth, least packets, source Internet Protocol (IP), token and Uniform Resource Locator (URL) hashing for example.
Current scalable database clusters rely on load balancers that are reactive and not predictive. All of the algorithms mentioned in the previous paragraph as reactive algorithms. This results in poor system performance and/or increased hardware costs to account for the inefficiency of the load balancing algorithms currently in use. Load balancing algorithms currently in use do not preemptively assign incoming tasks to particular servers based on predicted Central Processing Unit (CPU) and/or predicted memory/disk/network utilization for the incoming tasks. In other words, the currently utilized algorithms are not preemptive. Furthermore, in architectures that include a heterogeneous mix of writeable and readable database servers, i.e., master and slave database servers respectively, there are no known load balancers that preemptively schedule tasks based on the read or write characteristic of a particular task. Specifically, there are no known load balancers that direct write-based requests or tasks to a master for example. Furthermore, there are no known load balancers that utilize a neural network to learn and predict which read-based tasks will utilize predicted amounts of resources such as CPU and/or memory/disk/network and assign the task to a database server in a cluster based on the predicted utilization.
The most basic algorithms for load balancing database clusters include reactive algorithms such as round robin or least connection. These load balancing algorithms consider all database servers in a cluster as equal and distribute client requests between the database servers in a round-robin manner or based on the information about the number of open connections. Round robin algorithms spread the incoming tasks to the next server in a cluster regardless of the predicted resource utilization of the incoming task. Connection based algorithms spread the incoming task to the server with the least connections regardless of the predicted resource utilization of the incoming task. Neither of these algorithms take into account the particular resources available to each server for example, the number of CPUs in a given server or the amount of memory to predict the future utilization of the servers. Likewise, these methods do not take into consideration the difficulty of tasks running on the servers and their influence on the resource utilization of the server. Current load balancing methodologies also do not take into account the current database characteristics such as the number of records, lookups, images, Portable Document Format (PDF) files, Binary Large Objects (BLOBs) and the widths of the fields for example and hence cannot possibly predict how long a particular task utilizing these parameters will take to execute or how much memory the task would consume. The other algorithms listed above likewise are reactive in nature and in no way predict how long a particular request or task will take, or how resource intensive the task will be in order to choose a server in a cluster to direct the task.
An example of poor distribution occurs when utilizing known load balancing algorithms when an incoming task obtains a connection to a database server executing a �resource-hungry� request (e.g. matching, complicated search, mass record deletion) rather than to a database server executing several simple requests (e.g. record retrievals). In this case traditional load balancing methods lead to asymmetric load balancing between database servers in a cluster. This results in resource allocation that is not optimized for the database application in use. Specifically, the results which occur from the spreading the tasks using known algorithms are random since there is no estimation on a per task level to even resource utilization between servers in cluster.
For example, given a two server cluster, if four incoming tasks include two resource intensive tasks and two light resource utilization tasks, then in the round robin case, there is a good chance that the two resource intensive tasks will execute on the same server in the cluster. In this scenario, the two light resource utilization tasks will execute quickly on the other server which will then stand idle while the other server runs completely utilized. Depending on the order that the tasks arrive, it is possible that each server will obtain a resource intensive task and a light resource utilization task. Thus, the result is random since the result depends on the order in which the tasks arrive at the load balancer. Likewise with the least connection algorithm, one can readily see that the server with the least connections may be executing at least one task that may for example be executing an extremely resource intensive task that may take a tremendous amount of CPU. Using this algorithm, an incoming resource intensive task is still directed to the server with the least connections. Hence, the results of this load balancing algorithm are random since the �size� of the tasks has nothing to do with the number of connections that a server in the cluster currently has.
Import Syndication Mass Delete Matching Recalculate calculated fields Search according to expression Search with contain operators Sorting on main table fields Search according to qualifiers and taxonomy attributes Any other task that may cause a significant load on a database server may be analyzed and further utilized by embodiments of the invention to perform load balancing. In other embodiments of the invention, all tasks may be analyzed and utilized for preemptive load balancing.
FIG. 1 is shows an architecture diagram for an embodiment of the preemptive neural network database load balancer. Embodiments of the invention may simultaneously obtain many connection requests from standalone or enterprise applications, for example Client 1 through Client �n�. Embodiments of the invention include three modules operating in two threads. The client thread includes the connection pool module and the backend thread includes the load balancer engine and the neural network model. Although the tasks represented in FIG. 1 are shown as executing under two threads, any number of threads may be utilized as long as the functions detailed herein are executed. Use of any number of threads or processes is in keeping with the spirit of the invention.
The load balancer engine is responsible for collection for example through a �listener� of all needed information (CPU, memory, disk, network utilization) with respect to the tasks running in the cluster of servers (shown as the lower rectangle in FIG. 1). The listener continuously collects resource utilization information from the servers via and the load balancer engine calls the neural network model in order to continuously predict which server has the lowest current and predicted loads. In effect, the neural network is continuously learning. The load balancer engine is further coupled with the neural network model. The load balancer submits task and observed resource utilization forward to the neural network model and stores and utilizes predicted results obtained from the model.
The load balancer and neural network model execute within the backend thread independently from the client thread. The neural network model obtains task information and input parameters from the load balancer engine and in addition obtains observed resource utilization and analyzes the information. The information is utilized for training the neural network to predict resource utilization for future incoming tasks. Upon request from the load balancer engine, a given task with particular input parameters results in the neural network returning predicted resource utilization to the load balancer. The load balancer then assigns the incoming task to a particular server based upon the predicted and observed resource utilization of a given server and the predicted resource utilization of the particular incoming task. The load balancer engine may in one or more embodiments attempt to keep the future resource utilization of the servers in the cluster roughly the same. For example, in one embodiment, with a given incoming read-only task predicted to take 10 seconds of CPU to complete, and with server Slave 1 and Slave �m� having a predicted current utilization of 20 more seconds and Slave 2 having a predicted current utilization of 10 more seconds, the incoming task is assigned to Slave 2. The resource to be equalized may be CPU, memory, disk or network utilization in one or more embodiments of the invention or any other resource associated with a computing element. The direction of a task to a given server in a database cluster may also attempt to optimize more than one resource at the same time, i.e., attempting to fit a CPU intensive light memory task with a light CPU and memory intensive task for example to yield roughly equal resource utilization between another server having two medium CPU/memory tasks.
In one or more embodiments, any task related to data update, for example Create, Update and Delete requests are directed to the master. This allows for one server, i.e., the �master� server to perform all write operations with �m� slave servers all performing read operation related tasks. This allows for tremendous scalability for mostly read application instances. In one or more embodiments multiple masters may be utilized and in these embodiments the neural network may also be utilized by the load balancer to preemptively optimize resource utilization between write-based servers in a cluster.
FIG. 2 shows an embodiment of a load balancing algorithm implementing a preemptive neural network database load balancer. The connection pool receives a request from a client for a connection to specific repository at 201. Any type of task may be requested by the client including a write-based task or a read-based task. If at 202 the incoming task, i.e., request, is for a read-only operation/task, then processing proceeds at 203. If the request is for a write-based operation, then processing continues at 208 where a connection to the master server is returned at 211. Although the embodiment shown in FIG. 2 is directed at a single master, multi-slave system, steps 202 and 208 may be eliminated in a multi-master architecture. In the case of a read-only operation, if there is cached connection to an unused server at 203, then a connection to the unused server returned at 209 and control proceeds to 211. If however at 203 there is no cached connection to an unused server, then if there is an unconnected server at 204, then a new connection is created, placed in the connection pool and returned at 210 with processing proceeding to 211. If all servers have connections as per 204, then the �least busy� database server is calculated at 205. The �least busy� database designation may calculated to include current utilization along with neural network predicted utilization of any tasks that have been forwarded to the particular server. The predicted resource utilization �busy status� of the servers is recalculated at 206. This may include update of the resource utilization to the neural network, for example with respect to a given task and the actual observed resource utilization for executing that task. If an existing connection to the �least busy� server exists, then it is returned otherwise a new connection is returned at 207 with processing continuing to 211. When a new request from a client comes in, processing begins at 201 again.
IW�Input Weight matrices.
b�a scalar bias.
1 a, 1 b - the tan-sigmoid transfer functions.
LW�output weight matrices.
The net input to the transfer functions 1 a, 1 b is the sum of b and the IW or LW.
Targets�Data defining the desired network outputs is received from the server notification mechanism as resource utilizations associated with incoming tasks.
Outputs�Response of a network to its inputs as predicted resource utilization target values.
FIG. 5 shows a graphical representation of the resource utilization per unit time for the servers in a cluster. Specifically, a new incoming task 500 that will take a certain percentage of CPU namely �CPn�, on an idle server for a given execution time namely �Tnew� and that will take a certain amount of memory �memn� until the task completes. Predicted server resource utilization chart 501 shows the predicted CPU, memory utilization and completion times (that is updated when a task actually completes in one or more embodiments) of the tasks executing on a first server. Likewise, predicted server resource utilization chart 502 shows the predicted CPU, memory utilization and completion times for the tasks executing on a second server. Based on least connection scheduling, since the first server (as per 501) is executing 5 tasks and the second server (as per 502) is executing 7 tasks, incoming task 500 would be directed to the first server associated with predicted server resource utilization chart 501. Based on round robin scheduling, there is a 50-50 chance that incoming task 500 will be executed on the first server associated with predicted server resource utilization chart 501. As can be seen from predicted server resource utilization chart 501, this server is actually busier and has higher memory utilization than the second server associated with predicted server resource utilization chart 502. Since embodiments of the invention are able to predict the length of execution time of the tasks residing on each server, the preemptive neural network database load balancer directs incoming task 500 to the server associated with predicted server resource utilization chart 502. This results in the updated predicted server resource utilization chart 503 (which may be normalized in CPU percentage as the processing is spread between tasks while the memory is generally an absolute indication). Although the charts shown in FIG. 5 have memory and CPU utilization that is linear in the time axis and shows that memory utilization and CPU utilization end at precisely the same time, this is only shown in this manner for ease of illustration. Embodiments of the invention are fully capable of utilizing processing percentage and other resource utilization numbers that vary over time. For example, the memory utilization of each task may in general grow as time increases to the right in FIG. 5. Likewise, the CPU utilization may behave in a non-linear fashion since processing may delay for given intervals and then ramp up when data is available for processing. Hence, embodiments of the invention may direct tasks based on �average� CPU and memory utilizations, or in a more complex manner may interleave the tasks when there are known variations of CPU and other resource utilizations over time. This is termed resource utilization phase interleaving. For example if task 500 had a �hump� in the middle of the CPU utilization (upper portion) of the chart, then this could be taken into account and matched with a task that was in the correct phase (i.e., with a dip in the CPU utilization) at a particular time. Any other interleaving of resources when predicted variances of these parameters is to occur is in keeping with the spirit of the invention.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6327622 *Sep 3, 1998Dec 4, 2001Sun Microsystems, Inc.Load balancing in a network environmentUS7177923 *Mar 13, 2001Feb 13, 2007Agere Systems Inc.Methods and devices for selecting internet serversUS7552100 *Jul 28, 2006Jun 23, 2009Siemens Energy, Inc.Load prediction based on-line and off-line training of neural networksUS8051019 *Jul 13, 2006Nov 1, 2011Sap AgNeural network resource sizing apparatus for database applicationsUS20040093315 *Jul 30, 2003May 13, 2004John CarneyNeural network trainingUS20040139083 *Jan 9, 2003Jul 15, 2004International Business Machines CorporationReplication of changed information in a multi-master environmentUS20040177245 *Mar 5, 2003Sep 9, 2004Murphy Richard C.Automated resource management using perceptron predictionUS20040225631 *Apr 29, 2003Nov 11, 2004International Business Machines CorporationSystem and method for identifying a workload type for a given workload of database requestsUS20050154789 *Jan 13, 2004Jul 14, 2005International Business Machines CorporationMinimizing complex decisions to allocate additional resources to a job submitted to a grid environmentUS20050177549 *Mar 31, 2005Aug 11, 2005Oracle International CorporationData mining agents for efficient hardware utilizationUS20060224588 *Mar 31, 2005Oct 5, 2006International Business Machines CorporationDatabase contention and deadlock detection and reduction within application serversUS20070143765 *Dec 21, 2005Jun 21, 2007International Business Machines CorporationMethod and system for scheduling of jobsUS20070168678 *Jan 18, 2006Jul 19, 2007Sybase, Inc.Secured Database System with Built-in Antivirus ProtectionUS20080065574 *Sep 7, 2007Mar 13, 2008Morgan StanleyAdaptive database management and monitoringUS20080172673 *Jan 15, 2007Jul 17, 2008International Business Machines CorporationPrediction based resource matching for grid environments* Cited by examinerNon-Patent CitationsReference1 *El-Abd et al., "A Neural Network Approach for Dynamic Load Balancing in Homogeneous Distributed Systems," IEEE, 1997, pp. 1-8.* Cited by examinerClassifications U.S. Classification718/105, 706/15, 706/12, 709/226, 718/102, 707/999.002, 706/14International ClassificationG06F17/30, G06F9/50, G06F15/18, G06F9/44Cooperative ClassificationY10S707/99932, G06F2209/5019, G06F9/505European ClassificationG06F9/50A6LLegal EventsDateCodeEventDescriptionAug 26, 2014ASAssignmentOwner name: SAP SE, GERMANYEffective date: 20140707Free format text: CHANGE OF NAME;ASSIGNOR:SAP AG;REEL/FRAME:033625/0334Nov 8, 2007ASAssignmentOwner name: SAP, AG, GERMANYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SIGAL, LEV;GLAUBERMAN, ALEXANDER;REEL/FRAME:020091/0184Effective date: 20070406RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services