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

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application claims the benefit of United Kingdom Application No. 1607542.6, filed Apr. 29, 2016, in the United Kingdom Intellectual Property Office, and German Application No. 102016207472.5, filed Apr. 29, 2016, in the German Intellectual Property Office, the disclosures of which are incorporated herein by reference.

BACKGROUND

1. Field

0002The present invention relates to handling wide-area geographically distributed analytics. The invention finds multiple applications in today's world, where both data and processing are often distributed. A particular application is in the distribution of tasks to data centres. A data centre can be defined as a group of networked computing resources/computers (typically servers) which can be used by organisations for remote storage, processing or distribution of large amounts of data. Data centres normally present redundant resources and redundant data communication connections, etc.

0003Currently, the focus in the prior art is on how to distribute data processing task across different machines within one single data centre. The unique character in this situation is that: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0004">1. Network connection within one data centre is normally homogeneous. When considering locality of data and processing units, network heterogeneity normally does not feature in the optimisation method.</li><li id="ul0001-0002" num="0005">2. Influence of the uplink and downlink transfer of network are also less significant when all the process units and data are held in a single data centre with fast network connections.</li><li id="ul0001-0003" num="0006">3. Cost of network communication sometimes is considered less expensive compared to the cost of disk I/O. This is due to the fact that the speed of network within single data centres is normally much higher than the speed of reading from and writing to a conventional hard disk. Therefore, in-memory data across the network is preferred comparing to local on-disk data.</li></ul>

0007One key issue in the above approach is that with the rapid growth of data volume and data diversity, it becomes increasingly important to consider distribution of processing power across a wide-area of physical locations. This is based on the following observations: <ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0008">1. With the prevalence of data harvesting devices, e.g. sensors, data become increasingly distributed at the point of generation. Instead of collecting data to a central location and redistributing data according to predefined characteristics, it becomes natural to observe the data locality according to the point of generation. Fragments of the data and/or processing units are then redistributed to optimise the performance.</li><li id="ul0002-0002" num="0009">2. A real bottleneck of a centralised (or sometimes referred to as backhaul data collection and analysing) approach in the current worldwide computer network is the transoceanic fibre network crossing (e.g. transatlantic and transpacific cables). The cost and geographical difficulties dictate that such transoceanic fibre connections are likely to be the critical path in the conventional approach.</li><li id="ul0002-0003" num="0010">3. Data become naturally fragmented and distributed due to the diversity of specialised collection device, e.g. sensors. The outcome is that data within the regime of one harvesting method become increasingly homogeneous while data from different regimes become increasingly diverse. Processing data locally at the point of collection (and adapting to the regional data) may increase overall system performance.</li><li id="ul0002-0004" num="0011">4. The centralising-redistributing approach does not work in cases when moving data across the borders of sovereign countries. Due to safety, privacy and security reasons, many countries impose laws that prevent data (in any forms) from crossing borders. This makes optimisation based on a global, centralised view impossible.</li></ul>

0012Meanwhile the network connecting such locations can vary significantly. Such information should be taken into account when optimising data and process locality.

2. Description of the Related Art

0013Invention embodiments aim to take some or all of these observations into account and facilitate efficient data analysis which is suitable for use with geographically distributed data sources.

0014According to an embodiment of a first aspect of the invention, there is provided a computer-implemented method computer-implemented method of executing a query in a network of data centres, the method comprising a preparation stage and an execution stage; wherein

0015the preparation stage includes:

0016each 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;

0017and the execution stage includes:

0018the 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

0019both 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.

0020This combination of feature allows a dynamic hierarchical cluster structure (which may for example change in accordance with data centre parameters such as data size, operators supported or typical tasks processed). This hierarchical clustering allows grouping of similar and/or mutually proximate data centres, such as those in the same country processing the same type of data.

0021In this embodiment, both a child data centre and its parent data centre cache (temporarily store) executed tasks executed by the child and the sequence of outcomes from the child data centre, for instance until a query is completed. Thus the parent stores all the tasks and outcomes from each of the child data centres in the cluster. This caching allows a certain flexibility of operation, effectively using the stored information as a back-up.

0022In one embodiment, in the execution stage, if the child data centre 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 parent data centre. This is known as a “push-update”. For example, new incoming data may be of a greater volume and it may be possible to reproduce the effect of this on the outcomes cached using a transformation (if not, this process does not take place) and use the outcomes cached at the parent and transformation to avoid sending data unnecessarily.

0023In another embodiment referred to a pull-estimation (which may be combined with the push-update), in the execution stage, if communication between the parent data centre and the child data centre is interrupted, the parent data centre can use outcomes from another of the child data centres in the same cluster to carry on with the sequence of outcomes.

0024The child data centre clusters may be formed based on data centre parameters including any of: data size, expected tasks and data centre allowable operations. The child date centre may be formed based on data centre proximity factors including any of: physical proximity, network connection and regional location. In many embodiments, both data centre parameters (which are more likely to change over time) and proximity factors may be included.

0025The preparation stage can include providing, for the data centres, uplink bandwidth of the child data centre towards the parent data centre, and downlink bandwidth from the parent data centre towards the child data centre and size of the child data centre. These can be useful in assessing many factors, including data relocation considerations.

SUMMARY

0026Additional aspects and/or advantages will be set forth in part in the description which follows and, in part, will be apparent from the description, or may be learned by practice of the invention.

0027Invention embodiments may provide data (and therefore also task) relocation under defined conditions, the relocation including transferring data from an original child data centre to a destination child data centre and carrying out a task at the destination child data centre.

0028The defined conditions can take into account the amount of time required to transport the data which is transferred.

0029In one example, the defined conditions are defined based on uplink bandwidth of the child data centre towards the parent data centre, downlink bandwidth from the parent data centre towards the child data centre and size of the child data centre. These and potentially other factors may be used to calculate a ratio of data moved to a child data centre to data moved from that child data centre during data relocation.

0030The network may comprise one cluster, or a number of clusters, some perhaps including a single child date centre. The query may be entered into the network of data centres at a root data centre which is the overall parent of the hierarchy; the root data centre sending the tasks via (an) intermediate parent data centre(s) if the hierarchy has more than one level to child data centres which are leaf data centres forming the lowest level of the hierarchy.

0031The method may further comprise using, for each child data centre in the cluster, uplink bandwidth of the data centre towards the parent data centre, and size of the data centre to determine selection of a subset θ of data centres for executing the analysis task, wherein the size of the subset θ is preset to be greater than a threshold and the selection is to minimise the potential uplink communication.

0032According to an embodiment of a further aspect there is provided a parent data centre in a network of data centres for executing a query, wherein

0033the data centres are arranged in a dynamic hierarchical cluster topology of the 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 parent data centre being the only parent for the cluster;

0034the parent data centre comprising:

0035a processor and I/O configured to provide 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; and to receive from each child data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0036storage configured to cache executed tasks executed by the child and the sequence of outcomes of the tasks executed by the child data centre.

0037The processor and I/O may be configured to receive user queries and to form the hierarchical cluster topology. This configures the particular parent data centre as the rood data centre.

0038According to an embodiment of a still further aspect there is provided a child data centre in a network of data centres for executing a query, wherein

0039the data centres are arranged 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 parent data centre being the only parent for the cluster;

0040the child data centre comprising:

0041a processor and I/O configured to provide information relating to data centre parameters and/or proximity to other data centres, and further configured to receive the tasks from the parent data centres and to send the parent data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0042storage 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.

0043According to an embodiment of a yet further aspect there is provided a network of data centres for executing a query comprising a parent data centre as described above and a plurality of child data centres as described above. In this embodiment there may be provided network of data centres for executing a query, wherein

0044the data centres are arranged in a dynamic hierarchical cluster topology of the 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 parent data centre being the only parent for the cluster;

0045the parent data centre comprising:

0046a processor and I/O configured to provide 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; and to receive from each child data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0047storage configured to cache executed tasks executed by the child and the sequence of outcomes of the tasks executed by the child data centre; and

0048the child data centre comprising:

0049a processor and I/O configured to provide information relating to data centre parameters and/or proximity to other data centres, and further configured to receive the tasks from the parent data centres and to send the parent data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0050storage 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.

0051An apparatus or computer program according to preferred embodiments of the present invention can comprise any combination of the method aspects. Methods or computer programs according to further embodiments can be described as computer-implemented in that they require processing and memory capability.

0052The apparatus according to preferred embodiments is described as configured or arranged to, or simply “to” carry out certain functions. This configuration or arrangement could be by use of hardware or middleware or any other suitable system. In preferred embodiments, the configuration or arrangement is by software.

0053Thus according to one aspect there is provided a program which, when loaded onto at least one data centre configures the data centre to become the parent or child data centre according to any of the preceding data centre definitions or any combination thereof. Indeed the same software can be loaded onto a data centre and provide the configuration as the parent or child data centre dynamically in accordance with the dynamic cluster formation.

0054According to a further aspect there is provided a program which when loaded onto a network of data centres configures the data centres to carry out the method steps according to any of the preceding method definitions or any combination thereof.

0055The invention can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The invention can be implemented as a computer program or computer program product, i.e., a computer program tangibly embodied in a non-transitory information carrier, e.g., in a machine-readable storage device, or in a propagated signal, for execution by, or to control the operation of, one or more hardware modules.

0056A computer program can be in the form of a stand-alone program, a computer program portion or more than one computer program and can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a data processing environment. A computer program can be deployed to be executed on one module or on multiple modules at one site or distributed across multiple sites and interconnected by a communication network.

0057Method steps of the invention can be performed by one or more programmable processors executing a computer program to perform functions of the invention by operating on input data and generating output. Apparatus of the invention can be implemented as programmed hardware or as special purpose logic circuitry, including e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

0058Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions coupled to one or more memory devices for storing instructions and data.

0059The invention is described in terms of particular embodiments. Other embodiments are within the scope of the following claims. For example, the steps of the invention can be performed in a different order and still achieve desirable results. Multiple test script versions can be edited and invoked as a unit without using object-oriented programming technology; for example, the elements of a script object can be organized in a structured database or a file system, and the operations described as being performed by the script object can be performed by a test control program.

BRIEF DESCRIPTION OF THE DRAWINGS

Preferred features of the present invention will now be described, purely by way of example, with references to the accompanying drawings, in which:

<figref idref="DRAWINGS">FIG. 1</figref> is a flow chart of a method in a general embodiment;

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a parent or child data centre in a general embodiment of the invention;

<figref idref="DRAWINGS">FIG. 3</figref> is a more detailed diagram of a data centre for use in invention embodiments;

<figref idref="DRAWINGS">FIG. 4</figref> is an example of a hierarchy of data centres;

<figref idref="DRAWINGS">FIG. 5</figref> is an overview of the effect of a task on data;

<figref idref="DRAWINGS">FIG. 6</figref> is an example of pull-estimation;

<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart of preparation and execution according to an invention embodiment;

<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart of data centre characterisation; and

<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart of query distribution and execution.

DETAILED DESCRIPTION

0070Reference will now be made in detail to the embodiments, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below to explain the present invention by referring to the figures.

0071<figref idref="DRAWINGS">FIG. 1</figref> is a flowchart of a method of invention embodiments which may take place in a network of data centres and specifically in a cluster of that network.

0072In step S<b>10</b> each data centre provides information (for example about itself and about its connections to other data centres) to allow arrangement into a cluster with parent and children. This information may all be provided, for example, to a single data centre (perhaps a root data centre as discussed further hereinafter) in a data centre network. It may be stored centrally or in a distributed fashion.

0073In step S<b>20</b>, the parent in the hierarchy sends tasks to the children. These can be individual tasks which together make up the query (or the part of the query assigned to the parent if there are multiple parents at the same level in a larger hierarchy).

0074In step S<b>30</b>, each child sends outcomes to the parent in its cluster. In step S<b>40</b>, each child caches its own executed tasks and outcomes and the parent caches all the executed tasks and outcomes in the cluster.

0075<figref idref="DRAWINGS">FIG. 2</figref> is an overview diagram of components of data centre which may be a parent data centre or a child data centre. Each data centre may in fact function as a parent and as a child, but at different times or for different queries. Only the parts used in invention embodiments are depicted. Each data centre includes I/O (an input/output component) <b>100</b>, which is shown as a single unit, but may be split into sections, storage <b>110</b>, processor <b>120</b> (which is mentioned in the singular but is likely to include a number of processing units functioning together as a processor).

0076The data centres are arranged in a dynamic hierarchical cluster topology of the parent data centre and child data centres which is only represented here by a connection arrow and an additional data centre outline. Each child data centre stores its own local data sequence (for example from local data sources) which is to be processed by individual analysis tasks of a query. The child data centres together form a cluster of similar and/or proximate data centres, the parent data centre being the only parent for the cluster. An example network and cluster is shown in <figref idref="DRAWINGS">FIG. 4</figref>.

0077The parent data centre <b>10</b> comprises:

0078a processor <b>120</b> and I/O <b>100</b> configured to provide 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; and to receive from each child data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0079storage <b>110</b> configured to cache executed tasks executed by the child and the sequence of outcomes of the tasks executed by the child data centre.

0080The child data centre <b>10</b> comprises:

0081a processor <b>120</b> and I/O <b>100</b> configured to provide information relating to data centre parameters and/or proximity to other data centres, and further configured to receive the tasks from the parent data centres and to send the parent data centre a sequence of outcomes derived from the local data sequence and the tasks; and

0082storage <b>110</b> 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.

0083Hereinafter, a data centre is denoted as D_iwhich is assumed to have sufficient processor/CPU (central processing unit) power and storage space. This assumption is based on the fact that the price of CPUs (and processors in general) and storage devices is marginal comparing to the cost of constructing a major data centre. D_i's computational and storage capacities can be easily expanded. Also intra-D_inetwork connections (connections between the computers in a single data centre, and/or between the processors and memory in a single data centre) can be strictly regulated and carefully optimised. Latency of such communication can be ignored. Meanwhile, it is assumed that within each D_i, data and process locality issues are satisfactorily solved (using existing, off-the-shelf technologies from the distributed computing paradigm). This is also beyond the scope of this document. In the following, inter-D_iplanning and execution strategy is the focus.

SYMBOLS

0084In the following text, the following symbols are frequently used. <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0085">D_i: a data centre</li><li id="ul0003-0002" num="0086">s_i: the data size of a data centre. This is typically stated as gigabytes, although other widely accepted units can be used and will not affect the final computation.</li><li id="ul0003-0003" num="0087">r_i,j: the data size reduction ratio after jth (category of) operator is applied to the data. This is normally stated as a percentage, hence without units.</li><li id="ul0003-0004" num="0088">t_i,j: the time elapse of executing jth (category of) operator on a unit size of local data. Depending on the types of computation, typical units can be seconds, or milliseconds. This is elapsed real time.</li><li id="ul0003-0005" num="0089">T_i,j: the accumulative total time elapse of executing jth (category of) operator on all local data</li><li id="ul0003-0006" num="0090">W_i^ul: the uplink bandwidth of a data centre, with a typical unit of bits/second</li><li id="ul0003-0007" num="0091">W_i^dl: the downlink bandwidth of a data centre, again with a typical unit bits/second</li></ul>

0092Data Centre

0093Though it is not explicitly required, data centres in this document are assumed to follow a 3-tier design with potentially higher software layers. The typical 3-tier design consists of core layer, aggregation layer, and access layer. The core layer is considered the main ingress and egress layers of a data centre.

0094Servers in a data centre are arranged in multiple racks with a rack switch to distribute access requests. Rack switches are connected to rack cluster switches which are in turn connected to high performance computing facilities composing the core layer as the edge of the datacentre. Uplink of each tier can be collected either as the hardware specification or by using periodically network testing facilities. Downlink with respect to a data centre is measured by using network testing facilities. Such information can be relayed to the virtual parent data centres and stored at the layer <b>3</b> or layer <b>4</b> parent data centre (software) load balancers, should available resource be allowed at such locations. Ideally at layer <b>4</b> (software) load balancer, information about child data centres can extend the original information to allow the formation of virtual hierarchies with some data requests being redirected to child data centres if necessary.

0095Typically, a data centre can be represented with the virtual architecture shown in <figref idref="DRAWINGS">FIG. 3</figref>, which is a block diagram of a data centre <b>10</b> which embodies the present invention, and which may be used to implement a method of an embodiment of the invention.

0096A data centre can be viewed as a virtual machine <b>10</b>, with processing units <b>20</b> distributed across all the machines, transient and persistent data centre (DC) storage <b>30</b> provided by hard disks, network area storage, on chip or on board memories, etc. The virtual machine can differentiate Intra-DC I/O <b>40</b> and Inter-DC I/O <b>50</b> where the former should be considerably faster than the latter. The Inter-DC I/O should also differentiate uplink bandwidth <b>60</b> and downlink bandwidth <b>70</b> which in many cases are not equal. Intra-DC I/O <b>40</b> is not featured further in this document, but mentioned here for completeness.

0097An embodiment may be composed of a network of these data centres. Optionally, the data centre may also include one or more input mechanisms such as keyboard and mouse, and a display unit such as one or more monitors which are not shown. The components are connectable to one another via internal communication paths, also not shown.

0098The memory <b>30</b> may include a computer readable medium, which term may refer to a single medium or multiple media (e.g., a centralized or distributed database and/or associated caches and servers) configured to carry computer-executable instructions and/or have data structures stored thereon. Computer-executable instructions may include, for example, instructions and data accessible by and causing a general purpose computer, special purpose computer, or special purpose processing device (e.g., one or more processors) to perform one or more functions or operations. Thus, the term “computer-readable storage medium” may also include any medium that is capable of storing, encoding or carrying a set of instructions for execution by the machine and that cause the machine to perform any one or more of the methods of the present disclosure. The term “computer-readable storage medium” may accordingly be taken to include, but not be limited to, solid-state memories, optical media and magnetic media. By way of example, and not limitation, such computer-readable media may include non-transitory computer-readable storage media, including Random Access Memory (RAM), Read-Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Compact Disc Read-Only Memory (CD-ROM) or other optical disk storage, magnetic disk storage or other magnetic storage devices, flash memory devices (e.g., solid state memory devices).

0099The processor block <b>20</b> is configured to control the computing device and execute processing operations, for example executing code stored in the memory to implement the various different functions described here and in the claims. The memory <b>30</b> stores data being read and written by the processor <b>20</b>. As referred to herein, a processor may include one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. The processor may include a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, or a processor implementing other instruction sets or processors implementing a combination of instruction sets. The processor may also include one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. In one or more embodiments, a processor is configured to execute instructions for performing the operations and steps discussed herein.

0100A display unit may display a representation of data stored by the data centre and may also display a cursor and dialog boxes and screens enabling interaction between a user and the programs and data stored on the data centre. The input mechanisms may enable a user to input data and instructions to the computing device.

0101The interface <b>40</b> may be connected to a network, such as the Internet or a specialist network, and is connectable to other such data centres in the network. The interface <b>40</b> may control data input/output from/to other apparatus via the network. Other peripheral devices such as microphone, speakers, printer, power supply unit, fan, case, scanner, trackerball etc may be included in the computing device.

0102The data centre as used in invention embodiments may comprise processing instructions stored on a portion of the memory <b>110</b>, the processor <b>120</b> to execute the processing instructions, and a portion of the memory <b>110</b> to store data, tasks and outcomes during the execution of the processing instructions.

0103Methods embodying the present invention may be carried out on a data centre such as that illustrated in <figref idref="DRAWINGS">FIG. 3</figref> Such a computing device need not have every component illustrated in <figref idref="DRAWINGS">FIG. 3</figref>, and may be composed of a subset of those components.

0104A method embodying the present invention may be carried out by a plurality of data centres operating in cooperation with one another. Another method may take place in a single data centre.

0105Data Format

0106It is assumed that local data segments are often observed. Such segmentation can be based on format, syntax and semantics. Here, the segment is the natural separation of data when collected. For instance, clickstream (a series of mouse clicks made by a user, especially as monitored to assess a person's interests) collected from a region will be stored close to the point of generation and present a segmentation of data, which eventually will need to be combined with similar data from other regions to give the overall analysis. Also sensor data can be stored as they are collected (for example in the same format with the same syntax and semantics), on servers.

0107Meanwhile metadata are generated which faithfully reflect such local segmentations. For instance, for a meteorological sensor station, the metadata should contain both static and dynamic information. Static metadata include the data schema, data format (e.g. tabular format or unstructured text) and issuing organisation (and other key information for data provenance purposes), etc. The dynamic metadata include the rate of data generation, data size, data locality (local data location), etc. which tend to change over time due to data optimisation methods. Metadata also indicates that the sensor data are split based on dates and periods, for instance. This split can be a different dimension of segmentation that dices geographically segmented data potentially based on the time dimension for better operation.

0108Each data centre can also provide typical allowable operations (operators) that can be applied to the data held by the data centre. It is possible that a data centre holds a myriad of data. In this proposal, it is assumed that for each logically independent data block a list of categories of typical operators can be defined. A logically independent data block can be considered as data with a similarity of function or meaning, but different origins and/or further sliced with a second dimension, e.g. time. That is, logically independent blocks may be physically on the same machine but can be logically separated.

0109Operators can be aggregation or transfer ones. For data, typical transactions are data reduction transactions (such as aggregation) and size-preserving transactions (that covert data into a new form without changing the space complexity of data). Categories group similar operators together as an abstraction. The operator similarity can be based on the semantics of the operator: e.g. count type: such as counts, max, min, average, etc. and dimension-preserving type, such as rotation/distortion of image, matrix addition, etc. For each category j, the following characteristics can be estimated (or evaluated) for each data centre: r_i,jthe data size reduction ratio, t_i,j: the time elapse of executing jth (category of) operator, and the total time elapse T_i,j:

0110Here, t_i,jis the time spent on a unit data block. This unit data block and time can be defined by users for computational convenience. For instance, it can be unified across the entire system to count sensor data collected from one sensor during one hour (in kilobytes) as the basic unit or data from all the homogeneous sensors (data sources) during one day (in gigabytes) as the basic unit. How to define the basic unit data block can be decided by the users as long as they are unified across the entire setup. T_i,jis the accumulation of an operation j on all data of the same kind (homogeneous data blocks subject to the same transactions/operations.

0111Processing

0112In general, the proposed solution consists of two functional stages: <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0000"><ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0113">1. Preparation stage: essential network and task related characteristics are collected and estimated at this stage.</li><li id="ul0005-0002" num="0114">2. Execution stage: parameters derived from the preparation stage are used to dictate the execution of an arbitrary analysis task.</li></ul></li></ul>

0115<figref idref="DRAWINGS">FIG. 4</figref> is a logical abstraction of the framework basis for the preparation stage. In this illustration, data centres are divided into a hierarchy. The figure shows a root data centre D₀, with direct links to some data centres (these are D₁D₂, and D₃). D_ocan be seen as a parent data centre to these three data centres. In turn, these can be parent data centres for further data centres. For example, D₁has three child data centres, D₁₁, D₁₂, and D₁₃, which are sibling data centres forming a cluster. D₂has a single child data centre, D₂₁.

0116The idea is that the virtual hierarchy can have multiple layers (although it is normally not deep). All the nodes in the hierarchy should be able to process data locally (if they hold part of the data to answer the query). However, only the non-leaf node in the hierarchy needs to cache the intermediate results and implement (as the parent) the push/pull optimisations described in more detail hereinafter.

0117The data centres D_ishare the same logical architecture (represented by the blocks within the data centres which correspond to the structure of <figref idref="DRAWINGS">FIG. 3</figref>), although their physical implementation may be different. Among all the data centres, D₀refers to the one where the user queries arrive. This could be based on physical proximity of users and a data centre or based on explicit query submission defined by the user. Only one data centre will assume the role of receiving user queries. When a user submits a query through their UI (user interface) device, e.g. a personal computer or a laptop or a mobile or even directly at a data centre, the query is relayed to one data centre which is considered as D₀in this diagram. Answers to that query will be sent back to users via D₀. So D₀is the main entry point of user interaction.

0118D₀can change based on different queries. Often the queries are data intensive queries which are expected to run for a sustained period of time. The needs of repetitive execution and long execution duration justify the overhead of creating the virtual hierarchical structure.

0119All the data centres involved in this framework are arranged in a dynamic cluster structure, which groups together data centres in a way that is advantageous. This may allow certain tasks to be allocated to a cluster of data centres that are linked together by one or more similarities in terms of location, or by good connectivity or even by similar capacity/architecture. For example, cluster topology can be defined based at least partially on the following proximity factors (but also perhaps to take into account data centre parameters such as homogeneity of data stored in the data centres, and data centre operations): <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0000"><ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0120">1. Physical proximity: how far two data centres are from each other</li><li id="ul0007-0002" num="0121">2. Network connection among data centres and between any data centres and</li><li id="ul0007-0003" num="0122">3. geographic features: whether several data centres are located in the same sovereignty</li></ul></li></ul>

0123The skilled reader will know how to compute and construct the hierarchical structure and this is therefore not covered further in this document.

0124These cluster hierarchies are different data centres grouped into clusters and then arranged into several (maybe two or three—a large depth is not expected] layers of hierarchical structure. The advantage of this is two-fold: <ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0000"><ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0125">1. Homogeneous data centres can be grouped together in this logic topology. This grouping can be based on geographic proximity, data homogeneity, task homogeneity, etc. The ideal outcome is that children of a parent data centre D_pshall share similar data structures (in the context of handling a set of particular queries) and should respond largely similarly for a common set of tasks, even though they may hold different data and present different query responding characteristics. For instance, when analysing click stream of certain website (at a global scale), data centres holding such stream data can be grouped based on their geographic locations. An aggregation task can be executed locally whose results are aggregated through several layers in the hierarchical structure.</li><li id="ul0009-0002" num="0126">2. A parent data centre can manage its children. Due to similarity of data and geographic characteristics, data in the children centres are subject to the same safety and privacy regulations and thus data can be relocated for better system performance. Also, parent data centre has more visibility of the status of its children. It can estimate the availability and compensate when children are unavailable. <br /> Benefit: A logical structure is imposed on the data centre network. This can help to better manage the communication and data allocation. </li></ul></li></ul>

0127Preparation Stage

0128Invention embodiments can include the following steps in the preparation stage, in accordance with the requirements of the process: <ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0000"><ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0129">1. Each D_iestimates (or simply accesses if already known) metadata and parameters defined in the previous section. These include, for example, data size, s_i, r_i,j: the data size reduction ratio after jth (category of) operator is applied to the data so that data can be estimated at a future time point, and operations that can be applied to the data currently held and operations characteristics, t_i,j, T_i,j(time spent on a unit data block for one operator and time spent on all the data in the data centre for that operator).</li><li id="ul0011-0002" num="0130">2. The cluster hierarchy is defined (e.g. as described above and presented in <figref idref="DRAWINGS">FIG. 4</figref>). The hierarchy may be first created according to proximity and then be adjusted for data and/or query characterisation, for example to check what queries can be executed for a majority of data held locally in a cluster of data centres.</li><li id="ul0011-0003" num="0131">3. After this logical topology is defined, each data centre (D_iand D₀) can periodically “poke” the network to estimate and predict network performance, for example if no query arrives. This process assumes a given computation task which is assumed to consume data from all data centres D_i. <ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0132">a. An exemplary fragment of data is generated (or sampled where appropriate) to reflect the data typically held at D_i. Ideally this should be the same size, as n-fold of a unit block (where n is an integer). So one can gauge the entire network performance using this representative dataset for comparison.</li></ul></li><li id="ul0011-0004" num="0133">b. D_iperiodically sends such exemplary data to D₀together with its time stamp</li><li id="ul0011-0005" num="0134">c. D₀receives the data and estimates the uplink bandwidth of D_i(W_i^ul).</li><li id="ul0011-0006" num="0135">d. D₀periodically broadcasts a test (handshaking) data segment to all D_ifor estimating the downlink bandwidth of D_i(W_t^dl).</li><li id="ul0011-0007" num="0136">e. Where hierarchical structure presents, the uplink and downlink bandwidth should be estimated for each pair of parent-child data centres. <br /> The preparation stage is not necessarily continuous. Each D_iproduces data and forwards it along the hierarchy to its parent, the one in charge of task re-allocation/re-distribution. It can be performed whenever the entire framework has spare capacities (e.g. dynamically in an interval between two queries). </li><li id="ul0011-0008" num="0137">4. Data locality in-cluster adjustment is a process described below that may be performed between queries. It makes use of the uplink and downlink bandwidth estimation described above.</li></ul></li></ul>

0138Data locality in-cluster adjustment is among all the children of D_p, a strict data locality regulation is not applicable. For instance, all the children may actually be located in the same sovereignty region (so that transfer of data between the data centres does not cross any borders). It is therefore possible to transport and/or duplicate data across leaf children data centres of D_pfor performance tuning. Such optimisation is likely to be only carried out at the leaf level. This data is for processing, so it is possible to execute a task on one data centre using data originally stored at another data centre. Such functionality supplies the invention embodiments with data relocation for better process efficiency.

0139This kind of optimisation can be based on r_i,j, t_i,j, W_i^ul, W_i^dl, α_ifor the size of data to be downloaded (i.e. moved from another data centre] for processing locally (that is, at a certain data centre) and β_ifor the size of data to be processed remotely. Also define s_ias the size of local data (as before). The target is to:

0140<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><munder><mi>min</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></munder><mo>⁢</mo><mrow><munderover><mo>∑</mo><mi>i</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><munderover><mo>∑</mo><mi>j</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><mfrac><mrow><msub><mi>r</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>·</mo><mrow><mo>(</mo><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>-</mo><msub><mi>β</mi><mi>i</mi></msub><mo>+</mo><msub><mi>α</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><msubsup><mi>W</mi><mi>i</mi><mi>ul</mi></msubsup></mfrac><mo>+</mo><mfrac><msub><mi>α</mi><mi>i</mi></msub><msubsup><mi>W</mi><mi>i</mi><mi>dl</mi></msubsup></mfrac></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><munderover><mo>∑</mo><mi>j</mi><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo>⁢</mo><mrow><msub><mi>t</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>·</mo><mrow><mo>(</mo><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>-</mo><msub><mi>β</mi><mi>i</mi></msub><mo>+</mo><msub><mi>α</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></math></maths><br /> essentially, this equation operates as follows In the first part,

0141<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mfrac><msub><mi>α</mi><mi>i</mi></msub><msubsup><mi>W</mi><mi>i</mi><mi>dl</mi></msubsup></mfrac></math></maths><br /> gives how long extra data need to be downloaded to D_i, and

0142<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mfrac><mrow><msub><mi>r</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>·</mo><mrow><mo>(</mo><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>-</mo><msub><mi>β</mi><mi>i</mi></msub><mo>+</mo><msub><mi>α</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><msubsup><mi>W</mi><mi>i</mi><mi>ul</mi></msubsup></mfrac></math></maths><br /> gives that after downloading data from others and uploading data to others, and after some data operation (r_i,j), how long the results should be uploaded; together these two expressions tell how long it takes the data to be transported to and from D_i.

0143The second part is how long it takes to operate on the data. Together the two parts are to compute the time consumption of relocating the operation of some data to a different data centre. This will then be minimised across all the children to find the most optimised data transportation schedule, so that the whole network consumes the least amount of time for a query.

0144The minimisation target is the total time involved in processing the query at the immediate parent data centres of the leaf data centres. The total time is broken down as above to factor in the time for uploading and downloading data when cross data centre communication is necessary and the time for processing the queries locally at the data centre. The optimisation terminates when the best α_iand β_iratio can be found. Such an optimisation process can be time-consuming. At the start of the process, one can assume that all data should be handled at the local data centre without re-location.

0145The above target can be simplified as based on three assumptions: <ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0000"><ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0146">1. Data locality is against all the children data centres evenly, α_iand β_iare effectively equivalent.</li><li id="ul0014-0002" num="0147">2. Comparing to network communication time, local processing time can be largely ignored.</li><li id="ul0014-0003" num="0148">3. Operators are independent, i.e. operator j and k will not depend on one another.</li></ul></li></ul>

0149This produces the simplified equation below:

0150<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><munder><mi>min</mi><mi>α</mi></munder><mo>⁢</mo><mrow><mi>M</mi><mo>·</mo><mrow><mo>(</mo><mrow><mfrac><mrow><mrow><mover><mi>r</mi><mi>_</mi></mover><mo>·</mo><mrow><mo>(</mo><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>-</mo><mrow><mi>α</mi><mo>/</mo><mi>N</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mi>α</mi></mrow><msubsup><mi>W</mi><mi>i</mi><mi>ul</mi></msubsup></mfrac><mo>+</mo><mfrac><mi>α</mi><msubsup><mi>W</mi><mi>i</mi><mi>dl</mi></msubsup></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></math></maths><br /> where <o ostyle="single">r</o>, M and N are constants: <o ostyle="single">r</o> is the average data reduction ratio, N the number of children, M the number of operators to be applied on data held by a data centre. The above optimisation target can be easily solved to estimate the data to be reallocated or replicated in other data centres belonging to the same parent group.

0151Note that cross cluster data and/or process locality normalisation is not supported for non-child leaves in the case with the assumption that such locality transactions can risk data safety and sovereignty regulations, where only the (intermediate) processing outcomes can be transported.

0152The scope of this data locality tuning is illustrated in <figref idref="DRAWINGS">FIG. 4</figref>, in which a cluster of leaf data centres is circled. Moving upwards, intermediate results are aggregated at parent data centres. Note, that this is not a permanent physical hierarchical arrangement. Rather, the hierarchical structure changes based on the characteristics of data to be processed and/or the queries which are received.

0153Benefit: data locality tuning can improve task performance. Restricting the data locality tuning to be within each cluster (among sibling data centres) allows the observation of high level data security, privacy, and sovereignty rules. This offers a balance between performance and safety.

0154Execution Stage

0155At the execution stage, based on the logic/virtual hierarchical structure, the root data centre plays the role of receiving user queries, distributing queries down the hierarchy, aggregating the overall results, and delivering back to the users.

0156Data for processing are stored at leaf data centres (the lowest level of the hierarchy). The root data centre (D₀) is only responsible for task relocation. The root data centre is normally selected based on a balance between the proximity between end users and location where majority of data reside. Since the query and the intermediate data for final aggregation are normally small in size, a straightforward approach is to locate the root data centre in a region where the majority of data (for the query/application) are located.

0157Execution may comprise advantageous features such as: <ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0158">Subset selection</li><li id="ul0015-0002" num="0159">Push-update</li><li id="ul0015-0003" num="0160">Pull-estimation</li></ul>

0161Subset Selection

0162For the selection of further data centres for a given query (if required), the following strategy may be applied: where C is the set of all children of a parent data centre (the root data centre is taken as the overall parent here because it forms the root of the hierarchy) σ_iconstant coefficients that can be used to adjust the selection strategy, and γ a constant to avoid zero denominators,

0163<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><munder><mi>min</mi><mrow><mi>θ</mi><mo>∈</mo><mrow><mrow><msup><mn>2</mn><mi>C</mi></msup><mo>⋀</mo><mrow><mo></mo><mi>θ</mi><mo></mo></mrow></mrow><mo>></mo><mi>τ</mi></mrow></mrow></munder><mo>⁢</mo><mrow><mo>(</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>θ</mi></mrow><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></munderover><mo>⁢</mo><mrow><mo>(</mo><mrow><msub><mi>σ</mi><mi>i</mi></msub><mo>·</mo><mfrac><msub><mi>s</mi><mi>i</mi></msub><mrow><msubsup><mi>W</mi><mi>i</mi><mi>ul</mi></msubsup><mo>+</mo><mi>γ</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow></math></maths>

0164Basically, the selection finds a subset θ among all the child data centres that can minimise the potential uplink communication between the children and the parent. In order to simply the target function, one can set σ_i=1 a and γ to a sufficiently small number. Also, the size of θ should be greater than a threshold (either predefined by the users or set as a percentage of the entire population of children). This size of subset θ is greater than a threshold because it should be the same as or greater than a minimum value that enables the execution of a task. θ ∈ 2^Csimply requires θ to be a subset of C.

0165At this stage, the method tries to find the subset of data centres based on their listed characters. The above is the simplest implementation only considering data size and uplink.

0166In terms of tasks/query allocation among the subset, all the data centres present as children of a parent data centre are pre-registered with the parent as those that potentially holding data necessary to complete a task at the parent. The task allocation resembles a map-reduce task (which splits an input into independent chunks for processing (mapping) in a parallel way and then provides a summary) in the sense that tasks/processes can be sent to the child C based on the assumption that characteristics of data on child DC are already known and can be/should be used when processing a task.

0167This subset selection step is not always necessary. It is included here, for example, to cater for cases in which there are not enough resources to process the task at all the child data centres. A subset of the data centres can be selected based on a minimum requirement set by the users or a minimum number of data centres the user deem to be sufficient for an analysis task. For instance, if one wants to analyse click stream of a region, in cases when only limited time is available, one instructs the system to only analyse 80% of the entire data sets (presumably roughly evenly distributed across data centres—data distribution can be rebalanced when at the interim time between two queries as explained above). The above target function is a simple implementation of centre selection. If it is a hard constraint that all data should participate in the analysis, the above subset selection step is then not necessary.

0168Push-update In this process, viewed from a parent centre (D_p) perspective, the data are pushed to it without an explicit request, hence the name. In the above logic topology, after the execution of initial analytics tasks (and thus part of the way through the allocated task) both D_iand its parent data centre D_pwill cache the executed tasks/operators as well as the outcomes (o_ij^t) of executing such tasks, assuming the initial communication can be successfully established.

0169The analysis may be obtained on some parts of the local data on D_i. D_imonitors its own data. This data changes. This data (from which the outcomes are generated) can be viewed as one set of vertices in an m-n bipartite graph between data sets and analysis results, in the sense that there are no connections between data and no connections among analysis results. When data changes, the corresponding results will be flagged. D_iwill: <ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0000"><ul id="ul0017" list-style="none"><li id="ul0017-0001" num="0170">1. Test whether the changes affect outcomes of the analytics tasks. (Normally non-size-preserving or projection tasks will be affected by data changes, for instance, as explained in <figref idref="DRAWINGS">FIG. 5</figref>, which illustrates a bi-partite graph.) Some data changes do not affect the results. These will be operations in which the outputs share the same data semantics as inputs, for instance, a data format change or data projection.</li><li id="ul0017-0002" num="0171">2. If so, redo the analytics tasks to see whether the outcomes are changed (as o_ij^t+1)</li><li id="ul0017-0003" num="0172">3. If so, identify the changes from the previous outcomes (Δ=o_ij^t+1−o_ij^t)</li><li id="ul0017-0004" num="0173">4. Generate transformation plans p_j(Δ) that can reproduce Δ at D_pusing locally cached analytics outcomes at D_p.</li></ul></li></ul>

0174<figref idref="DRAWINGS">FIG. 5</figref> shows a mapping of data to outcomes and shows that, for size-preserving transactions, changes can be isolated and an extra projection can be created (as the dotted transformation). For non-size-preserving transactions, it may be necessary to redo the analysis. This can provide a clue for the decision in the above first bullet point.

0175Benefit: By doing so, network traffic can be greatly reduced. Even when D_iis not available for certain queries, local cached copies at D_pcan be used instead in further queries. The assumption is that the parent does not know what and how data have been changed, so this process takes place at the local data centre.

0176For instance, when the child realises data have changed (e.g. with increased data size, more items), it will first isolate the data that are changed and try to compute how the changed results can be derived from previous analysis results. For instance, the operation average(i_0, . . . i_100) can contribute to average(i_0, . . . , i_110)=(average(i_0, . . . , i_100)*100+average(i_101, . . . , i_110)*10)/110. The right hand side is a transformation plan that is independent from data and can be transported alone to be recreated at parent server. Such kinds of transformation plan can be either pre-defined or composed based on heuristic rules or by a human data engineer at the child data centre. The composition of transformation plan is not detailed further in this document.

0177Pull-estimation (again from the parent's perspective, this is actively requesting data from children): when D_pis performing updates (processing results) based on the pushed updates from its children, it performs the updates based on the first come first serve strategy. When updates from D_ihave been committed, D_pperforms data transformation allocated at its level (using visibility of tasks and data of its children) and relays the results to its parent (if there is one).

0178Due to potential network malfunction, communication between D_pand its children D_ican vary. An interruption can be caused when either the connection is broken or the data centre is down. A time-out threshold is pre-configured. If the communication between D_pand its children D_iis interrupted for a time lapse greater than the threshold, D_pterminates its communication and processes its' locally cached o_i,j^tusing incomplete transformation plan {circumflex over (p)}_j(Δ), which is a partial transformation plan or an estimated one by the parent. The time threshold value can be learned from historical communication patterns between D_iand D_por set proportional to the completion of updates from other children data centres.

0179It is clear that the actual p_i,j(Δ) (the actual transformation plan that D_iproposes to the parent to execute) cannot be obtained in this case. D_pderives an approximation {circumflex over (p)}_i,j(Δ) based on information received from other children regarding their updates. A major assumption here is that all the children of D_pshall share similar data structure and data update frequencies (at a given update episode) with respect to a query/application. The assumption is based on the data centres processing the same type of data. Thus the hierarchy is arranged so that children should have homogeneous data and perform largely similar data processes. When a majority of children have submitted their updates, D_pcan estimate essentially the updates from by finding the most similar {circumflex over (p)}_i,j(Δ) based on the partial knowledge of p_i,j(Δ) and operation instructions from other child data centres. This estimation can be done as follows: <br /><i>{circumflex over (p)}</i>_i,j(Δ)=Π_i,j(Δ)∥<i>p</i>_k≠i,j(Δ)<i>s.t</i>.max(<i>p</i>_k,j(Δ)≈Π_i,j(Δ))

0180where Π_i,j(Δ) is the partial update operation received from D_i, ∥ concatenates or merge two update operations together, and p_k≠i,j(Δ) s.t.max(p_k,j(Δ)≈Π_i,j(Δ)) select the most similar complete update operation matching the partial one received from D_i(s.t.max stands for “so that max( . . . )”).

0181In practice, for simplicity, one can assume that at a given update episode, all children perform largely similar update operations and complete updates received from other children can be applied to cached data to complete the partial ones.

0182<figref idref="DRAWINGS">FIG. 6</figref> illustrates the update idea. D_p1and D_p2complete their update while D_p3fails to do so. D_ponly receives partial update from D_p3, p₀³. . . p_a³. Assume D_p1is deemed to provide the most similar updates using the information received already in this case, {circumflex over (p)}(Δ) is computed by combining two updates together as {circumflex over (p)}(Δ)=p₀³. . . p_a³, p_a+1¹, . . . , p_m¹. This is essentially carrying on the incomplete sequence using values from another child data centre.

0183Of course any further analytics based on such assumption is not accurate. The purpose of continuing the sequence using results from another data centre is to trade absolute accuracy with data safety and process efficiency, as the completely accurate results may never be obtainable. The principle of “eventual consistency” is adopted here: D_pwill continue pulling updates from D_iwhile at this same time assuming updates based on {circumflex over (p)}_j(Δ) are correct. Computation logs are preserved until a response from D_iis received. D_pcan then decide whether to trace back (repeat) the computation made during the time window when D_iwas not available.

0184Benefit: by doing this, the entire system can run (in an effective eventual consistent way) when certain child data centres are not available. The hierarchical structure is essential in this case to ensure that all the sibling data centres can behave largely similarly to be able to act as a reference against each other.

0185Overall Benefit

0186Some benefits of invention embodiments can be seen as follows: <ul id="ul0018" list-style="none"><li id="ul0018-0001" num="0000"><ul id="ul0019" list-style="none"><li id="ul0019-0001" num="0187">1. A logical organisation of data centres to group similar or proximal centres together for better data locality and query handling</li><li id="ul0019-0002" num="0188">2. A local caching approach that facilitates “off-line” data processing, update-only communication, and reconstruction of updates when necessary</li><li id="ul0019-0003" num="0189">3. An in-cluster data locality scheme that improve the performance across data centres using data re-location and replication</li><li id="ul0019-0004" num="0190">4. A strategy to select which data centre should be used so as to avoid bottlenecks, in the form of selection of a subset of child data centres</li><li id="ul0019-0005" num="0191">5. A mechanism to gauge data centre performance that can help to constantly maintain a performance profile of all the data centres involved in query handling or a particular application. This relates primarily to downlink and uplink capacity.</li></ul></li></ul>

0192<figref idref="DRAWINGS">FIG. 7</figref> is a flow chart of an overall process according to one invention embodiment, including preparation and execution.

0193In general the whole process starts with initial task and/or query analysis, S<b>110</b>

0194This can be analysis based on expected tasks (based on application logic and potentially historical information about queries to be processed). This characterisation (along with proximity, which is however a constant can be used to guide logical data centre cluster generation in S<b>110</b>. That is, it imposes a virtual hierarchical structure over all data centres to be involved, also taking into account the characteristics of data centres.

0195In order to optimise, we require certain knowledge of what can be performed on the data (or what kind of analysis can be done on the data and/or what are the likely outcomes). This is considered the set of “admissible operations”. For instance, typically for temperature sensors, we can expect operations such as sum, periodical average, min, max, etc.

0196The intention in query characterisation (S<b>120</b>) is to establish what queries can be executed for a majority of data held locally in a group of data centres. This is to help the re-organisation of how the virtual multiple data centre hierarchy should be established.

0197Once the logical structure is defined, the system estimates whether in-cluster data locality tuning is necessary and possible according to whether a query has arrived in S<b>130</b>: if queries have not arrived, data locality tuning can be conducted (S<b>140</b>); otherwise the system proceeds to query processing (S<b>150</b>).

0198<figref idref="DRAWINGS">FIG. 8</figref> outlines continuous characterisation of data centres, by for instance parents or root data centres. Results of such characterisation are stored in a persistent storage.

0199Here, data locality tuning, S<b>140</b>, (as described in the cluster locality section) is based on both data centre and data features in the context of a particular application/processing task. The data features are: s_i, t, T, r. The data centre features can relate to uplink and downlink parameters. The system first queries a persistent storage in step S<b>170</b> to see if these data centre features are already available (and potentially to check if available data centre features are out of date). The persistent storage is a shared (distributed data store, e.g. distributed hash table) or centralised data store. If not available, a handshaking message will be sent S<b>180</b> to probe the connection with child data centre for uplink and downlink performance. Further information will follow to understand typical operators, their data reduction rate and their performance. These are the parameters mentioned in previous sections: r, t, and T.

0200<figref idref="DRAWINGS">FIG. 9</figref> shows query execution.

0201A query is executed as follows:

0202S<b>200</b>. The query is distributed potentially taking into account the uplink and downlink of each child data centre to select a subset of the leaf data centres. This subset selection is when not all children are used. It is not relevant when all children have to participate.

0203S<b>210</b>: there is a query if complete results have been received

0204S<b>220</b>. If complete results are received from child data centres, they are cached both at the child and the parent data centres. The system proceeds to the next query.

0205S<b>230</b>. In the case that the complete results (outcomes) are not received: <ul id="ul0020" list-style="none"><li id="ul0020-0001" num="0000"><ul id="ul0021" list-style="none"><li id="ul0021-0001" num="0206">S<b>240</b>. If there are cached outcomes and a cached task from the previous execution, the process approximates the results using either the push-update explained earlier or the pull-estimation or both.</li><li id="ul0021-0002" num="0207">S<b>250</b>. If there are not cached outcomes and a cached task, track back any intermediate results based on this child. That is, if there is no way of approximating results from D_ieven based on those from other children, D_iis deemed permanently dead and should be removed from future processing.</li></ul></li></ul>

0208S<b>260</b>. For either case, continue pulling till <ul id="ul0022" list-style="none"><li id="ul0022-0001" num="0000"><ul id="ul0023" list-style="none"><li id="ul0023-0001" num="0209">i. Either a threshold is reached and the child can be presumed permanently not available</li><li id="ul0023-0002" num="0210">ii. Or results arrive and processing continues.</li></ul></li></ul>

0211The query processing ends when there are no more queries.

0212According to invention embodiments, a method, a network including clusters, parent and child data centres and a computer program facilitate efficient data analysis across geographically distributed data sources. A comprehensive measure can be used to gather and estimate/predict the performance of analytics to be carried out on a dataset. That is, performance of admissible operations/analysis tasks is estimated based on the characteristics of data communication network between data centres and processing performance.

0213Invention embodiments can: <ul id="ul0024" list-style="none"><li id="ul0024-0001" num="0000"><ul id="ul0025" list-style="none"><li id="ul0025-0001" num="0214">1. Store data at the edge (where the data are generated). Here, the term ‘edge’ means the entry point where the data is entering the system/network, so data need not be transported for storage, instead, they should be stored at their origins</li><li id="ul0025-0002" num="0215">2. Estimate the cost of executing an analytics task at a different data centre from where the data is produced and across different geographic regions (where different clusters are located). This is a reason the locality is only adjusted within one “parent-children” sub-tree which are organised within one jurisdiction or geographic region.</li><li id="ul0025-0003" num="0216">3. Plan a best strategy for executing the analytics task. This refers to the optimisation based on uplink and downlink to adjust data and decide where the aggregation (task) should be carried out.</li><li id="ul0025-0004" num="0217">4. Transport and/or update the results to facilitate the most efficient task execution, as explained i the push-update and pull-estimation sections.</li></ul></li></ul>

0218Key features of invention embodiments can include: <ul id="ul0026" list-style="none"><li id="ul0026-0001" num="0000"><ul id="ul0027" list-style="none"><li id="ul0027-0001" num="0219">1. Dynamism of the processes in invention embodiments: the estimation of system performance is continuously updated to reflect the most up-to-date changes. This feature refers to the continuous monitoring and estimating of uplink and downlink of all involved datacentres and/or continuous estimation of data operations (as part of processes satisfying a query) effect on data.</li><li id="ul0027-0002" num="0220">2. Incremental: the data analysis is performed incrementally to minimise the resource requirement</li></ul></li></ul>

0221Data safety: the proposed solution can observe regulatory and safety constraints.

0222Although a few embodiments have been shown and described, it would be appreciated by those skilled in the art that changes may be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the claims and their equivalents.