Computer storage deduplication

• US 10,437,865 B1
• Filed: 05/19/2010
• Issued: 10/08/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): Ehichioya, Irete F
• Assistant Examiner(s): Johnson, Johnese T
• Application Number:
  US12/783,408
• Time in Patent Office: 3,429 Days
• Field of Search: None
• 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 virtualized computer environment having multiple storage devices employ a hash index for each storage device. When an image of a virtual machine is selected to be migrated from a source storage device to a destination storage device, hash values representing content of the storage blocks of the virtual machine are compared with hash entries of the destination hash index. Storage blocks of the virtual machine that have matching hash entries in the destination hash index are not transferred as part of the migration process so that the overall migration process can be accelerated.

Claims

1. A method of migrating an image of a virtual machine stored in a first storage system to a second storage system, said method being carried out by a host of the virtual machine, the host being connected to the first and second storage systems over a network, comprising:

retrieving entries of a first index that is stored in the first storage system and maintained for used storage blocks of the first storage system, wherein the used storage blocks of the first storage system include storage blocks of the virtual machine and the retrieved entries correspond to the storage blocks of the virtual machine;

comparing the retrieved entries with entries of a second index that is stored in the second storage system and maintained for used storage blocks of the second storage system; and

initiating a migration process of the storage blocks of the virtual machine from the first storage system to the second storage system based on relative workloads of the first storage system and the second storage system, and

carrying out the migration process based on the comparison of the retrieved entries with the entries of the second index, and wherein storage blocks of the first storage system corresponding to the retrieved entries that do not match entries of the second index are transferred to the second storage system, and storage blocks of the first storage system corresponding to the retrieved entries that match entries of the second index are not transferred to the second storage system.

2. The method of claim 1, further comprising:

identifying entries of the first index associated with the storage blocks of the virtual machine that match entries of the second index, wherein said migration process includes transferring the storage blocks of the virtual machine that are not associated with the identified entries and not transferring the storage blocks of the virtual machine that are associated with the identified entries.

3. The method of claim 1, further comprising:

identifying entries of the first index associated with the storage blocks of the virtual machine that match entries of the second index,

wherein said migration process includes transferring a first set of storage blocks of the virtual machine prior to completion of said identifying and then transferring a second set of storage blocks of the virtual machine after completion of said identifying until completion of said migrating, and

wherein the second set of storage blocks do not include the storage blocks of the virtual machine that are associated with the identified entries.

4. The method of claim 1, further comprising:

maintaining a Bloom filter for the entries in the second index;

using said Bloom filter, determining a set of storage blocks of the virtual machine that are not stored in the second storage system; and

transferring the set of storage blocks of the virtual machine to the second storage system.

5. The method of claim 4, further comprising:

identifying entries of the first index associated with the storage blocks of the virtual machine that match entries of the second index, wherein said transferring is carried out prior to completion of said identifying.

6. The method of claim 1, wherein a computer system hosting the virtual machine has access to the first index and the second index.

7. The method of claim 1, wherein the first storage system is implemented on a first storage device and the second storage system is implemented on a second storage device that is physically separate from the first storage device.

17. The method of claim 1,

wherein the first index is maintained prior to the migration process by a first host and a second host to cooperatively implement deduplication in the first storage system, and

wherein the first host and the second host are prevented from concurrently accessing the same storage blocks of the first storage system.

18. The method of claim 1, wherein, before said migration process, data storage for the virtual machine is provided by the first storage system, and after said migration process, data storage for the virtual machine is provided by the second storage system.

19. The method of claim 1, wherein the migrated image of the virtual machine on the second storage system comprises portions of a pool file having metadata block pointers referring to storage blocks of the second storage system corresponding to the matching entries of the second index.

8. A method of migrating an image of a virtual machine stored in a first storage system to a second storage system, said method being carried out by a host of the virtual machine, the host being connected to the first and second storage systems over a network, comprising:

starting a migration process of the virtual machine from the first storage system to the second storage system based on relative workloads of the first storage system and the second storage system;

identifying a set of blocks of the virtual machine that are not stored in the second storage system and are stored in the first storage system; and

transferring the set of blocks from the first storage system to the second storage system, wherein storage blocks of the first storage system corresponding to entries of a first index in the first storage system that do not match entries of a second index in the second storage system are transferred to the second storage system, and storage blocks of the first storage system corresponding to the entries of the first index that match entries of the second index are not transferred to the second storage system.

9. The method of claim 8, further comprising:

maintaining the first index in the first storage system, the first index including entries representing contents of storage blocks of the virtual machine; and

maintaining the second index in the second storage system, the second index including entries representing contents of storage blocks stored in the second storage system, wherein said identifying includes comparing the entries in the first index with the entries in the second index.

10. The method of claim 8, further comprising:

maintaining a Bloom filter for storage blocks stored in the second storage system, wherein the set of blocks of the virtual machine that are not stored in the second storage system is identified using said Bloom filter.

11. The method of claim 10, wherein the Bloom filter is maintained by the second storage system and updated each time new content is written into storage blocks of the second storage system.

12. The method of claim 11, further comprising:

identifying another set of blocks of the virtual machine that are not stored in the second storage system during the migration process; and

transferring said another set of blocks of the virtual machine from the first storage system to the second storage system during the migration process.

13. A computer system comprising:

a host computer for a virtual machine;

a source storage device having an image of the virtual machine stored therein and including a first index; and

a destination storage device that is physically separate from the source storage device to which the image of the virtual machine is to be migrated, wherein the destination storage device includes a second index, wherein the host computer is connected to the source storage device and the destination storage device over a network and is programmed to;

initiate a migration process for the virtual machine based on relative workloads of the source storage device and the destination storage device, and compare entries associated with the virtual machine stored in the first index with entries of the second index,

identify matching entries, and

transfer those storage blocks of the virtual machine stored in the source storage device associated with the non-matching entries to the destination storage device, and not transfer those storage blocks of the virtual machine stored in the source storage device associated with matching entries to the destination storage device.

14. The computer system of claim 13, further comprising:

another host computer coupled to the destination storage device and configured to run the virtual machine after the migration process, wherein said another host computer is programmed to determine the subset of the storage blocks of the virtual machine to be transferred.

15. The computer system of claim 14,

wherein the source storage device includes a first index and the destination storage device includes a second index, and

wherein said another host computer is programmed to compare entries associated with the virtual machine stored in the first index with entries of the second index, identify matching entries, and communicate the matching entries to the host computer.

16. The computer system of claim 13, wherein the destination storage device includes a Bloom filter that is updated as new content is written into storage blocks of the destination storage device, and the subset of the storage blocks of the virtual machine to be transferred is identified using the Bloom filter.