Managing deduplication of stored data

• US 9,092,151 B1
• Filed: 03/13/2013
• Issued: 07/28/2015
• Est. Priority Date: 09/17/2010
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Permabit Technology Corporation (International Business Machines Corporation)
• Inventors: Floyd, Jered J., Fortson, Michael, Westerlund, Assar, Coburn, Jonathan
• Primary Examiner(s): Nguyen, Kim
• Application Number:
  US13/800,837
• Time in Patent Office: 867 Days
• Field of Search: 707/609, 707/610
• US Class Current: 1/1
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques

Abstract

In one aspect, in general, a method for managing data includes receiving, at a data deduplication engine of a computer system, data to be stored in a data storage system, computing a first value corresponding to at least one portion of the received data, determining that the first value matches a second value stored in a collection of identifiers, each identifier corresponding to a particular portion of data stored in the data storage system, each identifier comprising a computed value corresponding to the particular portion of data and including metadata indicating a location where the particular portion of data is being stored in the data storage system, and based on the determination that the first value matches a second value stored in the collection of identifiers, reallocating one or more physical locations from corresponding one or more virtual locations to different respective one or more virtual locations.

Claims

1. A method for managing data, the method comprising:

receiving, at a data deduplication engine executing on at least one processor of a computer system, data stored in a data storage system in communication with the computer system,

wherein the data storage system comprises at least one flash memory device that includes a flash memory controller and a flash memory;

computing, by the at least one processor, a first value corresponding to at least one portion of the received data;

determining, by the at least one processor, that the first value matches a second value stored in a collection of identifiers,

each identifier corresponding to a particular portion of data stored in the flash memory of the flash memory device, each identifier comprising a computed value corresponding to the particular portion of data and including metadata indicating a location where the particular portion of data is being stored in the flash memory of the flash memory device;

determining, by the at least one processor, that a first virtual location of the flash memory contains a portion of data corresponding to an identifier that corresponds to the first value; and

based on the determination that the first value matches a second value stored in the collection of identifiers, and on the determination that the first virtual location contains the portion of data corresponding to the identifier that corresponds to the first value,

communicating, by the at least one processor, to the flash memory controller of the flash memory device, a request to;

1) allocate the first virtual location of the flash memory to a first physical location of the flash memory, the first physical location being associated with at least a second virtual location of the flash memory, and

2) remove an association between the first virtual location and a second physical location of the flash memory.

2. The method of claim 1, wherein each virtual location represents a portion of storage of the flash memory device.

3. The method of claim 2, wherein the portion of storage of the flash memory device comprises a block of the flash memory.

4. The method of claim 1, wherein communicating to the flash memory controller of the flash memory device the request to allocate the first virtual location of the flash memory to a first physical location of the flash memory, the first physical location being associated with at least the second virtual location of the flash memory comprises:

making a request that the first virtual location be merged with the second virtual location into a single virtual location corresponding to the first physical location.

5. The method of claim 1, wherein the first virtual location is allocated to a portion of data corresponding to the identifier corresponding to the first value, and wherein the second virtual location is allocated to a portion of data corresponding to the identifier corresponding to the second value.

6. The method of claim 1, comprising, based on the determination that the first value matches a second value stored in the collection of identifiers, designating the second physical location as unallocated, wherein the second physical location contains a portion of data corresponding to the identifier corresponding to the first value.

7. The method of claim 6, wherein designating the second physical location as unallocated comprises the removing of the association between the first virtual location and the second physical location.

8. The method of claim 1, comprising receiving an indication that an identifier corresponding to a portion of the received data was previously stored in the collection of identifiers, and, in response, verifying that the indicated identifier still corresponds to a portion of data stored in the flash memory.

9. The method of claim 1, the first and second virtual locations comprise virtual segments.

10. A method comprising:

at a data deduplication engine of a computer system in communication with a data storage system, wherein the data storage system comprises at least one flash memory device that includes a flash memory controller and a flash memory;

computing a first value corresponding to at least one portion of data, and

determining that the first value matches a second value stored in a collection of identifiers,

each identifier corresponding to a particular portion of data stored in the data storage system, each identifier comprising a computed value corresponding to the particular portion of data and including metadata indicating a location where the particular portion of data is being stored in the data storage system; and

based on the determination that the first value matches a second value stored in the collection of identifiers, sending a command to the flash memory controller of the flash memory device,

the command comprising an identification of a first virtual location and a second virtual location,

the command comprising instructions to associate the first and second virtual locations of the flash memory with a first physical location of the flash memory, and

the command comprising instructions to remove an association between the first virtual location and a second physical location,

wherein the first virtual location corresponds to a location indicated by a first identifier associated with the first value.

11. The method of claim 10, wherein the command causes the controller device to designate the second physical location of the flash memory as unallocated.

12. The method of claim 10, wherein

the second virtual location corresponds to a location indicated by a second identifier associated with the second value.

13. A system comprising:

a data storage device comprising at least one flash memory device, the flash memory device including a flash memory controller and a flash memory;

a data deduplication engine configured to;

compute a first value corresponding to at least one portion of data,

determine that the first value matches a second value stored in a collection of identifiers,

each identifier corresponding to a particular portion of data stored in the flash memory, each identifier comprising a computed value corresponding to the particular portion of data and including metadata indicating a location where the particular portion of data is being stored in the flash memory, and

based on the determination that the first value matches a second value stored in the collection of identifiers, send a command to the flash memory controller of the flash memory device,

the command comprising an identification of a first virtual location and a second virtual location,

the command comprising instructions to associate the first and second virtual locations of the flash memory with a first physical location of the flash memory

the command comprising instructions to remove an association between the first virtual location and a second physical location,

wherein the first virtual location corresponds to a location indicated by a first identifier associated with the first value.

14. The system of claim 13, wherein the flash memory controller is configured to, in response to the command, designate a second physical location of the flash memory as unallocated.

15. The system of claim 14, wherein the flash controller is configured to designate the second physical location of the flash memory as unallocated by the removing of the association between the first virtual location and the second physical location.

16. The system of claim 13, wherein

the second virtual location corresponds to a location indicated by a second identifier associated with the second value.

17. The system of claim 13, wherein each of the two virtual segments represents a portion of storage of the flash memory.