Patent ID: 9230000
Filing Date: 2016-01-05
CPC Classification: G06F,H04L

Claim Text:
1. A method of pipelining Paxos transactions in a distributed database comprising a plurality of replica servers at a plurality of distinct geographic locations, each replica server having one or more processors and memory, the method comprising: selecting a leader server from the plurality of replica servers, wherein the leader server is selected by a consensus of the replica servers; allocating a finite sequence of Paxos log numbers for a current epoch, wherein a lowest Paxos log number in the finite sequence is greater than a highest Paxos log number allocated in previous epochs; establishing a leadership lock assigned to the leader server for the current epoch, wherein the leadership lock precludes any non-leader replica server from constructing proposed write transactions; receiving a first database write request at the leader server; assigning a first Paxos log number to the first database write request, the first Paxos log number being selected from the finite sequence of Paxos log numbers for the current epoch; constructing a first proposed write transaction that includes the first Paxos log number and incorporates the first received write request; transmitting the first proposed write transaction to at least a plurality of the non-leader replica servers; receiving a second database write request at the leader server, wherein the second write request and the first write request access distinct objects in the distributed database; assigning a second Paxos log number to the second database write request, wherein the second Paxos log number is selected from the finite sequence of Paxos log numbers for the current epoch and is distinct from the first Paxos log number; constructing a second proposed write transaction that includes the second Paxos log number and incorporates the second received write request; transmitting the second proposed write transaction to at least a plurality of the non-leader replica servers prior to committing the first proposed write transaction; committing the first and second proposed write transactions after receiving a plurality of confirmations for the first and second proposed write transactions from the replica servers; and after all of the finite sequence of Paxos log numbers have been assigned to Paxos write transactions, performing one or more inter-epoch tasks prior to allocating additional Paxos log numbers for a subsequent epoch.