Mixed-mode replication for sharded database systems

Patent metadata

Field	Value
Publication number	US-11809404-B1
Application number	US-202017038544-A
Country	US
Kind code	B1
Filing date	Sep 30, 2020
Priority date	Sep 30, 2020
Publication date	Nov 7, 2023
Grant date	Nov 7, 2023

Abstract

Techniques are described for enabling a database service to provide a zonal consistency model for read and write operations involving database tables replicated across a plurality of availability zones of a cloud provider network according to some embodiments. A database service routes zonally consistent operations to request routers and storage nodes that are located in a same availability zone as the client device from which the request originates. For example, in contrast to standard write operations and strongly consistent read operations, which are processed by a leader storage node that may be located in a different availability zone than the originating request, zonally consistent operations can be processed by any storage node and, in particular, by a storage node in a same availability zone as the originating client device.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, by a request router of a database service, a request to perform a write operation involving a data item stored in a partition of a database table, wherein the partition is replicated at each of a plurality of storage nodes in a respective plurality of availability zones of a cloud provider network, and wherein the request originates from a computing device located in a first availability zone of the plurality of availability zones;
determining that the request specifies a zonal consistency model for the request;
determining, based on the request specifying a zonal consistency model for the request, to send the request to a first storage node of the plurality of storage nodes located in the first availability zone;
sending the request to the first storage node located in the first availability zone, wherein the first storage node stores a replicated copy of the partition;
generating, by the first storage node, a log entry reflecting the write operation and including a timestamp;
sending, by the first storage node, the log entry to a second storage node of the plurality of storage nodes in a second availability zone of the plurality of availability zones, wherein the second storage node is an elected leader of the plurality of storage nodes based on a leader election protocol;
propagating, by the second storage node, the log entry to the plurality of storage nodes using a consensus protocol; and
sending a response to the computing device indicating that the request was successfully processed.

2. The computer-implemented method of claim 1 , wherein the request is a first request to perform a first write operation, the request router is a first request router, and the log entry is a first log entry including a first timestamp, and wherein the method further comprises:
receiving, by a second request router located in the second availability zone, a second request to perform a second write operation involving the data item, wherein the second write operation conflicts with the first write operation;
sending the second request to the second storage node in the second availability zone;
generating, by the second storage node in the second availability zone, a second log entry reflecting the second write operation and including a second timestamp;
reconciling, by a third storage node of the plurality of storage nodes in a third availability zone of the plurality of availability zones, the conflict between the first write operation and the second write operation in favor of the first write operation based on a comparison of the first timestamp and the second timestamp; and
propagating the first log entry reflecting the first write operation to the plurality of storage nodes using a consensus protocol.

3. A computer-implemented method comprising:
receiving, by a request router of a database service, a request to perform a write operation involving a data item stored in a database table, wherein the data item is stored in a partition of the database table that is replicated at a plurality of storage nodes in a respective plurality of availability zones of a cloud provider network, and wherein the request originates from a computing device located in a first availability zone of the plurality of availability zones and specifies a zonal consistency model;
determining, based on the request specifying a zonal consistency model, to send the request to a first storage node of the plurality of storage nodes, wherein the first storage node is located in the first availability zone;
causing the first storage node located in the first availability zone to process the request using a replicated copy of the partition stored at the first storage node;
generating, by the first storage node in the first availability zone, a log entry reflecting the write operation and including a timestamp;
sending, by the first storage node, the log entry to a second storage node of the plurality of storage nodes in a second availability zone of the plurality of availability zones, wherein the second storage node is an elected leader of the plurality of storage nodes based on a leader election protocol;
propagating, by the second storage node, the log entry to the plurality of storage nodes using a consensus protocol; and
sending a response to the computing device according to the request.

4. The computer-implemented method of claim 3 , wherein the request is a first request to perform a first write operation, the request router is a first request router, and the log entry is a first log entry including a first timestamp, and wherein the method further comprises:
receiving, by a second request router located in the second availability zone a second request to perform a second write operation involving the data item, wherein the second write operation conflicts with the first write operation;
sending the second request to the second storage node in the second availability zone;
generating, by the second storage node in the second availability zone, a second log entry reflecting the second write operation and including a second timestamp;
reconciling, by a third request router in a third availability zone of the plurality of availability zones, the conflict between the first write operation and the second write operation in favor of the first write operation based on a comparison of the first timestamp and the second timestamp; and
propagating the first log entry reflecting the first write operation to the plurality of storage nodes using a consensus protocol.

5. The computer-implemented method of claim 3 , further comprising receiving a request to read another data item stored in the database table, and wherein the first storage node obtains the another data item using an index managed by the first storage node.

6. The computer-implemented method of claim 3 , further comprising:
sending, by the first storage node, the log entry to each of two logging servers;
receiving responses from each of the two logging servers indicating that the log entry has been stored by each of the two logging servers; and
sending a response to the computing device indicating that the write operation is successful.

7. The computer-implemented method of claim 3 , wherein the plurality of availability zones is a first plurality of availability zones, wherein the computing device is part of a clustered application including application instances in each of a second plurality of availability zones, and wherein the method further comprises:
determining that requests received from the clustered application originate in each of the second plurality of availability zones; and
migrating replicated copies of the partition to storage nodes located in the second plurality of availability zones.

8. The computer-implemented method of claim 3 , further comprising determining, by the request router, the first availability zone based on an identifier of the first availability zone included in the request.

9. The computer-implemented method of claim 3 , wherein the log entry is stored in one of: a replication log used by storage nodes in the plurality of availability zones to replicate the database table using a consensus-based replication protocol, or a separate zonal log.

10. The computer-implemented method of claim 3 , further comprising causing the first storage node to generate a zonal log entry that identifies the first availability zone in which the first storage node is located and to send the zonal log entry to one or more log acceptors in the first availability zone in which the first storage node is located.

11. A system comprising:
a first one or more electronic

Assignees

• Amazon Tech Inc

Inventors

• Mritunjai Akhilesh
• Vig Akshat
• Howard Craig Wesley
• He Hao

Classifications

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• H04L67/1021 Primary

  based on client or server locations · CPC title

• G06F16/27

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