Efficient data reads from distributed storage systems

Patent metadata

Field	Value
Publication number	US-9747155-B2
Application number	US-201615342717-A
Country	US
Kind code	B2
Filing date	Nov 3, 2016
Priority date	Jan 31, 2014
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

A method of distributing data in a distributed storage system includes receiving a file and dividing the received file into chunks. The chunks are data-chunks and non-data chunks. The method further includes grouping chunks into a group and determining a distribution of the chunks of the group among storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system. The maintenance hierarchy includes hierarchical maintenance levels and maintenance domains. Each maintenance domain has an active state or an inactive state; and each storage device is associated with at least one maintenance domain. The method also includes distributing the chunks of the group to the storage devices based on the determined distribution. The chunks of the group are distributed across multiple maintenance domains to maintain an ability to reconstruct chunks of the group when a maintenance domain is in the inactive state.

First claim

What is claimed is:

1. A method of distributing data in a distributed storage system, the method comprising:
receiving, at data processing hardware, a file;
dividing, by the data processing hardware, the received file into chunks, the chunks being data-chunks and non-data chunks;
grouping, by the data processing hardware, chunks into a group;
determining, by the data processing hardware, a distribution of the chunks of the group among storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system, the maintenance hierarchy comprising hierarchical maintenance levels and maintenance domains, each maintenance domain having an active state or an inactive state, each storage device associated with at least one maintenance domain; and
distributing, by the data processing hardware, the chunks of the group to the storage devices based on the determined distribution, the chunks of the group being distributed across multiple maintenance domains to maintain an ability to reconstruct chunks of the group when a maintenance domain is in the inactive state.

2. The method of claim 1 , wherein the group comprises one or more of the data chunks and one or more of the non-data chunks, and wherein one or more of the data chunks or one or more of the non-data chunks of the group are capable of being reconstructed from other chunks of the group.

3. The method of claim 1 , wherein each maintenance domain spans one or more adjacent hierarchical maintenance levels.

4. The method of claim 1 , wherein the hierarchical maintenance levels comprise:
a storage device level;
a rack level, the storage device level depending from the rack level;
a bus duct level, the rack level depending from the bus duct level; and
a power distribution center level, the bus duct level depending from the power distribution center level,
wherein each maintenance domain spans at least the storage device level.

5. The method of claim 1 , further comprising restricting, by the data processing hardware, a number of chunks of a group distributed to storage devices of any one maintenance domain.

6. The method of claim 1 , wherein the distribution comprises a random selection of storage devices matching a number of the chunks of the group capable of maintaining accessibility of the group when one or more maintenance domains are in the inactive state.

7. The method of claim 6 , wherein when the random selection of the storage devices is incapable of maintaining accessibility of the group when one or more maintenance domains are in the inactive state, modifying, by the data processing hardware, the random selection of the storage devices by adding and/or removing one or more randomly selected storage devices.

8. The method of claim 6 , further comprising determining, by the data processing hardware, the first random selection of storage devices using a simple sampling, a probability sampling, a stratified sampling, or a cluster sampling.

9. The method of claim 1 , wherein determining the distribution of the chunks of the group among the storage devices comprises selecting a consecutive number of storage devices equal to a number of chunks of the group from an ordered circular list of the storage devices of the distributed storage system.

10. The method of claim 9 , further comprising, when the selected storage devices are collectively incapable of maintaining the accessibility of the group when one or more maintenance domains are in an inactive state, selecting, by the data processing hardware, another consecutive number of storage devices from the ordered circular list equal to the number of chunks of the group.

11. The method of claim 9 , further comprising determining, by the data processing hardware, the ordered circular list of storage devices of the distributed storage system, adjacent storage devices on the ordered circular list associated with different maintenance domains.

12. The method of claim 11 , wherein a threshold number of consecutive storage devices on the ordered circular list are each at least one of:
associated with different maintenance domains; or
in different geographical locations.

13. A system for distributing data in a distributed storage system, the system comprising:
storage devices; and
a computer processor in communication with the storage devices, the computer processor configured to perform operations comprising:
receiving a file;
dividing the received file into chunks, the chunks being data-chunks and non-data chunks;
grouping the chunks into a group;
determining a distribution of the chunks of the group among storage devices of the distributed storage system based on a maintenance hierarchy of the distributed storage system, the maintenance hierarchy comprising hierarchical maintenance levels and maintenance domains, each maintenance domain having an active state or an inactive state, each storage device associated with at least one maintenance domain; and
distributing the chunks of the group to the storage devices based on the determined distribution, the chunks of the group being distributed across multiple maintenance domains to maintain an ability to reconstruct chunks of the group when a maintenance domain is in the inactive state.

14. The system of claim 13 , wherein the group comprises one or more of the data chunks and one or more of the non-data chunks, and wherein one or more of the data chunks or one or more of the non-data chunks of the group are capable of being reconstructed from other chunks of the group.

15. The system of claim 13 , wherein each maintenance domain spans one or more adjacent hierarchical maintenance levels.

16. The system of claim 13 , wherein the hierarchical maintenance levels comprise:
a storage device level;
a rack level, the storage device level depending from the rack level;
a bus duct level, the rack level depending from the bus duct level; and
a power distribution center level, the bus duct level depending from the power distribution center level,
wherein each maintenance domain spans at least the storage device level.

17. The system of claim 13 , wherein the operations further comprise restricting a number of chunks of a group distributed to storage devices of any one maintenance domain.

18. The system of claim 13 , wherein the distribution comprises a random selection of storage devices matching a number of the chunks of the group capable of maintaining accessibility of the group when one or more maintenance domains are in the inactive state.

19. The system of claim 18 , wherein when the random selection of the storage devices is incapable of maintaining accessibility of the group when one or more maintenance domains are in the inactive state, the operations further comprise modifying the random selection of the storage devices by adding and/or removing one or more randomly selected storage devices.

20. The system of claim 18 , wherein the operations further comprise determining the first random selection of storage devices using a simple sampling, a probability sampling, a stratified sampling, or a cluster sampling.

21. The system of claim 13 , wherein determining the distribution of the chunks of the group among the storage devices comprises selecting a consecutive number of storage devices equal to a number of chunks of the group from an ordered circular list of the storage devices of the distributed storage system.

22. The system of claim 21 , wherein the operations further com

Assignees

• Google Inc

Inventors

• Cypher Robert
• Quinlan Sean
• Schirripa Steven Robert
• Carmi Lidor
• Schrock Christian Eric

Classifications

• G06F2211/1028

  Distributed, i.e. distributed RAID systems with parity · CPC title

• G06F11/0793 Primary

  Remedial or corrective actions (recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40) · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G06F11/0727

  in a storage system, e.g. in a DASD or network based storage system (drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097) · CPC title