APPARATUS, SYSTEM, AND METHOD FOR IMPROVED DATA DEDUPLICATION

• US 20110055471A1
• Filed: 08/28/2009
• Published: 03/03/2011
• Est. Priority Date: 08/28/2009
• Status: Abandoned Application

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Strasser, John, Flynn, David, Thatcher, Jonathan
• Application Number:
  US12/550,260
• Publication Number:
  US 20110055471A1
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

An apparatus, system, and method are disclosed for improved deduplication. The apparatus includes an input module, a hash module, and a transmission module that are implemented in a nonvolatile storage device. The input module receives hash requests from requesting entities that may be internal or external to the nonvolatile storage device; the hash requests include a data unit identifier that identifies the data unit for which the hash is requested. The hash module generates a hash for the data unit using a hash function. The hash is generated using the computing resources of the nonvolatile storage device. The transmission module sends the hash to a receiving entity when the input module receives the hash request. A deduplication agent uses the hash to determine whether or not the data unit is a duplicate of a data unit already stored in the storage system that includes the nonvolatile storage device.

Claims

1. An apparatus for generating, in a nonvolatile storage device, a hash of a data unit that is stored in the nonvolatile storage device, the apparatus comprising:

an input module that is implemented on a nonvolatile storage device and that receives a hash request from a requesting entity, the hash request comprising a data unit identifier that identifies the data unit for which the hash is requested;

wherein the data unit identified by the data unit identifier is stored in the nonvolatile storage device, the nonvolatile storage device comprising a storage controller and a nonvolatile storage connected by a first communications connection, the nonvolatile storage device configured to connect to one or more external devices through a second communications connection that is separate from the first communications connection;

a hash module that is implemented on the nonvolatile storage device and that generates, within the nonvolatile storage device, a hash for the data unit identified by the data unit identifier;

wherein the hash identifies the data unit for which the hash is generated; and

a transmission module that is implemented on the nonvolatile storage device and that sends the hash to a receiving entity over the second communications connection.

2. The apparatus of claim 1, wherein the data unit identifier is one of:

a data unit label that references one or more data unit locations in which the data unit is stored on the nonvolatile storage device, wherein the nonvolatile storage device comprises one or more data structures associating the data unit label and the one or more data unit locations; and

a data structure comprising one or more data unit locations that identify one or more locations on the nonvolatile data storage device where the data unit for which the hash is requested is stored.

3. The apparatus of claim 2, wherein the data unit label is one of a filename, an object ID, and an i-node, and wherein the one or more data unit locations are one of a logical block address and a physical address.

4. The apparatus of claim 1, wherein the hash module generates the hash for the data unit in response to the input module receiving the hash request from the requesting entity.

5. The apparatus of claim 1, wherein the hash request is part of a request to write the data unit.

6. The apparatus of claim 1, wherein the transmission module sends the hash as part of an acknowledgment that the data unit has been successfully written to the nonvolatile storage device.

7. The apparatus of claim 1, wherein the nonvolatile storage device is part of a RAIDed system comprising a plurality of nonvolatile storage devices, and wherein the data unit is a data segment of a RAID data stripe generated for a RAID data block.

8. The apparatus of claim 7, further comprising a seed module that:

receives a seed for generating the hash; and

provides the seed to the hash module, the hash module using the seed to generate the hash in response to receiving the seed from the seed module.

9. The apparatus of claim 8, wherein the seed is a hash of a first data segment of the RAID data stripe, and wherein the hash module uses the seed to generate a hash of a second data segment of the RAID data stripe.

10. The apparatus of claim 9, wherein the receiving entity is a second nonvolatile storage device having a second data segment of the RAID data stripe, and wherein the hash is the seed for the second data segment.

11. The apparatus of claim 7, wherein the nonvolatile storage device is a parity-mirror nonvolatile storage device that locally stores each data segment of the RAID data stripe, the hash module of the parity-mirror nonvolatile storage device generating the hash of the RAID data stripe in conjunction with an operation to generate a parity segment for the RAID data stripe, wherein the hash module uses the locally stored data segments to generate the hash.

12. The apparatus of claim 1, wherein the requesting entity sends the hash request in response to determining that the data unit is moving down at least one level in a cache.

13. The apparatus of claim 1, wherein the requesting entity sends the hash request in response to determining that the data unit is the target of a data grooming operation and that the data unit has not been deduplicated.

14. The apparatus of claim 13, wherein the data grooming operation is one of a garbage collection operation, a defragmentation operation, and a refresh operation.

15. The apparatus of claim 1, wherein the receiving entity is one of the requesting entity and a second nonvolatile storage device.

16. The apparatus of claim 1, wherein the requesting entity is one of internal to the nonvolatile storage device and external to the nonvolatile storage device.

17. An apparatus to perform operations for improved deduplication on a computing device, the apparatus comprising:

a receipt module for receiving a hash of a data unit from one or more remote computing devices that are connected to the computing device by a network, wherein the one or more remote computing devices generate the hash of the data unit and transmit the hash over the network;

a duplicate module for determining, without touching the data unit, whether the data unit is a duplicate of an existing data unit in a storage system, wherein the determination is made using the hash provided by the one or more remote computing devices;

a delete module for causing one or more nonvolatile storage devices in the storage system to maintain a single logical copy that is one of the data unit and the existing data unit in the storage system; and

an update module for associating the data unit with the existing data unit in response to determining that the data unit is a duplicate of the existing data unit such that requests for the data unit and the existing data unit are directed to the logical copy of the data unit stored in the storage system.

18. The apparatus of claim 17, further comprising coordinating the generation of hashes on the one or more remote computing devices.

19. The apparatus of claim 17, further comprising at least one of:

a request module for sending a hash request that requests the hash of the data unit to one or more remote computing devices and that comprises a data unit identifier; and

the receipt module receiving the hash of the data unit from one or more remote computing devices without requesting the hash from the one or more remote computing devices.

20. The computer program product of claim 17, wherein the apparatus is part of a file system operating on the computing device that comprises a processor and memory.

21. The computer program product of claim 17, the request module further configured to send a seed associated with the data unit to the one or more remote computing devices, the one or more remote computing devices generating the hash of the data unit using the seed.

22. The apparatus of claim 17, wherein the one or more remote computing devices are client devices and wherein the hash is generated in one of a CPU, a bridge, a bus, a controller, a memory, and a network interface card (NIC) of the remote client devices.

23. A system for improved deduplication, the system comprising:

a deduplication agent that determines whether a data unit is a duplicate of an existing data unit in a storage system comprising one or more nonvolatile storage devices by using a hash of the data unit, the deduplication agent operating on a first computing device;

a hash generation apparatus for generating the hash of the data unit, the hash generation apparatus operating on a second computing device remote from the first computing device and connected to the first computing device by a communications connection, the hash generation apparatus comprising;

an input module that receives a hash request from a requesting entity, the hash request comprising a data unit identifier that identifies the data unit for which the hash is requested;

a hash module that generates a hash for the data unit identified by the data unit identifier, wherein the hash identifies the data unit for which the hash is generated; and

a transmission module that sends the hash to a receiving entity in response to the input module receiving the hash request.

24. The system of claim 23, wherein the nonvolatile storage devices are configured as a RAIDed system, wherein the data unit is a data segment of a RAID data stripe generated for a RAID data block.

25. They system of claim 24, wherein the hash generation apparatus further comprises a seed module that:

receives a seed for generating the hash; and

provides the seed to the hash module, the hash module using the seed to generate the hash for the data stripe in response to receiving the seed from the seed module.

26. The system of claim 23, wherein the requesting entity is the deduplication agent.

27. The system of claim 23, wherein the first computing device is one of a nonvolatile storage device, a network device, a network interface card (NIC), a RAID controller, a bridge, and a bus, and wherein the second computing device is one of a nonvolatile storage device, a network device, a network interface card (NIC), a RAID controller, a bridge, and a bus.

28. The system of claim 23, wherein hash generation apparatus communicates with the deduplication agent using a hash passing protocol.

29. The system of claim 23, further comprising one or more additional hash generation apparatuses, and wherein the hash generation apparatus of each device that touches the data unit during data storage and data retrieval operations generates a hash for data protection.