Retrieving multi-generational stored data in a dispersed storage network

• US 9,612,882 B2
• Filed: 03/04/2015
• Issued: 04/04/2017
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K., Dhuse, Greg, Volvovski, Ilya, Leggette, Wesley
• Primary Examiner(s): MCMAHON, DANIEL F
• Application Number:
  US14/638,175
• Publication Number:
  US 20150319244A1
• Time in Patent Office: 762 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• 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/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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 9/526 Mutual exclusion algorithms
• 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: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Methods for use by processing modules in a dispersed storage network (DSN) to retrieve a data object stored in one of a plurality of storage generations of the DSN, each of the storage generations including a plurality of storage units. In various examples, a first retrieval request is generated to retrieve metadata addressing information. Based on the metadata addressing information, a second retrieval request is generated to retrieve the metadata. Using the metadata, a third retrieval request is then generated to retrieve at least a portion of the data object. The metadata addressing information, the metadata, and the data object may be retrieved from differing storage generations. Each of the first, second, and third retrieval requests are formatted in accordance with a read request format of the DSN, the read request format including a storage generation identifier field.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the DSN including a plurality of storage generations, each of the plurality of storage generations utilizing a plurality of storage units, the method comprises:

generating, based on a data object name, a first retrieval request for retrieving metadata addressing information, wherein the first retrieval request is formatted in accordance with a read request format of the DSN;

generating, based on retrieved metadata addressing information, a second retrieval request for retrieving metadata, wherein the second retrieval request is formatted in accordance with the read request format of the DSN; and

generating, based on retrieved metadata, a third retrieval request for retrieving at least a portion of a data object associated with the data object name, wherein the third retrieval request is formatted in accordance with the read request format of the DSN, wherein at least two of the metadata addressing information, the metadata, and the data object are stored in differing storage generations of the plurality of storage generations.

2. The method of claim 1, wherein the generating the first retrieval request comprises:

performing a deterministic function on the data object name to produce a digital value;

using a first portion of the digital value as a generation identifier in a generation identifier field of the read request format of the DSN; and

using a second portion of the digital value as an object identifier of the read request format of the DSN.

3. The method of claim 2, wherein the generating the first retrieval request comprises:

determining a vault identifier associated with the data object; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

4. The method of claim 1 further comprises:

generating, based on the data object name, the first retrieval request by;

generating a set of first level read requests for retrieving at least a decode threshold number of metadata addressing information slices, wherein the metadata addressing information includes addressing information regarding storage of the metadata within the DSN, wherein the metadata addressing information was dispersed storage error encoded to produce a set of metadata addressing information slices, and wherein the decode threshold number of metadata addressing information slices represents a minimum number of metadata addressing information slices of the set of metadata addressing information slices that is required to recover the metadata addressing information; and

decoding the at least a decode threshold number of metadata addressing information slices to recover the metadata addressing information.

5. The method of claim 1, wherein the generating the second retrieval request comprises:

generating, based on the metadata addressing information, a set of second level read requests for retrieving at least a decode threshold number of metadata slices, wherein the metadata includes addressing information regarding storage of a plurality of sets of encoded data slices of the data object within the DSN, wherein the metadata was dispersed storage error encoded to produce a set of metadata slices, and wherein the decode threshold number of metadata slices represents a minimum number of metadata slices of the set of metadata slices that is required to recover the metadata.

6. The method of claim 5 further comprises:

decoding the at least a decode threshold number of metadata slices to recover the metadata.

7. The method of claim 1, wherein the generating the second retrieval request comprises:

extracting a generation identifier and an object identifier from the metadata addressing information, the generation identifier indicating one of the plurality of storage generations;

determining a vault identifier associated with the data object;

using the generation identifier in a generation identifier field of the read request format of the DSN;

using the object identifier in an object identifier field of the read request format of the DSN; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

8. The method of claim 1, wherein the generating the third retrieval request comprises:

generating, based on the metadata, at least one set of third level read requests for retrieving at least a decode threshold number of encoded data slices, wherein the data object was dispersed storage error encoded to produce a plurality of sets of encoded data slices, and wherein the decode threshold number of encoded data slices represents a minimum number of encoded data slices of a set of the plurality of sets of encoded data slices that is required to recover the portion of the data object.

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

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), causes the one or more computing devices to;

generate, based on a data object name, a first retrieval request for retrieving metadata addressing information, wherein the first retrieval request is formatted in accordance with a read request format of the DSN;

generate, based on retrieved metadata addressing information, a second retrieval request for retrieving metadata, wherein the second retrieval request is formatted in accordance with the read request format of the DSN; and

generate, based on retrieved metadata, a third retrieval request for retrieving at least a portion of a data object associated with the data object name, wherein the third retrieval request is formatted in accordance with the read request format of the DSN, the DSN including a plurality of storage generations, each of the plurality of storage generations utilizing a plurality of storage units, and further wherein at least two of the metadata addressing information, the metadata, and the data object are stored in differing storage generations of the plurality of storage generations.

10. The non-transitory computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the first retrieval request by:

performing a deterministic function on the data object name to produce a digital value;

using a first portion of the digital value as a generation identifier in a generation identifier field of the read request format of the DSN; and

using a second portion of the digital value as an object identifier of the read request format of the DSN.

11. The non-transitory computer readable storage medium of claim 10, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the first retrieval request by:

determining a vault identifier associated with the data object; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

12. The non-transitory computer readable storage medium of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

generate, based on the data object name, the first retrieval request by;

generating a set of first level read requests for retrieving at least a decode threshold number of metadata addressing information slices, wherein the metadata addressing information includes addressing information regarding storage of the metadata within the DSN, wherein the metadata addressing information was dispersed storage error encoded to produce a set of metadata addressing information slices, and wherein the decode threshold number of metadata addressing information slices represents a minimum number of metadata addressing information slices of the set of metadata addressing information slices that is required to recover the metadata addressing information; and

decode the at least a decode threshold number of metadata addressing information slices to recover the metadata addressing information.

13. The non-transitory computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the second retrieval request by:

generating, based on the metadata addressing information, a set of second level read requests for retrieving at least a decode threshold number of metadata slices, wherein the metadata includes addressing information regarding storage of a plurality of sets of encoded data slices of the data object within the DSN, wherein the metadata was dispersed storage error encoded to produce a set of metadata slices, and wherein the decode threshold number of metadata slices represents a minimum number of metadata slices of the set of metadata slices that is required to recover the metadata.

14. The non-transitory computer readable storage medium of claim 13 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

decode the at least a decode threshold number of metadata slices to recover the metadata.

15. The non-transitory computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the second retrieval request by:

extracting a generation identifier and an object identifier from the metadata addressing information, the generation identifier indicating one of the plurality of storage generations;

determining a vault identifier associated with the data object;

using the generation identifier in a generation identifier field of the read request format of the DSN;

using the object identifier in an object identifier field of the read request format of the DSN; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

16. The non-transitory computer readable storage medium of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to generate the third retrieval request by:

generating, based on the metadata, at least one set of third level read requests for retrieving at least a decode threshold number of encoded data slices, wherein the data object was dispersed storage error encoded to produce a plurality of sets of encoded data slices, and wherein the decode threshold number of encoded data slices represents a minimum number of encoded data slices of a set of the plurality of sets of encoded data slices that is required to recover the portion of the data object.

17. A computing device of a group of computing devices of a dispersed storage network (DSN), the DSN including a plurality of storage generations, each of the plurality of storage generations utilizing a plurality of storage units, the computing device comprises:

an interface;

a local memory; and

a processing module operably coupled to the interface and the local memory, wherein the processing module functions to;

generate, based on a data object name, a first retrieval request for retrieving metadata addressing information, wherein the first retrieval request is formatted in accordance with a read request format of the DSN;

generate, based on retrieved metadata addressing information, a second retrieval request for retrieving metadata, wherein the second retrieval request is formatted in accordance with the read request format of the DSN; and

generate, based on retrieved metadata, a third retrieval request for retrieving at least a portion of a data object associated with the data object name, wherein the third retrieval request is formatted in accordance with the read request format of the DSN, wherein at least two of the metadata addressing information, the metadata, and the data object are stored in differing storage generations of the plurality of storage generations.

18. The computing device of claim 17, wherein the processing module functions to generate the first retrieval request by:

performing a deterministic function on the data object name to produce a digital value;

using a first portion of the digital value as a generation identifier in a generation identifier field of the read request format of the DSN, the generation identifier indicating one of the plurality of storage generations; and

using a second portion of the digital value as an object identifier of the read request format of the DSN.

19. The computing device of claim 18, wherein the processing module functions to generate the first retrieval request by:

determining a vault identifier associated with the data object; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

20. The computing device of claim 17, wherein the processing module further functions to:

generate, based on the data object name, the first retrieval request by;

generating a set of first level read requests for retrieving at least a decode threshold number of metadata addressing information slices, wherein the metadata addressing information includes addressing information regarding storage of the metadata within the DSN, wherein the metadata addressing information was dispersed storage error encoded to produce a set of metadata addressing information slices, and wherein the decode threshold number of metadata addressing information slices represents a minimum number of metadata addressing information slices of the set of metadata addressing information slices that is required to recover the metadata addressing information; and

decode the at least a decode threshold number of metadata addressing information slices to recover the metadata addressing information.

21. The computing device of claim 17, wherein the processing module functions to generate the second retrieval request by:

generating, based on the metadata addressing information, a set of second level read requests for retrieving at least a decode threshold number of metadata slices, wherein the metadata includes addressing information regarding storage of a plurality of sets of encoded data slices of the data object within the DSN, wherein the metadata was dispersed storage error encoded to produce a set of metadata slices, and wherein the decode threshold number of metadata slices represents a minimum number of metadata slices of the set of metadata slices that is required to recover the metadata.

22. The computing device of claim 21, wherein the processing module further functions to:

decode the at least a decode threshold number of metadata slices to recover the metadata.

23. The computing device of claim 17, wherein the processing module functions to generate the second retrieval request by:

extracting a generation identifier and an object identifier from the metadata addressing information, the generation identifier indicating one of the plurality of storage generations;

determining a vault identifier associated with the data object;

using the generation identifier in a generation identifier field of the read request format of the DSN;

using the object identifier in an object identifier field of the read request format of the DSN; and

using the vault identifier in a vault identifier field of the read request format of the DSN.

24. The computing device of claim 17, wherein the processing module functions to generate the third retrieval request by:

generating, based on the metadata, at least one set of third level read requests for retrieving at least a decode threshold number of encoded data slices, wherein the data object was dispersed storage error encoded to produce a plurality of sets of encoded data slices, and wherein the decode threshold number of encoded data slices represents a minimum number of encoded data slices of a set of the plurality of sets of encoded data slices that is required to recover the portion of the data object.