Distributing data on distributed storage systems

Patent metadata

Field	Value
Publication number	US-10318384-B2
Application number	US-201615180896-A
Country	US
Kind code	B2
Filing date	Jun 13, 2016
Priority date	Dec 5, 2013
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

A method of distributing data in a distributed storage system includes receiving a file, dividing the received file into chunks, and determining a distribution of the chunks among storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system. The maintenance hierarchy includes maintenance levels, and each maintenance level includes one or more maintenance units. Each maintenance unit has an active state and an inactive state. Moreover, each storage device is associated with a maintenance unit. The determining of the distribution of the chunks includes identifying a random selection of the storage devices matching a number of chunks of the file and being capable of maintaining accessibility of the file when one or more maintenance units are in an inactive state. The method also includes distributing the chunks to storage devices of the distributed storage system according to the determined distribution.

First claim

What is claimed is:

1. A method of distributing data in a distributed storage system, the method comprising:
receiving a file at data processing hardware;
dividing, by the data processing hardware, the received file into a number of chunks;
determining, by the data processing hardware, a distribution of the number of chunks among a set of storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system, the maintenance hierarchy comprising maintenance levels, each maintenance level comprising one or more maintenance units, each maintenance unit having an accessible state and an inaccessible state, each storage device associated with a maintenance unit, wherein determining the distribution of the number of chunks comprises:
selecting a number of storage devices randomly from the set of storage devices, the number of storage devices equal to the number of chunks; and
determining accessibility of the file from the selected number of storage devices when one or more of the maintenance units are in the inaccessible state; and

when the file is determined accessible, distributing, by the data processing hardware, the number of chunks to the selected number of storage devices of the distributed storage system according to the determined distribution.

2. The method of claim 1 , further comprising restricting the number of chunks distributed to the selected number of storage devices of any one maintenance unit.

3. The method of claim 1 , wherein when the file is determined inaccessible, selecting another number of storage devices matching the number of chunks of the file.

4. The method of claim 1 , wherein when the file is determined inaccessible, modifying the selected number of storage devices by adding and removing one or more randomly selected storage devices.

5. The method of claim 1 , further comprising selecting the number of storage devices using a simple sampling, a probability sampling, a stratified sampling, or a cluster sampling.

6. The method of claim 1 , further comprising determining the distribution of the number of chunks among the selected number of storage devices by selecting a consecutive number of storage devices equal to the number of chunks of the file from an ordered circular list of the set of storage devices of the distributed storage system.

7. The method of claim 6 , further comprising, when the file is determined inaccessible, selecting another consecutive number of storage devices from the ordered circular list equal to the number of chunks of the file.

8. The method of claim 6 , wherein adjacent storage devices on the ordered circular list are associated with different maintenance units.

9. The method of claim 8 , wherein a threshold number of consecutive storage devices on the ordered circular list are each associated with different maintenance units or are in different geographical locations.

10. The method of claim 1 , further comprising:
dividing, by the data processing hardware, the received file into stripes, each file including a replication code and/or an error correcting code;
when the file includes a replication code, replicating, by the data processing hardware, at least one stripe as replication chunks;
when the file includes an error correcting code, dividing, by the data processing hardware, at least one stripe into data chunks and code chunks; and
distributing, by the data processing hardware, replication chunks among the storage devices differently than distributing the data chunks and the code chunks among the selected number of storage devices.

11. A system for distributing data in a distributed storage system, the system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving a file;
dividing the received file into a number of chunks;
determining a distribution of the number of chunks among a set of storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system, the maintenance hierarchy comprising maintenance levels, each maintenance level comprising one or more maintenance units, each maintenance unit having an accessible state and an inaccessible state, each storage device associated with a maintenance unit, wherein determining the distribution of the number of chunks comprises:
selecting a number of storage devices randomly from the set of storage devices, the number of storage devices equal to the number of chunks and the selected number of storage devices; and
determining accessibility of the file from the selected number of storage devices when one or more of the maintenance units are in the inaccessible state; and

when the file is determined accessible, distributing the number of chunks to the selected number of storage devices of the distributed storage system according to the determined distribution.

12. The system of claim 11 , wherein the operations further comprise restricting the number of chunks distributed to the selected number of storage devices of any one maintenance unit.

13. The system of claim 11 , wherein when the file is determined inaccessible, selecting another number of storage devices matching the number of chunks of the file.

14. The system of claim 11 , wherein when the file is determined inaccessible, modifying the selected number of storage devices by adding and removing one or more randomly selected storage devices.

15. The system of claim 11 , wherein the operations further comprise selecting the number of storage devices using a simple sampling, a probability sampling, a stratified sampling, or a cluster sampling.

16. The system of claim 11 , wherein the operations further comprise determining the distribution of the number of chunks among the selected number of storage devices by selecting a consecutive number of storage devices equal to the number of chunks of the file from an ordered circular list of the set of storage devices of the distributed storage system.

17. The system of claim 16 , wherein the operations further comprise, when the file is determined inaccessible, selecting another consecutive number of storage devices from the ordered circular list equal to the number of chunks of the file.

18. The system of claim 16 , wherein adjacent storage devices on the ordered circular list are associated with different maintenance units.

19. The system of claim 18 , wherein a threshold number of consecutive storage devices on the ordered circular list are each associated with different maintenance units or are in different geographical locations.

20. The system of claim 11 , wherein the operations further comprise:
dividing the received file into stripes, each file including a replication code and/or an error correcting code;
when the file includes a replication code, replicating at least one stripe as replication chunks;
when the file includes an error correcting code, dividing at least one stripe into data chunks and code chunks; and
distributing replication chunks among the storage devices differently than distributing the data chunks and the code chunks among the selected number of storage devices.

Assignees

• Google Llc

Inventors

• Cypher Robert
• Quinlan Sean
• Schirripa Steven Robert

Classifications

• G06F16/182 Primary

  Distributed file systems · CPC title

• G06F11/1435 Primary

  using file system or storage system metadata · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/1748

  De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641) · CPC title