Log-structured distributed storage using a single log sequence number space

• US 9,552,242 B1
• Filed: 09/25/2013
• Issued: 01/24/2017
• Est. Priority Date: 09/25/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Leshinsky, Yan Valerie, Corey, James McClellan, Madhavarapu, Pradeep Jnana, Gupta, Anurag Windlass, Tobler, Benjamin, McKelvie, Samuel James
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): DAVIS, INDIA L
• Application Number:
  US14/036,775
• Time in Patent Office: 1,217 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A distributed database system may implement log-structured distributed storage using a single log sequence number space. A log for a data volume may be maintained in a log-structured distributed storage system. The log may be segmented across multiple protection groups according to a partitioning of user data for the data volume. Updates to the log may be assigned a log sequence number from a log sequence number space for the data volume. A protection group may be determined for an update according to which partition of user data space the update pertains. Metadata to be included with the log record may indicate a previous log sequence number of a log record maintained at the protection group. The log record may be sent to the protection group and identified as committed based on acknowledgments received from storage nodes implementing the protection group.

Claims

1. A system, comprising:

a log-structured distributed storage system that maintains a log for a data volume, wherein updates to the log are assigned a log sequence number according to a log sequence number space for the data volume, wherein the log is segmented across a plurality of protection groups according to a partitioning of user data for the data volume such that a segment of the log and a partition of user data to which the segment of the log pertains are co-located together at a protection group, wherein each protection group comprises a plurality of storage nodes that provide redundant storage for a given segment of the log; and

a storage client that processes access requests for the data volume and is configured to;

in response to receiving an update to the log;

determine a protection group of the plurality of protection groups according to which partition of user data space the update pertains;

generate metadata to be included with a log record indicating the update, wherein the metadata comprises an indication of a previous log sequence number of a log record maintained at the protection group such that a position in a recovery sequence for the protection group and a position in the log sequence number space are identifiable;

send the log record to the protection group; and

based, at least in part, on acknowledgments received from one or more of the plurality of storage nodes implementing the protection group, identify the log record as eligible for durability in the log for the data volume.

2. The system of claim 1,

wherein the storage client is further configured to:

upon recovery from a failure of the storage client;

request one or more candidate log records for log recovery from each of the plurality of protection groups;

evaluate the received candidate log records to identify a recovery point in the log for the data volume according to the log sequence number space;

make a view of the data available for access requests consistent with the recovery point in the log for the data volume;

wherein each protection group of the plurality of protection groups is configured to;

receive the request for the one or more candidate log records for log recovery from the storage client;

based, at least in part, on metadata indicating a previous log sequence number for each log record maintained at the protection group, select one or more log records to identify as the one or more candidate log records for log recovery from the protection group; and

send respective metadata for the one or more candidate log records to the storage client.

3. The system of claim 1, wherein the log for the data volume is not segmented across the plurality of protection groups according to different ranges in the log sequence number space.

4. The system of claim 1, wherein the storage client is a database node of a network-based database service, and wherein the log-structured, distributed storage system is a network-based, multi-tenant distributed storage service.

5. A method, comprising:

performing, by a plurality of computing devices;

maintaining a log for a data volume at a log-structured distributed storage system for a storage client, wherein updates to the log are assigned a log sequence number according to a log sequence number space for the data volume, wherein the log is segmented across a plurality of protection groups according to a partitioning of user data for the data volume such that a segment of the log and a partition of user data to which the segment of the log pertains are co-located together at a protection group; and

in response to receiving an update to the log;

determining a protection group of the plurality of protection groups according to which partition of user data space the update pertains;

generating metadata to be included with a log record indicating the update, wherein the metadata comprises an indication of a previous log sequence number of a log record maintained at the protection group such that a position in a recovery sequence for the protection group and a position in the log sequence number space for the data volume are identifiable; and

sending the log record to the protection group.

6. The method of claim 5, further comprising based, at least in part, on one or more acknowledgments of the log record received from one or more storage nodes of a plurality of storage nodes implementing the protection group, identifying the log record as eligible for durability in the log for the data volume.

7. The method of claim 6, further comprising:

upon recovery from failure of the storage client;

requesting from each of the plurality of protection groups one or more candidate log records for log recovery;

evaluating the received candidate log records to identify a recovery point in the log for the data volume according to the log sequence number space; and

making a view of the data volume available for access requests consistent with the recovery point in the log for the data volume.

8. The method of claim 7, further comprising:

receiving, at a protection group, the request for one or more candidate log records for log recovery; and

based, at least in part, on metadata indicating a previous log sequence number for each log record maintained at the protection group, selecting one or more log records to identify as the one or more candidate log records for log recovery from the protection group for which respective metadata is to be sent in response to the request.

9. The method of claim 8, further comprising removing from the selected one or more log records those log records that do not indicate completion of a system transaction.

10. The method of claim 7, wherein the generated metadata included with the log record further comprises an indication of a previous log sequence number of a log record in the log sequence number space, and wherein said evaluating the received candidate log records to identify the recovery point in the log for the data volume according to the log sequence number space, comprises determining a first break in a sequence of the received candidate log records in the log sequence number space based, at least in part, on respective indicators of a previous log sequence number in the log sequence number space in metadata included with the received candidate log records.

11. The method of claim 7, wherein the recovery point indicates a range of log records in the log sequence number space, and wherein said making the view of the data volume available for access requests consistent with the recovery point in the log for the data volume, comprises excluding log records with log sequence numbers within the indicated range of log records from the log for the data volume.

12. The method of claim 11, wherein said excluding log records with log sequence numbers within the indicated range of log records from the log for the data volume is performed at each of the protection groups in parallel with respect to the respective segment of the log and partition of the user data at the protection group.

13. The method of claim 5, wherein said maintaining, said determining, said generating, and said sending are performed without performing a two-phase commit.

14. The method of claim 5, wherein the storage client is a network-based, database service, and wherein the log-structured, distributed storage system is a network-based, distributed storage service.

15. A non-transitory, computer-readable storage medium, storing program instructions that when executed by a plurality of computing devices cause the plurality of computing devices to implement:

maintaining a log for a data volume at a log-structured distributed storage system for a storage client, wherein updates to the log are assigned a log sequence number according to a log sequence number space for the data volume, wherein the log is segmented across a plurality of protection groups according to a partitioning of user data for the data volume such that a segment of the log and a partition of user data to which the segment of the log pertains are co-located together at a protection group; and

in response to receiving an update to the log;

determining a protection group of the plurality of protection groups according to which partition of user data space the update pertains;

generating metadata to be included with a log record indicating the update, wherein the metadata comprises an indication of a previous log sequence number of a log record maintained at the protection group such that a position in a recovery sequence for the protection group and a position in the log sequence number space for the data volume are identifiable;

sending the log record to the protection group; and

based, at least in part, on one or more acknowledgments of the log record received from one or more storage nodes of a plurality of storage nodes implementing the protection group, identifying the log record as eligible for durability in the log for the data volume.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the log for the data volume is not segmented across the plurality of protection groups by striping the log sequence number space.

17. The non-transitory, computer-readable storage medium of claim 15, wherein in said identifying the log record as eligible for durability in the log for the data volume, the program instructions when executed by the plurality of computing devices cause the plurality of computing devices to implement determining that the one or more acknowledgments of the log record satisfy a write quorum requirement.

18. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions when executed by the plurality of computing devices cause the plurality of computing devices to further implement:

upon recovery from failure of the storage client;

requesting from each of the plurality of protection groups one or more candidate log records for log recovery;

evaluating the received candidate log records to identify a recovery point in the log for the data volume according to the log sequence number space; and

making a view of the data available for access requests consistent with the recovery point in the log for the data volume.

19. The non-transitory, computer-readable storage medium of claim 18, wherein the program instructions when executed by the plurality of computing devices cause the plurality of computing devices to further implement:

receiving, at a protection group, the request for one or more candidate log records for log recovery; and

based, at least in part, on metadata indicating a previous log sequence number for each log record maintained at the protection group, selecting one or more log records to identify as the one or more candidate log records for log recovery from the protection group to be sent in response to the request.

20. The non-transitory, computer-readable storage medium of claim 15, wherein the recovery point indicates a range of log records in the log sequence number space, and wherein in said making the view of the data volume available for access requests consistent with the recovery point in the log for the data volume, the program instructions when executed by the plurality of computing devices cause the plurality of computing devices to implement excluding log records with log sequence numbers within the indicated range of log records from the log for the data volume.

21. The non-transitory, computer-readable storage medium of claim 15, wherein the storage client is a database, and wherein the log sequence number space for the data volume is the same as a log sequence number space for the database.