Method for the dynamic replication of data under distributed system control to control utilization of resources in a multiprocessing, distributed data base system

• US 4,432,057 A
• Filed: 11/27/1981
• Issued: 02/14/1984
• Est. Priority Date: 11/27/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Harding, Robert C. Jr., Nauckhoff, Sven H. H., Lewis, Neil J., Daniell, Thomas P.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/325,531
• Time in Patent Office: 809 Days
• Field of Search: 364/300
• US Class Current: 707/610
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method for dynamic replication of data under distributed system control to control the utilization of resources in a multiprocessing, distributed data base system. Previously, systems providing for data replication at nodes of a multiprocessing, distributed data base system required that a central node maintain control, or that replicated data be synchronized by immediately conforming all copies of an updated data item. By this invention, requests for access to data of a specified currency are permitted and conformation of updated data is selectively deferred by use of a control procedure implemented at each node and utilizing a status and control (SAC) filed at each node which describes that node'"'"'s view of the status for shared data items at other nodes.

Claims

1. A method for operating a computing apparatus having a plurality of nodes, each node having storage means for storing a plurality of data items and means responsive to a request for accessing a specified data item, and communication means interconnecting selected nodes, the method including the steps of controlling access to the specified data item and controlling the modification of copies of the data item, characterized by the steps of:

distributing data access control to each node of the apparatus; and

, responsive to a request having a specified currency, dynamically replicating data items while selectively deferring conformation of the replicated data;

such that the most current data items migrate to their respective affinity nodes.

2. The method of claim 1, wherein said replicating step is further characterized by:

selectively updating a data item at a request processing node in connection with the processing of a request at said request processing node while selectively deferring conformation of copies of the updated data item at other nodes.

3. A method for operating a computing system including a plurality of nodes, with each node having means for storing at least one data item, comprising the steps of:

responsive to a request having a specified currency, dynamically replicating data under distributed system control, while

selectively deferring conformation of the replicated data.

4. A method for operating a computing apparatus to dynamically replicate data under distributed system control comprising the steps of:

storing a data item at each of two nodes;

storing at each of the nodes a dipole half for said date item, the dipole half stored at a first node describing the status of the data item at the second node assumed by said first node;

responsive to a request for access to said data item at said first node, (1) determining from the dipole half stored at said first node if the status at the second node assumed by the first node is in conflict with the request, (2) if in conflict, resolving the conflict by communicating with said second node, and (3) when the conflict is resolved, granting the request for access.

5. A method for operating a computing apparatus including a plurality of nodes, with each node having means for storing at least one data item and means responsive to a request for accessing a specified data item, and communication means interconnecting selected nodes, the computing apparatus being operated in response to a request for accessing a specified data item and controlling the modification of copies of the data item at a plurality of nodes, the method characterized by the steps of:

generating a data request specifying a required currency for a specific data item at the node of the request;

determining if the node of the request views any other node as having for said specific data item a currency status which is in conflict with said required currency;

resolving currency conflicts; and

thereafter

granting the request for accessing the specified data item.

6. A method for operating a first node of a multinode computing apparatus, said first node including means for storing at least one data item, means responsive to a request for accessing a specified data item, and a port for communicating data and control signals with respect to at least one other node, said first node being operated in response to a request for accessing a specified data item and controlling the modification of copies of data items at said first node, the method characterized by the steps of:

generating a data request specifying a required currency for a specific data item at said first node;

determining if said first node views any other node as having for said specific data item a currency status which is in conflict with said required currency;

communicating a message containing a data request to other nodes and receiving from each such other node a response resolving any currency conflicts; and

thereafter

granting the request for access to the specified data item.

7. The method of claim 6, further characterized by the steps of:

storing or enabling generation of a set of dipole halves at said first node, with a dipole half in said set for each other node with which said first node shares a data item;

each such dipole half specifying the status assumed by said first node for the shared data item at the other node.

8. The method of claim 7, further characterized by the step of:

specifying in each such dipole half the currency control, quality control, and responsibility control assumed by said first node for the shared data item at an other node;

wherein said currency control describes the currency of the contents of the shared data item at said other node assumed by said first node and is established as one of exclusive, unique clean, shared clean, prior, or not accessible;

wherein said quality control defines the relative quality of the shared data item at said first node and at or through said other node; and

wherein said responsibility control specifies whether said other node has agreed to always be able to obtain a copy of said shared data item at the currency given by said currency control on behalf of said first node.

9. A method for operating a node of a computing system, said node including means for storing at least one data item and control information for use in controlling access to such data item, and a port for communicating data and control signals with respect to at least one other node, the method characterized by the steps of:

responsive to a request specifying a required currency for a specific data item at said node, determining if said node views any other node as having for said spcific data item a currency status which is in conflict with said required currency; and

for each such currency conflict, generating a message containing a data request to resolve the conflict for communication to the other node.

10. The method of claim 9, further characterized by the steps of:

responsive to a request for access to a data item, generating a request quark specifying the currency control set, quality control and responsibility control required by the said request; and

storing at said node in a status and control file for each data item stored at said node a set of dipole halves, with one dipole half in said set for each other node with which said node shares such data item, each such dipole half specifying the status of the shared data item at the other node assumed by said node.

11. A method for operating a first node of a computing system, said first node including means for storing at least one data item, means responsive to a request for accessing a specified data item, and a port for communicating data and control signals with respect to at least one other node, said first node being operated in response to the request for accessing the specified data item and controlling the modification of copies of data items at said first node, the method characterized by the steps of:

storing or enabling generation of a set of dipole halves at said first node, with a dipole half for each other node with which said node shares a data item;

responsive to a request quark specifying for a given data item the dipole half desired at said first node by a related node and the dipole half at the related node for said first node, executing a quark processing unit comprising the following steps;

determining if any dipole halves stored at said first node for said given data item have a conflicting status;

generating a conflict quark for each dipole half having a conflicting status for communication to the other node having the conflicting status;

waiting for a response to each communicated conflict quark;

modifying dipole halves stored at said first node for other nodes as required to reflect processing of said request quark, and modifying the dipole half at said first node for said related node as required to reflect processing of said request quark; and

selectively generating a response quark or otherwise responding to the originator of said request quark.

12. A method for operating a computing system including a plurality of nodes interconnected by a communication network;

each node storing in a data file a plurality of data items which may be unique or copies of data items stored at other nodes;

each node, responsive to a request for access to a specified data item by an application, controlling the applications'"'"'s access to said stored data item; and

each node selectively communicating the updated data item to other nodes storing copies of the specified dta item;

wherein improvements to the controlling, storing, and communicating steps provide dynamic replication of data under distributed system control and comprise the steps of;

storing a dipole with respect to a data item shared by a node pair, a dipole half being stored in each node of the node pair specifying the status, assumed by this node, of the shared data item at a related node, with the data state of a given data item at this node being defined by the set of dipole halves stored at this node with respect to all related nodes sharing copies of that given data item;

responsive to a request for access to a data item from an application at this node having a copy of the data item at a data state consistent with the request, granting the request without network interaction with related nodes;

responsive to a request for access to a data item from an application at this node having a data state conflict with the request, negotiating a dipole change with each related node with which this node receiving the access request shares a conflicting dipole, and upon resolution of all such conflicts, granting the request; and

responsive to an update request which has been granted, storing the updated data item at this node and only thereafter in connection with an application request communicating from some other node, or in the course of data base conformation processing, communicating the updated item to that other node.