Managing server load by varying responses to page requests

PRIORITY CLAIM

0001This application is a division of application Ser. No. 10/390,067, filed Mar. 14, 2003, which claims the benefit of U.S. Provisional Appl. No. 60/400,079, filed Jul. 31, 2002. The disclosures of the aforesaid applications are hereby incorporated by reference.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003This invention relates to systems and methods for managing load levels of web server systems that generate and personalize web pages dynamically.

00042. Description of the Related Art

0005The term “load” is commonly used to describe how much of a computing device's or system's resources are being used. These resources can include, for example, processing capacity, random access memory, incoming and outgoing communication bandwidth, and/or disk input/output (I/O) capacity. Operating systems commonly generate a number of different parameters indicative of the current load on a system.

0006A high load on a computing device typically means that some or all of the resources are being fully or almost fully utilized. A low load typically means that there are sufficient resources available to handle additional tasks. As the load on a computing device increases, performance in handling tasks generally suffers. When load exceeds certain critical levels, response times can degrade precipitously.

0007A web site is typically hosted on a server system which can include one or more computing devices. A low traffic web site, for example, can typically be hosted on a single server computer. A very high traffic web site, for example, will typically include multiple computing devices such as load balancing computers, web server computers, application server computers, and database server computers. The load on such a system can be specified in terms of the loads on the individual physical computing devices that make up the system.

0008The load on a web server system is affected by a number of factors, such as the number of web page requests being handled simultaneously, the rate at which new requests are being received, and the amount of processing and memory required to handle each request. In order to maintain acceptable user response times, well-maintained web sites have historically been hosted on systems that have sufficient excess capacity to handle peak loads. When the host system is lightly loaded, the excess capacity is unused.

0009In certain instances, the popularity of a web site increases unexpectedly, and the entity hosting the site does not have the ability (e.g. funds or time) to add server capacity to respond to the increasing loads. In these situations, the site's servers can become overloaded. As a result, wait times for requests can become unacceptable, and some requests may be dropped altogether without a response. When requests are dropped or when wait times become longer than several seconds, users' perceptions of a web site can be adversely affected.

0010In a paper titled “Reading Course Paper Overview of Internet QoS and Web Server QoS,” (Department of Computer Science, The University of Western Ontario, London, Ontario, Canada, Apr. 6, 2000), Nikolaos Vasiliou surveys several application level systems designed to handle peak server loads when serving page requests. The systems surveyed generally propose varying the priority with which requests are handled in order to guarantee reasonable response times for high priority requests. Most of the systems described in the paper prioritize requests based on factors such as how much a web hosting customer is paying for the hosting of a requested web page. One of the systems prioritizes requests based upon the identity of the user requesting the page. These systems, however, end up favoring the high priority requests at the expense of lower priority requests. As a result, when loads increase, lower priority requests are more likely to be delayed or dropped.

0011Systems that address load problems solely by prioritizing some requests over others are unacceptable in certain contexts. For example, in many environments, long server response times and dropped page requests can result in a loss of customers. The present invention seeks to address this problem, among others.

SUMMARY

0012The present invention provides a system and method for managing server load levels by varying the quantity of processing resources used in response to like requests for dynamically generated web pages. In accordance with one aspect of the invention, a dynamic page generator monitors load levels associated with one or more servers, services, and/or other components used to generate dynamic web page content. When a page request is received from a user, the dynamic page generator determines how to process the page request based at least in-part on these load levels, such that the quantity of processing resources used in generating the page will generally be inversely proportional to the current load level.

0013For example, if system load is currently high, the dynamic page generator may limit the depth of processing that will be performed by a recommendations engine or other personalization component in generating personalized content. The dynamic page generator may additionally or alternatively control the type or types of dynamic content included in the requested web page—such as by selecting between two or more alternative web page templates for the requested URL. In this manner, the load placed on the system by each dynamic page request may be varied so as to maintain load levels, and thus page response times, at an acceptable level. The process of determining how to respond to dynamic page requests is referred to herein as a “level of service” determination, as it affects the level of service provided to users.

0014Neither this summary nor the following detailed description is intended to define the invention. The invention is defined by the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

0015<figref idref="DRAWINGS">FIG. 1</figref> illustrates the general software architecture of a system which regulates load levels according to one embodiment of the invention.

0016<figref idref="DRAWINGS">FIG. 2</figref> illustrates an example system configuration that may be used to implement the system of <figref idref="DRAWINGS">FIG. 1</figref>.

0017<figref idref="DRAWINGS">FIG. 3</figref> illustrates an example sequence of steps that may be performed by the dynamic page generator of <figref idref="DRAWINGS">FIG. 1</figref> in response to a dynamic page request.

0018<figref idref="DRAWINGS">FIG. 4</figref> illustrates the general arrangement of an example web page generated in accordance with the invention.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

I. Overview (FIGS.

1

and

2

)

0019<figref idref="DRAWINGS">FIG. 1</figref> illustrates a web site system <b>30</b> that embodies the invention. The system includes a dynamic page generator <b>32</b> that responds to page requests received from Internet users. The dynamic page generator <b>32</b> may run in-whole or in-part on a physical web server <b>34</b> (<figref idref="DRAWINGS">FIG. 2</figref>). The dynamic page generator <b>32</b> in the illustrated embodiment communicates with one or more services <b>36</b> that generate content incorporated into dynamic web pages. These services may, for example, include one or more recommendations engines that recommend items, such as products, to users based on the respective profiles of such users. Examples of recommendation engines and algorithms that may be used for this purpose are disclosed in U.S. Pat. No. 6,266,649 and published U.S. Patent Application Publication 2002/0198882 A1, the disclosures of which are hereby incorporated by references. The services <b>36</b> are preferably implemented as program modules that run on one or more physical servers. For example, each service may be implemented using a different respective server or set of servers. The dynamic page generator <b>32</b> may also access a repository <b>46</b> of web page templates and HTML content.

0020As further depicted by <figref idref="DRAWINGS">FIG. 1</figref>, as requests for dynamic web pages are received from user computers <b>40</b>, the dynamic page generator <b>32</b> invokes a level-of-service computation module <b>42</b> to determine how to respond to such requests. As illustrated, this level-of-service module <b>42</b> may determine how to respond to a given request based on load data associated with the external services <b>36</b> or their servers. In addition, the level-of-service module may take into consideration data stored in a user profiles database <b>44</b>, or user score values generated from such data.

0021The output of the level-of-service module <b>42</b> may be in any of a variety of forms. For example, this module <b>42</b> may generate a level-of-service score, such as a value between one and ten, that specifies a level of service to be provided to the user. This score value may then be passed to each service <b>36</b> invoked by the particular page request, which may in turn use the score to select the appropriate type and/or quantity of processing to be performed to generate the requested data. The level-of-service module <b>42</b> may additionally or alternatively select a web page template that specifies the type or types of dynamic content to be included in the response. Further, the level-of-service module <b>42</b> may additionally or alternatively generate one or more service parameters that specify or control the amount of processing that will be performed by a particular service <b>36</b> in responding to the request, as described below. Moreover, the level-of-service module <b>42</b> may additionally or alternatively determine the amount of and length of time that user data is cached in a cache memory <b>43</b>. Regardless of the particular form, the output of this module <b>42</b> indirectly or directly specifies a level of service to be provided in responding to the page request.

0022The levels of service are preferably dynamically selected or varied such that the quantity of processing resources used to respond to a request for a given page is generally inversely proportional to the current load level(s) of the invoked component(s) or of the system as a whole. The system in <figref idref="DRAWINGS">FIG. 1</figref> thus operates in a feedback configuration, reducing the amount of processing performed during heavy load conditions and increasing the amount of processing performed during light load conditions. Preferably, the levels of service are varied so as to maintain response times for all users at an acceptable level, with very little or no need to drop page requests.

0023<figref idref="DRAWINGS">FIG. 2</figref> illustrates one example of how the above-described functions may be assigned to physical machines. In this example, the web site system <b>30</b> includes one or more physical web servers <b>34</b>, one or more physical application servers <b>36</b>A, and one or more physical database servers <b>36</b>B, all of which communicate over a local area network. The system also includes a load monitoring machine <b>50</b> that polls each physical web server <b>34</b>, application server <b>36</b>A and database server <b>36</b>B to obtain real time load values. The real time load values may include various server resource parameters commonly generated by Unix and/or Windows operating systems, and may be requested using application program interfaces (APIs) provided by these operating systems.

0024Real time load data collected by the load monitoring machine <b>50</b> is reported to a level of service machine <b>52</b>, optionally in an aggregated form in which the loads of multiple machines are appropriately averaged. The level of service machine <b>52</b> in this example also receives user score values generated by an off-line user score generator module <b>56</b>, which may run on any appropriate machine. The user score generator <b>56</b> may alternatively be omitted, in which case levels of service may be based solely on load data.

0025In one embodiment, the user score generator <b>56</b> periodically generates a separate score for each user of the system by analyzing the browsing and/or purchase histories of the users. A user's score may, for example, be based on one or more of the following: (a) the amount of time spent by the user browsing the web site, (b) the quantity of transactions conducted by the user on the web site, (c) the length of time since the user set up an account on the web site (d) the user's connection speed. The scores may be generated or updated at any appropriate time, such as when a user finishes a browsing session or completes a transaction. Although the user scores are shown as flowing directly from the user score generator to the level of service machine <b>52</b>, they may actually be read from the user database <b>44</b> as needed to respond to page requests, or may be extracted from browser cookies transmitted with such requests.

0026The level of service machine <b>52</b> generates level of service parameters based on the load data and (preferably) the user scores, as described above, and reports these parameter values to the web servers <b>34</b>. Preferably, each parameter value or set of parameter values corresponds to a particular page request, and directly or indirectly specifies the amount of processing to be performed in responding to that request. However, in some embodiments, these parameter values may alternatively specify how the web servers <b>34</b> should respond to a particular class of request. For example, the level of service machine <b>52</b> way instruct the web servers <b>34</b> to temporarily disable personalized ranking of search results for all users, or for all users whose score falls below a particular threshold.

II. Example Methods for Limiting Utilization of Processing Resources

0027One particular method that may be used to control the amount of processing resources used in responding to page requests involves controlling the size of an input data set used to generate personalized page content. For example, in one embodiment, a recommendations service of the type described in U.S. Pat. No. 6,266,649, referenced above, is used to generate personalized recommendations of items, such as products represented in a database. To generate these recommendations, the recommendations service maps an input data set of items that are “known” to be of interest to the user (e.g. those the user has viewed or purchased) to a set of additional items that are deemed likely to be of interest to the user. The amount of processing performed to identify these additional items is directly proportional to the size of the input data set (i.e., the set of “items of known interest”). The recommendations are generated on-the-fly in response to page requests, and are incorporated into the requested web pages.

0028In accordance with the invention, the quantity of processing performed by the recommendations service is controlled, on a page request by page request basis, by selectively limiting the size of the set of items of known interest used to generate the personalized recommendations. For example, when the server system is lightly loaded, the entire purchase history of a user may be used to generate the personalized recommendations. When, on the other hand, the system is heavily loaded, the recommendations may be generated based solely on the last N (e.g., 5) items purchased by the user, even though the user's purchase history may include a much larger number of items. The value of N may be selected dynamically based on the load of the web server system as a whole, based on the load on the recommendations service, and/or based on information about the particular user. Thus, regardless of the load level, the user is provided with personalized item recommendations, although these recommendations may be based on a relatively small amount of information about the user during heavy load conditions. Recommendations provided during high load conditions may therefore be less tailored or less accurate than recommendations provided during low load conditions.

0029The amount of processing performed by a search engine or service in response to user-submitted search queries can similarly be controlled. For example, in one embodiment, a product search engine of the web site system ranks search results based on information known about the user, such as the user's purchase history. The goal of this ranking, in one embodiment, is to more prominently display those products that are the most similar to items the user has purchased. An example of a search engine system that uses information about the user (as well as other types of information) to rank search results is described in U.S. Pat. No. 6,185,558. As with the recommendations service example above, the amount of processing performed to generate the personalized ranking may be selectively controlled by limiting the amount of user profile information incorporated into the ranking process. For instance, during heavy load conditions, only a small subset of the user's purchase history may be incorporated into the ranking process, while during light load conditions the user's entire purchase history may be used.

0030The amount of processing performed by a web server system <b>30</b> may also be controlled by effectively turning on and off certain types of services. For example, U.S. Pat. No. 6,144,958 describes a spell checking service used to check the spellings of search terms in search queries; and U.S. Pat. No. 6,006,225 describes a service for suggesting additional search terms to users to assist these users in refining their queries. One or both of these services may be selectively turned off during heavy load conditions, and/or in response to requests from certain classes of users, to reduce the processing load associated with responding to search query submissions. The disclosures of the aforesaid patents are hereby incorporated by reference.

0031In all of the examples provided above, web pages with meaningful content are always provided to the user (during error-free operation), but according to different levels of service. That is, all or nearly all of the web pages will contain the same type of content, but the amount of processing used to generate the content will vary inversely to the load on the system generating the web pages.

III. Process Flow (FIGS.

3

and

4

)

0032<figref idref="DRAWINGS">FIG. 3</figref> illustrates one example of a sequence of steps that may be performed by the dynamic page generator <b>32</b> of <figref idref="DRAWINGS">FIG. 1</figref> to respond to dynamic page requests in accordance with the invention. In response to receiving a dynamic page request from a user (block <b>70</b>), the dynamic page generator <b>32</b> obtains the load data associated with the component or components ordinarily invoked by the request (block <b>72</b>). For example, if the request is for a page that ordinarily includes personalized recommendations, load data associated with the corresponding recommendations service—or a server on which this service runs—may be obtained. If multiple components <b>36</b> are invoked, the load data associated with each such component may be obtained.

0033The dynamic page generator <b>32</b> also identifies the user (typically using a browser cookie transmitted with the page request), and retrieves a profile of the user and/or a user score derived from the user's profile (block <b>74</b>). If no score exists for the user, the user's profile data may be used to generate a score on-the-fly, or a default score may be used. As depicted by block <b>76</b>, the dynamic page generator <b>32</b> uses the load data and the user score to generate one or more level-of-service parameters for responding to the request (block <b>78</b>). The level of service parameter(s) may include one or more of the following, and may depend upon the particular URL requested: (1) an identifier of a web page template to be used; (2) a general level-of-service value that applies to all components, (3) separate level-of-service values for specific components or sets of components, (4) one or more depth-of-processing values indicating, e.g., a size of an input data set (such as a set used to generate personalized content), or (5) an indication of specific services or features to be disabled for purposes of generating personalized content.

0034As depicted by block <b>78</b>, the dynamic page generator <b>32</b> generates service requests to one or more services <b>36</b> in accordance with the level-of-service parameter(s) generated in block <b>76</b>. The data returned by the service or services <b>36</b> is then assembled into a dynamic web page, and the web page is returned to the user (block <b>80</b>).

0035Although the process shown in <figref idref="DRAWINGS">FIG. 3</figref> uses separate load data for each invoked component, the levels of service may be based in-whole or in-part on load data reflective of the current load on the web site system as a whole. In addition, although the level-of-service parameters in this example depend upon the identity of the user, they may alternatively be generated without regard to user identity.

0036Further, the task of selecting levels of service may be performed by the services themselves rather than by a centralized level of service module or computer. For example, in one embodiment, each service has its own respective level-of-service module <b>42</b> which may run on a particular server of that service. When a request is passed to such a service, the service (through its own level-of-service module <b>42</b>) selects an appropriate level of service based on its own load level (and optionally the user's identity), and responds to the request accordingly. Thus, rather than having a central server that dictates the processing for each page, each of the services makes its own level-of-service determinations.

0037<figref idref="DRAWINGS">FIG. 4</figref> illustrates the general form of a web page that may be generated according to the process of <figref idref="DRAWINGS">FIG. 3</figref>. In this example, the web page includes three dynamic content sections <b>84</b>, each of which contains content generated by a different respective service <b>36</b>. The particular selection of content sections <b>84</b> used to respond to a given URL request may depend upon the particular template selected, which may in-turn depend upon the current load levels of the various components or services <b>36</b> within the system. In addition, the content included within each section <b>84</b> may depend upon the level-of-service parameters associated with the page request. For example, for a content section <b>84</b> that includes purchase-history-based recommendations, the recommendations may be based on the entire purchase history of the user if the associated load levels are currently low, and may be based on a subset of this purchase history if load levels are currently high.

0038As discussed above, the level of service determination or feedback procedure preferably takes into account current system load levels in determining a level of service. Available system memory and available processing capacity are two load factors that may be considered. Another load factor that can be taken into account is a rate at which new web page requests are being received. The rate can be used as a rough measure of the amount of computing resources that can be allocated to responding to each request. In one embodiment, the available resources (e.g. processing cycles per second) can be divided by the rate of receipt (e.g., requests per second) to determine the amount of resources that can be allocated to serving each page without overloading the system.

IV. Data Caching Policies

0039Personalized content is commonly generated based on user profile data read from a database. To reduce the need to access such a database, some or all of a user's profile data may be maintained in a server system's non-volatile random access memory. Since a server system generally will not have enough random access memory to hold all of the data of all users in its memory, a caching policy is typically used. For example, a user's profile may be retrieved from a database and cached when first needed, and may later be overwritten in the cache memory according to a least-recently-used deletion policy. As a result of the caching policy, a user's first page request after a long period of inactivity may be substantially delayed by the time it takes to retrieve the user's data from a database.

0040In accordance with one embodiment, the external servers/and or services <b>36</b> vary their caching policy from user-to-user based on the profile of each user, or the user score generated therefrom. For example, for a relatively heavy user of the system, a service or server may do one or more of the following (1) keep a greater quantity of the user's purchase history, browsing history, or other profile data in cache memory (i.e., vary the amount of cache dedicated to a user); or (2) keep the user's profile data in cache memory for a longer period of time (e.g., for several hours or days) since the user's last access to the system, relative to the amount of time used for other users of the system. The servers and/or services <b>36</b> may additionally vary their caching policies based on current load data.

0041Although the invention has been described in terms of certain embodiments, other embodiments that will be apparent to those of ordinary skill in the art, including embodiments which do not provide all of the features and advantages set forth herein, are also within the scope of this invention. Accordingly, the scope of the invention is defined by the claims that follow.