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

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.sup.S.sub.x, for storing said F fragments in the data processors in each said group, where for a particular fragment F.sup.S.sub.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.sup.S.sub.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).multidot.Q(S) ) modulo avail
• where y identifies which data processor fragment F.sup.S.sub.x is assigned to, N.sub.S is the number of data processors in group S used for storing database fragments, Q(S) is an integer between 0 and N.sub.S -1 where Q(S) is a distinct value for each said group, and avail is the number of said N.sub.S data processors that have not failed.