Google Inc.

Hewlett-packard Development Company, L.p.

Shun-Tak Leung

Sanjay Ghemawat

Howard Bradley Gobioff

Minwen Ji

David L desJARDINS

A system facilitates the distribution and redistribution of chunks of data among multiple servers. The system may identify servers to store a replica of the data based on at least one of utilization of the servers, prior data distribution involving the servers, and failure correlation properties associated with the servers, and place the replicas of the data at the identified servers. The system may also monitor total numbers of replicas of the chunks available in the system, identify chunks that have a total number of replicas below one or more chunk thresholds, assign priorities to the identified chunks, and re-replicate the identified chunks based substantially on the assigned priorities. The system may further monitor utilization of the servers, determine whether to redistribute any of the replicas, select one or more of the replicas to redistribute based on the utilization of the servers, select one or more of the servers to which to move the one or more replicas, and move the one or more replicas to the selected one or more servers.

Systems and methods for replicating data

A system that facilitates the distribution and redistribution of chunks of data among multiple servers, may identify servers to store replicas of the chunks based on at least one of utilization, prior data distribution, and failure correlation properties, and place the replicas at the identified servers. The system may monitor total numbers of replicas available in the system, identify chunks that have a total number of replicas below one or more thresholds, assign priorities to the identified chunks, and re-replicate the identified chunks based on the assigned priorities. The system may monitor utilization of the servers, select one or more of the replicas to redistribute based on the utilization of the servers, select one or more of the servers to which to move the one or more replicas, and move the one or more replicas to the selected one or more servers.

A system facilitates the deletion of data, such as files, orphaned chunks, and stale replicas. The system may identify a file to be deleted, rename the identified file, permanently delete the renamed file a predetermined amount of time after renaming the identified file as part of a garbage collection process, receive, from the servers, information concerning chunks stored by the servers, and identify, to the servers, ones of the chunks that do not exist possibly due to the permanent deletion of the renamed file. The system may further provide a mapping of file names to chunks, identify chunks, as orphaned chunks, that are not reachable from any of the file names, delete the orphaned chunks, receive, from the servers, information concerning chunks stored by the servers, and identify, to the servers, ones of the chunks that are orphaned chunks. The system may also associate version information with replicas of chunks, identify stale replicas based on the associated version information, delete the stale replicas, receive, from the servers, information concerning replicas stored by the servers, and identify, to the servers, ones of the replicas that are stale replicas.

Garbage collecting systems and methods

A file system includes a master connected to multiple servers. The servers may store data. The master may communicate with the servers upon startup of the master to authoritatively identify the data stored by the servers and record location information that identifies ones of the servers that store the data.

Maintaining data in a file system

A system may perform a first operation within a file system in which directories and files are organized as nodes in a namespace tree. The system may associate a read-write lock with each of the nodes in the namespace tree. The system may acquire a first lock on a name of one or more directories involved in the first operation, acquire a second lock on an entire pathname involved in the first operation, determine whether the first lock or the second lock conflicts with third locks acquired by a second operation, and perform the first operation when the first lock or the second lock does not conflict with the third locks. The first, second, and third locks may include read-write locks.

Namespace locking scheme

A system facilitates the performance of a record append operation. The system may include a primary replica and one or more secondary replicas that store copies of data. The primary and secondary replicas may receive a record to be appended to the data and a record append request that identifies the record to be appended to the data. The primary and secondary replicas may append the record to the data, possibly at the same offset. If multiple record append requests are concurrently received, the requests may be serialized to establish an order for the requests.

Systems and methods for performing record append operations

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.

Leasing scheme for data-modifying operations

A method of redundantly storing data in a geographically-diverse data-storing system is presented. The data-storing system has one or more data sites and a set of data-protecting sites. A new version of a set of data is written to a first data site, and a representation of the new version is generated. The representation is transmitted from the first data site to a subset of the data-protecting sites. At each data-protecting site, the representation is stored and an acknowledgment of the storing is transmitted back. Also, upon receipt back of a commit command, a data-protecting operation is performed on the representation to generate a data-protecting value, which is also stored. Then, storage corresponding to the representation is released. Further, at a first data site, once acknowledgments from each data-protecting site are received, a commit command is transmitted to the subset of data-protecting sites. Additionally, storage is released corresponding to a previous version of the set of data.

Growing community of inventors

Mountain View, CA, United States of America

Shun-Tak Leung