Method for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failure
First Claim
1. In a distributed computing network containing a plurality of interconnected nodes, each node comprising a processor and data storage means, a plurality of data files or non-volatile storage distributed among said nodes including a tree structure of key-index data, said tree structure of key-index data including a ROOT of the tree structure for a top level of the tree, a method for balancing, among nodes, said tree structure, comprising processor executed steps of:
- a. providing said ROOT in a file in a non-volatile storage, said ROOT including first and second lists, each being a list of keys describing a distribution of key-index data indentifiers are distributed, copies of said ROOT;
c. determining if a first node contains an excess of said key-index data indentifiers in comparison to a second node;
d. upon a determination of said excess, moving said excess key-index data indentifiers to non-volatile storage on said second node to achieve an approximately balanced distribution thereof; and
e. updating said second lists in files containing copies of said ROOT in said first and second nodes by noting each move of a key index data identifier, whereby upon a malfunction of either said first or second node before said approximate balance is achieved, a difference in entries exists between said first and second lists in a ROOT file in a non-failed first or second node that enables system recovery.
1 Assignment
0 Petitions
Accused Products
Abstract
A distributed network is described which contains a plurality of interconnected nodes each node including a processor and data storage apparatus. A plurality of key-index data identifiers are distributed among the nodes, with each node including a tree data structure in non-volatile storage defining locations of the key-index data identifiers. The tree data structure includes a ROOT data structure comprising two lists, "NEW ROOT" and "OLD ROOT", each comprised of an ordered array of boundaries assigned nodes for the top level of the tree. A method is described for balancing the tree data structure which comprises the steps of:
a. a providing in each of the nodes across which the key-index data identifiers are distributed, at least copies of the two lists, "NEW ROOT" and "OLD ROOT", of the ROOT data structure;
b. determining when a first node contains an excess of key-index data identifiers;
c. moving the excess of key-index data identifiers to a second node;
d. updating the first node/second node boundary value in "NEW ROOT" of the ROOT data structure and the copies of "NEW ROOT" in the first and second nodes to note the movement of the data file identifiers, whereby in the event of a malfunction of one of the nodes, a record exists in both of the nodes of both an updated and non-updated ROOT data structure to enable data recovery.
166 Citations
11 Claims
-
1. In a distributed computing network containing a plurality of interconnected nodes, each node comprising a processor and data storage means, a plurality of data files or non-volatile storage distributed among said nodes including a tree structure of key-index data, said tree structure of key-index data including a ROOT of the tree structure for a top level of the tree, a method for balancing, among nodes, said tree structure, comprising processor executed steps of:
-
a. providing said ROOT in a file in a non-volatile storage, said ROOT including first and second lists, each being a list of keys describing a distribution of key-index data indentifiers are distributed, copies of said ROOT; c. determining if a first node contains an excess of said key-index data indentifiers in comparison to a second node; d. upon a determination of said excess, moving said excess key-index data indentifiers to non-volatile storage on said second node to achieve an approximately balanced distribution thereof; and e. updating said second lists in files containing copies of said ROOT in said first and second nodes by noting each move of a key index data identifier, whereby upon a malfunction of either said first or second node before said approximate balance is achieved, a difference in entries exists between said first and second lists in a ROOT file in a non-failed first or second node that enables system recovery. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
Specification