System and method for log conflict detection and resolution in a data store

• US 10,248,704 B2
• Filed: 05/05/2014
• Issued: 04/02/2019
• 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
• Primary Examiner(s): Hutton, Nan
• Application Number:
  US14/270,323
• Publication Number:
  US 20140244581A1
• Time in Patent Office: 1,793 Days
• 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 that receive log records from the master replica, 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; and

a master reign identifier indicating a reign of a particular master replica over the replica group when the log record was generated;

compare metadata for the received log record to metadata for one or more other log records in the log to determine a conflict in master reign between the received log record and the one or more other log records;

determine an action to be taken in response to receiving the log record dependent on results of the comparison, wherein the action resolves the determined conflict; 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 a log record that immediately follows a 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 a 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;

receiving, by a replica in a replica group that comprises two or more replicas, 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, by the replica, at least one element of the metadata for the received log record to a corresponding element of the metadata for a log record that was previously appended to the log, wherein the comparing determines whether a conflict in master reign exists between the received log record and one or more log records that were previously appended to the log, and wherein the metadata comprises a master reign identifier indicating a reign of a particular master replica over the replica group when the log record was generated and a sequence number that was assigned to the log record when the log record was generated;

determining, by the replica, an action to be taken in response to receiving the log record dependent on results of the comparison, wherein the action resolves any determined conflict; and

taking, by the replica, 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 a 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 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 the received log record is received from a replica acting as master replica for the replica group.

13. 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.

14. The method of claim 6, wherein the master reign identifier comprises a lock generation identifier that was fixed by the particular master replica that generated the log record at a time when the particular master owned an external lock for the replica group, and wherein said comparing comprises comparing the lock generation identifier in the received log record to a lock generation identifier in the log record that was previously appended to the log.

15. The method of claim 6, wherein the master reign identifier comprises an epoch identifier that indicates that the log record was produced during a particular time period when the particular master 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 an epoch identifier in the log record that was previously appended to the log.

16. The method of claim 6, wherein the metadata for the received log includes an indication of an epoch change, and wherein 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 in response to determining that the indication indicates an epoch change.

17. 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.

18. A non-transitory computer-readable storage medium storing program instructions that if executed on one or more computers cause the one or more computers to perform:

receiving, at replica in a replica group that comprises two or more replicas, 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 for the received log record to a corresponding element of the metadata for a log record that was previously appended to the log, wherein the comparing determines whether a conflict in master reign exists between the received log record and one or more log records that were previously appended to the log, and wherein the metadata comprises a master reign identifier indicating a reign of a particular master replica over the replica group when the log record was generated and a sequence number that was assigned to the log record when the log record was generated;

determining an action to be taken in response to receiving the log record dependent on results of the comparison, wherein the action resolves any determined conflict; and

taking the determined action.

19. The non-transitory computer-readable storage medium of claim 18, wherein the log record that was previously appended to the log comprises a log record that was most recently appended to the log.

20. The non-transitory computer-readable storage medium of claim 18, wherein the received log record is received from a replica acting as master replica for the replica group.