Encoding data for storage in a dispersed storage network

• US 10,013,191 B2
• Filed: 07/27/2016
• Issued: 07/03/2018
• Est. Priority Date: 08/31/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K.
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US15/221,198
• Publication Number:
  US 20170060684A1
• Time in Patent Office: 706 Days
• Field of Search: 714764, 714766, 714768-770, 714773, 714784, 714 62, 714 622, 714 52, 714 54
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing 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 Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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/0622 in relation to access
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0637 Permissions
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• 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]

Abstract

A method for execution by a dispersed storage and task (DST) processing unit that includes a processor includes receiving a data object for storage in the DSN via a network. Available storage unit data is generated, indicating a subset of a plurality of storage units of the DSN that corresponds to a plurality of available storage units. A shortened encoding matrix is generated based on an original encoding matrix and the available storage unit data. A size of the shortened encoding matrix is based on a number of storage units in the plurality of available storage units. A plurality of encoded slices is generated, each for transmission to one of the plurality of available storage units via the network, by performing an encoding function on the shortened encoding matrix and the data object.

Claims

1. A method for execution by a dispersed storage and task (DST) processing unit that includes a processor, the method comprises:

receiving a data object for storage in a distributed storage network (DSN) via a network;

generating available storage unit data indicating a subset of a plurality of storage units of the DSN that corresponds to a plurality of available storage units;

generating a shortened encoding matrix based on an original encoding matrix and the available storage unit data, wherein a size of the shortened encoding matrix is based on a number of storage units in the plurality of available storage units; and

generating a plurality of encoded slices, each for transmission to one of the plurality of available storage units via the network, by performing an encoding function on the shortened encoding matrix and the data object.

2. The method of claim 1, wherein the plurality of available storage units is a proper subset of the plurality of storage units, wherein the shortened encoding matrix is generated by eliminating at least one row from the original encoding matrix, and wherein the at least one row corresponds to at least one unavailable storage unit not included in the subset.

3. The method of claim 1, wherein the shortened encoding matrix includes at least a number of rows corresponding to one of:

a decode threshold number or a write threshold number.

4. The method of claim 1, wherein generating the available storage unit data includes comparing the number of storage units in the plurality of available storage units to at least one of:

a decode threshold number or a write threshold number, and wherein the shortened encoding matrix and plurality of encoded slices are generated when the available storage unit data indicates that the number of storage units in the plurality of available storage units is greater than or equal to the at least one of;

the decode threshold number or the write threshold number.

5. The method of claim 4, further comprising generating a low storage unit availability notification for transmission via the network when the available storage unit data indicates that the number of storage units in the plurality of available storage units is less than the at least one of:

the decode threshold number or the write threshold number, indicating that the DST processing unit will forego storage of the data object.

6. The method of claim 1, wherein generating the plurality of encoded slices includes dividing the data object into at least one data segment, generating a data matrix corresponding to each data segment, multiplying each data matrix by the shorting encoding matrix to produce at least one coded matrix, and extracting the plurality of encoded slices from the at least one coded matrix.

7. The method of claim 1, further comprising receiving storage unit status data via the network, wherein generating the available storage unit data is based on the storage unit status data.

8. The method of claim 7, further comprising generating a plurality of status requests for transmission to a plurality of storage units, and wherein the storage unit status data is received from the plurality of storage units in response to the plurality of status requests.

9. The method of claim 1, wherein generating the available storage unit data includes at least one of:

interpreting results of a test or interpreting results of a previous access.

10. A processing system of a dispersed storage and task (DST) processing unit comprises:

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to;

receive a data object for storage in a distributed storage network (DSN) via a network;

generate available storage unit data indicating a subset of a plurality of storage units of the DSN that corresponds to a plurality of available storage units;

generate a shortened encoding matrix based on an original encoding matrix and the available storage unit data, wherein a size of the shortened encoding matrix is based on a number of storage units in the plurality of available storage units; and

generate a plurality of encoded slices, each for transmission to one of the plurality of available storage units via the network, by performing an encoding function on the shortened encoding matrix and the data object.

11. The processing system of claim 10, wherein the plurality of available storage units is a proper subset of the plurality of storage units, wherein the shortened encoding matrix is generated by eliminating at least one row from the original encoding matrix, and wherein the at least one row corresponds to at least one unavailable storage unit not included in the subset.

12. The processing system of claim 10, wherein the shortened encoding matrix includes at least a number of rows corresponding to one of:

a decode threshold number or a write threshold number.

13. The processing system of claim 10, wherein generating the available storage unit data includes comparing the number of storage units in the plurality of available storage units to at least one of:

a decode threshold number or a write threshold number, and wherein the shortened encoding matrix and plurality of encoded slices are generated when the available storage unit data indicates that the number of storage units in the plurality of available storage units is greater than or equal to the at least one of;

the decode threshold number or the write threshold number.

14. The processing system of claim 13, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to generate a low storage unit availability notification for transmission via the network when the available storage unit data indicates that the number of storage units in the plurality of available storage units is less than the at least one of:

the decode threshold number or the write threshold number, indicating that the DST processing unit will forego storage of the data object.

15. The processing system of claim 10, wherein generating the plurality of encoded slices includes dividing the data object into at least one data segment, generating a data matrix corresponding to each data segment, multiplying each data matrix by the shorting encoding matrix to produce at least one coded matrix, and extracting the plurality of encoded slices from the at least one coded matrix.

16. The processing system of claim 10, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to receive storage unit status data via the network, wherein generating the available storage unit data is based on the storage unit status data.

17. The processing system of claim 16, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to generate a plurality of status requests for transmission to a plurality of storage units, and wherein the storage unit status data is received from the plurality of storage units in response to the plurality of status requests.

18. The processing system of claim 10, wherein generating the available storage unit data includes at least one of:

interpreting results of a test or interpreting results of a previous access.

19. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to;

receive a data object for storage in the DSN via a network;

generate available storage unit data indicating a subset of a plurality of storage units of the DSN that corresponds to a plurality of available storage units;

generate a shortened encoding matrix based on an original encoding matrix and the available storage unit data, wherein a size of the shortened encoding matrix is based on a number of storage units in the plurality of available storage units; and

generate a plurality of encoded slices, each for transmission to one of the plurality of available storage units via the network, by performing an encoding function on the shortened encoding matrix and the data object.

20. The non-transitory computer readable storage medium of claim 19, wherein the plurality of available storage units is a proper subset of the plurality of storage units, wherein the shortened encoding matrix is generated by eliminating at least one row from the original encoding matrix, and wherein the at least one row corresponds to at least one unavailable storage unit not included in the subset.