US 8,805,901 B1Granted

Geographically distributed file system

AssigneeGoogle Inc.

InventorsAaron Jacobs, Benjamin C. Appleton

Life of this patent

Estimating the term…

Loading patent…

Abstract

Implementations of the present disclosure are directed to a method, system, and storage media for receiving an indication that an attempt to make a modified first version of a directory a current version of the directory in a file system using a consensus protocol did not succeed and, in response thereto, obtaining a most recent second version of the directory including second pointers and a second name associated with each of the second pointers, wherein each second pointer is a reference to an immutable data object in the file system; and identifying one or more of the second names, each identified second name being the same as one of the first names but being associated with a second pointer that is different than the first name's respective first pointer, and obtaining for each identified second name, the data object referenced by the respective second pointer from the file system.

Claims24

Dependent claims

A method implemented by data processing apparatus, the method including:

identifying, by a first pointer manager of a plurality of pointer managers, a first version of a directory, the first version of the directory including i) a first pointer and ii) an association of a name with the first pointer, wherein the first pointer is a reference to a first version of an immutable data object in an append-only file system;
receiving, by the first pointer manager, a modified version of the data object from a first computing device in communication with the first pointer manager;
determining, by each pointer manager of the plurality of pointer managers, whether the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was not updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
creating a second pointer that is a reference to the modified version of the data object, associating the name with the second pointer, and disassociating the name from the first pointer, and
creating a modified version of the directory, the modified version of the directory including i) the second pointer and ii) an association of the name with the second pointer;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
providing, to the first computing device, a current version of the directory stored by the filed system including i) a third pointer to a most current version of the data object and ii) an association of the name with the third pointer.

5 more elements

A system comprising:

a computer readable medium having instructions stored thereon;
and
data processing apparatus configured to execute the instructions to perform operations comprising:
identifying, by a first pointer manager of a plurality of pointer managers, a first version of a directory, the first version of the directory including i) a first pointer and ii) an association of a name with the first pointer, wherein the first pointer is a reference to a first version of an immutable data object in an append-only file system;
receiving, by the first pointer manager, a modified version of the data object from a first computing device in communication with the first pointer manager;
determining, by each pointer manager of the plurality of pointer managers, whether the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was not updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
creating a second pointer that is a reference to the modified version of the data object, associating the name with the second pointer, and disassociating the name from the first pointer, and
creating a modified version of the directory, the modified version of the directory including i) the second pointer and ii) an association of the name with the second pointer;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
providing, to the first computing device, a current version of the directory stored by the filed system including i) a third pointer to a most current version of the data object and ii) an association of the name with the third pointer.

8 more elements

A storage media having instructions stored thereon that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

identifying, by a first pointer manager of a plurality of pointer managers, a first version of a directory, the first version of the directory including i) a first pointer and ii) an association of a name with the first pointer, wherein the first pointer is a reference to a first version of an immutable data object in an append-only file system;
receiving, by the first pointer manager, a modified version of the data object from a first computing device in communication with the first pointer manager;
determining, by each pointer manager of the plurality of pointer managers, whether the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was not updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
creating a second pointer that is a reference to the modified version of the data object, associating the name with the second pointer, and disassociating the name from the first pointer, and
creating a modified version of the directory, the modified version of the directory including i) the second pointer and ii) an association of the name with the second pointer;
if a majority of the plurality of pointer managers determine that the data object stored by the file system was updated by any computing device other than the first computing device before the first pointer manager received the modified version of the data object:
providing, to the first computing device, a current version of the directory stored by the filed system including i) a third pointer to a most current version of the data object and ii) an association of the name with the third pointer.

5 more elements

Dependencies are inferred from the claim text.