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

• US 7,116,249 B2
• Filed: 09/08/2005
• Issued: 10/03/2006
• Est. Priority Date: 10/30/2002
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: NBT Technology, Inc.
• Inventors: McCanne, Steven, Demmer, Michael J.
• Primary Examiner(s): Jeanpierre, Peguy
• Assistant Examiner(s): Lauture, Joseph
• Application Number:
  US11/223,789
• Publication Number:
  US 20060061495A1
• Time in Patent Office: 390 Days
• Field of Search: 341/51, 341/50, 341/106, 715/744, 709/203, 395/200.33
• 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 storing data, comprising:

receiving a file from a client at a server;

segmenting the file into one or more segments;

forming a list, comprising;

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;

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

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 an association between the file and the list.

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

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

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

5. The method of claim 1, wherein the server is a unix file system (UFS), and wherein a directory entry in the UFS for a file references the segment store.

6. 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;

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;

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

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.

7. A system for storing data, comprising:

a server for receiving a file from a client;

a segmenter configured to segment the file;

an encoder for forming a list, comprising;

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;

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

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 the file and the list.

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

9. The system of claim 7, wherein the reference labels are partly independent of content of a segment.

10. The system of claim 7, further comprising logic configured to add a time stamp to the list.

11. The system of claim 7, wherein the server is a unix file system (UFS), wherein a directory entry in the UFS for a file references the segment store.

12. The system of claim 7, further comprising:

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

wherein the encoder further comprises;

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;

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

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.

13. A method for retrieving data, comprising:

receiving a request for a file from a client at a server;

retrieving a list including reference labels to segments of the file, wherein the list is associated with the file;

decoding the list, comprising;

replacing reference labels with segments of the file; and

sending the file from the server to the client.

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

15. The method of claim 13, wherein the retrieved list has a time stamp that is greatest time that other lists associated with the file.

16. The method of claim 13, wherein the request includes a specified time stamp, and wherein the retrieved list has the greatest time stamp that is less than or equal to the specified time stamp.

17. The method of claim 13, wherein the server is a unix file system (UFS), wherein a directory entry in the UFS for a file references the segment store.

18. The method of claim 13, wherein the list includes a group label to reference labels to segments of the file, and wherein decoding the list further comprises replacing a group label with the segments to which the reference labels refer.

19. A system for storing files, comprising:

a front-end file system for receiving from a client a file command for a file, wherein the front-end file system includes a front-end file server;

a back-end storage system including

logic to segment the file; and

a segment store for storing the segments;

a network file system interface for sending or receiving contents of the file between the front-end file system and the back-end storage system.

20. The system of claim 19, wherein the network file system interface is NFS.

21. The system of claim 19, wherein the network file system interface is CIFS.

22. The system of claim 19, wherein the front-end file system caches file data from the segment store when the file is being accessed by the client.

23. The system of claim 19, wherein the file is constructed from data received at the front-end file system from the segment store when the client opens the file.

24. The system of claim 19, wherein the file is sent from the front-end file system to a representation in the segment store when the client closes the file.

25. A method for storing files, comprising:

receiving, at a front-end file system from a client, a file command for a file, wherein the front-end file system includes a front-end file server;

based on the file command, using a network file system interface to transfer contents of the file between the front-end file system and a back-end storage system;

segmenting the file at the back-end storage system; and

maintaining a storage of the segments in a segment store of the back-end storage system.

26. The system of claim 25, wherein the network file system interface is NFS.

27. The system of claim 25, wherein the network file system interface is CIFS.

28. The method of claim 25, further comprising caching file data from the segment store at the front-end file system when the file is being accessed by the client.

29. The method of claim 25, further comprising constructing the file from data received at the front-end file system from the segment store when the client opens the file.

30. The method of claim 25, further comprising sending the file from the front-end file system to a representation in the segment store when the client closes the file.