# US 2009/0271402 A1 · Deduplication of Data on Disk Devices Based on a Threshold Number of Sequential Blocks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2009/0271402 A1 - Document ID: US20090271402A1 - Status: Published application - Kind: A1 - Application number: 12/110,122 - Filed: 2008-04-25 - Published: 2009-10-29 - Earliest claimed: 2008-04-25 - Assignees: NetApp, Inc. - Inventors: Kiran Srinivasan; Garth Goodson; Kaladhar Voruganti - Web page: https://patentgrep.com/patent/US20090271402A1 ## CPC - 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 Deduplication of data on disk devices based on a threshold number (THN) of sequential blocks is described herein, the threshold number being two or greater. Deduplication may be performed when a series of THN or more received blocks (THN series) match a sequence of THN or more stored blocks (THN sequence), whereby a sequence comprises blocks stored on the same track of a disk device. Deduplication may be performed using a block-comparison mechanism comprising metadata entries of stored blocks and a mapping mechanism containing mappings of deduplicated blocks to their matching blocks. The mapping mechanism may be used to perform later read requests received for the deduplicated blocks. The deduplication described herein may reduce the read latency as the number of seeks between tracks may be reduced. Also, when a seek to a different track is performed, the seek time cost is spread over THN or more blocks. ## Claims ### Claim 1 A storage system for deduplicating blocks of data based on a predetermined threshold number (THN) of sequential blocks, the storage system comprising: a set of one or more disk devices for storing a plurality of blocks, each disk device comprising a set of tracks for storing blocks; and a deduplication layer configured for: receiving a set of blocks; determining whether a series of THN or more received blocks (THN series) matches a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising a series of blocks stored on a same track of a disk device, THN having a value of 2 or greater; and upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series using the matching THN sequence. ### Claim 2 (depends on 1) The storage system of claim 1, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence. ### Claim 3 (depends on 1) The storage system of claim 1, further comprising: comparison mechanism for storing metadata entries for a plurality of THN sequences, each metadata entry comprising metadata for a THN sequence and being indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence using the comparison mechanism. ### Claim 4 (depends on 3) The storage system of claim 3, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content. ### Claim 5 (depends on 3) The storage system of claim 3, wherein the comparison mechanism stores metadata entries for full or partial THN sequences, a partial THN sequence comprising a subset of THN or more blocks of a full THN sequence, a set of zero or more partial THN sequences being derived from each full THN sequence, each partial THN sequence in the set having a different combination of block size and offset from the beginning of the full THN sequence. ### Claim 6 (depends on 1) The storage system of claim 1, further comprising: a mapping mechanism for storing mappings of deduplicated blocks of the THN series to blocks of the matching THN sequence, wherein the deduplication layer is configured for deduplicating the blocks of the THN series by creating indexes to the blocks of the matching THN sequence in the mapping mechanism. ### Claim 7 (depends on 6) The storage system of claim 6, wherein: the mapping mechanism comprises a set of inodes or a metadata structure; and the mapping mechanism is used for performing a subsequent read request for the deduplicated blocks of the THN series, wherein the read request comprises a seek operation to the track storing the matching THN sequence and sequential reads of the blocks of the matching THN sequence comprising sequential reads of THN or more blocks. ### Claim 8 (depends on 6) The storage system of claim 6, wherein: the THN series comprises blocks to be written to a disk device using a write log comprising the data of the blocks and assigned address locations for the blocks; and the deduplication layer is further configured for deduplicating the blocks of the THN series by deleting the data of the blocks and the assigned address locations for the blocks in the write log. ### Claim 9 (depends on 6) The storage system of claim 6, wherein: the THN series comprises blocks stored on a disk device; and the deduplication layer is further configured for deduplicating the blocks of the THN series by deleting the blocks of the THN series stored on the disk device. ### Claim 10 (depends on 3) The storage system of claim 3, wherein: a set of non-deduplicated blocks comprises received blocks that are not deduplicated, each non-deduplicated block having an assigned address location indicating a location on a disk device for storage; the deduplication layer is further configured for: determining a set of zero or more THN sequences of non-deduplicated blocks, a THN sequence of non-deduplicated blocks comprising THN or more non-deduplicated blocks having consecutive assigned address locations; and for each THN sequence of non-deduplicated blocks, producing a metadata entry in the comparison mechanism. ### Claim 11 (depends on 1) The storage system of claim 1, wherein: the set of received blocks is received from a first application or a second application; the deduplication layer is further configured for: using a first threshold number for the set of received blocks received from the first application and a second threshold number for the set of received blocks received from the second application, the first and second threshold numbers being different in value. ### Claim 12 A storage system for deduplicating blocks of data for storage based on a predetermined threshold number (THN) of blocks, the storage system comprising: a set of one or more disk devices for storing a plurality of blocks, each block having an address location; and a deduplication layer configured for: receiving a set of blocks; determining whether a series of THN or more received blocks (THN series) match a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising blocks having consecutive address locations, THN having a value of 2 or greater; and upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series. ### Claim 13 (depends on 12) The storage system of claim 12, wherein: an address location comprises a logical block number (LBN); and a THN sequence comprises a set of THN or more stored blocks having consecutive LBNs. ### Claim 14 (depends on 12) The storage system of claim 12 wherein: each disk device comprises a set of tracks for storing blocks; and a sequence of blocks comprises a series of blocks stored on a same track of a disk device. ### Claim 15 (depends on 12) The storage system of claim 12, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence. ### Claim 16 (depends on 12) The storage system of claim 12, further comprising: comparison mechanism for storing metadata entries for a plurality of THN sequences, each metadata entry comprising metadata for a THN sequence and being indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence using the comparison mechanism. ### Claim 17 (depends on 16) The storage system of claim 16, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content. ### Claim 18 (depends on 12) The storage system of claim 12, further comprising: a mapping mechanism for storing mappings of deduplicated blocks of the THN series to blocks of the matching THN sequence, wherein the deduplication layer is configured for deduplicating the blocks of the THN series by creating indexes to the blocks of the matching THN sequence in the mapping mechanism. ### Claim 19 A storage system for deduplicating blocks of data based on a predetermined threshold number (THN) of sequential blocks, the storage system comprising: a set of one or more disk devices for storing a plurality of blocks, each disk device comprising a set of tracks for storing blocks; a deduplication layer configured for: receiving a set of blocks; using a comparison mechanism, determining whether a series of THN or more received blocks (THN series) matches a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising a series of blocks stored on a same track of a disk device, THN having a value of 2 or greater; and upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series using the matching THN sequence; and the comparison mechanism for storing metadata entries for a plurality of THN sequences comprising full or partial THN sequences, a partial THN sequence comprising a subset of THN or more blocks of a full THN sequence, a set of zero or more partial THN sequences being derived from each full THN sequence, each partial THN sequence in the set having a different combination of block size and offset from the beginning of the full THN sequence. ### Claim 20 (depends on 19) The storage system of claim 19, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence. ### Claim 21 (depends on 19) The storage system of claim 19, wherein each metadata entry comprises metadata for a THN sequence and is indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence. ### Claim 22 (depends on 21) The storage system of claim 21, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content.