Efficient Inline Data De-Duplication on a Storage System

• US 20130238876A1
• Filed: 03/07/2012
• Published: 09/12/2013
• Est. Priority Date: 03/07/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fiske, Rahul M., Roy, Subhojit, Walls, Andrew D.
• Granted Patent: US 9,417,811 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/1024 Latency reduction
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A mechanism is provided in a storage system for efficient inline data de-duplication. The mechanism receives a write command and a hash key for a portion of data to be written from an application host to a write address. The write command indicates whether the application host is tolerant or intolerant to data loss. Responsive to the write command indicating the application host is tolerant to data loss, the mechanism performs a hash key lookup in a hash index. The mechanism determines whether the portion of data has previously been written to the storage system. Responsive to determining the portion of data has previously been written to the storage system, the mechanism stores a pointer to the previously written data at the write address.

Claims

1. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a storage system, causes the storage system to:

receive a write command and a hash key for a portion of data to be written from an application host to a write address, wherein the write command indicates whether the application host is tolerant or intolerant to data loss;

responsive to the write command indicating the application host is tolerant to data loss, perform a hash key lookup in a hash index;

determine whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, store a pointer to the previously written data at the write address.

2. The computer program product of claim 1, wherein the computer readable program further causes the storage system to:

responsive to the storage system determining the portion of data has not previously been written to the storage system, send a transfer ready indicator to the application host;

receive the portion of data to be written;

write the portion of data to the storage system; and

update the hash index with the hash key.

3. The computer program product of claim 1, wherein the computer readable program further causes the storage system to:

responsive to the write command indicating the application host is intolerant to data loss, send a transfer ready indicator to the application host;

receive a write payload comprising the portion of data to be written;

perform a hash key lookup in a hash index;

determine whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, store a pointer to the previously written data at the write address.

4. The computer program product of claim 3, wherein the write payload comprises a number of hash keys, a size of each hash key, a plurality of hash keys including the hash key, and write data including the portion of data to be written.

5. The computer program product of claim 3, wherein determining whether the portion of data has previously been written to the storage system comprises:

determining whether the hash key lookup results in a match;

responsive to the hash key lookup resulting in a match, performing a bit-by-bit comparison of the portion of data and a previously stored portion of data corresponding to a matching hash in the hash index; and

responsive to the bit-by-bit comparison resulting in a match, determining that the portion of data has previously been written to the storage system.

6. The computer program product of claim 1, wherein the computer readable program further causes the storage system to:

notify the application host of a grain size and an identifier of a hash key calculation algorithm, wherein the application host calculates the hash key using the grain size and the identified hash key calculation algorithm.

7. The computer program product of claim 1, wherein the computer readable program further causes the storage system to:

responsive to receiving the write command and the hash key, determine whether the portion of data has previously been written to a cache memory; and

responsive to the storage system determining the portion of data has previously been written to the cache memory, store a pointer to the previously written data in the cache memory.

8. The computer program product of claim 1, wherein the application host uses a cache memory local to the application host to identify false positive hash key matches prior to sending the write command.

9. The computer program product of claim 1, wherein the computer readable program is stored in a computer readable storage medium in a data processing system and wherein the computer readable program was downloaded over a network from a remote data processing system.

10. The computer program product of claim 1, wherein the computer readable program is stored in a computer readable storage medium in a server data processing system and wherein the computer readable program is downloaded over a network to a remote data processing system for use in a computer readable storage medium with the remote system.

11. A storage system, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive a write command and a hash key for a portion of data to be written from an application host to a write address, wherein the write command indicates whether the application host is tolerant or intolerant to data loss;

responsive to the write command indicating the application host is tolerant to data loss, perform a hash key lookup in a hash index;

determine whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, store a pointer to the previously written data at the write address.

12. The storage system of claim 11, wherein the instructions further cause the processor to:

responsive to the storage system determining the portion of data has not previously been written to the storage system, send a transfer ready indicator to the application host;

receive the portion of data to be written;

write die portion of data to the storage system; and

update the hash index with the hash key.

13. The storage system of claim 11, wherein the instructions further cause the processor to:

responsive to the write command indicating the application host is intolerant to data loss, send a transfer ready indicator to the application host;

receive a write payload comprising the portion of data to be written;

perform a hash key lookup in a hash index;

determine whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, store a pointer to the previously written data at the write address.

14. The storage system of claim 13, wherein the write payload comprises a number of hash keys, a size of each hash key, a plurality of hash keys including the hash key, and write data including the portion of data to be written.

15. The storage system of claim 13, wherein the instructions further cause the processor to:

determining whether the hash key lookup results in a match;

responsive to the hash key lookup resulting in a match, performing a bit-by-bit comparison of the portion of data and a previously stored portion of data corresponding to a matching hash in the hash index; and

responsive to the bit-by-bit comparison resulting in a match, determining that the portion of data has previously been written to the storage system.

16. The storage system of claim 11, wherein the instructions further cause the processor to:

notify the application host of a grain size and an identifier of a hash key calculation algorithm, wherein the application host calculates the hash key using the grain size and the identified hash key calculation algorithm.

17. The storage system of claim 11, wherein the instructions further cause the processor to:

responsive to receiving the write command and the hash key, determine whether the portion of data has previously been written to a cache memory; and

responsive to the storage system determining the portion of data has previously been written to the cache memory, store a pointer to the previously written data in the cache memory.

18. The storage system of claim 11, wherein the application host uses a cache memory local to the application host to identify false positive hash key matches prior to sending the write command.

19. A method, in a storage system, for efficient inline data de-duplication, the method comprising:

receiving, by the storage system, a write command and a hash key for a portion of data to be written from an application host to a write address, wherein the write command indicates whether the application host is tolerant or intolerant to data loss;

responsive to the write command indicating the application host is tolerant to data loss, performing, by the storage system, a hash key lookup in a hash index;

determining, by the storage system, whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, storing, by the storage system, a pointer to the previously written data at the write address.

20. The method of claim 19, further comprising:

responsive to the write command indicating the application host is intolerant to data loss, sending a transfer ready indicator to the application host;

receiving a write payload comprising the portion of data to be written;

performing a hash key lookup in a hash index;

determining whether the portion of data has previously been written to the storage system; and

responsive to the storage system determining the portion of data has previously been written to the storage system, storing a pointer to the previously written data at the write address.