Proxy Server Caching Mechanism That Provides a File Directory Structure and a Mapping Mechanism Within the File Directory Structure

1. Technical Field

The invention relates to the exchange of information over an electronic network. More particularly, the invention relates to a proxy server caching mechanism that provides a file directory structure and a mapping mechanism within the file directory structure in an electronic network.

2. Description of the Prior Art

Modern information networks, e.g. the Internet, use servers to store documents. In the World Wide Web (Web), these documents are addressed by uniform resource locators (URLs). URLs specify the protocol by a prefix in the URL, such as http:// for HyperText Transfer Protocol, the host in the Internet where the document is stored, and the address of the document within that host. The Web is thus not a single protocol, but a combination of several protocols united by a common addressing scheme, i.e. the URL.

The tremendous continuing growth of the Web makes it necessary to have intermediate servers which perform caching (store documents locally, such that the documents may be quickly accessed from the local file system, instead of being retransferred again from the original server. Such servers (see, for example A. Luotonen, K. Altis, World wide Web Proxies, Proceedings of First International World-Wide Web Conference, Geneva 1994) are referred to as caching proxy servers, or proxies for short. See, also A. Chakhuntod, P. Danzig, C. Neerdaels, M. Schwartz, K. Worrell, A Hierarchical Internet Object Cache, USENIX 1996 ANNUAL TECHNICAL CONFERENCE, http://usenix.org/publications/library/proceedings/sd96/danzig.html). Proxies reduce network load, and shorten response times to the user.

FIG. 1 is a block schematic diagram of a proxy server 14. When a client 12 requests a new document from the proxy server 14, the proxy server copies the document from the origin server 16 to its local file system in addition to sending the document to the client 12. When another request comes for the same document, the proxy server returns the document from the cache 15 if the cached copy is still up to date. If the proxy server determines that the document may be out of date, it performs an up-to-date check from the remote origin server and refreshes the document, if necessary, before sending it to the client 12.

Within a proxy server, an internal addressing mechanism is necessary to map the URLs to their location in the cache of the proxy server. Historically, the first caching proxy server, the "CERN httpd," mapped the URL directly to a UNIX file system path such that, for example:

http://home.netscape.com/some/file.html would become:

/cache-root/http/home.netscape.com/some/file.html.

This, however, was inefficient in several ways, including:

The path names for cached files could get extensively long and thus the file itself was time-consuming to located in the file system;

The directory holding the subdirectories corresponding to the second part of the URL (the host names) could get extensively large (i.e. thousands of entries). This is not very efficient in most commonly used operating systems, such as UNIX, because such operating systems must perform a time-consuming sequential searching through the directory to actually locate the desired file; and

The maintenance of such a cache becomes extensively hard because the contents of the cache are location-dependent, and the material at a given location in the cache is not "average." Thus, deciding which files should be kept in the cache and which removed therefrom is difficult.

Another caching proxy server, the Harvest Cache Daemon (see A. Chakhuntod, P. Danzig, C. Neerdaels, M. Schwartz, K. Worrell, A Hierarchical Internet Object Cache, ibid.), does not use the URL as part of the mapping scheme, but simply assigns a random file name to each URL, and maintains a central file containing the mappings from URLs to file names. This approach also has limitations, such as for example:

It is slow to start up the proxy server because it has to load the map file into the memory. Such process typically takes several minutes, thus exacerbating system latency;

It is wasteful of the RAM (main memory of the computer) because such central map file can get very big; and

It is fragile because the entire cache becomes unusable if the map file is lost or damaged.

The ability to locate documents in the cache without latency induced by long path names and large directories is very important. There is also another important aspect of the cache design, that is to make it easy to clean up old cache documents that are no longer necessary (i.e. garbage collection).

As described above, the "CERN httpd" proxy server cache has the undesired quality of being very location specific, i.e. each directory could contain entirely different types of documents, and no given directory could be considered "average." For example, some directories might contain only GIF images, whereas others would contain only HTML files (HyperText Markup Language), or Postscript files. Thus, when the "garbage collector" is traversing the cache structure, it is impossible to know beforehand how much data and how many documents are in the cache because the structure of the cache is not known until the cache is entirely traversed. Therefore, it is hard to make effective decisions about which documents should be kept and which should be removed.

It would be advantageous to provide a proxy server cache structure that stores and accesses documents in an optimum manner in a storage hierarchy that is easily managed.

The invention provides a mechanism that makes it possible to locate any cache document anywhere in the cache by using an input URL to mathematically produce both a unique (in practice) file name and a directory to which the file belongs. An algorithm, such as the MD5.RTM. (Message Digest-5) protocol is used in the process of generating the file name and the directory location. A fixed size directory structure is provided, thus eliminating deep path names. Hashing throughout the cache directories is provided to avoid extensively large directories, while providing a fairly even distribution of cache documents throughout the cache.

The invention uses a technique, such as the MD5.RTM. (Message Digest-5) protocol, to compress a variable length URL and thereby homogenize the URL, such that each URL, in practice, has a unique identity and a fixed size. Because all the data produced using the MD5.RTM. (Message Digest-5) protocol to compress and homogenize the URL are not needed, it is possible to support more documents than necessary with less than the sum total of data generated by the MD5.RTM. (Message Digest-5) protocol. With a subset of the total available data, it is possible to take a first portion of the data, e.g. six bytes and, for each byte, take the first N bits of each of the first M bytes to map the URL to the proxy server cache structure, as discussed above. After the system proceeds through this hierarchy and maps the URL to the directory, the system also provides a unique file name for each document pointed to by a URL.

The MD5.RTM. (Message Digest-5) protocol fingerprint is used to develop a unique document name at the bottom of the cache hierarchy. When the path identified by the first N bits in the first bytes is followed, there is a unique file name for the URL that is derived from the selected subset of the MD5.RTM. (Message Digest-5) protocol fingerprint. To produce the desired eight character file name, the system takes the six valid bytes, including the already once used bits to yield the directory path. The reason for reusing these bits is that any given document can be remapped later to a structure that had been expanded or collapsed, so that the first bits are not unique to a particular hierarchy.

A special file in each cache directory, the cache info file (CIF), provides a central repository for information for all the documents in that specific directory. In the CIF, there are single lines that start with the file name, so that the system can match which entry belongs to which file. There are several parameters associated with the CIF that describe, for example when a related document was loaded to the cache, when it was last accessed, and when it was last refreshed or checked that it was still up to date.

Accordingly, the invention provides a way of organizing the cache with small entries containing enough information about each cache file so that the actual cache document needs not be opened during cache cleanup (i.e. garbage collection).

FIG. 1 is a block schematic diagram of a proxy server;

FIG. 2 is a block schematic diagram showing generation of a directory mapping and a file name from a URL according to a preferred embodiment of the invention;

FIG. 3a is a schematic representation of a file directory structure according to a first embodiment of the invention;

FIG. 3b is a schematic representation of a file directory structure according to a second embodiment of the invention; and

FIG. 4 is a schematic representation of a file directory showing a CIF file structure according to the invention.

The invention provides a mechanism that reduces the number of files or directories in any given directory in the cache directory structure and that also reduces the depth of the directory structure. The invention includes a cache architecture that provides a preallocated structure of directories which, in one embodiment of the invention (FIG. 3a) comprises 16 directories, where each such directory is three levels deep (thus, on the third level there are 4,096 directories total); and which, in a second embodiment of the invention (FIG. 3b) comprises any number of cache partitions that may include any desired number of cache sections, where each cache section has 64 subdirectories. The invention is of particular use for caching documents pointed to by URLs, such that it is not necessary to keep going out and finding and re-retrieving the documents, e.g. frequently used documents are stored locally.

FIG. 2 is a block schematic diagram showing generation of a directory mapping and a file name from a URL according to the invention. In operation, the invention provides a protocol 20 that digests the URL in such way that a fixed length, unique (with high probability thereof) fingerprint is produced for each URL. The preferred embodiment of the invention takes an MD5.RTM. (Message Digest-5) protocol (RSA Data Security, Inc.) signature of the URL in the proxy server 14.

A message digest (signature) may be thought of as a fingerprint of data in which an input piece of data, such as a URL, produces an output that, in the case of the MD5.RTM. (Message Digest-5) protocol is 128 bits of data, and that has a high probability of unique correlation with regard to the input data. For example, if a book is processed through the MD5.RTM. (Message Digest-5) protocol, it always produces the same signature. If even one character is changed in the book, the signature changes. Thus, the MD5.RTM. (Message Digest-5) protocol is useful for indicating if anyone has tampered with the data, or if the data have been corrupted. If there are more samples than can be described with the amount of bits provided in the signature, there is a possibility that a collision can occur in which two different sets of data produce the same fingerprint, but in practice such occurrence is extremely unlikely. For purposes of practicing the invention, it is not essential that the MD5.RTM. (Message Digest-5) protocol be used. Other message digest techniques can be used that produce a unique, fixed length word from a variable length string of input data.

In the preferred embodiment of the invention, the proxy server provides a module 22 that ignores ten bytes of the signature produced by the MD5.RTM. (Message Digest-5) protocol, i.e. it only use six bytes or 48 bits. These values are parameters that are provided for purposes of the discussion herein and can be selected as desired for the application to which to invention is put. The 48 bits provided are sufficient to map about 70 million URLs (i.e. 70 million documents) with a very high probability they are unique, such that the proxy sever is not likely to produce collisions. These 70 million URLs, given a typical document size of 12,000 bytes, comprise almost 1 terabyte of data. For comparison, in today's typical setup the cache size is only 2-10 Gb. Should more storage be required, additional bits from the MD5.RTM. (Message Digest-5) protocol conversion may be retained, rather than discarded.

From a URL, the technique herein produces six bytes of data. This provides a good key for addressing the URL or the document in question. The invention provides a module 24 that preferably first operates on the six bytes of data to map the URL to a directory structure.

FIG. 3a is a schematic representation of a file directory structure according to a first embodiment of the invention. The top level directory 30 can have, for example one, two, four, eight, or 16 directories which map to a different cache capacity. The first preferred embodiment of the invention uses the full four bits of the first byte of the six bytes to map the URL signature to the first level of the directory. The directory shown in FIG. 3a provides a second level directory 32, consisting of 16 directories for each of the 16 directories at the first level directory (i.e. 256 directories), and a third level directory 34, consisting of 16 documents for each of the 256 second level directories.

FIG. 3b is a schematic representation of a file directory structure according to a second embodiment of the invention. This embodiment of the invention is presently preferred and uses another, more efficient set of parameters. The actual dimensions of the cache structure are tunable. The cache structure has 1, 2, 4, 8, 16, 32, 64, 128, or 256 top-level directories 37 ("cache sections") which, in this example are contained in cache partitions P1, P2, P3, . . . , Pn 36. It should be appreciated that there may be any number of cache partitions.

The directories are configurable, corresponding to different cache capacities from 125 Mb to 32 Gb, but the optimum figures depend upon the operating system used. There are 64 subdirectories 38 in each of the above mentioned directories. Thus, only two levels exist in this directory structure, while three levels of 16 directories each are provided by the cache directory structure shown in FIG. 3a. The structure of FIG. 3b yields the same number of deepest level directories (i.e. 4096) as the structure of FIG. 3a if there are 64 top level directories. The optimum dimensions of the cache depend upon the operating system used, desired cache capacity, and available disk space.

The invention also provides a module 26 (FIG. 2) that preferably next generates a file name for the URL from the six bytes of data. Because the invention only uses six bytes of the MD5.RTM. (Message Digest-5) protocol URL signature, which is 48 bits, eight of any of 64 characters (e.g. a-z, A-Z, 0-9, .sub.--, and ,) may be described because it takes six bits to represent 64 characters. In practice, an ASCII character is eight bits. These six bytes of MD5.RTM. (Message Digest-5) protocol data are therefore expanded to the eight bytes, i.e. eight characters, in a file name. This is accomplished by taking the first six bits of the 48 bits that comprise the six bytes of data and mapping them to one of the characters in the document name, and then taking the subsequent sets of six next bits again and again. This process results in eight of these six bit chunks because 8.times.6 is 48.

The invention makes it possible to locate any cache document anywhere by providing the input URL is used to produce both a document name and a directory to which the document belongs. A fixed size directory structure is thus provided in which a digest scheme, such as the MD5.RTM. (Message Digest-5) protocol, is used both to map the URL into the directory, and to generate the file name. In some embodiments of the invention, eliminating the third directory level to provide only two directory levels having bigger directories is a more efficient load. Proportionally going one more directory level deep degrades system performance more than having to search through a slightly bigger directory. The actual directory structure is determined as a matter of choice based upon such factors as the target architecture and operating system.

The invention uses a technique, such as the MD5.RTM. (Message Digest-5) protocol, to digest a variable length URL and thereby homogenize the URL, such that each URL has a unique identity and a fixed size. Because all the data produced using MD5.RTM. (Message Digest-5) protocol to digest and homogenize the URL are not needed, it is possible to support more documents than needed with less than the sum total of data generated by the MD5.RTM. (Message Digest-5) protocol. With a subset of the data, it is possible to take the first portion of the data, e.g. six bytes and, for each byte, take the first N bits of the first M bytes to map the URL to the proxy server cache structure, as discussed above. After the system proceeds through this hierarchy and maps the URL to the directory, the system also provides a unique file name for each URL. Thus, a subset of the MD5.RTM. (Message Digest-5) protocol fingerprint is used to develop a unique file name at the end of a cache hierarchy. When the path identified by the first N bits is followed, there is a unique file name for the URL that is derived from the subset of the MD5.RTM. (Message Digest-5) protocol fingerprint. To produce the desired eight character document name, the system takes the six valid bytes and uses the same bits again in the document name. The reason for reusing these bits is that any given document can be remapped later to a structure that had been expanded or collapsed, so that the first bits are not unique to a particular hierarchy.

A file in the directory, the cache information file (CIF), provides a central repository for information for all the documents in the directory and contains information about all the other documents in the directory. The CIF is much smaller than a global cache information file would be. In the exemplary CIF, there are single lines that start with the file name, so that the system can match which entry belongs to which cache file. There are several parameters associated with the CIF for each file that describe, for example when a related document was loaded to the cache, when it was last accessed, and when it was last refreshed or checked that it was still up to date.

FIG. 4 is a schematic representation of a file directory showing a CIF file structure according to the invention. A cache document includes both a header and the document content. One use of the proxy server is to make such header information more easily accessible. It is not desirable to mark the headers themselves. Therefore, the invention provides the CIF file, for example to store such information as the document expiration date, the last modified date, document length, and content type in the cache document. Such information is stored in the CIF file to make the information faster and more convenient for the proxy server and the garbage collector to locate and use.

The CIF file 40 comprises a list of document names, e.g. file name 1 through file name N, as well as each related cache document, e.g. documents ABXXYI.sub.-- 2 42 and XQQPrSt2 43. When the proxy server is accessed, the invention provides a mechanism for checking to determine if the desired URL is cached. Thus, an MD5.RTM. (Message Digest-5) protocol fingerprint is generated from the URL, the directory path and document name are generated, and a check is made to see if the desired file exists. If it does, then the CIF entry for the URL fingerprint is looked up in the CIF file. For the sake of hash collision detection, i.e. where the same fingerprint is produced for two different URLs, the CIF also includes the URL, which is then checked before the cache file is actually used.

When the CIF file is opened by the proxy server, various document related parameters may be accessed. Such parameters may include, for example when the document was last refreshed, which determines when the document should be checked again. Sometimes it is not necessary to check the document again. Rather it is only necessary to determine if the document has been checked recently enough that it still has a high probability of being up to date. Thus, the document can be returned without any external connection, which makes accessing the document much faster.

Other CIF file related parameters include the document expiration time and the last modification time. Expiration time requires that it is mandatory to force a check that the document is still up to date if it is marked expired by the original server. The last modified date is used to make those up-to-date checks.

Parameters may also include when the server originally sent the document and the last modified date. When it is desired to perform up-to-date checks, the proxy server connects to the remote server and requests that the document in question be sent, but only if the document has been modified since the most recently logged modification date/time. There may also be some information related the CIF file that are not stored in the CIF file because the operating system, e.g. the UNIX file system, already maintains them, for example the last access and last modification time of the file.

Other parameters that may be included in a file's CIF file entry include a requirement that authentication is needed and the length of the document.

As shown on FIG. 4, a single line of text is provided in the CIF file for every cache document. In the example shown on FIG. 4, every cache document other than the CIF file starts with a status line, e.g. "HTTP/1.0 200 OK." The document then indicates document content type, e.g. a text/html document. There may also be other headers, and then there is an empty line, after which the actual document is provided, e.g. an HTML document. The format is thus the same as the format used by the HTTP protocol. In the example of FIG. 4, the document content is "Hello, World|" FIG. 4 also shows another cache document that has the HTTP header section, the header lines, an empty line, and then the actual document content, which is in this case a GIF document.

Thus, the invention produces the MD5.RTM. (Message Digest-5) protocol signature, derives the file name, and looks up the file. If the document is not in the cache, then the invention creates a cache entry that comprises the document and also adds the document information to the CIF file as a CIF entry. If the document is already in cache, then the cached document may be used and it is not necessary to obtain the document over the network. However, before the cache file may be used, it is nonetheless necessary to determine the status of the document by accessing the CIF file entry for the document, and possibly make an up-to-date check to the remote origin server.

Although the invention is described herein with reference to the preferred embodiment, one skilled in the art will readily appreciate that other applications may be substituted for those set forth herein without departing from the spirit and scope of the present invention. Accordingly, the invention should only be limited by the Claims included below.