Primary Data Storage System with Staged Deduplication

• US 20130117516A1
• Filed: 11/07/2012
• Published: 05/09/2013
• Est. Priority Date: 11/07/2011
• Status: Active Grant

• Current Assignee: Pivot3, Inc., NexGen Storage, Inc. (Western Digital Corporation)
• Original Assignee: NexGen Storage, Inc. (Western Digital Corporation)
• Inventors: Sobolewski, Sebastian Piotr, Long, Kelly E., Ashmore, Paul A.
• Granted Patent: US 10,248,582 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 12/16 Protection against loss of memory contents contains no material, see G06F11/00
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0649 Lifecycle management
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

The invention is directed to a primary data storage system for use in a computer network in which a network allows user computers to transfer data to and/or from the primary data storage system. In one embodiment of the invention, the storage processor operates to analyze the data associated with write block commands that relate to different storage locations in a data store system that is associated with the primary data storage system so as to identify the potential writing of the block(s) of the same data to the data store system and prevent the writing of such blocks of data.

Claims

1. A primary data storage system for use in a computer network and having de-duplication capability that endeavors to attain predetermined performance criteria for the primary data storage system, the system comprising:

an input/output port for receiving a block command packet that embodies one of a read block command and a write block command and transmitting a block result packet in reply to a block command packet;

a data store system having at least a first data store and a second data store;

wherein each of the first and second data stores is capable of receiving and storing data in response to a write block command and retrieving and providing data in response to a read block command;

wherein the first data store has first performance characteristics;

wherein the second data store has second performance characteristics;

wherein the first characteristics and the second characteristics are different;

a deduplication processor for receiving one of a write block command and a read block command and performing a deduplication operation on the one of the write block command and the read block command in accordance with performance criteria relating to the primary data storage system.

2. A primary data storage system, as claimed in claim 1, wherein:

the deduplication processor includes a write determination processor for determining if a write block command is received.

3. A primary data storage system, as claimed in claim 2, wherein:

the deduplication processor includes a headroom processor for determining if there is likely to be sufficient time to;

(a) determine if the write data associated with a write block command has a data pattern for which there is a calculation engine that potentially can calculate the write data and (b) compare the write data associated with a write block command to the data produced by a calculation engine to determine if the write data can be deduplicated.

4. A primary data storage system, as claimed in claim 3, wherein:

the deduplication processor includes a hash processor for identifying a single calculation engine that can potentially generate identical data to the write data associated with a write block command.

5. A primary data storage system, as claimed in claim 3, wherein:

the deduplication processor includes a compare processor for comparing data produced by a calculation engine to the write data associated with a write block command in whichever of the first and second stores will provide a faster comparison.

6. A primary data storage system, as claimed in claim 5, wherein:

the deduplication processor includes a dedup identified processor for indicating that there is a calculation engine that can calculate the write data associated with a write block command.

7. A primary data storage system, as claimed in claim 2, wherein:

the deduplication processor includes a headroom processor for determining if there is likely to be sufficient time to;

(a) determine if the write data associated with a write block command has a data pattern for which there is an entry in a dictionary that hosts substantially non-calculable data patterns that potentially has a matching pattern and (b) compare the write data associated with a write block command to an entry in the dictionary.

8. A primary data storage system, as claimed in claim 7, wherein:

the deduplication processor includes a compare processor for comparing a portion of the write data associated with a write block command to a portion of each entry in the dictionary in whichever of the first and second stores will provide faster comparisons.

9. A primary data storage system, as claimed in claim 7, wherein:

the deduplication processor includes a compare processor for comparing the write data associated with a write block command to an entry in the dictionary in whichever of the first and second stores will provide a faster comparison.

10. A primary data storage system, as claimed in claim 9, wherein:

the deduplication processor includes a dedup identified processor for indicating that there is an entry in the dictionary that is identical to the write data associated with a write block command.

11. A primary data storage system, as claimed in claim 2, wherein:

the deduplication processor includes a hash processor for determining if one or more entries in a dictionary have a hash value representative of the write data associated with a write block command.

12. A primary data storage system, as claimed in claim 2, wherein:

the deduplication processor includes a compare processor for comparing the write data associated with a write block command to an entry of a dictionary that is or a copy is located in whichever of the first and second stores will provide a faster comparision.

13. A primary data storage system, as claimed in claim 1, wherein:

the deduplication processor includes a read determination processor for determining if a read block command is received.

14. A primary data storage system, as claimed in claim 13, wherein:

the deduplication processor includes a dedup identified processor for determining if the read data associated with the read block command has been previously identified as capable of being produced by a calculation engine.

15. A primary data storage system, as claimed in claim 14, wherein:

the deduplication processor includes a calculation engine for calculating a predetermined data pattern in the one of the first and second data stores that is more likely to be able to more quickly provide the predetermined data pattern in response to the read block command.

16. A primary data storage system, as claimed in claim 13, wherein:

the deduplication processor includes a dedup identified processor for determining if the read data associated with the read block command has been previously identified as being present in a dictionary that hosts substantially non-calculable data patterns.

27. A primary data storage system, as claimed in claim 9, wherein:

the deduplication processor includes a foreground dictionary processor for maintaining a foreground dictionary capable of holding a number of entries that each identify data that has satisfied a frequency related threshold of deduplication.

17. A primary data storage system for use in a computer network and having de-duplication capability that endeavors to attain predetermined performance criteria for the primary data storage system, the system comprising:

an input/output port for receiving a block command packet that embodies one of a read block command and a write block command and transmitting a block result packet in reply to a block command packet;

a data store system having at least one data store capable of receiving and storing data in response to a write block command and retrieving and providing data in response to a read block command;

a deduplication processor for receiving one of a write block command and a read block commands and performing a deduplication operation on the one of a write block command and a read block command in accordance with performance criteria relating to the primary data storage system.

18. A primary data storage system, as claimed in claim 17, wherein:

the deduplication processor includes;

a foreground deduplication processor that endeavors to operate within a first latency constraint and

a background deduplication processor that operates within a second latency constraint that is greater than the first latency constraint.

19. A primary data storage system, as claimed in claim 18, wherein:

the foreground deduplication processor includes a calculable pattern processor that includes one or more calculation engines with each calculation engine capable of calculating a data pattern.

20. A primary data storage system, as claimed in claim 18, wherein:

the foreground deduplication processor includes a foreground dictionary processor that maintains a foreground dictionary capable of holding a number of entries that each identify data that has satisfied a frequency related threshold of deduplication.

21. A primary data storage system, as claimed in claim 18, wherein:

the foreground deduplication processor includes

a calculable pattern processor that includes one or more calculation engines with each calculation engine capable of calculating a data pattern and

a foreground dictionary processor that maintains a foreground dictionary capable of holding a number of entries that each identify data that has satisfied a frequency related threshold of deduplication.

22. A primary data storage system, as claimed in claim 19, wherein:

the background deduplication processor includes a background dictionary processor that maintains a background dictionary capable of holding a number of entries that each identify deduplication data.

23. A primary data storage system, as claimed in claim 20 wherein:

the background deduplication processor includes a background dictionary processor that maintains a background dictionary capable of holding a number of entries that each identify deduplication data.

24. A primary data storage system, as claimed in claim 21, wherein:

the background deduplication processor includes a background dictionary processor that maintains a background dictionary capable of holding a number of entries that each identify deduplication data.

25. A primary data storage system, as claimed in claim 17, further comprising:

a storage processor that includes a foreground processor that operates within a first latency constraint and a background processor that operates within a second latency constraint that is greater than the first latency constraint,

wherein the foreground processor includes the deduplication processor.

26. A primary data storage system, as claimed in claim 25, wherein:

the deduplication processor includes a calculable pattern processor that is capable of accommodating one or more calculation engines with each calculation engine capable of calculating a data pattern.

28. A primary data storage system, as claimed in claim 25, wherein:

the deduplication processor includes

a calculable pattern processor that is capable of accommodating one or more calculation engines with each calculation engine capable of calculating a data pattern and

a foreground dictionary processor for maintaining a foreground dictionary capable of holding a number of entries that each identify data that has satisfied a frequency related threshold of deduplication.

29. A primary data storage system, as claimed in claim 17, wherein:

the deduplication processor includes;

a foreground deduplication processor for operating on a write block command with the size of the write data associated with the write block command being a variable multiple of a block size and

a background deduplication processor for operating on a write block command with the size of the write data associated with the write block command being a fixed multiple of the block size.

30. A primary data storage system, as claimed in claim 17, wherein:

the deduplication processor includes;

a foreground deduplication processor for operating on a write block command with the size of the write data being associated with the write block command being a fixed multiple of a block size and

a background deduplication processor for operating on a write block command with the size of the write data associated with the write block command being a fixed multiple of the block size, wherein the second fixed multiple of the block size is the same as the first fixed multiple of the block size.

31. A primary data storage system, as claimed in claim 17, wherein:

the deduplication processor includes;

a foreground deduplication processor and

a background deduplication processor comprised of a first background deduplication subprocessor and a second background deduplication subprocessor,

wherein the foreground deduplication processor uses a first time related criteria to determine whether to perform a deduplication operation;

wherein the first background deduplication subprocessor using a second time related criteria to determine whether to perform a deduplication operation;

wherein the second background deduplication subprocessor using a third time related criteria to determine whether to perform a deduplication operation.

32. A primary data storage system, as claimed in claim 17, wherein:

the deduplication processor includes

a foreground deduplication processor that maintains a foreground dictionary capable of holding a number of entries that each identify data that has satisfied a frequency related threshold of deduplication and

a background deduplication processor capable of holding a number of entries that each identify deduplication data.

33. A primary data storage system, as claimed in claim 32, wherein:

the background deduplication processor including a frequency processor for moving an entry in the background dictionary that satisfies the frequency related threshold for the foreground dictionary to the foreground dictionary.

34. A primary data storage system, as claimed in claim 33, wherein:

the frequency processor including an entry space processor for determining if there is an available entry in the foreground dictionary;

if there is not an available entry, deleting an entry from the foreground dictionary to make an available entry for the entry from the background dictionary and adding the entry from the background dictionary to the foreground dictionary;

if there is an available entry, adding the entry from the background dictionary to the foreground dictionary.

35. A primary data storage system, as claimed in claim 32, wherein:

the number of potential entries in the foreground dictionary is less than the number of potential entries in the background dictionary.

36. A primary data storage system, as claimed in claim 32, wherein:

each of the entries in the foreground and background dictionaries is only capable of holding a data pattern that is not readily calculable.