Leasing scheme for data-modifying operations

• US 7,065,618 B1
• Filed: 06/30/2003
• Issued: 06/20/2006
• Est. Priority Date: 02/14/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Gobioff, Howard, Leung, Shun-Tak
• Primary Examiner(s): Elmore, Stephen C.
• Application Number:
  US10/608,136
• Time in Patent Office: 1,086 Days
• Field of Search: 711/161, 711/154, 711/114, 711/112, 711/4, 707/201, 707/203
• US Class Current: 711/161
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• 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 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system may facilitate performance of a data-modifying operation in a file network that includes multiple servers that store replicas of data. One of the servers may serve as a primary replica for one of the replicas of data and at least one other one of the servers may serve as at least one secondary replica for the replica of data. The system may send data associated with the data-modifying operation to the primary replica and the at least one secondary replica based on a network topology and independently send a data-modifying control signal that requests execution of the data-modifying operation using the data associated with the data-modifying operation to the primary replica and the at least one secondary replica.

Claims

1. A method for performing a data-modifying operation in a file system that includes a plurality of servers that store replicas of data, one of the servers serving as a primary replica server for one of the replicas of data and at least one other one of the servers serving as at least one secondary replica server for the one replica of data, the method comprising:

sending data associated with the data-modifying operation to the primary replica server and the at least one secondary replica server; and

sending a data-modifying control signal that requests execution of the data-modifying operation on the data associated with the data-modifying operation to the primary replica server and the at least one secondary replica server,

where a sequence in which the data associated with the data-modifying operation is received at each of the primary replica server and the at least one secondary replica server is independent of a sequence in which the data-modifying control signal is received at each of the primary replica server and the at least one secondary replica server.

2. The method of claim 1, wherein the sending data associated with the data-modifying operation includes:

pushing the data to one of the primary replica server or the at least one secondary replica server that is closest in a network topology to a sender of the data, the one of the primary replica server or the at least one secondary replica server serving as a closest replica server.

3. The method of claim 2, wherein the sending data associated with the data-modifying operation further includes:

forwarding the data from the closest replica server to one of the primary replica server and the at least one secondary replica server that is closest in the network topology to the closest replica server.

4. The method of claim 3, wherein the sending data associated with the data-modifying operation further includes:

continuing to forward the data based on the network topology until all of the primary replica server and the at least one secondary replica server have received the data.

5. The method of claim 1, wherein the sending data associated with the data-modifying operation includes:

pipelining transmission of the data to the primary replica server and the at least one secondary replica server.

6. The method of claim 5, wherein the pipelining transmission of the data includes:

receiving the data at one of the primary replica server or the at least one secondary replica server, and

while receiving the data at the one of the primary replica server or the at least one secondary replica server, forwarding the data to another one of the primary replica server or the at least one secondary replica server.

7. The method of claim 1, wherein the sending a data-modifying control signal includes:

receiving the data-modifying control signal at the primary replica server from a sender of the data-modifying control signal, and

forwarding the data-modifying control signal to the at least one secondary replica server.

8. The method of claim 1, wherein the at least one secondary replica server includes a plurality of secondary replica servers;

and

wherein the method further comprises;

assigning serial numbers to the secondary replica servers that define an order in which the secondary replica servers perform the data-modifying operation.

9. The method of claim 1, further comprising:

reporting that the data-modifying operation is successful when the data-modifying operation is successfully executed at the primary replica server and the at least one secondary replica server.

10. The method of claim 1, wherein the file system further includes a master;

and

wherein the method further comprises;

granting a lease to one of the servers that stores the one replica of data, the one server thereafter being the primary replica server.

11. The method of claim 10, wherein the lease has an initial timeout period.

12. The method of claim 11, wherein the initial timeout period is extendable.

13. The method of claim 10, further comprising:

receiving, by the master, a request for identification of the primary replica server and the at least one secondary replica server; and

sending, by the master, a reply that identifies locations of the primary replica server and the at least one secondary replica server.

14. A system for performing a data-modifying operation in a file network that includes a plurality of servers that store replicas of data, one of the servers serving as a primary replica server for one of the replicas of data and other ones of the servers serving as secondary replica servers for the one replica of data, the system comprising:

means for pushing data associated with the data-modifying operation to the primary replica server and the secondary replica servers; and

means for sending a data-modifying control signal to the primary replica server and the secondary replica servers, the data-modifying control signal requesting execution of the data-modifying operation on the data associated with the data-modifying operation,

where the data associated with the data-modifying operation is pushed to the primary replica server and the secondary replica servers in an order independent of an order in which the data-modifying control signal is sent to the primary replica server and the secondary replica servers.

15. A file system, comprising:

a primary replica server configured to store a replica of data; and

at least one secondary replica server configured to also store the replica of data, the primary replica server and the at least one secondary replica server in combination being configured to;

receive data associated with a data-modifying operation at one of the primary replica server or the at least one secondary replica server that is closest to a sender of the data,

forward the data to another one of the primary replica server or the at least one secondary replica server from the one of the primary replica server or the at least one secondary replica server that is closest to the sender of the data,

receive, at the primary replica server, a data-modifying control signal that requests execution of the data-modifying operation on the data associated with the data-modifying operation, and

forward the data-modifying control signal to the at least one secondary replica server from the primary replica server.

16. A method for performing a data-modifying operation in a file system that includes a plurality of servers that store replicas of data, one of the servers serving as a primary replica server for one of the replicas of data and other ones of the servers serving as secondary replica servers for the one replica of data, the method comprising:

receiving data associated with the data-modifying operation at the primary replica server or one of the secondary replica servers;

forwarding the data from the primary replica server or one of the secondary replica servers to other ones of the primary replica server or the secondary replica servers;

receiving, at the primary replica server, a data-modifying signal that requests execution of the data-modifying operation on the data associated with the data-modifying operation, the primary replica server receiving the data-modifying signal independently of the data; and

forwarding the data-modifying signal to the secondary replica servers.

17. A file system, comprising:

a plurality of servers configured to store replicas of data; and

a master connected to the servers and configured to;

receive a request for identification of the servers that store a replica of data,

determine whether one of the servers has a lease for the replica of data,

identify the one server as a primary replica server when the one server has a lease for the replica of data,

identify other ones of the servers, as secondary replica servers, that store the replica of data, and

send a reply that identifies locations of the primary replica server and the secondary replica servers.

18. The system of claim 17, wherein the master is further configured to grant a lease to one of the servers that stores the replica of data when none of the servers has a lease for the replica of data.

19. The system of claim 17, wherein the primary replica server is configured to assign serial numbers to the secondary replica servers that define an order in which the secondary replica servers perform a data-modifying operation associated with the replica of data.

20. The system of claim 17, wherein the lease has an initial timeout period.

21. The system of claim 20, wherein the initial timeout period is extendable.

22. A file system that includes a plurality of servers that store replicas of data, one of the servers serving as a primary replica server for one of the replicas of data and other ones of the servers serving as secondary replica servers for the one replica of data, the file system comprising:

means for sending data associated with a data-modifying operation from a client to the primary replica server and the secondary replica servers in a first sequence; and

means for sending a data-modifying control signal that requests execution of the data-modifying operation on the data associated with the data-modifying operation to the primary replica server and the secondary replica servers in a second sequence, where the second sequence is independent of the first sequence.