SYSTEM AND METHOD FOR LOG CONFLICT DETECTION AND RESOLUTION IN A DATA STORE

• US 20140244581A1
• Filed: 05/05/2014
• Published: 08/28/2014
• Est. Priority Date: 01/17/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: RATH, TIMOTHY ANDREW
• Granted Patent: US 10,248,704 B2
• Time in Patent Office: Days
• US Class Current: 707/623
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• 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 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A system that implements a data storage service may store data on behalf of storage service clients. The system may maintain data in multiple replicas that are stored on respective computing nodes in the system. Updates to the stored data and to the membership of replica groups are propagated as replicated log records. A replica receiving a log record may compare metadata in the received log record to corresponding metadata in a log record that was previously appended to its log to determine a response. The metadata may include a sequence number, a lock generation identifier, an epoch identifier, or an indication of an epoch change. The replica may append the received log record to its log, drop the received log record, or cache the received log record for future use. If a log conflict indicates an invalid log stream branch, one or more log records may be deleted.

Claims

1. A system, comprising:

a plurality of computing nodes, each comprising at least one processor and memory, wherein the plurality of computing nodes is configured to implement a data storage service;

wherein the data storage service maintains data on behalf of one or more storage service clients, wherein maintaining the data comprises storing two or more replicas of the data on respective computing nodes in the system, wherein the two or more replicas make up a replica group, wherein at most one of the replicas in the replica group can act as a master replica for the replica group at a time, and wherein replicas in the replica group that are not acting as the master replica act as slave replicas in the replica group;

wherein one of the replicas in the replica group is configured to;

receive a log record to be appended to a log maintained by the replica, wherein the log comprises a plurality of log records, wherein each log record indicates an update to the data being maintained on behalf of the storage service clients or an update to the membership of the replica group, and wherein each log record comprises metadata associated with the update or the replica group, wherein the metadata comprises;

a sequence number that was assigned to the log record when the log record was generated and that comprises a value in a strictly increasing series;

a lock generation identifier that indicates the acquisition of an external lock for the replica group, wherein the lock identifier value was fixed by the replica that generated the log record at a time when the replica that generated the log record was acting as master for the group and owned the external lock for the replica group;

an epoch identifier that was assigned to the log record when the log record was generated and that indicates that the log record was produced during a particular time period when a given replica was acting as master replica for the replica group;

or

an indication of an epoch change;

compare metadata in the received log record to metadata in a log record that was previously appended to the log;

determine an action to be taken in response to receiving the log record dependent on results of the comparison; and

take the determined action.

2. The system of claim 1, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is the log record that immediately follows the log record that was previously appended to the log in sequential order; and

in response to determining that the received log record is the log record that immediately follows the log record that was previously appended to the log in sequential order, determining that the replica should append the received log record to the log.

3. The system of claim 1, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is redundant in the log or has been superseded by another log record that was previously appended to the log; and

in response to determining that the received log record is redundant in the log or has been superseded by another log record that was previously appended to the log, determining that the replica should refrain from appending the received log record to the log.

4. The system of claim 1, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is a log record that follows the log record that was previously appended to the log and one or more other log records that have not yet been appended to the log in sequential order; and

in response to determining that the received log record is a log record that follows the log record that was previously appended to the log and one or more other log records that have not yet been appended to the log in sequential order, determining that the replica should not yet append the received log record to the log, but should cache the received log record for potential future use.

5. The system of claim 1, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether one or more log records in the log are on an invalid branch of the log; and

in response to determining that one or more log records in the log are on an invalid branch of the log;

determining that the replica should delete the one or more log records that are on an invalid branch from the log.

6. A method, comprising:

performing by a computer;

a replica in a replica group that comprises two or more replicas;

receiving a log record to be appended to a log maintained by the replica, wherein the log comprises a plurality of log records, wherein each log record comprises metadata associated with an update to be applied in the replica group, wherein the two or more replicas maintain data on respective computing nodes in a data store, wherein at most one of the replicas in the replica group can act as a master replica for the replica group at a time, and wherein replicas in the replica group that are not acting as the master replica act as slave replicas in the replica group;

comparing at least one element of the metadata in the received log record to a corresponding element of the metadata in a log record that was previously appended to the log, wherein the metadata comprises a lock generation identifier that indicates the acquisition of an external lock for the replica group, wherein the lock identifier value was fixed by the replica that generated the log record at a time when the replica that generated the log record was acting as master for the group and owned the external lock for the replica group, and wherein the metadata further comprises one or more of;

a sequence number that was assigned to the log record when the log record was generated, an epoch identifier that was assigned to the log record when the log record was generated, or an indication of an epoch change;

determining an action to be taken in response to receiving the log record dependent on results of the comparison; and

taking the determined action;

7. The method of claim 6, wherein each log record indicates an update to the data being maintained by the replica group or an update to the membership of the replica group.

8. The method of claim 6, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is the log record that immediately follows the log record that was previously appended to the log in sequential order; and

in response to determining that the received log record is the log record that immediately follows the log record that was previously appended to the log in sequential order, determining that the replica should append the received log record to the log.

9. The method of claim 6,

wherein one of the replicas in the replica group acts as master replica for the replica group at a time;

wherein said determining an action further comprises determining whether the received log record comprises an indication that there has been a change in mastership for the replica group; and

wherein the determined action is dependent on whether the received log record comprises an indication that there has been a change in mastership for the replica group.

10. The method of claim 6, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is redundant in the log or has been superseded by another log record that was previously appended to the log; and

in response to determining that the received log record is redundant in the log or has been superseded by another log record that was previously appended to the log, determining that the replica should refrain from appending the received log record to the log.

11. The method of claim 6, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether the received log record is a log record that follows the log record that was previously appended to the log and one or more other log records that have not yet been appended to the log in sequential order; and

in response to determining that the received log record is a log record that follows the log record that was previously appended to the log and one or more other log records that have not yet been appended to the log in sequential order, determining that the replica should not yet append the received log record to the log, but should cache the received log record for potential future use.

12. The method of claim 6, wherein said determining an action comprises:

determining, dependent on the results of the comparison, whether one or more log records in the log are on an invalid branch of the log; and

in response to determining that one or more log records in the log are on an invalid branch of the log, determining that the replica should delete the one or more log records that are on an invalid branch from the log.

13. The method of claim 12, further comprising:

subsequent deleting the one or more log records that are on an invalid branch, repeating said comparing the metadata, said determining an action, and said taking the determined action.

14. The method of claim 6, wherein the log record that was previously appended to the log comprises the log record that was most recently appended to the log.

15. The method of claim 6, wherein the received log record is received from a replica acting as master replica for the replica group.

16. The method of claim 6, wherein sequence numbers assigned by a given replica to log records are strictly increasing, and wherein said comparing comprises comparing the sequence number in the received log record to the sequence number in the log record that was previously appended to the log.

17. The method of claim 6, wherein said comparing comprises comparing the lock generation identifier in the received log record to the lock generation identifier in the log record that was previously appended to the log.

18. The method of claim 6, wherein the epoch identifier indicates that the log record was produced during a particular time period when a given replica was acting as master replica for the replica group, and wherein said comparing comprises comparing the epoch identifier in the received log record to the epoch identifier in the log record that was previously appended to the log.

19. The method of claim 6, wherein said determining an action is further dependent on the indication of an epoch change, and wherein in response to determining that the indication of an epoch change indicates an epoch change, said comparing further comprises comparing a previous lock generation identifier associated with the received log record to a previous lock generation identifier associated with the log record that was previously appended to the log.

20. The method of claim 6, wherein comparing the metadata comprises determining whether a component of the metadata in the received log record is equal to, less than, one greater than, or more than one greater than a corresponding component of the metadata in the log record that was previously appended to the log.

21-35. -35. (canceled)