Highly Scalable and Distributed Data De-Duplication

• US 20110231374A1
• Filed: 03/16/2011
• Published: 09/22/2011
• Est. Priority Date: 03/16/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Copiun Incorporated (Blackberry Limited)
• Inventors: JAIN, Sanjay, CHAUDHRY, Puneesh
• Granted Patent: US 8,452,739 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

This disclosure relates to systems and methods for both maintaining referential integrity within a data storage system, and freeing unused storage in the system, without the need to maintain reference counts to the blocks of storage used to represent and store the data.

Claims

1. A method comprising:

partitioning, in a data storage system, each of a plurality of instances of digital data into a respective plurality of blocks, wherein each instance of digital data is represented by a file identifier, the file identifier referencing each of the respective plurality of blocks; and

maintaining a last-reference-check timestamp for each of the blocks within each of the pluralities of blocks such that each last-reference-check timestamp indicates a last time, if ever, the block was validated to confirm that the block was referenced within the system;

maintaining a last-validation timestamp for each file identifier such that each last-validation timestamp indicates when, if ever, each block referenced by the file identifier had been validated to confirm that the file identifier referenced the respective block;

removing a block from the data storage system when the last-reference-check timestamp associated with the block is earlier than the earliest last-validation timestamp in the system.

2. The method of claim 1, wherein partitioning each of the plurality of instances of digital data includes:

partitioning a new instance of digital data into a plurality of blocks, including a first block,

generating a first file identifier based at least in part on the new digital data;

associating the first file identifier with the first block and the new digital data such that the first block is referenced by the first file identifier;

storing the first file identifier in the data storage system;

setting the first file identifier'"'"'s last-validation timestamp to the current time;

storing the first block in the data storage system if the first block has not already been stored;

determining if the system is currently in the process of removing unreferenced blocks; and

if the system is currently in the process of removing unreferenced blocks, setting the first block'"'"'s last-reference-check timestamp to the current time.

3. The method of claim 1, wherein maintaining a last-reference-check timestamp and maintaining a last-validation timestamp for each file identifier include:

repeatedly performing a block reference update, the block reference update comprising;

identifying the file identifier with the oldest last-validation timestamp in the data storage system as the current-file-identifier,

validating each block referenced by the current-file-identifier such that each such block'"'"'s last-reference-check timestamp is set to the current time; and

updating the current-file-identifier'"'"'s last-validation timestamp to the current time.

4. The method of claim 3, wherein each block in the storage system may exist in either a recycling bin or a primary storage bin, and wherein validating each block referenced by the current-file-identifier includes:

if the block being validated does not exist in the primary storage bin, but does exist in the recycling bin, moving the block being validated back from the recycling bin to the primary storage bin; and

if the block being validated exists neither in the primary storage bin nor the recycling bin, marking the current-file-identifier as invalid.

5. The method of claim 1, wherein removing a block from the data storage system includes:

providing an indication that unreferenced blocks are currently in the process of being removed from the storage system;

removing blocks from the data storage system whose last-reference-check timestamp is earlier than the earliest last-validation timestamp;

providing an indication that unreferenced blocks are no longer in the process of being removed from the storage system.

6. The method of claim 5, wherein each block may exist in either a recycling bin or a primary storage bin, and wherein removing all blocks from the data storage system includes:

for each block in the primary storage bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, moving the block to the recycling bin and setting the block'"'"'s last-reference-check timestamp to the current time; and

for each block in the recycling bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, removing the block from the recycling bin and freeing any storage associated with the removed block.

7. The method of claim 1, wherein each instance of digital data is further partitioned into respective additional data, wherein a combination of the respective plurality of blocks and additional data together represent all of the digital data of the instance, the additional data including at least one of position-dependent data, instance-dependent data, format-specific headers or footers, and format-specific transformations.

8. The method of claim 1, wherein maintaining a last-reference-check timestamp for each of the blocks, maintaining a last-validation timestamp for each file identifier, and removing a block from the data storage system are performed concurrently.

9. A system comprising:

a memory capable of storing data; and

a processor configured for;

partitioning, in a data storage system, each of a plurality of instances of digital data into a respective plurality of blocks, wherein each instance of digital data is represented by a file identifier, the file identifier referencing each of the respective plurality of blocks; and

maintaining a last-reference-check timestamp for each of the blocks within each of the pluralities of blocks such that each last-reference-check timestamp indicates a last time, if ever, the block was validated to confirm that the block was referenced within the system;

maintaining a last-validation timestamp for each file identifier such that each last-validation timestamp indicates when, if ever, each block referenced by the file identifier had been validated to confirm that the file identifier referenced the respective block;

removing a block from the data storage system when the last-reference-check timestamp associated with the block is earlier than the earliest last-validation timestamp in the system.

10. The system of claim 9, wherein partitioning each of the plurality of instances of digital data includes:

partitioning a new instance of digital data into a plurality of blocks, including a first block,

generating a first file identifier based at least in part on the new digital data;

associating the first file identifier with the first block and the new digital data such that the first block is referenced by the first file identifier;

storing the first file identifier in the data storage system;

setting the first file identifier'"'"'s last-validation timestamp to the current time;

storing the first block in the data storage system if the first block has not already been stored;

determining if the system is currently in the process of removing unreferenced blocks; and

if the system is currently in the process of removing unreferenced blocks, setting the first block'"'"'s last-reference-check timestamp to the current time.

11. The system of claim 9, wherein maintaining a last-reference-check timestamp and maintaining a last-validation timestamp for each file identifier include:

repeatedly performing a block reference update, the block reference update comprising;

identifying the file identifier with the oldest last-validation timestamp in the data storage system as the current-file-identifier,

validating each block referenced by the current-file-identifier such that each such block'"'"'s last-reference-check timestamp is set to the current time; and

updating the current-file-identifier'"'"'s last-validation timestamp to the current time.

12. The system of claim 11, wherein each block in the storage system may exist in either a recycling bin or a primary storage bin, and wherein validating each block referenced by the current-file-identifier includes:

if the block being validated does not exist in the primary storage bin, but does exist in the recycling bin, moving the block being validated back from the recycling bin to the primary storage bin; and

if the block being validated exists neither in the primary storage bin nor the recycling bin, marking the current-file-identifier as invalid.

13. The system of claim 9, wherein removing a block from the data storage system includes:

providing an indication that unreferenced blocks are currently in the process of being removed from the storage system;

removing blocks from the data storage system whose last-reference-check timestamp is earlier than the earliest last-validation timestamp;

providing an indication that unreferenced blocks are no longer in the process of being removed from the storage system.

14. The system of claim 13, wherein each block may exist in either a recycling bin or a primary storage bin, and wherein removing all blocks from the data storage system includes:

for each block in the primary storage bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, moving the block to the recycling bin and setting the block'"'"'s last-reference-check timestamp to the current time; and

for each block in the recycling bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, removing the block from the recycling bin and freeing any storage associated with the removed block.

15. The system of claim 9, wherein each instance of digital data is further partitioned into respective additional data, wherein a combination of the respective plurality of blocks and additional data together represent all of the digital data of the instance, the additional data including at least one of position-dependent data, instance-dependent data, format-specific headers or footers, and format-specific transformations.

16. The system of claim 9, wherein maintaining a last-reference-check timestamp for each of the blocks, maintaining a last-validation timestamp for each file identifier, and removing a block from the data storage system are performed concurrently.

17. Logic encoded in one or more non-transient media that includes code for execution and when executed by a processor is operable to perform operations comprising:

partitioning, in a data storage system, each of a plurality of instances of digital data into a respective plurality of blocks, wherein each instance of digital data is represented by a file identifier, the file identifier referencing each of the respective plurality of blocks; and

maintaining a last-reference-check timestamp for each of the blocks within each of the pluralities of blocks such that each last-reference-check timestamp indicates a last time, if ever, the block was validated to confirm that the block was referenced within the system;

maintaining a last-validation timestamp for each file identifier such that each last-validation timestamp indicates when, if ever, each block referenced by the file identifier had been validated to confirm that the file identifier referenced the respective block;

removing a block from the data storage system when the last-reference-check timestamp associated with the block is earlier than the earliest last-validation timestamp in the system.

18. The logic of claim 17, wherein partitioning each of the plurality of instances of digital data includes:

partitioning a new instance of digital data into a plurality of blocks, including a first block,

generating a first file identifier based at least in part on the new digital data;

associating the first file identifier with the first block and the new digital data such that the first block is referenced by the first file identifier;

storing the first file identifier in the data storage system;

setting the first file identifier'"'"'s last-validation timestamp to the current time;

storing the first block in the data storage system if the first block has not already been stored;

determining if the system is currently in the process of removing unreferenced blocks; and

if the system is currently in the process of removing unreferenced blocks, setting the first block'"'"'s last-reference-check timestamp to the current time.

19. The logic of claim 17, wherein maintaining a last-reference-check timestamp and maintaining a last-validation timestamp for each file identifier include:

repeatedly performing a block reference update, the block reference update comprising;

identifying the file identifier with the oldest last-validation timestamp in the data storage system as the current-file-identifier,

validating each block referenced by the current-file-identifier such that each such block'"'"'s last-reference-check timestamp is set to the current time; and

updating the current-file-identifier'"'"'s last-validation timestamp to the current time.

20. The logic of claim 19, wherein each block in the storage system may exist in either a recycling bin or a primary storage bin, and wherein validating each block referenced by the current-file-identifier includes:

if the block being validated does not exist in the primary storage bin, but does exist in the recycling bin, moving the block being validated back from the recycling bin to the primary storage bin; and

if the block being validated exists neither in the primary storage bin nor the recycling bin, marking the current-file-identifier as invalid.

21. The logic of claim 17, wherein removing a block from the data storage system includes:

providing an indication that unreferenced blocks are currently in the process of being removed from the storage system;

removing blocks from the data storage system whose last-reference-check timestamp is earlier than the earliest last-validation timestamp;

providing an indication that unreferenced blocks are no longer in the process of being removed from the storage system.

22. The logic of claim 21, wherein each block may exist in either a recycling bin or a primary storage bin, and wherein removing all blocks from the data storage system includes:

for each block in the primary storage bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, moving the block to the recycling bin and setting the block'"'"'s last-reference-check timestamp to the current time; and

for each block in the recycling bin whose last-reference-check timestamp is earlier than the earliest last-validation timestamp, removing the block from the recycling bin and freeing any storage associated with the removed block.

23. The logic of claim 17, wherein each instance of digital data is further partitioned into respective additional data, wherein a combination of the respective plurality of blocks and additional data together represent all of the digital data of the instance, the additional data including at least one of position-dependent data, instance-dependent data, format-specific headers or footers, and format-specific transformations.

24. The logic of claim 17, wherein maintaining a last-reference-check timestamp for each of the blocks, maintaining a last-validation timestamp for each file identifier, and removing a block from the data storage system are performed concurrently.