Granted Patent B2

US 11,232,074 · App. 16/878,516 · Granted Jan 25, 2022

Inventor: Philip Shilane (Newtown, PA)

Assignee: EMC IP Holding Company LLC

G06F16/1748G06F16/156G06F16/2282G06K9/6215

Abstract

Claims (114)

1. A method comprising:

receiving, at a deduplicated storage system, a search query comprising a search term, the deduplicated storage system storing data segmented into a plurality of segments, wherein fingerprints of the segments are generated referencing the segments, and metadata is maintained to allow reconstruction of the segmented data, the metadata comprising fingerprint listings indicating sequences according to which the segments should be reconstructed for an object;

reading the plurality of segments to determine whether a segment includes at least a portion of the search term;

identifying a full match when all of the search term is found in the segment;

recording full matches in a results table, each record of a full match comprising a fingerprint of the segment in which the full match was identified;

reading a first fingerprint listing associated with a first object;

querying the results table for fingerprints in the first fingerprint listing to determine whether the first object references any matches in the results table;

receiving from the results table a full match of the search term; and

identifying the first object as having the search term.

2. The method of claim 1 further comprising:

applying filter settings received with the search query to the metadata to obtain a subset of fingerprint listings to be read, the first fingerprint listing that is read thereby being a fingerprint listing of the first object that has meet the filter settings.

3. The method of claim 1 wherein the search term comprises at least one of a string or a byte sequence.

4. The method of claim 1 further comprising:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found; and

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match.

5. The method of claim 1 further comprising:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

combining the partial matches in the results table to form full matches, each record of a full match formed from combining the partial matches comprising a first fingerprint at which one of the beginning or ending portion of the search term was found, and a second fingerprint at which another of the beginning or ending portion of the search term was found;

reading a second fingerprint listing associated with a second object; and

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table.

6. The method of claim 1 further comprising:

identifying a partial match when a beginning portion of the search term is found at an end of the segment, an ending portion of the search term is found at a start of the segment, or a middle portion of the search term is found extending across the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found;

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match;

receiving from the results table the second partial match; and

querying the results table for a third fingerprint, next to the second fingerprint, in the second fingerprint listing to determine whether the results table comprises a third partial match of the search term that combines with the first and second partial matches.

7. The method of claim 1 further comprising:

recording in the results table an offset in the segment at which the search term is found;

during the reading a first fingerprint listing associated with the first object, maintaining a running total of segment sizes for segments having fingerprints in the first fingerprint listing that are being read; and

upon identifying the first object as having the search term, adding the offset in the segment at which the search term was found with the running total of segment sizes to report a position within the first object at which the search term was found.

8. The method of claim 1 further comprising:

receiving, at the deduplicated storage system, a second search query comprising a second search term; and

dynamically determining whether to execute the second search query by performing a search across deduplicated segments of the deduplicated storage system or by performing a search across logical objects of the deduplicated storage system,

wherein the dynamically determining comprises examining a deduplication ratio of the deduplicated storage system, a first estimated running time required to perform the search across the deduplicated segments, and a second estimated running time required to perform the search across the logical objects, and

wherein the search across the logical objects includes when two or more logical objects reference a same segment, reading the same segment a first time when a first logical object of the two or more logical objects is searched, and reading the same segment a second time when a second logical object of the two or more logical objects is searched.

9. The method of claim 1 further comprising:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified; and

dynamically selecting one of combining the partial matches in the results table to form full matches or not combining the partial matches in the results table to form full matches.

10. The method of claim 1 wherein the deduplicated storage system stores the segments as uncompressed individual segments, compressed individual segments, groups of uncompressed segments, or groups of compressed segments.

11. A system comprising: a processor, and memory storing one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:

receiving, at a deduplicated storage system, a search query comprising a search term, the deduplicated storage system storing data segmented into a plurality of segments, wherein fingerprints of the segments are generated referencing the segments, and metadata is maintained to allow reconstruction of the segmented data, the metadata comprising fingerprint listings indicating sequences according to which the segments should be reconstructed for an object;

reading the plurality of segments to determine whether a segment includes at least a portion of the search term;

identifying a full match when all of the search term is found in the segment;

recording full matches in a results table, each record of a full match comprising a fingerprint of the segment in which the full match was identified;

reading a first fingerprint listing associated with a first object;

querying the results table for fingerprints in the first fingerprint listing to determine whether the first object references any matches in the results table;

receiving from the results table a full match of the search term; and

identifying the first object as having the search term.

12. The system of claim 11 wherein the processor further carries out the steps of:

applying filter settings received with the search query to the metadata to obtain a subset of fingerprint listings to be read, the first fingerprint listing that is read thereby being a fingerprint listing of the first object that has meet the filter settings.

13. The system of claim 11 wherein the processor further carries out the steps of:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found; and

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match.

14. The system of claim 11 wherein the processor further carries out the steps of:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

combining the partial matches in the results table to form full matches, each record of a full match formed from combining the partial matches comprising a first fingerprint at which one of the beginning or ending portion of the search term was found, and a second fingerprint at which another of the beginning or ending portion of the search term was found;

reading a second fingerprint listing associated with a second object; and

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table.

15. The system of claim 11 wherein the processor further carries out the steps of:

identifying a partial match when a beginning portion of the search term is found at an end of the segment, an ending portion of the search term is found at a start of the segment, or a middle portion of the search term is found extending across the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found;

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match;

receiving from the results table the second partial match; and

querying the results table for a third fingerprint, next to the second fingerprint, in the second fingerprint listing to determine whether the results table comprises a third partial match of the search term that combines with the first and second partial matches.

16. A computer program product comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a method comprising:

receiving, at a deduplicated storage system, a search query comprising a search term, the deduplicated storage system storing data segmented into a plurality of segments, wherein fingerprints of the segments are generated referencing the segments, and metadata is maintained to allow reconstruction of the segmented data, the metadata comprising fingerprint listings indicating sequences according to which the segments should be reconstructed for an object;

reading the plurality of segments to determine whether a segment includes at least a portion of the search term;

identifying a full match when all of the search term is found in the segment;

recording full matches in a results table, each record of a full match comprising a fingerprint of the segment in which the full match was identified;

reading a first fingerprint listing associated with a first object;

querying the results table for fingerprints in the first fingerprint listing to determine whether the first object references any matches in the results table;

receiving from the results table a full match of the search term; and

identifying the first object as having the search term.

17. The computer program product of claim 16 wherein the method further comprises:

applying filter settings received with the search query to the metadata to obtain a subset of fingerprint listings to be read, the first fingerprint listing that is read thereby being a fingerprint listing of the first object that has meet the filter settings.

18. The computer program product of claim 16 wherein the method further comprises:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found; and

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match.

19. The computer program product of claim 16 wherein the method further comprises:

identifying a partial match when a beginning portion of the search term is found at an end of the segment or when an ending portion of the search term is found at a start of the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

combining the partial matches in the results table to form full matches, each record of a full match formed from combining the partial matches comprising a first fingerprint at which one of the beginning or ending portion of the search term was found, and a second fingerprint at which another of the beginning or ending portion of the search term was found;

reading a second fingerprint listing associated with a second object; and

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table.

20. The computer program product of claim 16 wherein the method further comprises:

identifying a partial match when a beginning portion of the search term is found at an end of the segment, an ending portion of the search term is found at a start of the segment, or a middle portion of the search term is found extending across the segment;

recording partial matches in the results table, each record of a partial match comprising a fingerprint of the segment in which the partial match was identified;

reading a second fingerprint listing associated with a second object;

querying the results table for fingerprints in the second fingerprint listing to determine whether the second object references any matches in the results table;

receiving from the results table a first partial match of the search term, the first partial match comprising a first fingerprint of a segment in which the first partial match was found;

querying the results table for a second fingerprint, next to the first fingerprint, in the second fingerprint listing to determine whether the results table comprises a second partial match of the search term that combines with the first partial match;

receiving from the results table the second partial match; and

querying the results table for a third fingerprint, next to the second fingerprint, in the second fingerprint listing to determine whether the results table comprises a third partial match of the search term that combines with the first and second partial matches.

Assignments (9)

Continuity (1)