Creating and managing links to deduplication information

• US 8,442,954 B2
• Filed: 07/21/2009
• Issued: 05/14/2013
• Est. Priority Date: 07/21/2009
• Status: Expired due to Fees

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Stephen Philip Spackman
• Inventors: Spackman, Stephen Philip
• Primary Examiner(s): BURKE, JEFF A
• Application Number:
  US12/506,400
• Publication Number:
  US 20110022825A1
• Time in Patent Office: 1,393 Days
• Field of Search: 707692- 93, 707692-693
• US Class Current: 707/692
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

In a method of linking to information in a deduplication data sequence, a branching point is identified. The branching point is a place where a branch data sequence diverges from a parent data sequence that has been previously stored in a data deduplication process. A signature value associated with a subsequence of the information represented in the branch data sequence is determined. A branch location where the information of the branch data sequence begins is identified. Link information is stored in association with the branching point. The link information is stored in a computer memory. The link information comprises a link to the branch location and also comprises a portion of the signature value.

Claims

1. A computer-implemented method of linking to information in a deduplication data sequence, said method comprising:

identifying a branching point where a branch data sequence diverges from a parent data sequence that has been previously stored in a data deduplication process;

determining a signature value associated with a subsequence of information represented in said branch data sequence;

identifying a branch location where said information of said branch data sequence begins; and

in association with said branching point, storing link information in a computer memory, wherein said link information comprises a link to said branch location and also comprises a portion of said signature value.

2. The computer-implemented method as recited in claim 1, further comprising:

during a follow-on deduplication activity involving reference to said branching point of said parent data sequence, comparing a second signature value associated with a next blocklet to be deduplicated in said follow-on deduplication activity to determine if said portion of said signature value matches with a like range of said second signature value; and

in the event of said portion matching, using said link information to branch to said branch location to continue with said follow-on deduplication activity.

3. The computer-implemented as recited in claim 1, further comprising:

identifying a returning point where said branch data sequence returns to said parent data sequence;

identifying a return location in said parent data sequence where said branch data sequence returns from said returning point to resume said parent data sequence;

determining a return location signature value of a blocklet of information represented at said return location; and

in association with said returning point, storing additional link information in said computer memory, wherein said additional link information comprises a link to said return location and also comprises a portion of said return location signature value.

4. The computer-implemented method as recited in claim 1, wherein said identifying a branching point where a branch data sequence diverges from a parent data sequence that has been previously stored in a data deduplication process comprises:

identifying an end point associated with the end of a cluster of stored deduplication information.

5. The method as recited in claim 1, wherein said determining a signature value associated with a subsequence of information represented in said branch data sequence comprises:

determining said signature value for a head of said branch data sequence.

6. The method as recited in claim 1, wherein said determining a signature value associated with a subsequence of information represented in said branch data sequence comprises:

determining said signature value for a tail of said branch data sequence.

7. The computer-implemented as recited in claim 1, wherein said storing link information in a computer memory comprises:

storing said link information in a cluster header of plurality of deduplication clusters that include said branching point.

8. The computer-implemented as recited in claim 1, wherein said storing said link information in said computer memory comprises:

storing a pointer in a cluster header for a plurality of deduplication clusters.

9. The computer-implemented as recited in claim 1, wherein said storing said link information in said computer memory comprises:

storing a pointer to a memory address that includes a head subsequence or a tail subsequence of said branch data sequence.

10. The computer-implemented method as recited in claim 1, wherein said storing link information in a computer memory, wherein said link information comprises a link to said branch location and a portion of said signature value comprises:

storing an entirety of said signature value as said portion of said signature value.

11. The computer-implemented method as recited in claim 1, wherein said storing link information in a computer memory, wherein said link information comprises a link to said branch location and a portion of said signature value comprises:

storing a subset of said signature value as said portion of said signature value.

12. A computer-implemented method of informed deduplication link information management, said method comprising:

in association with a diverging point from a data sequence, storing link information in a computer memory, wherein said link information comprises a link to a divergent location where information of a divergent data sequence begins diverging from said diverging point;

storing an updatable link value in association with said link information, wherein said link value is set to an initial level upon initial storage of said link information and updated over time as a function of whether the link information is successfully employed to link to a branch data sequence; and

using said link value to inform competitively managed retention of a plurality of link information stored in said computer memory.

13. The computer-implemented method as recited in claim 12, wherein said storing an updatable link value in association with said link information comprises:

storing said link value in a cluster header for a plurality of clusters of deduplication information, wherein said diverging point is included in one of said clusters.

14. The computer-implemented method as recited in claim 12, wherein said storing an updatable link value in association with said link information, wherein said link value is set to an initial level upon initial storage of said link information and updated over time as a function of whether the link information is successfully employed to link to a branch data sequence comprises:

incrementing said link value for each successful use of said link information; and

decrementing said link value as said link information ages with non-use.

15. The computer-implemented method as recited in claim 12, wherein said using said link value to inform competitively managed retention of a plurality of link information stored in said computer memory comprises:

determining a lowest valued link information from a plurality of stored link information; and

displacing said lowest valued link information to make room for new link information.

16. The computer-implemented method as recited in claim 15, wherein said displacing said low-valued link information to make room for new link information comprises:

displacing said lowest valued link information from a cluster header.

17. The computer-implemented method as recited in claim 15, wherein said displacing said low-valued link information to make room for new link information comprises:

deleting said lowest valued link information.

18. The computer-implemented method as recited in claim 15, wherein said displacing said low-valued link information to make room for new link information comprises:

moving said lowest valued link information to a secondary storage location.

19. A non-transitory computer-readable storage medium having instructions stored thereon for causing a computer processor to perform a method of linking to deduplication information, said method comprising instructions for:

identifying a branching point where a branch data sequence diverges from a parent data sequence that has been previously stored in a data deduplication process;

determining a signature value associated with a subsequence of information represented in said branch data sequence;

identifying a branch location where said information of said branch data sequence begins;

storing link information in a computer memory, wherein said link information comprises a link to said branch location and also comprises a portion of said signature value; and

storing an updatable link value in said computer memory, said link value providing a usefulness ranking for said link information.

20. The non-transitory computer-readable storage medium of claim 19, wherein said method further comprises instructions for:

using said link value to inform competitively managed retention of a plurality of link information stored in said computer memory.

21. The non-transitory computer-readable storage medium of claim 19, wherein said storing an updatable link value in said computer memory, said link value providing a usefulness ranking for said link information further comprises instructions for:

updating said link value over time based upon usefulness of said link information.

22. The non-transitory computer-readable storage medium of claim 19, wherein said determining a signature value associated with a subsequence of information represented in said branch data sequence comprises:

determining said signature value associated with a head subsequence of said information represented in said branch data sequence.

23. A deduplication link creation and management system, said system comprising:

a computer system;

a computer memory of said computer system;

a branching point identifier portion of said computer system, said branching point identifier configured for identifying a branching point where a branch data sequence diverges from a parent data sequence that has been previously stored in a data deduplication process;

a signature value determiner portion of said computer system, said signature value determiner portion configured for determining a signature value associated with a subsequence of information represented in said branch data sequence;

a branch location identifier portion of said computer system, said branch location identifier configured for identifying a branch location where said information of said branch data sequence begins;

a link information storer portion of said computer system, said link information storer configured for storing link information in said computer memory, wherein said link information comprises a link to said branch location and also comprises a portion of said signature value; and

a link value storer portion of said computer system, said link value storer configured for storing an updatable link value in said computer memory, said link value providing a usefulness ranking for said link information.

24. The system of claim 23, further comprising:

a link information manager portion of said computer system, said link information manager configured for using said link value to inform competitively managed retention of a plurality of link information stored in said computer memory.

25. The system of claim 23, further comprising:

a link value updater portion of said computer system, said link value updater configured for updating said link value over time based upon usefulness of said link information.