M X N dispatching in large scale distributed system

• US 9,753,980 B1
• Filed: 03/15/2013
• Issued: 09/05/2017
• Est. Priority Date: 02/25/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Chang, Lei, Ma, Tao, Wang, Zhanwei, Lonergan, Luke, Jian, Lirong, Ma, Lili
• Primary Examiner(s): Khong, Alexander
• Application Number:
  US13/840,948
• Time in Patent Office: 1,635 Days
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• 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/43 Querying
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: H04L 65/60 Network streaming of media packets
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

M×N dispatching in a large scale distributed system is disclosed. In various embodiments, a query is received. A query plan is generated to perform the query. A subset of query processing segments is selected, from a set of available query processing segments, to perform an assigned portion of the query plan. An assignment to perform the assigned portion of the query plan is dispatched to the selected subset of query processing segments.

Claims

1. A method, comprising:

receiving a query;

generating, by a master node, a query plan to perform the query, wherein the generating of the query plan includes dividing the query plan into at least a first portion and a second portion, and wherein the master node comprises one or more hardware processors;

selecting, by the master node, from a set of available query processing segments a first subset of query processing segments to perform a first assigned portion of the query plan corresponding to the first portion of the query plan, and a second subset of query processing segments to perform a second assigned portion of the query plan corresponding to the second portion of the query plan, wherein at least one segment of the set of available query processing segments is included in the first subset and the second subset of query processing segments, wherein a first number of segments selected to perform the first portion of the query plan is dynamically determined according to one or both of (1) data locality of data corresponding to the first portion of the query plan associated with the query in relation to the first subset of query processing segments, and (2) available resources, wherein the first subset of query processing segments is selected based at least in part on a co-locality of one or more of the selected query processing segments with data with which the assigned portion of the query plan is associated, and wherein the first number of segments is selected to perform the first portion of the query plan and a second number of segments, different from the first number, is selected to perform the second portion of the query plan; and

dispatching to the selected first subset of query processing segments an assignment to perform the first assigned portion of the query plan, wherein the dispatching of the assignment to perform the first assigned portion of the query plan includes providing to the selected first subset of query processing segments with corresponding metadata that is obtained from a central metadata store, wherein the metadata provided to the corresponding selected first subset of query processing segments is determined to be used to perform the first assigned portion of the query plan.

2. The method of claim 1, wherein the dividing the query plan into at least a first portion and a second portion includes dividing the query plan into a plurality of independently executable slices.

3. The method of claim 1, wherein selecting the first subset of query processing segments includes receiving from a resource manager an indication of a degree of availability of processing segments included in the set of available query processing segments.

4. The method of claim 1, wherein the first subset of query processing segments is selected according to a determination for each of a plurality of portions of the query plan a corresponding number of segments to be assigned to perform that portion.

5. The method of claim 1, wherein the assignment comprises a network communication sent via a network interconnect.

6. The method of claim 1, wherein the assignment includes embedded metadata to be used to perform one or more tasks associated with the assigned portion of the query plan.

7. The method of claim 1, wherein segments comprising the subset of query processing segments are associated with one or more segments hosts, each of which is configured to provide one or more processing segments.

8. The method of claim 1, wherein the assignment includes the metadata, wherein the metadata indicates a location, within a distributed storage layer, of data associated with the assignment.

9. The method of claim 8, wherein the location includes identification of a table of data to be search in connection with the assignment.

17. The method of claim 1, wherein the first subset of query processing segments and the second subset of query processing segments include at least a first segment.

10. A system, comprising:

a communication interface; and

one or more hardware processors coupled to the communication interface and configured to;

receive a query;

generate a query plan to perform the query, wherein the query plan is generated such that the query plan is divided into at least a first portion and a second portion;

select from a set of available query processing segments a first subset of query processing segments to perform a first assigned portion of the query plan, corresponding to the first portion of the query plan, and a second subset of query processing segments to perform a second assigned portion of the query plan corresponding to the second portion of the query plan, wherein at least one segment of the set of available query processing segments is included in the first subset and the second subset of query processing segments, wherein a first number of segments selected to perform the first portion of the query plan is dynamically determined according to one or both of (1) data locality of data corresponding to the first portion of the query plan associated with the query in relation to the first subset of query processing segments, and (2) available resources, wherein the first subset of query processing segments is selected based at least in part on a co-locality of one or more of the selected query processing segments with data with which the assigned portion of the query plan is associated, and wherein the first number of segments is selected to perform the first portion of the query plan and a second number of segments, different from the first number, is selected to perform the second portion of the query plan; and

dispatch to the selected first subset of query processing segments, via the communication interface, an assignment to perform the first assigned portion of the query plan, wherein to dispatch the assignment to perform the first assigned portion of the query plan includes providing to the selected first subset of query processing segments with corresponding metadata that is obtained from a central metadata store, wherein the metadata provided to the corresponding selected first subset of query processing segments is determined to be used to perform the first assigned portion of the query plan.

11. The system of claim 10, wherein the dividing the query plan into at least a first portion and a second portion includes dividing the query plan into a plurality of independently executable slices.

12. The system of claim 10, wherein selecting the first subset of query processing segments includes receiving from a resource manager an indication of a degree of availability of processing segments included in the set of available query processing segments.

13. The system of claim 10, wherein the first subset of query processing segments is selected according to a determination for each of a plurality of portions of the query plan a corresponding number of segments to be assigned to perform that portion.

14. The system of claim 10, wherein the assignment includes the metadata, wherein the metadata is to be used to perform one or more tasks associated with the assigned portion of the query plan.

15. A computer program product embodied in a tangible, non-transitory computer readable storage means, comprising computer instructions for:

receiving a query;

generating a query plan to perform the query, wherein the generating of the query plan includes dividing the query plan into at least a first portion and a second portion;

selecting from a set of available query processing segments a first subset of query processing segments to perform a first assigned portion of the query plan corresponding to the first portion of the query plan, and a second subset of query processing segments to perform a second assigned portion of the query plan corresponding to the second portion of the query plan, wherein at least one segment of the set of available query processing segments is included in the first subset and the second subset of query processing segments, wherein a first number of segments selected to perform the first portion of the query plan is dynamically determined according to one or both of (1) data locality of data corresponding to the first portion of the query plan associated with the query in relation to the first subset of query processing segments, and (2) available resources, wherein the first subset of query processing segments is selected based at least in part on a co-locality of one or more of the selected query processing segments with data with which the assigned portion of the query plan is associated, and wherein the first number of segments is selected to perform the first portion of the query plan and a second number of segments, different from the first number, is selected to perform the second portion of the query plan; and

dispatching to the selected first subset of query processing segments an assignment to perform the first assigned portion of the query plan, wherein the dispatching of the assignment to perform the first assigned portion of the query plan includes providing to the selected first subset of query processing segments with corresponding metadata that is obtained from a central metadata store, wherein the metadata provided to the corresponding selected first subset of query processing segments is determined to be used to perform the first assigned portion of the query plan.

16. The computer program product of claim 15, wherein the first subset of query processing segments is selected according to a determination for each of a plurality of portions of the query plan a corresponding number of segments to be assigned to perform that portion.