US5555404A — Continuously available database server having mul…

Claim 1

Independent Claim 469 words

A multiprocessor computer system, comprising: N data processors, wherein N is a positive integer greater than three, each data processor having its own, separate, central processing unit, memory for storing database tables and other data structures, and communication channels for communication with other ones of said N data processors; each of said N data processors independently executing a distinct instruction data stream; at least a plurality of said N data processors including a communications processor for receiving transaction requests and for transmitting responses thereto; said N data processors being divided into at least two groups, each having at least two data processors; each data processor including: fragmenting means for fragmenting each of said database tables into N fragments, and for storing replicas of each fragment in different ones of said N data processors, wherein said different ones of said N data processors are in different ones of said groups of data processors such that a complete copy of each of said database tables is located within each said group of data processors and such that simultaneous failure of all data processors in either of said groups would leave a complete copy of each of said database tables in the other of said groups of data processors; a data dictionary that stores information indicating where each said replica replica of each fragment of said database tables is stored among said N data processors; said fragmenting means further adapted for changing the information stored in said data dictionary upon failure of any one of said N data processors to indicate that the replicas stored on the failed data processor are not available, and for regenerating said replicas on the failed data processor in non-failed ones, if any, of the data processors in the same group of data processors as the failed data processor; and said fragmenting means further adapted for dividing said database tables into F fragments F S x , for storing said F fragments in the data processors in each said group, where for a particular fragment F S x , S identifies the group of data processors in which the fragment is stored and x is an index that identifies the fragment and has a value between 0 and F-1; said fragmenting means adapted to assign each fragment F S x to a data processor y in group S in accordance with the following fragment to node assignment equation: y=(x+(xdiv N.sub.S)·Q(S) ) modulo avail where y identifies which data processor fragment F S x is assigned to, N S is the number of data processors in group S used for storing database fragments, Q(S) is an integer between 0 and N S -1 where Q(S) is a distinct value for each said group, and avail is the number of said N S data processors that have not failed.

Claim 2

Dependent Claim 469 words

A multiprocessor computer system, comprising: N data processors, wherein N is a positive integer greater than three, each data processor having its own, separate, central processing unit, memory for storing database tables and other data structures, and communication channels for communication with other ones of said N data processors; each of said N data processors independently executing a distinct instruction data stream; at least a plurality of said N data processors including a communications processor for receiving transaction requests and for transmitting responses thereto; said N data processors being divided into at least two groups, each having at least two data processors; each data processor including: fragmenting means for fragmenting each of said database tables into N fragments, and for storing replicas of each fragment in different ones of said N data processors, wherein said different ones of said N data processors are in different ones of said groups of data processors such that a complete copy of each of said database tables is located within each said group of data processors and such that simultaneous failure of all data processors in either of said groups would leave a complete copy of each of said database tables in the other of said groups of data processors; a data dictionary that stores information indicating where each said replica replica of each fragment of said database tables is stored among said N data processors; said fragmenting means further adapted for changing the information stored in said data dictionary upon failure of any one of said N data processors to indicate that the replicas stored on the failed data processor are not available, and for regenerating said replicas on the failed data processor in non-failed ones, if any, of the data processors in the same group of data processors as the failed data processor; and said fragmenting means further adapted for dividing said database tables into F fragments F S x , for storing said F fragments in the data processors in each said group, where for a particular fragment F S x , S identifies the group of data processors in which the fragment is stored and x is an index that identifies the fragment and has a value between 0 and F-1; said fragmenting means adapted to assign each fragment F S x to a data processor y in group S in accordance with the following fragment to node assignment equation: y=(x+(xdiv N.sub.S)·Q(S) ) modulo avail where y identifies which data processor fragment F S x is assigned to, N S is the number of data processors in group S used for storing database fragments, Q(S) is an integer between 0 and N S -1 where Q(S) is a distinct value for each said group, and avail is the number of said N S data processors that have not failed.

Claim 3

Dependent Claim 23 words

The multiprocessor computer system of claim 1, wherein each of said groups of data processors have different power supplies and different cooling systems.

Claim 4

Dependent Claim 98 words

The multiprocessor computer system of claim 1, wherein said fragmenting means is adapted to respond to failure of a data processor in one of said groups by (A) remapping data processor indices y associated with said one group into a contiguous set ranging from 0 to avail-1, where avail is the number of said data processors at said one site that have not failed, and (B) reassigning each fragment F S x previously stored on said failed data processor to another data processor y in said one group S in accordance with said fragment to node assignment equation.

Claim 5

Dependent Claim 122 words

The multiprocessor computer system of claim 1, wherein said fragmenting means in each data processor is adapted to respond to failure of one of said N data processors by (A) updating said data dictionary to indicate that the fragment replicas on said one data processor are not available, (B) locating available ones of said fragment replicas corresponding to the fragment replicas on said one data processor, and (C) storing on a subset of said N data processors that have not failed, new replicas of the fragment replicas made unavailable by said failure on said one data processor such that a replica of each said database table fragment is stored in data processors that have not failed in each group of data processors.

Claim 6

Independent Claim 468 words

A method of distributing data storage and transactional workloads in multiprocessor computer system having: N data processors, wherein N is a positive integer greater than three, each data processor having its own, separate, central processing unit, memory for storing database tables and other data structures, and communication channels for communication with other ones of said N data processors; at least a plurality of said N data processors including a communications processor that receives transaction requests and transmits responses thereto; said N data processors being divided into at least two groups, each having at least two data processors; the steps of the method comprising: independently executing a distinct instruction data stream on each of said N data processors; fragmenting each of said database tables into N fragments, and storing replicas of each fragment in different ones of said N data processors, wherein said different ones of said N data processors are in different ones of said groups of data processors such that a complete copy of each of said database tables is located within each said group of data processors and such that simultaneous failure of all data processors in either of said groups would leave a complete copy of each of said database tables in the other of said groups of data processors; said fragmenting step including allocating each record in any one of said database tables to a particular one of its N fragments in accordance with predefined criteria; storing in a data dictionary in each of said N data processors information indicating where each said replica of each fragment of said database tables is stored among said N data processors; and upon failure of any one of said N data processors, changing the information stored in said data dictionary to indicate that the replicas stored on the failed data processor are not available; said fragmenting step including dividing said database tables into F fragments F S x , storing said F fragments in the data processors in each said group, where for a particular fragment F S x , S identifies the group of data processors in which the fragment is stored and x is an index that identifies the fragment and has a value between 0 and F-1; said fragmenting step assigning each fragment F S x to a data processor y in group S in accordance with the following fragment to node assignment equation: y=(x+(x div N.sub.S)·Q(S) ) modulo avail where y identifies which data processor fragment F S x is assigned to, N S is the number of data processors in group S used for storing database fragments, Q(S) is an integer between 0 and N S -1 where Q(S) is a distinct value for each said group, and avail is the number of said N S data processors that have not failed.

Claim 7

Independent Claim 468 words

A method of distributing data storage and transactional workloads in multiprocessor computer system having: N data processors, wherein N is a positive integer greater than three, each data processor having its own, separate, central processing unit, memory for storing database tables and other data structures, and communication channels for communication with other ones of said N data processors; at least a plurality of said N data processors including a communications processor that receives transaction requests and transmits responses thereto; said N data processors being divided into at least two groups, each having at least two data processors; the steps of the method comprising: independently executing a distinct instruction data stream on each of said N data processors; fragmenting each of said database tables into N fragments, and storing replicas of each fragment in different ones of said N data processors, wherein said different ones of said N data processors are in different ones of said groups of data processors such that a complete copy of each of said database tables is located within each said group of data processors and such that simultaneous failure of all data processors in either of said groups would leave a complete copy of each of said database tables in the other of said groups of data processors; said fragmenting step including allocating each record in any one of said database tables to a particular one of its N fragments in accordance with predefined criteria; storing in a data dictionary in each of said N data processors information indicating where each said replica of each fragment of said database tables is stored among said N data processors; and upon failure of any one of said N data processors, changing the information stored in said data dictionary to indicate that the replicas stored on the failed data processor are not available; said fragmenting step including dividing said database tables into F fragments F S x , storing said F fragments in the data processors in each said group, where for a particular fragment F S x , S identifies the group of data processors in which the fragment is stored and x is an index that identifies the fragment and has a value between 0 and F-1; said fragmenting step assigning each fragment F S x to a data processor y in group S in accordance with the following fragment to node assignment equation: y=(x+(x div N.sub.S)·Q(S) ) modulo avail where y identifies which data processor fragment F S x is assigned to, N S is the number of data processors in group S used for storing database fragments, Q(S) is an integer between 0 and N S -1 where Q(S) is a distinct value for each said group, and avail is the number of said N S data processors that have not failed.

Claim 8

Dependent Claim 84 words

The method of claim 5, wherein when a data processor in one of said groups fails, indices y associated with said groups are remapped into a contiguous set ranging from 0 to avail-1, where avail is the number of said data processors at said one site that have not failed, and then reassigning each fragment F S x previously stored on said failed data processor to another data processor y in said one group S in accordance with said fragment to node assignment equation.

Claim 9

Dependent Claim 111 words

The method of claim 5, further including responding to failure of one of said N data processors by (A) updating said data dictionary to indicate that the fragment replicas on said one data processor are not available, (B) locating available ones of said fragment replicas corresponding to the fragment replicas on said one data processor, and (C) storing on a subset of said N data processors that have not failed, new replicas of the fragment replicas made unavailable by said failure on said one data processor such that a replica of each said database table fragment is stored in data processors that have not failed in each group of data processors.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-09-10	2000-03-11	2000-09-10	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-09-10	2004-03-11	2004-09-10	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-09-10	2008-03-11	2008-09-10	$7700.00	Window Closed / Lapsed

Continuously available database server having multiple groups of nodes with minimum intersecting sets of database fragment replicas

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag