System and method for providing highly available data storage using globally addressable memory

• US 5,909,540 A
• Filed: 05/02/1997
• Issued: 06/01/1999
• Est. Priority Date: 11/22/1996
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ManageSoft Corporation (Flexera Software LLC)
• Inventors: Carter, John B., Lee, Hsin H., Porter, David, Woods, John, Phillips, Robert S., Frank, Steven J., Dietterich, Daniel J., Davis, Scott H.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elmore, Stephen C.
• Application Number:
  US08/848,967
• Time in Patent Office: 760 Days
• Field of Search: 395/182.02, 395/183.01, 395/185.01, 395/183.16, 395/200.31, 395/200.44, 395/200.45, 395/200.51, 395/406, 707/10, 707/202, 711/6, 711/162, 711/202, 711/203
• US Class Current: 714/4.4
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: H04L 67/00 Network arrangements or protocols for supporting network services or applications user-to-user messaging H04L51/00; network arrangements, protocols or services for supporting real-time applications in data packet communications networks H04L65/00
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/75 Indicating network or usage conditions on the user display
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/966 : Distributed
• CPC Class Codes: Y10S 707/99943 : Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 : Object-oriented database structure processing

Abstract

A network of computer node interface to globally addressable memory system that provides persistent storage of data exchange periodic connectivity information. The exchanged connectivity information provides information regarding node failure to other nodes in the system, and the surviving nodes use the information to determine which node, if any, has ceased functioning. Various processes are used to recover the portion of the global address space for which the failed node was responsible, including RAM directory, disk directory, or file system information. Additionally, nodes may be subdivided into groups and connectivity information is exchanged between nodes belonging to a group. Each group then exchanges group-wise connectivity information and failures may be recovered.

Claims

1. In a system for providing distributed control over data, a method for continuing operation after a node failure, the method comprising:

(a) providing a plurality of nodes inter-connected by a network which periodically exchange connectivity information;

(b) storing on each node an instance of a data control program for manipulating data to provide multiple, distributed instances of the data control program;

(c) interfacing each instance of the data control program to a distributed shared memory system that provides distributed storage across the inter-connected node and that provides addressable persistent storage of data;

(d) operating each instance of the data control program to employ the shared memory system as a memory device having data contained therein, whereby the shared memory system maintains multiple, persistent copies of data distributed among more than one network node;

(e) determining from the exchanged connectivity information the failure of a node;

(f) determining a portion of the data for which the failed node was responsible; and

(g) storing a copy of the portion of the data for which the failed node was responsible in persistent storage hosted by a surviving node.

2. The method of claim 1 wherein step (a) further compromises:

(a-a) providing a plurality of nodes interconnected by a network;

(a-b) designating a heartbeat monitor node from the plurality of interconnected nodes;

wherein the plurality of nodes periodically transmit information to the heartbeat monitor node and the heartbeat monitor node periodically broadcasts information to the plurality of the nodes.

3. The method of claim 1 wherein step (a) further comprises:

(a-a) providing a plurality of nodes interconnected by a network, the nodes organized into hierarchical groups of nodes;

(a-b) designating a heartbeat monitor node for each group of nodes,

wherein each node in a group periodically transmits information to the heartbeat monitor node for the group, each heartbeat monitor node periodically broadcasts information to the nodes belonging to its group, and the plurality of heartbeat monitor nodes exchange information.

4. The method of claim 2 wherein step (e) comprises determining the failure of a node from the absence of exchanged information from the node.

5. The method of claim 1 wherein step (d) comprises operating each instance of the data control program to employ the shared memory system as a memory device having data contained therein, whereby the shared memory system uses a directory to coordinate access to data stored in volatile memory elements associated with each node and maintains multiple, persistent copies of data distributed among more than one network node.

6. The method of claim 5 wherein step (f) further comprises:

(f-a) determining a portion of the data which the failed node had stored in its associated volatile memory element; and

(f-b) determining a portion of the data which the failed node had stored in its associated persistent memory element.

7. The method of claim 5 wherein step (g) comprises rebuilding the volatile memory directory.

8. In a system for providing distributed control over data, a method for continuing operation after a node failure, the method comprising:

(a) providing a plurality of nodes inter-connected by a network which periodically exchange connectivity information;

(b) storing on each node an instance of a data control program for manipulating data to provide multiple, distributed instances of the data control program;

(c) interfacing each instance of the data control program to a globally addressable data store that provides distributed storage across the inter-connected node and that provides addressable persistent storage of data;

(d) operating each instance of the data control program to employ the globally addressable data store as a memory device having data contained therein, whereby the globally addressable data store maintains multiple, persistent copies of data distributed among more than one network node;

(e) determining from the exchanged connectivity information the failure of a node;

(f) determining a portion of the data for which the failed node was responsible; and

(g) storing a copy of the portion of the data for which the failed node was responsible in persistent storage hosted by a surviving node.

9. The method of claim 8 wherein step (a) further compromises:

(a-a) providing a plurality of nodes interconnected by a network;

(a-b) designating a heartbeat monitor node from the plurality of interconnected nodes;

wherein the plurality of nodes periodically transmit information to the heartbeat monitor node and the heartbeat monitor node periodically broadcasts information to the plurality of the nodes.

10. The method of claim 8 wherein step (a) further comprises:

(a-a) providing a plurality of nodes interconnected by a network, the nodes organized into hierarchical groups of nodes;

(a-b) designating a heartbeat monitor node for each group of nodes, wherein each node in a group periodically transmits information to the heartbeat monitor node for the group, each heartbeat monitor node periodically broadcasts information to the nodes belonging to its group, and the plurality of heartbeat monitor nodes exchange information.

11. The method of claim 9 wherein step (e) comprises determining the failure of a node from the absence of exchanged information from the node.

12. The method of claim 8 wherein step (d) comprises operating each instance of the data control program to employ the globally addressable data store as a memory device having data contained therein, whereby the globally addressable data store uses a directory to coordinate access to data stored in volatile memory elements associated with each node and maintains multiple, persistent copies of data distributed among more than one network node.

13. The method of claim 12 wherein step (f) further comprises:

(f-a) determining a portion of the data which the failed node had stored in its associated volatile memory element; and

(f-b) determining a portion of the data which the failed node had stored in its associated persistent memory element.

14. The method of claim 12 wherein step (g) comprises rebuilding the volatile memory directory.