US 9,178,958 B2Granted

Distributed storage system

AssigneeFacebook, Inc.

InventorsJack William Lindamood, Douglas John Beaver, Apostolos Lerios, Matthew Page, Peter Avelino Ruibal

Life of this patent

Estimating the term…

Loading patent…

Abstract

In one embodiment, a first computing device receives a write request and data from a second computing device; iteratively attempts to write the data until a copy of the data is successfully written to each and every storage node belonging to a storage volume; and transmits a volume identifier of the storage volume and a data identifier assigned to the data to the second computing device. In one embodiment, a first computing device receives a read request and a volume identifier and a data identifier from a second computing device; accesses a cache to select the storage volume identified by the volume identifier; iteratively attempts to read data identified by the data identifier until a copy of the data is successfully read from a storage node belonging to the selected storage volume; and transmits the copy of the data to the second computing device.

Claims15

Dependent claims

A method comprising:

by one or more first computing devices, in response to a write request and data associated with the write request received from a second computing device, selecting from a cache a first storage volume of a plurality of storage volumes, wherein each storage volume of the plurality of storage volumes is identified by a unique volume identifier and comprises a plurality of storage nodes;
by the one or more first computing devices, sending instructions to write a copy of the data to each storage node of the first storage volume;
in response to a determination that the copy of the data was not successfully written to one or more storage nodes of the first storage volume, by the one or more first computing devices, selecting from the cache a second storage volume of the plurality of storage volumes;
by the one or more first computing devices, sending instructions to write a copy of the data to each storage node of the second storage volume;
in response to a determination that the copy of the data was successfully written to each storage node of the second storage volume, by the one or more first computing devices, generating a data-scrambler number associated with the data, wherein the data-scrambler number is randomly generated;
by the one or more first computing devices, sending to the second computing device:
a volume identifier of the second storage volume;
a data identifier assigned to the data;
and
the data-scrambler number;
by the one or more first computing devices, receiving a read request from a third computing device, the read request comprising:
the volume identifier of the second storage volume;
the data identifier assigned to the data;
and
an invalid data-scrambler number;
and
in response to a determination that the invalid data-scrambler number does not match the data-scrambler number associated with the data, by the one or more first computing devices, sending a read-failure message to the third computing device.

14 more elements

One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

in response to a write request and data associated with the write request received from a second computing device, select from a cache a first storage volume of a plurality of storage volumes, wherein each storage volume of the plurality of storage volumes is identified by a unique volume identifier and comprises a plurality of storage nodes;
send instructions to write a copy of the data to each storage node of the first storage volume;
in response to a determination that the copy of the data was not successfully written to one or more storage nodes of the first storage volume, select from the cache a second storage volume of the plurality of storage volumes;
send instructions to write a copy of the data to each storage node of the second storage volume;
in response to a determination that the copy of the data was successfully written to each storage node of the second storage volume, generate a data-scrambler number associated with the data, wherein the data-scrambler number is randomly generated;
send to the second computing device:
a volume identifier of the second storage volume;
a data identifier assigned to the data;
and
the data-scrambler number;
receive a read request from a third computing device, the read request comprising:
the volume identifier of the second storage volume;
the data identifier assigned to the data;
and
an invalid data-scrambler number;
and
in response to a determination that the invalid data-scrambler number does not match the data-scrambler number associated with the data, send a read-failure message to the third computing device.

14 more elements

A system comprising:

one or more processors;
and
a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
in response to a write request and data associated with the write request received from a second computing device, select from a cache a first storage volume of a plurality of storage volumes, wherein each storage volume of the plurality of storage volumes is identified by a unique volume identifier and comprises a plurality of storage nodes;
send instructions to write a copy of the data to each storage node of the first storage volume;
in response to a determination that the copy of the data was not successfully written to one or more storage nodes of the first storage volume, select from the cache a second storage volume of the plurality of storage volumes;
send instructions to write a copy of the data to each storage node of the second storage volume;
in response to a determination that the copy of the data was successfully written to each storage node of the second storage volume, generate a data-scrambler number associated with the data, wherein the data-scrambler number is randomly generated;
send to the second computing device:
a volume identifier of the second storage volume;
a data identifier assigned to the data;
and
the data-scrambler number;
receive a read request from a third computing device, the read request comprising:
the volume identifier of the second storage volume;
the data identifier assigned to the data;
and
an invalid data-scrambler number;
and
in response to a determination that the invalid data-scrambler number does not match the data-scrambler number associated with the data, send a read-failure message to the third computing device.

17 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/298,481Filed 6 Jun 2014 · continuation
Priority: 17 Dec 2010
Published: US 2014/0289358 A125 Sep 2014
Granted: 3 Nov 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

H04L 67/568
Provisioning of proxy services: storing data temporarily at an intermediate stage, e.g. caching
G06F 3/0611
Improving I/O performance: in relation to response time
G06F 3/0619
Improving the reliability of storage systems: in relation to data integrity, e.g. data losses, bit errors
G06F 3/065
Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems: replication mechanisms

Family

Application12/972,220Parent of this continuation · filed 17 Dec 2010
US 2014/0289358 A1Pre-grant publication · published 25 Sep 2014
US 2012/0159099 A1Published application
US 8,793,328 B2Related patent
US 9,178,958 B2This patent

From the US filing history. Foreign family members aren’t listed.