MECHANISM FOR CO-LOCATED DATA PLACEMENT IN A PARALLEL ELASTIC DATABASE MANAGEMENT SYSTEM

• US 20120041976A1
• Filed: 10/05/2011
• Published: 02/16/2012
• Est. Priority Date: 10/26/2010
• Status: Abandoned Application

• Current Assignee: Tesora, Inc. (Stratoscale Ltd.)
• Original Assignee: Tesora, Inc. (Stratoscale Ltd.)
• Inventors: ANNAPRAGADA, MRITHYUNJAYA
• Application Number:
  US13/253,222
• Publication Number:
  US 20120041976A1
• Time in Patent Office: Days
• US Class Current: 707/770
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A database management system implemented in a cloud computing environment. Operational nodes are assigned as groups of controller-nodes, compute-nodes or storage-nodes. Assignments as compute-nodes or storage-nodes vary during execution of queries. Queries specify tables for an associated database operation, and respective storage nodegroup(s). The number of nodes executing a query may change by (a) changing a compute-nodegroup, or (b) adding or removing nodes from a compute nodegroup; and/or distributing data to the storage nodegroup based on a Distribution Method which may be specified by a Distribution Vector (DV) that determines at least where each row is stored.

Claims

1. A database management system comprising:

a network interface, for receiving database queries from two or more client application processes as a network database service, the client application processes originating from two different users, the system providing a least one connection into the system for each such client application process;

a group of two or more operational nodes for executing the queries as database operations, each operational node implemented as a logical collection of software components that execute on one or more physical machines;

where the number of physical machines is not necessarily the same as the number of operational nodes;

with the operational nodes assigned as controller-nodes, compute-nodes or storage-nodes, and groups of controller-nodes forming controller nodegroups, and groups of compute-nodes forming compute nodegroups, and groups of storage nodes forming storage nodegroups;

the number of operational nodes, and their available assignment as compute-nodes or storage-nodes varying during execution of the queries;

each client connection being assigned to an associated compute nodegroup;

the queries also specifying one or more tables for an associated database operation, with each such table being assigned to a respective storage nodegroup;

the operational nodes further;

operating in parallel;

with the number of operational nodes executing a given query or queries changing during a given time interval by at least one of;

(a) changing the compute-nodegroup associated with a connection, or

(b) adding or removing nodes from the compute nodegroup associated with a connection; and

distributing data from the tables among the nodes in a storage nodegroup according to a data dependent distribution method specified by a Distribution Vector (DV), the DV including a set of attributes of the table that determine at least where each row is stored.

2. The system of claim 1 wherein the DVs each include a number of distribution columns and two DVs are considered comparable if the number of distribution columns in both DVs are the same, a corresponding distribution column in both DVs share a canonical representation, and the size of a binary representation of both the DVs is the same.

3. The system of claim 2 wherein two DVs are considered identical if they are comparable and their binary representations are identical.

4. The system of claim 1 wherein

two rows originate from one table, or two rows originate from different tables associated with the same nodegroup,

the data distribution method is data dependent, and

when the rows have identical DVs, co-location is provided by storing the two rows on the same node in the nodegroup.

5. The system of claim 1 wherein if tables are distributed according to an Elastic Data Distribution (EDD) method, co-location is guaranteed when nodes are added to the nodegroup even without first redistributing data among the nodes in the nodegroup.

6. The system of claim 1 wherein when a row is associated with a table that is distributed according to a data dependent distribution method, a data distribution manager determines in which node to store the row.

7. The system of claim 6 wherein if a table is distributed according to an elastic data distribution, the data distribution manager stores a new row of data in a manner that ensures co-location by

(a) computing a DV for the new row;

(b) determining whether this is a first occurrence of the DV associated with the nodegroup associated to the table, and

(c) if it is the first such occurence, the new row is stored on some node in the nodegroup, as determined by an Allocation Strategy (AS);

else

(d) if the DV has been seen before, the new row is stored on the same node that was used to store a row with the same DV before.

8. The system of claim 7 further comprising:

associating a Distribution Map (DM) with each nodegroup, such that the DM stores information tracking all DVs ever seen for any table in that nodegroup, and a location where the row associated with that DV was stored.

9. The system of claim 1 further comprising:

associating with each nodegroup one or more generations, such that when a nodegroup is initially created it has a first generation, and such that the generation consists of at least a generation number, a Distribution Map (DM), and an Allocation Strategy (AS).

10. The system of claim 9 wherein the AS determines where to send a row of data, and must be executable based on just the DV of the row, and any information in that generation.

11. The system of claim 9 wherein the latest generation of a nodegroup is a current generation of the nodegroup.

12. The system of claim 9 wherein the DM determines which DVs may not have been seen for the first time, when the associated generation was the current generation.

13. The system of claim 9 wherein when a change in the nodes belonging to a nodegroup, or a change in an Allocation Strategy, occurs, a new generation is created for the nodegroup.

14. The system of claim 9 wherein if a table is distributed according to an elastic data distribution, a new row of data is stored in a manner that ensures co-location by

(a) performing an iterative search through all generations to determine an earliest generation where it cannot be determined for sure that the DV was not seen;

(b) if such a generation can be found, the new row is dispatched according to the allocation strategy in that generation;

else

(c) if such a generation cannot be found, it is determined that the DV was never seen before, and the new row is dispatched according to the Allocation Strategy in the current generation, and the DM for the current generation is updated to reflect the occurrence of the DV for the new row.

15. The system of claim 9 wherein when a new row is encountered with a DV that has never been seen before, the new row is stored, and an indication is made in the DM of the current generation that the DV has now been seen for the first time, in the current generation.

16. The system of claim 14 wherein a DV has a unique indication in the DM, but multiple different DVs may generate the same identification in the DM.

17. The system of claim 16 wherein as a result, it cannot be determined for sure whether a particular DV was seen before, but it can be determined whether a DV was not seen before.

18. The system of claim 1 wherein the operational nodes are further for:

adding a new node to a storage nodegroup;

identifying random and round-robin distributed tables associated with the storage nodegroup, and creating empty tables for these tables on the new node;

identifying broadcast distributed tables associated with the storage-nodegroup and creating and populating these tables on the new node;

identifying tables using EDD in the storage-nodegroup and creating empty tables for these tables on the new node;

creating the next generation for the storage-nodegroup;

populating an empty DM for the next generation of the storage-nodegroup;

updating the node member list for the new generation for the storage-nodegroup to include the newly added node;

updating the AS for the new generation;

updating and flushing the DM for the current generation;

informing all nodes in the storage-nodegroup of the new generation of the storage nodegroup; and

updating the current generation of the storage nodegroup to be the newly created generation.

19. A database management system comprising:

a network interface, for receiving database queries from two or more client application processes as a network database service, the client application processes originating from two different users, the system providing a least one connection into the system for each such client application process;

a group of two or more operational nodes for executing the queries as database operations, each operational node implemented as a logical collection of software components that execute on one or more physical machines;

where the number of physical machines is not necessarily the same as the number of operational nodes;

with the operational nodes assigned as controller-nodes, compute-nodes or storage-nodes, and groups of controller-nodes forming controller nodegroups, and groups of compute-nodes forming compute nodegroups, and groups storage nodes forming storage nodegroups;

the number of operational nodes, and their available assignment as compute-nodes or storage-nodes varying during execution of the queries;

each client connection being assigned to an associated compute nodegroup;

the queries also specifying one or more tables for an associated database operation, with each such table being assigned to a respective storage nodegroup;

the operational nodes further;

operating in parallel;

with the number of operational nodes executing a given query or queries changing during a given time interval by at least one of;

(a) changing the compute-nodegroup associated with a connection, or

(b) adding or removing nodes from the compute nodegroup associated with a connection; and

wherein data from the tables is distributed among the nodes in a storage nodegroup according to a data dependent distribution method specified by a Distribution Vector (DV), the DV including a set of attributes of the table that determine at least where each row is stored; and

further wherein

each nodegroup is associated with one or more generations, such that when a nodegroup is initially created it has a first generation, and the generation consists of at least a generation number, a Distribution Map (DM), and an Allocation Strategy (AS), with the AS determining where to send a row of data, and executable based on the DV of the row, and any information in that generation, the Distribution Map (DM) being used to keep track of whether DVs have not been seen previously, and where when a change in the nodes belonging to a nodegroup, or a change in an AS occurs, a new generation is created for the nodegroup; and

if a table is to be distributed according to an elastic data distribution, a new row of data is stored in a manner that ensures co-location by

(a) performing an iterative search through all generations to determine an earliest generation where it cannot be determined for sure that the DV was not seen;

(b) if such a generation can be found, the new row is dispatched according to the allocation strategy in that generation;

else

(c) if such a generation cannot be found, it is determined that the DV was never seen before, and the new row is dispatched according to the AS in the current generation, and

(d) the DM for the current generation is updated to reflect the first occurrence of the DV for the new row in the current generation.