Highly scalable and distributed data de-duplication

• US 8,452,739 B2
• Filed: 03/16/2011
• Issued: 05/28/2013
• 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
• Primary Examiner(s): HO, BINH VAN
• Application Number:
  US13/049,095
• Publication Number:
  US 20110231374A1
• Time in Patent Office: 804 Days
• Field of Search: 707/692
• 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:

maintaining, in a data storage system, a plurality of blocks of data, the storage system representing a plurality of sets of digital data, by associating each of said sets of digital data with at least one of said plurality of blocks;

maintaining a first timestamp corresponding to each of the plurality of blocks, the first timestamp indicating a last time when a block was verified to have been associated with at least one of said sets of digital data;

maintaining a second timestamp corresponding to each of the sets of digital data, the second timestamp indicating a time when an association between a set of digital data and at least one of said plurality of blocks was verified;

providing an indication that a given block that is not associated with any of the sets of digital data is in the process of being removed from the storage system, wherein the first timestamp associated with the block indicates an earlier time than each of the second timestamps;

deleting the given block of data from the storage system; and

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

2. The method of claim 1, comprising:

maintaining a further plurality of blocks corresponding to a further set of digital data;

associating the further set of digital data with a further block of the further plurality of blocks;

setting a second timestamp associated with the further set of digital data to a current time;

determining if said further block does not correspond to any of the plurality of data blocks; and

in dependence on said determination, storing said further block and setting a first timestamp associated with said further block to the current time.

3. The method of claim 1, comprising:

identifying a set of digital data with an earliest second timestamp in the data storage system;

validating an association between the set of digital data and each of the plurality of blocks associated therewith and setting the first timestamp associated with each of the plurality of blocks in dependence on said verification to the current time; and

updating the second timestamp associated with the set of digital data to the current time.

4. The method of claim 3, wherein each of said plurality of blocks is maintained in a first storage area or a second, different storage area, the method comprising:

if a block being validated is maintained on the second storage area, moving the block being validated from the second storage area to the first storage area; and

if the block being validated cannot be located on the first storage area and the second storage area, marking the set of digital data associated therewith as invalid.

5. The method of claim 4, comprising:

for each of the blocks maintained on the first storage area;

comparing the first timestamp associated therewith each of the second timestamps,

moving the block to the second storage area in dependence on said comparison, and

setting the first timestamp associated with the block to the current time; and

for each of the blocks maintained on the second storage area;

comparing the first timestamp associated therewith each of the second timestamps, and

removing the block from the second storage area in dependence on said comparison.

6. The method of claim 1, wherein each said set of digital data is associated with at least one of a position-dependent data, an instance-dependent data, a format-specific header, a footer, and format-specific data.

7. A system comprising:

a memory configured to store data; and

a processor configured to;

maintain, in the memory, a plurality of blocks of data, the memory representing a plurality of sets of digital data, by associating each of said sets of digital data with at least one of said plurality of blocks;

maintain a first timestamp corresponding to each of the plurality of blocks, the first timestamp indicating a time when a block was verified to have been associated with at least one of said sets of digital data;

maintain a second timestamp corresponding to each of the sets of digital data, the second timestamp indicating a time when an association between a set of digital data and at least one of said plurality of blocks was verified;

provide an indication that a given block that is not associated with any of the sets of digital data is in the process of being removed from a storage system, wherein the first timestamp associated with the block indicates an earlier time than each of the second timestamps;

delete the given block of data from the storage system; and

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

8. The system of claim 7, wherein the processor is further configured to:

maintain a further plurality of blocks corresponding to a further set of digital data;

associate the further set of digital data with a further block;

set a second timestamp associated with the further set of digital data to a current time;

determine if said further block does not correspond to any of the plurality of data blocks; and

in dependence on said determination, store said further block and set a first timestamp associated with said further block to the current time.

9. The system of claim 7, wherein the processor is further configured to:

identify a set of digital data with an earliest second timestamp in the data storage system;

validate an association between the set of digital data and each of the plurality of blocks associated therewith and set the first timestamp associated with each of the plurality of blocks in dependence on said verification to a current time; and

update the second timestamp associated with the set of digital data to the current time.

10. The system of claim 9, wherein each of said plurality of blocks is maintained in a first storage area or a second, different storage area, and the processor is further configured to:

if a block being validated is maintained on the second storage area, move the block being validated back from the second storage area to the first storage; and

if the block being validated cannot be located on the first storage area or the second storage area, mark the set of digital data associated therewith as invalid.

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

for each of the blocks maintained on the first storage area;

compare the first timestamp associated therewith each of the second timestamps,

move the block to the second storage area in dependence on said comparison,

set the first timestamp associated with the block to the current time; and

for each of the blocks maintained on the second storage area;

compare the first timestamp associated therewith each of the second timestamps; and

remove the block from the second storage area in dependence on said comparison.

12. The system of claim 7, wherein the processor is configured to associate each said set of digital data with at least one of a position-dependent data, an instance-dependent data, a format-specific header or a footer, and format-specific data.

13. A non-transitory computer readable storage medium storing computer readable instructions thereon, the computer readable instructions when executed by a processor of a computing device cause the processor to perform a method comprising:

maintaining, in a data storage system, a plurality of blocks of data, the storage system representing a plurality of sets of digital data, by associating each of said sets of digital data with at least one of said plurality of blocks;

maintaining a first timestamp corresponding to each of the plurality of blocks, the first timestamp indicating a time when a block was verified to have been associated with at least one of said sets of digital data;

maintaining a second timestamp corresponding to each of the sets of digital data, the second timestamp indicating a time when an association between a set of digital data and at least one of said plurality of blocks of data was verified;

providing an indication that a given block that is not associated with any of the sets of digital data is in the process of being removed from the storage system, wherein the first timestamp associated with the block indicates an earlier time than each of the second timestamps;

deleting the given block of data from the storage system; and

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

14. The non-transitory computer readable storage medium of claim 13, wherein the computer readable instructions cause the processor to:

maintain a further plurality of blocks corresponding to a further set of digital data;

associate the further set of digital data with a further block;

set a second timestamp associated with the further set of digital data to a current time;

determine if said further block does not correspond to any of the plurality of data blocks; and

in dependence on said determination, store said further block and set a first timestamp associated with the further block to the current time.

15. The non-transitory computer readable storage medium of claim 13, wherein the computer readable instructions cause the processor to:

identify a set of digital data with an earliest second timestamp in the data storage system;

validate an association between the set of digital data and each of the plurality of blocks associated therewith and set the first timestamp associated with each of the plurality of blocks in dependence on said verification to a current time; and

update the second timestamp associated with the set of digital data to the current time.

16. The non-transitory computer readable storage medium of claim 15, wherein each of said plurality of blocks is maintained in a first storage area or a second, different storage area, and the computer readable instructions cause the processor to:

if a block being validated is maintained on the second storage area, move the block being validated back from the second storage area to the first storage area; and

if the block being validated cannot be located on the first storage area or the second storage area, mark the set of digital data associated therewith as invalid.

17. The non-transitory computer readable storage medium of claim 16, wherein the computer readable instructions cause the processor to:

for each of the blocks maintained on the first storage area;

compare the first timestamp associated therewith each of the second timestamps,

move the block to the second storage area in dependence on said comparison, and

set the first timestamp associated with the block to the current time; and

for each of the blocks maintained on the second storage area;

compare the first timestamp associated therewith each of the second timestamps, and

remove the block from the second storage area in dependence on said comparison.

18. The non-transitory computer readable storage medium of claim 13, wherein the computer readable instructions cause the processor to associate each said set of digital data with at least one of a position-dependent data, an instance-dependent data, a format-specific header, a footer, and format-specific data.