Computer-implemented method of executing a query in a network of data centres

Patent metadata

Field	Value
Publication number	US-10691692-B2
Application number	US-201715444816-A
Country	US
Kind code	B2
Filing date	Feb 28, 2017
Priority date	Apr 29, 2016
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

A computer-implemented method of executing a query in a network of data centres, the method comprising a preparation stage and an execution stage; wherein the preparation stage includes: each data centre providing information relating to data centre parameters and/or proximity, allowing arrangement of the data centres in a dynamic hierarchical cluster topology of a parent data centre and child data centres, each child data centre having its own local data sequence which is to be processed by individual analysis tasks of the query, the child data centres together forming a cluster of similar and/or proximate data centres, the cluster having a single parent data centre; and the execution stage includes: the parent data centre sending the tasks to the child data centres and the child data centres sending to the parent data centre a sequence of outcomes derived from the local data sequence and the tasks; wherein both a child data centre and its parent data centre cache executed tasks executed by the child and the sequence of outcomes of the tasks executed by the child data centre.

First claim

What is claimed is:

1. A computer-implemented method of executing a query in a network of data centres, the method comprising a preparation stage and an execution stage; wherein
the preparation stage includes:
arranging the data centres in a dynamic hierarchical cluster topology of a parent data centre and child data centres, based on information relating to data centre parameters and/or proximity provided by each data centre, each child data centre having its own local data sequence which is to be processed by individual analysis tasks of the query, the child data centres together forming a cluster of similar and/or proximate data centres, the cluster having a single parent data centre; and

the execution stage includes:
the single parent data centre sending the tasks to the child data centres in the cluster and the child data centres in the cluster sending to the single parent data centre a sequence of outcomes derived from the local data sequence and the tasks;

wherein the child data centres in the cluster and the single parent data centre cache executed tasks executed by the child data centres in the cluster and the sequence of outcomes of the tasks executed by the child data centres in the cluster until the query is completed.

2. The method according to claim 1 , wherein
in the execution stage, if a child data centre among the child data centres in the cluster identifies any change in outcomes associated with new incoming data, the child data centre provides a transformation to reproduce the change from the outcomes cached and sends the transformation to the single parent data centre.

3. The method according to claim 1 , wherein
in the execution stage, if communication between the single parent data centre and a child data centre among the child data centres in the cluster is interrupted, the single parent data centre uses outcomes from another of the child data centres in the cluster to carry on with the sequence of outcomes.

4. The method according to claim 1 , wherein the child data centres in the cluster are formed based on data centre parameters including any of: data size, expected tasks and data centre allowable operations and on data centre proximity factors including any of: physical proximity, network connection and regional location.

5. The method according to claim 1 , wherein the preparation stage includes:
providing, for the data centres D i , uplink bandwidth of a child data centre W i ul among the child data centres in the cluster towards the single parent data centre, and downlink bandwidth W i dl from the single parent data centre towards the child data centre and size of the child data centre s i .

6. The method according to claim 1 , further comprising:
relocating data and a task under defined conditions, the relocating including transferring data among the child data centres in the cluster from an original child data centre to a destination child data centre and carrying out the task at the destination child data centre.

7. The method according to claim 6 , wherein the defined conditions take into account an amount of time required to transport the data which is transferred.

8. The method according to claim 6 , wherein
the defined conditions are defined based on uplink bandwidth of the child data centre W i ul towards the single parent data centre, downlink bandwidth W i dl from the single parent data centre towards the child data centre and size of the child data centre s i and calculate a ratio of data to be moved to the original child data centre to data moved from the original child data centre during data relocation.

9. The method according to claim 1 , wherein:
the query is entered into the network of data centres at a root data centre which is an overall parent in a hierarchy of the data centres;
the root data centre sending the tasks via any intermediate parent data centre to child data centres which are leaf data centres forming a lowest level of the hierarchy.

10. The method according to claim 1 , further comprising:
using, for each child data centre in the cluster, uplink bandwidth of the data centre W i ul towards the single parent data centre, and size of the data centre s i to determine selection of a subset θ of the child data centres for executing the task, wherein the size of the subset θ is preset to be greater than a threshold and the selection is to 4 minimize the potential uplink communication.

11. A parent data centre in a network of data centres for executing a query, wherein
the data centres are arranged in a dynamic hierarchical cluster topology of the parent data centre and child data centres, based on information relating to data centre parameters and/or proximity provided by each data centre, each child data centre having its own local data sequence which is to be processed by individual analysis tasks of the query; the child data centres together forming a cluster of similar and/or proximate data centres, the parent data centre being the only parent for the cluster;
the parent data centre comprising:
a processor and an input-output component, I/O, configured to provide the information relating to data centre parameters and/or proximity to other data centres; and further configured to receive the tasks, to send the tasks to the child data centres in the cluster; and to receive from each child data centre in the cluster a sequence of outcomes derived from the local data sequence and the tasks; and
a storage configured to cache executed tasks executed by each child centre in the cluster and the sequence of outcomes of the tasks executed by each child data centre in the cluster until the query is completed.

12. The parent data centre according to claim 11 , wherein the processor and I/O are configured to receive user queries and to form the hierarchical cluster topology.

13. A child data centre among child date centres in a network of data centres for executing a query, wherein
the data centres are arranged in a dynamic hierarchical cluster topology of a parent data centre and the child data centres, based on information relating to data centre parameters and/or proximity provided by each data centre, the child data centre having its own local data sequence which is to be processed by individual analysis tasks of the query, the child data centres together forming a cluster of similar and/or proximate data centres, the parent data centre being the only parent for the cluster;
the child data centre comprising:
a processor and an input-output component, I/O configured to provide the information relating to data centre parameters and/or proximity to other data centres, and further configured to receive the tasks from the parent data centre and to send the parent data centre a sequence of outcomes derived from the local data sequence and the tasks; and
a storage configured to cache tasks that the child data centre has executed and the sequence of outcomes of the tasks that the child data centre has executed until the query is completed.

14. A network of data centres for executing a query comprising a parent data centre according to claim 11 and a plurality of child data centres according to claim 13 .

Assignees

• Fujitsu Ltd

Inventors

• Hu Bo

Classifications

• G06F9/5027 Primary

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F16/285

  Clustering or classification · CPC title

• H04L41/044

  comprising hierarchical management structures · CPC title

• H04L67/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] · CPC title