Network distributed site cache RAM claimed as up/down stream request/reply channel for storing anticipated data and meta data

• US 6,026,452 A
• Filed: 08/31/1998
• Issued: 02/15/2000
• Est. Priority Date: 02/26/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: William M. Pitts
• Inventors: Pitts, William Michael
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/144,602
• Time in Patent Office: 533 Days
• Field of Search: 711/129, 711/133, 711/137, 710/52, 710/56, 709/203, 709/238
• US Class Current: 710/56
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method and apparatus for caching data in a Network Distributed Cache ("NDC") (50) that is included in a network of digital computers (22, 24, 26A and 26B). The NDC (50) includes an NDC buffer (129) for storing at least a portion of an image of a dataset such as a file (156) retrieved from a server site (22) in response to a request from a client workstation (42) to access the dataset. The NDC (50) allocates channels (116) that store metadata extracted from the requests to access the dataset for which the channels (116) have been claimed, and from responses to such requests. The NDC (50) uses accumulated data stored in channels (116) to anticipate future requests to access datasets, and to forestall, as much as practicable, the client workstation (42) from experiencing any delay in accessing data by asynchronously pre-fetching data in advance of receiving a request from a client workstation (42).

Claims

1. In a digital computer system that includes high speed random access memory("RAM"), a method for caching in the RAM of the computer system an image of a portion of data stored in a dataset that the computer system can access in response to a request to access such data, the method comprising the steps of:

(a) claiming a channel in the RAM of the computer system for storing metadata relevant to accessing data in the dataset;

(b) loading metadata into the channel;

(c) from a pool of buffers in the RAM of the computer system, assigning to the channel a buffer for storing an image of a portion of the data from the dataset;

(d) accessing the dataset to load an image of a portion of the data from the dataset into the buffer assigned to the channel; and

(e) responding to the request to access the data by supplying from the buffer an image of the data stored in such buffer together with a portion of the metadata stored in the channel.

2. The method of claim 1 wherein a plurality of buffers are assigned to the channel from the pool of buffers in the RAM of the computer system, each buffer for storing an image of a portion of the data from the dataset, and wherein the dataset is accessed to load images of a portion of the data from the dataset into such plurality of buffers for responding to the request to access data.

3. The method of claim 2 wherein the plurality of buffers that may be assigned to the channel is limited to a maximum number, the method further comprising the steps of:

(f) claiming a subchannel in the RAM of the computer system and associating the subchannel with the previously claimed channel;

(g) assigning a buffer from the pool of buffers in the RAM of the computer system to the subchannel for storing an image of a portion of the data from the dataset;

(h) accessing the dataset to load an image of a portion of the data from the dataset into the buffer assigned to the subchannel; and

(i) responding to the request to access the data by supplying from the buffer assigned to the subchannel an image of the data stored in such buffer together with a portion of the metadata stored in the channel.

4. The method of claim 3 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the method further comprising the steps of:

(j) selecting for further processing the least recently used of the previously claimed channels; and

(k) processing the selected channel to prepare it for immediate claiming in response to a subsequent request to access data stored in another dataset.

5. The method of claim 2 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the method further comprising the steps of:

(f) selecting for further processing the least recently used of the previously claimed channels; and

(g) processing the selected channel to prepare it for immediate claiming in response to a subsequent request to access data stored in another dataset.

6. The method of claim 1 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the method further comprising the steps of:

(f) selecting for further processing the least recently used of the previously claimed channels; and

(g) processing the selected channel to prepare it for immediate claiming in response to a subsequent request to access data stored in another dataset.

7. A cache for a digital computer system having a high speed RAM, said cache caching an image of a portion of data stored in a dataset in response to a request to access such data, said cache comprising:

(a) channel claiming means for claiming a channel in the RAM of the computer system, said channel being adapted for storing metadata relevant to accessing data in the dataset;

(b) means for loading metadata into said channel;

(c) a pool of buffers in the RAM of the computer system from which a buffer is assigned to said channel for storing an image of a portion of the data from the dataset;

(d) data loading means for accessing the dataset to load an image of a portion of the data from the dataset into said buffer assigned to said channel; and

(e) request response means for responding to the request to access the data by supplying from said buffer assigned to said channel an image of the data stored in such buffer together with a portion of the metadata stored in said channel.

8. The cache of claim 7 wherein a plurality of buffers are assigned to said channel from said pool of buffers in the RAM of the computer system, each buffer assigned to said channel storing an image of a portion of the data from the dataset, and wherein said data loading means accesses the dataset to load images of a portion of the data from the dataset into such plurality of buffers for responding to the request to access data.

9. The cache of claim 8 wherein the plurality of buffers that may be assigned to said channel is limited to a maximum number, the cache further comprising:

(f) subchannel claiming means for claiming a subchannel in the RAM of the computer system and associating said subchannel with said channel; and

(g) a buffer assigned from said pool of buffers in the RAM of the computer system to said subchannel for storing an image of a portion of the data from the dataset, said data loading means accessing the dataset to load an image of a portion of the data from the dataset into said buffer assigned to said subchannel, and said request response means supplying from said buffer assigned to said subchannel an image of the data stored in such buffer together with a portion of the metadata stored in said channel in response to the request to access the data.

10. The cache of claim 9 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the cache further comprising:

(f) channel selection means for selecting for further processing the least recently used of the previously claimed channels; and

(g) channel readying means for processing said channel selected by the channel selection means to prepare it for immediate re-claiming in response to a subsequent request to access data stored in another dataset.

11. The cache of claim 8 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the cache further comprising:

(f) channel selection means for selecting for further processing the least recently used of the previously claimed channels; and

(g) channel readying means for processing said channel selected by the channel selection means to prepare it for immediate re-claiming in response to a subsequent request to access data stored in another dataset.

12. The cache of claim 7 wherein only a limited space in RAM is allocated for channels thereby establishing a maximum number of channels that may be simultaneously claimed for responding to requests to access data stored in datasets, the cache further comprising:

(f) channel selection means for selecting for further processing the least recently used of the previously claimed channels; and

(g) channel readying means for processing said channel selected by the channel selection means to prepare it for immediate re-claiming in response to a subsequent request to access data stored in another dataset.

13. A Network Distributed Cache ("NDC") site adapted for inclusion into a network of digital computers, the network including a client terminator site that is adapted for receiving a request from a client for access to data stored in a dataset located at a server terminator site, the server terminator site also being included in the network and being accessible by the client terminator site via the network, the NDC site comprising:

(a) an NDC having an NDC buffer and including;

i. means for receiving requests for access to data stored in a dataset; and

ii. means for the NDC to check the NDC buffer to determine when a projected image of valid data responsive to at least a portion of requests therefor is already present in the NDC buffer wherein;

A. if the NDC buffer does not contain a projected image of all data requested from the dataset, and if the NDC site is not the server terminator site for the dataset, the NDC including means for transmitting a request for data via the network from the NDC site downstream to another site closer to the server terminator site for the dataset than the NDC site;

B. if the NDC buffer does not contain a projected image of all data requested from the dataset, and if the NDC site is the server terminator site for the dataset, the NDC including means for accessing the dataset to project a valid image of the requested data into the NDC buffer;

C. if the NDC buffer contains a projected image of all requested data, and if the NDC site is not the client terminator site which received the request from the client, the NDC including means for returning data requested from the NDC site upstream to the site from which the NDC received the request, whereby through a succession of such returns of data from one site to the next upstream site the requested data ultimately arrives at the client terminator site; and

D. if the NDC buffer contains a valid projected image of all requested data, and if the NDC site is the client terminator site which received the request from the client, the NDC including data return means for returning the requested data from the NDC buffer to the client site.

14. The NDC site of claim 13 wherein, prior to returning the requested data to the client site, said means for the NDC to check the NDC buffer reformats the requested data from a protocol employed for communications between digital computers of the network into a protocol in which the client requested access to the dataset from the client terminator site.

15. The NDC site of claim 14 wherein said means for the NDC to check the NDC buffer selectively reformats the requested data from the protocol employed for communications between pairs of digital computers of the network into a particular one of a plurality of different protocols that matches the protocol in which the client requested access to the dataset from the client terminator site.

16. The NDC site of claim 13 further comprising:

(b) means for the NDC, upon receiving the initial request to access the dataset, to claim a channel for storing various data relevant to processing requests to access the dataset;

(c) means for the NDC to store in the channel data collected by the NDC while processing requests to access the dataset;

(d) while the NDC site is not responding to a request to access dataset, means for the NDC to periodically analyze data stored in the channel to determine whether it is possible to anticipate future requests to access the dataset;

(e) if the analysis of data stored in the channel by the NDC establishes that it is possible to anticipate future requests to access the dataset, means for the NDC to further analyze data stored in the channel to determine whether anticipated future requests will soon present this NDC with another request to access the dataset and whether the projected image of data present in the NDC buffer includes sufficient data to respond immediately to the anticipated request; and

(f) if anticipated future requests will soon present this NDC site with another request to access the dataset and if the projected image of data present in the NDC buffer lacks sufficient data to respond immediately to the anticipated request, means for the NDC to request from the next downstream site data from the dataset before receiving a request therefor.

17. The NDC site of claim 16 wherein the NDC site requests from the next downstream site a quantity of data from the dataset before receiving a request therefor, the quantity of data requested by the NDC site being larger than the amount of data returned by the client terminator site to the requesting client in response to a request to access the dataset received by the client terminator site from the client.

18. The NDC site of claim 13 wherein the NDC further comprises:

(b) means for the NDC, upon receiving the initial request to access the dataset, to claim a channel for storing various data relevant to processing requests to access the dataset;

(c) if the NDC is not responding to a request to access a dataset, means for the NDC to periodically analyze channels to determine if such channel is presently no longer needed for responding to requests to access the dataset for which the channel was claimed; and

(d) if analysis of the channel establishes that the channel is no longer needed for responding to requests to access the dataset, means for the NDC to process the no longer needed channel to prepare it for immediate claiming in response to a subsequent request from a client to access another dataset.

19. The NDC site of claim 18 wherein said NDC further includes means for halting the analysis of channels to determine if such channels are presently no longer needed for responding to requests if the number of channels available to respond to future requests to access datasets exceeds a pre-established upper threshold.

20. The NDC site of claim 19 wherein said NDC further includes means for resuming the previously halted analysis of channels to determine if such channels are presently no longer needed for responding to requests if the number of channels available to respond to future requests to access datasets drops below a pre-established lower threshold that is less than the pre-established upper threshold.