Chaining log operations in data replication groups

• US 10,489,230 B1
• Filed: 12/02/2015
• Issued: 11/26/2019
• Est. Priority Date: 12/02/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Chen, Tao, Zulak, Matthew Joseph, Pallikila, Lakshmi N., Agrawal, Shobha, Ping, Fan, Jain, Divya Ashok Kumar
• Primary Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US14/957,468
• Time in Patent Office: 1,455 Days
• CPC Class Codes: G06F 11/0778 Dumping, i.e. gathering error/state information after a fault for later diagnosis
• CPC Class Codes: G06F 11/0781 Error filtering or prioritizing based on a policy defined by the user or on a policy defined by a hardware/software module, e.g. according to a severity level
• CPC Class Codes: G06F 11/0787 Storage of error reports, e.g. persistent data storage, storage using memory protection

Abstract

Data replication groups may be used to store data in a distributed computing environment. The data replication groups may include a set of nodes executing a consensus protocol to maintain data durably. In order to monitor and debug the operation of the data replication group a chaining mechanism may be utilized during log creation by the set of nodes of the data replication group. The chaining mechanism may cause entries in the log to indicate an operation being performed and an operation performed immediately prior to the operation being performed. In various embodiments, an outside observer receives the logs and checks the logs for errors indicated by the chaining mechanism.

Claims

1. A computer-implemented method, comprising:

receiving, at a first node of a data replication group, a message from a second node of the data replication group, where the data replication group comprises a plurality of nodes implementing a consensus protocol;

determining to commit an operation to the first node, where the operation is indicated in the message;

obtaining an operation number corresponding to the operation;

obtaining a previous operation number corresponding to a previous operation committed immediately prior to the operation;

recording the operation number and the previous operation number in a log entry such that the log entry indicates that the first node committed the previous operation immediately prior to the operation in error, wherein the error indicates that a gap exists between the operation number and the previous operation number in the log entry; and

determining validity of the gap and other gaps in a log that comprises the log entry and other log entries by using state information of the node and state information of the data replication group.

2. The computer-implemented method of claim 1, further includes providing the log to a client.

3. The computer-implemented method of claim 2, wherein the computer-implemented method further includes detecting an error performed by the first node based at least in part on the log entry and one or more other log entries generated by plurality of nodes of the data replication group.

4. The computer-implemented method of claim 3, wherein the client is further configured to transmit an alarm to a replication group service as a result of detecting the error.

5. A system, comprising:

one or more processors; and

memory that includes instructions that, when executed by the one or more processors, cause the system to;

receive a message from a node of a data replication group, the data replication group including one or more nodes implementing a consensus protocol;

obtain an operation number associated with a performed operation and a previous operation number associated with a previously performed operation;

determine whether the operation number and the previous operation number in a log entry of a log is valid based at least in part on analyzing whether one or more gaps in the log entries in the data replication group exists; and

mitigate errors to the one or more gaps in the log entries in the data replication group.

6. The system of claim 5, wherein the memory further includes instructions that, when executed by the one or more processors, cause the system to obtain the log such that the log is processed and made available to an event stream.

7. The system of claim 6, wherein the memory further includes instructions that, when executed by the one or more processors, cause the system to delete entries in the log as a result of a command from a log collector.

8. The system of claim 5, wherein:

the system further comprises a computer system configured to detect errors in an implementation of the data replication group; and

the memory further includes instructions that, when executed by the one or more processors, cause the system to transmit the log to the computer system.

9. The system of claim 5, wherein:

the memory further includes instructions that, when executed by the one or more processors, cause the system to transmit a first proposal to one or more other nodes of the data replication group; and

receiving the message further comprises receiving a second proposal indicating an operation to be performed.

10. The system of claim 5, wherein the operation number further comprises a value relative to the data replication group and is configured to increase with each performed operation of the data replication group.

11. The system of claim 5, wherein recording the operation number further comprises recording the operation number in a linked list in the log entry, such that the operation number is linked to the previous operation number.

12. The system of claim 5, wherein the memory further includes instructions that, when executed by the one or more processors, cause the system to separate the log into a plurality of segments indicating operations performed by the system.

13. A non-transitory computer-readable storage medium comprising thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

obtain a log generated by a node of a data replication group, the data replication group comprising one or more nodes implementing a consensus protocol;

determine a set of operations performed by the node based at least in part on the log;

detect a gap in the set of operations, where the gap in the set of operations is indicated by a chaining mechanism utilized to generate log entries of the log;

determine a validity of the gap based at least in part on a first operation performed by the node indicated by a log entry of the log and a previous operation performed by the node indicated by the log entry of the log by at least comparing state information of the node with state information of the data replication group;

detect a second gap in the set of operations, where the second gap in the set of operations is detected based at least in part on a chaining mechanism utilized, by the node, to generate log entries of the log;

determine that the detected second gap is a valid operation of the data replication group based at least in part on the log entries of the log; and

transmit a notification indicating information about the gap and the second gap.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to determine additional information associated with the detected gap in the set of operations, where the additional information indicates at least a cause for the detected gap in the set of operations.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to provide the additional information for remediating errors occurring in the data replication group.

16. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

aggregate a set of logs from a set of nodes of the data replication group.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to determine the validity of the gap and the second gap based at least in part on information from the aggregated set of logs.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine the validity of the gap further include instructions that cause the computer system to determine that the gap is an error as a result of the node not performing one or more operations prior to performing the first operation indicated by the chaining mechanism.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine the validity of the gap further include instructions that cause the computer system to determine that the gap is a result of a delay in providing the log or dropping the log.

20. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to transmit the notification further include instructions that cause the computer system to transmit the notification to a replication group service responsible for management of the data replication group.

21. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine the validity of the gap further include instructions that cause the computer system to apply a catchup algorithm that enables the node to compare the state information of the node with the state information of the data replication group and determine whether the state information of the node matches the state information of the data replication group.