Relative placement of volume partitions

Patent metadata

Field	Value
Publication number	US-9826041-B1
Application number	US-201514731318-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 determining a first set of placements for a first set of partitions first set of partitions of a volume based at least in part on a set of constraints, and placing the first set of partitions based at least in part on the first set of placements. The system and method further includes determining a second set of placements for a second set of partitions of the volume based at least in part on the first set of placements and the set of constraints, the second set of partitions being a replica of the first set of partitions, and placing the second set of partitions based at least in part on the second set of placements.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
under the control of one or more computer systems configured with executable instructions,
receiving a first request for a first set of partition placements for placing a master partition of a volume, the master partition being a member of a partition replica pair comprising the master partition and a slave partition;
generating the first set of partition placements based at least in part on a first server suitability score, the first server suitability score comprising how suitable a server is for placement of a specified partition, the first server suitability score based at least in part on a set of previous partition placements that were previously provided for other partitions of the volume;
providing the first set of partition placements;
receiving a second request for a second set of partition placements for placing the slave partition of the volume;
generating the second set of partition placements based at least in part on a second server suitability score, the second server suitability score based at least in part on a rack diversity constraint, the set of previous partition placements, and the first set of partition placements; and
providing the second set of partition placements.

2. The computer-implemented method of claim 1 , wherein:
the rack diversity constraint specifies that each member should be placed on a server in different rack from the other member; and
the first and second server suitability scores are based at least further in part to minimize a number of racks of servers for hosting partitions of the volume.

3. The computer-implemented method of claim 1 , the method further comprising:
tracking a count of replica pairs comprising a quantity of partition replica pairs hosted on a pair of servers; and
generating the second set of partition placements based at least further in part on the count of replica pairs and a server pair diversity constraint.

4. The computer-implemented method of claim 3 , wherein the server pair diversity constraint specifies that, for a pair of servers, a lower count of replica pairs is preferable to a higher count of replica pairs.

5. A system, comprising:
one or more processors; and
memory including instructions that, when executed by the one or more processors, cause the system to:
generate first placement information for placement of a first partition of a set of partitions of a volume;
save a partition state based at least in part on the first placement information;
provide the first placement information;
generate, based at least in part on the partition state, a second placement information for placement of a second partition of the set of partitions of the volume;
update the partition state based at least in part on the second placement information; and
provide the second placement information.

6. The system of claim 5 , wherein:
the set of partitions is a set of partition pairs, and each member of the partition pair is a replica of the other member; and
the instructions further include instructions that cause the system to generate the second placement information based at least further in part on a constraint specifying:
that the set of partition pairs should be distributed among a specified number of groups of computing devices; and
that each member should be placed with a different group of computing devices than the other member.

7. The system of claim 5 , wherein the instructions further include instructions that cause the system to generate the second placement information based at least further in part on a constraint specifying that the second partition should be placed with a computing device in a same computer network as a computing device indicated in the first placement information.

8. The system of claim 5 , wherein:
the set of partitions is a set of partition pairs, and each pair is a redundant copy of the same logical data; and
the instructions further include instructions that cause the system to:
obtain a set of partition pair counts comprising a quantity of partition pairs hosted by a pair of computing devices that are available to host a partition pair; and
generate the second placement information based at least further in part on a constraint that weights the second placement information based at least in part on the set of partition pair counts.

9. The system of claim 5 , wherein the second partition is a copy of data comprising the first partition.

10. The system of claim 5 , wherein:
the volume is configured to have a set of master partitions and a set of slave partitions, wherein the set of slave partitions is a replica of the set of master partitions; and
the first partition and the second partition are members of the set of master partitions.

11. The system of claim 5 , wherein the instructions further include instructions that cause the system to:
determine a computing device indicated by the first placement information for placing the first partition; and
based at least in part on the determination, place the first partition with the computing device.

12. The system of claim 11 , wherein:
the instructions that cause the system to generate the first placement information further include instructions that cause the system to indicate suitability levels for placement, wherein the suitability levels comprise how suitable a computing device is for placement of the first partition; and
the instructions that cause the system to determine the computing device further include instructions that cause the system to iterate through the first placement information and determine the computing device based on the suitability levels for placement and whether a computing device indicated by the first placement information is still available for placing the first partition.

13. 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:
determine a first set of placements for a first set of partitions corresponding to a replicated volume based at least in part on a set of constraints;
place the first set of partitions based at least in part on the first set of placements;
determine a second set of placements for a second set of partitions corresponding to the replicated volume based at least in part on the first set of placements and the set of constraints, the second set of partitions being a replica of the first set of partitions; and
place the second set of partitions based at least in part on the second set of placements.

14. The non-transitory computer-readable storage medium of claim 13 , wherein the first set of placements and the second set of placements include suitability scores of computing devices.

15. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further include instructions that, when executed by the one or more processors, cause the computer system to save placement state information corresponding to the first set of partitions based at least in part on the first set of placements.

16. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further include instructions that cause the computer system to assess whether currently-placed volume partitions are in compliance with the set of constraints, and, if not, reorganize one or more volume partitions to bring the currently-placed volume partitions into closer compliance with the set of constraints.

17. Th

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

• H04L67/1095

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

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• H04L67/1097 Primary

  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