Placement of volume partition replica pairs

Patent metadata

Field	Value
Publication number	US-9826030-B1
Application number	US-201514731337-A
Country	US
Kind code	B1
Filing date	Jun 4, 2015
Priority date	Jun 4, 2015
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

A system and method for providing sets of partition placements, the system and method including, receiving at least one placement request for a set of partitions of a volume. Based at least in part on counts of pairs of partitions hosted by pairs of computing devices, the system and method further includes determining how suitable the pairs of computing devices are for placement of partitions of the set of partitions, generating a set of placements based at least in part on the determination, and providing the set of placements in response to the at least one placement request.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a request for at least one partition placement for placing a partition;
calculating replica pair count, wherein the replica pair count includes a count of pairs of replicated partitions allocated to a customer of a computing resource service provider that are hosted by a pair of servers;
determining a server suitability score based at least in part on the replica pair count, the server suitability score comprising how suitable a server is for placement of a specified partition;
generating the at least one partition placement based at least in part on the server suitability score; and
providing the at least one partition placement.

2. The computer-implemented method of claim 1 , further comprising, for a replicated volume comprising partitions, the partitions having a first partition and a second partition, with the first and second partitions being replicas of each other:
perform the receiving, calculating, determining, generating, and providing for the first partition; and
perform the receiving, calculating, determining, generating, and providing for the second partition.

3. The computer-implemented method of claim 1 , wherein determining the server suitability score further comprises:
favoring servers with lower replica pair counts when a count of previously provided placements exceeds a threshold; and
favoring servers with higher replica pair counts when the count of previously provided placements does not exceed a threshold.

4. The computer-implemented method of claim 1 , wherein:
the partition is a member of a set of replicated partitions of a replicated volume of the customer; and
the replica pair count corresponds to a count of pairs of replicated partitions allocated to the customer.

5. The computer-implemented method of claim 1 , wherein the partition placement is one of a plurality of partition placements for placing the partition.

6. A system, comprising:
one or more processors; and
memory including instructions that, when executed by the one or more processors, cause the system to:
receive a request for a placement for placing a partition of a volume;
calculate a partition pair count, wherein the partition pair count includes a count of pairs of replicated partitions of one or more volumes hosted by pairs of computing devices;
determine a suitability score based at least in part on the partition pair count, the suitability score comprising how suitable a computing device is for placement of the partition;
generate the placement based at least in part on the suitability score; and
provide the placement.

7. The system of claim 6 , wherein:
the volume is allocated to a customer of a computing resource service provider; and
the one or more volumes included in calculating the partition pair count are allocated to the customer and the one or more volumes includes the volume.

8. The system of claim 6 , wherein the one or more volumes included in calculating the partition pair count is one or more replicated volumes allocated to one or more customers.

9. The system of claim 6 , wherein the one or more of volumes included in calculating the partition pair count is a replicated volume comprising pairs of replicated partitions including the partition.

10. The system of claim 6 , wherein the instructions that cause the system to determine the suitability score further include instructions that cause the system to favor higher partition pair counts.

11. The system of claim 6 , wherein the instructions that cause the system to determine the suitability score further include instructions that cause the system to favor lower partition pair counts.

12. The system of claim 6 , wherein the instructions that cause the system to determine the suitability score further include instructions that cause the system to, based at least in part on a count of previously provided sets of placements:
favor lower partition pair counts if the count of previously provided sets of placements does not exceed a threshold; and
favor higher partition pair counts, if the count of previously provided sets of placements exceeds the threshold.

13. The system of claim 6 , wherein the instructions that cause the system to determine the suitability score further include instructions that cause the system to, based at least in part on a count of previously provided sets of placements:
favor higher partition pair counts if the count of previously provided sets of placements does not exceed a threshold; and
favor lower partition pair counts, if the count of previously provided sets of placements exceeds the threshold.

14. The system of claim 6 , wherein the instructions further include instructions that cause the system to, based at least in part on a determination that currently-placed partitions of the volume are out of compliance with a set of constraints, reorganize the currently-placed partitions of the volume.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:
receive at least one placement request for a set of partitions of a volume;
based at least in part on a count of pairs of partitions hosted by pairs of computing devices, determine how suitable the computing devices are for placement of partitions of the set of partitions;
generate a placement based at least in part on the determination; and
provide the placement in response to the at least one placement request.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions that determine how suitable the pairs of computing devices are, further include instructions that cause the computer system to favor pairs of computing devices that have a higher count of hosted pairs of partitions than other pairs of computing devices.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions that determine how suitable the pairs of computing devices are, further include instructions that cause the computer system to favor pairs of computing devices that have a lower count of hosted pairs of partitions than other pairs of computing devices.

18. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions that determine how suitable the pairs of computing devices are, further include instructions that:
if a number of currently-placed partitions of the volume does not exceed a threshold, cause the computer system to more favorably weight a first pair of computing devices than a second pair of computing devices if the first pair of computing devices has a higher count of hosted pairs of partitions than the second pair of computing devices; and
if the number of currently placed partitions of the volume exceeds a threshold, cause the computer system to more favorably weight a first pair of computing devices than a second pair of computing devices if the first pair of computing devices has a lower count of hosted pairs of partitions than the second pair of computing devices.

19. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions that cause the computer system to determine how suitable the pairs of computing devices are include instructions that cause the computer system to determine how suitable the pairs of computing devices are for placement of the volume based further in part on performance requirements of the volume.

Assignees

• Amazon Tech Inc

Inventors

• Dhoolam Surya Prakash
• Greenwood Christopher Magee
• Flaherty Mitchell Gannon
• Brooker Marc John
• Peet Iain Michael Christopher
• Lakshmikanth Nishant Satya

Classifications

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L67/1008 Primary

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• H04L67/1095

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title