# US 10,120,875 B1 · Method and system for detecting boundaries of data blocks for deduplication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,875 B1 - Document ID: US10120875B1 - Status: Granted - Kind: B1 - Application number: 14/558,626 - Filed: 2014-12-02 - Granted: 2018-11-06 - Earliest claimed: 2014-12-02 - Assignees: EMC IP Holding Company LLC - Applicants: EMC Corporation - Inventors: Abhinav Duggal; Anshita Agrawal - Web page: https://patentgrep.com/patent/US10120875B1 ## CPC - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) - G06F 16/1752: {based on file chunks} - G06F 11/1453: {using de-duplication of the data} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques for deduplicating data streams are described herein. According to one embodiment, a first data stream is received to be stored in a storage system, where the first data stream includes data blocks and each data block includes a header and a footer. A boundary detector is to detect boundaries of the data blocks by matching at least a portion of a header with a footer of each data block and a header of an adjacent data block. An anchoring unit is to anchor the first data stream based on the determined boundaries of the data blocks using a plurality of anchors. A deduplication engine is to deduplicate the first data stream into a plurality of deduplicated data segments based on the plurality of anchors. The deduplicated data segments are then stored in one or more persistent storage devices of the storage system. ## Claims ### Claim 1 A computer-implemented method for deduplicating data objects, the method comprising: receiving a first data stream to be stored in a storage system, the first data stream including a plurality of data blocks, wherein each data block includes a header and a footer; determining by a boundary detector boundaries of the data blocks by matching at least a portion of a header with a footer of each data block and matching the at least a portion of the header with a header of an adjacent data block; anchoring by an anchoring unit the first data stream based on the determined boundaries of the data blocks using a plurality of anchors; deduplicating by a deduplication engine the first data stream into a plurality of deduplicated data segments based on the plurality of anchors; and storing the deduplicated data segments in one or more persistent storage devices of the storage system. ### Claim 2 (depends on 1) The method of claim 1, further comprising: searching within a predetermined proximity of each determined boundary of the first data stream to identify one or more markers prior to anchoring the first data stream; and removing the one or more markers from the first data stream to generate a second data stream without the markers, wherein the anchoring by the anchoring unit is performed on the second data stream. ### Claim 3 (depends on 2) The method of claim 2, wherein searching within a predetermined area of each determined boundary of the first data stream comprises searching within a header area of each determined boundary of the first data stream to identify a marker based on a predetermined marker pattern. ### Claim 4 (depends on 1) The method of claim 1, wherein determining boundaries of the data blocks comprises: identifying a first header of a first of the data blocks of the first data stream based on a predetermined data pattern; and searching at least a first portion of content of the first header within a first proximity before a predetermined distance from the first header to identify content matching the first portion of the content of the first header. ### Claim 5 (depends on 4) The method of claim 4, wherein the first proximity before the predetermined distance represents a first footer of the first data block. ### Claim 6 (depends on 5) The method of claim 5, further comprising: determining whether a distance between the first header and the first footer is greater than a predetermined threshold; and performing a content-based anchoring on content between the first header and the first footer in response to determining that the distance between the first header and the first footer is greater than the predetermined threshold. ### Claim 7 (depends on 6) The method of claim 6, wherein the predetermined threshold represents a maximum deduplicated segment size of the storage system. ### Claim 8 (depends on 4) The method of claim 4, further comprising: if the matching content is found within the first proximity, searching at least a second portion of content of the first header within a second proximity after the predetermined distance to identify content matching the second portion of the content of the first header; and indicating that a boundary of a data block corresponding to the first header is confirmed. ### Claim 9 (depends on 8) The method of claim 8, wherein the second proximity after the predetermined distance is associated with a second header of a second data block as adjacent to the first data block. ### Claim 10 (depends on 8) The method of claim 8, further comprising: if the matching content is not found within the first proximity, adjusting the predetermined distance based on one of a plurality of distance candidates; and iteratively performing identifying the first header and searching within the first proximity based on the adjusted predetermined distance, wherein the plurality of distance candidates represents a list of possible data block sizes. ### Claim 11 A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of deduplicating data objects, the operations comprising: receiving a first data stream to be stored in a storage system, the first data stream including a plurality of data blocks, wherein each data block includes a header and a footer; determining by a boundary detector boundaries of the data blocks by matching at least a portion of a header with a footer of each data block and matching the at least a portion of the header with a header of an adjacent data block; anchoring by an anchoring unit the first data stream based on the determined boundaries of the data blocks using a plurality of anchors; deduplicating by a deduplication engine the first data stream into a plurality of deduplicated data segments based on the plurality of anchors; and storing the deduplicated data segments in one or more persistent storage devices of the storage system. ### Claim 12 (depends on 11) The non-transitory machine-readable medium of claim 11, wherein the operations further comprise: searching within a predetermined proximity of each determined boundary of the first data stream to identify one or more markers prior to anchoring the first data stream; and removing the one or more markers from the first data stream to generate a second data stream without the markers, wherein the anchoring by the anchoring unit is performed on the second data stream. ### Claim 13 (depends on 12) The non-transitory machine-readable medium of claim 12, wherein searching within a predetermined area of each determined boundary of the first data stream comprises searching within a header area of each determined boundary of the first data stream to identify a marker based on a predetermined marker pattern. ### Claim 14 (depends on 11) The non-transitory machine-readable medium of claim 11, wherein determining boundaries of the data blocks comprises: identifying a first header of a first of the data blocks of the first data stream based on a predetermined data pattern; and searching at least a first portion of content of the first header within a first proximity before a predetermined distance from the first header to identify content matching the first portion of the content of the first header. ### Claim 15 (depends on 14) The non-transitory machine-readable medium of claim 14, wherein the first proximity before the predetermined distance represents a first footer of the first data block. ### Claim 16 (depends on 15) The non-transitory machine-readable medium of claim 15, wherein the operations further comprise: determining whether a distance between the first header and the first footer is greater than a predetermined threshold; and performing a content-based anchoring on content between the first header and the first footer in response to determining that the distance between the first header and the first footer is greater than the predetermined threshold. ### Claim 17 (depends on 16) The non-transitory machine-readable medium of claim 16, wherein the predetermined threshold represents a maximum deduplicated segment size of the storage system. ### Claim 18 (depends on 14) The non-transitory machine-readable medium of claim 14, wherein the operations further comprise: if the matching content is found within the first proximity, searching at least a second portion of content of the first header within a second proximity after the predetermined distance to identify content matching the second portion of the content of the first header; and indicating that a boundary of a data block corresponding to the first header is confirmed. ### Claim 19 (depends on 18) The non-transitory machine-readable medium of claim 18, wherein the second proximity after the predetermined distance is associated with a second header of a second data block as adjacent to the first data block. ### Claim 20 (depends on 18) The non-transitory machine-readable medium of claim 18, wherein the operations further comprise: if the matching content is not found within the first proximity, adjusting the predetermined distance based on one of a plurality of distance candidates; and iteratively performing identifying the first header and searching within the first proximity based on the adjusted predetermined distance, wherein the plurality of distance candidates represents a list of possible data block sizes. ### Claim 21 A storage system, comprising: a processor; a memory coupled to the processor; a boundary detector to receive a first data stream, the first data stream including a plurality of data blocks, wherein each data block includes a header and a footer, and to determine boundaries of the data blocks by matching at least a portion of a header with a footer of each data block and matching the at least a portion of the header with a header of an adjacent data block; an anchoring unit to anchor the first data stream based on the determined boundaries of the data blocks using a plurality of anchors; a deduplication engine to deduplicate the first data stream into a plurality of deduplicated data segments based on the plurality of anchors; and one or more storage devices to store the deduplicated data segments. ### Claim 22 (depends on 21) The system of claim 21, wherein the boundary detector is to: search within a predetermined proximity of each determined boundary of the first data stream to identify one or more markers prior to anchoring the first data stream, and remove the one or more markers from the first data stream to generate a second data stream without the markers, wherein the anchoring by the anchoring unit is performed on the second data stream. ### Claim 23 (depends on 22) The system of claim 22, wherein searching within a predetermined area of each determined boundary of the first data stream comprises searching within a header area of each determined boundary of the first data stream to identify a marker based on a predetermined marker pattern. ### Claim 24 (depends on 21) The system of claim 21, wherein determining boundaries of the data blocks comprises: identifying a first header of a first of the data blocks of the first data stream based on a predetermined data pattern; and searching at least a first portion of content of the first header within a first proximity before a predetermined distance from the first header to identify content matching the first portion of the content of the first header. ### Claim 25 (depends on 24) The system of claim 24, wherein the first proximity before the predetermined distance represents a first footer of the first data block.