System and method for scalable reference management in a deduplication based storage system

• US 8,392,376 B2
• Filed: 09/03/2010
• Issued: 03/05/2013
• Est. Priority Date: 09/03/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Guo, Fanglu
• Primary Examiner(s): Ly, Anh
• Application Number:
  US12/875,815
• Publication Number:
  US 20120059800A1
• Time in Patent Office: 914 Days
• Field of Search: 707/640, 707/664, 707/726, 707/800, 707/E17.011, 707/999.204, 707/795, 707/E17.007, 711/111, 711/112, 711/162, 711/E12.019
• US Class Current: 707/664
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

A system and method for managing a resource reclamation reference list at a coarse level. A storage device is configured to store a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects. A storage container reference list is maintained, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container. In response to detecting deletion of a given file that references an object within a particular storage container of the storage containers, a server is configured to update the storage container reference list by removing from the storage container reference list an identification of the given file. A reference list associating segment objects with files that reference those segment objects may not be updated response to the deletion.

Claims

1. A system for managing data storage, comprising:

a storage device configured to store file data as a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

a server, wherein in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers, and (2) determining a number of files referencing the particular container has not fallen to a threshold level, the server is configured to update a storage container reference list of the particular container by removing from the storage container reference list an identification of the given file;

wherein subsets of the plurality of files are grouped into backups, and wherein for each of the storage containers the storage container reference list identifies which backups of the backups include a file that reference a segment object within the given storage container.

2. The system as recited in claim 1, wherein the server is further configured to maintain a segment object reference list, wherein for a given segment object stored in the storage device, the segment object reference list identifies which files of the plurality of files reference the given segment object.

3. The system as recited in claim 2, wherein in response to determining a number of files referencing the particular container has fallen to the threshold level, the server is configured to update the segment object reference list instead of the container reference list responsive to detecting the file deletion.

4. The system as recited in claim 3, wherein when updating the segment object reference list, the server is configured to delete from the segment object reference list entries for segment objects referenced by the given file.

5. The system as recited in claim 3, wherein the server is further configured to determine a value of the threshold based at least in part on storage utilization of the storage device and a size of the storage container reference list.

6. The system as recited in claim 2, wherein in response to detecting said deletion and determining a number of files references the particular container has not fallen to a threshold level, the server does not update the segment object reference list.

7. The system as recited in claim 1, wherein the storage container reference list includes entries associated with a group of containers at a coarse level, with a separate coarse level entry for each file that references at least one segment object stored within said group of containers.

8. A computer implemented method comprising:

storing in a storage device a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

maintaining a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

removing from the storage container reference list an identification of the given file, in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers and (2) determining a number of files referencing the particular container has not fallen to a threshold level;

wherein subsets of the plurality of files are grouped into backups, and wherein for each of the storage containers the storage container reference list identifies which backups of the backups include a file that reference a segment object within the given storage container.

9. The method as recited in claim 8, further comprising maintaining a segment object reference list, wherein for a given segment object stored in the storage device, the segment object reference list identifies which files of the plurality of files reference the given segment object.

10. The method as recited in claim 9, wherein in response to determining a number of files referencing the particular container has fallen to the threshold level, the method comprises updating the segment object reference list instead of the container reference list responsive to detecting the file deletion.

11. The method as recited in claim 10, wherein when updating the segment object reference list, the method comprises deleting from the segment object reference list entries for segment objects referenced by the given file.

12. The method as recited in claim 9, wherein in response to detecting said deletion and determining a number of files references the particular container has not fallen to a threshold level, the method does not update the segment object reference list.

13. The method as recited in claim 8, wherein the storage container reference list includes entries associated with a group of containers at a coarse level, with a separate coarse level entry for each file that references at least one segment object stored within said group of containers.

14. A computer readable storage medium comprising program instructions, wherein when executed the program instructions are operable to:

store in a storage device a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

maintain a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

remove from the storage container reference list an identification of the given file, in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers and (2) determining a number of files referencing the particular container has not fallen to a threshold level;

wherein subsets of the plurality of files are grouped into backups, and wherein for each of the storage containers the storage container reference list identifies which backups of the backups include a file that reference a segment object within the given storage container.

15. The computer readable storage medium as recited in claim 14, wherein when executed the program instructions are further operable to maintain a segment object reference list, wherein for a given segment object stored in the storage device, the segment object reference list identifies which files of the plurality of files reference the given segment object.

16. The computer readable storage medium as recited in claim 15, wherein in response to determining a number of files referencing the particular container has fallen to the threshold level, the program instructions are further operable to update the segment object reference list instead of the container reference list responsive to detecting the file deletion.

17. The computer readable storage medium as recited in claim 14, wherein in response to detecting said deletion and determining the number of files referencing the given container has not fallen to said threshold, the segment object reference list is not updated.

18. A system for managing data storage, comprising:

a storage device configured to store file data as a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

a server, wherein in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers, and (2) determining a number of files referencing the particular container has not fallen to a threshold level, the server is configured to update a storage container reference list of the particular container by removing from the storage container reference list an identification of the given file;

wherein the storage container reference list includes entries associated with a group of containers at a coarse level, with a separate coarse level entry for each file that references at least one segment object stored within said group of containers.

19. A computer implemented method comprising:

storing in a storage device a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

maintaining a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

removing from the storage container reference list an identification of the given file, in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers and (2) determining a number of files referencing the particular container has not fallen to a threshold level;

wherein the storage container reference list includes entries associated with a group of containers at a coarse level, with a separate coarse level entry for each file that references at least one segment object stored within said group of containers.

20. A computer readable storage medium comprising program instructions, wherein when executed the program instructions are operable to:

store in a storage device a plurality of storage objects in a plurality of storage containers, each of said storage containers being configured to store a plurality of said storage objects, the storage objects representing a partitioned portion of a file;

maintain a storage container reference list, wherein for each of the storage containers the storage container reference list identifies which files of a plurality of files reference a storage object within a given storage container; and

remove from the storage container reference list an identification of the given file, in response to (1) detecting deletion of a given file that references an object within a particular storage container of the storage containers and (2) determining a number of files referencing the particular container has not fallen to a threshold level;

wherein the storage container reference list includes entries associated with a group of containers at a coarse level, with a separate coarse level entry for each file that references at least one segment object stored within said group of containers.