 |
Claims  |
|
|
What is claimed is:
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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
This application is the national stage of PCT/US92/04939 filed Jun. 3, 1992
and claims priority therefrom.
TECHNICAL FIELD
The present invention relates generally to the technical field of
multi-processor digital computer systems and, more particularly, to
multi-processor computer systems in which:
1. the processors are loosely coupled or networked together;
2. data needed by some of the processors is controlled by a different
processor that manages the storage of and access to the data;
3. processors needing access to data request such access from the processor
that controls the data;
4. the processor controlling data provides requesting processors with
access to it.
BACKGROUND ART
Within a digital computer system, processing data stored in a memory; e.g.,
a Random Access Memory ("RAM") or on a storage device such as a floppy
disk drive, a hard disk drive, a tape drive, etc.; requires copying the
data from one location to another prior to processing: Thus, for example,
prior to processing data stored in a file in a comparatively slow speed
storage device such as hard disk, the data is first copied from the
computer system's hard disk to its much higher speed RAM. After data has
been copied from the hard disk to the RAM, the data is again copied from
the RAM to the computer system's processing unit where it is actually
processed. Each of these copies of the data, i.e., the copy of the data
stored in the RAM and the copy of the data processed by the processing
unit, can be considered to be image of the data stored on the hard disk.
Each of these images of the data may be referred to as a projection of the
data stored on the hard disk.
In a loosely coupled or networked computer system having several processors
that operate autonomously, the data needed by one processor may be
accessed only by communications passing through one or more of the other
processors in the system. For example, in a Local Area Network ("LAN")
such as Ethernet one of the processors may be dedicated to operating as a
file server that receives data from other processors via the network for
storage on its hard disk, and supplies data from its hard disk to the
other processors via the network. In such networked computer systems, data
may pass through several processors in being transmitted from its source
at one processor to the processor requesting it.
In some networked computer systems, images of data are transmitted directly
from their source to a requesting processor. One operating characteristic
of networked computer systems of this type is that, as the number of
requests for access to data increase and/or the amount of data being
transmitted in processing each request increases, ultimately the processor
controlling access to the data or the data transmission network becomes
incapable of responding to requests within an acceptable time interval.
Thus, in such networked computer systems, an increasing workload on the
processor controlling access to data or on the data transmission network
ultimately causes unacceptably long delays between a processor's request
to access data and completion of the requested access.
In an attempt to reduce delays in providing access to data in networked
computer systems, there presently exist systems that project an image of
data from its source into an intermediate storage location in which the
data is more accessible than at the source of the data. The intermediate
storage location in such systems is frequently referred to as a "cache,"
and systems that project images of data into a cache are be referred to as
"caching" systems.
An important characteristic of caching systems, frequently referred to as
"cache consistency" or "cache coherency," is their ability to
simultaneously provide all processors in the networked computer system
with identical copies of the data. If several processors concurrently
request access to the same data, one processor may be updating the data
while another processor is in the process of referring to the data being
updated. For example, in commercial transactions occurring on a networked
computer system one processor may be accessing data to determine if a
customer has exceeded their credit limit while another processor is
simultaneously posting a charge against that customer's account. If a
caching system lacks cache consistency, it is possible that one
processor's access to data to determine if the customer has exceeded their
credit limit will use a projected image of the customer's data that has
not been updated with the most recent charge. Conversely, in a caching
system that possesses complete or absolute cache consistency, the
processor that is checking the credit limit is guaranteed that the data it
receives incorporates the most recent modifications.
One presently known system that employs data caching is the Berkeley
Software Distribution ("BSD") 4.3 version of the Unix timesharing
operating system. The BSD 4.3 system includes a buffer cache located in
the host computer's RAM for storing projected images of blocks of data,
typically 8k bytes, from files stored on a hard disk drive. Before a
particular item of data may be accessed on a BSD 4.3 system, the requested
data must be projected from the hard disk into the buffer cache. However,
before the data may be projected from the disk into the buffer cache,
space must first be found in the cache to store the projected image. Thus,
for data that is not already present in a BSD 4.3 system's buffer cache,
the system must perform the following steps in providing access to the
data:
Locate the buffer in the RAM that contains the Least Recently Used ("LRU")
block of disk data.
Discard the LRU block of data which may entail writing that block of data
back to the hard disk.
Project an image of the requested block of data into the now empty buffer.
Provide the requesting processor with access to the data.
If the data being accessed by a processor is already present in a BSD 4.3
system's data cache, then responding to a processor's request for access
to data requires only the last operation listed above. Because accessing
data stored in RAM is much faster that accessing data stored on a hard
disk, a BSD 4.3 system responds to requests for access to data that is
present in its buffer cache in approximately 1/250th the time that it
takes to respond to a request for access to data that is not already
present in the buffer cache.
The consistency of data images projected into the buffer cache in a BSD 4.3
system is excellent. Since the only path from processors requesting access
to data on the hard disk is t | | |
