Content-based segmentation scheme for data compression in storage and transmission including hierarchical segment representation

• US 7,477,166 B2
• Filed: 08/22/2006
• Issued: 01/13/2009
• Est. Priority Date: 10/30/2002
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: McCanne, Steven, Demmer, Michael J.
• Primary Examiner(s): Nguyen; Linh V
• Application Number:
  US11/508,531
• Publication Number:
  US 20070018858A1
• Time in Patent Office: 875 Days
• Field of Search: 341 50-107, 707/100, 707/102, 707/200, 707/203
• US Class Current: 341/50
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In a coding system, input data within a system is encoded. The input data might include sequences of symbols that repeat in the input data or occur in other input data encoded in the system. The encoding includes determining a target segment size, determining a window size, identifying a fingerprint within a window of symbols at an offset in the input data, determining whether the offset is to be designated as a cut point and segmenting the input data as indicated by the set of cut points. For each segment so identified, the encoder determines whether the segment is to be a referenced segment or an unreferenced segment, replacing the segment data of each referenced segment with a reference label and storing a reference binding in a persistent segment store for each referenced segment, if needed. Hierarchically, the process can be repeated by grouping references into groups, replacing the grouped references with a group label, storing a binding between the grouped references and group label, if one is not already present, and repeating the process. The number of levels of hierarchy can be fixed in advanced or it can be determined from the content encoded.

Claims

1. A method for performing a backup of files, the method comprising:

receiving, at a backup system, a plurality of files to be backed up;

segmenting, with a segmenter of the backup system, each file into one or more segments;

forming a list for each file, wherein forming a list comprises;

(a) determining whether each segment is present in a segment store, wherein a segment that is present in the segment store has an assigned reference label;

(b) for each segment present in the segment store, adding to the list the assigned reference label; and

(c) for each segment not present in the segment store, assigning a reference label to the segment, storing the segment and the reference label, and adding the reference label to the list; and

storing, in a database of the near-line file system, an association between each file and the corresponding list.

2. The method of claim 1, wherein the plurality of files are received from a file server that is connected with a plurality of clients.

3. The method of claim 1, wherein the backup system is a near-line file system.

4. The method of claim 1, wherein the segment and its assigned reference label are both stored in the segment store.

5. The method of claim 1, wherein the reference labels are partly independent of content of a segment.

6. The method of claim 1, further comprising adding a time stamp to a list.

7. The method of claim 1, further comprising:

determining whether any sequence of segments is grouped as a reference group,

wherein forming a list further comprises;

(d) determining whether a reference group is present in the segment store, wherein the segment store includes a group label to the reference labels of the reference group present in the segment store;

(e) for each reference group present in the segment store, adding to the list the group label; and

(f) for each reference group not present in the segment store, assigning a reference label to a reference group segment not present in the segment store, storing the reference group segment and the reference label in the segment store, assigning a group label to the reference labels of the reference group, storing the group label in the segment store, and adding the group label to the list.

8. A backup system for performing a backup of files, the near-line backup system comprising:

an interface for receiving a plurality of files to be backed up;

a segmenter configured to segment each file;

an encoder for forming a list for each file, the encoder comprising;

(a) logic configured to determine whether each segment is present in a segment store, wherein a segment that is present in the segment store has an assigned reference label;

(b) for each segment present in the segment store, logic configured to add to the list the assigned reference label; and

(c) for each segment not present in the segment store, logic configured to assign a reference label to the segment, store the segment and the reference label, and add the reference label to the list; and

logic configured to store an association between each file and the corresponding list in a database of the near-line file system.

9. The backup system of claim 8, wherein the interface is configured to receive the files from a file server that is connected with a plurality of clients.

10. The backup system of claim 8, wherein the backup system is a near-line file system.

11. The backup system of claim 8, wherein the segment and its assigned reference label are both stored in the segment store.

12. The backup system of claim 8, wherein the reference labels are partly independent of content of a segment.

13. The backup system of claim 8, further comprising logic configured to add a time stamp to a list.

14. The backup system of claim 8, further comprising:

a sequence determiner for determining whether any sequence of segments is grouped as a reference group,

wherein the encoder further comprises;

(d) logic configured to determine whether a reference group is present in the segment store, wherein the segment store includes a group label to the reference labels of the reference group present in the segment store;

(e) for each reference group present in the segment store, logic configured to add to the list the group label; and

(f) for each reference group not present in the segment store, logic configured to assign a reference label to a reference group segment not present in the segment store, store the reference group segment and the reference label in the segment store, assign a group label to the reference labels of the reference group, store the group label in the segment store, and add the group label to the list.

15. The backup system of claim 8, wherein the interface is NFS.

16. The backup system of claim 8, wherein the interface is CIFS.

17. The backup system of claim 8, further comprising:

a decoder for decoding a list for each file, the decoder comprising logic configured to replace reference labels with segments of the file to recreate the file.