System for accessing distributed data cache channel at each network node to pass requests and data

• US 5,611,049 A
• Filed: 11/28/1994
• Issued: 03/11/1997
• Est. Priority Date: 06/03/1992
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: William M. Pitts
• Inventors: Pitts, William M.
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US08/343,477
• Time in Patent Office: 834 Days
• Field of Search: 395/200.03, 395/200.09, 395/200.18, 395/876, 395/200.15, 395/464
• US Class Current: 1/1
• 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: G06F 16/10 File systems; File servers
• 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/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]
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Network Distributed Caches ("NDCs") (50) permit accessing a named dataset stored at an NDC server terminator site (22) in response to a request submitted to an NDC client terminator site (24) by a client workstation (42). In accessing the dataset, the NDCs (50) form a NDC data conduit (62) that provides an active virtual circuit ("AVC") from the NDC client site (24) through intermediate NDC sites (26B, 26A) to the NDC server site (22). Through the AVC provided by the conduit (62), the NDC sites (22, 26A and 26B) project an image of the requested portion of the named dataset into the NDC client site (24) where it may be either read or written by the workstation 42. The NDCs (50) maintain absolute consistency between the source dataset and its projections at all NDC client terminator sites (24, 204B and 206) at which client workstations access the dataset. Channels (116) in each NDC (50) accumulate profiling data from the requests to access the dataset for which they have been claimed. The NDCs (50) use the accumulated profile data stored in channels (116) to anticipate future requests to access datasets, and, whenever possible, prevent any delay to client workstations in accessing data by asynchronously pre-fetching the data in advance of receiving a request from a client workstation.

Claims

1. In a network of digital computers that includes a first plurality of Network Distributed Cache ("NDC") sites, each NDC site including an NDC that has an NDC buffer, a method for projecting images of a stored dataset from an NDC server terminator site into a second plurality of NDC client terminator sites in response to requests to concurrently access such stored dataset transmitted from a third plurality of client sites respectively to the second plurality of NDC client terminator sites, the method comprising the steps of:

(a) the NDC receiving the request to access data in the stored dataset;

(b) the NDC checking the NDC buffer at this NDC site to determine if a projected image of data requested from the stored dataset is already present there;

(c) if the NDC buffer of this NDC site does not contain a projected image of all data requested from the stored dataset, and if the NDC site receiving the request is not the NDC server terminator site for the stored dataset, the NDC of this NDC site transmitting a request for data from this NDC site downstream to another NDC site closer to the NDC server terminator site for the stored dataset than the present NDC site;

(d) if the NDC buffer of this NDC site does not contain a projected image of all data requested from the stored dataset, and if the NDC site receiving the request is the NDC server terminator site for the stored dataset, the NDC of the NDC server terminator site accessing the stored dataset to project an image of the requested data into the NDC buffer of the NDC server terminator site;

(e) repeating the steps (a) through (d) until the NDC buffer of the downstream NDC site receiving the request contains a projected image of all requested data;

(f) each successive NDC site, having obtained a projected image of all the requested data, returning the requested data upstream to the NDC site from which the NDC site received the request until the requested data arrives at the NDC client terminator site, each NDC site that returns data upstream to the requesting NDC site retaining a copy of the returned data that the returning NDC site may subsequently transmit to an NDC site other than the NDC site to which the returning NDC site first returned the data, whereby images of the stored dataset may be projected concurrently from a single NDC site into the second plurality of NDC client terminator sites; and

(g) the NDC client terminator site, upon receiving the requested data, returning the requested data to the client site that requested access to the stored dataset.

2. The method of claim 1 wherein, prior to returning the requested data to the client site, the NDC client terminator site reformats the requested data from the protocol employed for communications between pairs of NDC sites into the protocol in which the client site requested access to the stored dataset from the NDC client terminator site.

3. The method of claim 2 wherein the NDC client terminator site selectively reformats the requested data from the protocol employed for communications between pairs of NDC sites into a particular one of a plurality of different protocols that matches the protocol in which the client site requested access to the stored dataset from the NDC client terminator site.

4. The method of claim 1 further comprising the steps of:

(h) each NDC upon receiving the initial request to access the stored dataset claiming a channel and designating the channel for storing various data relevant to processing requests to access the stored dataset;

(i) storing in the channel of this NDC site data collected by the NDC while processing requests to access the stored dataset; and

(j) if the NDC site is not performing any steps of the method that are required for responding to a request to access the stored dataset, the method at NDC sites further including;

i. periodically analyzing data stored in the channel of this NDC site to determine whether future requests to access the stored dataset may be anticipated;

ii. if the analysis of data stored in the channel of this NDC site establishes a possibility for anticipating future requests to access the stored dataset, further analyzing data stored in the channel to determine whether anticipated future requests will soon present this NDC site with another request to access the stored dataset and whether the projected image of data present in the NDC buffer includes sufficient data to respond immediately to the anticipated request; and

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

5. The method of claim 4 wherein the NDC site, in requesting data from the next downstream NDC site, requests a quantity of data that is larger than the amount of data returned by the NDC client terminator site to the requesting client site in response to a request to access the stored dataset received by the NDC client terminator site from the client site.

6. The method of claim 1 wherein each NDC upon receiving the initial request to access the stored dataset claims a channel and designates the channel for storing various data relevant to processing requests to access the stored dataset, the method at NDC sites further comprising the step of:

(h) if the NDC is not performing any steps of the method that are required for responding to a request to access the stored dataset, the method at NDC sites further including;

i. periodically analyzing channels to determine if such channel is presently no longer needed for responding to requests to access the stored dataset for which the channel was claimed; and

ii. if the channel being analyzed is no longer needed for responding to requests to access the stored dataset, then processing the no longer needed channel to prepare such channel for immediate claiming in response to a subsequent request from a client site to access another dataset.

7. The method of claim 6 wherein the periodic analysis of channels to determine if such channel is presently no longer needed for responding to requests is halted if the number of channels available to respond to a future request to access a dataset exceeds a pre-established upper threshold.

8. The method of claim 7 wherein the NDC having stopped periodically analyzing channels, resumes periodically analyzing channels if the number of channels available to respond to a future request to access a dataset drops below a pre-established lower threshold that is less than the pre-established upper threshold.

9. The method of claim 1 further comprising the steps of:

(h) each NDC, upon receiving the initial request to access the stored dataset from an upstream NDC site, allocating an upstream site structure in which the NDC stores information indicating the type of activity being performed on the stored dataset at the upstream NDC site from which this NDC site received the request;

(i) each NDC, upon receiving a request to access the stored dataset if the type of activity occurring on the stored dataset differs from that already being supported for the stored dataset, transmitting a message to the downstream NDC site that returned requested data informing the downstream NDC site of the new type of activity now occurring on the stored dataset; and

(j) each NDC, upon receiving a message from an upstream NDC site informing the NDC of the type of activity being performed on the stored dataset at that upstream NDC site, storing such information in the upstream site structure for that upstream NDC site.

10. The method of claim 9 further comprising the steps of:

(k) each NDC, upon receiving information from a local client or from an upstream NDC site informing the NDC of the type of activity being performed on the stored dataset at that location, comparing the information just received with previously stored information recording the type of activity occurring on the stored dataset; and

(l) if the NDC determines from the comparison of the information just received with the previously stored information that the stored dataset is being accessed by at least two different NDC sites and one of those NDC sites is accessing the stored dataset to write data into the stored dataset, then a concurrent write sharing ("CWS") condition has occurred, and the NDC upon detecting the CWS condition becoming a consistency control site ("CCS") for the stored dataset.

11. The method of claim 10, after the NDC becomes the CCS, further comprising the steps of:

(m) if a request to access the stored dataset for writing creates the CWS condition, then the CCS transmitting disable messages to all upstream NDC sites other than the NDC site whose request created the CWS condition instructing such upstream NDC sites to disable any projected image of the dataset stored in the NDC buffer of such NDC sites; and

(n) if a request to access the stored dataset for reading creates the CWS condition, then transmitting a recall message to the upstream NDC site that is accessing the stored dataset to write data to the stored dataset instructing such upstream NDC site to transmit back to the CCS the projected image of the dataset stored in the NDC buffer of such NDC site.

12. The method of claim 11 further comprising the step of:

(o) the NDC that became the CCS for the stored dataset including with the data returned to all upstream NDC sites that access the stored dataset an indicator that instructs each such upstream NDC site not to maintain a projected image of the data in their NDC buffer after the data has traversed the NDC site.

13. The method of claim 12 further comprising the steps of:

(p) the NDC that became the CCS for the stored dataset, upon receiving information from a local client or from an upstream NDC site informing the CCS NDC of a cessation of a type of activity being performed on the stored dataset at that location, comparing the information just received with the previously stored information for the stored dataset;

(q) if the NDC determines from the comparison of the information just received with the previously stored information for the stored dataset that this NDC site need no longer function as the CCS for the stored dataset, then the NDC site ceasing to function as the CCS for the stored dataset; and

(r) upon this NDC site ceasing to function as the CCS for the stored dataset, permitting any upstream NDC site that is accessing the stored dataset to maintain in the NDC buffer of such NDC site an image of any subsequent projections of data from the stored dataset.

14. The method of claim 10 wherein;

before a disable message or a recall message transmitted upstream by the NDC site that recently became the CCS reaches an NDC site having a projected image of the stored dataset present in the NDC buffer of that NDC site;

such NDC site transmits downstream, through a channel toward the NDC site that became the CCS, a request to access the stored dataset;

the request to access the stored dataset transmitted downstream arriving at an NDC site that has already transmitted the recall or disable message upstream;

the method further comprising the steps of;

(o) the NDC site, that receives the request to access the stored dataset after having transmitted the recall or disable message upstream, responds to the request by rejecting the request to access the stored dataset;

(p) each upstream site upon receiving the response rejecting the request to access the stored dataset successively retransmitting the rejection response upstream until the rejection message reaches the client terminator site for the request to access the stored dataset; and

(g) upon receiving the rejection message, the NDC of the NDC client terminator site releasing the channel, waiting a short interval of time to allow the recall or disable message from the downstream CCS to be processed, and then generating and transmitting downstream a new request to access the stored dataset.

15. The method of claim 9 further comprising the steps of:

(m) the NDC site having become the CCS for the stored dataset, upon receiving information from a local client or from an upstream NDC site informing the CCS NDC of a cessation of a type of activity being performed on the stored dataset at that location, comparing the information just received with the previously stored information for the stored dataset; and

(n) if the NDC site determines from the comparison of the information just received with the previously stored information for the stored dataset that this NDC site need no longer function as the CCS for the stored dataset, then the NDC site ceasing to function as the CCS for the stored dataset.

16. A network of digital computers that includes a first plurality of client sites which request access to a stored dataset that is stored at a location that can be accessed through the network, the network comprising:

a second plurality of NDC sites, the stored dataset whose access is requested by the client sites being stored at an NDC server terminator site, a request from the client sites for access to the stored dataset being received by a third plurality of NDC client terminator sites, each NDC site including;

(a) an NDC that has an NDC buffer;

(b) means for the NDC to receive the request to access the stored dataset;

(c) means for the NDC to check the NDC buffer at this NDC site to determine if a projected image of data requested from the stored dataset is already present there, wherein;

i. if the NDC buffer of this NDC site does not contain a projected image of all data requested from the stored dataset, and if this NDC site is not the NDC server terminator site for the stored dataset, the NDC includes means for transmitting a request for data from this NDC site downstream to another NDC site closer to the NDC server terminator site for the stored dataset than the present NDC site;

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

iii. if the NDC buffer of an NDC site contains a projected image of all requested data, the NDC including means for returning the data requested from this NDC site upstream to the NDC site from which this NDC site received the request, whereby through a succession of such returns of data from one NDC site to the next upstream NDC site the requested data ultimately arrives at the NDC client terminator site, each NDC site that returns data upstream to the requesting NDC site retaining a copy of the returned data that the returning NDC site may subsequently transmit to an NDC site other than the NDC site to which the returning NDC site first returned the data, whereby images of the stored dataset may be projected concurrently from a single NDC site into the third plurality of NDC client terminator sites; and

(d) means for the NDC client terminator site to return the requested data to the client site that requested access to the stored dataset.

17. The network of claim 16 wherein, prior to returning the requested data to the client site, said data return means reformats the requested data from the protocol employed for communications between pairs of NDC sites into the protocol in which the client site requested access to the stored dataset from the NDC client terminator site.

18. The network of claim 17 wherein the data return means selectively reformats the requested data from the protocol employed for communications between pairs of NDC sites into a particular one of a plurality of different protocols that matches the protocol in which the client site requested access to the stored dataset from the NDC client terminator site.

19. The network of claim 16 wherein each NDC site further comprises:

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

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

(g) if the NDC site is not responding to a request to access the stored dataset, means for the NDC to periodically analyze data stored in the channel to determine whether future requests to access the stored dataset may be anticipated;

(h) if the analysis of data stored in the channel by the NDC establishes that future requests to access the stored dataset may be anticipated, 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 stored dataset and whether the projected image of data present in the NDC buffer includes sufficient data to respond immediately to the anticipated request; and

(i) if anticipated future requests will soon present this NDC site with another request to access the stored 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 NDC site data from the stored dataset before receiving a request therefor.

20. The network of claim 19 wherein the NDC site requests from the next downstream NDC site a quantity of data from the stored 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 NDC client terminator site to the requesting client site in response to a request to access the stored dataset received by the NDC client terminator site from the client site.

21. The network of claim 16 wherein each NDC site further comprises:

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

(f) if the NDC is not responding to a request to access the stored 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 stored dataset for which the channel was claimed; and

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

22. The network of claim 21 wherein each NDC site further comprises 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.

23. The network of claim 22 wherein each NDC site further comprises 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.

24. The network of claim 16 wherein each NDC site further comprises:

(e) means for the NDC, upon receiving the initial request to access the stored dataset from an upstream NDC site, to allocate an upstream site structure in which the NDC stores information indicating the type of activity being performed on the stored dataset at the upstream NDC site from which this NDC site received the request;

(f) means for each NDC, upon receiving a request to access the stored dataset if the type of activity occurring on the stored dataset differs from that already being supported for the stored dataset, to transmit a message to downstream NDC site that returned requested data informing the downstream NDC site of the new type of activity now occurring on the stored dataset; and

(g) means for each NDC, upon receiving a message from an upstream NDC site informing such NDC site of the type of activity being performed on the stored dataset at that upstream NDC site, to store such information in the upstream site structure for that upstream NDC site.

25. The network of claim 24 wherein each NDC site further comprises:

(h) means for each NDC, upon receiving information from a local client or from an upstream NDC site informing the NDC of the type of activity being performed on the stored dataset at that location, to compare the information just received with the previously stored information recording the type of activity occurring on the stored dataset; and

(i) if the NDC determines from the comparison of the information just received with the previously stored information for the stored dataset that the stored dataset is being accessed by at least two different NDC sites and one of those NDC sites is accessing the stored dataset to write data into the stored dataset, then means for the NDC to detect that a CWS condition has occurred, and to thereupon become a CCS for the stored dataset.

26. The network of claim 25 wherein the NDC site that has become of the CCS further comprises:

(j) if a request to access the stored dataset for writing creates the CWS condition, means for the NDC to transmit disable messages to all upstream NDC sites other than the NDC site whose request created the CWS condition instructing such upstream NDC sites to disable any projected image of the dataset stored in the NDC buffer of such NDC sites; and

(k) if a request to access the stored dataset for reading creates the CWS condition, means for the NDC to transmit a recall message to the upstream NDC site that is accessing the stored dataset to write data to the stored dataset instructing such upstream NDC site to transmit back to the CCS the projected image of the dataset stored in the NDC buffer of such NDC site.

27. The network of claim 26 wherein each NDC site further comprises:

(l) means for the NDC that became the CCS for the stored dataset to include with the data returned to all upstream NDC sites that access the stored dataset an indicator that instructs each such upstream NDC site not to maintain a projected image of the data in their NDC buffer after the data has traversed the NDC site.

28. The network of claim 27 wherein each NDC site further comprises:

(m) means for the NDC that became the CCS for the stored dataset, upon receiving information from a local client or from an upstream NDC site informing the CCS NDC of a cessation of a type of activity being performed on the stored dataset at that location, to compare the information just received with the previously stored information for the stored dataset;

(n) if the NDC determines from the comparison of the information just received with the previously stored information for the stored dataset that this NDC site need no longer function as the CCS for the stored dataset, means for the NDC site to cease functioning as the CCS for the stored dataset; and

(o) upon this NDC site ceasing to function as the CCS for the stored dataset, means for the NDC site to permit any upstream NDC site that is accessing the stored dataset to maintain in the NDC buffer of such NDC site an image of any subsequent projections of data from the stored dataset.

29. The network of claim 25 wherein each NDC site before a disable message or a recall message transmitted upstream by the NDC site that recently became the CCS reaches an NDC site having a projected image of the stored dataset present in the NDC buffer of that NDC site;

such NDC site transmits downstream, through a channel toward the NDC site that became the CCS, a request to access the stored dataset;

the request to access the stored dataset transmitted downstream arriving at an NDC site that has already transmitted the recall or disable message upstream;

each NDC site further comprising;

(l) means for the NDC site, that receives the request to access the stored dataset after having transmitted the recall or disable message upstream, to respond to the request by rejecting the request to access the stored dataset;

(m) means for each upstream site upon receiving the response rejecting the request to access the stored dataset successively retransmitting the rejection response upstream until the rejection message reaches the client terminator site for the request to access the stored dataset; and

(n) upon receiving the rejection message, means for the NDC of the NDC client terminator site to release the channel, wait a short interval of time to allow the recall or disable message from the downstream CCS to be processed, and then to generate and to transmit downstream a new request to access the stored dataset.

30. The network of claim 24 wherein each NDC site further comprises:

(j) means for the NDC site having become the CCS for the stored dataset, upon receiving information from a local client or from an upstream NDC site informing the CCS NDC of a cessation of a type of activity being performed on the stored dataset at that location, to compare the information just received with the previously stored information for the stored dataset; and

(k) if the NDC site determines from the comparison of the information just received with the previously stored information for the stored dataset that this NDC site need no longer function as the CCS for the stored dataset, means for the NDC site to cease functioning as the CCS for the stored dataset.