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

摘要

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.

主权项

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; oran 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; andtake the determined action.