Hierarchical wide spreading of distributed storage

Patent metadata

Field	Value
Publication number	US-2016239384-A1
Application number	US-201615143437-A
Country	US
Kind code	A1
Filing date	Apr 29, 2016
Priority date	Sep 2, 2014
Publication date	Aug 18, 2016
Grant date	—

Abstract

Systems and techniques for managing data storage are disclosed. In some aspects, a front-end node responds to a request to write an object by dividing the object into multiple source data segments. The front-end node generates redundancy data for the multiple source data segments using a rateless erasure encoding. The front-end node associates a respective subset of the redundancy data with each of the multiple source data segments, wherein each subset of redundancy data and associated source data segment form an encoded segment. The rateless erasure encoding further includes defining multiple segment-level fragments within each of the encoded segments. The front-end node transmits each of the encoded segments to a selected one of multiple storage nodes, wherein each of the selected storage nodes are selected based on a determined storage layout of the encoded segments across the multiple storage nodes. For each of the received encoded segments, the storage node generates one or more protection fragments based on redundancy data generated from the segment-level fragments and stores the segment-level fragments and corresponding protection fragments across multiple storage media devices managed by the selected storage node.

First claim

What is claimed is:

1 . A method for managing data storage, said method comprising:
in response to a request to write an object, dividing the object into multiple source data segments; generating redundancy data for the multiple source data segments using a rateless erasure encoding; associating a respective subset of the redundancy data with each of the multiple source data segments, wherein each subset of redundancy data and associated source data segment form an encoded segment; defining multiple segment-level fragments within each of the encoded segments; transmitting each of the encoded segments to a selected one of multiple storage nodes, wherein each of the selected storage nodes are selected based on a determined storage layout of the encoded segments across the multiple storage nodes; and for each of the encoded segments received at each of the selected storage nodes,
generating one or more protection fragments based on redundancy data generated from the segment-level fragments; and
storing the segment-level fragments and corresponding protection fragments across multiple storage media devices managed by the selected storage node.

2 . The method of claim 1 , wherein said generating one or more protection fragments based on redundancy data determined for the segment-level fragments comprises encoding the segment-level fragments using a fixed rate erasure code.

3 . The method of claim 1 , further comprising maintaining an identifier index for the segment-level fragments within a front-end node that is communicatively coupled to the selected storage nodes via network connections, wherein said front-end node performs said steps of:
in response to a request to write an object, dividing the object into multiple source data segments; generating redundancy data for the multiple source data segments using a rateless erasure encoding; and associating a respective subset of the redundancy data with each of the multiple source data segments, wherein each subset of redundancy data and associated source data segment form an encoded segment.

4 . The method of claim 1 , further comprising, for each of the encoded segments received by a corresponding one of the storage nodes, maintaining an identifier index for the segment-level fragments and the protection fragments within the corresponding storage node.

5 . The method of claim 1 , wherein said generating redundancy data for the source data segments comprises:
receiving object data into data ranges of a buffer having k data ranges and k protection ranges; precoding each of the k data ranges by,
determining redundancy data for the k data ranges using fixed rate erasure encoding; and
entering a subset of the determined redundancy data for the k data ranges into each of the k protection ranges, wherein each of the k data ranges and a corresponding one of the k protection ranges form a pre-coded segment; and
encoding the pre-coded segments using a Luby transform code to form the encoded segments.

6 . The method of claim 5 , further comprising:
dividing each of the pre-coded segments into k′ pre-coded fragments; and wherein said encoding the pre-coded segments includes, for each pre-coded segment, applying the Luby transform code to the k′ pre-coded fragments to generate a sequence of encoded symbols comprising k′+m segment-level fragments, wherein m is greater than or equal to one.

7 . The method of claim 1 , wherein said storing the segment-level fragments and corresponding protection fragments across multiple storage devices comprises:
selecting a zone set comprising a fixed number of physically contiguous storage areas within a fixed number of storage media devices; and assigning each of the segment-level fragments and protection fragments to be stored at respective ones of the physically contiguous storage areas within the fixed number of storage media devices.

8 . The method of claim 1 , further comprising:
generating index entries that associate address information for the physically contiguous storage areas with the segment-level fragments and protection fragments stored thereon.

9 . A non-transitory machine readable medium having stored thereon instructions for performing a method, wherein the instructions comprise machine executable code which when executed by at least one machine, causes the machine to:
in response to a request to write an object, divide the object into multiple source data segments; generate redundancy data for the multiple source data segments using a rateless erasure encoding; associate a respective subset of the redundancy data with each of the multiple source data segments, wherein each subset of redundancy data and associated source data segment form an encoded segment; define multiple segment-level fragments within each of the encoded segments; transmit each of the encoded segments to a selected one of multiple storage nodes, wherein each of the selected storage nodes are selected based on a determined storage layout of the encoded segments across the multiple storage nodes; and for each of the encoded segments received at each of the selected storage nodes,
generate one or more protection fragments based on redundancy data generated from the segment-level fragments; and
store the segment-level fragments and corresponding protection fragments across multiple storage media devices managed by the selected storage node.

10 . The non-transitory machine readable medium of claim 9 , wherein said generating one or more protection fragments based on redundancy data determined for the segment-level fragments comprises encoding the segment-level fragments using a fixed rate erasure code.

11 . The non-transitory machine readable medium of claim 9 , wherein the instructions comprise machine executable code which when executed by at least one machine, causes the machine to, for each of the encoded segments received by a corresponding one of the storage nodes, maintain an identifier index for the segment-level fragments and the protection fragments within the corresponding storage node.

12 . The non-transitory machine readable medium of claim 9 , wherein said generating redundancy data for the source data segments comprises:
receiving object data into data ranges of a buffer having k data ranges and k protection ranges; precoding each of the k data ranges by,
determining redundancy data for the k data ranges using fixed rate erasure encoding; and
entering a subset of the determined redundancy data for the k data ranges into each of the k protection ranges, wherein each of the k data ranges and a corresponding one of the k protection ranges form a pre-coded segment; and
encoding the pre-coded segments using a Luby transform code to form the encoded segments.

13 . The non-transitory machine readable medium of claim 12 , wherein the instructions comprise machine executable code which when executed by at least one machine, causes the machine to:
divide each of the pre-coded segments into k′ pre-coded fragments; and wherein said encoding the pre-coded segments includes, for each pre-coded segment,
applying the Luby transform code to the k′ pre-coded fragments to generate a sequence of encoded symbols comprising k′+m segment-level fragments, wherein m is greater than or equal to one.

14 . The non-transitory machine readable medium of claim 9 , wherein said storing the segment-level fragments and corresponding protection fragments across multiple storage devices comprises:
selecting a zone set comprising a fixed number of physically contiguous storage areas within a fixed number of storage media dev

Assignees

• Netapp Inc

Inventors

• Slik David Anthony
• Benight Barry Patrick

Classifications

• G06F11/1076 Primary

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

• H03M13/154

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title

• H04L67/1097 Primary

  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 title

• G06F3/0673

  Single storage device · CPC title

• H04L69/40

  for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection (management of faults, events, alarms or notifications in data switching networks H04L41/06) · CPC title