Method and system for caching fragments while avoiding parsing of pages that do not contain fragments Number:7,412,535 from the United States Patent and Trademark Office (PTO) owispatent

Title: Method and system for caching fragments while avoiding parsing of pages that do not contain fragments

Abstract: A method, a system, an apparatus, and a computer program product are presented for a fragment caching methodology. After a message is received at a computing device that contains a cache management unit, a fragment in the message body of the message is cached. Subsequent requests for the fragment at the cache management unit result in a cache hit. A FRAGMENTLINK tag is used to specify the location in a fragment for an included or linked fragment which is to be inserted into the fragment during fragment or page assembly or page rendering. If a FRAGMENTLINK tag is present within the message body of a message, then the FRAGMENT message header for the message may indicate the presence of the FRAGMENTLINK tag with a directive for the FRAGMENT message header, e.g., using a "contains-fragment" directive.

Patent Number: 7,412,535 Issued on 08/12/2008 to Agarwalla,   et al.

---

Inventors:	Agarwalla; Rajesh S. (Pittsburgh, PA), Challenger; James R. H. (Garrison, NY), Copeland; George P. (Austin, TX), Iyengar; Arun K. (Yorktown Heights, NY), Linehan; Mark H. (Yorktown Heights, NY)
Assignee:	International Business Machines Corporation (Armonk, NY)
Appl. No.:	10/034,748
Filed:	December 19, 2001

---

Current U.S. Class:	709/236 ; 709/201; 709/214; 711/118; 711/119
Current International Class:	G06F 15/16 (20060101)
Field of Search:	709/236

---

References Cited [Referenced By]

---

U.S. Patent Documents

5050166	September 1991	Cantoni et al.
5815516	September 1998	Aaker et al.
5897622	April 1999	Blinn et al.
5983227	November 1999	Nazem et al.
5987480	November 1999	Donohue et al.
6029182	February 2000	Nehab et al.
6067569	May 2000	Khaki et al.
6115752	September 2000	Chauhan
6128627	October 2000	Mattis et al.
6138158	October 2000	Boyle et al.
6163779	December 2000	Mantha et al.
6167451	December 2000	Stracke, Jr.
6170013	January 2001	Murata
6192382	February 2001	Lafer et al.
6219676	April 2001	Reiner
6226642	May 2001	Beranek et al.
6230196	May 2001	Guenthner et al.
6249844	June 2001	Schloss et al.
6253234	June 2001	Hunt et al.
6345292	February 2002	Daugherty et al.
6427187	July 2002	Malcolm
6557076	April 2003	Copeland et al.
6584548	June 2003	Bourne et al.
6615235	September 2003	Copeland et al.
6678791	January 2004	Jacobs et al.
6718427	April 2004	Carlson et al.
6983310	January 2006	Rouse et al.
2002/0004813	January 2002	Agrawal et al.
2002/0007393	January 2002	Hamel
2002/0112009	August 2002	Capers et al.
2003/0101431	May 2003	Duesterwald et al.
2003/0101439	May 2003	Desoli et al.
2003/0120875	June 2003	Bourne et al.

Foreign Patent Documents

	111024982		Jan., 1999		JP
	2000172614		Jun., 2000		JP
	2000250803		Sep., 2000		JP
	2000305836		Nov., 2000		JP
	2000311108		Nov., 2000		JP
	WO 00/77615		Dec., 2000		WO
	WO 02/17082		Feb., 2002		WO

Other References

Patterson et al., "Using HTML 4" 1998, Que Corporation, 3.sup.rd ed., pp. 6-8. cited by examiner . Dingle et al., "Web cache coherence," Computer Networks and ISDN Systems, v. 28, n. 7-11, pp. 907-920, May 1996. cited by other . R. Metcalfe, IEEE Internet Computing--Scaling the Internet, vol. 1, No. 2, Mar./Apr. 1997. cited by other . 2000 IEEE International Conference on Personal Wireless Communications, Conference Proceedings, Dec. 2000, Hyderabad, India. cited by other . 2000 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS, Apr. 24-25, 2000, Austin, Texas. cited by other . AV Proceedings--Seventh International Workshop on Research Issues in Data Engineering, High Performance Database Management for Large-Scale Applications, Apr. 7-8, 1997, Birmingham, England, IEEE Computer Society Technical Committee on Data Engineering. cited by other . Microsoft Computer Dictionary, Fifth Edition, p. 443, Microsoft Press, 2002. cited by other . Hampton, Kip, High Performance XML Parsing with SAX, XML.com, Feb. 14, 2001, http://www.xml.com/pub/a/2001/02/14/perlsax.html. cited by other . About SAX, Genesis, FAQ, http://sax.sourceforge.net. FAQ last modified Nov. 28, 2001. cited by other.

Primary Examiner: Dalencourt; Yves
Attorney, Agent or Firm: Hamilton & Terrile, LLP Hamilton; Gary W.

---

Claims

---

What is claimed is:

1. A method for processing objects within a data processing system in a network, the method comprising: receiving a message at a computing device, wherein the message comprises a set of message headers and a message body, wherein the message body contains a top-level fragment; retrieving a message header from the message, wherein the message header indicates that the message body includes a linking element to a next-level fragment retrieving the next-level fragment; combining the top-level fragment and the next-level fragment into an assembled fragment; obtaining a source identifier for the next-level fragment from the linking element; sending a request message for the next-level fragment using the source identifier for the next-level fragment; and receiving a response message comprising the next-level fragment.

2. The method of claim 1 wherein the protocol header is generated by a server that originated the top-level fragment.

3. The method of claim 1 wherein the linking element comprises a source identifier, wherein the source identifier is formatted as a URI (Uniform Resource Identifier).

4. The method of claim 1 wherein the linking element is defined using SGML (Standard Generalized Markup Language).

5. The method of claim 1 wherein the message is an HTTP (Hypertext Transport Protocol) Response message.

6. An apparatus for processing objects within a data processing system in a network, the apparatus comprising: means for receiving a message at a computing device, wherein the message comprises a set of message headers and a message body, wherein the message body contains a top-level fragment; means for retrieving a message header from the message, wherein the message header indicates that the message body includes a linking element to a next-level fragment means for retrieving the next-level fragment; means for combining the top-level fragment and the next-level fragment into an assembled fragment; means for obtaining a source identifier for the next-level fragment from the linking element; means for sending a request message for the next-level fragment using the source identifier for the next-level fragment; and means for receiving a response message comprising the next-level fragment.

7. The apparatus of claim 6 wherein the protocol header is generated by a server that originated the top-level fragment.

8. The apparatus of claim 6 wherein the linking element comprises a source identifier, wherein the source identifier is formatted as a URI (Uniform Resource Identifier).

9. The apparatus of claim 6 wherein the linking element is defined using SGML (Standard Generalized Markup Language).

10. The apparatus of claim 6 wherein the message is an HTTP (Hypertext Transport Protocol) Response message.

11. A computer program product having instructions stored in a computer readable storage medium for use within a data processing system in a network for processing objects, the computer program product comprising: instructions for receiving a message at a computing device, wherein the message comprises a set of message headers and a message body, wherein the message body contains a top-level fragment; instructions for retrieving a message header from the message, wherein the message header indicates that the message body includes a linking element to a next-level fragment instructions for retrieving the next-level fragment; instructions for combining the top-level fragment and the next-level fragment into an assembled fragment; instructions for obtaining a source identifier for the next-level fragment from the linking element; instructions for sending a request message for the next-level fragment using the source identifier for the next-level fragment; and instructions for receiving a response message comprising the next-level fragment.

12. The computer program product of claim 11 wherein the protocol header is generated by a server that originated the top-level fragment.

13. The computer program product of claim 11 wherein the linking element comprises a source identifier, wherein the source identifier is formatted as a URI (Uniform Resource Identifier).

14. The computer program product of claim 11 wherein the linking element is defined using SGML (Standard Generalized Markup Language.

15. The computer program product of claim 11 wherein the message is an HTTP (Hypertext Transport Protocol) Response message.

---

Description

---

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application is related to the following applications:

application Ser. No. 10/034,724, filed Dec. 19, 2001, titled "Method and System for Caching Role-Specific Fragments";

application Ser. No. 10/034,770, filed Dec. 19, 2001, titled "Method and system for restrictive caching of user-specific fragments limited to a fragment cache closest to user";

application Ser. No. 10/034,771, filed Dec. 19, 2001, titled "Method and system for a foreach mechanism in a fragment link to efficiently cache portal content";

application Ser. No. 10/034,772, filed Dec. 19, 2001, titled "Method and system for fragment linking and fragment caching"; and

application Ser. No. 10/034,726, filed Dec. 19, 2001, titled "Method and system for processing multiple fragment requests in a single message".

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to an improved data processing system and, in particular, to a data processing system with improved network resource allocation. Still more particularly, the present invention provides a method and system for caching data objects within a computer network.

2. Description of Related Art

The amount of data that is transmitted across the Internet continues to grow at a rate that exceeds the rate of growth in the number of users of the Internet or the rate of growth in the number of their transactions. A major factor in this growth is the changing nature of World Wide Web sites themselves. In the early phase of the World Wide Web, Web pages were comprised mainly of static content, such as text, images and links to other sites. The extent of the user's interaction with a Web site was to download an HTML page and its elements. Since the content was usually the same regardless of who requested the page, it was comparatively simple for the Web server to support numerous users. The present trend however, is toward interactive Web sites in which the content and appearance of the Web site change in response to specific users and/or user input. This is particularly true for e-commerce sites, which support online product selection and purchasing. Such sites are distinguished from earlier Web sites by their greater dynamic content. A familiar example of this is the "online catalog" provided at many Internet business sites. Each customer logged onto the site to make a purchase has the opportunity to browse the catalog, and even peruse detailed information on thousands of products. Seemingly, the Web server must maintain and update a unique Web page for each shopper. Internet users enjoy the convenience of such customizable, interactive Web sites, and customer expectations will undoubtedly provide an impetus for further use of dynamic content in Web pages.

The burgeoning use of dynamic content in Internet Web pages causes certain logistical problems for the operators of Web sites. Today's e-commerce sites are characterized by extremely high "browse-to-buy ratios". For shopping sites, a typical ratio is 60 interactions that do not update permanent business records ("requests" or "queries") to each one that does ("transactions")--browsing a product description is an example of a request, while making a purchase exemplifies a transaction. One effect of the increasing prevalence of dynamic content is that, although the number of transactions is growing at a predictable and manageable rate, the number of requests is growing explosively. The high user-interactivity of Web pages containing dynamic content is responsible for the large number of requests per transaction. The dynamic content within those Web pages is typically generated each time that a user requests to browse one of these Web pages. This results in a tremendous amount of content that must be prepared and conveyed to the user during a single session.

User expectations compel the site provider to provide dynamic Web content promptly in response to their requests. If potential customers perceive the Web site as too slow, they may cease visiting the site, resulting in lost business. However, dealing with the sheer volume of Internet traffic may impose an inordinate financial burden on an e-business. The most straightforward way for an e-business to meet the increasing demand for information by potential customers is to augment its server-side hardware by adding more computers, storage, and bandwidth. This solution can be prohibitively expensive and inefficient.

A more cost effective approach is caching, a technique commonly employed in digital computers to enhance performance. The main memory used in a computer for data storage is typically much slower than the processor. To accommodate the slower memory during a data access, wait states are customarily added to the processor's normal instruction timing. If the processor were required to always access data from the main memory, its performance would suffer significantly. Caching utilizes a small but extremely fast memory buffer, termed a "cache", to capture the advantage of a statistical characteristic known as "data locality" in order to overcome the main memory access bottleneck. Data locality refers to the common tendency for consecutive data accesses to involve the same general region of memory. This is sometimes stated in terms of the "80/20" rule in which 80% of the data accesses are to the same 20% of memory.

The following example, although not Web-related, illustrates the benefits of caching in general. Assume one has a computer program to multiply two large arrays of numbers and wants to consider ways the computer might be modified to allow it to run the program faster. The most straightforward modification would be to increase the speed of the processor, which has limitations. Each individual multiply operation in the program requires the processor to fetch two operands from memory, compute the product, and then write the result back to memory. At higher processor speeds, as the time required for the computation becomes less significant, the limiting factor becomes the time required for the processor to interact with memory. Although faster memory could be used, the use of a large amount of extremely high-speed memory for all of the computer's memory needs would be too impractical and too expensive. Fortunately, the matrix multiplication program exhibits high data locality since the elements of each of the two input arrays occupy consecutive addresses within a certain range of memory. Therefore, instead of using a large amount of extremely high-speed memory, a small amount of it is employed as a cache. At the start of the program, the input arrays from the main memory are transferred to the cache buffer. While the program executes, the processor fetches operands from the cache and writes back corresponding results to the cache. Since data accesses use the high-speed cache, the processor is able to execute the program much faster than if it had used main memory. In fact, the use of cache results in a speed improvement nearly as great as if the entire main memory were upgraded but at a significantly lower cost. Note that a cache system is beneficial only in situations where the assumption of data locality is justified; if the processor frequently has to go outside the cache for data, the speed advantage of the cache disappears.

Another issue connected with the use of a data cache is "cache coherency." As described above, data are typically copied to a cache to permit faster access. Each datum in the cache is an identical copy of the original version in main memory. A problem can arise if one application within the computer accesses a variable in main memory while another application accesses the copy in the cache. If either version of the variable is changed independently of the other, the cache loses coherency with potentially harmful results. For example, if the variable is a pointer to critical operating system data, a fatal error may occur. To avoid this, the state of the cache must be monitored. When data in the cache is modified, the "stale" copies in the main memory are temporarily invalidated until they can be updated. Hence, an important aspect of any cache-equipped system is a process to maintain cache coherency.

In view of these well-known issues and benefits, caches have been implemented within data processing systems at various locations within the Internet or within private networks, including so-called Content Delivery Networks (CDNs). As it turns out, Web traffic is well-suited to caching. The majority of e-commerce Internet traffic consists of data that is sent from the server to the user rather than vice versa. In most cases, the user requests information from a Web site, and the user sends information to the Web site relatively infrequently. For example, a user frequently requests Web pages and relatively infrequently submits personal information or transactional information that is stored at the Web site. Hence, the majority of the data traffic displays good cache coherency characteristics. Moreover, the majority of the data traffic displays good data locality characteristics because a user tends to browse and re-browse the content of a single Web site for some period of time before moving to a different Web site. In addition, many users tend to request the same information, and it would be more efficient to cache the information at some point than to repeatedly retrieve it from a database. Additionally, most web applications can tolerate some slack in how up-to-date the data is. For example, when a product price is changed, it may be tolerable to have a few minutes of delay for the change to take effect, i.e. cache coherency can be less than perfect, which also makes caching more valuable.

The benefits of caching Web content can be broadly illustrated in the following discussion. Each request from a client browser may flow through multiple data processing systems that are located throughout the Internet, such as firewalls, routers, and various types of servers, such as intermediate servers, presentation servers (e.g., reading static content, building dynamic pages), application servers (e.g., retrieving data for pages, performing updates), and backend servers (e.g., databases, services, and legacy applications). Each of these processing stages has associated cost and performance considerations.

If there is no caching at all, then all requests flow through to the presentation servers, which can satisfy some requests because they do not require dynamic content. Unfortunately, many requests also require processing from the application servers and backend servers to make updates or to obtain data for dynamic content pages.

However, a request need only propagate as far as is necessary to be satisfied, and performance can be increased with the use of caches, particularly within the application provider's site. For example, caching in an intermediate server may satisfy a majority of the requests so that only a minority of the requests propagate to the presentation servers. Caching in the presentation servers may handle some of the requests that reach the presentation servers, so that only a minority of the requests propagate to the application servers. Since an application server is typically transactional, limited caching can be accomplished within an application server. Overall, however, a significant cost savings can be achieved with a moderate use of caches within an application provider's site.

Given the advantages of caching, one can improve the responsiveness of a Web site that contains dynamic Web content by using caching techniques without the large investment in servers and other hardware that was mentioned above. However, a major consideration for the suitability of caching is the frequency with which the Web content changes. In general, the implementation of a cache becomes feasible as the access rate increases and the update rate decreases. More specifically, the caching of Web content is feasible when the user frequently retrieves static content from a Web site and infrequently sends data to be stored at the Web site. However, if the Web site comprises a significant amount of dynamic content, then the Web site is inherently configured such that its content changes frequently. In this case, the update rate of a cache within the Web site increases significantly, thereby nullifying the advantages of attempting to cache the Web site's content.

Various solutions for efficiently caching dynamic content within enterprises have been proposed and/or implemented. These techniques for caching Web content within a Web application server have significantly improved performance in terms of throughput and response times.

After gaining significant advantages of caching dynamic content within e-business Web sites, it would be advantageous to implement cooperative caches throughout networks themselves, so-called "distributed caching", because caching content closer to the user could yield much more significant benefits in response time or latency. However, well-known caching issues would have to be considered for a distributed caching solution. Indiscriminate placement and implementation of caches may increase performance in a way that is not cost-effective. Important issues that determine the effectiveness of a cache include the cache size, the cache hit path length, the amount of work required to maintain the cache contents, and the distance between the data requester and the location of the data.

With respect to cache size, memories and disk space continue to increase in size, but they are never big enough such that one does not need to consider their limitations. In other words, a distributed caching technique should not assume that large amounts of memory and disk space are available for a cache, and the need for a small cache is generally preferable to the need for a large cache. In addition, the bandwidth of memories and disks is improving at a slower rate than their sizes is increasing, and any attempt to cache larger and larger amounts of data will eventually be limited by bandwidth considerations.

With respect to cache hit path length, a distributed caching solution should preferably comprise a lightweight runtime application that can be deployed easily yet determine cache hits with a minimum amount of processing such that the throughput of cache hits is very large. The desired form of a distributed caching application should not be confused with other forms of distributed applications that also "cache" data close to end-users. In other words, there are other forms of applications that benefit from one of many ways of distributing parts of an application and its associated data throughout the Internet. For example, an entire application and its associated databases can be replicated in different locations, and the deploying enterprise can then synchronize the databases and maintain the applications as necessary. In other cases, the read-only display portion of an application and its associated data can be distributed to client-based browsers using plug-ins, JavaScript.TM., or similar mechanisms while keeping business logic at a protected host site.

With respect to the amount of work required to maintain the cache contents, caching within the serving enterprise improves either throughput or cost, i.e. the number of requests that are processed per second or the amount of required server hardware, because less work is done per request. Within the serving enterprise, the cache is preferably located closer to the entry point of the enterprise because the amount of processing by any systems within the enterprise is reduced, thereby increasing any improvements. For example, caching near a dispatcher can be much more effective than caching within an application server. Caching within the serving enterprise improves latency somewhat, but this is typically secondary because the latency within the serving enterprise is typically much smaller than the latency across the internet. Considerations for a robust distributed caching technique outside of the serving enterprise is intertwined with this and other issues.

With respect to the distance between the data requester and the location of the data, user-visible latency in the Internet is dominated by the distance between the user and the content. This distance is measured more by the number of routing hops than by physical distance. When content is cached at the "boundaries" of the Internet, such as Internet Service Providers (ISPs), user-visible latency is significantly reduced. For large content, such as multimedia files, bandwidth requirements can also be significantly reduced. A robust distributed caching solution should attempt to cache data close to users.

Since users are geographically spread out, caching content close to users means that the content has to be replicated in multiple caches at ISPs and exchange points throughout the internet. In general, this can reduce the control that the caching mechanism has over the security of the content and the manner in which the content is updated, i.e. cache coherency. One can maintain a coherent cache within a serving enterprise relatively easily given the fact that the caching mechanism within the serving enterprise is ostensibly under the control of a single organization. However, maintaining caches both inside and outside of the serving enterprise significantly increases the difficulty and the amount of work that is required to ensure cache coherency. Although the security and coherency considerations can be minimized if content distribution vendors, e.g., CDNs, are used in which cache space is rented and maintained within a much more controlled network environment than the public Internet, such solutions effectively nullify some of the advantages that are obtained through the use of open standards through the public Internet.

Preferably, a distributed caching technique should be implementable with some regard to enterprise boundaries yet also implementable throughout the Internet in a coordinated manner. In addition, caches should be deployable at a variety of important locations as may be determined to be necessary, such as near an end-user, e.g., in a client browser, near a serving enterprise's dispatcher, within a Web application server, or anywhere in between. Moreover, the technique should adhere to specifications such that different organizations can construct different implementations of a distributed caching specification in accordance with local system requirements.

The issues regarding any potentially robust distributed caching solution are complicated by the trend toward authoring and publishing Web content as fragments. A portion of content is placed into a fragment, and larger content entities, such as Web pages or other documents, are composed of fragments, although a content entity may be composed of a single fragment. Fragments can be stored separately and then assembled into a larger content entity when it is needed.

These runtime advantages are offset by the complexity in other aspects of maintaining and using fragments. Fragments can be assigned different lifetimes, thereby requiring a consistent invalidation mechanism. In addition, while fragments can be used to separate static portions of content from dynamic portions of content so that static content can be efficiently cached, one is confronted with the issues related to the caching of dynamic content, as discussed above. Most importantly, fragment assembly has been limited to locations within enterprise boundaries.

Therefore, it would be advantageous to have a robust distributed caching technique that supports caching of fragments and other objects. Moreover, it would be particularly advantageous to co-locate fragment assembly at cache sites throughout a network with either much regard or little regard for enterprise boundaries as is deemed necessary, thereby reducing processing loads on a serving enterprise and achieving additional benefits of distributed computing when desired. In addition, it would be advantageous to have a consistent naming technique such that fragments can be uniquely identified throughout the Internet, i.e. so that the distributed caches are maintained coherently.

As a further consideration for a robust distributed caching solution, any potential solution should consider the issue of existing programming models. For example, one could propose a distributed caching technique that required the replacement of an existing Web application server's programming model with a new programming model that works in conjunction with the distributed caching technique. Preferably, an implementation of a distributed caching technique would accommodate various programming models, thereby avoiding any favoritism among programming models.

It would be advantageous that an implementation of the distributed caching technique resulted in reduced fragment cache sizes that are maintainable by lightweight processes in a standard manner throughout the Internet with minimal regard to cache location. In addition, it would be particularly advantageous for the distributed caching technique to be compatible with existing programming models and Internet standards such that an implementation of the distributed caching technique is interoperable with other systems that have not implemented the distributed caching technique.

SUMMARY OF THE INVENTION

A method, a system, an apparatus, and a computer program product are presented for a fragment caching methodology. After a message is received at a computing device that contains a cache management unit, a fragment in the message body of the message is cached. Subsequent requests for the fragment at the cache management unit result in a cache hit. The cache management unit operates equivalently in support of fragment caching operations without regard to whether the computing device acts as a client, a server, or a hub located throughout the network; in other words, the fragment caching methodology is uniform throughout a network.

A FRAGMENT header is defined to be used within a network protocol, such as HTTP; the header associates metadata with a fragment for various purposes related to the processing and caching of a fragment. Cache ID rules accompany a fragment from an origin server; the cache ID rules describe a method for forming a unique cache ID for the fragment such that dynamic content can be cached away from an origin server. A cache ID may be based on a URI (Uniform Resource Identifier) for a fragment, but the cache ID may also be based on query parameters and/or cookies. Dependency IDs, which may differ from a cache ID or a URI for a fragment, may be associated with a fragment so that a server may initiate an invalidation operation that purges a fragment from a cache.

A FRAGMENTLINK tag is used to specify the location in a fragment for an included or linked fragment which is to be inserted into the fragment during fragment or page assembly or page rendering. If a FRAGMENTLINK tag is present within the message body of a message, then the FRAGMENT message header for the message indicates the presence of the FRAGMENTLINK tag with a directive for the FRAGMENT message header, e.g., using a "contains-fragment" directive.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, further objectives, and advantages thereof, will be best understood by reference to the following detailed description when read in conjunction with the accompanying drawings, wherein:

FIG. 1A depicts a typical distributed data processing system in which the present invention may be implemented;

FIG. 1B depicts a typical computer architecture that may be used within a data processing system in which the present invention may be implemented;

FIG. 1C depicts a typical distributed data processing system in which caches are implemented throughout a distributed data processing system;

FIG. 2 illustrates a typical Web page composed of fragments;

FIG. 3 is a formal Standard Generalized Markup Language (SGML) definition of the FRAGMENTLINK tag in accordance with a preferred embodiment of the present invention;

FIG. 4 is a formal definition of the FRAGMENT header in accordance with a preferred embodiment of the present invention;

FIGS. 5A-5G depict a set of fragment-supporting and non-fragment-supporting agents along object retrieval paths;

FIG. 6A depicts a cache management unit for a fragment-supporting cache within a computing device;

FIG. 6B is a flowchart that depicts a process that may be used by a fragment-supporting cache management unit when processing response messages that contain fragments;

FIG. 6C is a flowchart step that depicts a preferred method for determining whether or not a message body contains a fragment object;

FIG. 6D is a flowchart step that depicts a more particular method for determining whether or not a fragment object is cacheable;

FIG. 6E is a flowchart step that depicts a preferred method for determining whether or not a fragment object is cacheable;

FIG. 6F, a flowchart that depicts a method for determining whether or not a fragment object should be cached at a particular computing device;

FIG. 6G is a flowchart step that depicts a preferred method for determining whether or not a downstream device has a fragment-supporting cache;

FIG. 6H is a flowchart step that depicts a more particular method for determining whether or not the fragment object that is currently being processed should only be cached in the fragment-supporting cache that is closest to the destination user/client device;

FIG. 6I is a flowchart step that depicts a preferred method for determining whether or not the fragment object that is currently being processed should only be cached in the fragment-supporting cache that is closest to the destination user/client device;

FIG. 6J is a flowchart that depicts a method for determining whether or not page assembly is required prior to returning a response message from the current computing device;

FIG. 6K is a flowchart step that depicts a more particular method for determining whether or not the fragment object that is currently being processed has a link to another fragment;

FIG. 6L is a flowchart step that depicts an alternate method for determining whether or not the fragment object that is currently being processed has a link to another fragment;

FIG. 6M is a flowchart that depicts a process for performing page assembly;

FIG. 6N is a flowchart that depicts a process for optionally expanding a fragment link to multiple fragment links;

FIG. 6O is a flowchart step that depicts a preferred method for determining whether or not the fragment link in the current fragment from the response message indicates that it should be expanded to multiple fragment links;

FIG. 6P is a flowchart that depicts a process for expanding a fragment link to multiple fragment links in accordance with information associated with the fragment link;

FIG. 6Q is a flowchart that depicts a process for retrieving a fragment using a source identifier for the fragment;

FIG. 6R is a flowchart that depicts some of the processing that is performed when a fragment is cached within a fragment-supporting cache management unit;

FIG. 6S is a flowchart that depicts a process that may be used by a fragment-supporting cache management unit to obtain a fragment if it is cached at a computing device that contains the cache management unit;

FIG. 6T is a flowchart that depicts a process for combining header values and property values associated with a plurality of fragments;

FIG. 6U is a flowchart that depicts a set of steps that represent a series of combining functions for header types and property values;

FIG. 6V is a flowchart that depicts a process that may be used by a fragment-supporting cache management unit when processing request messages;

FIG. 6W is a flowchart that depicts a process that may be used by a fragment-supporting cache management unit when processing invalidation messages in accordance with an implementation of the present invention;

FIG. 7A is a block diagram that depicts some of the dataflow between a Web application server and a client in order to illustrate when some caches perform fragment assembly;

FIG. 7B is a block diagram that depicts some of the dataflow between a Web application server and a client in order to illustrate how a set of devices can be directed to cache fragments in a cache that is closest to an end-user or client device;

FIGS. 8A-8D are dataflow diagrams that depict some of the processing steps that occur within a client, an intermediate fragment-supporting cache, or a server to illustrate that caching of dynamic role-specific or category-specific content can be achieved using the present invention;

FIG. 9A is a flowchart that depicts a process by which multiple fragments can be specified in a single request message and subsequently processed;

FIG. 9B is a flowchart depicts a process by which a single request message can be received at an intermediate cache management unit and subsequently processed;

FIG. 9C is a flowchart that depicts a process at a Web application server for processing a batch request message for multiple fragments;

FIGS. 10A-10D are a set of examples that show the advantageous cache size reduction that can be achieved with the present invention; and

FIGS. 11A-11H are a series of diagrams that illustrate the manner in which the technique of the present invention constructs and uses unique cache identifiers for storing and processing fragments.

DETAILED DESCRIPTION OF THE INVENTION

The present invention is directed to a distributed fragment caching technique. In general, the devices that may comprise or relate to the present invention include a wide variety of data processing technology. Therefore, as background, a typical organization of hardware and software components within a distributed data processing system is described prior to describing the present invention in more detail.

With reference now to the figures, FIG. 1A depicts a typical network of data processing systems, each of which may implement some aspect of the present invention. Distributed data processing system 100 contains network 101, which is a medium that may be used to provide communications links between various devices and computers connected together within distributed data processing system 100. Network 101 may include permanent connections, such as wire or fiber optic cables, or temporary connections made through telephone or wireless communications. In the depicted example, server 102 and server 103 are connected to network 101 along with storage unit 104. In addition, clients 105-107 also are connected to network 101. Clients 105-107 and servers 102-103 may be represented by a variety of computing devices, such as mainframes, personal computers, personal digital assistants (PDAs), etc. Distributed data processing system 100 may include additional servers, clients, routers, other devices, and peer-to-peer architectures that are not shown. It should be noted that the distributed data processing system shown in FIG. 1A is contemplated as being fully able to support a variety of peer-to-peer subnets and peer-to-peer services.

In the depicted example, distributed data processing system 100 may include the Internet with network 101 representing a global collection of networks and gateways that use various protocols to communicate with one another, such as Lightweight Directory Access Protocol (LDAP), Transport Control Protocol/Internet Protocol (TCP/IP), Hypertext Transport Protocol (HTTP), Wireless Application Protocol (WAP), etc. Of course, distributed data processing system 100 may also include a number of different types of networks, such as, for example, an intranet, a local area network (LAN), a wireless LAN, or a wide area network (WAN). For example, server 102 directly supports client 109 and network 110, which incorporates wireless communication links. Network-enabled phone 111 connects to network 110 through wireless link 112, and PDA 113 connects to network 110 through wireless link 114. Phone 111 and PDA 113 can also directly transfer data between themselves across wireless link 115 using an appropriate technology, such as Bluetooth.TM. wireless technology, to create so-called personal area networks (PAN) or personal ad-hoc networks. In a similar manner, PDA 113 can transfer data to PDA 107 via wireless communication link 116.

The present invention could be implemented on a variety of hardware platforms; FIG. 1A is intended as an example of a heterogeneous computing environment and not as an architectural limitation for the present invention. It should be noted that the subsequent examples specifically refer to client-type functionality as compared to server-type functionality. However, as is well-known, some computing devices exhibit both client-type functionality and server-type functionality, such as hubs or computing devices, i.e. peers, within a peer-to-peer network. The present invention is able to be implemented on clients, servers, peers, or hubs as necessary.

With reference now to FIG. 1B, a diagram depicts a typical computer architecture of a data processing system, such as those shown in FIG. 1A, in which the present invention may be implemented. Data processing system 120 contains one or more central processing units (CPUs) 122 connected to internal system bus 123, which interconnects random access memory (RAM) 124, read-only memory 126, and input/output adapter 128, which supports various I/O devices, such as printer 130, disk units 132, or other devices not shown, such as a audio output system, etc. System bus 123 also connects communication adapter 134 that provides access to communication link 136. User interface adapter 148 connects various user devices, such as keyboard 140, mouse 142, or other devices not shown, such as a touch screen, stylus, or microphone. Display adapter 144 connects system bus 123 to display 146.

Those of ordinary skill in the art will appreciate that the hardware in FIG. 1B may vary depending on the system implementation. For example, the system may have one or more processors, such as an Intel.RTM. Pentium.RTM.-based processor and a digital signal processor (DSP), and one or more types of volatile and non-volatile memory. Other peripheral devices may be used in addition to or in place of the hardware depicted in FIG. 1B. In other words, one of ordinary skill in the art would expect to find some similar components or architectures within a Web-enabled or network-enabled phone and a fully featured desktop workstation. The depicted examples are not meant to imply architectural limitations with respect to the present invention.

In addition to being able to be implemented on a variety of hardware platforms, the present invention may be implemented in a variety of software environments. A typical operating system may be used to control program execution within each data processing system. For example, one device may run a Linux.RTM. operating system, while another device contains a simple Java.RTM. runtime environment. A representative computer platform may include a browser, which is a well-known software application for accessing files, documents, objects, or other data items in a variety of formats and encodings, such as graphic files, word processing files, Extensible Markup Language (XML), Hypertext Markup Language (HTML), Handheld Device Markup Language (HDML), Wireless Markup Language (WML). These objects are typically addressed using a Uniform Resource Identifier (URI). The set of URIs comprises Uniform Resource Locators (URLs) and Uniform Resource Names (URNs).

With reference now to FIG. 1C, a diagram depicts a typical distributed data processing system, such as the one shown in FIG. 1A, in which caches are implemented throughout the distributed data processing system. Distributed data processing system 150 contains requesting entity 152 that generates requests for content. Requesting entity 152 may be an ISP that serves various individual or institutional customers or an enterprise that uses the requested content for various purposes. As data, e.g., a request, moves from the requesting entity (using entity) toward the responding entity (serving entity, e.g., an origin server), the data is described as moving "upstream". As data, e.g., a response, moves from the responding entity toward the receiving entity, the data is described as moving "downstream".

Requests from client browsers 154 are routed by dispatcher 156, which evenly distributes the requests through a set of intermediate servers 158 in an attempt to satisfy the requests prior to forwarding the requests through the Internet at Internet exchange point 160. Each browser 154 may maintain a local cache, and each server 158 supports a forward proxy caching mechanism. Internet exchange point 160 also contains intermediate servers 162 and 164, each of which may maintain a cache. Various considerations for implementing a cache in browsers 154 or in intermediate servers 158, 160, 162, and 164 include improving response times and/or reducing bandwidth.

Requests are then routed from Internet exchange point 160 to dispatcher 166 in serving enterprise 168. Dispatcher 166 evenly distributes incoming requests through intermediate servers 170 that attempt to satisfy the requests prior to forwarding the requests to dispatcher 172; each intermediate server 170 supports a reverse proxy caching mechanism. Unfulfilled requests are evenly distributed by dispatcher 172 across Web application servers 174, which are able to ultimately satisfy a request in conjunction with database services or other applications that access database 176. Various considerations for implementing a cache in intermediate servers 170 or in Web application servers 174 include improving throughput and/or reducing costs.

Responses are routed in the opposite direction from the serving enterprise to a client device. It should be noted that similar intermediate servers can be deployed within the using enterprise, throughout the Internet, or within the serving enterprise. It should also be noted that each successive stage away from the client through which a request passes adds to the perceived response time.

The present invention may be implemented on a variety of hardware and software platforms, as described above. More specifically, though, the present invention is directed to a distributed fragment caching technique. Before describing the present invention in more detail, though, some background information is provided on static and dynamic Web content in general.

The format of Web pages containing static text and graphic content is typically specified using markup languages, such as HTML. The markup consists of special codes or tags which control the display of words and images when the page is read by an Internet browser. However, Java Server Pages (JSPs) and servlets are more suitable for Web pages containing dynamic content.

Basically, a JSP is a markup language document with embedded instructions that describe how to process a request for the page in order to generate a response that includes the page. The description intermixes static template content with dynamic actions implemented as Java code within a single document. Using JSP, one can also inline Java code into the page as server-side scriptlets. In other words, Java tags are specified on a Web page and run on the Web server to modify the Web page before it is sent to the user who requested it. This approach is appropriate when the programming logic is relatively minor. Having any more than a trivial amount of programming logic inside the markup language document defeats the advantages of JSP: separating the presentation of a document from the business logic that is associated with the document. To avoid inlining excessive amounts of code directly into the markup language document, JSP enables the ability to isolate business logic into JavaBeans which can be accessed at runtime using simple JSP tags.

More specifically, a JSP uses markup-like tags and scriptlets written in the Java programming language to encapsulate the logic that generates some or all of the content for the page. The application logic can reside in server-based resources, such as JavaBean components, that the page accesses with these tags and scriptlets. Use of markup language tags permits the encapsulation within a markup language document of useful functionality in a convenient form that can also be manipulated by tools, e.g., HTML page builders/editors. By separating the business logic from the presentation, a reusable component-based design is supported. JSP enables Web page authors to insert dynamic content modules into static HTML templates, thus greatly simplifying the creation of Web content. JSP is an integral part of Sun's Java Enterprise Edition (J2EE) programming model.

It should be noted that although the examples of the present invention that are discussed below may employ JSPs, the present invention is not restricted to this embodiment. Other types of server pages, e.g., Microsoft's Active Server Pages (ASPs), could also be employed.

A product display JSP presents data about products. A request for a particular product, e.g., a wrench, will identify that JSP as well as a product id as a query parameter. An execution of that JSP with a product id parameter outputs a page of HTML. When the underlying data for that product changes, e.g., the wrench price increases, that page should be invalidated. To do this, a dependency must be established between the page and the data by associating a dependency id that represents the data with the page.

Granularity is a characteristic of Web pages that is important to an efficient caching strategy. The content of a Web page is comprised of several components, some of which may change frequently while others are relatively static. The granularity of a Web page may be described in terms of "fragments", which are portions of content. A fragment can be created in a variety of manners, including fulfilling an HTTP request for a JSP file. In the above example, the product display page is a single fragment page.

With reference now to FIG. 2, a block diagram illustrates a Web page composed of fragments. This example illustrates that fragment granularity permits portions of a page to be cached even though some fragments are volatile and are known to be updated on some temporal basis. In other words, various types of Web content benefit to different degrees from caching.

A product display Web page comprises dynamic content fragments 200. The top-level fragment is a Java Server Page (JSP) 204, which contains five child fragments 206-214. Fragments 208 and 212 are cached. It should be noted that the child fragments are arranged from left to right in order of increasing rate of change in their underlying data, as indicated by the timeline in the figure.

Product URI 206 is a Uniform Resource Identifier (URI) link to a Graphics Interchange Format (GIF or .gif) image file of the product. A formatted table may hold detailed product description 208. A fragment which displays personalized greeting 210 may use a shopper name. This greeting changes often, e.g., for every user, but it may still be helpful to cache it since a given shopper name will be reused over the course of a session by the same user.

JSP 212 creates an abbreviated shopping cart. Shopping cart JSP 212 may create an HTML table to display the data. This content will change even more frequently than personalized greeting 210 since it should be updated every time the shopper adds something to his cart. Nevertheless, if the shopping cart appears on every page returned to the shopper, it is more efficient to cache JSP 212 than to retrieve the same data each time the cart is displayed. JSP 204 might also contain advertisement 214 appearing on the Web page which displays a stock watch list. Since the advertisement changes each time the page is requested, the update rate would be too high to benefit from caching.

FIGS. 1A-2 show various distributed data processing systems and an example of dynamic content as a background context for the discussion of the present invention. As mentioned above, it can be difficult to efficiently cache fragments. The present invention is directed to a technique that uses extensions to HTML and HTTP for efficiently caching fragments with particular attention to overcoming the difficulties associated with caching dynamic fragments and personalized fragments, i.e. dynamic content. A formalized introduction to the technique of the present invention is first presented, which is then followed by a description of some examples that use the technique of the present invention.

It should be noted that the examples provided below mention specific specifications of protocols, such as HTTP/1.1 and HTML 4.1. However, one of ordinary skill in the art would appreciate that the present invention may operate in conjunction with other proto