Fault tolerant computer parallel data processing ring architecture and work rebalancing method under node failure conditions

Claim 2

A fault-tolerant parallel data processing system, comprising: a plurality of more than two disk subsystems for distributed data storage of data fragments in groups of predetermined numbers of data fragments, a corresponding plurality of data processing nodes, referred to as nodes, for processing data fragments in said plurality of disk subsystems, said plurality of disk subsystems being interconnected with said plurality of nodes in a ring topology wherein each node has a first neighbor in a first direction along the ring and a second neighbor in a second direction along the ring, said nodes being interconnected through an interconnection system, each of said nodes being connected only to a single pair of disk subsystems on the ring and each of said disk subsystems being connected only to a single pair of nodes on the ring such that the data fragments being processed by any given one of said nodes during no-fault conditions are accessible by the given node's first neighbor, so that when any particular one of said nodes experiences a fault condition, the data fragments that were being processed by said particular node are processed by said particular node's first neighbor without moving the data fragments between disk subsystems, and at least some of the data fragments that were being processed by said particular node's first neighbor are processed by said particular node's first neighbor's first neighbor, whereby data processing loads can be balanced over said nodes during both fault and no-fault conditions on both sides of said particular node.

Claim 3

The system of claim 1, wherein said nodes and said disk subsystems are interconnected with a single bus structure.

Claim 4

The system of claim 1, wherein when said particular one of said nodes experiences a fault condition, said ring topology is broken into one or more chains comprising disk subsystems and other nodes connected to the particular node.

Claim 5

The system of claim 1, wherein when said particular node experiences a fault condition, data processing workload of said particular node is redistributed among other nodes which comprise a particular chain associated with said particular node which has experienced a fault condition.

Claim 6

The system of claim 4, wherein when said particular node experiences a fault condition, said data processing workload of said particular node is redistributed substantially evenly over said other nodes of said particular chain.

Claim 7

The system of claim 4, wherein when said particular node experiences a fault condition, said data processing workload of said particular node is redistributed such that data processing workload of any particular node of said particular chain does not deviate from the data processing workload of any other node of said particular chain by more than one data fragment.

Claim 8

The system of claim 1, wherein at least one of said disk subsystems comprises a plurality of interconnected disks.

Claim 9

The system of claim 1, wherein all of said data fragments are substantially equal in size.

Claim 10

The system of claim 1, wherein each node of the system is primarily associated with a particular disk subsystem, so that before a fault occurs data fragments stored on a given disk subsystem are initially processed by the node with which the disk subsystem is primarily associated.

Claim 11

The method of claim 1, wherein said data fragments of said particular node experiencing a fault condition being processed by said particular node's first neighbor comprises: data fragments of said particular node whose processing has been shifted in a clockwise manner to said particular node's first neighbor on the right.

Claim 12

The method of claim 1, wherein said data fragments of said particular node experiencing a fault condition being processed by said particular node's first neighbor comprises: data fragments of said particular node whose processing has been shifted in a counter-clockwise manner to said particular node's first neighbor on the left.

Claim 13

The system of claim 1, wherein said at least some of the data fragments that were being processed by said particular node's first neighbor comprise: all of the data fragments that were being processed by said particular node's first neighbor.

Claim 14

The system of claim 1, wherein processing of some of the data fragments of the node experiencing a fault condition is shifted clockwise to said particular node's first neighbor on the right and processing of others of said particular node's data fragments is shifted counter-clockwise to said particular node's first neighbor on the left.

Claim 15

The system of claim 1, wherein processing of data fragments of the particular node experiencing a fault condition is repeatedly shifted to successive neighbors within the ring topology until all data fragments of said particular node experiencing a fault condition are being processed by said particular node's first neighbor, so that increased processing resulting from the fault is evenly absorbed by others of said nodes.

Claim 16

The system of claim 1, wherein shifting of processing of data fragments results in an incremental increase in workload at each node other than the particular node, said incremental increase being equal to processing for a single data fragment greater than that originally being processed.

Claim 17

The system of claim 1, wherein said data fragments are distributed among said disk subsystems so that multiple threads of computation are enabled to permit access to multiple fragments of data in parallel.

Claim 18

In a computer system comprising a plurality of processing nodes and a plurality of more than two disk subsystems, a method for providing fault-tolerant data processing, the method comprising: (a) partitioning data storage into groups of predetermined numbers of data fragments; (b) interconnecting said plurality of disk subsystems with said plurality of nodes in a closed-loop topology wherein each node has a first neighbor in a first direction along the closed loop and a second neighbor in a second direction along the closed loop, said nodes being interconnected through an interconnection system, each of said nodes being connected only to a single pair of disk subsystems on the closed loop and each of said disk subsystems being connected only to a single pair of nodes on the closed loop such that the data fragments being processed by any given one of said nodes during no-fault conditions are accessible by the given node's first neighbor; (c) experiencing a fault condition at a particular one of said nodes; and (d) shifting processing of the data fragments such that the data fragments that were being processed by said particular node are processed by said particular node's first neighbor without moving the data fragments between disk subsystems, and at least some of the data fragments that were being processed by said particular node's first neighbor are processed by said particular node's first neighbor's first neighbor, wherein data processing loads can be balanced over said nodes during both fault and no-fault conditions on both sides of said particular node.

Claim 19

In a computer system comprising a plurality of processing nodes and a plurality of more than two disk subsystems, a method for providing fault-tolerant data processing, the method comprising: (a) partitioning data storage into groups of predetermined numbers of data fragments; (b) interconnecting said plurality of disk subsystems with said plurality of nodes in a closed-loop topology wherein each node has a first neighbor in a first direction along the closed loop and a second neighbor in a second direction along the closed loop, said nodes being interconnected through an interconnection system, each of said nodes being connected only to a single pair of disk subsystems on the closed loop and each of said disk subsystems being connected only to a single pair of nodes on the closed loop such that the data fragments being processed by any given one of said nodes during no-fault conditions are accessible by the given node's first neighbor; (c) experiencing a fault condition at a particular one of said nodes; and (d) shifting processing of the data fragments such that the data fragments that were being processed by said particular node are processed by said particular node's first neighbor without moving the data fragments between disk subsystems, and at least some of the data fragments that were being processed by said particular node's first neighbor are processed by said particular node's first neighbor's first neighbor, wherein data processing loads can be balanced over said nodes during both fault and no-fault conditions on both sides of said particular node.

Claim 20

The method of claim 17, wherein said interconnecting steps includes interconnecting said nodes and said disk subsystems in a single bus structure.

Claim 21

The method of claim 17, wherein when said particular one of said nodes experiences a fault condition, said closed-loop topology is broken into one or more chains comprising disk subsystems and other nodes connected to the particular node.

Claim 22

The method of claim 17, wherein when said particular node experiences a fault condition, data processing workload of said particular node is redistributed among other nodes which comprise a particular chain associated with said particular node which has experienced a fault condition.

Claim 23

The method of claim 20, wherein when said particular node experiences a fault condition, said data processing workload of said particular node is redistributed substantially evenly over said other nodes of said particular chain.

Claim 24

The method of claim 20, wherein when said particular node experiences a fault condition, said data processing workload of said particular node is redistributed such that data processing workload any particular node of said particular chain does not deviate from the data processing workload of any other node of said particular chain by more than one data fragment.

Claim 25

The method of claim 17, wherein said system processes said data fragments in parallel.

Claim 26

The method of claim 17, wherein all of said data fragments are substantially equal in size.

Claim 27

The method of claim 17, wherein each node of the system is primarily associated with a particular disk subsystem, so that before a fault occurs data fragments stored on a given disk subsystem are initially processed by the node with which the disk subsystem is primarily associated.

Claim 28

The method of claim 17, wherein said shifting processing step includes: shifting processing of data fragments of said particular node in a clockwise manner to said particular node's first neighbor on the right.

Claim 29

The method of claim 17, wherein said shifting step includes: shifting processing of data fragments of said particular node in a counter-clockwise manner to said particular node's first neighbor on the left.

Claim 30

The method of claim 17, wherein said at least some of the data fragments that were being processed by said particular node's first neighbor comprise: all of the data fragments that were being processed by said particular node's first neighbor.

Claim 31

The method of claim 17, wherein said shifting step includes: shifting processing of some of the data fragments of the node experiencing a fault condition clockwise to said particular node's first neighbor on the right and shifting processing of others of said particular node's data fragments counter-clockwise to said particular node's first neighbor on the left.

Claim 32

The method of claim 17, wherein said shifting step includes: shifting processing of data fragments of the particular node experiencing a fault condition repeatedly to successive neighbors within the closed-loop topology until all data fragments of said particular node experiencing a fault condition are being processed by said particular node's first neighbor, so that increased processing resulting from the fault is evenly absorbed by others of said nodes.

Claim 33

The method of claim 17, wherein said shifting step includes: shifting processing of data fragments such that only an incremental increase in workload results at each node other than the particular node, said incremental increase being equal to processing for a single data fragment greater than that originally being processed.

Claim 34

The method of claim 17, wherein said data fragments are distributed among said disk subsystems so that multiple threads of computation are enabled to permit access to multiple fragments of data in parallel.

Claim 35

The method of claim 17, wherein said closed-loop topology comprises a ring topology.