Primary data storage system with deduplication

• US 10,248,582 B2
• Filed: 11/07/2012
• Issued: 04/02/2019
• Est. Priority Date: 11/07/2011
• Status: Expired due to Fees

• 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.
• Primary Examiner(s): Perez-Velez, Rocio Del Mar
• Assistant Examiner(s): Ahmed, Zubair
• Application Number:
  US13/671,537
• Publication Number:
  US 20130117516A1
• Time in Patent Office: 2,337 Days
• Field of Search: 711162
• 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, the system comprising:

an input/output port configured to receive 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 a first responsiveness characteristic, the second data store has a second responsiveness characteristics, and the first and the second responsiveness characteristics are different;

a statistics database configured to provide hardware and/or volume statistical data relevant to a potential deduplication of data associated with a write block command; and

a deduplication processor configured to;

(a) receive a write block command and statistical data relevant to the received write block command from the statistics database, (b) determine, using the hardware and/or volume statistical data that is relevant to the potential deduplication of data associated with the write block command, if a yet to be performed deduplication operation on the data associated with the received write block command is expected to satisfy a time constraint specifically associated with the processing of the received write block command relative to the data store system, the time constraint being the difference between (i) an allowed amount of time to process the write block command that is specifically associated with the received write block command and reflects a quality of service goal and (ii) an amount of time previously expended in processing the received write block command, (c) if the yet to be performed deduplication on the data associated with the received write block command is expected to satisfy the time constraint specifically associated with the received write block command relative to the data store system, proceeding with the performance of the deduplication operation on the data associated with the received write block command, and (d) if the yet to be performed deduplication operation on the data associated with the received write block command is not expected to satisfy the time constraint specifically associated with the received write block command relative to the data store system, forgoing the performance of the deduplication operation and proceeding with the processing of the received write block command, thereby increasing the possibility that duplicate data is established on the data store system.

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

the deduplication processor includes a write determination processor configured to determine 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 configured to determine 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 configured to identify 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 configured to compare 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 configured to indicate 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 configured to determine 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 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 configured to compare 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 configured to compare 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 configured to indicate 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 configured to determine 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 configured to compare 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 comparison.

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

the deduplication processor includes a read determination processor configured to determine 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 configured to determine 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 configured to calculate 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 configured to determine 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.

17. A primary data storage system for use in a computer network and having de-duplication capability, the system comprising:

an input/output port configured to receive 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 statistics database configured to provide hardware and/or volume statistical data relevant to a potential deduplication of data associated with a write block command; and

a deduplication processor configured to;

(a) receive a write block command and statistical data relating to the received write block command from the statistics database, (b) determine, using the hardware and/or volume statistical data that is relevant to the potential deduplication of data associated with the received write block command, if a yet to be performed deduplication operation on the data associated with the received write block command is expected to satisfy a time constraint specifically associated with the processing of the received write block command relative to the data store system, the time constraint being the difference between (i) an allowed amount of time to process the received write block command that is specifically associated with the received write block command and reflects a quality of service goal and (ii) an amount of time previously expended in processing the received write block command, (c) if the yet to be performed deduplication of the data associated with the received write block command is expected to satisfy the time constraint specifically associated with the received write block command relative to the data store system, proceeding with the performance of the deduplication operation on the data associated with the received write block command, and (d) if the yet to be performed deduplication operation on the data associated with the received write block command is not expected to satisfy the time constraint specifically associated with the received write block command relative to the data store system, forgoing the performance of the deduplication operation and proceeding with the processing of the received write block command, thereby increasing the possibility that duplicate data is established on the data store 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.

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

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

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 configured to maintain 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 configured to operate 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 configured to operate 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 configured to operate on a write block command with the size of the write data being associated with the write block command being a first fixed multiple of a block size; and

a background deduplication processor configured to operate on a write block command with the size of the write data associated with the write block command being a second 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 uses a second time related criteria to determine whether to perform a deduplication operation;

wherein the second background deduplication subprocessor uses 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 that maintains a background dictionary 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 comprises a frequency processor configured to move 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 comprises an entry space processor configured to determine 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.