Distributed storage system

• US 9,178,958 B2
• Filed: 06/06/2014
• Issued: 11/03/2015
• Est. Priority Date: 12/17/2010
• Status: Expired due to Fees

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Beaver, Douglas John, Lerios, Apostolos, Page, Matthew, Ruibal, Peter Avelino, Lindamood, Jack William
• Primary Examiner(s): Moise, Emmanuel L
• Assistant Examiner(s): ABU ROUMI, MAHRAN Y
• Application Number:
  US14/298,481
• Publication Number:
  US 20140289358A1
• Time in Patent Office: 515 Days
• Field of Search: 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2056 by mirroring
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

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.

Claims

1. 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.

2. The method of claim 1, wherein each storage volume of the plurality of storage volumes is associated with a randomly generated volume-scrambler number.

3. The method of claim 2, further comprising, by the one or more first computing devices, sending a volume-scrambler number associated with the second storage volume to the second computing device.

4. The method of claim 1, further comprising:

by the one or more first computing devices, receiving a read request from a fourth computing device, the read request comprising;

the volume identifier of the second storage volume;

the data identifier assigned to the data; and

the data-scrambler number associated with the data;

in response to a determination that the volume identifier, the data identifier, and the data-scrambler number are valid, by the one or more first computing devices, sending instructions to retrieve a copy of the data from a storage node of the second storage volume; and

by the one or more first computing devices, sending the retrieved copy of the data to the fourth computing device.

5. The method of claim 1, wherein the data identifier and the data-scrambler number are unique within the second storage volume.

6. 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.

7. The media of claim 6, wherein each storage volume of the plurality of storage volumes is associated with a randomly generated volume-scrambler number.

8. The media of claim 7, wherein the software is further operable when executed to send a volume-scrambler number associated with the second storage volume to the second computing device.

9. The media of claim 6, wherein the software is further operable when executed to:

receive a read request from a fourth computing device, the read request comprising;

the volume identifier of the second storage volume;

the data identifier assigned to the data; and

the data-scrambler number associated with the data;

in response to a determination that the volume identifier, the data identifier, and the data-scrambler number are valid, send instructions to retrieve a copy of the data from a storage node of the second storage volume; and

send the retrieved copy of the data to the fourth computing device.

10. The media of claim 6, wherein the data identifier and the data-scrambler number are unique within the second storage volume.

11. 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.

12. The system of claim 11, wherein each storage volume of the plurality of storage volumes is associated with a randomly generated volume-scrambler number.

13. The system of claim 12, wherein the processors are further operable when executing the instructions to send a volume-scrambler number associated with the second storage volume to the second computing device.

14. The system of claim 11, wherein the processors are further operable when executing the instructions to:

receive a read request from a fourth computing device, the read request comprising;

the volume identifier of the second storage volume;

the data identifier assigned to the data; and

the data-scrambler number associated with the data;

in response to a determination that the volume identifier, the data identifier, and the data-scrambler number are valid, send instructions to retrieve a copy of the data from a storage node of the second storage volume; and

send the retrieved copy of the data to the fourth computing device.

15. The system of claim 11, wherein the data identifier and the data-scrambler number are unique within the second storage volume.