US5909540A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for providing highly available data storage using globally addressable memory
Assignee: Google LLC
•
Filing: 1997-05-02
•
Granted: 1999-06-01
•
Expires: 2017-05-02
Abstract
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.
Inventors
- 👤 John B. Carter
- 👤 Scott H. Davis
- 👤 Daniel J. Dietterich
- 👤 Steven J. Frank
- 👤 Robert S. Phillips
- 👤 John Woods
- 👤 David Porter
- 👤 Hsin H. Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 03:40
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5011; G06F9/5016; G06F11/00; G06F11/07; G06F11/0703; G06F11/0706; G06F11/0721; G06F11/0724; G06F11/0751; G06F11/0754; G06F11/0757; G06F11/14; G06F11/1402; G06F11/1415; G06F11/142; G06F11/1425; G06F11/1435; G06F11/16; G06F11/18; G06F11/182; G06F11/20; G06F11/2053; G06F11/2094; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0813; G06F12/10; G06F12/1072; G06F15/00; G06F15/16; G06F15/163; G06F15/167; G06F16/00; G06F16/90; G06F16/95; G06F16/957; G06F16/9574; H; H04; H04L; H04L67/00; H04L67/01; H04L67/02; H04L67/10; H04L67/1001; H04L67/50; H04L67/75; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329; H04L69/40; H04L69/24; Y; Y10; Y10S; Y10S707/00; Y10S707/964; Y10S707/966; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
185 words
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.
Claim 2
Dependent Claim
185 words
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.
Claim 3
Dependent Claim
59 words
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.
Claim 4
Dependent Claim
79 words
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.
Claim 5
Dependent Claim
24 words
The method of claim 2 wherein step (e) comprises determining the failure of a node from the absence of exchanged information from the node.
Claim 6
Dependent Claim
67 words
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.
Claim 7
Dependent Claim
49 words
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.
Claim 8
Dependent Claim
14 words
The method of claim 5 wherein step (g) comprises rebuilding the volatile memory directory.
Claim 9
Dependent Claim
187 words
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.
Claim 10
Dependent Claim
187 words
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.
Claim 11
Dependent Claim
59 words
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.
Claim 12
Dependent Claim
79 words
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.
Claim 13
Dependent Claim
24 words
The method of claim 9 wherein step (e) comprises determining the failure of a node from the absence of exchanged information from the node.
Claim 14
Dependent Claim
69 words
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.
Claim 15
Dependent Claim
49 words
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.
Claim 16
Dependent Claim
14 words
The method of claim 12 wherein step (g) comprises rebuilding the volatile memory directory.
References Cited (Backward Citations)
US4096567A
Cited
US4426688A
Cited
US4868738A
Cited
US4710926A
Cited
EP0288636A2
Cited
US5055999A
Cited
US5251308A
Cited
US5335325A
Cited
US5119481A
Cited
US5297265A
Cited
US5226039A
Cited
US5282201A
Cited
US5341483A
Cited
US5077736A
Cited
US5117350A
Cited
US4934764A
Cited
US5551035A
Cited
US5247673A
Cited
US5274789A
Cited
US5390316A
Cited
GB2257273A
Cited
US5560029A
Cited
US5313647A
Cited
US5245563A
Cited
US5423037A
Cited
US5592625A
Cited
US5522045A
Cited
US5452447A
Cited
US5394555A
Cited
US5493728A
Cited
US5408649A
Cited
US5390326A
Cited
WO1995002307A1
Cited
US5617537A
Cited
WO1995014279A1
Cited
US5560027A
Cited
EP0661651A1
Cited
US5649194A
Cited
US5701462A
Cited
US5689700A
Cited
US5675787A
Cited
US5588147A
Cited
US5519855A
Cited
US5490272A
Cited
WO1995022111A1
Cited
US5812533A
Cited
WO1995025306A2
Cited
US5613079A
Cited
WO1996023268A1
Cited
US5513314A
Cited
WO1996030847A1
Cited
US5727150A
Cited
US5812751A
Cited
US5687308A
Cited
US5781537A
Cited
US5805785A
Cited
US5832514A
Cited
US5768510A
Cited
US5805786A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-31 | 2002-11-30 | 2003-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-31 | 2006-11-30 | 2007-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-31 | 2010-11-30 | 2011-06-01 | $7700.00 | Window Closed / Lapsed |