METHODS AND SYSTEMS FOR SPACE MANAGEMENT IN DATA DE-DUPLICATION

• US 20090259701A1
• Filed: 04/14/2008
• Published: 10/15/2009
• Est. Priority Date: 04/14/2008
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Martin, Joshua Fitzsimmons, Burling, Douglas Alan, Leuschner, Jeffery D., Kline, John Theodore, Davis, Camden John, Wideman, Roderick B., Lord, Stephen Philip
• Granted Patent: US 8,650,228 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• 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

Abstract

The present invention is directed toward methods and systems for data de-duplication. More particularly, in various embodiments, the present invention provides systems and methods for data de-duplication that may utilize storage reclamation. In various embodiments, data de-duplication may be performed using data storage reclamation by reconciling a list of all active tags against a list of all tags present within the object store itself. Any tags found to be in the object store that have no corresponding active usage may then be deleted. In some embodiments additional steps may be taken to avoid race conditions in deleting tags that are needed by incoming data. In some embodiments the object store may request the lists. In other embodiments, a runtime list, in which each new tag is entered as they are returned from the object store. In another embodiment the object store may maintain this list directly.

Claims

1. A method of data storage space reclamation in a data de-duplication system comprising:

generating a list of active tags that includes a tag used by a data object stored in an object store;

generating a list of tags present within the object store;

comparing the list of active tags with the list of tags present within the object store; and

deleting data that is associated with a tag that is in the object store but not in the list of active tags.

2. The method of claim 1, further comprising incrementing a reference count associated with a tag based on the number of references to the tag and decrementing the reference count associated with a tag based on the number of deletions of references to the tag.

3. The method of claim 2, wherein the deletion of the data associated with the tag occurs if the reference count associated with the tag indicates that no references to the tag are active.

4. The method of claim 1, wherein the deletion of the data associated with the tag is delayed to determine if a reference to the tag is contained in incoming data.

5. The method of claim 1, wherein an application programming interface uses a process within the object store to generate the list of tags present within the object store.

6. The method of claim 1, wherein a runtime list is maintained to generate the list of tags present within the object store.

7. The method of claim 6, wherein each new tag is entered as they are returned from the object store.

8. The method of claim 6, wherein the object store maintains the list of tags present.

9. The method of claim 1, wherein reclamation of data storage space occurs after a predetermined period of time has passed.

10. The method of claim 1, wherein reclamation of data storage space occurs after a predetermined event.

11. The method of claim 1, wherein reclamation of data storage space occurs when the object store has a predetermined amount of data storage space available.

12. The method of claim 1, further comprising storing namespace snapshots associated with the list of active tags in the object store.

13. A data storage system comprising:

a data storage device;

a memory configured to store instructions;

a processor configured to read the memory and execute the instructions, the instructions configured to cause the processor to;

generate a list of active tags that includes a tag used by a data object stored in an object store;

generate a list of tags present within the data storage device;

comparing the list of active tags with the list of tags present within the data storage device; and

delete data that is associated with a tag that is in the data storage device but not in the list of active tag.

14. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to increment a reference count associated with a tag based on the number of references to the tag and decrement the reference count associated with a tag based on the number of deletions of references to the tag.

15. The data storage system of claim 14, wherein the instructions are further configured to cause the processor to delete a tag if the reference count associated with the tag indicates that no references to the tag are active.

16. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to delayed a deletion of data associated with a tag to determine if a reference to the tag is contained in incoming data.

17. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to maintain a runtime list is maintained to generate the list of tags present within the object store.

18. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to cause reclamation of data storage space to occur after a predetermined period of time has passed.

19. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to cause reclamation of data storage space to occur after a predetermined event.

20. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to cause reclamation of data storage space to occur when the object store has a predetermined amount of data storage space available.

21. The data storage system of claim 13, wherein the data storage device comprises a disk drive.

22. The data storage system of claim 13, wherein the data storage device comprises a tape drive.

23. The data storage system of claim 13, wherein the data storage device comprises a memory based data storage device.

24. The data storage system of claim 13, wherein the instructions are further configured to cause the processor to store namespace snapshots associated with the list of active tags in the object store.