Unsupervised round robin catch up algorithm

• US 10,567,499 B1
• Filed: 12/02/2015
• Issued: 02/18/2020
• 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): Harrell, Robert B
• Application Number:
  US14/957,477
• Time in Patent Office: 1,539 Days
• Field of Search: 709219, 714 15, 714 20
• 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/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/0775 Content or structure details of the error report, e.g. specific table structure, specific error fields
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 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]

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. During the execution of the set of nodes various nodes may become stale or otherwise obtain a state that is inconsistent with at least one other node of the data replication group. A catch up algorithm may be employed in which a set of teachers is initialized, the various node which may be stale may select a teacher from the set of teachers and perform learning operations. This process may be repeated until the state of the various nodes is current with at least one other node of the data replication group.

Claims

1. A non-transitory computer-readable storage medium having stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to:

initialize a set of nodes of a data replication group;

determine that one or more nodes of the set of nodes are stale;

initialize a set of teachers with information associated with the set of nodes that are current;

for each node of the determined one or more nodes, selecting a teacher from the set of teachers corresponding to a particular node of the set of nodes; and

until determining that the one or more nodes of the set of nodes are current, iteratively perform a learning operation to obtain state information from the set of teachers.

2. The non-transitory computer-readable storage medium of claim 1, wherein the executable instructions that cause the computer system to perform the learning operation further include instructions that cause the computer system to copy a state of the particular node of the data replication group associated with the teacher.

3. The non-transitory computer-readable storage medium of claim 2, wherein the executable instructions that cause the computer system to copy the state of the particular node further include instructions that cause the computer system to copy the state by at least obtaining a snapshot of the particular node and copying the snapshot to a memory.

4. The non-transitory computer-readable storage medium of claim 1, wherein the executable instructions that cause the computer system to perform the learning operation further include instructions that cause the computer system to obtain a log from a particular node of the data replication group associated with the teacher, where the log indicates operations performed by the data replication group.

5. The non-transitory computer-readable storage medium of claim 1, wherein the executable instructions further comprise instructions that, if executed by the one or more processors, cause the computer system to determine one or more additional nodes of the set of nodes are stale and for each node of the determined one or more additional nodes selecting a second teacher from the set of teachers and performing a second learning operation.

6. The non-transitory computer-readable storage medium of claim 1, wherein the executable instructions further comprise instructions that, if executed by the one or more processors, cause the computer system to remove the teacher from the set of teachers.

7. The non-transitory computer-readable storage medium of claim 1, wherein the executable instructions that cause the computer system to initialize the set of teachers further include instructions that cause the computer system to initialize the set of teachers with information corresponding to a second set of nodes of the data replication group, where the second set of nodes includes at least one node that is not a member of the set of nodes and was added to the data replication group after initialization.

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

add a new node to the data replication group;

select a new teacher from the set of teachers; and

perform a new learning operation with the new teacher and the new node.

9. A system, comprising:

one or more processors; and

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

detect that a state of the system is stale based at least in part on information obtained from at least one node of a set of nodes of a data replication group;

initialize a set of teachers corresponding to a set of other nodes of the data replication group, where the set of teachers includes information that enables the system to obtain state information from the set of teachers; and

until determining that the state of the system is current, iteratively perform a non-redundant catch up algorithm to update the state of the system by at least;

selecting a first teacher from the set of teachers corresponding to a particular node of the set of nodes; and

obtaining state information from the first teacher to update the state of the system.

10. The system of claim 9, wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to cause the data replication group to implement a consensus protocol.

11. The system of claim 10, wherein the consensus protocol is a Paxos consensus protocol.

12. The system of claim 9, wherein the memory further includes instructions that, if executed by the one or more processors, cause the system to remove the first teacher from the set of teachers after obtaining the state information from the first teacher.

13. The system of claim 9, wherein detecting that the state of the system is stale further comprises determining that a heartbeat message from the at least one other node of the set of nodes of the data replication group has not been received after an expiration of an interval of time.

14. The system of claim 9, wherein initializing the set of teachers further comprises initializing the set of teachers to an initial set of nodes of the data replication group, where the initial set of nodes corresponds to nodes of the data replication group included in the data replication group during generation of the data replication group.

15. The system of claim 9, wherein initializing the set of teachers further comprises initializing the set of teachers to a current set of nodes of the data replication group, where the current set of nodes correspond to nodes of the data replication group included in the data replication group at a point in time of initializing the set of teachers.

16. A computer-implemented method, comprising:

initializing a data replication group with a plurality of nodes implementing a consensus protocol;

detecting that a state of a node of the plurality of nodes has yet to advance to a state of at least one other node of the plurality of nodes of the data replication group;

initializing, by the node, a set of teachers, wherein the set of teachers includes information that enable the node to obtain information from the set of teachers; and

until determining that the state of the node has advanced to the state of the at least one other node of the plurality of nodes of the data replication group, iteratively performing, by the node, a non-redundant catch up algorithm to update the state of the node comprising;

selecting a teacher from the set of teachers, the teacher corresponding to a particular node of the plurality of nodes;

obtaining update information from the teacher; and

updating the state of the node in accordance with the update information.

17. The computer-implemented method of claim 16, wherein performing the non-redundant catch up algorithm to update the state of the node further comprises:

detecting that the state of the node has yet to advance to the state of the at least one other node of the plurality of nodes of the data replication group;

removing the teacher from the set of teachers such that the particular node is no longer included in the set of teachers;

selecting a second teacher from the set of teachers;

obtaining second update information from the second teacher; and

updating the state of the node in accordance with the second update information.

18. The computer-implemented method of claim 16, wherein initializing the set of teachers further comprises initializing the set of teachers with information corresponding to an initial membership of the data replication group.

19. The computer-implemented method of claim 16, wherein initializing the set of teachers further comprises initializing the set of teachers with information corresponding to a current membership of the data replication group.

20. The computer-implemented method of claim 16, wherein the consensus protocol is a Paxos consensus protocol.