Computer storage deduplication

• US 10,496,670 B1
• Filed: 05/19/2010
• Issued: 12/03/2019
• Est. Priority Date: 01/21/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Clements, Austin, Ahmad, Irfan, Li, Jinyuan, Vilayannur, Murali
• Primary Examiner(s): Featherstone, Mark D
• Assistant Examiner(s): Gmahl, Navneet
• Application Number:
  US12/783,392
• Time in Patent Office: 3,485 Days
• Field of Search: 707610, 707661
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/656 Address space sharing
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

Decentralized deduplication operations in a computer system employ a hash index that is a variant of a B+ tree to support both efficient sequential updates as well as efficient random updates. Sequential update is selected when deduplication is infrequently performed, such as on the order of days, and random update is selected when deduplication is performed more frequently, such as on the order of seconds. More frequent deduplication may be beneficial during periods when large amounts of temporary duplicate data are created, and the system may not have enough storage space to accommodate the temporary spike in demand.

Claims

1. A method of performing deduplication operations in a computer system having multiple host systems connected to a common storage system, the method comprising:

maintaining a hierarchical data structure including a low-level data structure and one or more higher level data structures, each containing hash values and being maintained as a sorted data structure according to the hash values,

wherein the low-level data structure contains hash values of storage blocks and the one or more higher level data structures contain some of, but not all of, the hash values in the low-level data structure that are to be used when locating hash values in the low-level data structure or adding new hash values into the low-level data structure; and

at each host system, tracking write operations to the common storage system during a period of time and asynchronously performing deduplication operations on storage blocks that are written in connection with the write operations using the hierarchical data structure,

wherein the low-level data structure is divided into pages including a first page and a second page, and one of the higher-level data structures that is at a next higher level than the low-level data structure contains a first hash value contained in the first page, a first pointer to the first page, a second hash value contained in the second page, and a second pointer to the second page.

2. The method of claim 1, wherein the deduplication operations include updating the low-level data structure.

3. The method of claim 2, further comprising:

at each host system, prior to performing the deduplication operations, determining whether a sequential update is to be performed on the low-level data structure or a random update is to be performed on the low-level data structure.

4. The method of claim 3, wherein the sequential update is determined if the period of time is greater than a threshold value, and the random update is determined otherwise.

5. The method of claim 2, wherein the low-level data structure is updated with reference to hash values of the storage blocks that are written.

6. The method of claim 5, further comprising:

determining a location within the low-level data structure associated with a storage block that is written using the one or more higher level data structures.

7. The method of claim 1, wherein some of the pages include a free space region at the end thereof.

8. The method of claim 1, further comprising:

updating one of the pages of the low-level data structure independently of the other pages of the low-level data structure.

9. The method of claim 8, further comprising:

determining whether the updating causes the page to overflow, wherein, in the case of an overflow, the updated page is divided into two parts and the first part is written into the original location of the updated page and the second part is appended to the end of the low-level data structure, and the next higher-level data structure is updated.

10. A non-transitory computer readable storage medium having stored therein instructions for causing a computer system to maintain a hierarchical data structure including a low-level data structure and one or more higher level data structures, each containing hash values and being maintained as a sorted data structure according to the hash values, and to track write operations to a storage system during a period of time and asynchronously perform deduplication operations on storage blocks that are written in connection with the write operations using the hierarchical data structure,

wherein the low-level data structure contains hash values of storage blocks and the one or more higher level data structures contain some of, but not all of, the hash values in the low-level data structure that are to be used when locating hash values in the low-level data structure or adding new hash values into the low-level data structure, and

wherein the low-level data structure is divided into pages including a first page and a second page, and one of the higher-level data structures that is at a next higher level than the low-level data structure contains a first hash value contained in the first page, a first pointer to the first page, a second hash value contained in the second page, and a second pointer to the second page.

11. The computer readable storage medium of claim 10, wherein the deduplication operations include updating the low-level data structure with reference to hash values of the storage blocks that are written.

12. The computer readable storage medium of claim 10, wherein the instructions further cause the computer system to determine a location within the low-level data structure associated with a storage block that is written using the one or more higher level data structures.

13. The computer readable storage medium of claim 10, wherein some of the pages include a free space region at the end thereof.

14. The computer readable storage medium of claim 10, wherein the instructions further cause the computer system to update one of the pages of the low-level data structure independently of the other pages of the low-level data structure.

15. The computer readable storage medium of claim 14, wherein the instructions further cause the computer system to determine whether the update causes the page to overflow, and wherein, in the case of an overflow, the updated page is divided into two parts and the first part is written into the original location of the updated page and the second part is appended to the end of the low-level data structure, and the next higher-level data structure is updated.

16. A computer system comprising:

a plurality of host systems connected to a common storage system,

wherein each host system is programmed to track, via one or more processors, write operations to the common storage system during a period of time and asynchronously perform deduplication operations on storage blocks that are written in connection with the write operations using a hierarchical data structure that is stored in the common storage system,

wherein the hierarchical data structure includes a low-level data structure and one or more higher level data structures, each containing hash values and being maintained as a sorted data structure according to the hash values, the low-level data structure containing hash values of storage blocks and the one or more higher level data structures containing some of, but not all of, the hash values in the low-level data structure that are to be used when locating hash values in the low-level data structure or adding new hash values into the low-level data structure, and

wherein the low-level data structure is divided into pages including a first page and a second page, and one of the higher-level data structures that is at a next higher level than the low-level data structure contains a first hash value contained in the first page, a first pointer to the first page, a second hash value contained in the second page, and a second pointer to the second page.

17. The computer system of claim 16, wherein some of the pages include a free space region at the end thereof.