Intelligent data propagation in a highly distributed environment

• US 9,268,836 B2
• Filed: 11/14/2013
• Issued: 02/23/2016
• Est. Priority Date: 11/14/2013
• Status: Active Grant

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Magdon-Ismail, Tariq, Cheveresan, Razvan
• Primary Examiner(s): Thai, Hanh
• Application Number:
  US14/080,710
• Publication Number:
  US 20150134606A1
• Time in Patent Office: 831 Days
• Field of Search: 707/610, 707/634, 707651-652, 707/654, 707/679
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• 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: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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

Exemplary methods, apparatuses, and systems that can intelligently copy data to a plurality of datastores are described. In one embodiment, a distance value of a path between each datastore is determined. Based on the distance values, a graph cluster analysis creates clusters of the datastores within close proximity to one another. Also, a shortest path tree determines the most efficient paths available for copying data from a source datastore to one or more destination datastores. The source datastore is designated as the root of the shortest path tree, and the one or more destination datastores are designated as the vertices of the tree. After each child vertex of the source datastore is ordered in descending order according to a number of unique clusters to which descendants of the child vertex belong, the data is copied from the source datastore to the one or more destination datastores in the descending order.

Claims

1. A computer-implemented method comprising:

determining, by a processing device, a distance value of a path between each datastore in a plurality of datastores;

performing, by a processing device, a graph cluster analysis using the distance values to create a plurality of clusters, wherein each cluster includes one or more of the datastores within close proximity to one another based upon the distance values;

determining, by a processing device, a shortest path tree to copy data from a source datastore at a root of the shortest path tree to a remainder of the plurality of datastores, wherein each datastore is represented as a vertex in the shortest path tree;

ordering, by a processing device, each child vertex of the root in descending order according to a number of unique clusters to which descendants of the child vertex belong; and

copying, by a processing device, the data from the source datastore to one or more of the plurality of datastores in the descending order.

2. The computer-implemented method of claim 1, wherein the distance value of the path between each datastore is based upon a network performance measurement between the datastores.

3. The computer-implemented method of claim 1, further comprising:

determining a performance value for each datastore, wherein the datastore performance value is based on resource utilization or input/output (I/O) speed of the corresponding datastore; and

modifying the distance values using corresponding datastore performance values of one or more datastores in the corresponding path, wherein the graph cluster analysis uses the modified distance values.

4. The computer-implemented method of claim 1, wherein the ordering each child vertex in the shortest path tree in descending order is further based upon a number of children of each child vertex, resource utilization of each child vertex'"'"'s corresponding datastore, I/O latency of each child vertex'"'"'s corresponding datastore, or network latency of each child vertex'"'"'s corresponding datastore.

5. The computer-implemented method of claim 1, wherein copying the data comprises:

copying the data from the source datastore to a datastore represented by a child vertex of the source datastore;

promoting the child vertex to a new source datastore upon completion of the copying of the data to the child vertex;

ordering each child vertex of the new source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the new source datastore belong; and

copying the data from the new source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the new source datastore.

6. The computer-implemented method of claim 1, further comprising:

determining an updated shortest path tree in response to a threshold number of times the data is copied to the plurality of datastores, the updated shortest path tree including an updated source datastore, wherein the updated source datastore is the source datastore or another datastore storing a copy of the data;

ordering each child vertex of the updated source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the updated source datastore belong; and

copying the data from the updated source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the updated source datastore.

7. The computer-implemented method of claim 1, further comprising:

generating a snapshot of a virtual machine from the source datastore at the root of the shortest path tree; and

running a copy of the virtual machine on a host device using the snapshot while the copying is performed, wherein the data that is copied from the source datastore to one or more of the plurality of datastores in the descending order is the virtual machine.

8. A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform a method comprising:

determining, by the processing device, a distance value of a path between each datastore in a plurality of datastores;

performing, by the processing device, a graph cluster analysis using the distance values to create a plurality of clusters, wherein each cluster includes one or more of the datastores within close proximity to one another based upon the distance values;

determining, by the processing device, a shortest path tree to copy data from a source datastore at a root of the shortest path tree to a remainder of the plurality of datastores, wherein each datastore is represented as a vertex in the shortest path tree;

ordering, by the processing device, each child vertex of the root in descending order according to a number of unique clusters to which descendants of the child vertex belong; and

copying, by the processing device, the data from the source datastore to one or more of the plurality of datastores in the descending order.

9. The non-transitory computer-readable medium of claim 8, wherein the distance value of the path between each datastore is based upon a network performance measurement between the datastores.

10. The non-transitory computer-readable medium of claim 8, the method further comprising:

determining a performance value for each datastore, wherein the datastore performance value is based on resource utilization or input/output (I/O) speed of the corresponding datastore; and

modifying the distance values using corresponding datastore performance values of one or more datastores in the corresponding path, wherein the graph cluster analysis uses the modified distance values.

11. The non-transitory computer-readable medium of claim 8, wherein the ordering each child vertex in the shortest path tree in descending order is further based upon a number of children of each child vertex, resource utilization of each child vertex'"'"'s corresponding datastore, I/O latency of each child vertex'"'"'s corresponding datastore, or network latency of each child vertex'"'"'s corresponding datastore.

12. The non-transitory computer-readable medium of claim 8, wherein copying the data comprises:

copying the data from the source datastore to a datastore represented by a child vertex of the source datastore;

promoting the child vertex to a new source datastore upon completion of the copying of the data to the child vertex;

ordering each child vertex of the new source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the new source datastore belong; and

copying the data from the new source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the new source datastore.

13. The non-transitory computer-readable medium of claim 8, the method further comprising:

determining an updated shortest path tree in response to a threshold number of times the data is copied to the plurality of datastores, the updated shortest path tree including an updated source datastore, wherein the updated source datastore is the source datastore or another datastore storing a copy of the data;

ordering each child vertex of the updated source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the updated source datastore belong; and

copying the data from the updated source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the updated source datastore.

14. The non-transitory computer-readable medium of claim 8, the method further comprising:

generating a snapshot of a virtual machine from the source datastore at the root of the shortest path tree; and

running a copy of the virtual machine on a host device using the snapshot while the copying is performed, wherein the data that is copied from the source datastore to one or more of the plurality of datastores in the descending order is the virtual machine.

15. An apparatus comprising:

a processing device, wherein the processing device executes instructions that cause the apparatus to perform a method comprising;

determining a distance value of a path between each datastore in a plurality of datastores;

performing a graph cluster analysis using the distance values to create a plurality of clusters, wherein each cluster includes one or more of the datastores within close proximity to one another based upon the distance values;

determining a shortest path tree to copy data from a source datastore at a root of the shortest path tree to a remainder of the plurality of datastores, wherein each datastore is represented as a vertex in the shortest path tree;

ordering each child vertex of the root in descending order according to a number of unique clusters to which descendants of the child vertex belong; and

copying the data from the source datastore to one or more of the plurality of datastores in the descending order.

16. The apparatus of claim 15, wherein the distance value of the path between each datastore is based upon a network performance measurement between the datastores, the method further comprising:

determining a performance value for each datastore, wherein the datastore performance value is based on resource utilization or input/output (I/O) speed of the corresponding datastore; and

modifying the distance values using corresponding datastore performance values of one or more datastores in the corresponding path, wherein the graph cluster analysis uses the modified distance values.

17. The apparatus of claim 15, wherein the ordering each child vertex in the shortest path tree in descending order is further based upon a number of children of each child vertex, resource utilization of each child vertex'"'"'s corresponding datastore, I/O latency of each child vertex'"'"'s corresponding datastore, or network latency of each child vertex'"'"'s corresponding datastore.

18. The apparatus of claim 15, wherein copying the data comprises:

copying the data from the source datastore to a datastore represented by a child vertex of the source datastore;

promoting the child vertex to a new source datastore upon completion of the copying of the data to the child vertex;

ordering each child vertex of the new source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the new source datastore belong; and

copying the data from the new source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the new source datastore.

19. The apparatus of claim 15, the method further comprising:

determining an updated shortest path tree in response to a threshold number of times the data is copied to the plurality of datastores, the updated shortest path tree including an updated source datastore, wherein the updated source datastore is the source datastore or another datastore storing a copy of the data;

ordering each child vertex of the updated source datastore in descending order according to a number of unique clusters to which descendants of the child vertex of the updated source datastore belong; and

copying the data from the updated source datastore to one or more of the plurality of datastores in the descending order of the child vertices of the updated source datastore.

20. The apparatus of claim 15, the method further comprising:

generating a snapshot of a virtual machine from the source datastore at the root of the shortest path tree; and

running a copy of the virtual machine on a host device using the snapshot while the copying is performed, wherein the data that is copied from the source datastore to one or more of the plurality of datastores in the descending order is the virtual machine.