Compacting dispersed storage space

• US 9,552,305 B2
• Filed: 10/11/2011
• Issued: 01/24/2017
• Est. Priority Date: 11/01/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Volvovski, Ilya, Resch, Jason K., Baptist, Andrew, Dhuse, Greg
• Primary Examiner(s): Chace, Christian P
• Assistant Examiner(s): LOONAN, ERIC T
• Application Number:
  US13/270,571
• Publication Number:
  US 20130145116A1
• Time in Patent Office: 1,932 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• 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 begins by a processing module identifying a first storage space zone that includes a plurality of deleted encoded data slices and a plurality of active encoded data slices. The method continues with the processing module determining to compact the first storage space zone based on a function of the plurality of deleted encoded data slices and the plurality of active encoded data slices. The method continues with the processing module retrieving the plurality of active encoded data slices from the first storage space zone, identifying a second storage space zone, storing the plurality of active encoded data slices in the second storage space zone, and erasing the plurality of deleted encoded data slices and the plurality of active encoded data slices from the first storage space zone when the first storage space zone is to be compacted.

Claims

1. A method for execution by a storage unit of a dispersed storage network (DSN), the method comprises:

identifying a first storage space zone of a plurality of storage space zones for potential compacting, wherein encoded data slices of an encoded data file are stored in at least one of first and second log files of a plurality of log files, and wherein a slice location table records storage of the encoded data slices in the at least one of the first and second log files;

executing a compacting function for the first and second log files wherein the compacting function comprises;

determining a total storage value (T) corresponding to total storage space of each of the first and second log files;

determining a deleted slice value (D) corresponding to a plurality of deleted storage spaces for each of the first and second log files;

determining an active slice value (W) corresponding to storage space occupied by the encoded data slices for each of the first and second log files;

determining an available storage value (E) corresponding to a available storage space for each of the first and second log files;

determining a compacting value (p) based on the total storage value, the deleted slice value, the active slice value, and the available storage value, wherein p=(D/(D+W))^(f*E/T), wherein f is a factor for increasing steepness of p; and

interpreting the compacting value to determine whether to compact the first storage space zone; and

when the compacting function indicates compacting of at least one of the first and second log files;

identifying one or more other log files of the plurality of log files that can store the encoded data slices stored in the at least one of the first and second log files;

storing the encoded data slices in the one or more other log files; and

updating the slice location table to indicate the storing of the encoded data slices in the one or more other log files.

2. The method of claim 1, wherein the identifying the one or more other log files comprises:

determining data size of the encoded data slices;

determining whether a third log file of the first storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices; and

when the third log file includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices, selecting the third log file.

3. The method of claim 1, wherein the method further comprises:

receiving a message to delete the encoded data slices;

identifying storage space of the first storage space zone storing the encoded data slices; and

updating the slice location table to indicate that the encoded data slices are deleted from the storage space and that the storage space is free.

4. The method of claim 1, wherein the identifying the one or more other log files comprises:

determining data size of the encoded data slices;

determining whether one or more log files of a second storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices; and

when the one or more log files of the second storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices, selecting the one or more log files of the second storage space zone.

5. A storage unit of a dispersed storage network, wherein the storage unit comprises:

an interface;

a memory; and

a processing module configured to;

identify a first storage space zone of a plurality of storage space zones for potential compacting, wherein encoded data slices of an encoded data file are stored in at least one of first and second log files of a plurality of log files, and wherein a slice location table records storage of the encoded data slices in the at least one of the first and second log files;

execute a compacting function for the first and second log files wherein the compacting function comprises;

determining a total storage value (T) corresponding to total storage space of each of the first and second log files;

determining a deleted slice value (D) corresponding to a plurality of deleted storage spaces for each of the first and second log files;

determining an active slice value (W) corresponding to storage space occupied by the encoded data slices for each of the first and second log files;

determining an available storage value (E) corresponding to a available storage space for each of the first and second log files;

determining a compacting value (p) based on the total storage value, the deleted slice value, the active slice value, and the available storage value, wherein p=(D/(D+W))^(f*E/T), wherein f is a factor for increasing steepness of p; and

interpreting the compacting value to determine whether to compact the first storage space zone; and

when the compacting function indicates compacting of at least one of the first and second log files;

identify one or more other log files of the plurality of log files that can store the encoded data slices stored in the at least one of the first and second log files;

store the encoded data slices in the one or more other log files; and

update the slice location table to indicate the storing of the encoded data slices in the one or more other log files.

6. The storage unit of claim 5, wherein the processing module is configured to identify the one or more other log files comprises:

determining data size of the encoded data slices;

determining whether a third log file of the first storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices; and

when the third log file includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices, selecting the third log file.

7. The storage unit of claim 5, wherein the processing module is further configured to:

receive, via the interface, a message to delete the encoded data slices;

identify storage space of the first storage space zone storing the encoded data slices; and

update the slice location table to indicate that the encoded data slices are deleted from the storage space and that the storage space is free.

8. The storage unit of claim 5, wherein the processing module is configured to identify the one or more other log files comprises:

determining data size of the encoded data slices;

determining whether one or more log files of a second storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices; and

when the one or more log files of the second storage space zone includes available and contiguous storage space that is equal to or exceeds the data size of the encoded data slices, selecting the one or more log files of the second storage space zone.