Data replication protocol with efficient update of replica machines
First Claim
1. A method of updating replica machines that are connected to a leader machine, the method comprising:
- maintaining, by each of the replica machines, an operation log, each log entry in each operation log including an operation log number, a key, and an operation performed on the key, the operation log sorted by operation log number;
assigning, by the leader machine, a monotonically increasing operation log number to an operation command;
receiving by the replica machines the operation command and operation log number assigned to the operation command from the leader machine to operate on the operation logs of the replica machines;
operating by the replica machines on the operation command;
inserting, into the operation log of each of the replica machines, a new log entry, the new log entry including the operation log number assigned to the operation command, a key specified in the operation command, and an operation to perform on the key specified in the operation command;
updating a secondary index of each of the replica machines, the secondary index sorted by keys; and
updating an operation log of a first replica machine based on an operation log of the leader machine by;
iteratively inserting, into the operation log of the first replica machine, those log entries in the tail end of the operation log of the leader machine that are missing in the operation log of the first replica machine; and
for each log entry being iteratively inserted into the operation log of the first replica machine, performing by the first replica machine an operation included in the said log entry being iteratively inserted into the operation log of the first replica machine.
13 Assignments
0 Petitions
Accused Products
Abstract
Steady state data distribution is provided between a client application, a leader machine, and a plurality of replica machines. The distribution comprises the leader machine receiving an operation request from the client application, the leader machine sending the prepare message to each of the plurality of replica machines, the replica machines recording in their logs information on the operation, the replica machines sending acknowledgement messages to the leader machine, and the leader machine sending commit command messages to the replica machines. A new quorum of the replica machines is created by using log information. Replica machines that become part of the new quorum are updated in an efficient manner.
17 Citations
31 Claims
-
1. A method of updating replica machines that are connected to a leader machine, the method comprising:
-
maintaining, by each of the replica machines, an operation log, each log entry in each operation log including an operation log number, a key, and an operation performed on the key, the operation log sorted by operation log number; assigning, by the leader machine, a monotonically increasing operation log number to an operation command; receiving by the replica machines the operation command and operation log number assigned to the operation command from the leader machine to operate on the operation logs of the replica machines; operating by the replica machines on the operation command; inserting, into the operation log of each of the replica machines, a new log entry, the new log entry including the operation log number assigned to the operation command, a key specified in the operation command, and an operation to perform on the key specified in the operation command; updating a secondary index of each of the replica machines, the secondary index sorted by keys; and updating an operation log of a first replica machine based on an operation log of the leader machine by; iteratively inserting, into the operation log of the first replica machine, those log entries in the tail end of the operation log of the leader machine that are missing in the operation log of the first replica machine; and for each log entry being iteratively inserted into the operation log of the first replica machine, performing by the first replica machine an operation included in the said log entry being iteratively inserted into the operation log of the first replica machine. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A method of updating a plurality of replica machines connected to a leader machine, wherein each replica machine comprises its own tree structure having four levels, further wherein a first level comprises a root node, a second level comprises interior nodes stemming from the root node, wherein the interior nodes are themselves organized into a tree, a third level comprises leaf nodes stemming from the interior nodes, and a fourth level comprises data stores stemming from the leaf nodes, the method comprising:
-
sending by the leader machine operation commands to the replica machines, wherein each operation command comprises an operation, a key, a monotonically increasing operation log number assigned to the operation command by the leader machine, and data; receiving, by each of the replica machines, the operation command; and updating, by each of the replica machines, its own tree structure according to the received operation command; updating a tree structure of a first replica machine based on a tree structure of the leader machine by; decomposing, into sub-ranges, a range of key values stored in the tree structure of the first replica machine, each sub-range having its own maximum operation log number; and for each sub-range, recursively comparing and updating a maximum operation log number in the sub-range with a maximum operation log number in a corresponding sub-range of key values stored in the tree structure of the leader machine; wherein each replica machine constructs and maintains its own tree structure. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
Specification