Systems and methods for replicating data

• US 8,504,518 B1
• Filed: 10/14/2011
• Issued: 08/06/2013
• Est. Priority Date: 02/14/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Gobioff, Howard, Leung, Shun-Tak
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/274,043
• Time in Patent Office: 662 Days
• Field of Search: 707/610, 707/623, 707/634
• US Class Current: 707/610
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A system that facilitates the distribution and redistribution of chunks of data among multiple servers, may identify servers to store replicas of the chunks based on at least one of utilization, prior data distribution, and failure correlation properties, and place the replicas at the identified servers. The system may monitor total numbers of replicas available in the system, identify chunks that have a total number of replicas below one or more thresholds, assign priorities to the identified chunks, and re-replicate the identified chunks based on the assigned priorities. The system may monitor utilization of the servers, select one or more of the replicas to redistribute based on the utilization of the servers, select one or more of the servers to which to move the one or more replicas, and move the one or more replicas to the selected one or more servers.

Claims

1. A method for distributing chunks of data in a system that includes a plurality of servers that store replicas of the chunks, the method comprising:

determining, by a device, a total number of replicas, of each chunk, stored in the system;

identifying, by the device, chunks that are associated with a total number of replicas, of the determined total number of replicas, below a threshold;

assigning, by the device, priorities to the identified chunks; and

replicating, by the device, the identified chunks in an order that is based substantially on the assigned priorities.

2. The method of claim 1, where assigning the priorities includes:

determining whether one of the identified chunks is associated with an active file;

assigning the one of the identified chunks a first priority when the one of the identified chunks is associated with the active file; and

assigning the one of the identified chunks a second priority when the one of the identified chunks is not associated with the active file,

where the second priority comprises a lower priority relative to the first priority, and

where a chunk assigned the first priority is replicated before a chunk assigned the second priority.

3. The method of claim 1, where assigning the priorities includes:

assigning the priority based on a number of replicas each of the total numbers of replicas, of the identified chunks, is below the threshold.

4. The method of claim 1, where assigning the priorities includes:

determining whether one of the identified chunks is associated with a deleted file;

assigning the one of the identified chunks a first priority when the one of the identified chunks is associated with the deleted file; and

assigning the one of the identified chunks a second priority when the one of the identified chunks is not associated with the deleted file,

where the second priority comprises a higher priority relative to the first priority, and

where a chunk that is assigned the second priority is replicated prior to a chunk that is assigned the first priority is replicated.

5. The method of claim 1, where the threshold comprises a plurality of thresholds, and

where the method further comprises:

determining that one of the identified chunks comprises a first type of chunk; and

determining that another one of the identified chunks comprises a second type of chunk that is different from the first type of chunk; and

where identifying the chunks that are associated with the total number of replicas below the threshold includes;

identifying that the one of the identified chunks comprises is associated with the total number of replicas below one of the plurality of thresholds based on the one of the identified chunks comprising the first type of chunk, and

identifying that the other one of the identified chunks is associated with the total number of replicas below another one of the plurality of thresholds based on the other one of the identified chunks comprising the second type of chunk.

6. The method of claim 1, where replicating the identified chunks includes:

determining a utilization of a memory for each of the plurality of servers;

selecting one or more of the plurality of servers based on the determined utilizations; and

instructing each of the selected one or more of the plurality of servers to create a replica of one of the identified chunks.

7. The method of claim 1, where replicating the identified chunks includes:

replicating a first one of the identified chunks prior to replicating a second one of the identified chunks, where the first one of the identified chunks is assigned a higher priority relative to the second one of the identified chunks.

8. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions which, when executed by one or more processors, cause the one or more processors to monitor a plurality of devices storing replicas of portions of data files;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to identify, based on the monitoring, one or more of the portions of the data files that comprise a total number of replicas below a threshold number of replicas;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to assign priorities to the identified one or more of the portions of the data files; and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to replicate the identified one or more of the portions of the data files in an order based on the assigned priorities.

9. The non-transitory computer-readable medium of claim 8, where the one or more instructions to assign the priorities include:

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine whether one of the one or more portions of the data files is associated with an active data file;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to assign the one of the one or more portions of the data files a first priority when the one of the one or more portions of the data files is associated with the active data file; and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to assign the one of the one or more portions of the data files a second priority when the one of the one or more of the portions of the data files is not associated with the active data file,

where a portion of a data file that is assigned the first priority is replicated before a portion of a data file that is assigned the second priority.

10. The non-transitory computer-readable medium of claim 8, where the priorities are assigned based on a number of replicas each of the total numbers of replicas is below the threshold number of replicas.

11. The non-transitory computer-readable medium of claim 8, where the one or more instructions to assign the priorities include:

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine whether one of the identified one or more portions of the data files is associated with a deleted data file;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to assign the one of the identified one or more portions of the data files a first priority when the one of the identified one or more portions of the data files is associated with the deleted data file; and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to assign the one of the identified one or more portions of the data files a second priority when the one of the identified one or more portions of the data files is not associated with the deleted data file,

where a portion of a data file that is assigned the second priority is replicated before a portion of a data file that is assigned the first priority.

12. The non-transitory computer-readable medium of claim 8, where the threshold number of replicas comprises:

a first threshold number of replicas associated with a first type of data, and

a second threshold number of replicas associated with a second type of data;

where the instructions further comprise;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine that one of the identified one or more portions of the data files comprises the first type of data;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine that another one of the identified one or more portions of the data files comprises the second type of data; and

where the one or more instructions to identify the portions of data files that comprise the total number of replicas below the threshold number of replicas include;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to identify that the one of the identified one or more portions of the data files comprises the total number of replicas below the first threshold number of replicas, based on the one of the identified one or more portions of the data files comprising the first type data, and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to identify that the other one of the identified one or more portions of the data files comprises the total number of replicas below the second threshold number of replicas, based on the other one of the identified one or more portions of the data files comprising the second type of data,

the second threshold number of replicas being different from the first threshold number of replicas.

13. The non-transitory computer-readable medium of claim 8, where the one or more instructions to replicate the identified one or more portions of the data files include:

one or more instructions which, when executed by the one or more processors, cause the one or more processors to determine a utilization of a memory for each of the plurality of devices;

one or more instructions which, when executed by the one or more processors, cause the one or more processors to select one or more of the plurality of devices based on the determined utilizations; and

one or more instructions which, when executed by the one or more processors, cause the one or more processors to cause each of the selected one or more of the plurality of devices to create a replica of one of the identified one or more portions of the data files.

14. The non-transitory computer-readable medium of claim 8, where the one or more instructions to replicate the identified one or more portions of the data files include:

one or more instructions which, when executed by the one or more processors, cause the one or more processors to replicate a first one of the identified one or more portions of the data files prior to replicating a second one of the identified one or more portions of data files,

where the first one of the identified one or more portions of the data files is assigned a higher priority relative to the second one of the identified one or more portions of the data files.

16. The device of claim 12, where, when assigning the priorities, the one or more processors are to execute the instructions to:

determine whether one of the one or more portions of the data files is associated with an active data file,

assign the one of the one or more portions of the data files a first priority when the one of the one or more portions of the data files is associated with the active data file, and

assign the one of the one or more portions of the data files a second priority when the one of the one or more of the portions of the data files is not associated with the active data file,

where a portion of a data file assigned the second priority is replicated before a portion of a data file assigned the first priority.

17. The device of claim 12, where the priorities are assigned based on a number of replicas each of the total numbers of replicas is below the threshold number of replicas.

18. The device of claim 12, where, when assigning the priorities, the one or more processors execute the instructions to:

determine whether one of the identified one or more portions of the data files is associated with a deleted data file,

assign the one of the identified one or more portions of the data files a first priority when the one of the identified one or more portions of the data files is associated with the deleted data file, and

assign the one of the identified one or more portions of the data files a second priority when the one of the identified one or more portions of the data files is not associated with the deleted data file,

where a portion of a data file assigned the second priority is replicated before a portion of a data file assigned the first priority.

19. The device of claim 12, where the threshold number of replicas comprises:

a first threshold number of replicas associated with a first type of data file, and

a second threshold number of replicas associated with a second type of data file,

where the one or more processors execute the instructions further to;

determine that one of the identified one or more portions of the data files is associated with the first type of data file,

determine that another one of the identified one or more portions of the data files is associated with the second type of data file, and

where, when identifying the one or more portions of the data files that are associated with the total number of replicas below the threshold number of replicas, the one or more processors execute the instructions further to;

identify that the one of the identified one or more portions of the data files is associated with the total number of replicas below the first threshold number of replicas, based on the one of the identified one or more portions of the data files being associated with the first type of data file, and

identify that the other one of the identified one or more portions of the data files is associated with the total number of replicas below the second threshold number of replicas, based on the other one of the identified one or more portions of the data files being associated with the second type of data file,

the second threshold number of replicas being different from the first threshold number of replicas.

20. The device of claim 12, where, when replicating the identified one or more portions of the data files, the one or more processors execute the instructions further to:

determine a utilization of a memory for each of the plurality of devices,

select one or more of the plurality of devices based on the determined utilizations, and

cause each of the selected one or more of the plurality of devices to create a replica of one of the identified one or more portions of the data files.

15. A device comprising:

a memory storing instructions; and

one or more processors to execute the instructions to;

monitor a plurality of devices storing replicas of portions of data files,

identify, based on monitoring the plurality of devices, one or more of the portions of the data files that are associated a total number of replicas below a threshold number of replicas,

assign priorities to the identified one or more of the portions of the data files, and

replicate the identified one or more of the portions of the data files in an order based on the assigned priorities.