Highly scalable and distributed data de-duplication

• US 9,110,915 B2
• Filed: 04/18/2013
• Issued: 08/18/2015
• Est. Priority Date: 12/18/2009
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Copiun Incorporated (Blackberry Limited)
• Inventors: Jain, Sanjay, Chaudhry, Puneesh
• Primary Examiner(s): HO, BINH VAN
• Application Number:
  US13/865,552
• Publication Number:
  US 20130232126A1
• Time in Patent Office: 852 Days
• Field of Search: 707/692
• US Class Current: 1/1
• 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 of maintaining data blocks in a data storage system, the method comprising:

maintaining a plurality of data blocks in the data storage system;

representing a plurality of data files by associating each file identifier of a plurality of file identifiers with at least one of the plurality of data blocks;

maintaining a first set of timestamps, each data block in the plurality of data blocks being associated with one of the first set of timestamps, each of the first set of timestamps indicating a time when a respective data block was verified to have been associated with at least one of the plurality of file identifiers;

maintaining a second set of timestamps, different than the first set of timestamps, each file identifier of the plurality of file identifiers being associated with one of the second set of timestamps, each of the second set of timestamps indicating a time when a respective file identifier was verified to have been associated with at least one of the plurality of data blocks; and

deleting a given data block when timestamp of the first set of timestamps associated with the given data block indicates an earlier time than each of the second set of timestamps.

2. The method of claim 1, further comprising:

providing an indication that the given data block has been removed from the data storage system.

3. The method of claim 1, further comprising:

representing a new data file by associating a new file identifier with a new data block;

determining if the new data block corresponds to any of the plurality of existing data blocks;

storing the new data block in the data storage system if the new data block does not correspond to any of the plurality of data blocks; and

setting a new timestamp of the first set of timestamps to a current time for the new data block.

4. The method of claim 1, further comprising:

identifying a given file identifier with an earliest timestamp of the second set of timestamps;

verifying an association between the given file identifier and each of the plurality of data blocks associated with the given file identifier;

setting a timestamp of the first set of timestamps associated with each of the plurality of data blocks associated with the given file identifier to a current time; and

setting a timestamp of the second timestamps associated with the given file identifier to the current time.

5. The method of claim 4, wherein the data storage system comprises a first storage area and a second storage area, and wherein verifying the association between the given file identifier and each of the plurality of data blocks associated with the given file identifier further comprises:

determining if another given data block associated with the given file identifier is maintained in the first storage area or the second storage area;

moving the other given data block associated with the given file identifier from the second storage area to the first storage area if the other given data block is in the second storage area; and

marking the file identifier invalid if the other given data block is not maintained in the first storage area or the second storage area.

6. The method of claim 1, wherein the data storage system comprises a first storage area and a second storage area, and wherein deleting the given data block further comprises:

moving the given data block from the first storage area to the second storage area; and

setting the timestamp of the first set of timestamps associated with the given data block to a current time.

7. The method of claim 6, further comprising:

determining an earliest timestamp of the second set of timestamps; and

for each data block in the second storage area;

deleting the given data block in the second storage area if the timestamp of the first set of timestamps associated with the given data block is earlier than the determined earliest timestamp of the second set of timestamps.

8. The method of claim 1, wherein associating each file identifier of the plurality of file identifiers with at least one of the plurality of data blocks further comprises:

maintaining a block map for a given file identifier,

wherein the block map identifies the relationship between the given file identifier and each data block in the plurality of data blocks associated with the given file identifier.

9. The method of claim 1 wherein at least one of the plurality of data blocks is associated with two or more file identifiers of the plurality of file identifiers.

10. A data storage system configured for maintaining data blocks, comprising:

a data store comprising software; and

a processor in data communication with the data store and configured to execute the software in order to cause the data storage system to;

maintain a plurality of data blocks;

represent a plurality of data files by associating each file identifier of a plurality of file identifiers with at least one of the plurality of data blocks;

maintain a first set of timestamps, each data block in the plurality of data blocks being associated with one of the first set of timestamps, each of the first set of timestamps indicating a time when a respective data block was verified to have been associated with at least one of the plurality of file identifiers;

maintain a second set of timestamps, different than the first set of timestamps, each file identifier of the plurality of file identifiers being associated with one of the second set of timestamps, each of the second set of timestamps indicating a time when a respective file identifier was verified to have been associated with at least one of the plurality of data blocks; and

delete a given data block when a timestamp of the first set of timestamps associated with the given data block indicates an earlier time than each of the second set of timestamps.

11. The data storage system of claim 10, wherein the processor is further configured to cause the data storage system to:

provide an indication that the given data block has been removed from the storage system.

12. The data storage system of claim 10, wherein the processor is further configured to cause the data storage system to:

represent a new data file by associating a new file identifier with a new data block;

determine if the new data block corresponds to any of the plurality of existing data blocks;

store the new data block in the data storage system if the new data block does not correspond to any of the plurality of data blocks; and

set a new timestamp of the first set of timestamps to a current time for the new data block.

13. The data storage system of claim 10, wherein the processor is further configured to cause the data storage system to:

identify a given file identifier with an earliest timestamp of the second set of timestamps;

verify an association between the given file identifier and each of the plurality of data blocks associated with the given file identifier;

set timestamps of the first set of timestamps associated with each of the plurality of data blocks associated with the given file identifier to a current time; and

set a timestamp of the second set of timestamps associated with the given file identifier to the current time.

14. The data storage system of claim 13, further comprising:

a first storage area and a second storage area, and

wherein to verify the association between the given file identifier and each of the plurality of data blocks associated with the given file identifier further comprises to;

determine if another given data block associated with the given file identifier is maintained in the first storage area or the second storage area;

move the other given data block associated with the given file identifier from the second storage area to the first storage area if the other given data block is in the second storage area; and

mark the file identifier invalid if the other given data block is not maintained in the first storage area or the second storage area.

15. The data storage system of claim 10, further comprising:

a first storage area and a second storage area, and

wherein to delete the given data block further comprises to;

move the given data block from the first storage area to the second storage area; and

set the timestamp of the first set of timestamps associated with the given data block to the current time.

16. The data storage system of claim 15, wherein the processor is further configured to cause the data storage system to:

determine an earliest timestamp of the second set of timestamps; and

for each data block in the second storage area;

delete the given data block in the second storage area if the timestamp of the first set of timestamps associated with the given data block is earlier than the determined earliest timestamp of the second set of timestamps.

17. The data storage system of claim 10, wherein associating each file identifier of the plurality of file identifiers with at least one of the plurality of data blocks further comprises:

maintaining a block map for a given file identifier,

wherein the block map identifies the relationship between the given file identifier and each data block in the plurality of data blocks associated with the given file identifier.

18. A non-transitory, computer-readable medium comprising computer-executable instructions that, when executed by a processor, cause a computing device to perform a method, the method comprising:

maintaining a plurality of data blocks in a data storage system;

representing a plurality of data files by associating each file identifier of a plurality of file identifiers with at least one of the plurality of data blocks;

maintaining a first set of timestamps, each data block in the plurality of data blocks being associated with one of the first set of timestamps, each of the first set of timestamps indicating a time when a respective data block was verified to have been associated with at least one of the plurality of file identifiers;

maintaining a second set of timestamps, different than the first set of timestamps, each file identifier of the plurality of file identifiers being associated with one of the second set of timestamps, each of the second set of timestamps indicating a time when a respective file identifier was verified to have been associated with at least one of the plurality of data blocks; and

deleting a given data block when a timestamp of the first set of time stamps associated with the given data block indicates an earlier time than each of the second set of timestamps.

19. The non-transitory, computer-readable medium of claim 18, wherein the method further comprises:

providing an indication that the given data block has been removed from the data storage system.

20. The non-transitory, computer-readable medium of claim 18, wherein the method further comprises:

representing a new data file by associating a new file identifier with a new data block;

determining if the new data block corresponds to any of the plurality of data blocks;

storing the new data block in the data storage system if the new data block does not correspond to any of the plurality of data blocks; and

setting a new timestamp of the first set of time stamps to a current time for the new data block.

21. The non-transitory, computer-readable medium of claim 18, wherein the method further comprises:

identifying a given file identifier with an earliest timestamp of the second set of timestamps;

verifying an association between the given file identifier and each of the plurality of data blocks associated with the given file identifier;

setting a timestamps of the first set of timestamps associated with each of the plurality of data blocks associated with the given file identifier to a current time; and

setting a timestamp of the second set of timestamps associated with the given file identifier to the current time.

22. The non-transitory, computer-readable medium of claim 21, wherein the data storage system comprises a first storage area and a second storage area, and wherein verifying the association between the given file identifier and each of the plurality of data blocks associated with the given file identifier further comprises:

determining if another given data block associated with the given file identifier is maintained in the first storage area or the second storage area;

moving the other given data block associated with the given file identifier from the second storage area to the first storage area if the other given data block is in the second storage area; and

marking the file identifier invalid if the other given data block is not maintained in the first storage area or the second storage area.

23. The non-transitory, computer-readable medium of claim 18, wherein the data storage system comprises a first storage area and a second storage area, and wherein deleting the given data block further comprises:

moving the given data block from the first storage area to the second storage area; and

setting the timestamp of the first set of timestamps associated with the given data block to a current time.

24. The non-transitory, computer-readable medium of claim 23, wherein the method further comprises:

determining an earliest timestamp of the second set of timestamps; and

for each data block in the second storage area;

deleting the given data block in the second storage area if the timestamp of the first set of timestamps associated with the given data block is earlier than the determined earliest timestamp of the second set of timestamps.

25. The non-transitory, computer-readable medium of claim 18, wherein associating each file identifier of the plurality of file identifiers with at least one of the plurality of data blocks further comprises:

maintaining a block map for a given file identifier,

wherein the block map identifies the relationship between the given file identifier and each data block in the plurality of data blocks associated with the given file identifier.