File deduplication using storage tiers

• US 8,548,953 B2
• Filed: 11/11/2008
• Issued: 10/01/2013
• Est. Priority Date: 11/12/2007
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Wong, Thomas K., Vogel, Ron S.
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US12/268,573
• Publication Number:
  US 20090204649A1
• Time in Patent Office: 1,785 Days
• Field of Search: 707/200, 707/203, 707/204, 707/205, 707/206, 707/639, 707/649, 707/664, 707/696, 707/698, 707/633, 707/640, 707/641, 707/692, 711/161, 711/162
• US Class Current: 707/664
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files

Abstract

A method and apparatus for removing duplicated data in a file system utilizing the concept of storage tiers. A synthetic namespace is created via file virtualization, and is comprised of one or more file systems. Deduplication is applied at the namespace level and on all of the file systems comprising the synthetic namespace. All files in a file system in a higher storage tier whose contents are identical to at least one other file in the synthetic namespace are moved to a destination file system in a lower storage tier. For each set of duplicated files that are moved from the original servers, a single instance copy of the file is left behind as a mirror copy. Read access to a duplicated file is redirected to its mirror copy. When the first write to a duplicated file is received, the association from the duplicated file stored in the destination server to its mirror copy that is stored in the origin server is discarded. Access to the “modified” duplicated file will then resume normally from the destination server.

Claims

1. A method of deduplicating files, the method comprising:

accessing, with a file virtualization device, a virtualized environment including one or more primary storage servers operating as a primary storage tier and storing a first plurality of files and one or more secondary storage servers operating as a secondary storage tier and storing a second plurality of files comprising at least a plurality of files not included in the first plurality of files, wherein a global namespace is associated with the first and second pluralities of files stored in the one or more primary and secondary storage servers;

identifying, with the file virtualization device, a subset of the first plurality of files that are stored in the primary storage tier and have identical file contents and storing a copy of only the subset of files in the secondary storage tier;

storing, with the file virtualization device, a single copy of the contents of each of the subset of files in the primary storage tier and deleting all other files having identical file contents from the primary storage tier; and

storing, with the file virtualization device, metadata associating each of the copies of the subset of files stored in the secondary storage tier with a corresponding one of the single copies stored in the primary storage tier.

2. A method according to claim 1, wherein identifying the subset of files that are stored in the primary storage tier and have identical file contents comprises:

computing, for each of the plurality of files, a hash value based on contents of the file; and

identifying files having identical file contents based on a comparison of the hash values.

3. A method according to claim 1, wherein storing the single copy of the contents comprises copying the file contents to a designated mirror server of the primary storage tier.

4. A method according to claim 1, further comprising:

upon a read access to one of the plurality of files, directing, with the file virtualization device, the read access to the single copy of the contents stored in the primary storage tier.

5. A method according to claim 1, further comprising, upon a write access to one of the plurality of files:

breaking, with the file virtualization device, the association between the copy in the secondary storage tier and the corresponding single copy of the contents stored in the primary storage tier;

modifying, with the file virtualization device, the copy stored in the secondary storage tier; and

migrating, with the file virtualization device, the modified copy from the secondary storage tier to the primary storage tier based on a migration policy.

6. A method according to claim 1, further comprising deduplicating, with the file virtualization device, a selected file in the primary storage tier comprising:

determining whether contents of the selected file match contents of a previously deduplicated file having a corresponding single copy stored in the primary storage tier;

when the contents of the selected file match the contents of a previously deduplicated file, deduplicating the selected file;

otherwise determining whether the contents of the selected file match the contents of a non-duplicate file in the primary storage tier; and

when the contents of the selected file match the contents of a non-duplicate file, deduplicating both the selected file and the non-duplicate file.

7. A method according to claim 6, wherein determining whether the contents of the selected file match the contents of a non-duplicate file in the primary storage tier comprises:

maintaining a list of non-duplicate files in the primary storage tier, the list including a distinct hash value for each non-duplicate file;

comparing a hash value associated with the selected file to the hash values associated with the non-duplicate files in the list; and

when the contents of the selected file do not match the contents of any non-duplicate file, adding the selected file to the list of non-duplicate files.

8. A virtualization apparatus for deduplicating files, the apparatus comprising:

at least one communication interface for communicating with one or more primary and secondary storage servers; and

at least one of configurable hardware logic configured to be capable of implementing or a processor configured to execute program instructions stored in a memory comprising;

accessing a virtualized environment including the one or more primary storage servers operating as a primary storage tier and storing a first plurality of files and the one or more secondary storage servers operating as a secondary storage tier and storing a second plurality of files comprising at least a plurality of files not included in the first plurality of files, wherein a global namespace is associated with the first and second pluralities of files stored in the one or more primary and secondary storage servers;

identifying a subset of the accessed files that are stored in the primary storage tier and have identical file contents and storing a copy of only the subset of files in the secondary storage tier;

storing a single copy of the contents of each of the subset of files in the primary storage tier and deleting all other files having identical file contents from the primary storage tier; and

storing metadata associating each of the copies of the subset of files stored in the secondary storage tier with a corresponding one of the single copies stored in the primary storage tier.

9. An apparatus according to claim 8, wherein identifying the subset of files that are stored in the primary storage tier and have identical file contents further comprises:

computing, for each of the plurality of files, a hash value based on contents of the file; and

identifying files having identical contents based on a comparison of the hash values.

10. Apparatus according to claim 8, wherein storing the single copy of the contents further comprises copying the file contents to a designated mirror server of the primary storage tier.

11. An apparatus according to claim 8, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising upon a read access to one of the plurality of files, directing the read access to the single copy of the contents stored in the primary storage tier.

12. An apparatus according to claim 8, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising upon a write access to one of the plurality of files:

breaking the association between the copy in the secondary storage tier and the corresponding single copy of the contents stored in the primary storage tier;

modifying the copy stored in the secondary storage tier; and

migrating the modified copy from the secondary storage tier to the primary storage tier based on a migration policy.

13. An apparatus according to claim 8, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising deduplicating a selected file in the primary storage tier comprising:

determining whether contents of the selected file match contents of a previously deduplicated file having a corresponding single copy stored in the primary storage tier;

when the contents of the selected file match the contents of a previously deduplicated file, deduplicating the selected file;

otherwise determining whether the contents of the selected file match the contents of a non-duplicate file in the primary storage tier; and

when the contents of the selected file match the contents of a non-duplicate file, deduplicating both the selected file and the non-duplicate file.

14. An apparatus according to claim 13, wherein determining whether the contents of the accessed file match the contents of a non-duplicate file in the primary storage tier further comprises:

maintaining a list of non-duplicate files in the primary storage tier, the list including a distinct hash value for each non-duplicate file;

comparing a hash value associated with the selected file to the hash values associated with the non-duplicate files in the list; and

when the contents of the selected file do not match the contents of any non-duplicate file, adding the selected file to the list of non-duplicate files.

15. A system that deduplicates files, the system comprising:

one or more primary storage servers operating as a primary storage tier and storing a first plurality of files and one or more secondary storage servers operating as a primary storage tier and storing a second plurality of files comprising at least a plurality of files not included in the first plurality of files, the storage servers storing the first and second pluralities of files in a virtualized environment, wherein a global namespace is associated with the first and second pluralities of files stored in the one or more primary and secondary storage servers;

a file virtualization device including at least one of configurable hardware logic configured to be capable of implementing or a processor configured to execute program instructions stored in a memory comprising;

identifying a subset of the plurality of files that are stored in the primary storage tier and have identical file contents and storing a copy of only the subset of files in the secondary storage tier;

storing a single copy of the contents of each of the subset of files in the primary storage tier and deleting all other files having identical file contents from the primary storage tier; and

storing metadata associating each of the copies of the subset of files stored in the secondary storage tier with a corresponding one of the single copies stored in the primary storage tier.

16. A system according to claim 15, wherein identifying the subset of files that are stored in the primary storage tier and have identical file contents further comprises:

computing, for each of the plurality of files, a hash value based on contents of the file; and

identifying files having identical contents based on a comparison of the hash values.

17. A system according to claim 15, wherein storing the single copy of the contents further comprises copying the file contents to a designated mirror server of the primary storage tier.

18. A system according to claim 15, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising upon a read access to one of the plurality of files, directing the read access to the single copy of the contents stored in the primary storage tier.

19. A system according to claim 15, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising upon a write access to one of the plurality of files:

breaking the association between the copy in the secondary storage tier and the corresponding single copy of the contents stored in the primary storage tier;

modifying the copy stored in the secondary storage tier; and

migrating the modified copy from the secondary storage tier to the primary storage tier based on a migration policy.

20. A system according to claim 15, wherein at least one of configurable hardware logic further configured to be capable of implementing or the processor is further configured to execute program instructions stored in a memory further comprising deduplicating a selected file in the primary storage tier comprising:

determining whether contents of the selected file match contents of a previously deduplicated file having a corresponding single copy stored in the primary storage tier;

when the contents of the selected file match the contents of a previously deduplicated file, deduplicating the selected file;

otherwise determining whether the contents of the selected file match the contents of a non-duplicate file in the primary storage tier; and

when the contents of the selected file match the contents of a non-duplicate file, deduplicating both the selected file and the non-duplicate file.

21. A system according to claim 20, wherein determining whether the contents of the accessed file match the contents of a non-duplicate file in the primary storage tier further comprises:

maintaining a list of non-duplicate files in the primary storage tier, the list including a distinct hash value for each non-duplicate file;

comparing a hash value associated with the selected file to the hash values associated with the non-duplicate files in the list; and

when the contents of the selected file do not match the contents of any non-duplicate file, adding the selected file to the list of non-duplicate files.

22. A non-transitory computer readable medium having stored thereon instructions for deduplicating files comprising machine executable code which when executed by at least one processor, causes the processor to perform steps comprising:

accessing a plurality of files stored in a virtualized environment including one or more primary storage servers operating as a primary storage tier and storing a first plurality of files and one or more secondary storage servers operating as a secondary storage tier and storing a second plurality of files comprising at least a plurality of files not included in the first plurality of files, wherein a global namespace is associated with the first and second pluralities of files stored in the one or more primary and secondary storage servers;

identifying a subset of the accessed files that are stored in the primary storage tier and have identical file contents and storing a copy of only the subset of files in the secondary storage tier;

storing a single copy of the contents of each of the subset of files in the primary storage tier and deleting all other files having identical file contents from the primary storage tier; and

storing metadata associating each of the copies of the subset of files stored in the secondary storage tier with a corresponding one of the single copies stored in the primary storage tier.

23. A non-transitory computer readable medium according to claim 22, wherein identifying the subset of files that are stored in the primary storage tier and have identical file contents further comprises:

computing, for each of the plurality of files, a hash value based on contents of the file; and

identifying files having identical contents based on a comparison of the hash values.

24. A non-transitory computer readable medium according to claim 22, wherein storing the single copy of the contents further comprises copying the file contents to a designated mirror server of the primary storage tier.

25. A non-transitory computer readable medium according to claim 22, further having stored thereon instructions that when executed by the at least one processor cause the processor to perform steps further comprising upon a read access to one of the plurality of files, directing the read access to the single copy of the contents stored in the primary storage tier.

26. A non-transitory computer readable medium according to claim 22, further having stored thereon instructions that when executed by the at least one processor cause the processor to perform steps further comprising:

breaking the association between the copy in the secondary storage tier and the corresponding single copy of the contents stored in the primary storage tier;

modifying the copy stored in the secondary storage tier; and

migrating the modified copy from the secondary storage tier to the primary storage tier based on a migration policy.

27. A non-transitory computer readable medium according to claim 22, further having stored thereon instructions that when executed by the at least one processor cause the processor to perform steps further comprising deduplicating a selected file in the primary storage tier comprising:

determining whether contents of the selected file match contents of a previously deduplicated file having a corresponding single copy stored in the primary storage tier;

when the contents of the selected file match the contents of a previously deduplicated file, deduplicating the selected file;

otherwise determining whether the contents of the selected file match the contents of a non-duplicate file in the primary storage tier; and

when the contents of the selected file match the contents of a non-duplicate file, deduplicating both the selected file and the non-duplicate file.

28. A non-transitory computer readable medium according to claim 27, wherein determining whether the contents of the accessed file match the contents of a non-duplicate file in the primary storage tier further comprises:

maintaining a list of non-duplicate files in the primary storage tier, the list including a distinct hash value for each non-duplicate file;

comparing a hash value associated with the selected file to the hash values associated with the non-duplicate files in the list; and

when the contents of the selected file do not match the contents of any non-duplicate file, adding the selected file to the list of non-duplicate files.