Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-10-05
2003-10-07
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06631449
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to systems and methods for maintaining storage object consistency across distributed storage networks and more particularly to a dynamic distributed data system and method which provides for minimized latency, reduced complexity and is extensible, scalable and isotropic.
2. Background of the Invention
Processors in a multiprocessor configuration are conventionally designed with a cache. A cache is a type of memory that is smaller and faster than other memory types. Caches are used by processors to store data retrieved from main memory. When a processor requests data and the data is not in its cache, the main memory supplies the data and a copy is then stored in the processor cache. A subsequent request from the processor for the same data results in the cache providing the data instead of the main memory because the cache is faster.
Since each processor has a cache with its own copy of data, data inconsistencies can result. For example, consider two processors A and B, each with caches with the same data. If processor A updates its cache data while processor B does not, then A and B have caches with inconsistent data. Furthermore, computations by B using its cached data will result in other data inconsistencies. The inconsistent data between caches is called the cache coherence problem.
The cache coherence problem exists at all levels in a computer memory hierarchy such as in multiple levels of caches, main memory, and secondary and tertiary storage (typically disks and tapes).
Prior solutions to the cache coherence problem typically fall into two categories. One known solution is the snoopy cache coherence protocol. In accordance with the snoopy cache coherence protocol, each processor “snoops” or eavesdrops on a shared interconnect, such as a bus or ring, to check if data blocks shared with other caches have been changed or modified, for example. If a snooping processor discovers that its copy of data is out-of-date, then the snooping processor will invalidate its data to force a fetch of the data from the memory or another cache on a subsequent data request. A typical snoopy cache coherence protocol solution includes the MOESI model as is well known in the art.
A uniquely identified data block
100
is identified with an address tag
105
as shown in FIG.
1
. In accordance with the MOESI model, a valid bit
110
indicates the state of data block
100
in the cache of the snooping processor. Such states include valid and invalid states. Other state bits such as an owned bit
120
and a shared bit
130
are conventionally used to represent states of data block
100
. Owned bit
120
is used to indicate ownership, that is, permission to write, of the data block
100
. Shared bit
130
is used to indicate that the data block
100
is shared, that is, other caches have a copy.
The three state bits including the valid bit
110
, the owned bit
120
, and the shared bit
130
yield eight possible states. The MOESI model includes a modified (M) state, an owned (O) state, an exclusive (E) state, a shared (S) state, and an invalid (I) state. These state bits define whether cache data has been modified, is owned, is exclusive, is shared, or has invalid data. The other three possible states are not defined in a standard MOESI implementation.
While the snoopy cache coherence protocol has been used in a system of connected processors on a shared interconnect, performance is typically limited to an optimum number of processors connected to the shared interconnect. The optimum number of processors is determined by the traffic handling capabilities of the shared interconnect. Thus the snoopy protocol is not scalable to arbitrarily large systems of connected processors. Additionally, the snoopy protocol is not extensible without modifying existing resources, because a solution to the scalability problem includes changing the bandwidth of the shared interconnect.
A second known solution to the cache coherence problem includes a directory-based cache coherence protocol. In the directory-based cache coherence protocol, a processor performs a table lookup in a directory when data in its cache is to be updated. Typically, the directory stores a table of cache locations that contain the same data block as the data block to be updated by the requesting processor. Data inconsistency arises because the data update may cause data stored in other caches or memory to become inconsistent. To resolve this, the other caches are notified of the impending data update and those copies are invalidated. Then the requesting processor can safely perform the data update.
A directory-based scheme is not scalable or extensible, since each cache needs to keep a directory entry for other interested caches in the system and as new caches are added, the existing tables must be expanded. Additionally, table lookups require more time as more processors are added to the system because added table entries for the added processors must also be checked. This increased lookup time leads to increased latency throughout the system thereby limiting the effectiveness of the directory-based cache coherence protocol. The directory-based cache coherence protocol also requires increased memory for the directory (which can be distributed) as the system of connected processors grows.
A generalization of a coherent cache system where the system contains only cache memories and discards the requirement for main memory by requiring at least one of the caches to keep data persistent is called a “main-memoryless” system or a “cache only memory architecture” (COMA).
When a system of storage elements, computer memory, disk devices, network switches, routers, or other computing system devices are networked together (hereinafter network of attached devices), a data inconsistency problem similar to the cache coherence problem results. Regardless of the extent of the network, common data residing on any device on the network can become inconsistent.
Additionally, the network of attached devices typically includes devices from various manufacturers, each of which implements and configures its devices differently. This leads to great complexity and extremely high costs in administering the network of attached devices. Adding a new device to the network of attached devices increases the complexity of the network of attached devices by requiring increased administration. The administration cost increases with increasing complexity because human capacity is finite and more personnel are required for the administration of each new device. This problem can be mitigated if the network is made isotropic, that is, the ability of the network to look the same to any attached device looking into the network from any direction. In such manner a single administrator with finite capacity can administer an indefinite size network of attached devices.
What is needed therefore is a system and method for maintaining data consistency which provides for minimized latency, reduced complexity and is extensible, scalable, and isotropic.
BRIEF SUMMARY OF THE INVENTION
The invention provides a dynamic distributed data system and method which includes at least one migratable repository of last resort (RLR). The RLR provides a facility for storing a last or only remaining data replica that may not be deleted. In this manner the RLR ensures the persistence of the data replica. The process of the invention monitors data requests to the RLR and determines whether to migrate the RLR to a requesting node.
REFERENCES:
patent: 5771349 (1998-06-01), Picazo, Jr. et al.
patent: 6347362 (2002-02-01), Schoinas et al.
Sweazey, Paul and Alan Jay Smith, A Class of Compatible Cache Consistency Protocols and their Support by the IEEE Futurebus, Proc. 13'th Ann. Symp. on Computer Architecture, Jun. 3-5, 1986, Tokyo, Japan.
Ellis Kevin L.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Veritas Operating Corporation
LandOfFree
Dynamic distributed data system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic distributed data system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic distributed data system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3120745