Distributed state manager jury selection

• US 9,852,221 B1
• Filed: 03/26/2015
• Issued: 12/26/2017
• Est. Priority Date: 03/26/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Callau, Carlos Vara, Vermeulen, Allan Henry, De Kadt, Christopher Richard Jacques
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/670,238
• Time in Patent Office: 1,006 Days
• Field of Search: 707723
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• 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

A jury candidate server (JCS) of a distributed state manager (DSM) implements a plurality of jury configuration evaluation iterations. In a particular iteration, the JCS generates one or more jury configuration options (JCOs) representing changes to a current jury, and assigns quality metrics to the JCOs based at least in part on a prioritized set of criteria among which location diversity has the highest priority. If a JCO meets a quality threshold, a corresponding jury transition is proposed for approval by the current jury.

Claims

1. A system, comprising:

one or more computing devices of a provider network, the one or more computing devices comprising one or more processors and memory storing program instructions that are executable by the one or more processors to instantiate a plurality of jury candidate servers (JCSs) of a distributed state manager (DSM), including a particular JCS, wherein one or more JCSs of the plurality of JCSs are designated as members of a jury responsible for determining whether to accept proposed transitions to at least a first state machine representing a distributed application; and

one or more client nodes of the distributed application;

wherein the particular JCS is configured to implement a sequence of configuration evaluation iterations, wherein a particular configuration evaluation iteration of the sequence comprises;

obtaining, using one or more locally-stored records at the particular JCS, (a) a first view of a respective availability status of individual JCSs of the plurality of JCSs, and (b) a second view of membership of a current jury;

generating one or more jury configuration options (JCOs) based at least in part on the first and second views, wherein a particular JCO of the one or more JCOs includes at least one change to the current jury;

computing, based at least in part on a plurality of prioritized criteria including (a) a location diversity criterion assigned a first priority and (b) an availability status criterion assigned a lower priority than the first priority;

a respective configuration quality score (CQS) of each of the one or more JCOs; and

a CQS of the current jury; and

proposing, for approval by the current jury, in response to a determination that a particular JCO'"'"'s CQS meets a threshold criterion with respect to the CQS of the current jury, a jury transition corresponding to the particular JCO; and

in response to determining that the jury transition has been approved, storing a particular local record indicative of a new jury resulting from the jury transition; and

wherein, in response to an approval by the new jury of a data modification request pertaining to the distributed application and received from a particular client node of the one or more client nodes, the particular JCS is configured to store an indication of the data modification corresponding to the data modification request.

2. The system as recited in claim 1, wherein the one or more JCOs include a first JCO and a second JCO, wherein in accordance with the location diversity criterion, the first JCO is assigned a higher CQS than the second JCO in response to a determination that jury members are distributed among a greater number of availability containers of the provider network in the first JCO than in the second JCO.

3. The system as recited in claim 1, wherein in accordance with the location diversity criterion, a first JCO of the one or more JCOs is assigned a CQS based at least in part on one or more of:

(a) a server rack at which a second JCS designated as a jury member in the first JCO is located (b) a data center room in which the second JCS is located or (c) a data center in which the second JCS is located.

4. The system as recited in claim 1, wherein the particular JCO includes, as a member of the jury, at least one JCS which is classified as being in an inactive state by the particular JCS.

5. The system as recited in claim 1, wherein said generating the one or more JCOs comprises:

identifying, by the particular JCS, one or more permissible jury membership changes, wherein each permissible jury membership change of the one or more permissible jury membership changes includes a change to a jury membership status of the particular JCS; and

selecting, for the particular JCO, a particular jury membership change of the one or more permissible jury membership changes.

6. A method, comprising:

performing, by one or more computing devices configured as a particular jury candidate server (JCS) of a plurality of JCSs of a distributed state manager (DSM), one or more configuration evaluation iterations, wherein one or more JCSs of the plurality of JCSs are designated as members of a jury responsible for implementing a state machine representing a particular application, wherein a particular configuration evaluation iteration of the one or more configuration evaluation iterations comprises;

generating one or more jury configuration options (JCOs), wherein a particular JCO of the one or more JCOs includes at least one change to a current jury membership;

computing, based at least on part on a plurality of prioritized criteria including a location diversity criterion assigned a highest priority among the plurality of prioritized criteria, a respective configuration quality ranking (CQR) of (a) each of the one or more JCOs and (b) the current jury membership; and

proposing, for approval by a current jury, in response to a determination that a CQR of a particular JCO of the one or more JCOs meets a threshold criterion, a jury transition corresponding to the particular JCO; and

in response to determining that the jury transition has been approved, storing a particular local record indicative of a new jury corresponding to the jury transition.

7. The method as recited in claim 6, wherein the one or more JCOs include a first JCO and a second JCO, wherein in accordance with the location diversity criterion, the first JCO is assigned a higher CQR than the second JCO in response to a determination that jury members are distributed among a greater number of availability containers of a provider network in the first JCO than in the second JCO.

8. The method as recited in claim 6, wherein in accordance with the location diversity criterion, a first JCO of the one or more JCOs is assigned a CQR based at least in part on one or more of:

(a) a server rack at which a second JCS designated as a jury member in the first JCO is located (b) a data center room in which the second JCS is located or (c) a data center in which the second JCS is located.

9. The method as recited in claim 6, wherein a first JCO of the one or more JCOs is assigned a CQR based at least in part on an identification of a component of a data center'"'"'s physical infrastructure which is being used for a second JCS designated as a jury member in the first JCO, wherein the component of the data center'"'"'s physical infrastructure comprises one of:

(a) an electrical component or (b) a cooling component.

10. The method as recited in claim 6, wherein the particular JCO includes, as a member of the jury, at least one JCS which is classified as being in an inactive state by the particular JCS.

11. The method as recited in claim 6, wherein the plurality of prioritized criteria include a server availability status criterion.

12. The method as recited in claim 6, wherein individual ones of the plurality of JCSs comprise respective threads of execution at one of a set of execution platform categories, wherein the execution platform categories of the set differ from one another at least in a performance capacity, and wherein the plurality of prioritized criteria include an execution platform diversity criterion.

13. The method as recited in claim 6, wherein the plurality of prioritized criteria include a server utilization level criterion.

14. The method as recited in claim 6, wherein said generating the one or more JCOs comprises:

identifying, by the particular JCS, a set of permissible jury membership changes, each of which includes a change to a jury membership status of the particular JCS; and

selecting, for the particular JCO, a particular jury membership change of the set of permissible jury membership changes.

15. The method as recited in claim 6, wherein the plurality of JCSs includes a first JCS and a second JCS, and wherein the jury transition comprises an atomic operation which includes (a) an addition of the first JCS to the jury and (b) a removal of the second JCS from the jury.

16. The method as recited in claim 6, further comprising:

storing, by the particular JCS at a local storage device, a plurality of configuration commit sequence numbers (CSNs) corresponding to respective approved jury transitions, wherein said proposing the jury transition includes indicating a particular proposed CSN corresponding to the jury transition, wherein the particular proposed CSN is based at least in part on a maximum CSN among the plurality of CSNs stored at the local storage device.

17. The method as recited in claim 6, wherein said proposing the jury transition comprises providing, by the particular JCS to a particular member of the current jury, an indication of a highest commit sequence number (CSN) corresponding to approved jury transitions stored at a local storage device of the particular JCS, further comprising:

verifying, by the particular member of the current jury prior to approving the jury transition proposed by the particular JCS, that the highest CSN corresponds to a most-recently-approved jury transition.

18. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a particular jury candidate server (JCS) of a plurality of JCSs of a distributed state manager (DSM), wherein the plurality of JCSs include one or more JCSs designated as members of a jury responsible for implementing a state machine, wherein the particular JCS is configured to perform one or more configuration evaluation iterations including a particular configuration evaluation iteration comprising:

generating one or more jury configuration options (JCOs), wherein a particular JCO of the one or more JCOs includes at least one change to a current jury membership;

determining, based at least on part on a plurality of prioritized criteria including a location diversity criterion assigned a highest priority among the plurality of prioritized criteria, a respective configuration quality ranking (CQR) of each of the one or more JCOs; and

proposing, for approval by a current jury, in response to a determination that a particular JCO of the one or more JCOs has a higher CQR than a CQR of the current jury, a jury transition corresponding to the particular JCO; and

in response to determining that the jury transition has been approved, storing a particular local record indicative of a new jury membership corresponding to the jury transition.

19. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the one or more JCOs include a first JCO and a second JCO, wherein in accordance with the location diversity criterion, the first JCO is assigned a higher CQR than the second JCO in response to a determination that jury members are distributed among a greater number of availability containers of a provider network in the first JCO than in the second JCO.

20. The non-transitory computer-accessible storage medium as recited in claim 18, wherein a first JCO of the one or more JCOs is assigned a CQR based at least in part on an identification of a component of a data center'"'"'s physical infrastructure which is being used for a second JCS designated as a jury member in the first JCO, wherein the component of the data center'"'"'s physical infrastructure comprises one of:

(a) an electrical component or (b) a cooling component.

21. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the particular JCO includes, as a member of the jury, at least one JCS which is classified as being in an inactive state by the particular JCS.