Lease based leader election system

• US 9,984,140 B1
• Filed: 02/05/2015
• Issued: 05/29/2018
• Est. Priority Date: 02/05/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sukumaran, Anish, Nicotra, Vincent Gerard
• Primary Examiner(s): Bowen, Richard
• Application Number:
  US14/615,302
• Time in Patent Office: 1,209 Days
• Field of Search: None
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A database service may store data on behalf of clients in multiple replicas on respective computing nodes in different availability zones. The service may employ a lease based protocol to select a master replica for a replica group that does not depend on an external service, but is managed by client processes executing on the database hosts themselves. To assume the role of a primary (writable) master for a database table, a master host may acquire a lease by updating a lease record for the table that is maintained in a consistent data store. If the master host fails to renew the lease within a pre-determined lease period, it may revert to read-only mode, and a secondary master host, having determining (based on the lease record) that the primary master no longer holds the lease, may assume the role of primary master by acquiring the lease and making itself writable.

Claims

1. A system, comprising:

a database service, implemented by one or more computing devices and configured to store a replica of a database table on respective master hosts on computing devices in the system, each master host residing in a different availability zone, wherein a master host configured to act as a primary master host can service write requests that are directed to the database table;

a data storage service, implemented by one or more computing devices;

wherein one of the master hosts is configured to assume the role of primary master host for the database table, wherein to assume the role of primary master host, the one of the master hosts is configured to;

update a lease record maintained by the data storage service to reflect that the one of the master hosts holds a lease for the database table, wherein the lease represents an authorization to act as the primary master host for the database table for a pre-determined lease period; and

enter a writable mode that enables writing to the replica of the database table stored on the one of the master hosts;

wherein the other one of the master hosts is configured to;

access the lease record to determine whether the lease is held; and

in response to determining that the lease is held by the one of the master hosts, maintain the replica of the database table stored on the other one of the master hosts in a read-only mode;

wherein the one of the master hosts is further configured to;

access, subsequent to assuming the role of primary master host and prior to expiration of the pre-determined lease period, the lease record to determine whether the lease is still held by the one of the master hosts;

maintain the replica of the database table stored on the one of the master hosts in the writable mode and renew the lease, in response to determining that the lease is still held by the one of the master hosts, wherein to renew the lease, the one of the master hosts updates the lease record to reflect that the one of the master hosts still holds the lease and that it has been renewed; and

enter a read-only mode and refrain from renewing the lease, in response to determining that the lease is held by the other one of the master hosts.

2. The system of claim 1, wherein, while the one of the master hosts holds the lease, the one of the master hosts is further configured to:

receive and service write requests that are directed to the database table; and

replicate the write requests to the other one of the master hosts.

3. The system of claim 1, wherein the other one of the master hosts is configured to assume the role of primary master host for the database table and enter a writable mode, in response to the one of the master hosts entering a read-only mode.

4. The system of claim 3,

wherein each of the respective master hosts is further configured to store information reflecting its replication status to the data storage service;

wherein, prior to entering the writable mode, the other one of the master hosts is configured to determine, based at least in part on the information reflecting its replication status and the replication status of the one of the master hosts, whether the data in the replica of the database table on the other one of the master hosts is caught up with the data in the replica of the database table on the one of the master hosts; and

wherein the other one of the master hosts is configured to enter the writable mode in response to determining that the data in the replica of the database table on the other one of the master hosts is caught up with the data in the replica of the database table on the one of the master hosts.

5. The system of claim 1, further comprising, in each of the availability zones, one or more read-only replicas of the database table, wherein each of the read-only replicas is hosted on a computing device in the system that serves as a slave with respect to the master host residing in the same availability zone.

6. A method, comprising:

performing by one or more computers;

acquiring, by a given one of a group of two or more computing nodes that operate collectively over multiple availability zones, a lease that represents an authorization to assume a particular role within the group of computing nodes for a pre-determined lease period, wherein at most one of the computing nodes in the group can be authorized to perform the particular role at a time, and wherein acquiring the lease comprises updating a lease record maintained in a consistent data store to reflect the acquisition of the lease;

renewing, one or more times by the given computing node subsequent to said assuming the particular role, the lease, wherein renewing the lease comprises updating the lease record to reflect the continued ownership of the lease by the given computing node;

accessing, by another one of the group of computing nodes, the lease record maintained in the consistent data store;

determining, by the other computing node, dependent at least in part on the lease record, whether the given computing node has renewed the lease during a most recent lease period;

acquiring, by the other computing node, in response to determining that the given computing node has not renewed the lease during the most recent lease period, the lease, wherein acquiring the lease comprises updating the lease record to reflect the acquisition of the lease by the other computing node; and

assuming, by the other computing node, the particular role within the group of computing nodes for the next lease period.

7. The method of claim 6, further comprising:

performing, by the given computing node, the particular role within the group of computing nodes while it holds the lease.

8. The method of claim 7,

wherein performing, by the given computing node, the particular role within the group of computing nodes while it holds the lease comprises executing a particular process that can only be executed by the one of the computing nodes that holds the lease;

and

wherein acquiring, by the other computing node, the lease further comprises killing the particular process on the given computing node.

9. The method of claim 6, further comprising:

storing locally, by the other computing node, the lease record and a local timestamp indicating when the lease record was accessed; and

comparing, by the other computing node, the local timestamp with another local timestamp that was stored along with the lease record when the lease record was previously accessed to determine if the pre-determined lease period or a safe portion of the pre-determined lease period has expired.

10. The method of claim 6, wherein the given computing node did not renew the lease during the most recent lease period due to a failure of the given computing node during the most recent lease period or because the given computing node was unable to access the consistent data store during the most recent lease period.

11. The method of claim 6,

wherein the group of computing nodes implements a database service;

wherein the particular role assumed by the given computing node is that of a primary master host for replicas of a database table that is stored by the database service on respective ones of the computing nodes in the group of computing nodes; and

wherein the replica stored on the primary master host is the only replica stored on the computing nodes in the group of computing nodes that is writable.

12. The method of claim 11, further comprising:

servicing, by the given computing node while acting as the primary master host for replicas of the database table, write requests that are directed to the database table;

replicating, by the given computing node while acting as the primary master host for replicas of the database table, the write requests to one or more computing nodes serving as slaves to the primary master host and to a computing node in an availability zone other than an availability zone in which the given computing node resides that serves as a secondary master host for replicas of the database table, wherein replicas stored on the one or more computing nodes serving as slaves to the primary master host and the replica stored on the secondary master host are read-only replicas; and

replicating, by the computing node that serves as the secondary master host, the write requests to one or more computing nodes in the other availability zone serving as slaves to secondary master host, wherein replicas stored on the one or more computing nodes serving as slaves to the secondary master host are read-only replicas.

13. The method of claim 11, further comprising, subsequent to determining that the given computing node has not renewed the lease during the most recent lease period and prior to acquiring the lease:

waiting, by the other computing node, for a pre-determined wait period to expire or for replication status information maintained by the consistent data store to indicate that the given computing node has switched from a writable mode to a read-only mode.

14. The method of claim 11, wherein assuming, by the other computing node, the particular role within the group of computing nodes for the next lease period comprises:

determining, by the other computing node, whether the database table has been completely replicated on the other computing node; and

switching, by the other computing node, from a read-only mode to a writable mode, in response to determining that the database table has been completely replicated on the other computing node or in response to determining that a flag indicating that the other computing node should be forced into a writable mode is set.

15. The method of claim 11,

wherein the other computing node is a computing node in an availability zone other than an availability zone in which the given computing node resides that serves as a secondary master host for replicas of the database table;

and

wherein acquiring, by the other computing node, the lease, and said assuming, by the other computing node, the particular role within the group of computing nodes for the next lease period are performed automatically by the other computing node in response to in response to determining that the given computing node has not renewed the lease during the most recent lease period.

16. The method of claim 11, further comprising:

storing, by each of the given computing node and the other computing node to the consistent data store, one or more of;

replication status information indicating the latest transaction that was applied to the replica of the database table stored on the corresponding computing node or audit data describing one or more attempts made by the corresponding computing node to acquire the lease.

17. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to implement a database service,

wherein the database service comprises two master hosts, each residing in a different availability zone;

wherein each of the master hosts executes a respective instance of a client process for performing lease based leader election, and wherein the respective instances of the client process collectively control assumption, by no more than one of the master hosts at a time, of the role of primary master host for a given database table, replicas of which are stored on each of the master hosts;

wherein to control assumption of the role of primary master host, the respective instance of the client process executing on each of the master hosts is configured to perform one or more of;

accessing lease information for the given database table that is maintained by a consistent data storage service;

determining, dependent on the lease information, whether a lease that represents an authorization to assume the role of primary master host for the given database table for a pre-determined lease period is held by one of the master hosts;

determining, dependent on the lease information or on replication status information for one or more of the master hosts that is maintained by the consistent data storage service, whether a master host that holds the lease has renewed the lease within a most recent lease period;

acquiring the lease in response to determining that no other master host holds the lease or that a master host that holds the lease has not renewed the lease within a most recent lease period, wherein acquiring the lease comprises updating the lease information for the given database table that is maintained by the consistent data storage service to reflect the acquisition of the lease by the master host;

or

renewing the lease prior to the expiration of the lease period in response to determining that the master host holds the lease, wherein renewing the lease comprises updating the lease information for the given database table that is maintained by the consistent data storage service to reflect the continued ownership of the lease by the master host.

18. The storage medium of claim 17, wherein the client process instance executing on each of the master hosts comprises a database state manager process,

wherein the database state manager process performs:

said accessing the lease information for the given database table that is maintained by a consistent data storage service;

said determining whether the lease is held by one of the master hosts; and

said renewing the lease; and

wherein the database state manager process further performs;

storing the lease information for the given database table locally on the master host; and

updating the replication status information for the master host that is maintained by the consistent data storage service.

19. The storage medium of claim 18, wherein the client process instance executing on each of the master hosts comprises a database write manager process,

wherein the database state manager process performs:

determining, dependent at least in part on the lease information for the given database table that is stored locally on the master host by the database state manager process, whether the master host owns the lease and whether the lease has been renewed during a most recent lease period; and

maintaining the replica of the given database table that is stored on the master host in a writable state in response to determining that the master host owns the lease and that the lease has been renewed during a most recent lease period or placing the replica of the given database table that is stored on the master host in a read-only state in response to determining that the master host does not own the lease or that the master host owns the lease but did not renew the lease during a most recent lease period.

20. The storage medium of claim 19,

wherein placing the replica of the given database table that is stored on the master host in a read-only state in response to determining that the master host does not own the lease or that the master host owns the lease but did not renew the lease during a most recent lease period comprises issuing a command to place the replica in a read-only state that blocks until all active transactions directed to the replica of the given database table that is stored on the master host have released their locks;

and

wherein the database state manager process further performs killing all active transactions that have not released their locks within a pre-determined blocking period.

21. The storage medium of claim 18,

wherein storing the lease information for the given database table locally on the master host comprises storing the lease information along with a timestamp indicating the time at which the lease information was retrieved from the consistent data store or the time at which the lease information was stored locally;

and

wherein the database state manager process further performs determining, dependent at least in part on the timestamp, whether a lease period or a safe portion of the a lease period has expired.