WO2001013600A1

WO2001013600A1 - Caching data in a network

Info

Publication number: WO2001013600A1
Application number: PCT/US2000/022415
Authority: WO
Inventors: Hua Chen
Original assignee: Orblynx, Inc.
Priority date: 1999-08-16
Filing date: 2000-08-16
Publication date: 2001-02-22
Also published as: AU6909100A

Abstract

A push caching technique for data stored in a network is described in which a server system forces a cache system to store a new or updated entity regardless of whether an older copy is found in the cache. In one embodiment, a push control list is employed to check whether the server system has permission to make the update.

Description

CACHING DATA IN A NETWORK

RELATED APPLICATIONS

The present application claims the benefit of the following U.S. Provisional Patent Applications:

U.S. Provisional Patent Application Serial No. 60/148,760 entitled "Internet Delivery System" filed on August 16, 1999 by Hua Chen et al; and

U.S. Provisional Patent Application Serial No. 60/184,346 entitled "Internet Services Though a Multicast Network Overlay" filed on February 23, 2000 by H. Phillip Chen et /.

FIELD OF THE INVENTION

The present invention relates to networks and more particularly to caching data in a network.

BACKGROUND OF THE INVENTION The explosive growth in the usage of the World Wide Web is increasing demands for communications bandwidth at a global scale. For example, it has been reported that by 2001 the number of users of the World Wide Web will jump to 175 million users and the number of Web pages will increase to around 4.4 billion pages. This growth implies that the demand of bandwidth will far outpace the rate of physical network construction in the near further.

Traditional data transport on the World Wide Web is from a single server system to an individual end user over the Internet. This approach, however, will not scale to the projected size of the World Wide Web in the next few years, leading to the so-called Internet meltdowns as Web traffic skyrockets. As high-bandwidth audio and video streaming content, such as music and movies, becomes more popular and more frequently delivered over the Internet, the prognosis is even worse. Therefore, there is a dire need for new ways of thinking and new technologies to help alleviate the foreseeable bandwidth demands. One approach for alleviating bandwidth demands and thereby improve network performance is to employ a cache. A cache is a local memory for temporarily storing frequently used data. FIG. 4A depicts a typical cache configuration involving a client system 400 such as a browser at which the user is located, a server system 402 such as a web site at which content is located, and a cache system 404 interspersed between the client system 400 and the server system 402. The cache system 404 is commonly located on the same computer as the client system 400 or at an Internet Service Provider (ISP) (not shown) that the client system 400 is directly connected to, for example, by a modem line. When a user makes a request to access content located on the server system 402, the client system 400 formulates and transmits a "get" request 410 identifying an entity such as a web page, graphic, audio, or video, hosted on the server system 404 in accordance with an appropriate protocol such as the Hypertext Transfer Protocol (HTTP). In the arrangement illustrated in FIG. 4A, the get request 410 is intercepted by the cache system 404. In response to receiving the get request 410, the cache system 404 checks its local cache to determine if the cache system 404 is storing a copy of the requested entity. If the cache system 404 is indeed storing a copy of the requested entity, then the cache system 404 retrieves the entity from the local cache memory and transmits the cached entity 412 to the client system 400. If the entity is frequently accessed, then requests for the entity are serviced locally, out of the cache system 404, without having to fetch the entity over the Internet from the server system 402. Without the cache, the same entity would have been transmitted multiple times over the Internet, consuming valuable bandwidth for essentially redundant traffic.

For the cache to be effective, there must be a "cache hit," or, in other words, the requested entity must be found within the cache. On the other hand, if the requested entity, however, is not in the cache, which is referred to as a "cache miss," then the cache system 404 fetches the requested entity from the server system 402 by transmitting a get request 420 to the server system 402. In response, the server system 402 retrieves the requested entity from its file system and sends the retrieved entity 422 to the cache system 404, which stored the retrieved entity 422 in its cache and forwards the entity 412 to the client system 400. This method of populating a cache system 404 is called "pull caching," because the cache system 404 actively "pulls", i.e. requests and retrieves, entities to be placed in the cache.

The pull caching model, however, is not useful for content providers at server systems 402 who regularly update their old content and publish new content, particular if the content provider expects the latest content to be popular and frequently accessed. This latest content, of course, will not be found in the cache system 404, and it is desirable under certain circumstances, e.g. at off-peak times, to update the cache system 404 with the latest entities. In the pull caching model, however, the latest entities will not actually be transmitted to the cache system 404 until there is a request for that entity, which may occur at a peak usage time, thereby consuming bandwidth when that bandwidth is most needed.

Accordingly, there has been much interest in developing techniques to force the cache system 404 to pull the latest entities from the server system 402 at appropriate times. One of these techniques is illustrated in FIG. 4B, in which a cache adapter 406 is interspersed between the cache system 404 and the server system 402. A cache adapter 406 is an ancillary device that intercepts requests from the cache system 404 for special handling. In this scenario, the server system 402 transmits an updated or new entity 430 to the cache adapter 406, which in turn submits a get request 432 to the cache system 404 for that entity 430. The get request 432 is identical to a get request from a client system 400, and the cache system 404 behaves identically in response. In particular, the cache system 404 attempts to find the requested entity in its cache, and upon not finding the entity, the cache system 404 makes another get request 434. The cache adapter 406 intercepts this get request 434 and services the cache system 404 with a copy 436 of the updated or new entity 430.

While such a pull caching technique addresses the issue of populating a cache with a completely new entity (e.g. a new entity at a new network location), it incurs a disadvantage with an updated entity (e.g. a new entity at an old network location, which replaces an old entity). For example, the cache system 404 may already be storing an older copy of the updated entity. Thus, when there is a get request to fetch that entity, whether from a client system 400 or a cache adapter 406, the cache system 404 responds to the request with the older copy because there is a cache hit for that request and never pulls the newer copy at the server system 402 into the cache system 404 until a conditional request is received from a user. Consequently, pull caching techniques are prone to maintaining stale data longer than necessary. Workarounds have been developed to reduce this problem, but conventional workarounds are difficult to use. For example, one common workaround is to remove a cached entity from the cache system 404 after some period of time. Determining the right period of time for a particular entity is difficult, and wrong estimates about the useful life of the cached entity hampers network performance. If the period of time is too short, then there are too many cache misses, forcing additional and unnecessary network activity to fetch an unchanged entity. On the other hand, if the period of time is too long, then the cache system 404 is more likely to serve stale data. Therefore, there is a need for improving the accuracy of cache systems, for example, by not returning stale data. There is also a need for improving the hit rate of cache systems, for example, by not prematurely polling for entities that have not changed.

SUMMARY OF THE INVENTION

These and other needs are addressed by the present invention, in which a push caching technique is employed to force the cache system to store a new or updated entity regardless of whether an older copy is found in the cache. Thus, forcing the cache system to overwrite an older copy of an entity in response to a push cache with the server system has updated the entity, reduces the staleness of the cached data and improves accuracy of cache systems. Furthermore, the hit rate of cache systems is improved because valid copies of entities are not prematurely aged out of the cache because the useful life time of the entity was estimated too low.

Accordingly, one aspect of the invention relates to a method and software for maintaining data in a cache system located in a network. A request is received from a server system to update a cache maintained by the cache system. The request includes an entity such as a web page, a graphic, audio, video, etc., to be placed in the cache and a resource identifier such as a URL that indicates the location of the entity in the server system. In response to the request, the cache is updated by storing the entity in the cache in association with the resource identifier. By updating the cache in response to the request, stale data expunged from the cache system.

In a push caching system, it is desirable for security and data integrity reasons to ensure that server systems are not allowed to "update" to the data that belongs to other server systems. Accordingly, one embodiment of the invention involves a method and software maintaining data in a cache system located in a network. A request is received from a server system to update a cache maintained by the cache system, in which the request includes an entity to be placed in the cache and a resource identifier indicating a location of the entity in the network. If the server system is determined to be permitted to update the entity in the cache, then the cache is updated by storing the entity in the cache in association with the resource identifier. In one implementation, this determination is made by consulting a push control list that stores the locations of registered server systems. If the location of the registered server systems and the resource identifier match, then the server system is considered to have the permission to update the cache with respect to that entity.

Another aspect of the invention pertains to a method and software for publishing data from a server system in a network. The location of the server system is registered in a cache system, and a request is transmitted from the server system to the cache system to update a cache maintained by the cache system. The request includes an entity to be placed in the cache and a resource identifier indicating the location of the entity in the network. In one implementation, the request is made in response to an updating of the entity.

Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 depicts a computer system upon which embodiments of the present invention may be implemented.

FIG. 2 illustrates a network and data flow in accordance with one embodiment of the present invention.

FIGS. 3A and 3B together constitute is a flow diagram illustrating the operation of an embodiment of the present invention.

FIG. 4A illustrates one conventional caching approach.

FIG. 4B illustrates another conventional caching approach.

DESCRIPTION OF THE PREFERRED EMBODIMENT

A methodology for caching data in a network is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

HARDWARE OVERVIEW

Figure 1 is a block diagram that illustrates a computer system 100 upon which an embodiment of the invention may be implemented. Computer system 100 includes a bus 102 or other communication mechanism for communicating information, and a processor

104 coupled with bus 102 for processing information. Computer system 100 also includes a main memory 106, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 102 for storing information and instructions to be executed by processor 104. Main memory 106 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 104. Computer system 100 further includes a read only memory (ROM) 108 or other static storage device coupled to bus 102 for storing static information and instructions for processor 104. A storage device 110, such as a magnetic disk or optical disk, is provided and coupled to bus 102 for storing information and instructions.

Computer system 100 may be coupled via bus 102 to a display 112, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 114, including alphanumeric and other keys, is coupled to bus 102 for communicating information and command selections to processor 104. Another type of user input device is cursor control 116, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 104 and for controlling cursor movement on display 112. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

The invention is related to the use of computer system 100 for caching data in a network. According to one embodiment of the invention, caching data in a network is provided by computer system 100 in response to processor 104 executing one or more sequences of one or more instructions contained in main memory 106. Such instructions may be read into main memory 106 from another computer-readable medium, such as storage device 110. Execution of the sequences of instructions contained in main memory 106 causes processor 104 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory 106. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software. The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to processor 104 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 110. Volatile media include dynamic memory, such as main memory 106. Transmission media include coaxial cables, copper wire and fiber optics, including the wires that comprise bus 102. Transmission media can also take the form of acoustic or light waves, such as those generated during radio frequency (RF) and infrared (IR) data communications. Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read. Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 104 for execution. For example, the instructions may initially be borne on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 100 can receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector coupled to bus 102 can receive the data carried in the infrared signal and place the data on bus 102. Bus 102 carries the data to main memory 106, from which processor 104 retrieves and executes the instructions. The instructions received by main memory 106 may optionally be stored on storage device 110 either before or after execution by processor 104.

Computer system 100 also includes a communication interface 118 coupled to bus 102. Communication interface 118 provides a two-way data communication coupling to a network link 120 that is connected to a local network 122. For example, communication interface 118 may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 118 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 118 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link 120 typically provides data communication through one or more networks to other data devices. For example, network link 120 may provide a connection through local network 122 to a host computer 124 or to data equipment operated by an Internet Service Provider (ISP) 126. ISP 126 in turn provides data communication services through the worldwide packet data communication network, now commonly referred to as the "Internet" 128. Local network 122 and Internet 128 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 120 and through communication interface 118, which carry the digital data to and from computer system 100, are exemplary forms of carrier waves transporting the information.

Computer system 100 can send messages and receive data, including program code, through the network(s), network link 120, and communication interface 118. In the Internet example, a server 130 might transmit a requested code for an application program through Internet 128, ISP 126, local network 122 and communication interface 118. In accordance with the invention, one such downloaded application provides for caching data in a network as described herein. The received code may be executed by processor 104 as it is received, and/or stored in storage device 110, or other non- volatile storage for later execution. In this manner, computer system 100 may obtain application code in the form of a carrier wave.

PUSH CACHING

FIG. 2 depicts a network arrangement in which one embodiment of the present invention may be employed. In this arrangement, there is a client system 200, such as a computer system at which a user is utilizing a web browser, and a server system 202, such as computer system for a web site of a content provider that hosts content that users are interested. The server system 202 can be a web server responsible for servicing requests, or a publish utility agent or application service provider that is responsible for proactively disseminating content. Like other caching arrangements, a cache system 204 may be provided between the client system 200 and the server system 202, and in various implementation may be located at the computer system for the client system 200 or an ISP (not shown).

The cache system 204 is typically implemented in software on a computer system to temporarily store entities in a storage device. These entities may include a web page (e.g. text), graphics (GIF files for drawings and JPEG files for photographs), audio such as music, and video. The present invention, of course, is not limited to the particular types of entities cached.

Moreover, the cache system 204 stores the entities in association with the host location of the entity in the Internet. The location of the entity is preferably given by a Uniform Resource Identifier (URI) such as a Uniform Resource Locator (URL), which identifies the server system 204 that is hosting the entity. The cache system 204 may employ hashing and compression techniques that make it difficult to add new entities in the file system managed by the cache system 204 except through a defined interface.

For one embodiment of the invention, the interface and software of the cache system 204 is extended to accepted a new "push" message 210 that is compatible in syntax with existing Hypertext Transfer Protocol (HTTP) messages. The push message 210 specifies the URI of the entity as well as the entity 212 itself. In one implementation, the push message has the following format, where "URL" stands for the resource identifier of the entity and the [Entity Body] stands for the content of the entity:

PUSH URL HTTP/version<crlf>

[Request Header]

(empty line)

[Entity Body]

Accordingly, the cache system 204 is adapted to accept the push message 210, and, in response to the push message, update or store the cache entry for the specified entity 212 (e.g. based on the URI) regardless of whether there is an older version of the entity already in the cache. Thus, updating the entity in the cache entry regardless of whether the entity is already in the cache, in contrast with a conventional get message, helps ensure that the cached entity is not stale after the push message. By contrast, a conventional get message does not cause the entry corresponding to the entity to be updated during a preset, arbitrary expiration period that is difficult to predict for all entities.

Referring to FIG. 3 A in conjunction with FIG. 2, the operation of one embodiment of the present invention starts at block 300, in which a server system 202 is registered for push caching at cache system 204. When a server system 202 is registered for push caching at the cache system 204, the location of the server system 202 is stored in a push control list at the cache system 204 (block 302). The push control list is a data structure that records the locations (e.g. IP address) of registered server systems. This registration may be performed manually or may be performed automatically in response to a message, e.g. an email, or remote procedure call, sent from the server system 202 to the cache system 204 directing the registration.

At block 310, the server system 202 publishes new content, causing a push message 210 to be sent to the cache system 204 with a URL that identifies the published entity 212 contained in the body of the push message 210. In response, at block 312, the cache system 204 checks to determine if the server system 202 is permitted to update the cache entry for that particular entity 212. In one embodiment, the cache system 204 checks the push control list to determine if the location of the server system 202 and the location of the entity 212 match, for example, by comparing the respective locations. In some implementations, a password is also used for verifying the authenticity of the server system 202 to prevent spoofing.

If the server system 202 is not permitted to perform the push cache operation for that particular object, then execution proceeds to block 314 where an error code is returned. On the other hand, if the server system 202 is indeed permitted to perform the push cache operation for that particular object, then execution branches to block 316, in which the entity is placed in the cache maintained by the cache system 204. When the content has changed, block 318 directs execution back to block 310 where the content is republished. This operation may be manual, for example at the command line, or automatically in response to a modification of the content at the server system 202, or based on a regularly scheduled interval, for example, via a UNIX™ crontab file. When the push message is sent in response to a modification of the content, e.g. in response to a modification event, the content is transmitted to the cache system 204 and updated in the cache system 204 regardless of whether an older copy of the content was already present in the cache system. By this mechanism, the most recent version of an entity holding content is disseminated throughout the network so that cache systems do not return stale content.

Later, with reference now to FIG. 3B, when a user at client system 200 makes a request 220 to get that entity, the get request 220 at block 320 is transmitted to the cache system 204, which intercepts the get request 220. In response, the cache system 204 inspects its cache to determine if the entity identified in the get request 220 is stored in the cache (block 322). If the entity is not stored therein, then execution proceeds to block 324 where the entity is fetched, for example, by a get request to a web host and cached. Then, execution proceeds to block 326.

If, on the other hand, the requested entity is indeed stored in the cache system 204, then execution skips to block 326 where the requested entity 222 is retrieved from the cache and transmitted to the client system 200. At block 328, the cached entity 222 is received by the client system 200.

Accordingly, a push caching technique is described, in which a server system can force a cache system to update its local copy of a particular entity. This approach facilitates publication of content by content providers, because stale copies are purged upon receipt of the request, and the request may be sent at off-peak hours or via efficient, multi-casting technologies such as over a geosynchronous satellite.

While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.

Claims

WHAT IS CLAIMED IS:

L A method for maintaining data in a cache system located in a network, comprising the steps of: receiving a request from a server system to update a cache maintained by the cache system, said request including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the server system; in response to the request, updating the cache by storing the entity in the cache in association with the resource identifier.

2. The method according to claim 1, further comprising the steps of: intercepting a client request from a client system to retrieve the entity, said client request indicating the location of the entity in the server system; and in response to the client request, retrieving the entity from the cache and transmitting the entity to the client system.

3. The method according to claim 1, wherein the entity is updated in the cache regardless of whether there is an older version of the entity stored in the cache.

4. The method according to claim 1, further comprising the step of periodically performing the steps of receiving and updating at regular intervals.

5. The method according to claim 1, wherein the step of updating the cache includes updating the cache without transmitting an indication that the entity is not stored in the cache.

6. A method for maintaining data in a cache system located in a network, comprising the steps of: receiving a request from a server system to update a cache maintained by the cache system, said request including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the network; determining whether the server system is permitted to update the entity in the cache based on the location of the entity in the network; and if the server system is permitted to update the entity in the cache, then updating the cache by storing the entity in the cache in association with the resource identifier.

7. The method according to claim 6, further comprising the step of registering a location of the server system; wherein the step of determining includes comparing the location of the entity in the network and the location of the server system.

8. A method for publishing data from a server system in a network, comprising the steps of: registering a location of the server system in a cache system; and transmitting a request from the server system to the cache system, said request to update a cache maintained by the cache system and including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the network.

9. The method according to claim 8, further comprising automatically performing the step of transmitting in response to an update of the entity at the server system.

10. The method according to claim 8, further comprising periodically performing the step of transmitting at regular intervals.

11. A computer-readable medium bearing instructions for maintaining data in a cache system located in a network, said instructions being arranged to cause one or more processors upon execution thereby to perform the steps of: receiving a request from a server system to update a cache maintained by the cache system, said request including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the server system; in response to the request, updating the cache by storing the entity in the cache in association with the resource identifier.

12. The computer-readable medium according to claim 11, said instructions being further arranged to cause one or more processors upon execution thereby to perform the steps of: intercepting a client request from a client system to retrieve the entity, said client request indicating the location of the entity in the server system; and in response to the client request, retrieving the entity from the cache and transmitting the entity to the client system.

13. The computer-readable medium according to claim 11, said instructions being further arranged to cause one or more processors upon execution thereby to perform the step of periodically performing the steps of receiving and updating at regular intervals.

14. The computer-readable medium according to claim 11, wherein the step of updating the cache includes updating the cache without transmitting an indication that the entity is not stored in the cache.

15. A computer-readable medium bearing instructions for maintaining data in a cache system located in a network, said instructions being arranged to cause one or more processors upon execution thereby to perform the steps of: receiving a request from a server system to update a cache maintained by the cache system, said request including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the network; determining whether the server system is permitted to update the entity in the cache based on the location of the entity in the network; and if the server system is permitted to update the entity in the cache, then updating the cache by storing the entity in the cache in association with the resource identifier.

16. The computer-readable medium according to claim 15, said instructions being further arranged to cause one or more processors upon execution thereby to perform the step of registering a location of the server system; wherein the step of determining includes comparing the location of the entity in the network and the location of the server system.

17. A computer-readable medium bearing instructions for publishing data from a server system in a network, said instructions being arranged to cause one or more processors upon execution thereby to perform the steps of: registering a location of the server system in a cache system; and transmitting a request from the server system to the cache system, said request to update a cache maintained by the cache system and including an entity to be placed in the cache and a resource identifier indicating a location of the entity in the network.

18. The computer-readable medium according to claim 17, further comprising periodically performing the step of transmitting at regular intervals.