Validating stored encoded data slice integrity in a dispersed storage network

• US 10,042,704 B2
• Filed: 05/02/2016
• Issued: 08/07/2018
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Motwani, Manish, Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US15/144,243
• Publication Number:
  US 20170031760A1
• Time in Patent Office: 827 Days
• 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/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• 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 13/4282 on a serial bus, e.g. I2C bus, SPI bus on daisy chain buses G06F13/4247
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/1824 implemented using Network-attached Storage [NAS] architecture distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/645 using a third party
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0653 : Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0668 : adopting a particular infrastructure
• 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/2906 : using block codes H03M13/2957 takes precedence
• 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 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/061 : for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/0853 : using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 63/108 : when the policy decisions are valid for a limited amount of time
• 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/63 : Routing a service request depending on the request content or context
• CPC Class Codes: H04L 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

An encoded data slice is received for storage by a dispersed storage and task (DST) execution unit. A plurality of initial integrity values are generated by executing a plurality of integrity check algorithms on the encoded data slice. The encoded data slice and the plurality of initial integrity values are stored in a memory of the DST execution unit. A subset of the plurality of integrity check algorithms are selected in response to a request to retrieve the encoded data slice. At least one final integrity value is generated by executing the subset of the plurality of integrity check algorithms on the encoded data slice stored in memory. An integrity status is generated by comparing the at least one final integrity value to the corresponding subset of the plurality of initial integrity values.

Claims

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

for a write request regarding an encoded data slice;

receiving the encoded data slice for storage by the DST execution unit;

generating a plurality of initial integrity values for the encoded data slice by executing a plurality of integrity check algorithms on the encoded data slice;

storing the encoded data slice and the plurality of initial integrity values in a memory of the DST execution unit; and

for a read request regarding the encoded data slice;

selecting a subset of the plurality of integrity check algorithms in response to the read request;

generating at least one final integrity value by executing the subset of the plurality of integrity check algorithms on the encoded data slice stored in the memory;

generating an integrity status by comparing the at least one final integrity value to the corresponding subset of the plurality of initial integrity values; and

when the integrity status is favorable, sending the encoded data slice to a requesting computing device in response to the read request.

2. The method of claim 1, further comprising selecting the plurality of integrity check algorithms to be executed on the encoded data slice.

3. The method of claim 2, wherein the plurality of integrity check algorithms are selected based on at least one of:

a processing resource availability level, a desired false-negative probability level, or an algorithm computational efficiency level.

4. The method of claim 2, wherein a first integrity check algorithm is more error-prone than a second integrity check algorithm, wherein the plurality of integrity check algorithms selected includes the first integrity check algorithm in response to determining that processing resource availability is low, and wherein the plurality of integrity check algorithms selected includes the second integrity check algorithm in response to determining that sufficient processing resources are available.

5. The method of claim 2, wherein a first integrity check algorithm is faster than a second integrity check algorithm, and wherein the plurality of integrity check algorithms selected includes the first integrity check algorithm in response to determining that a low desired latency level is required.

6. The method of claim 1 further comprising:

generating a plurality of priority levels corresponding to each of the plurality of integrity check algorithms;

wherein the plurality of integrity check algorithms are executed in an order based on the plurality of priority levels.

7. The method of claim 1 further comprising storing a plurality of identifiers corresponding to the plurality of integrity check algorithms in the memory.

8. The method of claim 1 wherein the subset of the plurality of integrity check algorithms is a non-null proper subset that is selected based on at least one of:

an available resource level, a required retrieval performance level, and a recovery desired maximum false-negative probability level.

9. The method of claim 1 wherein the integrity status indicates a favorable comparison when a result of the comparison indicates that the plurality of initial integrity values and the at least one final integrity value are substantially identical, and wherein the integrity status indicates an unfavorable comparison when a result of the comparison indicates that the corresponding subset of the plurality of initial integrity values and the at least one final integrity value are not substantially identical.

10. The method of claim 1, wherein the sending further comprises sending the integrity status.

11. A processing system of a dispersed storage and task (DST) execution 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;

for a write request regarding an encoded data slice;

receive the encoded data slice for storage by the DST execution unit;

generate a plurality of initial integrity values for the encoded data slice by executing a plurality of integrity check algorithms on the encoded data slice;

store the encoded data slice and the plurality of initial integrity values in a memory of the DST execution unit; and

for a read request regarding the encoded data slice;

select a subset of the plurality of integrity check algorithms in response to the read request;

generate at least one final integrity value by executing the subset of the plurality of integrity check algorithms on the encoded data slice stored in the memory;

generate an integrity status by comparing the at least one final integrity value to the corresponding subset of the plurality of initial integrity values; and

when the integrity status is favorable, sending the encoded data slice to a requesting computing device in response to the read request.

12. The processing system of claim 11, further comprising selecting the plurality of integrity check algorithms to be executed on the encoded data slice.

13. The processing system of claim 12, wherein the plurality of integrity check algorithms are selected based on at least one of:

a processing resource availability level, a desired false-negative probability level, or an algorithm computational efficiency level.

14. The processing system of claim 12, wherein a first integrity check algorithm is more error-prone than a second integrity check algorithm, wherein the plurality of integrity check algorithms selected includes the first integrity check algorithm in response to determining that processing resource availability is low, and wherein the plurality of integrity check algorithms selected includes the second integrity check algorithm in response to determining that sufficient processing resources are available.

15. The processing system of claim 12, wherein a first integrity check algorithm is faster than a second integrity check algorithm, and wherein the plurality of integrity check algorithms selected includes the first integrity check algorithm in response to determining that a low desired latency level is required.

16. The processing system of claim 11 further comprising:

generating a plurality of priority levels corresponding to each of the plurality of integrity check algorithms;

wherein the plurality of integrity check algorithms are executed in an order based on the plurality of priority levels.

17. The processing system of claim 11 further comprising storing a plurality of identifiers corresponding to the plurality of integrity check algorithms in the memory.

18. The processing system of claim 11 wherein the subset of the plurality of integrity check algorithms is a non-null proper subset that is selected based on at least one of:

an available resource level, a required retrieval performance level, and a recovery desired maximum false-negative probability level.

19. The processing system of claim 11 wherein the integrity status indicates a favorable comparison when a result of the comparison indicates that the plurality of initial integrity values and the at least one final integrity value are substantially identical, and wherein the integrity status indicates an unfavorable comparison when a result of the comparison indicates that the at least one initial integrity value and the at least one final integrity value are not substantially identical.

20. 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;

for a write request regarding an encoded data slice;

receive the encoded data slice for storage;

generate a plurality of initial integrity values for the encoded data slice by executing a plurality of integrity check algorithms on the encoded data slice;

store the encoded data slice and the plurality of initial integrity values in a memory of a dispersed storage and task (DST) execution unit; and

for a read request regarding the encoded data slice;

select a subset of the plurality of integrity check algorithms in response to the read request;

generate at least one final integrity value by executing the subset of the plurality of integrity check algorithms on the encoded data slice stored in the memory;

generate an integrity status by comparing the at least one final integrity value to the corresponding subset of the plurality of initial integrity values; and

when the integrity status is favorable, sending the encoded data slice to a requesting computing device in response to the read request.