Read-only operations processing in a paxos replication system

Patent metadata

Field	Value
Publication number	US-9852204-B2
Application number	US-201414195495-A
Country	US
Kind code	B2
Filing date	Mar 3, 2014
Priority date	Mar 18, 2011
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

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.

First claim

What is claimed is:

1. A computing system comprising at least one quorum leader for managing replication and storage of data by processing read-only operations, without storing the operations persistently, in a distributed computer system, the distributed computer system being operated under a Paxos-type protocol and including the quorum leader and one or more quorum members, 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:
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 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 selecting one of the quorum members to serve as an appropriate replica which is determined to process the received read-only request; and
the quorum leader sending the read-only request and the determined execution slot number and no-earlier-than indication to the determined appropriate replica causing the determined appropriate replica to execute the read-only request by processing a read-only operation of the request, based on the determined execution slot number and the no-earlier-than indication, at an execution slot that is later than the determined execution slot number, and 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 are executable by the one or more processors to cause 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 , 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.

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

6. The system of claim 5 , the one or more computer-readable storage media further comprising computer-executable instructions that are executable by the one or more processors to cause 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.

7. The system of claim 5 , the one or more computer-readable storage media further comprising computer-executable instructions that are executable by the one or more processors to cause 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.

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

9. 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.

10. A method, implemented at a computer system that includes one or more processors, for managing replication and storage of data by processing read-only operations, without storing the operations persistently, the method comprising:
receiving a read-only request;
determining an appropriate order defined by a determined execution slot for processing an operation for the read-only request;
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;
determining one of the plurality of quorum members to serve as an appropriate replica which is determined to be best able to process the received read-only request;
sending the read-only request and the determined execution slot and no-earlier-than indication to the appropriate replica, causing the read-only request to be executed at the determined appropriate replica by processing the operation for the read-only request, based on the slot and the no-earlier-than indication, at an execution slot that is later than the determined execution slot number, and without storing the operation persistently.

11. The method of claim 10 , the one or more computer-readable storage media further comprising computer-executable instructions that are executable by the one or more processors to cause the quorum leader to a message to the quorum members determine whether a new quorum leader has been recognized.

12. The method of claim 11 , the one or more computer-readable storage media further comprising computer-executable instructions that are executable by the one or more processors to cause 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.

13. The method of claim 11 , the one or more computer-readable storage media further comprising computer-executable instructions that are executable by the one or more processors to cause 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.

14. A computing system comprising at least one quorum leader for managing replication and storage of data by processing read-only operations, without storing the operations persistently, in a distributed computer system, the distributed computer system being operated under a Paxos-type protocol and including the quorum leader and one or more quorum members, the system comprising:
one or more processors; and
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:
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 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, wherein the operation is executed after the operation is committed, and wherein the operation is committed when at least half of the quorum members have both logged the operation and agreed to put the read-only request in the execution slot;
the quorum leader determining one of the quorum members to serve as an appropriate replica which is determined to be best able to process the r

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Bolosky William J
• Haagens Randolph B
• Kusters Norbert P
• Li Peng

Classifications

• G06F9/5038 Primary

  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 title

• G06F17/30581 Primary

  Physics · mapped topic

• H04L67/1008

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• G06F16/275 Primary

  Synchronous replication · CPC title