Lease based leader election system

Patent metadata

Field	Value
Publication number	US-9984140-B1
Application number	US-201514615302-A
Country	US
Kind code	B1
Filing date	Feb 5, 2015
Priority date	Feb 5, 2015
Publication date	May 29, 2018
Grant date	May 29, 2018

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.

First claim

What is claimed is:

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;
rep

Assignees

• Amazon Tech Inc

Inventors

• Sukumaran Anish
• Nicotra Vincent Gerard

Classifications

• G06F16/219

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F17/30309

  Physics · mapped topic

• G06F17/30575 Primary

  Physics · mapped topic