Reclaiming storage capacity in a dispersed storage network

• US 10,409,522 B2
• Filed: 01/10/2017
• Issued: 09/10/2019
• Est. Priority Date: 05/29/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Kazi, Asimuddin, Resch, Jason K.
• Primary Examiner(s): Schell, Joseph O
• Application Number:
  US15/402,443
• Publication Number:
  US 20170123719A1
• Time in Patent Office: 973 Days
• CPC Class Codes: G06F 11/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 Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0787 Storage of error reports, e.g. persistent data storage, storage using memory protection
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1612 where the redundant component is persistent storage
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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 an integrity processing unit includes determining to reclaim storage capacity of a DSN memory based on utilization information. Slice age information for a plurality of sets of encoded data slices stored in the DSN memory is determined, and a plurality of sets of encoded data slices are selected based on the slice age information. All encoded data slices are identified for deletion when substantially each of the selected plurality of sets includes less than or equal to a decode threshold number of encoded data slices. A subset of encoded data slices is identified for deletion when substantially each of the selected plurality of sets includes more than the decode threshold number of encoded data slices, where removal of the subset of encoded data slices results in at least the decode threshold number of encoded data slices remaining for each selected set of encoded data slices.

Claims

1. A method for execution by an integrity processing unit that includes a processor, the method comprises:

determining to reclaim storage capacity of a DSN memory based on utilization information;

determining slice age information for a plurality of sets of encoded data slices stored in the DSN memory;

selecting a plurality of sets of encoded data slices based on the slice age information;

identifying all encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes less than or equal to a decode threshold number of encoded data slices;

identifying a subset of encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes more than the decode threshold number of encoded data slices; and

facilitating deletion of the subset of encoded data slices in response to identifying the subset of encoded data slices for deletion, wherein the deletion of the subset of encoded data slices results in at least the decode threshold number of encoded data slices remaining for each set of encoded data slices of the selected plurality of sets of encoded data slices.

2. The method of claim 1, wherein the utilization information includes at least one of:

a storage capacity level or a storage utilization level.

3. The method of claim 1, wherein determining to reclaim storage capacity of a DSN memory is based on comparing a storage capacity utilization level to a storage capacity utilization level.

4. The method of claim 1, wherein the slice age information is extracted from metadata of encoded data slices.

5. The method of claim 1, wherein selecting the plurality of sets of encoded data slices includes identifying and selecting an old plurality of sets of encoded data slices associated with an oldest slice age of a plurality of stored data objects.

6. The method of claim 1, further comprising

determining a number of available encoded data slices for each of the plurality of sets of encoded data slices;

and

comparing the number of available encoded data slices to the decode threshold number of encoded data slices.

7. The method of claim 1, wherein identifying the subset of encoded data slices includes selecting encoded slices stored in different storage units for each set of encoded data slices by utilizing a round-robin selection strategy.

8. The method of claim 7, wherein the round-robin selection strategy is based on an information dispersal algorithm parameter.

9. The method of claim 1, further comprising removing the identified encoded data slices from storage.

10. The method of claim 1, further comprising generating a plurality of delete slice requests for transmission to a plurality of storage units, wherein the plurality of delete slice requests includes identifiers of the identified encoded data slices.

11. A processing system of an integrity 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;

determine to reclaim storage capacity of a DSN memory based on utilization information;

determine slice age information for a plurality of sets of encoded data slices stored in the DSN memory;

select a plurality of sets of encoded data slices based on the slice age information;

identify all encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes less than or equal to a decode threshold number of encoded data slices;

identify a subset of encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes more than the decode threshold number of encoded data slices; and

facilitate deletion of the subset of encoded data slices in response to identifying the subset of encoded data slices for deletion, wherein the deletion of the subset of encoded data slices results in at least the decode threshold number of encoded data slices remaining for each set of encoded data slices of the selected plurality of sets of encoded data slices.

12. The processing system of claim 11, wherein the utilization information includes at least one of:

a storage capacity level or a storage utilization level.

13. The processing system of claim 11, wherein determining to reclaim storage capacity of a DSN memory is based on comparing a storage capacity utilization level to a storage capacity utilization level.

14. The processing system of claim 11, wherein the slice age information is extracted from metadata of encoded data slices.

15. The processing system of claim 11, wherein selecting the plurality of sets of encoded data slices includes identifying and selecting an old plurality of sets of encoded data slices associated with an oldest slice age of a plurality of stored data objects.

16. The processing system of claim 11, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to:

determine a number of available encoded data slices for each of the plurality of sets of encoded data slices; and

compare the number of available encoded data slices to the decode threshold number of encoded data slices.

17. The processing system of claim 11, wherein identifying the subset of encoded data slices includes selecting encoded slices stored in different storage units for each set of encoded data slices by utilizing a round-robin selection strategy.

18. The processing system of claim 17, wherein the round-robin selection strategy is based on an information dispersal algorithm parameter.

19. The processing system of claim 11, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to generate a plurality of delete slice requests for transmission to a plurality of storage units, wherein the plurality of delete slice requests includes identifiers of the identified encoded data slices.

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;

determine to reclaim storage capacity of a DSN memory based on utilization information;

determine slice age information for a plurality of sets of encoded data slices stored in the DSN memory;

select a plurality of sets of encoded data slices based on the slice age information;

identify all encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes less than or equal to a decode threshold number of encoded data slices;

identify a subset of encoded data slices of the selected plurality of sets of encoded data slices for deletion when each set of the selected plurality of sets of encoded data slices includes more than the decode threshold number of encoded data slices; and

facilitate deletion of the subset of encoded data slices in response to identifying the subset of encoded data slices for deletion, wherein the deletion of the subset of encoded data slices results in at least the decode threshold number of encoded data slices remaining for each set of encoded data slices of the selected plurality of sets of encoded data slices.