Data de-duplication for iSCSI

• US 8,135,918 B1
• Filed: 12/31/2007
• Issued: 03/13/2012
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Yueh, Jedidiah
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Bertram, Ryan
• Application Number:
  US11/968,052
• Time in Patent Office: 1,534 Days
• Field of Search: 711/147, 711/159, 711/162
• US Class Current: 711/147
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence

Abstract

Redundant data is identified and eliminated in a network that implements the iSCSI protocol either in-band at the source, in-band at the target, or out-of-band at the target. For in-band de-duplication, a data block included with a write command is assigned a unique identifier that is compared to a database of unique identifiers corresponding to previously written data. If the unique identifier is identical to an existing unique identifier, this indicates that the data block is redundant and has previously been stored elsewhere, in which case it is not stored again. Instead, the storage address specified in the write command may be added to a routing table showing the equivalence of unique identifiers, actual storage addresses, and duplicate storage addresses. When a read request specifying a duplicate storage address is received, the duplicate storage address can be translated to a corresponding unique identifier which points to the actual storage address.

Claims

1. In a computer network that implements the internet small computer systems interface protocol to enable storage access across the computer network, a method for de-duplicating data in-band in the computer network, the method comprising:

receiving a first data block for storage at a first storage address;

assigning a first probabilistically unique identifier to the first data block;

comparing the first probabilistically unique identifier to a plurality of second probabilistically unique identifiers assigned to a plurality of second data blocks previously stored in the network;

if the first probabilistically unique identifier is identical to a second probabilistically unique identifier assigned to a second data block, indicating that the first data block is identical to the second data block stored at a second storage address, adding an entry to a routing table to re-route future read requests specifying the first storage address to the second storage address without storing the first data block at the first storage address, wherein the entry establishes a relationship between the first storage address and the second probabilistically unique identifier and future requests for the first storage address are translated into the second probabilistically unique identifier to re-route the future requests for the first storage address to the second storage address.

2. The method of claim 1, wherein each of the first probabilistically unique identifier and the plurality of second probabilistically unique identifiers comprises a hash valued derived from performing a hash function on the corresponding data block to which the probabilistically unique identifier is assigned.

3. The method of claim 1, wherein the method is implemented by an internet small computer systems interface driver installed on a first source generating data for storage on one or more small computer systems interface storage devices.

4. The method of claim 3, wherein comparing the first probabilistically unique identifier to a plurality of second probabilistically unique identifiers includes comparing the first probabilistically unique identifier to a first database on the first source that includes a first subset of the plurality of second probabilistically unique identifiers and comparing the first probabilistically unique identifier to a second database on a second source that includes a second subset of the plurality of second probabilistically unique identifiers.

5. The method of claim 1, wherein the method is implemented by a storage virtualization layer configured to virtualize some or all of the storage capacity from each of a plurality of small computer systems interface storage devices into a uniform pool.

6. The method of claim 1, further comprising, if the first probabilistically unique identifier is not identical to any one of the second plurality of probabilistically unique identifiers, thereby indicating that the first data block is new and is not identical to any of the second data blocks, storing the first data block in the network and adding the first probabilistically unique identifier to the plurality of second probabilistically unique identifiers.

7. The method of claim 6, wherein if the first probabilistically unique identifier is not identical to any one of the second plurality of probabilistically unique identifiers, the first data block is stored at the first storage address.

8. The method of claim 1, wherein the routing table includes a first information field identifying the identical probabilistically unique identifier, a second information field identifying the second storage address, and a third information field identifying the first storage address as a duplicate storage address where the first data block is not stored since the first data block is identical to the second data block.

9. The method of claim 1, further comprising, receiving a read request specifying the first storage address and re-routing the read request to the second storage address.

10. The method of claim 9, wherein re-routing the read request specifying the first storage address to the second storage address includes:

translating the first storage address to the identical probabilistically unique identifier using the routing table;

identifying the second storage address of the second data block using the identical probabilistically unique identifier; and

requesting or retrieving the second data block from the second storage address.

11. In a computer network that implements the internet small computer systems interface to enable storage access across the computer network, a method for de-duplicating data in-band in a computer network, the method comprising:

receiving a first data block for storage and a small computer systems interface write command specifying a first storage address in the network for storing the first data block;

determining that the first data block is a duplicate of a second data block stored at a second storage address in the network;

establishing a relationship between the first storage address and the second storage address in a routing table; and

storing an entry to the routing table to re-route requests to the first storage address to the second storage address based on the relationship without storing the first data block at the first storage address, wherein, upon receiving a small computer systems interface read command that specifies the first storage address, the routing table redirects the read command to the second data block at the second storage address, wherein future requests for the first storage block are translated into requests for the second storage block to re-route the future requests for the first storage block to the second storage block.

12. The method of claim 11, wherein the method is implemented by one or more of:

at least one internet small computer system interface driver on at least one corresponding source that generates data for storage in the network; and

a storage virtualization layer configured to virtualize some or all of the storage capacity from each of a plurality of small computer systems interface storage devices into a uniform pool.

13. The method of claim 12, wherein if the method is implemented by a storage virtualization layer:

the plurality of small computer systems interface storage devices includes at least one solid state storage device; and

the storage virtualization layer maintains, on the solid state storage device, a database of hash values assigned to previously stored data blocks for identifying duplicate data blocks.

14. The method of claim 11, wherein determining that the first data block is a duplicate of a second data block includes comparing a hash value of the first data block to a plurality of hash values that includes a hash value of the second data block, and wherein the hash value of the first data block is identical to the hash value of the second data block.

15. The method of claim 14, wherein the pointer or reference comprises the hash value of the identical block, and wherein storing a pointer or reference without storing the first data block includes recording the first storage address in a routing table along with the hash value of the identical data block, the routing table indicating the equivalence of the data block not written to the first storage address and the data block pointed to by the hash value.

16. In a computer network that implements the internet small computer systems interface protocol to enable storage access across the network, a method for de-duplicating data out-of-band in a computer network, the method comprising:

storing a first data block at a first storage address in the network and a second data block at a second storage address in the network;

determining that the second data block is identical to the first data block;

deleting the second data block from the second storage address; and

adding an entry to a routing table to re-route future small computer systems interface read commands specifying the second storage address to the first storage address, wherein the entry establishes a relationship between the second storage address and a unique identifier and future requests for the second storage address are translated into the unique identifier to re-route the future requests for the first storage address to the first storage address.

17. The method of claim 16, wherein determining that the second data block is identical to the first data block includes comparing a hash value of the second data block to a plurality of hash values that includes a hash value of the first data block, and wherein the hash value of the second data block is identical to the hash value of the first data block.

18. The method of claim 17, wherein adding an entry to a routing table includes recording the second storage address in the routing table along with the hash value of the identical data block, the hash value of the identical data block pointing to the first data block at the first storage address.

19. The method of claim 18, further comprising:

receiving a small computer system interface read command specifying the second storage address;

using the routing table to identify the hash value corresponding to the second data block deleted from the second storage address;

using the hash value to identify the first storage address of the identical data block; and

retrieving the identical data block from the first storage address.

20. The method of claim 16, wherein the method is implemented within a single small computer systems interface storage device or across a plurality of small computer systems interface storage devices.