COMPUTER STORAGE DEDUPLICATION

• US 20100077013A1
• Filed: 01/21/2009
• Published: 03/25/2010
• Est. Priority Date: 09/11/2008
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: CLEMENTS, Austin, AHMAD, Irfan, LI, Jinyuan, VILAYANNUR, Murali
• Granted Patent: US 10,642,794 B2
• Time in Patent Office: Days
• US Class Current: 707/822
• 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 data center comprising plural computer hosts and a storage system external to said hosts is disclosed. The storage system includes storage blocks for storing tangibly encoded data blocks. Each of said hosts includes a deduplicating file system for identifying and merging identical data blocks stored in respective storage blocks into one of said storage blocks so that a first file exclusively accessed by a first host of said hosts and a second file accessed exclusively by a second host of said hosts concurrently refer to the same one of said storage blocks.

Claims

1. A data center comprising plural computer hosts and a storage system external to said hosts, said storage system including storage blocks for storing tangibly encoded data blocks, each of said hosts including a deduplicating file system for identifying and merging identical data blocks stored in respective storage blocks into one of said storage blocks so that a first file exclusively accessed by a first host of said hosts and a second file accessed exclusively by a second host of said hosts concurrently refer to the same one of said storage blocks.

2. A data center as recited in claim 1 wherein said storage system has a shared-block file tangibly encoded thereon, said shared-block file including metadata pointers to storage blocks of said storage system that are referred to by more than one metadata block pointer of said files, the file managers of said hosts cooperatively updating said shared-block file.

3. A data center as recited in claim 2 wherein said file managers update said shared-block file by successively obtaining exclusive access to said shared-block file.

4. A data center as recited in claim 3 wherein said storage system has a hash index tangibly encoded thereon, said hash index including hash-index entries assigning hash values to files and file offsets, some of said hash-index entries associating hashes of said data blocks with the storage blocks that contain those data blocks via said shared-block file, others of said hash-index entries associating hashes of said data blocks with the storage blocks that contain those data blocks via files other than said shared-block file.

5. A data center as recited in claim 1 further comprising counts tangibly encoded in said storage system, each of said counts representing a number of metadata pointers referring to a respective one of said storage blocks, said file managers cooperatively updating said counts during write operations and merge operations.

6. A manufacture comprising computer-readable storage media encoded with a file system of computer-executable instructions, said file system, when executed on a host computer system connected to a storage system managing files, including a shared-block file, encoded in said storage system, said files having tangibly encoded metadata pointers referring to storage blocks containing tangibly encoded data blocks, said shared-block file having metadata pointers referring to blocks referred to by plural of said metadata pointers, said file system including a write-log handler for updating a hash index having a shared set of entries referring to shared storage blocks indirectly through said shared-block file, and having an unshared set of entries referring to unshared storage blocks indirectly through said files other than said shared-block file, said hash index being tangibly encoded in said storage system.

7. A manufacture as recited in claim 6 wherein said file system includes a merge-request handler and said write-log handler includes a merge-request generator:

said merge-request generator, when executed, creating first merge requests associated with files encoded on said storage system that said file system does not have access to; and

said merge-request handler, when executed, handling second merge requests associated with files that said file system does have access to by making a determination whether or not data blocks are identical and merging them into a single storage block if said determination is that said data blocks are identical.

8. A manufacture as recited in claim 7 wherein said merge-request handler, when executed, handles said second merge requests by comparing a hash of block contents of a storage block pointed to by a file that said file manager does not have access to with a hash of second block contents of a storage block pointed to by a file that said file manager does have access to.

9. A manufacture as recited in claim 6 further comprising a write-event logger that creates write-log events of write operations, said write-event logger storing them on said storage system, each of said write operations involving the write of a data block to a storage block, each of said write-log events referring to the respective storage block and containing a hash of the respective data block.

10. A manufacture as recited in claim 9 wherein said index merger, while updating said merge index, attempts to match a hash stored in a write-log event with a hash previously represented in said index.

11. A method comprising:

a first file system executing on a first host computer system, said first file system managing a first write operation to a first file on a storage system by writing a first data block to a first storage block of said storage system and causing a first metadata pointer of said first file to refer to said first storage block;

a second file system executing on a second host computer system managing a second write operation to a second file on a storage system by writing second contents to a second block of said storage system and causing a second metadata pointer of said second file to refer to said second block; and

said second file manager determining whether or not said second contents are identical to said first contents; and

if said second contents are identical to said first contents, said second file manager causing said second metadata pointer to refer to said first block.

12. A method as recited in claim 11 wherein said second file system determines whether or not said second data block is identical to said first data block at least in part by comparing a first hash of said first data block with a second hash of said second data block.

13. A method as recited in claim 11 wherein said second file manager generates said second hash during said second write operation.

14. A method as recited in claim 11 wherein:

said first file manager generates a merge request referring to said first and second blocks and writes said merge request to said storage system; and

said second file manager reads said merge request from said storage system and handles said merge request, said handling involving generating said second hash after said merge request is generated.

15. A method as recited in claim 11 wherein said determining involves comparing said blocks bit-by-bit.

16. A method for deduplicating a first storage block in a file system, the method comprising:

determining if a second storage block contains content identical to the first storage block in the file system, a size of the second storage block being identical to a size of the first storage block, wherein a pointer to the first storage block being stored in an inode of a file with which the first storage block is associated with;

changing metadata of the first storage block in the inode to include a copy on write (COW) mechanism; and

purging the second storage block and changing pointers to the second storage block to point to the first storage block,

wherein, if the size of the first storage block is larger than or equal to a first block size, the first storage block and the second storage block being logically subdivided in a number of blocks of a second block size each, the first block size being larger than the second block size.

17. The method as recited in claim 16, wherein the first block size is 1 megabyte and the second block size is 4 kilobyte.

18. The method as recited in claim 16, wherein the logically subdividing of the first storage block includes storing pointers to each of the subdivided blocks in a pointer block and replacing the pointer to the first storage block in the inode with a pointer to the pointer block.

19. The method as recited in claim 18, further including setting a flag in the inode to indicate that the inode contains the pointer to the pointer block.