# US 2008/0077586 A1 · System and method for identifying and mitigating redundancies in stored data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0077586 A1
- Document ID: US20080077586A1
- Status: Published application
- Kind: A1
- Application number: 11/894,007
- Filed: 2007-08-16
- Published: 2008-03-27
- Earliest claimed: 2006-08-18
- Assignees: FalconStor, Inc.
- Inventors: Wai Lam
- Web page: https://patentgrep.com/patent/US20080077586A1

## CPC

- G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06)
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 16/174: Redundancy elimination performed by the file system (error detection or correction of the data by redundancy in operations G06F11/14)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In an example of an embodiment of the invention, a repeating pattern is identified within stored data comprising a plurality of data files, each data file comprising at least a header section and a data section stored in an unknown format. At least one occurrence of the repeating pattern is identified as a header section of a respective data file, and a data section of the respective data file is identified based, at least in part, on a location of the at least one occurrence of the repeating pattern. The identified data section of the respective data file is backed up. Systems are also disclosed.

## Claims

### Claim 1

A method to manage data, comprising:
identifying a repeating pattern within stored data comprising a plurality of data files, each data file comprising at least a header section and a data section stored in an unknown format;
identifying at least one occurrence of the repeating pattern as a header section of a respective data file;
identifying a data section of the respective data file based, at least in part, on a location of the at least one occurrence of the repeating pattern; and
backing up the identified data section of the respective data file.

### Claim 2 (depends on 1)

The method of claim 1, wherein the pattern comprises a sequence.

### Claim 3 (depends on 1)

The method of claim 1, wherein the stored data is maintained on a tape storage medium.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
generating a first digest representing the identified data section;
comparing the first digest to a set of second digests; and
if the first digest is not found in the set of second digests:
adding the first digest to the set of second digests;
backing up the identified data section; and
replacing the identified data section in the stored data by the first digest.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
generating a first digest representing the identified data section;
comparing the first digest to a set of second digests; and
if the first digest is found in the set of second digests:
replacing the identified data section in the stored data by the first digest.

### Claim 6

A method to manage data, comprising:
identifying a repeating pattern in data stored in a storage system;
associating the pattern with at least a first component of a data structure within the stored data;
identifying at least a second component of the data structure, based at least in part on the pattern; and
performing a selected data processing operation with respect to the data structure.

### Claim 7 (depends on 6)

The method of claim 6, wherein the pattern appears in a first location and repeats in at least a second location within the data.

### Claim 8 (depends on 7)

The method of claim 7, wherein the data is stored in a storage system.

### Claim 9 (depends on 8)

The method of claim 8, wherein the data stored in the storage system is stored in an unknown format.

### Claim 10 (depends on 8)

The method of claim 8, wherein the pattern indicates at least one characteristic of the first component chosen from the group consisting of: a location of the first component, a structure of the first component, and a length of the first component.

### Claim 11 (depends on 10)

The method of claim 10, wherein the data structure comprises at least one data file.

### Claim 12 (depends on 11)

The method of claim 11, wherein the first component comprises a header section of the at least one data file.

### Claim 13 (depends on 12)

The method of claim 12, wherein the pattern indicates a characteristic of the header section chosen from the group consisting of: a beginning of the header section and an end of the header section.

### Claim 14 (depends on 12)

The method of claim 12, wherein the second component comprises a data section of the at least one data file.

### Claim 15 (depends on 6)

The method of claim 6, wherein the storage system comprises a tape library.

### Claim 16 (depends on 6)

The method of claim 6, comprising:
storing at least a portion of the data structure in a second storage system.

### Claim 17 (depends on 16)

The method of claim 16, comprising:
backing up the at least a portion of the data structure in the second storage system.

### Claim 18 (depends on 6)

The method of claim 6, wherein the first component is stored at a first location, the method further comprising:
comparing at least one indicator of the second component to a set of second indicators; and
if the at least one indicator of the second component is not found in the set of second indicators:
storing the at least one indicator of the second component;
storing at least a portion of the data structure in a second storage location; and
replacing the at least a portion of the data structure stored in the storage system by the at least one indicator of the second component.

### Claim 19 (depends on 18)

The method of claim 18, wherein:
the at least one indicator of the second component comprises a first digest representing the second component;
the method comprising:
comparing the first digest to a set of second digests; and
if the first digest is not found in the set of second digests:
storing the first digest;
storing at least a portion of the data structure in a second storage location; and
replacing the at least a portion of the data structure stored in the storage system by the first digest.

### Claim 20 (depends on 6)

The method of claim 6, wherein the pattern comprises a format of the data.

### Claim 21 (depends on 6)

The method of claim 6, wherein the pattern comprises a sequence of values.

### Claim 22 (depends on 21)

The method of claim 21, wherein the sequence of values repeats identically within the data.

### Claim 23 (depends on 6)

The method of claim 6, comprising:
identifying at least a second component of the data structure, based at least in part on a location of the pattern.

### Claim 24 (depends on 6)

The method of claim 6, wherein each occurrence of the pattern comprises a sequence chosen from the group consisting of: a sequence of bits, and a sequence of bytes.

### Claim 25

A method to manage data structures, comprising:
identifying a repeating pattern within data stored in a first storage system;
identifying a data section associated with a data file stored in the first storage system, based at least in part on a location of the pattern;
computing a value based at least in part on the data section;
comparing the computed value to one or more second values stored in a database; and
if the computed value is not found in the database:
storing the computed value in the database;
storing the data section in a second storage system; and
replacing the data section stored in the first storage system by the computed value.

### Claim 26 (depends on 25)

The method of claim 25, further comprising:
if the computed value is found in the database:
replacing the data section stored in the first storage system by the computed value.

### Claim 27 (depends on 25)

The method of claim 25, wherein the pattern appears in a first location and repeats in at least a second location within the data.

### Claim 28 (depends on 27)

The method of claim 27, wherein the pattern comprises a header section of the data file.

### Claim 29 (depends on 27)

The method of claim 27, wherein the pattern comprises the data section of the data file.

### Claim 30 (depends on 27)

The method of claim 27, wherein the value comprises a hash value.

### Claim 31 (depends on 30)

The method of claim 30, wherein the first storage system comprises a virtual tape library.

### Claim 32 (depends on 25)

The method of claim 25, wherein each occurrence of the pattern comprises a sequence chosen from the group consisting of: a sequence of bits, and a sequence of bytes.

### Claim 33

An apparatus to manage data structures, comprising:
means for identifying a repeating pattern in data stored in a storage system;
means for associating the pattern with at least a first component of a data structure within the stored data;
means for identifying at least a second component of the data structure, based at least in part on a location of the pattern; and
means for performing a selected data processing operation with respect to the data structure.

### Claim 34

A system to manage data structures, comprising:
a memory located in a storage system, the memory being configured to store data; and
a processor configured to:
identify a repeating pattern in the data;
associate the pattern with at least a first component of a data structure within the stored data;
identify at least a second component of the data structure, based at least in part on the pattern; and
perform a selected data processing operation with respect to the data structure.

### Claim 35 (depends on 34)

The system of claim 34, wherein the pattern appears in a first location and repeats in at least a second location within the data.

### Claim 36 (depends on 35)

The system of claim 35, wherein the data is stored in the memory in an unknown format.

### Claim 37 (depends on 36)

The system of claim 36, wherein the pattern indicates at least one characteristic of the first component chosen from the group consisting of: a location of the first component, a structure of the first component, and a length of the first component.

### Claim 38 (depends on 37)

The system of claim 37, wherein the processor is configured to:
associate the pattern with at least a first component of at least one data file within the stored data.

### Claim 39 (depends on 38)

The system of claim 38, wherein the processor is configured to:
associate the pattern with at least a header section of the at least one data file.

### Claim 40 (depends on 39)

The system of claim 39, wherein the pattern indicates a characteristic of the header section chosen from the group consisting of: a beginning of the header section and an end of the header section.

### Claim 41 (depends on 39)

The system of claim 39, wherein the processor is configured to:
identify at least a data section of the at least one data file, based at least in part on a location of the pattern;

### Claim 42 (depends on 34)

The system of claim 34, wherein the memory is located in a tape library.

### Claim 43 (depends on 34)

The system of claim 34, wherein the processor is further configured to:
store at least a portion of the data structure in a second storage system.

### Claim 44 (depends on 43)

The system of claim 43, wherein the processor is configured to:
back up the at least a portion of the data structure in the second storage system.

### Claim 45 (depends on 34)

The system of claim 34, wherein the first component is stored at a first location, the processor being further configured to:
compare at least one indicator of the second component to a set of second indicators; and
if the at least one indicator of the second component is not found in the set of second indicators:
store the at least one indicator of the second component;
store at least a portion of the data structure in a second storage location; and
replace the at least a portion of the data structure stored in the storage system by the at least one indicator of the second component.

### Claim 46 (depends on 45)

The system of claim 45, wherein:
the at least one indicator of the second component comprises a first digest representing the second component;
the processor being configured to:
compare the first digest to a set of second digests; and
if the first digest is not found in the set of second digests:
store the first digest;
store at least a portion of the data structure in a second storage location; and
replace the at least a portion of the data structure stored in the storage system by the first digest.

### Claim 47 (depends on 34)

The system of claim 34, wherein the processor is further configured to:
identify a format of the data based at least in part on the pattern.

### Claim 48 (depends on 47)

The system of claim 47, wherein the pattern comprises a sequence of values.

### Claim 49 (depends on 48)

The system of claim 48, wherein the sequence of values repeats identically within the data.

### Claim 50 (depends on 34)

The system of claim 34, wherein the processor is configured to:
identify at least a second component of the data structure, based at least in part on a location of the pattern.

### Claim 51 (depends on 34)

The system of claim 34, wherein each occurrence of the pattern comprises a sequence chosen from the group consisting of: a sequence of bits, and a sequence of bytes.

### Claim 52

A system to manage data structures, comprising:
a memory located in a first storage system, the memory being configured to store data; and
a processor configured to:
identify a repeating pattern within data stored in the first storage system;
identify a data section associated with a data file stored in the first storage system, based at least in part on a location of the pattern;
compute a value based on the data section;
compare the computed value to one or more second values stored in a database; and
if the computed value is not found in the database:
store the computed value in the database;
store the data section in a second storage system; and
replace the data section stored in the first storage system by the computed value.

### Claim 53 (depends on 52)

The system of claim 52, wherein the processor is further configured to:
if the computed value is found in the database:
replace the data section stored in the first storage system by the computed value.

### Claim 54 (depends on 52)

The system of claim 52, wherein the pattern appears in a first location and repeats in at least a second location within the data.

### Claim 55 (depends on 54)

The system of claim 54, wherein the processor is further configured to:
associate the pattern with a header section of the data file.

### Claim 56 (depends on 54)

The system of claim 54, wherein the processor is further configured to:
associate the pattern with the data section of the data file.

### Claim 57 (depends on 54)

The system of claim 54, wherein the processor is configured to:
compute a hash value based on the data section.

### Claim 58 (depends on 57)

The system of claim 57, wherein the first storage system comprises a virtual tape library.

### Claim 59 (depends on 52)

The system of claim 52, wherein each occurrence of the pattern comprises a sequence chosen from the group consisting of: a sequence of bits, and a sequence of bytes.
