READ-ONLY OPERATIONS PROCESSING IN A PAXOS REPLICATION SYSTEM

• US 20140181026A1
• Filed: 03/03/2014
• Published: 06/26/2014
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Haagens, Randolph B., Kusters, Norbert P., Li, Peng
• Granted Patent: US 9,852,204 B2
• Time in Patent Office: Days
• US Class Current: 707/634
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30

Abstract

Embodiments are directed to processing read-only operations without storing the operations persistently, determining a processing order for read-only requests, and to directing read-only requests to nodes best able to handle the requests. In an embodiment, a quorum leader receives various read-only requests. The quorum leader controls process ordering for replicas in the leader'"'"'s quorum. The quorum leader determines an appropriate order for processing the read-only operations, without clock-based synchronization. The quorum leader sends the read-only request to an appropriate replica in the quorum and executes the read-only request at the appropriate replica without storing the operation persistently.

Claims

1. A computing system for managing replication and storage of data by processing read-only operations without storing the operations persistently in a distributed computer system being operated under a Paxos-type protocol, the system comprising:

one or more processors;

one or more computer-readable storage media coupled to the one or more processors, and having stored thereon computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform the following;

in a distributed computing system, identifying a plurality of computer systems that serve as quorum members for storing replication data, and identifying one of the quorum members as a quorum leader designated to control process ordering for data to be replicated and stored among the quorum members;

the quorum leader receiving a read-only request;

the quorum leader determining an appropriate order defined by a determined execution slot for processing the read-only request, the quorum leader determining the appropriate order without clock-based synchronization by performing the following;

determining a highest write request that is committed in sequence by reason of at least half the quorum members having logged the write request and having agreed to put the write request in the execution slot; and

the quorum leader noting that the highest write request has been committed in sequence by at least half the quorum members;

the quorum leader determining that one of the quorum members should serve as an appropriate replica that is determined to be best able to process the received read-only request;

the quorum leader sending the read-only request to the determined appropriate replica; and

executing the read-only request at the determined appropriate replica by processing a read-only operation of the request without storing the operation persistently.

2. The system of claim 1, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to send the results of the executed read-only request to a computer user.

3. The system of claim 1, wherein the determined processing order further indicates an appropriate execution slot number for the read-only operation.

4. The system of claim 3, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to send the determined execution slot number to the determined appropriate replica in the quorum.

5. The system of claim 3, wherein determining the appropriate processing order comprises identifying the greater of the highest slot number that the quorum leader has committed in sequence and the highest operation number that a previous quorum leader proposed.

6. The system of claim 3, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to add an indication to the read-only operation indicating that the operation is to be executed no earlier than the determined execution slot number.

7. The system of claim 1, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to send a message to the quorum members to determine whether the quorum members have recognized a new leader.

8. The system of claim 7, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to determine that at least half of the quorum member, including the quorum leader, have replied that the quorum members still recognize the quorum leader as the leader of the quorum.

9. The system of claim 7, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform the following:

determine that the quorum members do not recognize the quorum leader as the leader of the quorum;

discard the read-only request; and

indicate to the user that the user is to re-send the read-only request to a new quorum leader.

10. The system of claim 1, wherein determining an appropriate order for processing the read-only operations identifies and implements disk-efficiency factors.

11. The system of claim 1, wherein the quorum leader determines several quorum members that are best able to handle the read-only request and sends the read-only request to those quorum members.

12. A computing system for managing replication and storage of data by processing read-only operations without storing the operations persistently in a distributed computer system being operated under a Paxos-type protocol, the system comprising:

one or more processors;

one or more computer-readable storage media coupled to the one or more processors, and having stored thereon computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform the following;

in a distributed computing system, identifying a plurality of computer systems that serve as quorum members for storing replication data, and identifying one of the quorum members as a quorum leader designated to control process ordering for data to be replicated and stored among the quorum members;

the quorum leader receiving a read-only request;

the quorum leader determining an appropriate order defined by a determined execution slot for processing an operation for the read-only request, the quorum leader determining the appropriate order without clock-based synchronization by performing the

determining a highest write request that is committed in sequence by reason of at least half the quorum members having logged the write request and having agreed to put the write request in the execution slot; and

the quorum leader noting that the highest write request has been committed in sequence by at least half the quorum members;

the quorum leader adding a no-earlier-than indication to the operation for the read-only request indicating that the operation is to be executed no earlier than the determined execution slot number;

the quorum leader determining that one of the quorum members should serve as an appropriate replica that is determined to be best able to process the read-only request;

the quorum leader sending the read-only request and the determined execution slot number and no-earlier-than indication to the appropriate replica; and

executing the read-only request at the determined appropriate replica by processing the operation for the read-only request, based on the slot number and the no-earlier-than indication, and without storing the operation persistently.

13. The system of claim 12, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the quorum leader to a message to the quorum members determine whether a new quorum leader has been recognized.

14. The system of claim 13, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to determine that at least half of the quorum members including the quorum leader have replied that the quorum members still recognize the quorum leader as the leader of the quorum.

15. The system of claim 13, the one or more computer-readable storage media further comprising computer-executable instructions that, when executed by the one or more processors, causes the computing system to:

determine that the quorum members do not recognize the quorum leader as the leader of the quorum;

discard the read-only request; and

indicate to the user that the user is to re-send the read-only request to a newly recognized quorum leader.

16. A computing system for managing replication and storage of data by processing read-only operations without storing the operations persistently in a distributed computer system being operated under a Paxos-type protocol, the system comprising:

one or more processors;

one or more computer-readable storage media coupled to the one or more processors, and having stored thereon computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform the following;

in a distributed computing system, identifying a plurality of computer systems that serve as quorum members for storing replication data, and identifying one of the quorum members as a quorum leader designated to control process ordering for data to be replicated and stored among the quorum members;

the quorum leader receiving a read-only request;

the quorum leader determining an appropriate order defined by a determined execution slot for processing an operation for the read-only request, the quorum leader determining the appropriate order without clock-based synchronization by performing the

determining a highest write request that is committed in sequence by reason of at least half the quorum members having logged the write request and having agreed to put the write request in the execution slot; and

the quorum leader noting that the highest write request has been committed in sequence by at least half the quorum members;

the quorum leader adding a no-earlier-than indication to the operation for the read-only request indicating that the operation is to be executed no earlier than the determined execution slot number;

the quorum leader determining that one of the quorum members should serve as an appropriate replica that is determined to be best able to process the read-only request;

the quorum leader then sending messages to the quorum members to determine whether the quorum members have recognized a new quorum leader, and

if not, sending the read-only request and the determined execution slot number and no-earlier-than indication to the appropriate replica, and then executing the read-only request at the determined appropriate replica by processing the read-only operation of the request, based on the slot number and the no-earlier-than indication, and without storing the operation persistently; and

if so, discarding any pending read-only request and the quorum leader then acting as a regular quorum member.

17. The system of claim 16, wherein determining which quorum member is best able to handle the read-only request comprises determining which quorum members are currently writing data to disk.

18. The system of claim 16, wherein determining which quorum member is best able to handle the read-only request comprises determining which quorum members currently have a desired memory value in memory.

19. The system of claim 16, wherein determining which quorum members is best able to handle the read-only request comprises determining which quorum member has at least one of a lower network and a lower processor load than the other replicas.