# US 10,482,102 B2 · Conditional master election in distributed databases > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,102 B2 - Document ID: US10482102B2 - Status: Granted - Kind: B2 - Application number: 15/431,706 - Filed: 2017-02-13 - Published: 2017-06-01 - Granted: 2019-11-19 - Earliest claimed: 2013-09-10 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Akshat Vig; Timothy Andrew Rath; Stuart Henry Seelye Marshall; Rande A. Blackman; David Alan Lutz; Jian Wang; Jiandan Zheng; Janani Narayanan - Web page: https://patentgrep.com/patent/US10482102B2 ## CPC - G06F 16/275: {Synchronous replication} - G06F 16/24565: {Triggers; Constraints} - G06F 16/2471: {Distributed queries} - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - G06F 16/28: Databases characterised by their database models, e.g. relational or object models - G06F 16/90: Details of database functions independent of the retrieved data types - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatus for conditional master election in a distributed database are described. A plurality of replicas of a database object are stored by a distributed database service. Some types of operations corresponding to client requests directed at the database object are to be coordinated by a master replica. Client access to the database object is enabled prior to election of a master replica. In response to a triggering condition, a particular replica is elected master. The master coordinates implementation of operations with one or more other replicas in response to client requests. ## Claims ### Claim 1 A computer-implemented method, comprising: storing a plurality of replicas of a data at respective storage nodes of a distributed database, wherein the plurality of replicas forms a replica group that can transition between a master-less state that in which access requests are processed without coordination by an elected master replica and an active state in which access requests are processed with coordination by an elected master replica; responding by one or more of the replicas to a first type of access request to the data while the replicas operate in the master-less state, wherein processing of the first type of access request does not require any master replica; receiving a second type of access request to the data and determining that processing of the second type of access request requires at least one master replica; and responsive to the determination that the second type of access request requires at least one master replica, transitioning the replica group to the active state, wherein the transitioning includes initiating a master election to elect at least one of the replicas to act as a master replica to process the second type of access request. ### Claim 2 (depends on 1) The method of claim 1, wherein receiving a second type of access request comprises receiving a write request or a consistent-read request to the data. ### Claim 3 (depends on 1) The method of claim 1, wherein responding to a first type of access request comprises responding to an eventually-consistent read request to the data. ### Claim 4 (depends on 1) The method of claim 1, further comprising electing the master replica, the election comprising: requesting, by a given replica, a token from a state manager; granting, by the state manager, the token to the given replica; providing an indication that the token has been received by the given replica; and receiving an acknowledgment from at least one other replica that the given replica has been elected as the master replica. ### Claim 5 (depends on 4) The method of claim 4, wherein the second type of access request is a write request, further comprising: performing, by the master replica: propagating the write request to a non-master replica of the plurality of replicas; and receiving an acknowledgment from the non-master replica that the write request has been completed by the non-master replica. ### Claim 6 (depends on 4) The method of claim 4, wherein the second type of access request is a consistent-read request, further comprising: receiving, by the master replica, an acknowledgment from a non-master replica that a most recent write request that has been completed at the master replica has also been completed by the non-master replica. ### Claim 7 (depends on 1) The method of claim 1, further comprising moving the replicas back to the master-less state, based on a probability that an access request of the second type will be received during a time window. ### Claim 8 (depends on 1) The method of claim 1, further comprising moving the replicas back to the master-less state, based on a determination that no access requests of the second type have been received during a time interval. ### Claim 9 A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors cause the one or more processors to: store a plurality of replicas of a data at respective storage nodes of a distributed database, wherein the plurality of replicas forms a replica group that can transition between a master-less state that in which access requests are processed without coordination by an elected master replica and an active state in which access requests are processed with coordination by an elected master replica; respond by one or more of the replicas to a first type of access request to the data while the replicas operate in the master-less state, wherein processing of the first type of access request does not require any master replica; receive a second type of access request to the data and determine that processing of the second type of access request requires at least one master replica; and responsive to the determination that the second type of access request requires at least one master replica, transition the replica group to the active state, wherein the transition includes initiating a master election for at least one of the replicas to act as a master replica to process the second type of access request. ### Claim 10 (depends on 9) The non-transitory computer-accessible storage medium of claim 9, wherein to receive a second type of access request, the program instructions when executed on the one or more processors cause the one or more processors to receive a write request or a consistent-read request to the data. ### Claim 11 (depends on 9) The non-transitory computer-accessible storage medium of claim 9, wherein to respond to a first type of access request, the program instructions when executed on the one or more processors cause the one or more processors to respond to an eventually-consistent-read request to the data. ### Claim 12 (depends on 9) The non-transitory computer-accessible storage medium of claim 9, wherein the program instructions when executed on the one or more processors cause the one or more processors to electing the master replica, the election comprising: requesting, by a given one replica, a token from a state manager; receiving, by the given replica, the token; providing an indication that the token has been received by the given replica; and receiving an acknowledgment from at least one other replica that the given replica has been elected as the master replica. ### Claim 13 (depends on 12) The non-transitory computer-accessible storage medium of claim 12, wherein the second type of access request is a write request, and the program instructions when executed on the one or more processors cause the one or more processors to: propagate, by the master replica, the write request to a non-master replica of the plurality of replicas; and receive, by the master replica, an acknowledgment from the non-master replica that the write request has been completed by the non-master replica. ### Claim 14 (depends on 12) The non-transitory computer-accessible storage medium of claim 12, wherein the second type of access request is a consistent-read request, and the program instructions when executed on the one or more processors cause the one or more processors to: receive, by the master replica, an acknowledgment from a non-master replica that a most recent write request that has been completed at the master replica has also been completed by the non-master replica. ### Claim 15 (depends on 9) The non-transitory computer-accessible storage medium of claim 9, wherein the program instructions when executed on the one or more processors cause the one or more processors to move the replicas back to the master-less state, based on a probability that an access request of the second type will be received during a time window. ### Claim 16 (depends on 9) The non-transitory computer-accessible storage medium of claim 9, wherein the program instructions when executed on the one or more processors cause the one or more processors to move the replicas back to the master-less state, based on a determination that no access requests of the second type have been received during a time interval. ### Claim 17 A system, comprising: one or more processors with associated memory that implement a state manager configured to grant a token to a replica responsive to a master election attempt by the replica in accordance with a master election protocol; a plurality of processors with associated memory that implement a plurality of storage nodes configured to store data of a distributed database in replica groups, each replica group comprising replicas of a portion of the data, wherein multiple ones of the replica groups can transition between an active state in which access requests are processed with coordination by an elected master replica and a master-less state in which access requests are processed without coordination by an elected master replica; and wherein the multiple replica groups are configured to delay master election to smooth, over time, master election attempts to the state manager upon recovery from an event in which each of the multiple replica groups lost a master replica, to initiate respective master elections at different times after the event in response to receipt of a first type of access request that requires a master replica, and to process a second type of access request that does not require any master replica while in a master-less state before the master election. ### Claim 18 (depends on 17) The system of claim 17, wherein the first type of access request comprises a write request or a consistent-read request, and the second type of access request comprises an eventually-consistent read request. ### Claim 19 (depends on 17) The system of claim 17, wherein the state manager is configured to monitor a health status of the replicas based on heartbeat messages received from the replicas. ### Claim 20 (depends on 17) The system of claim 17, wherein the state manager is configured to revoke a master status of a particular replica based on the health status of the particular replica.