Reliable array of distributed computing nodes

• US 6,088,330 A
• Filed: 10/01/1997
• Issued: 07/11/2000
• Est. Priority Date: 09/09/1997
• Status: Expired due to Term

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: LeMahieu, Paul, Fan, Chenggong, Bohossian, Vasken, Xu, Lihao, Bruck, Joshua, Riedel, Marcus David Daniel
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US08/943,049
• Time in Patent Office: 1,014 Days
• Field of Search: 709/217-9, 709/223, 709/224, 709/201, 370/242-4, 370/216-7, 370/221-228, 711/114, 711/127, 711/162, 348/13, 348/12, 348/7, 455/5.1, 455/4.2, 714/30, 714/31
• US Class Current: 370/228
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A system which uses redundant storage and redundant communication to provide a robust distributed server system.

Claims

1. A redundant distributed network system, comprising:

a plurality of system nodes, each of said system nodes including at least two communication devices and a storage device, said storage device including redundant storage information for the network to permit reconstruction of stored data from the storage information in any one node when combined with data in any other node;

a plurality of switching devices, connected to said communication devices of said system nodes in a way such that each of said conmunuication devices in any one system node is connected to a different one of said switching devices, allowing each of said system nodes to communicate to each other of said system nodes over one of at least two different paths, thereby providing redundant communication;

a detection routine at each node which detects system functional stated which may prevent any operation of the network system; and

a logical network process which reconfigures the network using one of at least said communication device redundancy and said storage information redundancy as needed to compensate for the system functional state using the network redundancy.

2. A system as in claim 1, wherein said detection routine detects functional states on at least a plurality of said system nodes, with an identical protocol being run by each said detection routine on each of said system nodes.

3. A system as in claim 1, wherein said system functional state include faults in network communication or faults in memory storage or any other kind of fault which produces an undesired result.

4. A system as in claim 3, wherein when said system functional state includes a fault in network communication, said logical network process commands a connection to be changed to a different connection.

5. A system as in claim 4, wherein when said system functional state includes a fault in memory storage, said logical network process commands desired information to be obtained from said redundant data storage.

6. A system as in claim 1, wherein said detection routine operates in each node to view a state of connection to other nodes in the network.

7. A system as in claim 6, wherein said detection routine operates to determine said state of connection using hints about a condition of the network.

8. A system as in claim 7, wherein said hints include a heartbeat signal which is produced by each said node at specified intervals, and said detection routine operates to receive said heartbeat signal and to detect a presence or absence of said heartbeat signal as one of said hints.

9. A system as in claim 7, further comprising a token passing system, wherein each node determines events in a monitored node over a monitored channel and passes a token to said monitored node over said monitored channel to indicate said event, wherein said monitored node passes back said token to indicate operation based on said event, and wherein each node has only a specified number of tokens to limit a number of events which can occur on one of said nodes without a corresponding event occurring on the other of said nodes.

10. A system as in claim 6, further comprising means for guaranteeing that each said node sees a same history of the network.

11. A system as in claim 1, wherein said connection is made such that no groups of computing nodes can be isolated.

12. A system as in claim 1, wherein said switches connect said nodes in the most non-local way possible.

13. A system as in claim 12, wherein said switches connect between two nodes which are farthest from one another.

14. A system as in claim 13, wherein said connections are made such that no failure of any two nodes can isolate any group of nodes from communicating with any other group of nodes.

15. A system as in claim 1 wherein each node is connected with each other node by at least two paths, and further comprising a network monitor process running at each said node and monitoring all connections from a local node on which said network monitor is running to each remote node over each connection path from the local node to the remote node.

16. A system as in claim 15, further comprising a reliable user data protocol running on said local node, and receiving a request to communicate from the local node to some other node, and determining a path from said network monitor process.

17. A system as in claim 16, further comprising reconfiguring a path of said communicating using a logical network interconnection that allows changing a physical connection between the nodes to a different node connection.

18. A system as in claim 1, further comprising a network monitor, determining operational connections among said nodes, a reliable user protocol, which processes information for the running nodes, and a logical network which reconfigures the communications based on said operational connections.

19. A system as in claim 1, wherein said storage device stores only a part of the information on each disk of each node.

20. A system as in claim 19, wherein each disk of each node also stores information indicating some property of information on other disks.

21. A redundant distributed server, comprising:

an array of distributed computing nodes, each of said computing nodes having different stored information man each other node, and said stored information being redundant among said computing nodes to permit reconstruction of stored data from the stored information in any one node when combined with data in any other node;

a switching system, connected to said array of computing nodes, and providing redundant communication paths among said array of computing nodes, operating such that any specified number of network faults will not affect the operation of the remaining nodes of the system, each of said computing nodes running the same protocol to determine network status, such that each said computing node will see the same network history and each said computing node including a detection routine that detects a system functional state that may prevent operation of the network system.

22. A server as in claim 21, wherein said stored information on each node stores only part, but not all of any desired information, and wherein no two nodes store the same information.

23. A server as in claim 22, wherein said stored information at a node includes an information portion, and a redundancy portion, said redundancy portion being information indicative of information portions for other nodes only.

24. A server as in claim 23, wherein said redundancy portion is formed from an array code where a plurality of said nodes are arranged into an array to form said information portion, and said redundancy portion are formed from checksums along diagonals of said array.

25. A redundant video server system, comprising:

a plurality of system video storage nodes, each of said system video storage nodes including at least two communication devices and a storage device, said storage device including redundant storage of video information;

a plurality of switching devices, connected to said communication devices of said system video storage nodes in a way such that each of said communication devices in any one system node is connected to a different one of said switching devices, allowing each of said system nodes to communicate to each other of said system nodes over one of at least two different paths, thereby providing redundant communication,

a connection on said switching devices and the redundant storage of video information being of a form that no specified number of failures can interrupt operation of the video server;

a detection routine at each node which detects system functional state which may prevent any operation of the network system; and

a logical network process which reconfigures the network using one of at least said communication redundancy or said storage redundancy to compensate for the system functional state using the network redundancy.

26. A method of operating a network to provide redundancy, comprising:

executing a controlling process that carries out a distributed read from a plurality of nodes, each of the nodes including at least two communication devices and a storage device, collectively storing system data, each node storing raw data, and redundant data indicative of raw data that is stored in nodes other than said each node, each node including a detection routine which detects system functional state which may prevent any operation of the network system;

communicating data between the nodes with a plurality of switching devices, connected to the communication devices in a way such that each of the communication devices in any one node is connected to a different one of the switching devices, allowing each of the nodes to communicate to each other of the nodes over one of at least two different paths, thereby providing redundant communication; and

performing a distributed read comprising the steps of

determining a parameter related to availability of nodes, and

reading said raw data from said plurality of nodes if said parameter indicates availability, and reading both said raw data and said redundant data from less than said plurality of nodes if said parameter indicates less than availability.